Back to papers
On the Enumeration Complexity of Unions of Conjunctive Queries
Summary: Generalizes free-connexity to UCQs and characterizes when UCQs admit linear preprocessing and constant‑delay enumeration, showing some unions—even of intractable CQs—can be tractable. For several query classes free‑connexity exactly captures tractability; full classification open.
(summarized by gpt-5-mini on Feb 09 2026)
Paper ID
h536fb820ffe66459
Venue
PODS
Year
2019
Pagerank
8.3550625e-05
Overall Rank
2,517 | 83.09%
DOI
10.1145/3294052.3319700
Incoming Non-self Citations Over Time
BibTeX Citation
Copy BibTeX
@inproceedings{carmeli_pods19,
address = {New York, NY, USA},
series = {{PODS} '19},
title = {{On the Enumeration Complexity of Unions of Conjunctive Queries}},
url = {https://dl.acm.org/doi/10.1145/3294052.3319700},
doi = {10.1145/3294052.3319700},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Carmeli, Nofar and Kröll, Markus},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 19 of 19 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
2,593
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
2020
VLDB
8.2429717e-05
2,757
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
8.0487636e-05
4,510
Conjunctive Queries with Comparisons
2022
SIGMOD
6.5673056e-05
5,487
Beyond Equi-joins: Ranking, Enumeration and Factorization
2021
VLDB
6.1085184e-05
5,895
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
2025
SIGMOD
5.9534254e-05
5,978
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS
5.9259322e-05
6,432
Evaluating Datalog over Semirings: A Grounding-based Approach
2024
PODS
5.7857524e-05
6,576
Output-Optimal Algorithms for Join-Aggregate Queries
2025
PODS
5.7428578e-05
7,294
Computing the Difference of Conjunctive Queries Efficiently
2023
SIGMOD
5.5616228e-05
7,724
CORE: a Complex Event Recognition Engine
2022
VLDB
5.4657408e-05
8,837
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration
2020
PODS
5.2661006e-05
9,477
Efficiently Enumerating Answers to Ontology-Mediated Queries
2022
PODS
5.1698497e-05
10,216
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
5.0572653e-05
10,383
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
4.9769913e-05
10,388
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
2026
PODS
4.9769913e-05
10,399
Towards Parameterized Hardness on Maintaining Conjunctive Queries
2026
PODS
4.9769913e-05
11,077
Towards Efficient Random-Order Enumeration for Join Queries
2026
VLDB
4.9769913e-05
11,091
Circuit Bounds for Conjunctive Queries with Self-joins
2025
PODS
4.9769913e-05
11,532
Relational Algorithms for Top-k Query Evaluation
2024
SIGMOD
4.9769913e-05
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
10,216
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
2
12,526
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
2013
PODS
3
637
Answering Conjunctive Queries under Updates
2017
PODS
4
9,177
Efficient Approximations of Conjunctive Queries
2012
PODS
5
1,737
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
2015
PODS
6
4,700
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
2021
PODS
7
10,383
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
8
11,494
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
2024
PODS
9
2,757
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
10
5,978
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS