Aggregation in Probabilistic Databases via Knowledge Compilation

Summary: Knowledge compilation enables aggregation over data: semiring/semimodule expressions compile into decomposition trees, yielding linear distribution. Tractable aggregates via decomposition trees; SPROUT prototype shows performance on TPC-H and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10683
Venue: VLDB
Year: 2012
Pagerank: 6.9035475e-05
Overall Rank: 4,098 | 71.89%
DOI: 10.14778/2140436.2140445

Incoming Non-self Citations Over Time

Authors

1. Robert Fink (University of Oxford)
2. Larisa Han (University of Oxford)
3. Dan Olteanu (University of Oxford)

BibTeX Citation

@article{fink_vldb12,
        title = {{Aggregation in Probabilistic Databases via Knowledge Compilation}},
        author = {Fink, Robert and Han, Larisa and Olteanu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {5},
        pages = {490--501},
        doi = {10.14778/2140436.2140445},
        url = {https://doi.org/10.14778/2140436.2140445},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,587	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	5.8333865e-05
6,839	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.7576811e-05
8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.4574671e-05
8,476	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.4170414e-05
8,509	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.4120069e-05
8,688	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	5.3847009e-05
8,970	Understanding Queries by Conditional Instances	2022	SIGMOD	5.3422757e-05
9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.3058708e-05
9,416	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD	5.2742007e-05
10,183	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	5.093636e-05
11,668	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	5.093636e-05
12,212	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059843817
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
806	Provenance for Aggregate Queries	2011	PODS	0.00013890398
960	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012945163
1,520	Conditioning Probabilistic Databases	2008	VLDB	0.00010510496
1,594	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010252583
2,172	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.0394311e-05
5,866	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	6.0615445e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,831	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD
2	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
3	7,306	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD
4	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
5	8,528	Aggregate Queries on Sparse Databases	2020	PODS
6	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
7	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
8	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
9	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
10	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB