Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers

Summary: UA-DBs fuse under- and over-approximations of certain answers to balance reliability and performance. Using incomplete K-relations, UA-DBs generalize incomplete databases, allow explicitly marked uncertain answers, and yield tight, high-utility approximations with efficient evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8260c7d397883b99
Venue: SIGMOD
Year: 2019
Pagerank: 6.3718189e-05
Overall Rank: 4,870 | 67.27%
DOI: 10.1145/3299869.3319887

Incoming Non-self Citations Over Time

Authors

1. Su Feng (Illinois Institute of Technology)
2. Aaron Huber (State University of New York at Buffalo)
3. Boris Glavic (Illinois Institute of Technology)
4. Oliver Kennedy (State University of New York at Buffalo)

BibTeX Citation

@inproceedings{feng_sigmod19,
        title = {{Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers}},
        author = {Feng, Su and Huber, Aaron and Glavic, Boris and Kennedy, Oliver},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319887},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319887},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,510	Troubles with Nulls, Views from the Users	2022	VLDB	6.0980926e-05
6,013	SQL Nulls and Two-Valued Logic	2023	PODS	5.911397e-05
6,048	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9024167e-05
7,710	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.471539e-05
8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3324907e-05
8,895	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2534908e-05
9,012	Coping with Incomplete Data: Recent Advances	2020	PODS	5.2369252e-05
9,383	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.1843659e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.00075910134
17	Provenance Semirings	2007	PODS	0.00059813669
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049326063
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023251151
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020613834
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014691377
897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013198452
1,098	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00012031983
1,360	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00010913787
2,597	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	8.2383888e-05
2,719	Partial Results in Database Systems	2014	SIGMOD	8.0942034e-05
5,803	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.9867996e-05
5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	5.9541051e-05
6,091	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.8880755e-05
7,232	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.5769079e-05
7,697	SPROUT2: A Squared Query Engine for Uncertain Web Data	2011	SIGMOD	5.4746748e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,658	Uncertainty Aware Query Execution Time Prediction	2014	VLDB
2	690	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB
3	12,867	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
4	9,115	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD
5	9,012	Coping with Incomplete Data: Recent Advances	2020	PODS
6	84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB
7	9,410	Queries with Arithmetic on Incomplete Databases	2020	PODS
8	9,382	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD
9	715	Data Integration with Uncertainty	2007	VLDB
10	8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD