On the Complexity of Database Queries (Extended Abstract)

Summary: Parameterizing by query size/#vars, classify relational calculus and fragments (conjunctive, positive) into the W-hierarchy, showing query size is inherently in the exponent of data complexity, increasingly so for more expressive languages. For recursive languages (fixpoint, Datalog) this exponential dependence is provable; acyclic queries with counting (#) avoid the blow-up, while adding order/inequalities does not. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1097
Venue: PODS
Year: 1997
Pagerank: 0.00018893507
Overall Rank: 414 | 97.17%
DOI: 10.1145/263661.263664

Incoming Non-self Citations Over Time

Authors

1. Christos H. Papadimitriou (University of California Berkeley)
2. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{papadimitriou_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{On the Complexity of Database Queries (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/263661.263664},
        doi = {10.1145/263661.263664},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papadimitriou, Christos H. and Yannakakis, Mihalis},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
747	Querying Graph Databases	2013	PODS	0.00014400452
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.4290753e-05
2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.2680182e-05
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
4,266	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	6.7936492e-05
4,644	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.5901073e-05
5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.3897022e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.8101181e-05
7,028	Semantic Acyclicity on Graph Databases	2013	PODS	5.7228058e-05
7,052	The Parameterized Complexity of Database Queries	2001	PODS	5.7171307e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
8,141	First-Order Query Evaluation with Cardinality Conditions	2018	PODS	5.4802066e-05
8,673	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	5.3872753e-05
9,036	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS	5.3272169e-05
9,933	Semantic Acyclicity Under Constraints	2016	PODS	5.1955087e-05
10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	5.093636e-05
11,410	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	5.093636e-05
11,753	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	5.093636e-05
11,832	Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory	2019	PODS	5.093636e-05
12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	5.093636e-05
12,408	Transducing Markov Sequences	2010	PODS	5.093636e-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
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
2	6,184	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
3	3,128	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD
4	644	The Complexity of Query Reliability	1998	PODS
5	2,986	Tractable Query Languages for Complex Object Databases	1991	PODS
6	7,052	The Parameterized Complexity of Database Queries	2001	PODS
7	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
8	2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS
9	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
10	763	On the Complexity of Bounded-Variable Queries	1995	PODS