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: hc4f51adc9875f0e1
Venue: SIGMOD
Year: 1986
Pagerank: 0.00038009523
Overall Rank: 67 | 99.56%
DOI: 10.1145/16894.16859

Incoming Non-self Citations Over Time

Authors

1. Francois Bancilhon (Microelectronics And Technology Computer Corporation)
2. Raghu Ramakrishnan (Microelectronics And Technology Computer Corporation; University of Texas)

BibTeX Citation

@inproceedings{bancilhon_sigmod86,
        title = {{An Amateur's Introduction to Recursive Query Processing Strategies}},
        author = {Bancilhon, Francois and Ramakrishnan, Raghu},
        series = {{SIGMOD} '86},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/16894.16859},
        url = {https://dl.acm.org/doi/10.1145/16894.16859},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 77 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,871	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.6597986e-05
6,892	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.6541068e-05
7,448	A Fix for the Fixation on Fixpoints	2023	CIDR	5.5239801e-05
7,576	A Generalized Transitive Closure for Relational Queries	1988	PODS	5.4924986e-05
8,051	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3992494e-05
8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.3925529e-05
8,148	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD	5.3906029e-05
8,481	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.3330859e-05
8,483	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	5.3327301e-05
8,549	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	5.3171056e-05
8,937	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	5.2559789e-05
8,995	Compiling Query Constraints	1994	PODS	5.2414297e-05
10,159	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.0690887e-05
10,196	Ariadne: Online Provenance for Big Graph Analytics	2019	SIGMOD	5.0623376e-05
10,334	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0254535e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05
13,100	Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases	2003	PODS	4.9793485e-05
13,310	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9793485e-05
13,366	Learning Efficient Query Processing Strategies	1992	PODS	4.9793485e-05
13,373	Implementing Deductive Databases by Linear Programming	1992	PODS	4.9793485e-05
13,423	Attribute Agreement	1989	PODS	4.9793485e-05
13,448	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.9793485e-05
13,450	A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing	1988	SIGMOD	4.9793485e-05
13,456	Fixed-point semantics and the representation of algorithms on large data	1988	VLDB	4.9793485e-05
13,469	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.9793485e-05
13,472	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	4.9793485e-05
13,476	An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments	1987	VLDB	4.9793485e-05

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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00023995155
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018227953
863	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00013392127
1,079	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00012135519
2,099	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.0515975e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,154	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
2	4,479	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
3	13,406	Semigroup techniques in recursive query optimization	1990	PODS
4	13,448	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
5	352	On the Power of Magic	1987	PODS
6	14,773	On Analogical Query Processing in Logic Database	1986	VLDB
7	5,692	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB
8	13,472	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB
9	440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
10	2,099	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD