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: 10496
Venue: VLDB
Year: 2012
Pagerank: 5.9763416e-05
Overall Rank: 4,708 | 67.29%
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,665	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	4.9657158e-05
6,800	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.918071e-05
7,944	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.6089395e-05
8,392	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.5234647e-05
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05
8,663	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.4676883e-05
8,958	Understanding Queries by Conditional Instances	2022	SIGMOD	4.417947e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.3997447e-05
9,183	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD	4.3778211e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1905499e-05
11,474	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1905499e-05
12,022	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	4.1905499e-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.00078516827
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
1,231	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013141213
1,698	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010857033
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010726683
2,273	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.1447774e-05
6,083	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.2173276e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,733	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2106718e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
7,429	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD	4.7275942e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-05
11,561	Aggregate Queries on Sparse Databases	2020	PODS	4.1905499e-05
6,167	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1725053e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
7,162	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8085863e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415