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: 2506
Venue: SIGMOD
Year: 1989
Pagerank: 9.4809066e-05
Overall Rank: 1,921 | 86.83%
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
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010965236
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
3,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	7.1421254e-05
4,099	Argument Reduction by Factoring	1989	VLDB	6.9030568e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05
7,867	ForBackBench: A Benchmark for Chasing vs. Query-Rewriting	2022	VLDB	5.5277527e-05
8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.5028526e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05
12,810	Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases	2003	PODS	5.093636e-05
12,939	Binding Propagation in Disjunctive Databases	1998	VLDB	5.093636e-05
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
344	On the Power of Magic	1987	PODS	0.00020659405
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
9,503	Counting Methods for Cyclic Relations	1988	PODS	5.2586367e-05

Semantically Similar Papers

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