|
TR-140-88
Compiling Separable Recursions |
|
| Authors: | Naughton, Jeffrey F. |
| Date: | March 1988 |
| Pages: | 28 |
| Download Formats: | [PDF] |
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). |
|