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
2445
Venue
SIGMOD
Year
1989
Pagerank
9.689916e-05
Overall Rank
2,048 | 85.77%
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
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
2,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
3,414 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1172834e-05
3,417 Overbound and Right-Linear Queries 1991 PODS 7.116211e-05
3,589 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9387274e-05
4,179 Argument Reduction by Factoring 1989 VLDB 6.3751001e-05
5,267 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 5.5930569e-05
6,881 Modular Acyclicity and Tail Recursion in Logic Programs 1991 PODS 4.8929836e-05
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
7,797 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 4.6438053e-05
11,056 Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers 2024 VLDB 4.1905499e-05
12,626 Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases 2003 PODS 4.1905499e-05
12,755 Binding Propagation in Disjunctive Databases 1998 VLDB 4.1905499e-05
12,939 Factoring Augmented Regular Chain Programs 1990 VLDB 4.1905499e-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.00099936325
157 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.0004048407
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
359 On the Power of Magic 1987 PODS 0.00025830228
1,611 One-Sided Recursions 1987 PODS 0.00011146101
3,556 Compiling Separable Recursions 1988 SIGMOD 6.9712392e-05
9,128 Counting Methods for Cyclic Relations 1988 PODS 4.3866751e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
359 On the Power of Magic 1987 PODS 0.00025830228
6,253 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.1318715e-05
3,556 Compiling Separable Recursions 1988 SIGMOD 6.9712392e-05
3,417 Overbound and Right-Linear Queries 1991 PODS 7.116211e-05
3,990 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5536618e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
7,069 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.8380576e-05
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
3,589 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9387274e-05