模糊XML文档与模糊DTD相似性研究

发布时间：2019-08-15 12:10

【摘要】：在模糊XML数据管理中,模糊XML文档和模糊DTD的相似性是模糊XML数据整合、模糊XML文档聚类的关键步骤.为了研究模糊XML文档和模糊DTD的相似性,对模糊DTD树进行了规则变换,主要解决元素和属性的析取约束和基数约束问题,即由析取范式转化为合取范式,将元素或属性的重复次数确定化,然后利用树编辑距离算法对模糊XML文档树和转化后的模糊DTD树集合进行相似性对比.通过实验验证了所提方法的性能优势.
【图文】：

实例图,XML文档,实例

用基于“隶属度和可能性分布”的模糊XML文档的表示模型［8］．在这个模型中，一个元素可以有相关的隶属度．元素的隶属度意味着成为其父亲的孩子节点的可能性．而元素的属性值可以用概率分布来表示，并且这些值可以是析取的，也可以是合取的．下面给出一个模糊XML文档片段，如图1所示．模糊XML文档可以用树形结构来表示．按照DOM［9］模型，一个模糊XML文档也可以表示为一个单根的有序标签树，其中的节点对应文档中的元素和属性．本文只比较树的结构相似性，所以省略元素和属性的值．图1中文档的树结构如图2所示．1.2模糊DTD及树形表示模糊DTD作为模糊XML文档的语法结构，描述了模糊XML文档的结构框架．与非模糊DTD不同的是，模糊DTD引入了模糊构造子Dist，Val，Poss，Type．下面给出图1中模糊XML文档对应的模糊DTD，如图3所示．＜collegeCName=“NEU”＞＜ValPoss=0.8＞＜departmentDName=“IST”＞＜studentSID=“20130425”＞＜age＞＜DistType=“disjunctive”＞＜ValPoss=0.8＞26＜/Val＞＜ValPoss=0.9＞28＜/Val＞＜ValPoss=0.8＞29＜/Val＞＜/Dist＞＜/age＞＜email＞＜DistType=“conjunctive”＞＜ValPoss=0.6＞John@yahoo．com＜/Val＞＜ValPoss=0.8＞John@qq．com＜/Val＞＜ValPoss=0.5＞john@sina．com＜/Val＞＜/Dist＞＜/email＞＜/student＞＜/department＞＜/Val＞＜/college＞图1模糊XML文档实例Fig.1SampleofafuzzyXMLdocument图2模糊XML文档树实例Fig.2SampleofafuzzyXMLdocumenttree＜!ELEMENTcollege(Val+)＞＜!ATTLISTcollegeCNameIDＲEF#ＲEQUIＲED＞＜!ELEMENTVal(department*)＞＜!ATTLISTValPossCDATA“1.0”＞＜!ELEMENTdepartment(student*)＞＜!

实例图,实例,析取,基数

与模糊XML文档一样，模糊DTD也可以用树形结构来表示．图3中模糊DTD的树结构如图4所示．图4模糊DTD树实例Fig.4SampleofafuzzyDTDtree2模糊DTD树的转换规则由于模糊DTD中包含基数约束和析取约束，所以无法将其直接与模糊XML文档树进行相似性比较，需要对这些约束条件进行转换处理．2.1析取约束的转换析取约束“|”，表示该符号前后元素或属性不能同时出现，“|”即OＲ运算符．如果模糊DTD中包含“|”运算符，需要将其转换为多个不包含“|”的DTD集合．例如:表达式＜!ELEMENTa(b，(c|d))＞可以分解为＜!ELEMENTa(b，c))＞和＜!ELEMENTa(b，d)＞两个表达式，分别对应两个DTD．这一过程称为析取分解过程．用规则1来表示．规则1:处理D中析取约束“|”，对“|”两边的元素或属性进行选择，形成多个不包含“|”符号表达式的d，从而构成DTD集合Dset，d为Dset中的DTD．特殊地，对于模糊构造子Val，若该Val的父节点Dist下Type值为disjunctive，，表示Dist下的Val子树是不能同时出现的，相当于析取约束，即需要根据Type下的值判断Dist下的Val子树的个数．因为Val下子树表示的是属性和它的值，一般地，各个子树结构是相同的．为了不增加将来相似性比较的复杂度，本文选择只保留一个Val子树．2.2基数约束的转换规则模糊DTD中元素和属性的基数约束“*”，“+”，“?”是用来说明所约束元素或属性的可重复次数．如果用e来表示元素或属性，则e*表示e可以重复0到无限次，e+表示e可重复1次到无限次，e?表示e可重复0或1次．对于基数约束组合，可以用下面的原则来转换，以达到简化的目的．e++→e+，e＊＊→e*，e*+→e*，e*?→e*，e?+→e*，e??→e?．也就是说，所有的基数约束组合最终都可以转化为e*，e+，e?．需要
【作者单位】：东北大学计算机科学与工程学院;渤海大学信息科学与技术学院;
【基金】：国家自然科学基金资助项目(61370075) 教育部新世纪优秀人才支持计划项目(NCET-05-0288)
【分类号】：TP311.1

【相似文献】