Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities

Summary: Confidence computation for conjunctive queries with inequalities on tuple-independent probabilistic databases. Defines a tractable query class with inequalities; introduces OBDD-based lineage compilation and a secondary-storage PostgreSQL variant that evaluates OBDD fragments on the fly in a single lineage scan, yielding up to 100x speedups on probabilistic TPC-H. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4134
Venue: SIGMOD
Year: 2009
Pagerank: 8.2185032e-05
Overall Rank: 2,728 | 81.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Dan Olteanu
2. Jiewen Huang

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.0001386199
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
3,314	Computing Query Probability with Incidence Algebras	2010	PODS	7.2318581e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
5,266	Probabilistic Databases with MarkoViews	2012	VLDB	5.5972559e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
6,804	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.9224361e-05
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-05
11,905	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010736755
2,875	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	7.9742313e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,653	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	4.3109001e-05
4,706	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9820914e-05
1,699	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010858983
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
12,356	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1945683e-05
7,163	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8132033e-05
7,149	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS	4.8173876e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-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