Approximation and inapproximability results on computing optimal repairs

Computing optimal subset repairs and optimal update repairs of an inconsistent database has a wide range of applications and is becoming standalone research problems. However, these problems have not been well studied in terms of both inapproximability and approximation algorithms. In this paper, we prove a new tighter inapproximability bound for computing optimal subset repairs. We show that it is frequently NP-hard to approximate an optimal subset repair within a factor better than 143/136. We develop an algorithm for computing optimal subset repairs with an approximation ratio (2 - 1 / 2 ^σ-1) , where σ is the number of functional dependencies. We improve it when the database contains a large amount of quasi-Turán clusters. We then extend our work for computing optimal update repairs. We show it is NP-hard to approximate an optimal update repair within a factor better than 143/136 for representative cases. We further develop an approximation algorithm for computing optimal update repairs with an approximation ratio mlc(Σ)(2 - 1 / 2 ^σ-1) , where mlc(Σ) depends on the given functional dependencies. We conduct experiments on real data to examine the performance and the effectiveness of our proposed approximation algorithms.