Database Reference
In-Depth Information
Not only disjunction in DTDs is problematic. As another illustration of difficulties in
composing XML schema mappings, look at the following example.
Example 19.19 Consider
a
∗
}
D
1
=
{
r
→
,
D
2
=
{
r
→
bb
}
,
D
3
=
{
r
→
ε
}
with
a
and
b
having an attribute each, and
Σ
12
=
{
r
/
a
(
x
)
−→
r
/
b
(
x
)
}
,
Σ
23
=
{
r
→
r
}
.
Here the target trees are single-node trees with label
r
. In the composition we have pairs
(
T
,
r
) such that in
T
at most two different data values are present. This again requires
disjunction, e.g.,
r
[
a
(
x
)
,
a
(
y
)
,
a
(
z
)]
−→
∨
∨
x
=
z
). Intuitively, what causes the
problem here is a fixed number of repetitions of a label in the DTD (i.e.,
bb
).
(
x
=
y
y
=
z
There is also a variety of features in patterns that can lead to compositions that cannot be
defined with SO tgds. The example below shows that the use of the wildcard should be
restricted.
Example 19.20 Consider
a
1
a
2
;
a
1
→
D
1
=
{
r
→
ε
}
,
D
2
=
{
r
→
b
;
a
2
→
b
}
,
D
3
=
{
r
→
c
1
?
c
2
?
c
3
?
}
with no attributes and
Σ
12
=
{
r
−→
r
/ /
b
}
,
Σ
23
=
{
r
/
a
1
−→
r
/
c
1
;
r
/
a
2
−→
r
/
c
2
}
.
Just like in
Example 19.18
,
(
D
1
,
D
2
,
Σ
12
)
◦
(
D
2
,
D
3
,
Σ
23
)
contains exactly pairs (
r
,
T
),
where
T
matches
r
/
c
1
or
r
/
c
2
.
+
,
+
,
= instead
of the wildcard (see
Exercise 22.3
). In other words, the following features take us out of
the class of mappings definable with SO tgds:
The mappings in
Example 19.20
can be modified to use either of
↓
→
,
→
•
disjunction or multiple (bounded) repetitions of labels in the productions of DTDs,
•
wildcard, descendant, next-sibling, following-sibling, and inequalities in st-tgds.
Well-behaved composition
Now that we understand which features cause problems with XML composition, just elim-
inate them all. We are then left with vertical navigation, equality comparisons, Skolem
functions, and nested-relational DTDs that rule out disjunctions and repetitions of labels.
That is, we are left with mappings from
SM
nr
(
↓
,
=
,
F
UN
)
.
The good news is that this class is closed under composition.
