Repair-Based Degrees of Database Inconsistency: Computation and Complexity
share
We propose a generic numerical measure of the inconsistency of a database with respect to a set of integrity constraints. It is based on an abstract repair semantics. In particular, an inconsistency measure associated to cardinality-repairs is investigated in detail. More specifically, it is shown that it can be computed via answer-set programs, but sometimes its computation can be intractable in data complexity. However, polynomial-time fixed-parameter exact computation, and also deterministic and randomized approximations are exhibited. The behavior of this measure under small updates is analyzed. Furthermore, alternative inconsistency measures are proposed and discussed.
READ FULL TEXT