Database Reference
In-Depth Information
types of schema mappings easier. Note also that these patterns use neither the descendant
relation nor the horizontal navigation nor inequalities.
Classification of schema mappings
We shall denote classes of schema mappings by SM
∗
(
σ
), with
σ
indicating features of
patterns used in mappings, and
restricting their structural features, such as the type of
schemas they use, or whether they deal with just the structure of documents, or both struc-
ture and data.
Specifically, we write
∗
SM
∗
(
) to restrict any class of mappings SM
∗
in a way that only uses patterns from
•
σ
Π
(
σ
).
For instance, SM(
⇓
,
⇒
,
∼
) is the class of all schema mappings and SM(
↓
,
=) is the class
of mappings that only mention the child axis and equality of data values.
As for possible values for
∗
,weusethreeofthem.
SM
◦
(
•
σ
) is the class of mappings in SM(
σ
) where st-tgds in
Σ
st
do not mention at-
tribute values, i.e., where all pattern formulae are of the form
[
]. These will be useful
for establishing hardness results, telling us that structural properties alone make certain
problems infeasible.
λ
SM
dtd
(
•
σ
) is the class of mappings from SM(
σ
) whose schemas are DTDs.
SM
nr
(
•
σ
) is the class of
nested relational schema mappings
in SM(
σ
), i.e., schema map-
pings whose
target
schemas are nested relational DTDs.
The class of nested relational schema mappings will play an important role in the study
of XML data exchange. These mappings have particularly nice properties, especially with
respect to the complexity of many computational problems. The class itself includes many
important types of schema mappings. Note, for example, that under the standard XML
encoding of relational databases shown earlier, relational schema mappings fall into the
class SM
nr
(
↓
,
=).
Complexity of schema mappings
We now move to the complexity of schema mappings. The general
membership problem
we consider is defined as follows:
PROBLEM
: XML-SM-M
EMBERSHIP
.
INPUT:
A schema mapping
M
, two XML trees
S
and
T
.
QUESTION
: s(
S
,
T
) in
M
?
Of course this corresponds to the
combined complexity
of schema mappings. We shall also
look at
data complexity
, when the mapping is fixed. That is, for each mapping
M
, we look
at the problem XML-SM-M
EMBERSHIP
(
M
) whose input consists only of
S
and
T
,and
the question, as before, is whether (
S
,
T
)
∈
M
.
