Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds

Summary: Introduces attribute-annotated uncertain databases (AU-DBs) that bound tuples and attribute values to compactly approximate incomplete data. Provides a scalable evaluation semantics closed under relational algebra with aggregation, using accuracy-for-performance optimizations for complex queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hebeb53aaae0a960b
Venue: SIGMOD
Year: 2021
Pagerank: 5.3148581e-05
Overall Rank: 8,451 | 43.36%
DOI: 10.1145/3448016.3452791

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{feng_sigmod21,
        title = {{Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds}},
        author = {Feng, Su and Glavic, Boris and Huber, Aaron and Kennedy, Oliver A.},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452791},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452791},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,943	Efficient Answering of Historical What-if Queries	2022	SIGMOD	6.3304729e-05
8,915	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2361195e-05
9,409	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.1672232e-05
10,874	Efficient Query Repair for Aggregate Constraints	2026	VLDB	4.9605343e-05
11,735	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059660827
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049435337
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023188414
340	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020548826
502	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017239652
597	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015742369
811	Provenance for Aggregate Queries	2011	PODS	0.00013713646
826	Data Integration: The Teenage Years	2006	VLDB	0.00013599086
899	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013158587
2,215	OLAP Over Uncertain and Imprecise Data	2005	VLDB	8.8284913e-05
2,730	Partial Results in Database Systems	2014	SIGMOD	8.0676725e-05
3,737	Snorkel: Fast Training Set Generation for Information Extraction	2017	SIGMOD	7.0425964e-05
4,196	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7317801e-05
4,472	Data Debugging and Exploration with Vizier	2019	SIGMOD	6.5709808e-05
4,892	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.3507497e-05
5,665	Foundations of Uncertain-Data Integration	2010	VLDB	6.0292508e-05
5,762	Answering Aggregate Queries in Data Exchange	2008	PODS	5.9846111e-05
5,819	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.9670046e-05
5,907	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	5.9344171e-05
5,997	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.9036298e-05
6,103	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.8688925e-05
7,251	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.5584673e-05
8,192	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.3646457e-05
9,033	Coping with Incomplete Data: Recent Advances	2020	PODS	5.2196086e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB
2	9,134	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD
3	9,408	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD
4	5,997	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD
5	1,619	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD
6	4,232	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
7	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
8	718	Data Integration with Uncertainty	2007	VLDB
9	9,435	Queries with Arithmetic on Incomplete Databases	2020	PODS
10	4,892	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD