XML Normalization Research On Functional Dependency And Multi-valued Dependency

eXtensible Markup Language is a new technology for data representation andexchange on the Internet, it is also a strong format for sharing information on the Web.With XML data representation mechanism becoming more and more popular, the problemof designing XML model is considered as one of the most research.The almost technologyof XML research based on DTD since it has many advantages. Since the defect ofdesigning XML model lead to data redundancy, there are data dependency which causedata abnormity. As Web is open, comparing to relational database, the harm of XML dataabnormity is more higher. Therefore, it has necessary to the research on XMLnormalization.Basis on present research situation at home and abroad, this paper resrach XMLnormalization on the condition of the coexistence of XML functional dependency andXML multi-valued dependency.Firstly, this paper studies the concepts of path expression in DTD, XML is extenedwith functional dependency and multi-valued dependency, which are fundanmental tosematic specification. And make formalized definition on functional depency andmulti-valued dependency of XML; Based on node equality, it provides the description ofkey and redundancy and makes further define logical implication and cover for XML datadependency.Secondly, Based on XML functional dependency, XML multi-valued dependency,key and redundancy etc, research the inference rules of XML functional dependency andXML multi-valued dependency, and prove the soundness and completeness of theinference rules.Thirdly, defining the path dependency basis, the membership and the minimizedependency set, and make further give the algorithms of computing path dependency basis,the membership and the minimize dependency set. The correctness, terminability and thetime complexity of the three algorithms are proved.Finally, this paper analyses characteristics of XML on the condition of thecoexistence of functional dependency and multi-valued dependency, then defines the third normal form and fourth normal form. it further proposes normalization rules and the termsto meet the fourth normal and provides theorem to detemine the XML document treewhich meet the above terms without redundancy, and the sound of the fourth normal formis proved by experiment.