Information Technology Reference
In-Depth Information
XML
Normalized XML
Y
Z
E
X
Y
ϗ
X
Z
ϗ
˶
ʻ˸̋̇˸́̆˼̂́ʳ˴ʼ
c_ref
ʻ˸̋̇˸́̆˼̂́ʳ˴ʼ
˵
ʻ˸̋̇˸́̆˼̂́ʳ˴ʼ
b_ref
ʻ˸̋̇˸́̆˼̂́ʳ˴ʼ
˸
a
a
normalize
ctoeref
ˢ
ˢ
btoeref
O=Overlap generalization
Note:
^b
DQG
^c
DUHUHIHUULQJWRHOHPHQWHWKURXJKWH[WYDOXHRIHOHPHQWH
Fig. 9.11
Normalized XML document in overlap generalization
Graphically, the above transformations are depicted as follows:
Our strategy to prove that our normalization process preserves the information
content of the input XML document is by induction on the number
n
of normaliza-
tion operations applied to the XML document. We use the notation D
i
to denote the
input XML document that has
i
normalization operations performed on it. Particu-
larly, D0 is the original input XML document.
Basis: When
n
= 0, no normalization operation has yet been applied. Thus, the
information content remains the same and is obviously preserved.
Induction: Assume the information content of the input XML document is pre-
served after applying
k
≥0normalizationoperationsforsomefixedinteger
k
. That
is, D0, D1, D2, …, D
k
all have the same information content. We now consider
applying the (
k
+ 1)
th
normalization operation and we need to show that the infor-
mation content of D
k
and D
k
+ 1 are the same. Our argument focuses on each of the
data semantics that require normalization operations.
• Overlapgeneralization:Inthiscase,twogeneralizationXMLelementsYandZ
have the same content. Our normalization operation adds a new XML element E
with the same content as e under the root element, as shown in Fig.
9.11
. Since E
has the same content as Y and Z and Y' and Z' are XML reference elements that
point to E, the information content of D
k
is preserved. In other words, D
k
and
D
k
+ 1 have the same information content.
• m-to-nCardinality:Inthiscase,someXMLelementshavethesameinforma-
tion content and they have many-to-many relationships among them. Again, for
the XML elements that have the same information content, we create a new
XML element E with the same information content under the root element. In
other words, the instance of elements d type and e type are in many-to-many
cardinality. We create new XML elements d_ref type and e_ref type with the
Search WWH ::
Custom Search