Database Reference
In-Depth Information
This target instance violates no dependency in
Σ t , and, therefore, is the result of a suc-
cessful chase sequence for S . We conclude that T 1 is a canonical universal solution for S
under
M
.
Suppose, on the other hand, that it is the egd that is applied first on T . Then nulls
1 and
2 are equated, which yields a target instance T =
{
E ( a ,
1 )
}
. Afterwards, we apply
the tgd and obtain the target instance:
T 2 =
{
E ( a ,
1 ) , F (
1 ,
2 )
}
.
This instance does not violate any dependency in
Σ t , and hence it is another canonical
universal solution for S under
M
.
Clearly, T 1 and T 2 are not isomorphic, which shows that S does not have a unique canonical
universal solution up to isomorphism.
Although canonical solutions are not necessarily unique, this cannot be considered as
a serious drawback. Indeed, Theorem 6.7 states that no matter which one of them we
materialize, the result will be equally useful for data exchange purposes (since any result
of a successful chase sequence is a universal solution). In some restricted cases, however,
it will be important to have a unique canonical universal solution. As the following simple
proposition shows, this is always the case when mappings contain no tgds in
Σ t . The proof
is left as an exercise for the reader.
Proposition 6.10
Σ t consists only of
egds. Then every source instance S has a unique canonical universal solution T (up to a
renaming of nulls) under
Let
M
=(R s , R t ,
Σ st ,
Σ t ) be a mapping such that
M
.
Each time that all canonical universal solutions are isomorphic for a source instance S ,
we will talk about the canonical universal solution for S .
Canonical universal solutions and weak acyclicity
Recall that at the end of Section 6.2 we introduced the desiderata for good solutions in
data exchange, in the form of three properties (C1), (C2),and(C3): these state that the
existence of solutions must imply the existence of universal solutions, which can be tested
algorithmically, and that some universal solution could be built in polynomial time. We
can now conclude that the class of mappings with weakly acyclic sets of tgds satisfies
these conditions. Indeed, we obtain the following as an immediate corollary to Theorems
6.7 and 5.11 .
Corollary 6.11
Σ t is the
union of a set of egds and a weakly acyclic set of tgds. Then U NI S OL E XISTENCE M can
be solved in P TIME . Furthermore, if solutions for a source instance S exist, then universal
solutions exist, and a canonical universal solution for S can be computed in polynomial
time.
Let
M
=(R s , R t ,
Σ st ,
Σ t ) be a relational mapping, such that
Search WWH ::




Custom Search