Normalization of XML Document with Strong MVD under Incomplete Information Circumstances

When there are multivalued dependencies among data elements for XML document under incomplete information circumstances, data redundancies and abnormal update often occur on condition that there are no constraints in XML document. In order to avoid data redundancies and abnormal update, the normalization of XML document under incomplete information circumstances is discussed based on XML strong multivalued dependencies. The definition of XML strong multivalued dependencies for the incomplete XML document tree is formalized based on the equivalence and the consistency of node’s information. Based on the hierarchical XML strong multivalued dependencies, the condition of satisfying an XML strong multivalued dependency normal form for the incomplete XML document tree is proposed. Justifying theorem that ensures redundancy free in the incomplete XML document tree is given, and an algorithm for normalizing an incomplete XML document tree is presented, and then the analysis of time complexity is given. Finally, according to the proposed theorem, the analysis of an instance is discussed. The results in this work can deal with data redundancies aroused by the hierarchical XML strong multivalued dependencies in XML document under incomplete information circumstances, and help carry out the objective of the normalization theory of XML database.