Data Normalization - Information Systems Reengineering, Integration and Normalization - page 357

ments can be linked together through reference pointers. Storing element data in
minimum fragments reduces query processing time. Preventing data redundancy
reduces storage and allows for simple constraint-satisfying update checks, thus re-
ducing both space and time. As a result, we propose a methodology to generate a
minimum fragmented and redundancy freed XML conceptual schema and map it
into XML schema.
To avoid reference-pointers fragmentation, we need to locate the smallest clo-
sure elements and put them under a root element. Then according to the functional
dependencies in the requested data semantics, we locate the dependent elements
under these smallest closure elements as their child elements. For example, for FD:
A→B,wehavechildelementAunderparentelementB.Similarly,forID:A ⊑ B
we have subclass element A under superclass element B. If there are replicate ele-
ments, we replace them by an element artifact to eliminate data redundancy.
Furthermore, if we allow the same child element under more than one parent
element, then we will get data redundancy because its attribute values may have
to be replicated. In other words, if an object O relating to multiple objects force
the corresponding element of O to appear multiple times, the attribute values of
O will have to be replicated as well. Therefore, data redundancy may appear in
both cases.
We can implement the above concepts in the following algorithm such that Step
1-4 designs a minimum fragmented XML schema and step 5 eliminates data redun-
dancy in the design.
Algorithm of a good XML design (FD = functional dependency)
Input: Data dependency in Metadata Data Model H.
Output: A DTD Graph D.
Step 1 Extract FDs from H according to the data semantics in Fig. 9.17 . Discard
FDs of the form Aₒ .
Step 2 Generate Functional Closures: For each element A in H, use the FDs ex-
tracted in step 1 to generate A + .
Step 3 Set L to 1;
Repeat until all elements in H have been added to D.
Choose all smallest elements in H. An element A is smallest if there is no other
elementBsuchthatB≠AandB + ⊏ A + . However, if there are smallest elements A 1 ,
A 2 , …, A n such that A 1 + = A 2 + = … A n + , then choose only A 1 .
Add all chosen smallest elements in H to D as L-level elements.
Add every data semantic DTD graph derived from H according to XSD Graph
and DTD Graph (in Fig. 9.17 ) to the current elements in D.
Set L = L + 1.
Step 4 For every element A that is a child of more than one element, replace all
but one occurrence of A by id and idref such that idref refers to id of A.
Step 5 Replace element with duplicate occurrence value by a “fragment”
(branch) elements, that is, branch of elements immediate under the root element,
with id and idref. The fragment has an attribute id referred by its original parent
element's attribute idref.