Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds

Authors

Materials

Abstract

Incomplete and probabilistic database techniques are principled methods for coping with uncertainty in data. Unfortunately, the class of queries that can be answered efficiently over such databases is severely limited, even when advanced approximation techniques are employed.We introduce attribute-annotated uncertain databases (AU-DBs), an uncertain data model that annotates tuples and attribute values with bounds to compactly approximate an incomplete database. AU-DBs are closed under relational algebra with aggregation using an efficient evaluation semantics. Using optimizations that trade accuracy for performance, our approach scales to complex queries and large datasets, and produces accurate results.

bibtex

@inproceedings{FH21,
  author = {Feng, Su and Huber, Aaron and Glavic, Boris and Kennedy, Oliver},
  booktitle = {Proceedings of the 46th International Conference on Management of Data},
  keywords = {UA-DB; Vizier},
  pages = {528 – 540},
  doi = {10.1145/3448016.3452791},
  pdfurl = {https://dl.acm.org/doi/pdf/10.1145/3448016.3452791},
  projects = {Vizier; UA-DB},
  video = {https://www.youtube.com/watch?v=si2HUS7idEs&list=PL3xUNnH4TdbsfndCMn02BqAAgGB0z7cwq},
  title = {Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds},
  venueshort = {SIGMOD},
  reproducibility = {https://github.com/fengsu91/AUDB_Reproducibility},
  longversionurl = {https://arxiv.org/pdf/2102.11796},
  year = {2021}
}

Reference

Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds Su Feng, Aaron Huber, Boris Glavic and Oliver Kennedy Proceedings of the 46th International Conference on Management of Data (2021), pp. 528–540.