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), which is obtained by a minimum number of tuple deletions, and an optimal update repair (optimal U-repair), which 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 Urepair, 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. reduction to S-repairs, where the loss in approximation is linear in the number of attributes. Hence, we obtain a constant-ratio approximation, where the constant has a linear dependence on the number of attributes. Kolahi and Lakshmanan [33] also gave an approximation for optimal U-repairs, but their worst-case approximation can be quadratic in the number of attributes. We show an infinite sequence of FD sets where this gap is actually realized. However, we also show an infinite sequence where our approximation is linear in the number of attributes, but theirs remains constant. Hence, in general, the two approximations are incomparable, and we can combine the two by running both approximations and taking the best. Stepping outside the framework of repairs, a different approach to data cleaning is probabilistic [4, 28, 39] . The idea is to define a probability space over possible clean databases, where the probability of a database is determined by the extent to which it satisfies the integrity constraints. The goal is to find a most probable database that, in turn, serves as the clean outcome. As an instantiation, Gribkoff, Van den Broeck, and Suciu [28] identify probabilistic cleaning as the "Most Probable Database" problem (MPD): given a tuple-independent probabilistic database [20, 42] and a set of FDs, find the most probable database among those satisfying the FDs (or, put differently, condition the probability space on consistency). They show a dichotomy for unary FDs, that is, FDs with a single attribute on the left-hand side. The case of general (not necessarily unary) FDs has been left open. It turns out that there are reductions from MPD to computing an optimal S-repair and vice versa. Consequently, we are able to generalize their dichotomy to all FDs, and hence, fully settle the open problem. This article extends a conference publication of the authors [37] . Compared to the conference version, the extension is as follows. First, we have strengthened the dichotomy in the complexity of MPD with hardness of approximation on the negative side (Theorem 3.8). Second, we have added all the proofs and intermediate results that were excluded from the conference paper. In particular, Section 4 is new and contains the full proof of our main result-the dichotomy in the complexity for S-repairs (Theorem 3.4). Moreover, we have added the proofs of Theorems 5. 2, 5.5, 5.12, 5.14, and 5.15 in Section 5. The rest of the article is organized as follows. In Section 2, we give the basic definitions and problem statements. We study the problem of computing an optimal S-repair in Section 3, where we also discuss the connection to MPD. Then, we give the full proof of our dichotomy for S-repairs in Section 4. In Section 5, we study the problem of computing an optimal U-repair. We conclude and discuss future directions in Section 6. We first present some basic terminology and notation that we use throughout the article. An instance of our data model is a single table where each tuple is associated with an identifier and a weight that states how costly it is to change or delete the tuple. Such a table corresponds to a relation schema that we denote by R (A 1 , . . . , A k ) , where R is the relation name and A 1 , . . . , A k are distinct attributes. We say that R(A 1 , . . . , A k ) is k-ary, since it has k attributes. When there is no risk of confusion, we may refer to R(A 1 , . . . , A k ) by simply R. We use capital letters from the beginning of the English alphabet (e.g., A, B, C), possibly with subscripts and/or superscripts, to denote individual attributes, and capital letters from the end of the English alphabet (e.g., X , Y , Z ), possibly with subscripts and/or superscripts, to denote sets of attributes. We follow the convention of avoiding commas and curly braces when writing sets of attributes (e.g., ABC instead of {A, B, C}).
For the upper bound, the best approximation on subset repair is still 2 obtained by solving the corresponding vertex cover problem REF without the limitation on the number of given FDs.
Computing Optimal Repairs for Functional Dependencies
ACM Transactions on Database Systems (TODS)
Computer Science