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: 10495
Venue: VLDB
Year: 2012
Pagerank: 5.9820914e-05
Overall Rank: 4,706 | 67.27%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,662	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	4.9704872e-05
6,804	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.9224361e-05
7,941	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.613363e-05
8,394	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.527807e-05
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-05
8,665	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.471975e-05
8,954	Understanding Queries by Conditional Instances	2022	SIGMOD	4.4221863e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.4039656e-05
9,179	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD	4.3820222e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1945683e-05
11,471	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1945683e-05
12,014	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	4.1945683e-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
31	Provenance Semirings	2007	PODS	0.0007857786
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
1,238	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013114581
1,699	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010858983
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010736755
2,268	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.1497575e-05
6,079	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.2223439e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,728	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2185032e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
7,434	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD	4.7314358e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
6,169	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1716068e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
7,163	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8132033e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292