Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds

Su Feng, Boris Glavic, Aaron Huber, Oliver A. Kennedy

TL;DR

This paper introduces Attribute-Annotated Uncertain Databases (AU-DBs), a novel data model that efficiently tracks uncertainty in complex queries, including aggregations. AU-DBs offer a practical balance between precision and performance, outperforming existing methods for uncertain data management.

What Problem Does This Paper Address?

Managing uncertainty in data is a critical challenge across many domains, from sensor readings to information extraction. Traditional approaches to handling this uncertainty, like returning only "certain" answers, often exclude valuable, albeit uncertain, information. While more advanced techniques exist, they often struggle with complex queries (especially aggregations) or are computationally too expensive for practical use. This leaves users with a dilemma: either accept incomplete results or resort to heuristics that discard all uncertainty information, potentially leading to severe consequences. The authors aim to bridge this gap by providing a system that can efficiently handle complex queries over uncertain data while maintaining meaningful bounds on the results.

Methods

The core contribution is the Attribute-Annotated Uncertain Database (AU-DB) model. AU-DBs extend previous Uncertainty-Annotated Databases (UA-DBs) by introducing:

  • Attribute-level bounds: Instead of just bounding tuple-level uncertainty, AU-DBs annotate individual attribute values with lower and upper bounds, capturing finer-grained uncertainty.
  • Tuple-level bounds: AU-DBs also encode an upper bound on tuple multiplicity, which is crucial for handling non-monotone queries like aggregation and set difference.

These annotations are represented using a KAU-semiring, which is a direct product of a semiring K (like N for bag semantics or B for set semantics) with itself three times (K³). This structure allows for compact representation of uncertainty. The paper also details:

  • Range-annotated expression evaluation: A semantics for evaluating expressions over uncertain values, preserving bounds.
  • Query semantics for AU-DBs: A set of operations (selection, projection, join, union, set difference, aggregation) that are closed under the AU-DB model and preserve the encoded bounds.
  • Optimized query rewriting: Techniques to translate AU-DB queries into SQL queries on a relational encoding, including optimizations for joins and aggregations to improve performance by trading some accuracy for speed.

Datasets

The paper evaluates their approach using:

  • PDBench: A modified TPC-H data generator that creates x-DBs (block-independent databases) with attribute-level uncertainty.
  • TPC-H queries: Standard TPC-H queries are used to evaluate performance, particularly for aggregations with uncertain group-by attributes.
  • Real-world datasets: The authors use datasets from Netflix, Chicago Crimes, and Medicare Hospital Compare to demonstrate the practical applicability of AU-DBs.
  • Synthetic tables: Used for micro-benchmarks to evaluate performance and accuracy under varying conditions (e.g., number of group-by attributes, number of aggregates).

Key Insights and Ideas

  • Attribute-level uncertainty is key: The paper highlights that simply bounding tuple existence isn't enough for complex queries. Capturing uncertainty within attribute values is essential for accurate results, especially for aggregations.
  • Compactness through bounds: AU-DBs offer a compact way to represent uncertainty by using lower and upper bounds, which is more efficient than enumerating all possible worlds or using complex symbolic representations.
  • Balancing precision and performance: The authors acknowledge that perfect precision can be computationally prohibitive. Their work introduces optimizations that allow for a trade-off between accuracy and performance, making the system practical for large datasets.
  • Unified framework for complex queries: AU-DBs provide a unified approach to handle a wide range of complex queries, including those involving aggregations and set operations, which were previously challenging for uncertain data models.

Key Results

  • PTIME Data Complexity: AU-DB query evaluation has PTIME data complexity, making it efficient for large datasets.
  • Performance Gains: AU-DBs significantly outperform existing methods like UA-DBs, MayBMS, and Trio, especially for complex queries involving aggregation. For instance, they show up to a 570% speedup over MCDB for aggregation queries.
  • Scalability: The approach scales linearly with dataset size and uncertainty levels for simple queries.
  • Accuracy: AU-DBs provide tight bounds for query results, often closely matching exact bounds, while outperforming sampling-based methods like MCDB.
  • Join Optimization: Optimized join rewrites using splitting and compression techniques reduce runtime by 1-2 orders of magnitude, with controlled trade-offs in accuracy.

Limitations and Future Work

  • Tightness of Bounds: While AU-DBs provide bounds, achieving maximally tight bounds is computationally intractable (NP-hard). The paper focuses on providing practical, bound-preserving approximations.
  • Non-ordinal Categorical Attributes: The current model assumes an order for attribute values to define ranges. Extending this to handle non-ordinal categorical attributes is a direction for future work.
  • Queries with Ordering: Extending the model to handle queries involving ordering (e.g., top-k queries, window functions) is another area for future research.
  • Generalizing Semirings: The current work focuses on bag and set semantics. Generalizing the model to support a wider range of semirings for provenance and other uncertainty types is a potential extension.

Summary updated

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{feng2021efficient,
  author = {Su Feng and Boris Glavic and Aaron Huber and Oliver A. Kennedy},
  title = {{Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds}},
  booktitle = {SIGMOD},
  year = {2021},
  doi = {10.1145/3448016.3452791},
}
Figure