combining TGDs and EGDs
The idea of this note is to study the reasoning of TGDs and EGDs toghether. The query answering problem becomes more difficult in this context.
Definitions
An Equality Generating Dependency (EGD) is a formula of the following form: \[\phi(x_{1}, \dots, x_{n}) \rightarrow x_{i} = x_{j}\] where \(1 \leq i,j \leq n\) and \(\phi\) is a conjunctive query.
Chase terminaison
As explained in DBLP:journals/pvldb/CalauttiGMT16, determining if the chase evaluation with EGDs and TGDs will terminated is undecidable. Since the chase consists of applying a sequence of steps, where each step enforces a dependency (TGD or EGD) that is not satisfied by the current instance. It might well be the case that multiple dependencies can be enforced, and, in this case, the chase picks one non deterministically. Different choices leads to different sequences, some of which might be terminating, while other might not. This aspect is illustrated in the following set of dependencies on the database \(D = \{N(a)\}\):
- \(r_{1}: N(x) \rightarrow \exists y~ E(x,y)\),
- \(r_{2}: E(x,y) \rightarrow N(y)\),
\(r_{3}: E(x,y) \rightarrow x = y\).
Applying the core chase in parallel on every possible choices of dependencies enforcement is a procedure that computes a universal model, if it exists.
It is important to notice that if the TGDs is a finite expansion set, it don't implies that the EDGs and the TGDs forms an fes. For instance, you can consider the following example:
- \(N(x) \rightarrow E(x, y)\)
- \(E(x,x) \rightarrow P(x,y), N(y)\)
- \(E(x,y) \rightarrow x = y\)
Yet, if \(\Sigma\) is the union of a set of weakly acyclic TGDs and a set of EGDs, then there exists a polynomial in the size of an instance K that bounds the length of every chase sequence of K with \(\Sigma\) DBLP:conf/icdt/FaginKMP03. Moreover, the standard chase always terminates on every instance with a such \(\Sigma\).
Query answering problem
The general problem of query answering with TGDs and EGDs is undecidable.
Case with guarded TGDs
In DBLP:journals/jair/CaliGK13, they recall that the query answering problem with guarded TGDs is decidable, but considering both inclusion dependencies (a simple subclass of guarded TGDs) and functional dependencies (a subclass of EGDs) or even key dependencies makes the query answering problem undecidable.
Innocuous EGDs
In DBLP:journals/jair/CaliGK13, they define the innocuousness of a set of EDG with respect to a set of TGD, by imposing that each EGD application in the chase returns an instance, which includes in the one of which the EGD have been applied. Under this semantic condition between EGDs and TGDs, the query answering boils down to query answering with TGDs only.
