Approximating Optimal Soft Repairs for Denial Constraints

Computing optimal soft repairs of inconsistent relational databases with respect to functional dependencies (rel-fd-OSR) is known to be NP-hard. Constant-ratio approximation algorithms for rel-fd-OSR have been well studied. However, it is still open whether there is a constant ratio approximation algorithm for optimal soft repairs of inconsistent relational databases with respect to denial constraints (rel-dc-OSR). This paper studies an LP-based framework for approximating rel-dc-OSR. Based on this framework, we obtain a polynomial-time (λ + 1)-approximation algorithm for rel-dc-OSR where the constant λ is the maximum number of tuples involved in a violation with respect to the given set of DCs. Moreover, the approximation ratio reduces to 2 when λ = 2, thus immediately improving the state of the art 3-approximation algorithm for rel-fd-OSR.The application of our framework can also be extended to computing optimal soft repairs of inconsistent temporal databases with respect to DCs (temp-dc-OSR). We show that a (λ +1)-approximation algorithm that runs in polynomial time can be easily derived for temp-dc-OSR based on our framework and a polynomial-time λ-approximation can be obtained for temp-dc-OSR of all given DCs are hard constraints. Experiments on five real-world datasets (up to 100K tuples and tens of millions of violations) show that algorithms derived from our framework achieve up to 21% lower repair cost than existing methods while maintaining stable running times and improved discriminative power for query answering.