Database Reference
In-Depth Information
Decidable cases of consistency
The main result of this section is an algorithm for solving the problem C
ONS
(
⇓
,
⇒
), i.e.,
consistency without the =
,
= comparisons. The algorithm works in single-exponential
time, and this time bound cannot be lowered, since the problem is E
XPTIME
-complete.
That is, we prove the following result.
Theorem 18.1
The problem
C
ONS
(
⇓
,
⇒
)
is solvable in single-exponential time, and is
in fact
E
XPTIME
-complete.
The algorithm is based on using automata-theoretic tools. We already know that every
schema can be encoded as an UNFTA, i.e., a nondeterministic tree automaton working on
unranked trees (see
Definition 10.6
on page
139
). Now we are going to see how to encode
a pattern as UFTA(DFA), that is, deterministic UNFTA with all transitions represented by
DFAs. As UNFTAs do not look at data values at all, we cannot hope to do the same for
general tree patterns; we need to assume the patterns do not talk about data values either.
Lemma 18.2
For every pattern
π
without variables, one can compute in exponential
T
T
time a UFTA(DFA)
A
π
such that L
(
A
π
)=
{
|
=
π
}
.
Proof
We construct
A
π
by induction on the structure of
π
.If
π
=
with
∈
Γ
∪{}
,the
claim follows easily. Assume we have an UFTA(DFA)
A
π
=(
Q
,
δ
,
F
) for
π
. To obtain
//
π
(
f
,
a
)=
Q
∗
(
F
)
Q
∗
for every
a
A
//
π
add a fresh state
f
,set
δ
∪{
f
}
∈
Γ
(the equivalent
//
π
(
q
,
a
)=
F
)
∗
for every
a
DFA has two states),
δ
δ
(
q
,
a
)
∩
(
Q
−
∈
Γ
,
q
∈
Q
(equivalent
DFAs grow by at most one state), and
F
//
π
=
F
∪{
f
}
.
The last case is that of
π
=
[
μ
1
,...,
μ
n
]. Let us first construct an UFTA(DFA) for
[
μ
]
with
π
1
1
π
2
2
···
k
−
1
π
k
)
,
μ
=(
+
and
1
,
2
,...,
k
−
1
∈{→
,
→
}
.Let
A
π
j
=(
Q
j
,
δ
j
,
F
j
) be the UFTA(DFA) constructed
for
π
j
. The state space of
A
[μ]
is
Q
=
Q
1
×
Q
2
×···×
Q
k
×{
,
⊥}
. Consider the language
M
defined by the regular expression
Q
∗
F
1
α
1
F
2
α
2
···
F
k
−
1
α
k
−
1
F
k
Q
∗
,
Q
q
j
∈
where
F
j
=
α
i
=
Q
∗
if
+
,and
otherwise. It is
not difficult to construct an NFA with
O
(
k
) states recognizing
M
; standard determinization
gives an equivalent DFA
{
(
q
1
,...,
q
k
+1
)
∈
F
j
}
,
i
=
→
α
i
=
ε
with 2
O
(
k
)
states. The transition relation of
B
A
[μ]
is now defined
as
((
q
,
s
)
,
a
)=(
δ
1
(
q
1
,
a
)
×
δ
2
(
q
2
,
a
)
×···×
δ
k
(
q
k
,
a
)
×{
,
⊥}
∩
δ
)
K
,
a
=
(or
= ), and
K
=
Q
∗
−
where
K
=
M
if
s
=
M
otherwise. Each such transition
can be represented by a product of DFAs
B
1
,...,
B
n
and
B
(or its complement), where
B
j
are single-exponential in
π
j
,and
B
is single-exponential in
k
.Since
π
is roughly
n
j
=1
n
j
=1
π
j
B
j
·B
π
∑
, the size of the product DFA
∏
is single-exponential in
.The
