Abstract
Answering queries over incomplete data is ubiquitous in data management and in many AI applications that use query rewriting to take advantage of
relational database technology. In these scenarios
one lacks full information on the data but queries
still need to be answered with certainty. The certainty aspect often makes query answering unfeasible except for restricted classes, such as unions of
conjunctive queries. In addition often there are no,
or very few, certain answers, thus expensive computation is in vain. Therefore we study a relaxation of certain answers called best answers. They
are defined as those answers for which there is no
better one (that is, no answer true in more possible worlds). When certain answers exist the two
notions coincide. We compare different ways of
casting query answering as a decision problem and
characterise its complexity for first-order queries,
showing significant differences in the behaviour of
best and certain answers. We then restrict attention
to best answers for unions of conjunctive queries
and produce a practical algorithm for finding them
based on query rewriting techniques