# Simplified Integrity Checking for an Expressive Class of Denial Constraints
## 1 Introduction  
Data integrity is a ubiquitous concern that is at the basis of crucial objectives such as data correctness and data quality. Typically, a specification of the correct states of a database is given through integrity constraints, which can be thought of as formulas that need to be kept satisfied throughout the life of the database. In any data-intensive scenario, such as an OLTP system, data are updated all the time and, therefore, integrity constraints need to be checked continuously. While DBMSs are able to optimally handle common constraints such as key and foreign key constraints, the standard practice is to resort to ad hoc solutions (for instance, at the application level or through manually designed triggers) when the integrity constraints to be maintained are more complex. Automatic integrity constraint checking--and simplified integrity constraint checking in particular--is a topic that has spurred numerous research attempts since the 1980s [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] with the objective of mechanically producing the best possible set of conditions to check against a database in the face of updates. The main idea, common to the majority of the approaches, is to exploit the assumption that a database is _consistent_ (i.e., satisfies the integrity constraints) before an update; with this, the formula to be checked, corresponding to the originalintegrity constraints, may be simplified so as to avoid checks of subformulas that are already guaranteed to hold thanks to the consistency assumption. For instance, consider the relation \(b(I,T)\), indicating that there is a book with an ISBN \(I\) and a title \(T\). The fact that the ISBN univocally identifies a book can be expressed as the integrity constraint \(T_{1}=T_{2}\gets b(I,T_{1})\wedge b(I,T_{2})\) (with all variables implicitly universally quantified). Now, assume that the tuple \(b(i,t)\) is added to the database. Under the consistency assumption, one just needs to check that there is no other book with the same ISBN \(i\) and a different title than \(t\) (we are using set semantics, so having more than one occurrence of \(b(i,t)\) is harmless), which could be expressed by the simplified formula \(T=t\gets b(i,T)\). Without the consistency assumption, instead, we would have had to check for satisfaction of the original constraint for all the books already present in the database. The difference between the simplified formula and the original one bears heavy implications from the point of view of the complexity of the corresponding check, which, in turn, may depend on the way in which the data are physically organized in the database. In the absence of indices, the simplified formula requires a linear scan of all the books; the original formula, instead, requires checking that, for _every_ book present in the database, there is no other book with the same ISBN and a different title, which entails a quadratic (i.e., much higher) cost in the size of the table. With indices (say, a hash-based index on the ISBN), the original check would simply require a linear scan of the books, as an ISBN-based lookup would then take constant time; however, with the same index, the simplified formula would no longer require a linear scan, because a single (constant-time, thus much faster) lookup of the hash-based index would suffice. Overall, simplified integrity checking aims to maintain satisfaction of the integrity constraints (specified at database schema design time) after each update to the data without overburdening the system with checks that would be too long to carry out. So, \"simplification\" in this sense means to obtain tests that are simpler to verify than the original constraints, while achieving the same verification effects. As rooted in the defining properties of databases, integrity constraints are one of the building blocks of relational technology and their maintenance is one of the core aspects of DBMSs, which have to guarantee integrity constraint satisfaction at all times.