A dichotomy in the complexity of consistent query answering for queries with two atoms

We establish a dichotomy in the complexity of computing the consistent answers of a Boolean conjunctive query with exactly two atoms and without self-joins. Specifically, we show that the problem of computing the consistent answers of such a query either is in P or it is coNP-complete. Moreover, we give an efficiently checkable criterion for determining which of these two possibilities holds for a given query.

► Complexity of consistent answers of self-join free conjunctive queries with two atoms. ► Dichotomy theorem for the complexity established. ► Computing the certain answers either is in P or it is coNP-complete.