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,055 | When is Shapley Value Computation a Matter of Counting? | 2024 | PODS | 5.2324399e-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,739 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.663547e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,804 | A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases | 2014 | PODS | 4.9224361e-05 |
| 4,720 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB | 5.973811e-05 |
| 10,919 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 4.1945683e-05 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 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,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.6248763e-05 |
| 12,356 | Query Evaluation with Soft-Key Constraints | 2008 | PODS | 4.1945683e-05 |
| 7,149 | Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases | 2020 | PODS | 4.8173876e-05 |
| 1,268 | The Dichotomy of Conjunctive Queries on Probabilistic Structures | 2007 | PODS | 0.00012931993 |