Database Reference
In-Depth Information
Arbitrary schemas
Nested-relational DTDs
C
ONS
(
⇓
)
E
XPTIME
-complete
P
TIME
C
ONS
(
⇓,⇒
)
E
XPTIME
-complete
P
SPACE
-complete
C
ONS
(
⇓,∼
)
undecidable
N
EXPTIME
-complete
C
ONS
(
⇓,⇒,∼
)
undecidable
undecidable
Figure 18.1 Complexity of consistency problems.
solution
T
. Recall that a target tree is a solution for
S
iff it satisfies the partially evaluated
pattern
δ
S
,M
combining all target requirements (
Lemma 12.1
). Fix a homomorphism
ξ
δ
S
,M
into
T
.Let
T
be the solution obtained from
T
by removing all nodes which are
not enforced by
from
nor by
D
t
.Thatis,an
-labeled child of an
-labeled node is removed if
it has no descendant in the image of
ξ
, and the production for
contains
∗
,
?, or
+
(for
ξ
+
keep at least one
-labeled child).
For each node the number of children enforced by
b
Σ
st
ξ
is bounded by
δ
S
,M
≤|
Σ
st
|
,
s
and the number of children enforced by
D
t
is at most
D
t
.As
D
t
is nonrecursive, the size
b
Σ
st
of
T
can be bounded by
b
t
=(
)
D
t
, which is single-exponential.
Given these bounds, the algorithm for consistency guesses some
S
|
Σ
st
|
+
D
t
s
=
D
s
with data values
|
b
Σ
st
in
{
1
,
2
,...,
b
s
}
,some
T
|
=
D
t
with branching at most
|
Σ
st
|
+
D
t
and data values in
s
{
, and checks if
S
,
T
satisfy the st-tgds. The check need not be P
TIME
,
but a naıve algorithm checking each st-tgd
1
,
2
,...,
b
s
+
b
t
}
against each possible valuation requires at
)
Σ
st
checks polynomial in the size of
S
,
T
,and
most
|
Σ
st
|·
(
|
S
|
+
|
T
|
Σ
st
. Altogether this
gives a N
EXPTIME
algorithm.
Figure 18.1
summarizes the complexity results of this section.
18.3 Absolute consistency for XML
Reasoning about the complexity of absolute consistency is significantly harder than rea-
soning about the consistency problem. We know that C
ONS
(
⇓
,
⇒
) can be easily reduced to
C
ONS
◦
(
). However, eliminating data values does not work for absolute consistency.
Indeed, consider a mapping
⇓
,
⇒
M
with:
a
∗
,
a
•
a source DTD
r
→
→
ε
;
•
atargetDTD
r
→
a
,
a
→
ε
, with
a
having a single attribute in both DTDs;
•
a single st-tgd
r
/
a
(
x
)
−→
r
/
a
(
x
).
