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: 4135
Venue: SIGMOD
Year: 2009
Pagerank: 8.2106718e-05
Overall Rank: 2,733 | 81.01%
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.00013851012
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
3,315	Computing Query Probability with Incidence Algebras	2010	PODS	7.2247513e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
5,270	Probabilistic Databases with MarkoViews	2012	VLDB	5.5925747e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
6,800	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.918071e-05
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05
11,913	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.1905499e-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
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
630	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018942778
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010726683
2,883	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	7.9665191e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,654	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	4.3067693e-05
4,708	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9763416e-05
1,698	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010857033
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
12,364	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1905499e-05
7,162	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8085863e-05
7,151	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS	4.8127652e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-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