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: 2353
Venue: SIGMOD
Year: 1986
Pagerank: 0.00038782376
Overall Rank: 63 | 99.57%
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,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.789691e-05
6,752	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.7837368e-05
7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS	5.6184826e-05
7,885	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.5228272e-05
7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.5160399e-05
7,986	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD	5.5125835e-05
8,314	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.4554917e-05
8,316	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	5.4551195e-05
8,380	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	5.4377187e-05
8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	5.3766157e-05
8,827	Compiling Query Constraints	1994	PODS	5.3615981e-05
9,833	A Fix for the Fixation on Fixpoints	2023	CIDR	5.2115442e-05
9,981	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.1845938e-05
10,690	Dynamic Pruning for Recursive Joins	2025	SIGMOD	5.093636e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05
11,842	Ariadne: Online Provenance for Big Graph Analytics	2019	SIGMOD	5.093636e-05
12,810	Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases	2003	PODS	5.093636e-05
13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	5.093636e-05
13,076	Learning Efficient Query Processing Strategies	1992	PODS	5.093636e-05
13,083	Implementing Deductive Databases by Linear Programming	1992	PODS	5.093636e-05
13,133	Attribute Agreement	1989	PODS	5.093636e-05
13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	5.093636e-05
13,160	A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing	1988	SIGMOD	5.093636e-05
13,166	Fixed-point semantics and the representation of algorithms on large data	1988	VLDB	5.093636e-05
13,179	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	5.093636e-05
13,182	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	5.093636e-05
13,186	An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments	1987	VLDB	5.093636e-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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
848	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00013651467
1,051	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00012406675
2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.2516006e-05

Semantically Similar Papers

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