  To answer database queries over incomplete data the gold standard is finding
certain answers: those that are true regardless of how incomplete data is
interpreted. Such answers can be found efficiently for conjunctive queries and
their unions, even in the presence of constraints. With negation added, the
problem becomes intractable however. We concentrate on the complexity of
certain answers under constraints, and on effficiently answering queries
outside the usual classes of (unions) of conjunctive queries by means of
rewriting as Datalog and first-order queries. We first notice that there are
three different ways in which query answering can be cast as a decision
problem. We complete the existing picture and provide precise complexity bounds
on all versions of the decision problem, for certain and best answers. We then
study a well-behaved class of queries that extends unions of conjunctive
queries with a mild form of negation. We show that for them, certain answers
can be expressed in Datalog with negation, even in the presence of functional
dependencies, thus making them tractable in data complexity. We show that in
general Datalog cannot be replaced by first-order logic, but without
constraints such a rewriting can be done in first-order. The paper is under
consideration in Theory and Practice of Logic Programming (TPLP).
