Database Reference
In-Depth Information
of chase steps such that
(i)
S
0
=
S
,
(ii) each
d
i
is a dependency in
Σ
,and
(iii) for each distinct
i
,
j
=
a
j
). This technical condition simply ensures that chase sequences consist of different
chase steps.
≥
0, it is the case that (
d
i
,
a
i
)
=(
d
j
,
a
j
) (that is,
d
i
=
d
j
or
a
i
•
A
finite
chase sequence for
S
under
Σ
is a chase sequence
d
i
,
a
i
−−→
S
i
S
i
+1
(0
≤
i
<
m
)
for
S
under
. We call
S
m
its
result
.
- If
S
m
=
fail
, we refer to this sequence as a
failing
chase sequence.
- If no chase step can be applied to
S
m
with the dependencies in
Σ
, we refer to it as a
successful
chase sequence. Technically, this means the following: there is no depen-
dency
d
in
Σ
d
,
a
−−→
, tuple
a
in
S
m
and instance
S
such that
S
m
S
and (
d
,
a
)
Σ
=(
d
i
,
a
i
) for
every 0
≤
i
≤
m
−
1.
In principle there could be different results of the chase, as we have to make some
arbitrary choices: for example, if an egd equates nulls
⊥
, we can either replace
⊥
and
⊥
,or
⊥
by
⊥
. These choices are rather innocuous, as they produce
isomorphic
instances, i.e., instances that are equal up to a renaming of the nulls. There is, however, a
more important choice we make when constructing a chase sequence: that is the order in
which the egds and tgds are applied. We show in
Chapter 6
that this choice is relevant. In
particular, we show in
Section 6.3
that the result of the chase is not always unique, i.e., that
two different chase sequences may yield different results.
by
⊥
The chase in data exchange
We now explain how chase can be used in data exchange. Let
M
be a relational mapping
and
S
a source instance. A
chase sequence for S under
M
is defined as a chase sequence
for (
S
,
0) under
Σ
st
∪
Σ
t
. Since in data exchange we are interested in materializing a target
instance, the result (
S
,
T
) of a successful chase sequence for
S
under
M
is usually identified
with the target instance
T
.
The following proposition justifies the application of the chase as a tool for checking for
the existence of solutions in data exchange.
Proposition 5.6
be a mapping and S a source instance. If there is a successful
chase sequence for S under
M
with result T , then T is a solution for S. On the other hand,
if there exists a failing chase sequence for S under
Let
M
M
, then S has no solution.
must
be an instance of the form
T
where
T
is a solution for
S
. But not only that, the proposition
tells us that if there exists a failing chase sequence for
S
under
Notice that, by definition, any result of a successful chase sequence for
S
under
M
, then all of its chase
sequences are failing, which further implies that
S
has no solutions under
M
M
. We skip the
