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.3748367e-05
Overall Rank: 4,868 | 67.28%
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,507	Troubles with Nulls, Views from the Users	2022	VLDB	6.1009808e-05
6,013	SQL Nulls and Two-Valued Logic	2023	PODS	5.9141967e-05
6,046	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9052121e-05
7,704	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.4741304e-05
8,426	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3350162e-05
8,886	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2559789e-05
9,002	Coping with Incomplete Data: Recent Advances	2020	PODS	5.2394054e-05
9,374	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.1868213e-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.00075944947
17	Provenance Semirings	2007	PODS	0.00059752575
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020621631
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014697176
897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013204612
1,099	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00012037058
1,365	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00010913898
2,595	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	8.2422907e-05
2,717	Partial Results in Database Systems	2014	SIGMOD	8.0980367e-05
5,802	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.989635e-05
5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	5.956925e-05
6,089	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.8908642e-05
7,230	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.5795492e-05
7,691	SPROUT2: A Squared Query Engine for Uncertain Web Data	2011	SIGMOD	5.4772676e-05

Semantically Similar Papers

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