Database Paper Browser

Back to papers

An Amateur's Introduction to Recursive Query Processing Strategies

Summary: Survey and comparison of recursive query processing strategies for Horn-clause queries in relational DBs, limited to evaluable predicates without function symbols. Presents a framework: characterize strategies, ranges, examples, and analytical performance via cost curves and closed-form solutions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2292
Venue
SIGMOD
Year
1986
Pagerank
0.00056010993
Overall Rank
79 | 99.46%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 77 citing papers.

Rank Citing Paper Year Venue Pagerank
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
359 On the Power of Magic 1987 PODS 0.00025830228
408 HaLoop: Efficient Iterative Data Processing on Large Clusters 2010 VLDB 0.00023939456
569 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019912758
772 Efficient Pattern Matching over Event Streams 2008 SIGMOD 0.00016790632
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
1,326 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00012571381
1,381 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 0.00012271947
1,420 SchemaSQL - A Language for Interoperability in Relational Multi-database Systems 1996 VLDB 0.00012068815
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
1,450 Theory of Database Queries (Extended Abstract) 1988 PODS 0.00011926567
1,550 ODE (Object Database and Environment): The Language and the Data Model 1989 SIGMOD 0.00011396754
1,611 One-Sided Recursions 1987 PODS 0.00011146101
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,681 GUPT: Privacy Preserving Data Analysis Made Easy 2012 SIGMOD 0.00010922454
1,687 Automata Theory for Database Theoreticians 1989 PODS 0.0001090256
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
1,997 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.837483e-05
2,087 A Framework for the Parallel Processing of Datalog Queries 1990 SIGMOD 9.5715836e-05
2,179 Spinning Fast Iterative Data Flows 2012 VLDB 9.3632007e-05
2,395 A Method for Change Computation in Deductive Databases 1992 VLDB 8.889951e-05
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
2,528 Pregelix: Big(ger) Graph Analytics on A Dataflow Engine 2015 VLDB 8.5953347e-05
2,740 Database Theory: Past and Future 1987 PODS 8.1989773e-05
2,790 An Axiomatic Approach to Deciding Query Safety in Deductive Databases 1988 PODS 8.1203289e-05
3,012 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7129076e-05
3,350 Efficiently Supporting Procedures In Relational Database Systems 1987 SIGMOD 7.1867845e-05
3,414 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1172834e-05
3,860 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6864693e-05
3,986 CLASSIC: A Structural Data Model for Objects 1989 SIGMOD 6.5574084e-05
3,990 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5536618e-05
4,138 Safety of Datalog Queries over Infinite Databases 1989 PODS 6.4127061e-05
4,251 Hypothetical Datalog: Negation and Linear Recursion 1989 PODS 6.3149914e-05
4,310 Integrity Constraints Checking In Deductive Databases 1991 VLDB 6.2824978e-05
4,367 Distributed Processing Of Logic Programs 1988 SIGMOD 6.2423944e-05
4,440 Magic Counting Methods 1987 SIGMOD 6.180671e-05
4,479 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 6.1439609e-05
5,005 Efficient Main Memory Data Management Using the DBGraph Storage Model 1990 VLDB 5.7599923e-05
5,183 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6368566e-05
5,191 Storage Reclamation in Object Oriented Database Systems 1987 SIGMOD 5.6331612e-05
5,267 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 5.5930569e-05
5,347 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 5.555803e-05
5,629 Datalog and Emerging Applications: An Interactive Tutorial 2011 SIGMOD 5.4018902e-05
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05
5,699 PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics 2013 VLDB 5.3655096e-05
5,927 Parallelizing Datalog Programs by Generalized Pivoting 1991 PODS 5.2666195e-05
6,412 Optimizing Existential Datalog Queries 1988 PODS 5.0668361e-05
6,465 Research Directions in Object-Oriented Database Systems 1990 PODS 5.0464278e-05
6,514 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.0273291e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
459 CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract) 1986 PODS 0.00022684266
637 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00018812264
1,552 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011393892
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,109 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5283567e-05
3,990 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5536618e-05
12,931 Semigroup techniques in recursive query optimization 1990 PODS 4.1905499e-05
12,972 Classification Of Recursive Formulas In Deductive Databases 1988 SIGMOD 4.1905499e-05
359 On the Power of Magic 1987 PODS 0.00025830228
14,275 On Analogical Query Processing in Logic Database 1986 VLDB -
5,754 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3391931e-05
12,995 Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy 1987 VLDB 4.1905499e-05
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
1,552 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011393892