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: he8a1fde32da41d0c
Venue: PODS
Year: 1986
Pagerank: 0.00018227953
Overall Rank: 440 | 97.05%
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
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
352	On the Power of Magic	1987	PODS	0.00020223279
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
2,024	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.166955e-05
4,425	Magic Counting Methods	1987	SIGMOD	6.6039832e-05
4,735	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.4452165e-05
5,050	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2976106e-05
5,413	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.1401229e-05
5,419	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.137651e-05
8,053	Polynomial-time program transformations in deductive databases	1990	PODS	5.3986864e-05
8,483	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	5.3327301e-05
9,689	Counting Methods for Cyclic Relations	1988	PODS	5.1406988e-05
10,159	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.0690887e-05
10,334	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0254535e-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,457	Computing Facts in Non-Horn Deductive Systems	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

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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
913	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013115161

Semantically Similar Papers

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