Paper Info
Title
Computing Optimal Repairs for Functional Dependencies
Abstract
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) updates. 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.
Year
DOI
Venue
2017
10.1145/3196959.3196980
SIGMOD/PODS '18: International Conference on Management of Data Houston TX USA June, 2018
Keywords
Field
DocType
Inconsistent Databases, Database Cleaning, Optimal Repairs, Cardinality Repairs, Value Repairs, Functional Dependencies, Dichotomy, Approximation
Open problem,Tuple,Computer science,Theoretical computer science,Functional dependency,Data integrity
Journal
Volume
ISBN
Citations 
abs/1712.07705
978-1-4503-4706-8
3
PageRank 
References 
Authors
0.38
23
3
Name
Order
Citations
PageRank
Ester Livshits154.47
Benny Kimelfeld2103471.63
Sudeepa Roy326830.95