Database Reference
In-Depth Information
+
, ,
↓
∼
Algorithm 12.3 Building solutions for SM(
)
+
, ,
Require:
M
=(
S
s
,
S
t
,
Σ
)
∈
SM(
↓
∼
),
T
|
=
S
s
,and
S
t
=(
A
,
Attr
)
compute
Δ
T
,M
A
A
+max
δ
∈
Δ
T
,M
δ
n
:=
D
:=
d
d
is used in
T
∪{⊥
0
,
⊥
1
,...,
⊥
}
n
for all
A
-kinds
K
of height and branching at most
A
, data values in
D
, admitting an
accepting run do
for all δ
∈
Δ
T
,M
do
find
S
δ
∈
L
(
K
) with data values in
D
and a witnessing substitution of forests and
contexts of height and branching at most
A·
(2+
δ
), 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
'
A
M
Proof
Let
.
Lemma 12.20
guaran-
tees that if there is a solution to
T
, it agrees with a kind
K
that admits an accepting run, and
has height and branching bounded by
be the UNFTA underlying the target schema of
A
. It suffices to consider kinds using data values
A
A
. The size of the run is linear in
used in
T
and nulls
{⊥
1
,
⊥
2
,...,
⊥
}
, with
=
|
K
|
and its correctness can be checked in time polynomial in
.By
Lemma 12.19
,
it is enough to check for each such kind if there is a partial solution for each target require-
ment
|
K
|
and
A
.It
is not difficult to give bounds on the height and branching of forest and contexts substituted
at ports of
K
in the partial solutions. Arguing exactly like in
Lemma 12.3
one shows the
bound
δ
∈
Δ
T
,M
: if we succeed, we combine the partial solutions using the operation
⊕
) for forest and tree ports. For context ports we modify the argument
as follows. When a context
C
is substituted, one needs to take into account the existence of
the port in
C
. It is enough to consider the port a red node in the argument of
Lemma 12.3
.
Since the port is a leaf in
C
, the number of blocks of white nodes on any branch does not
increase, and the bound on the height is not influenced. In the argument for the branching,
the number of blocks can increase by one, which means that the bound increases by
A·
(1+
δ
A
,
resulting in
A·
(2+
δ
).
12.5 The general algorithm
Recall our journey so far:
•
First, in
Section 12.2
,wegaveanaıve exhaustive-search algorithm for building a solu-
tion; it ran in exponential time.
•
Then, in
Section 12.3
, we described a polynomial-time algorithm for building solutions
for mappings in SM
nr
(
⇓
,
∼
), i.e., those with nested-relational DTDs and downward nav-
