On the Implementation of a Simple Class of Logic Queries for Databases

Summary: Unifying framework for implementing canonical strongly linear (CSL) recursive queries, introducing binding-set/binding-passing and l-bound CSL where initial bindings propagate to a single recursive argument. Compares counting, eager, magic-set and a new hybrid "magic counting", characterizing trade-offs in binding propagation and execution cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 767
Venue: PODS
Year: 1986
Pagerank: 0.00018607152
Overall Rank: 429 | 97.06%
DOI: 10.1145/6012.6013

Incoming Non-self Citations Over Time

Authors

1. Domenico Saccà (CRAI)
2. Carlo Zaniolo (Microelectronics And Technology Computer Corporation)

BibTeX Citation

@inproceedings{sacca_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{On the Implementation of a Simple Class of Logic Queries for Databases}},
        url = {https://dl.acm.org/doi/10.1145/6012.6013},
        doi = {10.1145/6012.6013},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Saccà, Domenico and Zaniolo, Carlo},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
344	On the Power of Magic	1987	PODS	0.00020659405
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
4,337	Magic Counting Methods	1987	SIGMOD	6.7554367e-05
4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.5930956e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05
5,295	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.2784683e-05
7,886	Polynomial-time program transformations in deductive databases	1990	PODS	5.5225498e-05
8,316	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	5.4551195e-05
9,503	Counting Methods for Cyclic Relations	1988	PODS	5.2586367e-05
9,981	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.1845938e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	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,167	Computing Facts in Non-Horn Deductive Systems	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

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
888	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013402577

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
2	3,629	Compiling Separable Recursions	1988	SIGMOD
3	13,116	Semigroup techniques in recursive query optimization	1990	PODS
4	13,207	QUERYING LOGICAL DATABASES: Preliminary Report	1985	PODS
5	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
6	63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD
7	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
8	4,337	Magic Counting Methods	1987	SIGMOD
9	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	5,295	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS