Efficient Evaluation of Right-, Left-, and Multi-Linear Rules

Summary: Efficient evaluation of recursive queries via a rewriting phase (like magic sets) and semi-naive bottom-up evaluation. Yields O(n) speedup over magic sets on a broad class of recursions by arity-reducing the recursive predicates in transformed rules. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hca9d2ab4e562881c
Venue: SIGMOD
Year: 1989
Pagerank: 9.2371562e-05
Overall Rank: 1,986 | 86.69%
DOI: 10.1145/67544.66948

Incoming Non-self Citations Over Time

Authors

1. J. F. Naughton (Princeton University)
2. R. Ramakrishnan (IBM; University of Wisconsin)
3. Y. Sagiv (Hebrew University; Stanford University)
4. J. D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{naughton_sigmod89,
        title = {{Efficient Evaluation of Right-, Left-, and Multi-Linear Rules}},
        author = {Naughton, J. F. and Ramakrishnan, R. and Sagiv, Y. and Ullman, J. D.},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66948},
        url = {https://dl.acm.org/doi/10.1145/67544.66948},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
1,423	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010696781
3,030	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7156987e-05
3,326	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4103766e-05
3,567	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.1826291e-05
3,685	Overbound and Right-Linear Queries	1991	PODS	7.081251e-05
3,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9565167e-05
4,206	Argument Reduction by Factoring	1989	VLDB	6.722747e-05
5,073	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2738154e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05
8,055	ForBackBench: A Benchmark for Chasing vs. Query-Rewriting	2022	VLDB	5.3833071e-05
8,218	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3595692e-05
10,368	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0064651e-05
13,147	Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases	2003	PODS	4.9605343e-05
13,276	Binding Propagation in Disjunctive Databases	1998	VLDB	4.9605343e-05
13,461	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058816744
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.0002391304
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
353	On the Power of Magic	1987	PODS	0.0002014941
2,078	One-Sided Recursions	1987	PODS	9.0607099e-05
3,722	Compiling Separable Recursions	1988	SIGMOD	7.0503269e-05
9,724	Counting Methods for Cyclic Relations	1988	PODS	5.121278e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	353	On the Power of Magic	1987	PODS
2	6,149	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
3	3,722	Compiling Separable Recursions	1988	SIGMOD
4	3,685	Overbound and Right-Linear Queries	1991	PODS
5	4,501	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
6	1,443	Magic is Relevant	1990	SIGMOD
7	7,300	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
8	6,894	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
9	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	3,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB