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
