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: 768
Venue: PODS
Year: 1986
Pagerank: 0.00028644922
Overall Rank: 296 | 97.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Domenico Saccà
2. Carlo Zaniolo

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
365	On the Power of Magic	1987	PODS	0.00025585898
1,712	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.00010804573
2,036	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.714898e-05
4,555	Magic Counting Methods	1987	SIGMOD	6.0891017e-05
4,881	Translation And Optimization Of Logic Queries: The Algebraic Approach	1986	VLDB	5.8567721e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
5,259	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	5.5984356e-05
5,515	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	5.4636431e-05
7,156	Counting Methods for Cyclic Relations	1988	PODS	4.8145046e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
8,012	Non-deterministic Modelling of Logical Queries in Deductive Databases	1987	SIGMOD	4.6064553e-05
9,834	Magic Functions : A Technique To Optimize Extended Datalog Recursive Programs	1987	VLDB	4.2751057e-05
11,053	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	4.1945683e-05
12,964	A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing	1988	SIGMOD	4.1945683e-05
12,970	Computing Facts In Non-Horn Deductive Systems.	1988	VLDB	4.1945683e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-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.0010066783
490	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00022016773

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05
3,553	Compiling Separable Recursions	1988	SIGMOD	6.9779134e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
13,008	QUERYING LOGICAL DATABASES: Preliminary Report	1985	PODS	4.1945683e-05
1,529	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011496686
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
5,628	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.4030815e-05
4,555	Magic Counting Methods	1987	SIGMOD	6.0891017e-05
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
5,515	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	5.4636431e-05