Database Reference
In-Depth Information
Compared to patterns, the data complexity remains low; the combined complexity jumps
to the second level of the polynomial hierarchy, but the parameter that makes it jump there
is the number of variables in st-tgds. If we fix that number, even the combined complexity
is tractable.
p
2
-complete. Its complex-
ity drops to
P
TIME
if the maximum number of variables per pattern is fixed.
Theorem 11.13
•
The problem
XML-SM-M
EMBERSHIP
is
Π
•
The problem
XML-SM-M
EMBERSHIP
(
M
)
is always in
L
OGSPACE
. Moreover, there
is a mapping
M
0
such that
XML-SM-M
EMBERSHIP
(
M
0
)
is
L
OGSPACE
-complete.
p
2
-complete, but
tractable when we fix the number of variables used in patterns; the data complexity of
schema mappings is low: in L
OGSPACE
, and the bound cannot be lowered.
In other words, the combined complexity of schema mappings is
Π
Proof
We first explain the proof for data complexity. Checking if a given tree conforms to
a schema amounts to verifying if the tree is accepted by the underlying UNFTA . As shown
by
Gottlob et al.
(
2005
), this can be done in L
OGSPACE
if the size of the automaton is fixed.
Let us now see how to check if
S
and
T
satisfy a single constraint
π
(
x
,
z
).Let
x
=
x
1
,
x
2
,...,
x
k
,
y
=
y
1
,
y
2
,...,
y
,and
z
=
z
1
,
z
2
,...,
z
m
.Let
A
be the set of data values
used in
S
or
T
. We need to check that for each
a
(
x
,
y
)
→∃
π
z
A
k
and each
b
(
a
,
b
)
A
such that
S
∈
∈
|
=
π
there exists
c
∈
A
m
π
(
a
,
c
). Since the numbers
k
,,
m
are fixed (as parts
of the fixed mapping), the space needed for storing all three valuations is logarithmic in
the size of
S
and
T
.Using
Proposition 11.6
we obtain a L
OGSPACE
algorithm by simply
iterating over all possible valuations
a
,
b
,and
c
.L
OGSPACE
-hardness is shown in the same
way as in the proof of
Proposition 11.6
.
We now move to combined complexity. Checking conformance to schemas can be done
in P
TIME
. Let us concentrate on verifying the dependencies. Consider the following algo-
rithm for the complementary problem: guess a dependency
such that
T
|
=
π
(
x
,
z
) and tuples
π
(
x
,
y
)
→∃
z
a
,
b
, and check that
S
(
a
,
b
) and
T
π
(
a
,
z
).By
Proposition 11.6
, the first check
is polynomial. The second check however involves a tree pattern possibly containing vari-
ables, so it can only be done in
CO
NP. Altogether the algorithm is in
|
=
π
|
=
∃
z
p
2
. Hardness can be
Π
obtained via a reduction from the validity of
Π
2
quantified Boolean formulae (see
Exer-
cise 16.3
).
When the maximum number of variables per pattern is fixed, proceed like in the case of
a fixed mapping. Since there are only polynomially many possible valuations of variables,
we may iterate over all of them using the algorithm from
Proposition 11.6
to check if
S
(
a
,
b
) and
T
π
(
a
,
c
).
|
|
=
π
=
