Database Reference
In-Depth Information
proof of
Proposition 5.6
, since in
Section 6.2
(
Theorem 6.7
) we will prove a more general
result.
Example 5.7 (
Example 4.1
continued)
It is clear that there is a unique successful chase
sequence for
S
under
, and that its result is
T
shownonpage
39
. Thus, from
Proposition
5.6
,
T
is a solution for
S
.
M
But the chase as a tool for data exchange has one drawback: nothing can be concluded
about the existence of solutions in the case when the chase does not terminate. Thus, we
now concentrate on conditions that guarantee chase termination.
5.4 Weak acyclicity of target constraints
As we have seen, the main problem with the application of the chase is nontermination.
This happens, for instance, when the set of tgds permits an infinite sequence of null creation
during the chase (as in the second case of
Example 5.4
). So a natural idea is to restrict target
constraints to make such an infinite sequence of null creation impossible.
We now do precisely this, and restrict the shape of tgds to prevent such behavior, and
obtain a meaningful class of mappings for which the chase is not only guaranteed to termi-
nate, but does it in polynomially many steps.
We first provide some intuition behind the restriction. Recall
Example 5.4
,inwhich
we had a single target tgd
zL
(
y
,
z
). In that example, the tgd was fired to
create new tuples in relation
L
based on tuples in relation
G
, and once it was done, the chase
terminated. However, when we extended the set of constraints with the tgd
θ
1
=
G
(
x
,
y
)
→∃
θ
2
=
L
(
x
,
y
)
→
∃
zG
(
y
,
z
), we entered a cycle: each fact in
G
created a fact in
L
, which then created a fact
in
G
, which created a fact in
L
, and so on.
Thus, we need to avoid cycles. To enforce this syntactically, note that in our example,
θ
1
says that
L
depends on
G
,and
θ
2
says that
G
depends on
L
. So, we break cycles of this
kind. Formally, we do it as follows.
Assume that
as
follows. The nodes (positions) of the graph are all pairs (
R
,
i
),where
R
is a relation symbol
in R
t
of arity
n
and 1
Σ
is a set of tgds over R
t
. We construct the
simple dependency graph
of
Σ
≤
i
≤
n
. Then we add edges as follows. For every tgd
∀
x
∀
y
(
ϕ
(
x
,
y
)
→
∃
, and for every variable
x
mentioned in
x
that occurs in the
i
th position
(attribute) of relation
R
in
z
ψ
(
x
,
z
)) in
Σ
, add an edge from (
R
,
i
) to (
T
,
j
) if the variable that occurs in
the
j
th position of relation
T
in
ϕ
ψ
is:
•
x
itself, or
•
an existentially quantified variable
z
(that corresponds to the introduction of a new
value).
Definition 5.8 (Acyclicity) We say that a set
Σ
of tgds is
acyclic
if its simple dependency
graph has no cycles.
