  Certain answers are a principled method for coping with uncertainty that
arises in many practical data management tasks. Unfortunately, this method is
expensive and may exclude useful (if uncertain) answers. Thus, users frequently
resort to less principled approaches to resolve the uncertainty. In this paper,
we propose Uncertainty Annotated Databases (UA-DBs), which combine an under-
and over-approximation of certain answers to achieve the reliability of certain
answers, with the performance of a classical database system. Furthermore, in
contrast to prior work on certain answers, UA-DBs achieve a higher utility by
including some (explicitly marked) answers that are not certain. UA-DBs are
based on incomplete K-relations, which we introduce to generalize the classical
set-based notions of incomplete databases and certain answers to a much larger
class of data models. Using an implementation of our approach, we demonstrate
experimentally that it efficiently produces tight approximations of certain
answers that are of high utility.
