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: h9e0ca7d3385455ba
Venue: SIGMOD
Year: 2009
Pagerank: 7.9338024e-05
Overall Rank: 2,860 | 80.78%
DOI: 10.1145/1559845.1559887

Incoming Non-self Citations Over Time

Authors

1. Dan Olteanu (University of Oxford)
2. Jiewen Huang (University of Oxford)

BibTeX Citation

@inproceedings{olteanu_sigmod09,
        title = {{Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities}},
        author = {Olteanu, Dan and Huang, Jiewen},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559887},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559887},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
2,299	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6727773e-05
3,291	Computing Query Probability with Incidence Algebras	2010	PODS	7.4519264e-05
4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.6226901e-05
4,765	Probabilistic Databases with MarkoViews	2012	VLDB	6.4275411e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
6,982	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.6287253e-05
8,643	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.2954976e-05
12,397	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.9793485e-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
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
1,065	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.0001219981
1,549	Conditioning Probabilistic Databases	2008	VLDB	0.00010288725
2,805	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	7.9836802e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,007	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
2	4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
3	1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD
4	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
5	12,839	Query Evaluation with Soft-Key Constraints	2008	PODS
6	7,466	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
7	7,569	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS
8	5,340	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
9	7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
10	4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB