Computing Minimum Subset Repair on Incomplete Data

Subset repair of inconsistent data is an important research problem in the field of data cleaning. For an inconsistent data set, subset repair removes a minimal set of tuples such that the integrity constraints are no longer violated in the remaining tuples. There is a vast body of work in subset repair, among which the minimum subset repair has attract the most attention due to its good repair performance and few modification to the dataset. However, the effectiveness of the minimum subset repair will be significantly affected when there are missing values in the dataset. We intuitively notice that under a proper model, the probability of the correct imputations will be larger than that of the wrong ones. Therefore, we propose to compute all possible imputations and quantify the correctness as probabilities. Then the original dataset can be extended to a probabilistic database where the effect of missing values on the distribution of inconsistent tuples can be effectively alleviated. In this paper, we first formalize the minimum subset repair on incomplete data problem and explicitly analyze its hardness. Then we propose an efficient imputation approach and a scalable inference method to construct the probabilistic database. Finally, an efficient approximation algorithm for computing the minimum subset repair on incomplete data is proposed. Extensive experiments on real-world datasets show that our proposal achieves higher precision and recall compared to state-of-the-art methods.