Database Reference
In-Depth Information
Figure 2. Two XML trees as equivalent instances of S
1
; J
2
is a canonical instance, whereas J
1
is not
•
(
I
,
r
) ≤ (/
top
[
E
], ω), iff
∧
n
∧
N
e
(
child
(
r, n
)
∧
(
I
,
n
) ≤ (
top
[
E
], ω));
•
(
I
,
n
) ≤ (
l
[
E
1
, ...,
E
k
], ω), iff λ(
n
) =
l
and
∧
n
1
, ...,
n
k
∧
N
e
(
child
(
n, n
1
)
∧
(
I
,
n
1
) ≤ (
E
1
, ω)
∧
...
∧
child
(
n, n
k
)
∧
(
I
,
n
k
) ≤ (
E
k
, ω));
•
(
I
,
n
) ≤ (
l
/
E
, ω), iff λ(
n
) =
l
∧ ∧
n'
∧
N
e
(
child
(
n, n'
)
∧
(
I
,
n'
) ≤ (
E
, ω));
•
(
I
,
n
) ≤ (
l = x
, ω), iff λ(
n
) =
l
and
∧
n'
∧
N
t
(
child
(
n, n'
)
∧
ν(
n'
) = ω(
x
)).
In fact, a description (
S
, Ω) represents a class of instances of
S
with the same set of valuations Ω,
since elements in instance trees can be grouped and nested in different ways.
For example, both XML trees
J
1
and
J
2
in Figure 2 conform to the schema
S
1
from Example 1, and
satisfy the description (
S
1
, {(
XML
,
2005
,
Ann
,
LA
), (
XML
,
2005
,
John
,
NY
)}, although they are organized
in different ways.
By a
canonical instance
we will understand the instance with the maximal width, i.e. the instance
where subtrees corresponding to valuations are pair-wise disjoint. For example, the instance
J
2
in Figure
2 is a canonical instance, whereas
J
1
is not since two authors are nested under one publication.
SCHEMA MAPPINGS
Further on in this chapter, we will refer to the running example depicted in Figure 3. There are three XML
schema trees
S
1
,
S
2
,
S
3
, along with their instances
I
1
,
I
2
, and
I
3
, respectively.
S
1
is the same as
S
1
in Figure
1, and its instance
I
1
is empty. The schemas and their instances are on peers
P
1
,
P
2
, and
P
3
, respectively.
The key issue in data integration is this of
schema mapping
. Schema mapping is a specification
defining how data structured under one schema (the
source schema
) is to be transformed into data struc-
tured under another schema (the
target schema
). In the theory of relational data exchange,
source-to-
