Checking Violation Tolerance of Approaches to Database Integrity

Abstract. A hitherto unquestioned assumption made by all methods for integrity checking has been that the database satisfies its constraints before each update. This consistency assumption has been exploited for improving the efficiency of determining whether integrity is satisfied or violated after the update. Based on a notion of violation tolerance, we present and discuss an abstract property which, for any given approach to integrity checking, is an easy, sufficient condition to check whether the consistency assumption can be abandoned without sacrificing usabil-ity and efficiency of the approach. We demonstrate the usefulness of our definitions by showing that the theorem-proving approach to database in-tegrity by Sadri and Kowalski, as well as several other well-known meth-ods, can indeed afford to abandon the consistency assumption without losing their efficiency, while their applicability is vastly increased.