On Simplification of Database Integrity Constraints

Without proper simplification techniques, database integrity checking can be prohibitively time consuming. Several methods have been developed for producing simplified incremental checks for each update but none until now of sufficient quality and generality for providing a true practical impact, and the present paper is an attempt to fill this gap. On the theoretical side, a general characterization is introduced of the problem of simplification of integrity constraints and a natural definition is given of what it means for a simplification procedure to be ideal. We prove that ideality of simplification is strictly related to query containment; in fact, an ideal simplification procedure can only exist in database languages for which query containment is decidable. However, simplifications that do not qualify as ideal may also be relevant for practical purposes. We present a concrete approach based on transformation operators that apply to integrity constraints written in a rich DATALOG-like language with negation. The resulting procedure produces, at design-time, simplified constraints for parametric transaction patterns, which can then be instantiated and checked for consistency at run-time. These tests take place before the execution of the update, so that only consistency-preserving updates are eventually given to the database. The extension to more expressive languages and the application of the framework to other contexts, such as data integration and concurrent database systems, are also discussed. Our experiments show that the simplifications obtained with our method may give rise to much better performance than with previous methods and that further improvements are achieved by checking consistency before executing the update.