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.00018219394
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.00037991902
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021580917
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
353	On the Power of Magic	1987	PODS	0.00020213935
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8804595e-05
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
4,427	Magic Counting Methods	1987	SIGMOD	6.6008592e-05
4,736	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.4421654e-05
5,054	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2946294e-05
5,417	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.1372173e-05
5,423	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.1347456e-05
8,059	Polynomial-time program transformations in deductive databases	1990	PODS	5.3961311e-05
8,491	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	5.3302058e-05
9,695	Counting Methods for Cyclic Relations	1988	PODS	5.1382653e-05
10,163	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.066689e-05
10,341	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0230745e-05
13,456	A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing	1988	SIGMOD	4.9769913e-05
13,463	Computing Facts in Non-Horn Deductive Systems	1988	VLDB	4.9769913e-05
13,475	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.9769913e-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.00058997063
914	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013109036

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,454	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
2	3,715	Compiling Separable Recursions	1988	SIGMOD
3	13,412	Semigroup techniques in recursive query optimization	1990	PODS
4	13,503	QUERYING LOGICAL DATABASES: Preliminary Report	1985	PODS
5	2,100	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,875	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
8	4,427	Magic Counting Methods	1987	SIGMOD
9	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	5,423	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS