Computing Maximal Likelihood Subset Repair for Inconsistent Data

In this paper, we study the problem of subset repair under integrity constraints. For an inconsistent data set, a subset repair removes a minimal set of tuples such that the integrity constraints are no longer violated in the remaining tuples. There usually exist multiple subset repairs and it is difficult to determine which one is optimal. Most previous work prefer the one with minimum number of deleted tuples to avoid excessive removal and information loss. However, it will delete clean tuples and retain dirty tuples when the majority of tuples are dirty in a local scope. We intuitively notice that under a proper model, the correctness probabilities of clean tuples are often larger than that of dirty tuples, and therefore we propose to determine the subset repair with maximum likelihood, which retain tuples with large correctness probability as many as possible. In this paper, we first formalize the maximum likelihood subset repair problem and analyze the hardness. Then we propose a correctness probability model, together with a scalable inference approach. Finally, an efficient approximate algorithm is proposed to compute the maximum likelihood subset repair. Extensive experiments on real-world datasets show that our proposal can achieve higher precision and recall compared with state-of-the-art methods.