Efficient Approximation Algorithms for Repairing Inconsistent Databases

Abstract

We consider the problem of repairing a database that is inconsistent wrt a set of integrity constraints by updating numerical values. In particular, we concentrate on denial integrity constraints with numerical built-in predicates. So far research in this context has concentrated in computational complexity analysis. In this paper we focus on efficient approximation algorithms to obtain a database repair and we present an algorithm that runs in O(n log n) wrt the size of the database. Our experimental evaluations show that even for large databases an approximate repair of the database can be computed efficiently despite the fact that the exact problem is computationally intractable. Finally, we show that our results can also be applied to database repairs obtained by a minimal number of tuple deletions.