Worst-case Complexity Analysis of Methods for Logic Query Implementation

Summary: Graph-based worst-case complexity analysis of three implementation methods (Eager, Counting, Magic Set) for canonical strongly linear (CSL) queries via a directed query-graph model with three arc types. Establishes Counting yields the best upper bound for non-cyclic queries and presents an extension of Counting to handle cyclic queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 804
Venue: PODS
Year: 1987
Pagerank: 5.555803e-05
Overall Rank: 5,347 | 62.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,473	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7048914e-05
4,440	Magic Counting Methods	1987	SIGMOD	6.180671e-05
6,363	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.0896537e-05
9,128	Counting Methods for Cyclic Relations	1988	PODS	4.3866751e-05
12,995	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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.00099936325
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
299	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028555103
4,440	Magic Counting Methods	1987	SIGMOD	6.180671e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
3,005	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7315492e-05
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
4,440	Magic Counting Methods	1987	SIGMOD	6.180671e-05
8,650	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	4.4710131e-05
12,039	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1905499e-05
9,128	Counting Methods for Cyclic Relations	1988	PODS	4.3866751e-05
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00099936325
299	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028555103