Commutativity and its Role in the Processing of Linear Recursion
Yannis Ioannidis
Date published: 
Published In: 
Journal of Logic Programming, Vol. 14, No. 3-4, Nov. 1992, pp. 223-252. (Expanded version of the VLDB '89 paper)
Journal Article

We investigate the role of commutativity in query processing of linear recursion. We give a sufficient condition for two linear, function-free, and constant-free rules to commute. The condition depends on the form of the rules themselves. For a restricted class of rules, we show that the condition is necessary and sufficient and can be tested in polynomial time in the size of the rules. Using the algebraic structure of such rules, we study the relationship of commutativity with several other properties of linear recursive rules and show that it is closely related to the important special classes of separable recursion and recursion with recursively redundant predicates.

Related files: 

MaDgIK 2009-2018