Database Reference
In-Depth Information
nonemptiness of
¯
A
2
×
∏
×
∏
j
:
T
|
=δ
j
i
:
S
|
=ϕ
i
A
A
γ
j
)
,
(
ψ
i
)
(
where
A
2
is the UNFTA underlying
S
2
,
A
(ψ
i
) recognizes the language of trees satisfying
ψ
i
,and
¯
γ
j
.By
Lemma 18.2
,all
these automata are at most exponential, which gives an E
XPTIME
algorithm for the case
without data values.
Let us now consider the general case, with variables. Still, neither equality nor inequality
is allowed. In particular, no variable can be used more than once in any tree pattern. The
main idea is simply to throw in every data value used in
S
to the alphabet. A tentative set
of positive constraints imposed on
U
by
S
would then be
A
(
γ
j
) recognizes the language of trees that do not satisfy
(
a
,
z
)
ϕ
(
a
,
b
)
Δ
=
{
ψ
(
x
,
y
)
−→ ∃
z
ψ
(
x
,
z
)
∈
Σ
12
and
S
|
=
ϕ
}
.
Patterns in
can still contain free variables, but one can simply ignore them, as without
repetitions and data comparisons, the variables merely state that some data value is there,
which is already enforced by the schema.
For the set of negative constraints enforced by
T
we would like
Δ
(
a
,
y
)
γ
{
γ
(
x
,
y
)
−→ ∃
z
δ
(
x
,
z
)
∈
Σ
23
and
T
|
=
δ
(
a
,
z
)
}
,
but this yields a potentially infinite set. How do we limit the domain from which the entries
of
a
are taken? Let
A
be the set of data values used in
S
or in
T
. It is not difficult to see
that in an intermediate tree
U
each data value not in
A
can be safely replaced by any fixed
data value, in particular, by a fixed data value from
A
. This holds because we do not use =
nor
=. Hence, we can assume that
U
only uses data values from
A
and take
(
a
,
y
)
γ
A
|
x
|
,
T
Φ
=
{
γ
(
x
,
y
)
−→ ∃
z
δ
(
x
,
z
)
∈
Σ
23
,
a
∈
|
=
δ
(
a
,
z
)
}
with the free variables ignored just like for
.
The composition membership algorithm should construct the set
Δ
|
Σ
12
||
S
|
Σ
12
Δ
(at most
)
Σ
23
polynomial checks). Then it is
polynomial checks) and
Φ
(at most
|
Σ
23
|
(
|
S
|
+
|
T
|
enough to check nonemptiness of
A
2
×
ψ
∈
Δ
A
(ψ)
×
γ
∈
Φ
¯
A
(
γ
)
,
which can be done in time exponential in the size of
Δ
and
Φ
(which are polynomial in the
size of
S
). This gives an E
XPTIME
algorithm.
Theorem 19.15
shows that in principle there could be a suitable formalism for compo-
sitions of SM(
), but most likely it is not SO tgds. Indeed, as we show below, the
composition problem can be E
XPTIME
-hard for some mappings in SM(
⇓
,
⇒
). Note that
this does not prove that SO tgds are incapable of expressing XML compositions, as it is not
known whether NP
⇓
,
⇒
E
XPTIME
. However, it is generally believed that NP
P
SPACE
,and
