Database Reference
In-Depth Information
in which
some
trees have solutions, we would like to consider mappings in which
every
tree has a solution. These are very desirable for a variety of reasons: not only are we guar-
anteed to have possible target documents for every possible source, but the property is also
preserved when we compose mappings (see
Chapter 19
).
We say that a mapping
Σ
st
) is
consistent
if it can be useful for at least
some source instances. That is, a mapping is consistent if S
OL
M
(
S
)
M
=(
S
s
,
S
t
,
= 0 for some source
instances
S
= 0.
Recall that in
Part THREE
of the topic we dealt with XML schema mapping classes of
the form SM(
|
=
S
s
. This can be restated as
M
lists available features of the mappings, such as axes used in
navigation through documents, or the possibility of using equalities and inequalities. The
first key problem we consider is the one below.
σ
),where
σ
P
ROBLEM
: C
ONS
(
)
I
NPUT
: A mapping
σ
M
=(
S
s
,
S
t
,
Σ
st
)
∈
SM(
σ
)
Q
UESTION
: s
M
consistent?
If we use SM
◦
(
) (i.e., if we use mappings in which attribute values are
not mentioned at all), we denote the consistency problem by C
ONS
◦
(
σ
) instead of SM(
σ
σ
).
is
absolutely consistent
if it makes sense for
every
source tree
S
: each
such tree has a solution under the mapping. That is, S
OL
M
(
S
)
A mapping
M
= /0forall
S
|
=
S
s
.Wethen
consider the problem:
P
ROBLEM
: A
B
C
ONS
(
σ
)
I
NPUT
: Mapping
M
=(
S
s
,
S
t
,
Σ
st
)
∈
SM(
σ
)
Q
UESTION
: s
M
absolutely consistent?
These are the two main problems studied in this chapter.
18.2 Consistency for XML
The goal of this section is to show that the behavior of the consistency problem C
ONS
(
σ
)
depends heavily on
σ
, i.e., on the exact set of features allowed in mappings. Recall that
+
,
+
, as well as data comparisons = and
σ
may contain navigational axes
↓
,
→
,
↓
→
=,
+
,
as
see
Chapter 11
,page
147
. Recall that we abbreviate
↓
,
↓
⇓
(vertical navigation),
+
,
as
→
,
(data comparisons).
A brief summary of the algorithmic properties of the consistency problem is as follows:
→
⇒
(horizontal navigation), and =
,
= as
∼
•
= comparisons, the problem can be solved in exponential time, and this
complexity cannot be lowered.
•
With =
,
= comparisons the problem quickly becomes undecidable.
•
Without =
,
When schemas are restricted to be nested-relational DTDs, the complexity in general
drops, but not in every single case.
