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: hfe5d97d8a065c5b2
Venue: PODS
Year: 1987
Pagerank: 6.137651e-05
Overall Rank: 5,419 | 63.57%
DOI: 10.1145/28659.28691

Incoming Non-self Citations Over Time

Authors

1. Alberto Marchetti-Spaccamela (Sapienza University)
2. Antonella Pelaggi (Sapienza University)
3. Domenico Saccà (CRAI; University of Calabria)

BibTeX Citation

@inproceedings{marchettispaccamela_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{Worst-case Complexity Analysis of Methods for Logic Query Implementation}},
        url = {https://dl.acm.org/doi/10.1145/28659.28691},
        doi = {10.1145/28659.28691},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Marchetti-Spaccamela, Alberto and Pelaggi, Antonella and Saccà, Domenico},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
4,425	Magic Counting Methods	1987	SIGMOD	6.6039832e-05
7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.6020796e-05
9,689	Counting Methods for Cyclic Relations	1988	PODS	5.1406988e-05
13,472	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	4.9793485e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018227953
4,425	Magic Counting Methods	1987	SIGMOD	6.6039832e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
2	5,978	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
3	4,355	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS
4	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
5	8,828	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS
6	4,425	Magic Counting Methods	1987	SIGMOD
7	12,520	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
8	9,689	Counting Methods for Cyclic Relations	1988	PODS
9	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS