A STUDY ON THE STRUCTURE OF LINEAR RECURSION

We study a general class of single linear recursions and the propertie s of their expansions by analyzing the structures of the recursions. W e show that the expansions of a linear recursion of this class are ver y regular in that the variable connections are heavily shared and chan ge periodically with respect to the expansions. The variable connectio ns can be precisely characterized as static bindings and chain connect ions. We conclude that a single linear recursion under our assumptions either is bounded or can be expressed as chain recursions. This study contributes to query processing, because it provides the basis for ru le compilation as a general and powerful technique for query processin g. Combined with query information, the expansion properties of the re cursion provide optimized query-processing plans.