Repair-Based Degrees of Database Inconsistency: Computation and Complexity
This work addresses the problem of measuring inconsistency in databases for database management and integrity constraint enforcement, presenting incremental improvements in computational methods.
The paper tackles the problem of quantifying database inconsistency with respect to integrity constraints by proposing a generic numerical measure based on repair semantics, specifically investigating a cardinality-repair measure that can be computed via answer-set programs but is sometimes intractable, with polynomial-time approximations and fixed-parameter tractability results for small updates.
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 deterministic and randomized approximations are exhibited. The behavior of this measure under small updates is analyzed, obtaining fixed-parameter tractability results. Furthermore, alternative inconsistency measures are proposed and discussed.