# Simplified Integrity Checking for an Expressive Class of Denial Constraints
## 4 A Simplification Procedure for Obtaining a Pre-Test
### The Core Language \(\mathcal{L}_{5}\)  
We now formally characterize a language, that we call \(\mathcal{L}_{5}\), on which a core simplification procedure can be applied. We introduce a few technical notions that are needed in order to precisely identify the class of predicates, integrity constraints, and updates that are part of \(\mathcal{L}_{5}\), which is a non-recursive, function-free language equipped with negation. **Definition 5** (Starred dependency graph). : _Let \(S=\langle IDB,\Gamma\rangle\) be a schema in which the IDB consists of a set of disjunctive (range-restricted) predicate definitions and \(\Gamma\) is a set of range-restricted denials. Let \(\mathcal{G}\) be a graph that has a node \(N^{p}\) for each predicate \(p\) in \(S\) plus another node named \(\bot\), and no other node; if \(p\)'s defining formula has variables not occurring in the head, then \(N^{p}\) is marked with a \"\({}^{\ast}\)\". For any two predicates \(p\) and \(p^{\prime}\) in \(S\), \(\mathcal{G}\) has an arc from \(N^{p}\) to \(N^{p^{\prime}}\) for each occurrence of \(p\) in an IDB rule in which \(p^{\prime}\) occurs in the head; similarly, there is an arc from \(N^{p}\) to \(\bot\) for each occurrence of \(p\) in the body of a denial in \(\Gamma\). In both cases, the arc is labelled with a \"\(-\)\" (and said to be negative) if \(p\) occurs negatively. \(\mathcal{G}\) is the starred dependency graph for \(S\)._  
**Example 3**. : _Let \(S_{1}=\langle IDB_{1},\Gamma_{1}\rangle\) and \(S_{2}=\langle IDB_{2},\Gamma_{2}\rangle\) be schemata with_  
\[ \begin{array}{rcl}IDB_{1}&=\{&s_{1}(X)\gets r_{1}(X,Y)\},\\ \Gamma_{1}&=\{&\leftarrow p_{1}(X)\wedge\
eg s_{1}(X)\},\\ IDB_{2}&=\{&s_{2}(X)\gets r_{2}(X,Y),\\ &&q_{2}(X)\leftarrow\
eg s_{2}(X)\wedge t_{2}(X)\},\\ \Gamma_{2}&=\{&\leftarrow p_{2}(X)\wedge\
eg q_{2}(X)\}.\end{array} \]  
_The starred dependency graphs of \(S_{1}\) and \(S_{2}\) are shown in Figure 2._  
**Definition 6** (\(\mathcal{L}_{5}\)). : _A schema \(S\) is in \(\mathcal{L}_{5}\) if its starred dependency graph \(\mathcal{G}\) is acyclic and, in every path in \(\mathcal{G}\) from a starred node to \(\bot\), the number of arcs labelled with \"\(-\)\" is even. An update \(\{p_{1}(\overrightarrow{X}_{1})\Leftarrow q_{1}(\overrightarrow{X}_{1}),\ \ldots,\ p_{m}( \overrightarrow{X}_{m})\Leftarrow q_{m}(\overrightarrow{X}_{m})\}\) is in \(\mathcal{L}_{5}\) if the graph obtained from \(\mathcal{G}\) by adding an arc from \(N^{q_{i}}\) to \(N^{p_{i}}\), \(1\leq i\leq m\) meets the above condition._  
Acyclicity corresponds to absence of recursion. The second condition requires that the unfolding of the intensional predicates in the constraint theory does not introduce any negated existentially quantified variable. In particular, starred nodes correspond to literals with existentially quantified variable (called _non-distinguished_). In order to avoid negated existential quantifiers, the number of \"\(-\)\" signs must be even, as an even number of negations means no negation. This requirement will be removed in the next section. **Example 4**. : _Consider \(S_{1}\) and \(S_{2}\) from Example 3. Clearly, \(S_{1}\) is not in \(\mathcal{L}_{5}\), as in its starred dependency graph \(\mathcal{G}_{1}\) in Figure 2, there is a path from \(s_{1}^{\ast}\) to \(\bot\) containing one \"\(-\)\" arc, while \(S_{2}\) is in \(\mathcal{L}_{5}\), as in \(\mathcal{G}_{2}\), the only path from \(s_{2}^{\ast}\) to \(\bot\) contains two \"\(-\)\" arcs._  
Figure 2: The starred dependency graphs for the schemata of Example 3. The plan is now to refine the sketch shown in Figure 1 so as to specialize the application of the After and Optimize operators for the \(\mathcal{L}_{\mathsf{s}}\) language.