Database Paper Browser

Back to papers

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
2444
Venue
SIGMOD
Year
1989
Pagerank
9.699257e-05
Overall Rank
2,042 | 85.80%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
3,413 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1240395e-05
3,414 Overbound and Right-Linear Queries 1991 PODS 7.1232056e-05
3,585 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9454028e-05
4,178 Argument Reduction by Factoring 1989 VLDB 6.3812002e-05
5,259 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 5.5984356e-05
6,876 Modular Acyclicity and Tail Recursion in Logic Programs 1991 PODS 4.8977465e-05
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
7,795 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 4.6482625e-05
11,053 Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers 2024 VLDB 4.1945683e-05
12,617 Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases 2003 PODS 4.1945683e-05
12,746 Binding Propagation in Disjunctive Databases 1998 VLDB 4.1945683e-05
12,929 Factoring Augmented Regular Chain Programs 1990 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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.0010066783
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
365 On the Power of Magic 1987 PODS 0.00025585898
673 One-Sided Recursions 1987 PODS 0.00018348841
3,553 Compiling Separable Recursions 1988 SIGMOD 6.9779134e-05
7,156 Counting Methods for Cyclic Relations 1988 PODS 4.8145046e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
365 On the Power of Magic 1987 PODS 0.00025585898
6,254 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.1368042e-05
3,553 Compiling Separable Recursions 1988 SIGMOD 6.9779134e-05
3,414 Overbound and Right-Linear Queries 1991 PODS 7.1232056e-05
3,999 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5469939e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
7,075 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.842703e-05
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
3,585 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9454028e-05