Database Reference

In-Depth Information

(
G
,
1)

(
G
,
2)

(
G
,
1)

(
G
,
2)

(
L
,
1)

(
L
,
2)

(
L
,
1)

(
L
,
2)

(b)

(a)

Figure 5.1 Dependency graphs of (a)
{
θ
1
}
and (b)
{
θ
1
,
θ
2
}
.

Look at the example in
Figure 5.1
(for now, ignore the
annotation of some of the

edges). The graph in the left part of the figure corresponds to

θ
1
, and it has no cycles;

the graph in the right part of the figure corresponds to

, and it has a cycle. So

intuitively, the notion of acyclicity does the job prohibiting nonterminating chase.

We will see that the chase will terminate, and do so in polynomiallymany steps, if the set

of target tgds is acyclic. But in fact we will do more. The notion of acyclicity could be too

restrictive sometimes (although it does arise in several examples; for instance we shall see

it again when we deal with XML data exchange by means of relational representations).

If we look at the definition of the simple dependency graph, we see that there are two

kinds of edges, and only the second kind, to an existentially quantified variable, actually

creates a new value in the target instance. So it seems that all we need to do is to forbid

cycles involving such value-creating edges, and this will be enough to rule out infinite

chase sequences.

We now modify the definition of a graph of a set of tgds. If Σ is a set of tgds over R
t
, its

dependency graph
has the same nodes as before, and two kinds of edges: usual ones, and

edges with a special label
. For every tgd

{
θ
1
,

θ
2
}

∀

x
∀

y
(

ϕ

(
x
,
y
)

→∃

z
ψ

(
x
,
z
)) in

Σ

, and for every

variable
x
mentioned in
x
that occurs in the
i
th position of relation
R
in

, we 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
; in this case, the edge from (
R
,
i
) to (
T
,
j
) that we

add is labeled
.

Definition 5.9 (Weak acyclicity) A set

Σ

of tgds is
weakly acyclic
if the dependency

graph of

Σ

does not have a cycle going through an edge labeled
.

Example 5.10 (
Example 5.4
continued) Returning to
Figure 5.1
, we see that it depicts

dependency graphs of

{
θ
1
}

(which is weakly acyclic), and

{
θ
1
,

θ
2
}

(which is not).

Of course every acyclic set of tgds is weakly acyclic too, as the edges in the dependency