Skip to main content

Properties of Inconsistency Measures for Databases

Publication ,  Conference
Livshits, E; Kochirgan, R; Tsur, S; Ilyas, IF; Kimelfeld, B; Roy, S
Published in: Proceedings of the ACM SIGMOD International Conference on Management of Data
January 1, 2021

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.

Duke Scholars

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

Publication Date

January 1, 2021

Start / End Page

1182 / 1194
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Livshits, E., Kochirgan, R., Tsur, S., Ilyas, I. F., Kimelfeld, B., & Roy, S. (2021). Properties of Inconsistency Measures for Databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 1182–1194). https://doi.org/10.1145/3448016.3457310
Livshits, E., R. Kochirgan, S. Tsur, I. F. Ilyas, B. Kimelfeld, and S. Roy. “Properties of Inconsistency Measures for Databases.” In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1182–94, 2021. https://doi.org/10.1145/3448016.3457310.
Livshits E, Kochirgan R, Tsur S, Ilyas IF, Kimelfeld B, Roy S. Properties of Inconsistency Measures for Databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2021. p. 1182–94.
Livshits, E., et al. “Properties of Inconsistency Measures for Databases.” Proceedings of the ACM SIGMOD International Conference on Management of Data, 2021, pp. 1182–94. Scopus, doi:10.1145/3448016.3457310.
Livshits E, Kochirgan R, Tsur S, Ilyas IF, Kimelfeld B, Roy S. Properties of Inconsistency Measures for Databases. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2021. p. 1182–1194.

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

Publication Date

January 1, 2021

Start / End Page

1182 / 1194