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.00018516535
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.00021246
719	Querying Graph Databases	2013	PODS	0.00014529156
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010251636
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
2,365	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5654557e-05
2,594	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2426092e-05
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0895728e-05
3,132	Matching Twigs in Probabilistic XML	2007	VLDB	7.6137556e-05
4,355	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	6.6412791e-05
4,660	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4822086e-05
5,164	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.2464259e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
6,798	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6797989e-05
7,140	Semantic Acyclicity on Graph Databases	2013	PODS	5.6005794e-05
7,186	The Parameterized Complexity of Database Queries	2001	PODS	5.5912387e-05
7,292	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5642569e-05
8,311	First-Order Query Evaluation with Cardinality Conditions	2018	PODS	5.3572454e-05
8,828	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	5.2685945e-05
9,202	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS	5.2082996e-05
10,115	Semantic Acyclicity Under Constraints	2016	PODS	5.0789354e-05
10,371	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	4.9793485e-05
11,724	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9793485e-05
12,056	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.9793485e-05
12,133	Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory	2019	PODS	4.9793485e-05
12,520	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.9793485e-05
12,699	Transducing Markov Sequences	2010	PODS	4.9793485e-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.00013941847
914	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013104061

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,520	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
2	3,183	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD
3	6,318	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
4	658	The Complexity of Query Reliability	1998	PODS
5	3,046	Tractable Query Languages for Complex Object Databases	1991	PODS
6	7,186	The Parameterized Complexity of Database Queries	2001	PODS
7	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
8	2,968	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