Skip to main content

Computing Optimal Repairs for Functional Dependencies.

Publication ,  Journal Article
Livshits, E; Kimelfeld, B; Roy, S
Published in: Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
June 2018

We investigate the complexity of computing an optimal repair of an inconsistent database, in the case where integrity constraints are Functional Dependencies (FDs). We focus on two types of repairs: an optimal subset repair (optimal S-repair) that is obtained by a minimum number of tuple deletions, and an optimal update repair (optimal U-repair) that is obtained by a minimum number of value (cell) up-dates. For computing an optimal S-repair, we present a polynomial-time algorithm that succeeds on certain sets of FDs and fails on others. We prove the following about the algorithm. When it succeeds, it can also incorporate weighted tuples and duplicate tuples. When it fails, the problem is NP-hard, and in fact, APX-complete (hence, cannot be approximated better than some constant). Thus, we establish a dichotomy in the complexity of computing an optimal S-repair. We present general analysis techniques for the complexity of computing an optimal U-repair, some based on the dichotomy for S-repairs. We also draw a connection to a past dichotomy in the complexity of finding a "most probable database" that satisfies a set of FDs with a single attribute on the left hand side; the case of general FDs was left open, and we show how our dichotomy provides the missing generalization and thereby settles the open problem.

Duke Scholars

Published In

Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISSN

1055-6338

Publication Date

June 2018

Volume

2018

Start / End Page

225 / 237
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Livshits, E., Kimelfeld, B., & Roy, S. (2018). Computing Optimal Repairs for Functional Dependencies. Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2018, 225–237. https://doi.org/10.1145/3196959.3196980
Livshits, Ester, Benny Kimelfeld, and Sudeepa Roy. “Computing Optimal Repairs for Functional Dependencies.Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems 2018 (June 2018): 225–37. https://doi.org/10.1145/3196959.3196980.
Livshits E, Kimelfeld B, Roy S. Computing Optimal Repairs for Functional Dependencies. Proceedings of the . ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2018 Jun;2018:225–37.
Livshits, Ester, et al. “Computing Optimal Repairs for Functional Dependencies.Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, vol. 2018, June 2018, pp. 225–37. Epmc, doi:10.1145/3196959.3196980.
Livshits E, Kimelfeld B, Roy S. Computing Optimal Repairs for Functional Dependencies. Proceedings of the . ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2018 Jun;2018:225–237.

Published In

Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISSN

1055-6338

Publication Date

June 2018

Volume

2018

Start / End Page

225 / 237