Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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).

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/147

[2] ftp://ftp.cs.princeton.edu/techreports/1988/140.pdf