# Repair-Based Degrees of Database Inconsistency: Computation and Complexity

arXiv: https://arxiv.org/abs/1809.10286 · HTML: https://mlsanity.com/paper/1809.10286/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2018.

## Built on by (most cited first, 2 of 2)

- [Score-Based Explanations in Data Management and Machine Learning: An Answer-Set Programming Approach to Counterfactual Analysis](https://mlsanity.com/paper/2106.10562/) (2021)
- [Attribution-Scores in Data Management and Explainable Machine Learning](https://mlsanity.com/paper/2308.00184/) (2023)

## Abstract (arXiv)

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.