# Simplified Integrity Checking for an Expressive Class of Denial Constraints
## 2 Related Work  
The idea of simplifying integrity constraints has been long recognized, dating back to at least [1; 2], as discussed in the previous section. We continued this line of research in [15; 16]. In particular, in [15], we considered an expressive language, \(\mathcal{L}_{\text{\tiny tot}}\), for formulating schemata and constraints, for which we could provide a sound and terminating simplification procedure. An important distinction between our work and other simplification techniques is the \"preventive\" approach that we adopt; we check whether an update is legal before executing it, so that no work needs to be undone if an illegal update is detected. All other approaches in the literature adopt a \"corrective\" approach instead, i.e., the update is always executed, then the updated databases is checked for integrity violations, and, if needed, the update is undone. Evidently, a preventive approach allows one to avoid a lot of unneeded work in case of illegal updates (their execution and the subsequent retraction). The simplification problem is also tightly connected to query containment (QC) [17], i.e., the problem of establishing whether, given two queries \(q_{1}\) and \(q_{2}\), the answer to \(q_{1}\) is always a subset of the answer to \(q_{2}\) for all database instances. Indeed, \"perfect\" simplifications may be generated if and only if QC is decidable. Unfortunately, QC is already undecidable for datalog databases without negation [18; 19]. The kind of integrity constraints considered here are the so-called _static_ integrity constraints, in that they refer to properties that must be met by the data in each database state. _Dynamic_ constraints, instead, are used to impose restrictions on the way the database states can evolve over time, be it on successive states or on arbitrary sets of states. Dynamic constraints have been considered, e.g., in [20; 21]. Another important distinction can be made between _hard_ (or _strong_) constraints and _soft_ (or _denotic_) constraints. The former ones are used to model necessary requirements of the world that the database represents, like the constraints studied here. Deontic constraints govern what is obligatory but not necessary of the world, so violations of deontic constraints correspond to violations of obligations that have to be reported to the user or administrator of the database rather than inconsistencies proper. The wording \"soft constraint\" sometimes refers to a condition that should preferably be satisfied, but may also be violated. Deontic constraints have been considered, e.g., in [22] and soft constraints in [23]. Soft constraints are akin to preferences, covered by an abundant literature [24; 25; 26; 27; 28; 29; 30]. Other kinds of constraints, of a more structural nature, are the so-called access constraints, or access patterns, whose interaction with integrity constraints proper has also been studied [31]. Often, integrity constraints are characterized as _dependencies_. Many common dependencies are used in database practice. Among those involving a single relation, we mention _functional dependencies_[32] (including _key dependencies_) and _multi-valued dependencies_[33; 34]. For the inter-relation case, the most common ones are _inclusion dependencies_ (i.e., _referential constraints_). All of these can straightforwardly be represented as extended denials. In particular, many authors acknowledge tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs) to be the most important types of dependencies in a database, since they encompass most others [35] and are also commonly used for schema mappings in data exchange [36]. The dependencies can be expressed by our extended denials, as we will show in Section 5. So our framework captures the most representative cases of constraints used in the literature. More detailed classifications of integrity constraints for deductive databases have been attempted by several authors, e.g., [37; 38; 39].