ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

Constraint-Based Normalization Algorithms for XML Documents

Zhang Zhongping1, Wang Chao3, and Zhu Yangyong1   

  1. 1(Department of Computing and Information Technology, Fudan University, Shanghai 200433) 2(Department of Computing Science and Engineering, Yanshan University, Qinhuangdao 066004) 3(IPEDO, Inc., Shanghai 200030)
  • Online:2005-05-15

Abstract: 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.

Key words: XML, DTD, schema design, normalization