Database Reference
In-Depth Information
from the run of
M
on the word encoded in the sequence of
t
i
-leaves of
S
.Whatif
S
uses
some data values more than once? For a function
h
:
and a tree
U
,let
h
(
U
) be the
tree obtained from
U
by replacing each data value
a
with
h
(
a
).Now,let
S
be a tree with
the structure identical as
S
, but using distinct data values, and let
h
be a function on data
values such that
h
(
S
)=
S
. By the previously considered case, there is a solution
T
for
S
. Since our mapping does not use inequality on the target side, nor equality on the source
side,
h
(
T
) is a solution for
h
(
S
)=
S
.
N
→
N
In the reduction above we can remove disjunction from the DTDs turning them into
nested-relational at the cost of allowing inequality or next-sibling on the source side. For
mappings in SM
nr
(
↓
, ,
=) one can prove N
EXPTIME
-hardness.
Bounded depth mappings
We have seen that absolute consistency is highly intractable even for patterns using only
vertical axes and nonrecursiveDTDs with very simple productions. The N
EXPTIME
lower
bound means that for all we know, a
doubly
-exponential algorithm is required. For static
reasoning that we encounter in dealing with metadata, in general it is a
single
-exponential
bound that is viewed as acceptable. So the question is whether such a bound is achievable
for absolute consistency under some restrictions.
In this section we show that the complexity can be lowered substantially if the height of
trees is bounded by a constant. We say that a mapping
M
has depth at most d
if the source
and target schema only admit trees of height at most
d
.
In this case the problem falls into the polynomial hierarchy. We have seen two levels
of it,
p
2
and
p
2
, so far. Now we need the fourth level of it,
p
4
. These levels are defined
Π
Σ
Π
p
k
is the class of problems solved in NP with a
p
k
p
k
is the
inductively:
Σ
Σ
1
oracle, and
Π
−
p
k
class of problems solved in
CO
NP with a
1
oracle. All these classes are contained in
P
SPACE
, and thus problems belonging to these classes can be solved in single-exponential
time.
Σ
−
p
4
.
Proof
We claim that the general algorithm presented in
Theorem 18.8
has the desired
complexity for mappings of bounded depth.
Assume that an UNFTA
Theorem 18.10 A
B
C
ONS
for mappings of bounded depth is in
Π
-kind.
Obviously
K
's height is at most
d
. Moreover,
K
contains no vertical ports, as otherwise
arbitrarily high trees would agree with
K
.
It follows that, for a bounded depth mapping, the kinds played in the first round have
polynomial branching and bounded depth, which means they are polynomial. In the second
round, the objects played are polynomial in the size of those from the first round. As the
correctness of the moves is polynomial, this gives a
A
only accepts trees of height at most
d
and let
K
be an
A
p
4
-algorithm.
A small modification of our techniques makes it possible to prove
Theorem 18.10
for a
more general definition of boundedness:
Π
has depth at most d
if every pattern it uses
can only be realized within the initial
d
levels of every tree conforming to the schema.
M
