Constraint-Based Normalization Algorithms for XML Documents

XML schema design is part and parcel of databases design. Based on the basic con cepts of XML documents, some related definitions are given. They are definitions of partial functional dependency, transitive functional dependency for XML docu ments, normal form for XML documents named from the first normal form to the thi rd normal form for XML documents, and lossless decomposition for DTDs. Normaliza tion rules for XML schema and two normalization algorithms of lossless decomposi tion are provided. Validity, terminability, and time complexity of these will al gorithms are proved. The efficiency of query and storage for XML documents norma lized is enhanced. These will establish theoretic foundation for preserving func tional dependency for XML documents, multi-valued dependency for XML documents, and further normalization research of XML schema design.