The Parameterized Complexity of Database Queries

Summary: Introduces parameterized complexity to the DB theory community and frames query evaluation as parameterized decision problems. Shows that evaluation of first-order queries and conjunctive queries, when parameterized by query (formula) size, is parameterized-hard, highlighting inherent complexity barriers. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1226
Venue: PODS
Year: 2001
Pagerank: 5.1417208e-05
Overall Rank: 6,239 | 56.60%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Martin Grohe

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493

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
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
2,015	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.7901938e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,522	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS	5.0287573e-05
1,448	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011938045
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
8,652	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	4.4753042e-05
602	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019352415
3,003	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7388586e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05