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: 803
Venue: PODS
Year: 1987
Pagerank: 6.2784683e-05
Overall Rank: 5,295 | 63.68%
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
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
4,337	Magic Counting Methods	1987	SIGMOD	6.7554367e-05
6,948	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.7306589e-05
9,503	Counting Methods for Cyclic Relations	1988	PODS	5.2586367e-05
13,182	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	5.093636e-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.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
4,337	Magic Counting Methods	1987	SIGMOD	6.7554367e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
2	5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
3	4,266	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS
4	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
5	4,337	Magic Counting Methods	1987	SIGMOD
6	8,673	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS
7	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
8	9,503	Counting Methods for Cyclic Relations	1988	PODS
9	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS