First-Order Rewritability of Rule-Based Ontology Mediated Queries with Negation

Rule-based languages lie at the core of numerous areas of central importance to databases and artificial intelligence. It is widely accepted that tuple-generating dependencies (tgds) form a prominent rule-based language, originally introduced as a unifying framework for database constraints [1]. Tgds are first-order sentences of the form $\forall \overline{x}\forall \overline{y}\left(\varphi (\overline{x},\overline{y})\to \exists \overline{z}\psi (\overline{x},\overline{z})\right)$, where $\varphi$ (the body) and $\psi$ (the head) are conjunctions of relational atoms, and they essentially state that certain tuples in a database imply the presence of some other tuples in the database. The last fifteen years or so, they have been employed for knowledge representation purposes, in particular, as an alternative way to model ontologies that are used to enrich user queries, typically conjunctive queries, with domain knowledge. The marriage of ontologies with user queries has been originally proposed in the context of ontology-based data integration in order to facilitate access to data that is heterogeneous and incomplete [14]. The ontology and the user query can be conveniently seen as two components of one composite query, called ontology-mediated query (omq) [6]. In this context, the main problem of interest is to compute the answer to such an omq over a database. In particular, given a database $D$ and an omq $O=(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }$ is a finite set of tgds (the ontology) and $Q$ a conjunctive query (the user query), the goal is compute the certain answers to $O$ over $D$, denoted $\mathrm{𝖺𝗇𝗌}(O,D)$, which are all the tuples of database elements that are answers to $Q$ no matter on which model of $D$ and $\mathrm{\Sigma }$ it is evaluated, i.e., the answers to $Q$ derived by every model of $D$ and $\mathrm{\Sigma }$.

Building ontology-aware database systems from scratch, with sophisticated optimization techniques, is a highly non-trivial task that requires a great effort. An alternative approach towards practical implementations of evaluating an omq over a database is to use conventional database systems. However, such systems are unaware of ontologies. This obstacle can be addressed by query rewriting: the omq $O=(\mathrm{\Sigma },Q)$ is rewritten into a new query $Q_O$, the so-called rewriting, which has the same answer as the omq $O$ over all input databases, i.e., for every database $D$, $\mathrm{𝖺𝗇𝗌}(O,D)$ coincides with the answer to $Q_O$ over $D$. It is of course essential that the query $Q_O$ is expressed in a query language that can be handled by standard database systems. The typical target query language that is considered in this setting is that of first-order queries. The problem of rewriting omqs into first-order queries, when the ontology is a set of tgds and the user query a conjunctive query, has been extensively studied. This research effort led to several syntactic classes $𝖢$ of tgds that give rise to first-order rewritable classes of omqs $(𝖢,\mathrm{𝖢𝖰})$, i.e., every omq $(\mathrm{\Sigma },Q)$ of $(𝖢,\mathrm{𝖢𝖰})$, where $\mathrm{\Sigma }$ is a set of tgds from $𝖢$ and $Q$ a query from the class of conjunctive queries $\mathrm{𝖢𝖰}$, admits a first-order rewriting, together with prototype systems illustrating the effectiveness of this approach; see, e.g., [7, 8, 10, 12]. What is even more remarkable is the fact that every first-order rewritable tgd-based class of omqs, no matter how the class of tgds is defined, can be handled via one uniform rewriting algorithm. More precisely, there is a resolution-based algorithm $\mathrm{𝖱𝖾𝗐𝗋𝗂𝗍𝖾}$ such that, for every class $𝖢$ of tgds, the omq class $(𝖢,\mathrm{𝖢𝖰})$ is first-order rewritable iff for every omq $O$ from $(𝖢,\mathrm{𝖢𝖰})$, $\mathrm{𝖱𝖾𝗐𝗋𝗂𝗍𝖾}$ on input $O$ terminates and returns a first-order rewriting of $O$ [12]. This provides an algorithmic characterization of when an omq class $(𝖢,\mathrm{𝖢𝖰})$, where $𝖢$ is a class of tgds, is first-order rewritable.

Although conjunctive queries form a key tool for querying data, they are not able to express negation, a very useful construct that allows us to express non-monotonic queries that naturally appear in real-life scenarios. It is thus very natural to consider classes of tgd-based omqs $(𝖢,{\mathrm{𝖢𝖰}}^{\neg })$, where the user query comes from the class of conjunctive queries with negation, denoted ${\mathrm{𝖢𝖰}}^{\neg }$. The problem of evaluating such non-positive omqs has also attracted attention in the literature; see, e.g., [3, 4, 7, 9, 11]. Having said that, answering non-positive omqs of this kind via first-order rewritability, unlike the case of positive omqs discussed above, is largely unexplored. An interesting question is whether the algorithmic characterization discussed above concerning the first-order rewritability of positive omqs can be extended to non-positive omqs. More precisely, we are asking whether there exists one uniform algorithm, which does not depend on any class of tgds, that acts as a first-order rewriter for every class $(𝖢,{\mathrm{𝖢𝖰}}^{\neg })$ of tgd-based omqs that is first-order rewritable. The goal of this work is to initiate effort towards the settlement of this highly non-trivial question. But first we need to discuss how the answer to such omqs should be defined, and, in fact, whether the standard certain answers semantics is conceptually meaningful in this case.

Consider the database $D=\{R(a),S(b)\}$ and the omq $O=(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }$ consists of the tgd $\forall x(R(x)\to \exists yP(x,y))$ and $Q$ is the Boolean query $\text{Ans}\text{:-}R(x),P(x,y),\neg S(x)$. The answer to $O$ over $D$ is empty (i.e., the query is false) since there exists at least one model of $D$ and $\mathrm{\Sigma }$ that does not entail $Q$; e.g., the model $I=\{R(a),S(b),P(a,a),S(a)\}$ does not entail $Q$ due to the atom $S(a)$ since the only way to match the positive part of $Q$ to $I$ is by mapping both variables $x$ and $y$ to $a$, whereas $S(a)$ belongs to $I$. On the other hand, $S(a)$ is not supported by $D$ and $\mathrm{\Sigma }$. Indeed, there is no reason to derive the atom $S(a)$ since the instance $I\setminus \{S(a)\}$ is also a model of $D$ and $\mathrm{\Sigma }$. Hence, the model $I$ should not be a valid reason for the non-entailment of $Q$ by $D$ and $\mathrm{\Sigma }$. The above example can be generalized and show that for a database $D$ and an omq $O=(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }$ is set of tgds and $Q$ a conjunctive query with at least one negated atom, there is always a model $I$ of $D$ and $\mathrm{\Sigma }$ such that the answer to $Q$ over $I$ is empty – $I$ is simply the model that collects all the atoms that can be formed using the predicates of the schema and the constants in $D$ and $Q$.

The above discussion leads to the natural idea that has been adopted in the literature of considering only models without redundant information that may distort the expected answer to the given omq, i.e., considering only minimal models. Coming back to the above example, it is easy to see that $Q$ is entailed by every minimal model of $D$ and $\mathrm{\Sigma }$. Hence, the main problem of interest in this context is as follows: given a database $D$ and an omq $(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }$ is a set of tgds and $Q$ a conjunctive query with negation, compute all the tuples of database elements that are answers to $Q$ derived by every minimal model of $D$ and $\mathrm{\Sigma }$.

Once we adopt the minimal model semantics, there is one more aspect that we need to carefully consider, which has to do with the existentially quantified variables in tgd-heads, that greatly affects the obtained semantics: either keep those existentially quantified variables, or eliminate them via the standard technique of Skolemization. Both approaches are quite relevant and have been considered in the literature; see, e.g., [2, 9]. In this work, we focus on the latter, which we call Skolem semantics. Let us clarify that for positive tgd-based omqs, considering all the models or only the minimal models, and keeping or eliminating the existentially quantified variables in tgd-heads, lead to the exact same semantics.

This work makes a first non-trivial step towards an algorithmic characterization of when an omq class $(𝖢,{\mathrm{𝖢𝖰}}^{\neg })$, where $𝖢$ is a class of tgds, is first-order rewritable. In particular, we establish the existence of an algorithm that, no matter which class $𝖢$ of tgds we consider among linear or acyclic tgds – two central classes of tgds that ensure first-order rewritability for positive omqs – is a first-order rewriter for $(𝖢,{\mathrm{𝖢𝖰}}^{\neg })$ under the Skolem semantics. This new algorithm is significantly more sophisticated than the one for positive omqs as it needs to carefully treat the negative part of the user query. We strongly believe that it can serve as a good starting point towards an algorithmic characterization of first-order rewritability for non-positive classes of tgd-based omqs under the Skolem semantics. Interestingly, the proposed algorithm produces rewritings that fall in a novel fragment of first-order queries, which is strictly less expressive than the full language of first-order queries. We also show that unions of conjunctive queries with equality and negation are not powerful enough for our purposes as one might think, influenced by the fact that unions of conjunctive queries with equality are enough for positive tgd-based omqs.

Let $𝐂$, $𝐍$ and $𝐕$ be disjoint countably infinite sets of constants, (marked) nulls and variables, respectively. We further consider the countably infinite set $𝐅$ of function symbols (each of them associated with a positive arity), which is disjoint from $𝐂$, $𝐍$ and $𝐕$. We assume that different constants represent different objects and different function symbols represent different functions (unique name assumption). Functional terms are inductively defined as follows: (i) variables are functional terms, and (ii) $f(t_1,\mathrm{\dots },t_n)$, where $n>0$, $f$ is an $n$-ary function symbol of $𝐅$, and $t_1,\mathrm{\dots },t_n$ are functional terms, is a functional term. Ground functional terms are defined similarly: (i) constants of $𝐂$ are ground functional terms, and (ii) $f(t_1,\mathrm{\dots },t_n)$, where $n>0$, $f$ is an $n$-ary function symbol of $𝐅$, and $t_1,\mathrm{\dots },t_n$ are ground functional terms, is a ground functional term. We refer to constants, nulls, variables, functional terms, and ground functional terms as terms.

A schema $𝐒$ is a finite set of relation names (or predicates) with associated positive arity. We write $R/n$ to say that $R$ has arity $n>0$; we may write $\mathrm{𝖺𝗋}(R)$ for the integer $n$. A (relational) atom $\alpha$ over $𝐒$ is an expression of the form $R(\overline{t})$, where $R/n\in 𝐒$ and $\overline{t}$ is an $n$-tuple of terms; note that we may treat a tuple as the set of its elements. For a set $A$ of atoms, we write $\mathrm{𝗍𝖾𝗋𝗆𝗌}(A)$ and $\mathrm{𝗏𝖺𝗋}(A)$ for the set of terms and variables, respectively, mentioned in the atoms of $A$.

A central notion is that of homomorphism that allows us to embed a set of atoms into another set of atoms while preserving its structure. Formally, a homomorphism from a set of atoms $A$ to a set of atoms $B$ is a function $h:\mathrm{𝗍𝖾𝗋𝗆𝗌}(A)\to \mathrm{𝗍𝖾𝗋𝗆𝗌}(B)$ that is the identity on $𝐂$ with $R(h(\overline{t}))\in B$ for every $R(\overline{t})\in A$; for a term $f(t_1,\mathrm{\dots },t_n)$, $h(f(t_1,\mathrm{\dots },t_n))=f(h(t_1),\mathrm{\dots },h(t_n))$. We write $A\to B$ to denote that there is a homomorphism from $A$ to $B$.

We make the distinction between instances that mention only constants and nulls and instances that mention only ground functional terms. A null instance over a schema $𝐒$ is a (possibly infinite) set of atoms over $𝐒$ that mention only constants and nulls. A functional instance over $𝐒$ is a (possibly infinite) set of atoms over $𝐒$ that mention only ground functional terms. A database over $𝐒$ is a non-empty finite set of atoms over $𝐒$ that mention only constants. Clearly, a database over $𝐒$ is trivially a null and a functional instance over $𝐒$. We write $\mathrm{𝖽𝗈𝗆}(I)$ for the set of terms occurring in an instance $I$.

We assume the reader is familiar with the syntax and semantics of first-order logic. We consider only function-free first-order formulas, i.e., formulas that mention variables and constants of $𝐂$, but no function symbols. For such a formula $\mathrm{\Phi }$, we write $\mathrm{𝖿𝗏}(\mathrm{\Phi })$ and $\mathrm{𝖽𝗈𝗆}(\mathrm{\Phi })$ for the set of its free variables and the set of constants occurring in it, respectively. We use the standard symbol $\vDash$ for the notion of satisfaction of sentences. A first-order query $Q$ over a schema $𝐒$ is an expression $\{(x_1,\mathrm{\dots },x_k)\mid \mathrm{\Phi }\}$, for $k\ge 0$, where $\mathrm{\Phi }$ is a first-order formula over $𝐒$ and $(x_1,\mathrm{\dots },x_k)$ is a tuple over $\mathrm{𝖿𝗏}(\mathrm{\Phi })$ such that each variable of $\mathrm{𝖿𝗏}(\mathrm{\Phi })$ occurs in $(x_1,\mathrm{\dots },x_k)$ at least once, i.e., $\mathrm{𝖿𝗏}(\mathrm{\Phi })=\{x_1,\mathrm{\dots },x_k\}$. Note that a first-order query is always a finite object, i.e., the first-order formula $\mathrm{\Phi }$ above is finite. For a tuple of constants $(c_1,\mathrm{\dots },c_k)$, we write $\mathrm{\Phi }(c_1,\mathrm{\dots },c_k)$ for the sentence obtained from $\mathrm{\Phi }$ after replacing each occurrence of $x_i$ with $c_i$, for each $i\in [k]$. Given a database $D$ over $𝐒$, the answer to $Q$ over $D$ is the set $Q(D)=\{(c_1,\mathrm{\dots },c_k)\in {(\mathrm{𝖽𝗈𝗆}(D)\cup \mathrm{𝖽𝗈𝗆}(\mathrm{\Phi }))}^k\mid D\vDash \mathrm{\Phi }(c_1,\mathrm{\dots },c_k)\}$.

A restricted class of first-order queries that is crucial for our work is that of conjunctive queries with negation. Formally, a conjunctive query with negation (ncq) $Q$ over a schema $𝐒$ is a first-order query $\{\overline{x}\mid \mathrm{\Phi }\}$ over $𝐒$ with $\mathrm{\Phi }$ being a formula of the form $\exists \overline{y}\left(R_1({\overline{y}}_1)\wedge \mathrm{\cdots }\wedge R_n({\overline{y}}_n)\wedge \neg P_1({\overline{z}}_1)\wedge \mathrm{\cdots }\wedge \neg P_m({\overline{z}}_m)\right)$ for $n\ge 1$ and $m\ge 0$, where (i) $R_i({\overline{y}}_i)$ and $P_j({\overline{z}}_j)$ are atoms with ${\overline{y}}_i$ and ${\overline{z}}_j$ being tuples of constants and variables mentioned in $\overline{x}$ and $\overline{y}$, for each $i\in [n]$ and $j\in [m]$, and (ii) for each $j\in [m]$, each variable in ${\overline{z}}_j$ is mentioned in ${\overline{y}}_i$ for some $i\in [n]$; the latter condition means that the negation in $Q$ is safe. Note that if $m=0$, i.e., there are no negated atoms, then $Q$ is simply a conjunctive query (cq). We write $Q^{+}$ for the non-empty set of atoms $\{R_1({\overline{y}}_1),\mathrm{\dots },R_n({\overline{y}}_n)\}$ and $Q^{-}$ for the (possibly empty) set of atoms $\{P_1({\overline{z}}_1),\mathrm{\dots },P_m({\overline{z}}_m)\}$. Let ${\mathrm{𝖢𝖰}}^{\neg }$ be the set of all ncqs and $\mathrm{𝖢𝖰}$ the set of all cqs. It is well-known that the semantics of ncqs can be conveniently defined via homomorphisms. Given a null or functional instance $I$, the answer to $Q$ over $I$, denoted $Q(I)$, is the set of all tuples $\overline{c}\in {𝐂}^{|\overline{x}|}$ such that (i) there is a homomorphism $h$ from $Q^{+}$ to $I$ with $h(\overline{x})=\overline{c}$, and (ii) for each $i\in [m]$, $P_i(h({\overline{z}}_i))\notin I$. Note that, unlike arbitrary first-order queries, the answer to ncqs is defined over arbitrary instances, and not only over databases, since this is needed for our technical development.

A tuple-generating dependency (tgd) $\sigma$ over a schema $𝐒$ is a first-order sentence $\forall \overline{x}\forall \overline{y}\left(\varphi (\overline{x},\overline{y})\to \exists \overline{z}\psi (\overline{x},\overline{z})\right),$ where $\varphi$ and $\psi$ are (non-empty) conjunctions of atoms over $𝐒$ that mention only variables. For brevity, we write $\sigma$ as $\varphi (\overline{x},\overline{y})\to \exists \overline{z}\psi (\overline{x},\overline{z})$ and use comma instead of $\wedge$ for joining atoms. We call $\varphi (\overline{x},\overline{y})$ and $\psi (\overline{x},\overline{z})$ the body and head of $\sigma$, denoted $\mathrm{𝖻𝗈𝖽𝗒}(\sigma )$ and $\mathrm{𝗁𝖾𝖺𝖽}(\sigma )$, respectively. Note that we may treat a conjunction of atoms as the set of its atoms, which means that $\mathrm{𝖻𝗈𝖽𝗒}(\sigma )$ and $\mathrm{𝗁𝖾𝖺𝖽}(\sigma )$ can be treated as sets of atoms. We denote by $\mathrm{𝖿𝗋}(\sigma )$ the so-called frontier variables of $\sigma$, i.e., the universally quantified variables of $\sigma$ that appear in $\mathrm{𝗁𝖾𝖺𝖽}(\sigma )$. Let $\mathrm{𝖳𝖦𝖣}$ be the family of all finite sets of tgds; in the rest of the paper, a set of tgds is always finite. A class $𝖢$ of tgds is simply a subset of $\mathrm{𝖳𝖦𝖣}$. A null instance $I$ over $𝐒$ satisfies $\sigma$, written $I\vDash \sigma$, if, whenever $\varphi (\overline{x},\overline{y})\to I$ via $h$, then $\psi (\overline{x},\overline{z})\to I$ via $h^{\prime }$ that agrees with $h$ on $\overline{x}$. The null instance $I$ satisfies a set $\mathrm{\Sigma }$ of tgds, written $I\vDash \mathrm{\Sigma }$, if $I\vDash \sigma$ for each $\sigma \in \mathrm{\Sigma }$. Given a database $D$ over $𝐒$, a model of $D$ and $\mathrm{\Sigma }$ is a (possibly infinite) null instance $I\supseteq D$ such that $I\vDash \mathrm{\Sigma }$.

We now discuss how a set of tgds can be transformed into a logic program by eliminating the existentially quantified variables via Skolemization. This is needed for defining the semantics of ontology-mediated queries below. The Skolemization of a tgd $\sigma$ of the form $\varphi (\overline{x},\overline{y})\to \exists \overline{z}\psi (\overline{x},\overline{z})$, denoted $\mathrm{𝖲𝗄}(\sigma )$, is the logic programming rule (or simply LP-rule), $\varphi (\overline{x},\overline{y})\to \psi (\overline{x},{𝐟}_{\sigma }(\overline{x},\overline{y})),$ where ${𝐟}_{\sigma }$ is a vector of function symbols $f_{\sigma ,z}\in 𝐅$, one for each variable $z\in \overline{z}$. For example, the Skolemization of the tgd $\sigma =R(x,y)\to \exists z\exists wP(z,y,w)$ is the LP-rule $R(x,y)\to P(f_{\sigma ,z}(x,y),y,f_{\sigma ,w}(x,y))$. The Skolemization of a set $\mathrm{\Sigma }$ of tgds, denoted $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$, is the set of LP-rules $\{\mathrm{𝖲𝗄}(\sigma )\mid \sigma \in \mathrm{\Sigma }\}$. A functional instance $I$ satisfies $\mathrm{𝖲𝗄}(\sigma )$, where $\sigma$ is a tgd as above, written $I\vDash \mathrm{𝖲𝗄}(\sigma )$, if, whenever $\varphi (\overline{x},\overline{y})\to I$ via a homomorphism $h$, then $\psi (\overline{x},{𝐟}_{\sigma }(\overline{x},\overline{y}))\to I$ via $h$. The instance $I$ satisfies $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$ for a set $\mathrm{\Sigma }$ of tgds, written $I\vDash \mathrm{𝖲𝗄}(\mathrm{\Sigma })$, if $I\vDash \mathrm{𝖲𝗄}(\sigma )$ for each $\sigma \in \mathrm{\Sigma }$. Given a database $D$, a model of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$ is a (possibly infinite) functional instance $I\supseteq D$ such that $I\vDash \mathrm{\Sigma }$. A model $I$ of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$ is minimal if there is no $J\subset I$ that is a model of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$. In fact, it is easy to show that there is a unique minimal model of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$, and thus, we can refer to the minimal model of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$, denoted $\mathrm{𝗆𝗆}(D,\mathrm{𝖲𝗄}(\mathrm{\Sigma }))$.

An ontology-mediated query (omq) over a schema $𝐒$ is a pair $O=(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }$ is a set of tgds over $𝐒$ (the ontology) and $Q$ is an ncq over $𝐒$ (the user query). For a class $𝖢\subseteq \mathrm{𝖳𝖦𝖣}$ of tgds, let $(𝖢,{\mathrm{𝖢𝖰}}^{\neg })$ be the class of omqs $(\mathrm{\Sigma },Q)$, where $\mathrm{\Sigma }\in 𝖢$ and $Q\in {\mathrm{𝖢𝖰}}^{\neg }$. The class of omqs $(𝖢,\mathrm{𝖢𝖰})$ is defined analogously. One of the standard ways for defining the answer to an omq $(\mathrm{\Sigma },Q)$ is to first convert $\mathrm{\Sigma }$ into the logic program $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$ and then evaluate the user query over the unique minimal model of the input database and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$. Formally, given a database $D$ and an omq $O=(\mathrm{\Sigma },Q)$, the answer to $O$ over $D$, denoted ${\mathrm{𝖺𝗇𝗌}}_{\mathrm{𝖲𝗄}}(O,D)$, is defined as $Q(\mathrm{𝗆𝗆}(D,\mathrm{𝖲𝗄}(\mathrm{\Sigma })))$. At this point, let us stress that this semantics extends the well-established certain answers semantics for positive omqs, where the user query is a cq without negation. More precisely, for an omq $O=(\mathrm{\Sigma },Q)$ over $𝐒$, where $Q$ is a cq without negation, the certain answers of $O$ over a database $D$, denoted $\mathrm{𝖼𝖾𝗋𝗍𝖺𝗂𝗇}(O,D)$, is defined as ${\bigcap }_{I\in \mathrm{𝗆𝗈𝖽𝗌}(D,\mathrm{\Sigma })}Q(I)$, where $\mathrm{𝗆𝗈𝖽𝗌}(D,\mathrm{\Sigma })$ collects all the models of $D$ and $\mathrm{\Sigma }$. It is then not difficult to show that $\mathrm{𝖼𝖾𝗋𝗍𝖺𝗂𝗇}(O,D)={\mathrm{𝖺𝗇𝗌}}_{\mathrm{𝖲𝗄}}(O,D)$.

Given a database $D$ and an omq $O=(\mathrm{\Sigma },Q)$, we can use the chase procedure, a useful tool when reasoning with tgds, to construct a model of $D$ and $\mathrm{\Sigma }$ that is isomorphic to the unique minimal model of $D$ and $\mathrm{𝖲𝗄}(\mathrm{\Sigma })$, which in turn can be used for computing ${\mathrm{𝖺𝗇𝗌}}_{\mathrm{𝖲𝗄}}(O,D)$. This allows us to directly work with the original set of tgds, instead of its Skolemized version, which is technically more convenient. We assume the reader is familiar with the oblivious version of the chase procedure; see, e.g., [5]. Given a chase derivation $\delta$ of a database $D$ w.r.t. a set $\mathrm{\Sigma }$ of tgds, which is essentially a sequence of instances ${(I_i)}_{i\ge 0}$ where $I_0=D$ and, for each $i>0$, $I_{i+1}$ is obtained from $I_i$ by applying a tgd of $\mathrm{\Sigma }$, we write ${\mathrm{𝖼𝗁𝖺𝗌𝖾}}_{\delta }(D,\mathrm{\Sigma })$ for the result of $\delta$, that is, the instance ${\bigcup }_{i\ge 0}{I}_i$. It is not difficult to show that there is a bijection $\mu$ from the constants and nulls in ${\mathrm{𝖼𝗁𝖺𝗌𝖾}}_{\delta }(D,\mathrm{\Sigma })$ to the ground functional terms in $\mathrm{𝗆𝗆}(D,\mathrm{𝖲𝗄}(\mathrm{\Sigma }))$, which is the identity on $𝐂$, such that $\mu ({\mathrm{𝖼𝗁𝖺𝗌𝖾}}_{\delta }(D,\mathrm{\Sigma }))=\mathrm{𝗆𝗆}(D,\mathrm{𝖲𝗄}(\mathrm{\Sigma }))$ and ${\mu }^{-1}(\mathrm{𝗆𝗆}(D,\mathrm{𝖲𝗄}(\mathrm{\Sigma })))={\mathrm{𝖼𝗁𝖺𝗌𝖾}}_{\delta }(D,\mathrm{\Sigma })$. Thus, we get the following result that allows us to use the chase procedure for our purposes: