Compiling Separable Recursions

Abstract:

In this paper we consider evaluating queries on relations defined by a combination of recursive rules. We first define separable recursions. We then give a specialized algorithm for evaluating selections on separable recursions. Like the Magic Sets and Counting algorithms, this algorithm uses selection
constants to avoid examining irrelevant portions of the database; however, on some simple recursions this algorithm is O(n), whereas the Magic Sets algorithm is omega(n2) and the Generalized Counting Method is omega(2n).