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
- 2. Dan Suciu
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,058 | When is Shapley Value Computation a Matter of Counting? | 2024 | PODS | 5.2274142e-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 |
|---|---|---|---|---|
| 7,738 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.6590737e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,800 | A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases | 2014 | PODS | 4.918071e-05 |
| 4,722 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB | 5.9646931e-05 |
| 10,923 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 4.1905499e-05 |
| 770 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.0001686092 |
| 3,374 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1631303e-05 |
| 7,604 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS | 4.6944524e-05 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.620459e-05 |
| 12,364 | Query Evaluation with Soft-Key Constraints | 2008 | PODS | 4.1905499e-05 |
| 7,151 | Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases | 2020 | PODS | 4.8127652e-05 |
| 1,269 | The Dichotomy of Conjunctive Queries on Probabilistic Structures | 2007 | PODS | 0.00012911894 |