Database Reference
In-Depth Information
Finally, if u is a context port, let V below , V u , V above be a partition of
π
's vertices into those
mapped to T . v , Z u = T . w
T . v , and elsewhere. The only possible edges between x
V u ,
+ y ) with the witnessing paths
visiting v , v , or both of these, respectively. Consequently, we can transfer the image of V u
to the copy of Z u contained in T u , preserving the existence of the witnessing paths.
V above ,and y
+ x ), ( x
+ y ),or( y
y
V below ,are( y
12.6 Combined complexity of solution building
The solutions built by the algorithms from the previous sections are polynomial-size, and
can be constructed in polynomial time, for each fixed mapping
M
. A quick analysis of
the algorithm (already done in the proofs of correctness results) shows that in terms of
M
, such solutions can be of exponential size. This bound is in fact tight: the smallest tree
conforming to the target schema might be exponential, and even if the schema is fixed, a
simple rule like
r [ // ( x 1 ) ,// ( x 2 ) ,...,// ( x n )]
−→
r / a ( x 1 , x 2 ,..., x n )
causes exponential blow-up.
We now investigate the bounds on the combined complexity of solution building. That
is, we look at the problem of building a solution when the input consists of both a mapping
M
and a source tree T .
Theorem 12.27
The combined complexity of solution building for schema mappings in
SM(
,
,
) is in E XPSPACE .
Proof Let us sum up the space used by Algorithm 12.4 . The kinds and partial solutions
considered by the algorithm have branching and height bounded by functions polynomial
in the size of the mapping, and their data values come from a set single-exponential in the
size of the mapping. The number of partial solutions kept in memory at the same time is
bounded by the number of target requirements, i.e.,
| M .
| Δ T ,M |
, which is at most
M·|
T
It follows that these objects can be stored in exponential memory.
The merging operation
m uses memory polynomial in the size of the partial solutions
and the kind (modulo exponential multiplicative overhead needed for the padding contexts
and forests used in the operation). All other checks and operations need memory polyno-
mial in the size of these objects.
Note that an E XPSPACE algorithm in general implies doubly-exponential running time
(just like a P SPACE algorithm implies a single-exponential running time). To understand
better the complexity of the problem, and to see whether this bound can be lowered, we
consider a decision version of solution building, i.e., solution existence .
P ROBLEM : S OL E XISTENCE
I NPUT : Mapping
M
, source tree T .
Q UESTION : s
M
( T ) nonempty?
Search WWH ::




Custom Search