2019
Repair-Based Degrees of Database Inconsistency
Publication
Publication
We propose and investigate a concrete numerical measure of the inconsistency of a database with respect to a set of integrity constraints. It is based on a database repair semantics associated to cardinality-repairs. More specifically, it is shown that the computation of this measure can be intractable in data complexity, but answer-set programs are exhibited that can be used to compute it. Furthermore, its is established that there are polynomial-time deterministic and randomized approximations. The behavior of this measure under small updates is analyzed, obtaining fixed-parameter tractability results. We explore abstract extensions of this measure that appeal to generic classes of database repairs. Inconsistency measures and repairs at the attribute level are investigated as a particular, but relevant and natural case.
Additional Metadata | |
---|---|
doi.org/10.1007/978-3-030-20528-7_15 | |
Lecture Notes in Computer Science | |
Organisation | School of Computer Science |
Bertossi, L. (2019). Repair-Based Degrees of Database Inconsistency. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-20528-7_15
|