  Certain answers are a principled method for coping with the uncertainty that
arises in many practical data management tasks. Unfortunately, this method is
expensive and may exclude useful (if uncertain) answers. Prior work introduced
Uncertainty Annotated Databases (UA-DBs), which combine an under- and
over-approximation of certain answers. UA-DBs combine the reliability of
certain answers based on incomplete K-relations with the performance of
classical deterministic database systems. However, UA-DBs only support a
limited class of queries and do not support attribute-level uncertainty which
can lead to inaccurate under-approximations of certain answers. In this paper,
we introduce attribute-annotated uncertain databases (AU-DBs) which extend the
UA-DB model with attribute-level annotations that record bounds on the values
of an attribute across all possible worlds. This enables more precise
approximations of incomplete databases. Furthermore, we extend UA-DBs to encode
an compact over-approximation of possible answers which is necessary to support
non-monotone queries including aggregation and set difference. We prove that
query processing over AU-DBs preserves the bounds of certain and possible
answers and investigate algorithms for compacting intermediate results to
retain efficiency. Through an compact encoding of possible answers, our
approach also provides a solid foundation for handling missing data. Using
optimizations that trade accuracy for performance, our approach scales to
complex queries and large datasets, and produces accurate results. Furthermore,
it significantly outperforms alternative methods for uncertain data management.
