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
2291
Venue
SIGMOD
Year
1986
Pagerank
0.00057043861
Overall Rank
77 | 99.47%
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
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
365 On the Power of Magic 1987 PODS 0.00025585898
413 HaLoop: Efficient Iterative Data Processing on Large Clusters 2010 VLDB 0.00023904409
566 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019970535
673 One-Sided Recursions 1987 PODS 0.00018348841
776 Efficient Pattern Matching over Event Streams 2008 SIGMOD 0.00016799754
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
1,339 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00012492597
1,381 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 0.00012283951
1,422 SchemaSQL - A Language for Interoperability in Relational Multi-database Systems 1996 VLDB 0.00012056887
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
1,448 Theory of Database Queries (Extended Abstract) 1988 PODS 0.00011938045
1,468 ODE (Object Database and Environment): The Language and the Data Model 1989 SIGMOD 0.00011846499
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
1,681 GUPT: Privacy Preserving Data Analysis Made Easy 2012 SIGMOD 0.00010929746
1,688 Automata Theory for Database Theoreticians 1989 PODS 0.00010913301
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
1,991 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.84713e-05
2,079 A Framework for the Parallel Processing of Datalog Queries 1990 SIGMOD 9.5979932e-05
2,172 Spinning Fast Iterative Data Flows 2012 VLDB 9.3706587e-05
2,397 A Method for Change Computation in Deductive Databases 1992 VLDB 8.8979335e-05
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
2,529 Pregelix: Big(ger) Graph Analytics on A Dataflow Engine 2015 VLDB 8.5940768e-05
2,735 Database Theory: Past and Future 1987 PODS 8.2069893e-05
2,786 An Axiomatic Approach to Deciding Query Safety in Deductive Databases 1988 PODS 8.1283801e-05
3,010 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7205569e-05
3,346 Efficiently Supporting Procedures In Relational Database Systems 1987 SIGMOD 7.1924206e-05
3,413 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1240395e-05
3,855 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6953401e-05
3,984 CLASSIC: A Structural Data Model for Objects 1989 SIGMOD 6.5634369e-05
3,999 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5469939e-05
4,136 Safety of Datalog Queries over Infinite Databases 1989 PODS 6.4188795e-05
4,255 Hypothetical Datalog: Negation and Linear Recursion 1989 PODS 6.3212356e-05
4,317 Integrity Constraints Checking In Deductive Databases 1991 VLDB 6.2885419e-05
4,370 Distributed Processing Of Logic Programs 1988 SIGMOD 6.2486359e-05
4,555 Magic Counting Methods 1987 SIGMOD 6.0891017e-05
4,732 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 5.9639609e-05
5,004 Efficient Main Memory Data Management Using the DBGraph Storage Model 1990 VLDB 5.76478e-05
5,180 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6422249e-05
5,189 Storage Reclamation in Object Oriented Database Systems 1987 SIGMOD 5.638567e-05
5,259 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 5.5984356e-05
5,515 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 5.4636431e-05
5,620 Datalog and Emerging Applications: An Interactive Tutorial 2011 SIGMOD 5.407079e-05
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
5,688 PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics 2013 VLDB 5.3702808e-05
5,925 Parallelizing Datalog Programs by Generalized Pivoting 1991 PODS 5.2717743e-05
6,417 Optimizing Existential Datalog Queries 1988 PODS 5.0717071e-05
6,473 Research Directions in Object-Oriented Database Systems 1990 PODS 5.0509826e-05
6,518 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.0321577e-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.0010066783
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
452 CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract) 1986 PODS 0.00022799064
632 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00018923134
1,529 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011496686
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,110 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5315487e-05
3,999 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5469939e-05
12,921 Semigroup techniques in recursive query optimization 1990 PODS 4.1945683e-05
12,962 Classification Of Recursive Formulas In Deductive Databases 1988 SIGMOD 4.1945683e-05
365 On the Power of Magic 1987 PODS 0.00025585898
14,261 On Analogical Query Processing in Logic Database 1986 VLDB -
5,743 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3442345e-05
12,984 Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy 1987 VLDB 4.1945683e-05
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
1,529 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011496686