Compiling Separable Recursions
Report ID: TR-140-88Author: Naughton, Jeffrey F.
Date: 1988-03-00
Pages: 28
Download Formats: |PDF|
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).