Compiling Separable Recursions
|Authors:||Naughton, Jeffrey F.|
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).