Database Reference
In-Depth Information
Algorithm 12.2 Building solutions for nested-relational DTDs
Require:
SM
nr
(
M
=(
D
s
,
D
t
,
Σ
)
∈
⇓
,
∼
) and
T
|
=
D
s
compute
Δ
T
,M
m
:=
D
t
+max
δ
∈
Δ
T
,M
δ
n
:=
D
t
D
t
+max
δ
∈
Δ
T
,M
δ
D
:=
d
d
is used in
T
∪{⊥
0
,
⊥
n
}
for all
D
t
-kinds
K
with data values in
D
do
for all
⊥
1
,...,
δ
∈
Δ
T
,M
do
find
S
δ
∈
L
(
K
) with data values in
D
, branching at most
m
, satisfying
S
δ
|
=
δ
end for
if all
S
δ
found then return
δ
∈
Δ
T
,M
S
δ
end for
if no success for each
K
return '
T
has no solution with respect to
M
'
one shows that
S
δ
only needs to use data values in
D
. Hence, also the entries of
c
are taken
from
D
. In consequence, we can look for a partial solution
S
δ
by exhaustive search.
If for some
the search fails, there is no solution for
T
agreeing with
K
. If all partial
solutions have been found, we can combine them with the operation
δ
⊕
into a single full
solution in E
XPTIME
,by
Lemma 12.12
.
For a fixed mapping, the set
Δ
T
,M
can be computed in polynomial time. The number of
possible kinds is polynomial in
|
|
and their size is bounded by a constant. Their correct-
ness can be checked in time polynomial in
T
(independent of
T
). For each kind
finding and combining partial solutions takes polynomial time. Hence, the whole procedure
is in P
TIME
.
|
K
|
and
D
t
Difficulties with extension to the general case
We now give two examples which explain why extending the algorithm of this section to
the general case causes problems.
Example 12.14 Consider the mapping given by
D
s
=
r
ab
∗
,
D
t
=
r
a
,
→
→
c
;
c
→
cb
|
Σ
st
=
r
[
a
(
x
)
,
b
(
y
)]
r
[
//
a
(
x
)
,//
b
(
y
)]
,
−→
where
a
and
b
have one attribute. For the source tree shown in
Figure 12.3
(a), partial
solutions could be the trees in
Figure 12.3
(b). The natural combination of these partial
solutions, shown in
Figure 12.3
(c), cannot be expressed in terms of kinds, as defined in
this section. The unique
a
node on the target side should clearly be part of the kind, as
shown in
Figure 12.3
(d), but under the current definition this is not allowed. In the next
section, we are going to develop a more general definition of kinds, allowing internal ports
into which contexts are substituted. The ports will also have much richer requirements for
