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: h18d41cf07e34c750
Venue: PODS
Year: 1997
Pagerank: 0.00018507815
Overall Rank: 421 | 97.18%
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
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
720	Querying Graph Databases	2013	PODS	0.00014522278
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010246783
1,726	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7857214e-05
1,813	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5759542e-05
2,366	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5614655e-05
2,596	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2387266e-05
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.08577e-05
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
4,356	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	6.6381352e-05
4,662	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4792038e-05
5,166	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.2434689e-05
5,487	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1085184e-05
6,804	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6771104e-05
7,142	Semantic Acyclicity on Graph Databases	2013	PODS	5.5979329e-05
7,188	The Parameterized Complexity of Database Queries	2001	PODS	5.5885989e-05
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
8,317	First-Order Query Evaluation with Cardinality Conditions	2018	PODS	5.3547094e-05
8,837	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	5.2661006e-05
9,211	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS	5.205834e-05
10,119	Semantic Acyclicity Under Constraints	2016	PODS	5.0765311e-05
10,383	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	4.9769913e-05
11,730	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9769913e-05
12,062	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.9769913e-05
12,139	Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory	2019	PODS	4.9769913e-05
12,526	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.9769913e-05
12,705	Transducing Markov Sequences	2010	PODS	4.9769913e-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
794	On the Complexity of Bounded-Variable Queries	1995	PODS	0.0001393526
915	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013097866

Semantically Similar Papers

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