Querying and Repairing Inconsistent Databases Under Three-Valued Semantics

The problem of managing and querying inconsistent databases has been deeply investigated in the last few years. As, in the general case, the problem of consistent query answering is hard, most of the techniques so far proposed have an exponential complexity. Moreover, polynomial techniques have been proposed only for restricted forms of constraints (e.g. functional dependencies) and queries. In this paper we present a technique which allows us to compute "approximated" consistent answers in polynomial time, for general constraints and queries. The paper presents a three-valued semantics for constraint satisfaction, called deterministic, and considers three valued databases. Thus, a repaired database is a database where atoms may be either true or undefined (whereas missing atoms are false) that satisfies constraints under the deterministic three valued semantics. We show that in querying possibly inconsistent databases the answer is safe (true and false atoms in the answers are, respectively, true and false under the classical two-valued semantics) and the answers can be computed in polynomial time. We also show that deterministic answers can be computed by rewriting constraints into logic programs.