Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration

Summary: Survey of fine-grained complexity for query answering that unifies decision, counting, and enumeration tasks, presenting algorithmic techniques, complexity measures and conditional lower bounds. Emphasizes consequences for aggregation and probabilistic databases, and enumeration trade-offs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1801
Venue: PODS
Year: 2020
Pagerank: 4.4753042e-05
Overall Rank: 8,652 | 39.81%
DOI: 10.1145/3375395.3389130

Incoming Non-self Citations Over Time

Authors

1. Arnaud Durand

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
5,967	Change Propagation Without Joins	2023	VLDB	5.250976e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
2,293	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS	9.0899933e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
3,387	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.1573735e-05
5,576	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.426344e-05
6,167	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	5.1717635e-05
13,395	Enumerating Answers to First-Order Queries over Databases of Low Degree	2014	PODS	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,239	The Parameterized Complexity of Database Queries	2001	PODS	5.1417208e-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
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
3,003	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7388586e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05