Database Reference
In-Depth Information
The bound on the size does not immediately give a bound on the number of trees we need
to consider, because there are infinitely many ways to fill the attributes with data values.
We now show that one can restrict to data values used in the source tree and a small set of
nulls
, representing the values invented to fill in the unspecified attributes on the target side.
Lemma 12.4
For each XML tree T , pattern
π
(
x
,
y
)
and tuple of values a, such that T
|
=
(
a
,
y
)
, there exists a tree T
with the same tree structure as T but storing only data values
used in a or taken from the set
{⊥
0
,⊥
1
,...,⊥
|
y
|
}
, such that T
|
= π(
a
,
y
)
.
π
(
a
,
b
) for some tuple of values
b
and let
h
be the witnessing
homomorphism. Let
A
,
B
be the sets of values used in
a
and
b
, respectively. There exists
an injection
Proof
Suppose that
T
|
=
π
⊥
|
y
|
}
such that
f
(
a
)=
a
for all
a
∈
A
.Let
c
be the tuple
f
(
b
1
)
,
f
(
b
2
)
,...,
f
(
b
|
y
|
)
and let
T
be
obtained by replacing each data value
d
in
T
with
f
(
d
) if
d
∈
A
∪
B
, and with
f
:
A
∪
B
→
A
∪{⊥
1
,
⊥
2
,...,
⊥
0
otherwise.
Note the nodes in the image of
h
can only store data values from
A
∪
B
. Hence,
h
witnesses
that
T
|
=
π
(
a
,
c
).
Combining the bounds, we obtain a simple algorithm for constructive satisfiability (
Al-
gorithm 12.1
). Checking conformance to a schema can be done in polynomial time. By
Algorithm 12.1 Constructive satisfiability by exhaustive search
Require:
S
is a regular schema over
Γ
,
π
(
x
,
y
) is a pattern,
a
is a tuple of values
S
D
:=
d
d
is used in
a
∪{⊥
0
,
2+
n
:= 12
·
π
·S
⊥
|
y
|
}
for all trees
T
of size at most
n
and data values in
D
and all tuples
b
from
D
do
if
T
|
⊥
1
,...,
(
a
,
b
) then return
T
=
S
and
T
|
=
π
end for
if no
T
found return '
π
(
a
,
y
) is not satisfiable with respect to
S
'
Proposition 11.6
, evaluation of the patterns also takes only polynomial time. Hence, each
iteration of the loop takes time polynomial in
n
, and the number of iterations is exponential
in
n
. For a fixed schema
this gives a single exponential algorithm.
To compute a solution for a given source tree
T
with respect to a fixed mapping
S
M
,we
simply apply
Algorithm 12.1
to the pattern
δ
T
,M
and the schema
S
t
.Since
M
is fixed, the
size of
δ
T
,M
is polynomial, and the whole procedure is single exponential. Summing up,
we have the following.
Theorem 12.5
Algorithm 12.1
correctly computes a solution for a source tree T under a
schema mapping
M
(if there is one). Its data complexity is single-exponential.
The brute force algorithm for constructive satisfiability described above cannot be sig-
nificantly improved unless NP = P
TIME
.
Indeed, constructing a tree satisfying a given
