Compiling separable recursions
JF Naughton - ACM SIGMOD Record, 1988 - dl.acm.org
ACM SIGMOD Record, 1988•dl.acm.org
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 Generalized Magic Sets and
Generalized Counting algorithms, thus algorithm uses selection constants to avoid
examining irrelevant portions of the database, however, on some simple recursions this
algorithm is Ο (n), whereas Generalized Magic Sets is Ω (n 2) and Generalized Counting is …
recursive rules. We first define separable recursions. We then give a specialized algorithm
for evaluating selections on separable recursions. Like the Generalized Magic Sets and
Generalized Counting algorithms, thus algorithm uses selection constants to avoid
examining irrelevant portions of the database, however, on some simple recursions this
algorithm is Ο (n), whereas Generalized Magic Sets is Ω (n 2) and Generalized Counting is …
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 Generalized Magic Sets and Generalized Counting algorithms, thus algorithm uses selection constants to avoid examining irrelevant portions of the database, however, on some simple recursions this algorithm is Ο(n), whereas Generalized Magic Sets is Ω(n2) and Generalized Counting is Ω(2n)