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