曹路舟

(池州职业技术学院 信息技术系，安徽 池州 247000)

由于XML(Xtensible Markup Language)在Internet上的应用非常广泛，因此XML在具体使用过程中为了得到高质量的数据，对其模式的设计就显得特别重要，而其中DTD(Document Type Definition)模式的设计一直倍受广大XML研究者关注。DTD模式的研究主要包括以下几个方面的内容：怎样判定一个DTD模式设计是否良好；如果是一个设计不好的DTD，我们要通过什么样方法将其转化成一个满足要求的好的DTD模式等。如何来判定一个DTD设计是否良好呢？其主要依据是检查该DTD有没有存在着数据冗余信息，如果存在着数据冗余信息，它就和关系数据库一样，会引起XML文档的插入、删除、更新等操作异常，这势必影响到XML在不同应用程序之间的数据表示和交换上的使用。

本文利用XML层次结构特点，从路径的角度出发，提出了由XML函数依赖引起的XML文档树有路径冗余的几种可能存在的情形，并相应的给出了消除冗余的方法及其相关的正确性证明，最后通过具体的实例验证了定理的正确性和有效性。

一、相关定义及符号声明

定义1(XML路径)给定DTD D(E,A,P,R,r)和满足D的XML文档树T( V,lab,ele,att,val,root),文档树T中的路径可以定义如下：路径q=v1.…. vn,其中,v1=root, vk∈ele(vk-1), (k=2,…,n-1)。若lab(vn)∈E，vn∈

ele(vn-1)， P(lab(vn))≠S，则称该路径q为元素节点型路径；若lab(vn)∈A，vn∈att(vn-1)或lab(vn)∈E，vn∈ele(vn-1)，P(lab(vk))=S，则称该路径q为值类型路径。

XML路径说明：

(1)令last(q)=vn,表示路径q中的最后一个节点，q-last(q)表示路径q在除去最后一个节点路径后的路径，本文仅考虑最后一个元素不为空的情况；

(2)Paths(T) 表示文档树T中所有路径的集合,即Paths(T)={q|q是T中的路径}；其中EPaths(T) 、APaths(T) 、VPaths(T)分别表示元素节点类型路径的……