Efficient evaluation of right-, left-, and multi-linear rules
JF Naughton, R Ramakrishnan, Y Sagiv… - ACM SIGMOD …, 1989 - dl.acm.org
ACM SIGMOD Record, 1989•dl.acm.org
We present an algorithm for the efficient evaluation of a useful subset of recursive queries.
Like the magic sets transformation, the algorithm consists of a rewriting phase followed by
semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of
recursions, this algorithm achieves a factor of Ο (n) speedup over magic sets. Intuitively, the
transformations in this algorithm achieve their performance by reducing the arity of the
recursive predicates in the transformed rules.
Like the magic sets transformation, the algorithm consists of a rewriting phase followed by
semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of
recursions, this algorithm achieves a factor of Ο (n) speedup over magic sets. Intuitively, the
transformations in this algorithm achieve their performance by reducing the arity of the
recursive predicates in the transformed rules.
We present an algorithm for the efficient evaluation of a useful subset of recursive queries. Like the magic sets transformation, the algorithm consists of a rewriting phase followed by semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of recursions, this algorithm achieves a factor of Ο(n) speedup over magic sets. Intuitively, the transformations in this algorithm achieve their performance by reducing the arity of the recursive predicates in the transformed rules.