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: 1833
Venue: PODS
Year: 2020
Pagerank: 5.3872753e-05
Overall Rank: 8,673 | 40.50%
DOI: 10.1145/3375395.3389130

Incoming Non-self Citations Over Time

Authors

1. Arnaud Durand (University of Paris)

BibTeX Citation

@inproceedings{durand_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3389130},
        doi = {10.1145/3375395.3389130},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Durand, Arnaud},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,985	Change Propagation Without Joins	2023	VLDB	6.412102e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
3,472	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS	7.3870922e-05
4,063	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS	6.9307541e-05
5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.3897022e-05
5,066	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.3771079e-05
13,596	Enumerating Answers to First-Order Queries over Databases of Low Degree	2014	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
2	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
3	2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS
4	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
5	4,266	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS
6	8,528	Aggregate Queries on Sparse Databases	2020	PODS
7	5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
8	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
9	10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS
10	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS