A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries
Summary: Strengthens the dichotomy for generalized model counting on UCQs by showing every unsafe UCQ is #P-hard even when tuple probabilities are restricted to {0,1/2,1}, using novel hardness techniques. Also proves that model counting with probabilities in {0,1/2} is #P-hard for Type‑I forbidden queries. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Batya Kenig (University of Washington)
- 2. Dan Suciu (University of Washington)
BibTeX Citation
@inproceedings{kenig_pods21,
address = {New York, NY, USA},
series = {{PODS} '21},
title = {{A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries}},
url = {https://dl.acm.org/doi/10.1145/3452021.3458313},
doi = {10.1145/3452021.3458313},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Kenig, Batya and Suciu, Dan},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,657 | When is Shapley Value Computation a Matter of Counting? | 2024 | PODS | 6.1313425e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,084 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 5.4910538e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,839 | A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases | 2014 | PODS |
| 2 | 4,301 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB |
| 3 | 11,140 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS |
| 4 | 636 | Answering Conjunctive Queries under Updates | 2017 | PODS |
| 5 | 2,468 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS |
| 6 | 7,706 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS |
| 7 | 4,187 | Maximally Joining Probabilistic Data | 2007 | PODS |
| 8 | 12,549 | Query Evaluation with Soft-Key Constraints | 2008 | PODS |
| 9 | 7,430 | Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases | 2020 | PODS |
| 10 | 1,041 | The Dichotomy of Conjunctive Queries on Probabilistic Structures | 2007 | PODS |