不完全信息环境下存在XML强多值依赖的XML文档规范化研究

Normalization of XML Document with Strong MVD under Incomplete Information Circumstances

不完全信息环境下XML文档中的数据存在多值依赖时,为了避免在没有约束条件下XML文档数据出现冗余及更新异常,引入XML强多值依赖的概念和理论对XML文档的规范化进行了系统研究.基于节点信息等价、节点信息相容的概念给出了XML强多值依赖的定义;基于层次化的XML强多值依赖,提出了不完全XML文档树满足XML强多值依赖范式的条件;给出了满足该条件的不完全XML文档树无数据冗余的判定定理;提出了不完全XML文档树的规范化算法,对其时间复杂性进行了分析.理论研究和实例分析表明:研究成果较好地解决了在不完全信息环境下XML文档中存在层次化的XML强多值依赖引起的数据冗余问题.

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 inform＇ation 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.