Properties of Inconsistency Measures for Databases

Conference Paper

How should we quantify the inconsistency of a database that violates integrity constraints? Proper measures are important for various tasks, such as progress indication and action prioritization in cleaning systems, and reliability estimation for new datasets. To choose an appropriate inconsistency measure, it is important to identify the desired properties in the application and understand which of these is guaranteed or at least expected in practice. For example, in some use cases, the inconsistency should reduce if constraints are eliminated; in others, it should be stable and avoid jitters and jumps in reaction to small changes in the database. We embark on a systematic investigation of properties for database inconsistency measures. We investigate a collection of basic measures that have been proposed in the past in both the Knowledge Representation and Database communities, analyze their theoretical properties, and empirically observe their behavior in an experimental study. We also demonstrate how the framework can lead to new inconsistency measures by introducing a new measure that, in contrast to the rest, satisfies all of the properties we consider and can be computed in polynomial time.

Full Text

Duke Authors

Cited Authors

  • Livshits, E; Kochirgan, R; Tsur, S; Ilyas, IF; Kimelfeld, B; Roy, S

Published Date

  • January 1, 2021

Published In

Start / End Page

  • 1182 - 1194

International Standard Serial Number (ISSN)

  • 0730-8078

Digital Object Identifier (DOI)

  • 10.1145/3448016.3457310

Citation Source

  • Scopus