Database Reference
In-Depth Information
6. Now
T
4
=
{
G
(
a
,
b
)
,
G
(
⊥
,
⊥
1
)
,
L
(
b
,
⊥
)
,
L
(
⊥
1
,
⊥
2
)
}
violates
θ
2
, so a new fact
G
(
⊥
2
,
⊥
3
)
must be added. And the process now continues indefinitely.
In this case, the chase
does not terminate
. Notice that it does not imply the lack of solutions
for
S
; in fact,
T
=
is a solution for
S
. Nontermination simply says that
the chase procedure cannot compute a solution.
Finally, consider a
{
G
(
a
,
b
)
,
L
(
b
,
a
)
}
Σ
t
x
=
y
. Then, after the
first step when it constructs
T
1
, the chase
fails
, since the fact
G
(
a
,
b
), and the egd
that contains a single egd
α
=
G
(
x
,
y
)
→
implies
that two distinct constants
a
and
b
are equal. Notice that, in this case,
S
has no solution.
α
We now formally define the chase procedure, and explain how its three possible out-
comes - successful termination, nontermination, and failure - are interpreted in terms of
the existence of data exchange solutions.
We first define the notion of a
chase step
for an instance
S
. We distinguish between two
kinds of chase steps - tgd steps and egd steps.
(tgd) Let
d
be a tgd of the form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
), such that for some tuple
a
of elements
in D
OM
(
S
) it is the case that
. Then the
result of
applying d to S with a
is the instance
S
that extends
S
with every fact
R
(
c
) that
belongs to
ϕ
(
a
) holds in
S
,where
|
a
|
=
|
x
|
(
a
,
¯
),where
¯
ψ
⊥
⊥
is a tuple of fresh distinct values in V
AR
such that
¯
|
⊥|
.
In that case we write
S
=
|
y
|
d
,
a
−−→
S
.
(egd) Let
d
be an egd of the form
x
i
=
x
j
. Assume that there is a tuple
a
=(
a
1
,...,
a
n
) of elements of D
OM
(
S
) such that
ϕ
(
x
1
,...,
x
n
)
→
ϕ
(
a
) holds in
S
,and
a
i
=
a
j
.
Then:
•
if both
a
i
and
a
j
are constants, the
result of applying d to S with a
is “failure”,
which is denoted by
S
d
,
a
−−→
fail
;
otherwise, the
result of applying d to S with a
is the instance
S
obtained as
follows:
1. if one of
a
i
,
a
j
is a constant and the other is a null, then
S
is obtained from
S
by replacing the null with the constant everywhere;
2. if both
a
i
and
a
j
are nulls, then
S
is obtained from
S
by replacing
a
i
with
a
j
everywhere.
•
d
,
a
−−→
S
. Note that in the second step we arbitrarily choose
whether to replace
a
i
by
a
j
or
a
j
to
a
i
, but, up to renaming of nulls, this will not
affect the result.
In both cases we write
S
With the notion of chase step we can now define a chase sequence.
Definition 5.5 (Chase) Let
Σ
be a set of tgds and egds and
S
an instance.
•
Achase
sequence
for
S
under
Σ
is a sequence
d
i
,
a
i
−−→
S
i
S
i
+1
(
i
≥
0)
