Commutativity and its role in the processing of linear recursion

AbstractWe 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