Efficient Evaluation of Multiple Linear Recursions

A multiple linear (ML) recursion is a recursion which consists of multiple linear recursive rules and one or more nonrecursive rules. ML recursions can be classified into two classes: side-coherent and non-side-coherent. This paper studies the efficient evaluation of side-coherent ML recursions, which can be further classified into three types: (I) multiple one-sided, (II) multiple balanced k-sided, and (III) multiple mixed k-sided. New techniques are developed by integrating the existing single-linear recursive query evaluation methods with the idea of side-relation unioned processing, which leads to a set of efficient query evaluation algorithms such as a side-relation unioned transitive closure algorithm for the processing of Type I ML recursions, and a generalized side-relation unioned magic sets method for the processing of Types II and III ML recursions. Therefore the evaluation of ML recursions can be mapped to the framework of the evaluation of single linear recursions. Previously developed techniques for the evaluation of single linear recursions, such as the selection of processing strategies for queries with complex instantiations and inquiries, can be applied to the evaluation of ML recursions as well.