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