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.00018448553
Overall Rank: 424 | 97.16%
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
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
719	Querying Graph Databases	2013	PODS	0.00014493767
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010212902
1,734	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7545941e-05
1,821	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5466386e-05
2,376	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5345413e-05
2,604	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2136514e-05
2,739	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0598805e-05
3,143	Matching Twigs in Probabilistic XML	2007	VLDB	7.5857903e-05
4,379	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	6.6161854e-05
4,665	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4634883e-05
5,187	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.2228242e-05
5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.0883761e-05
6,820	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6583428e-05
7,163	Semantic Acyclicity on Graph Databases	2013	PODS	5.5797798e-05
7,206	The Parameterized Complexity of Database Queries	2001	PODS	5.5701964e-05
7,311	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5432326e-05
8,332	First-Order Query Evaluation with Cardinality Conditions	2018	PODS	5.3370034e-05
8,855	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	5.2486885e-05
9,233	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS	5.1886203e-05
10,156	Semantic Acyclicity Under Constraints	2016	PODS	5.0597449e-05
10,449	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	4.9605343e-05
11,775	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9605343e-05
12,106	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.9605343e-05
12,183	Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory	2019	PODS	4.9605343e-05
12,569	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.9605343e-05
12,748	Transducing Markov Sequences	2010	PODS	4.9605343e-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
796	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00013890233
917	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013054852

Semantically Similar Papers

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