1792一种基于结构索引的xml模式匹配方法

《1792一种基于结构索引的xml模式匹配方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种基于结构索引的XML模式匹配方法乔健陈彤兵汪卫施伯乐（复旦大学计算机与信息技术系200433）摘要XML文档采用了树型的数据模型，对其查询通常是用带宥选择谓词的模式树在XML数据屮进行匹配，因此找出XML文档中所有符合模式树结构的元素集是XML查询处理的核心操作。本文提出了结构索引JoinGuide,并在此拈础上提出了一种新的XML模式匹配方法。它使用JoinGuide来对模式树进行预匹配，这祥在XML文档上查询时可以利用索引上的匹配结果來忽略部分连接谓词和不必耍的候选XML元素序列。本文还提出丫三种具体算法来利用索引匹配结果进行

2、进一步的查询。实验结果表明木文中的模式树匹配方法优于以往的匹配方法，并且索引所需的空间很小。关键词XML：模式树匹配：结构索引：JoinGuideAStructuralIndexBasedXMLPatternMatchingApproachQiaoJian,ChenTongbing,WangWei，andSHIBai-Le(DepartmentofComputingandInformationTechnology，FudanUniversity，Shanghai200433)AbstractXMLdocumentemploysatre

3、e-structureddatamodelanditsqueriestypicallyspecifypatternsofselectionpredicatestomatchXMLdata.SoFindingalloccurrencesofsuchapatterninaXMLdocumentisthecoreoperationofXMLqueryprocessing.Inthispaper，weintroduceakindofstructuralindexcalledJoinGuide,andthenpresentanovelxmlpa

4、tternmatchingapproachbasedonit.ItutilizesJoinGuidetopre-matchapatterntree,thenwhenqueryingXMLdocuments，wccanusetheprc-matchresulttoavoidsomejoinpredicatesandinputxmlelementslist.WealsopresentthreealgorithmstoqueryXMLdocumentsusingpre-matchresult.Experimentsshowthatourap

5、proachoutperformsthepreviousones，andtheindexsizeissmall.KeywordsXML;patternmatching;structuralindex;JoinGuide1引言随着XML的广泛应用，如何高效的查询XML数据变得越来越重要。常用的XML查询语言有XPath和XQuery等，由于XML的树模型，它们也常被表示成树型结构的模式[8],因此找出模式树在XML文档中的所有匹配是查询处理的关键操作。PJU0j[9j[3j巾提出了对XML数据建立结构索引的方法，可以较快的处理一般路径查

6、询，但是这类方法无法判断返回结点的子树条件，也无法返回具有结构关系的结点对。[13][1][2][7]屮提出将XML文档编码后使用结构化连接的方法进行查询，这类方法可以找出模式树在文档中的匹配，查询能力大于结构索引方法，但是没有利用结构索引，要进行大量连接操作，影响了查询效率。本文结合了这两类查询方法的优点，提出了一种新的XML模式树匹配方法，使用结构索引减少不必要的连接且查询能力等价于结构化连接方法。本文提fli结构摘要索引JoinGuide,在进行模式树匹配时首先在JoinGuide上进行预匹配，根据预匹配结果可以去掉原模式树中的

7、一部分谓词条件，减少候选XML元素序列。本文还提出了三种具体算法来利用预匹配结果查询原XML数据。本文剩余部分组织如下。第2节介绍了相关工作；第3节简述了问题的基本概念；第4节描述了JoinGuide索引结构及作川；第5节提出Z具体的查询算法：第6节通过实验证明了本文算法的性能：最后第7节屮给出总结。2相关工作以前的工作己经对模式树匹配问题做了大量研宂。[1]中通过分解模式树为二元结构关系，分别连接再把二元结果组合起来来处理模式树匹配，但是连接代价较大且会产生大量无用的中间结果。[2]中的TwigStack算法可以将整棵模式树一起匹配

8、处理,避免保存无用的中间结果，它对于只有祖先后代边的模式树匹配是最优的。但是它没有使用索引信息,必须对模式树屮所有的边都进行连接，而且它对于带有父子边的模式树不能保证最优。[7]在TwigStack算法的基础上使用了XR