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.1369162e-05
Overall Rank: 6,238 | 56.65%
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,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141

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
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
2,007	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8123766e-05
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,519	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS	5.0239231e-05
1,450	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011926567
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
8,650	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	4.4710131e-05
603	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019334592
3,005	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7315492e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
12,039	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1905499e-05