Efficient evaluation of right-, left-, and multi-linear rules
Jeff Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey David Ullman · ACM SIGMOD Record · 1989
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.