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: 4196
Venue: SIGMOD
Year: 2009
Pagerank: 8.0788784e-05
Overall Rank: 2,831 | 80.58%
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
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.7737212e-05
4,680	Probabilistic Databases with MarkoViews	2012	VLDB	6.5675814e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
6,839	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.7576811e-05
8,476	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.4170414e-05
12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	5.093636e-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
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
1,520	Conditioning Probabilistic Databases	2008	VLDB	0.00010510496
2,775	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	8.1359291e-05

Semantically Similar Papers

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