Database Reference

In-Depth Information

graph and the simple dependency graph are the same: the only difference is that in the

dependency graph, some edges are annotated with
. Another interesting class of weakly

acyclic sets of tgds includes sets of tgds without existential quantification in the right-hand

side, i.e., full tgds.

We now prove that the chase always terminates for mappings with a weakly acyclic sets

of tgds. Moreover, in this case the chase for
S
terminates after polynomially many steps.

Theorem 5.11

Σ
t
is

the union of a set of egds and a weakly acyclic set of tgds. Then there exists a polynomial p

such that the length of every chase sequence for a source instance S under

Let

M

=(R
s
,
R
t
,

Σ
st
,

Σ
t
)
be a fixed relational mapping, such that

M

is bounded

by p
(

S

)
.

Proof
For the sake of simplicity we prove the theorem in the absence of egds. The addi-

tion of egds does not change the argument of the proof in any fundamental way.

First of all, with each node (
V
,
i
) in the dependency graph of

Σ
t
we associate its
rank
,

denoted by rank(
V
,
i
), which is the maximum number of special edges in any path in the

dependency graph
G
of

Σ
t
is weakly acyclic, the rank of each

node in
G
is finite. Moreover, it is clear that the maximum rank
r
of a node in
G
is bounded

by the number
m
of nodes in
G
itself. Notice that
m
(and, thus,
r
) is a constant, since it

corresponds to the total number of attributes in the schema R
t
(which is assumed to be

fixed).

Let us partition the nodes of
G
into sets
N
0
,
N
1
,...,
N
r
such that (
V
,
i
) belongs to
N
j
if

and only if rank(
V
,
i
)=
j
,for0

Σ
t
that ends in (
V
,
i
).Since

≤

j

≤

r
. To prove the theorem, we need the following

technical result.

Claim 5.12

r, there exists a polynomial p
j
such that the following

holds. Let T be a target instance and T
be any target instance that is obtained from T by

a sequence of chase steps using the tgds in

Fo r e a c h
0

≤

j

≤

Σ
t
. Then the number of distinct elements (i.e.,

constants and nulls) that occur in T
at positions that are restricted to be in N
j
is bounded

by p
j
(

T

)
.

First we show how the theorem can be proved from
Claim 5.12
. It follows easily from

the proof of
Proposition 5.1
that there is a polynomial
p
, which depends only on

M

,

such that if
T
is the result of any chase sequence for
S
under

Σ
st
,then

T

is bounded

by
p
(

). Furthermore, it follows from
Claim 5.12
that there exists a polynomial
p
,

which depends only on

S

, such that the maximum number of elements that occur in the

result
T
of a chase sequence for
T
under

M

Σ
t
, at a single position, is bounded by
p
(

T

).

Thus, the total number of tuples that can exist in one relation in
T
is at most
p
(

)
m

(since each relation symbol in R
t
can have arity at most
m
). Thus, the total number of

tuples in
T
is bounded by

T

p
(

)
m
. This is polynomial in

is fixed.

Furthermore, each chase step that uses a tgd adds at least one tuple. Thus, the length of

any chase sequence
c
for a source instance
S
under

M·

T

T

,since

M

))
m
.

This is because
c
is a sequence of chase steps that are obtained by either applying an std in

Σ
st
to the source instance
S
,oratgdin

p
(
p
(

M

is bounded by

M·

S

Σ
t
to the facts that have already been added to the