Skip to main content

Commutativity and its Role in the Processing of Linear Recursion

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.

Citation
Yannis Ioannidis, "Commutativity and its Role in the Processing of Linear Recursion ", Journal of Logic Programming, Vol. 14, No. 3-4, Nov. 1992, pp. 223-252. (Expanded version of the VLDB '89 paper), 1992
TAGS
Access
Unknown
Published at
Journal of Logic Programming, Vol. 14, No. 3-4, Nov. 1992, pp. 223-252. Expanded version of the VLDB '89 paper
Related research area
No related research area
Related Organizations
No related organizations