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.