Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases
Summary: Provide a polynomial-time construction of deterministic decomposable circuits for a class of UCQs previously conjectured to separate extensional (inclusion–exclusion) and intensional approaches. Show inclusion–exclusion can be avoided via negation, proving intensional compilation suffices for this case. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Mika el Monet (IMFD Chile; University of Chile)
BibTeX Citation
@inproceedings{monet_pods20,
address = {New York, NY, USA},
series = {{PODS} '20},
title = {{Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases}},
url = {https://dl.acm.org/doi/10.1145/3375395.3387642},
doi = {10.1145/3375395.3387642},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Monet, Mika el},
year = {2020}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,424 | Computing the Shapley Value of Facts in Query Answering | 2022 | SIGMOD | 8.6009068e-05 |
| 5,382 | Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases | 2024 | PODS | 6.237788e-05 |
| 6,741 | Probabilistic Databases for All | 2020 | PODS | 5.7866368e-05 |
| 9,819 | Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration | 2021 | PODS | 5.214913e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,965 | ProvSQL: Provenance and Probability Management in PostgreSQL | 2018 | VLDB | 9.3852716e-05 |
| 6,713 | Circuit Treewidth, Sentential Decision, and Query Compilation | 2017 | PODS | 5.7961371e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,136 | Approximating Predicates and Expressive Queries on Probabilistic Databases | 2008 | PODS |
| 2 | 8,745 | Querying Probabilistic Preferences in Databases | 2017 | PODS |
| 3 | 8,626 | Charting the Tractability Frontier of Certain Conjunctive Query Answering | 2013 | PODS |
| 4 | 7,317 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS |
| 5 | 5,225 | Approximate Lifted Inference with Probabilistic Databases | 2015 | VLDB |
| 6 | 7,851 | A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries | 2021 | PODS |
| 7 | 2,831 | Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities | 2009 | SIGMOD |
| 8 | 9,819 | Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration | 2021 | PODS |
| 9 | 7,706 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS |
| 10 | 4,301 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB |