The Research On Multivalued Dependencies For XML

XML has recently emerged as a new standard for data representation and interchange on Web by its various adavantages. But the schema of XML provides little semantic content. Similar to relational database, if XML schema designing is not good, it will also cause abnormity for inserting, deleting and updating data. But the harmfulness of XML data abnormity is further higher than relational data as Web is open. Therefore it is necessary to develop the normalization theory in XML now. Based on the general analyzing of the related work in domestic and international, this paper investigated the issue of multivalued dependencies for XML on the DTD level. The primary coverage is as follows.Firstly, the constraint of multivalued dependencies for XML is investigated based on the analyzing the designing of DTD. Then, the definition of multivalued dependencies in XML is proposed based on path expression and tree tuple.Secondly, the problem of inference rules for multivalued dependencies for XML is investigated. The definitions of path dependency basis and the closure of paths of multivalued dependencies for XML are proposed. A sound and complete set of inference rules is presented, and soundness and completeness of the inference rules are proved.Thirdly, the membership problem of multivalued dependency for XML is investigated. An algorithm of computing path dependency basis is given. Then, based on computing path dependency basis, an algorithm of membership problem of XMVD is presented. The correctness of the two algorithms are proved and the time complexity of them is analyzed in this paper.Fourthly, the normal form and normalization problem of multivalueddependencies for XML are investigated. The definition of normal form (MXNF) for the situation under which multivalued dependencies exist is proposed. Then proveness of that MXNF can avoid updating anomalies and redundancies is given. Based on the normal form, an algorithm for converting an arbitrary DTD into one in MXNF is presented. The termination and correctness of the algorithm is proved and the time complexity of it is analyzed.Finally, the problem of checking the satisfaction of a set of multivalued dependencies in an XML document is investigated. By given the definitions of a stack structure and the value tuple, the control structure of a document is defined. An algorithm for calculating contributing elements is given. An algorithm for parsing the document is proposed. Then, an algorithm for checking the satisfaction of a set of multivalued dependencies in an XML document is presented. The analysis of the algorithm is given.