xml+twig查询优化研究

《xml+twig查询优化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要XML因其具有自描述性，可扩展性以及开放性等优点已经成为网络上信息表达和数据交换的事实标准。随着XML数据的不断增长，尤其是大规模XML数据的出现(如XML数据库)，对XML数据的查询正在成为学术界和工业界的研究热点。但同时由于XML文档具有的半结构的特性，使得传统的对关系数据库的查询算法对其不适用，因此如何高效地查询XML数据成为新的研究课题。为了实现XML的查询优化，近年来人们提出了各种算法，主要有基于路径索引的树遍历、基于序列的方法以及结构连接和整体twig查询，其中整体twig查询可以

2、避免结构连接产生大量的中间结果而具有很大的优越性，得到了广泛的研究。本文对整体twig查询优化展开研究，主要做了以下几个方面的工作：(1)提出了DBL排序算法，用于决定叶子查询结点的处理顺序，更重要的是在构造与查询结点相关联的列表中起到过滤对查询结果没有贡献的元素的作用。(2)提出了一种新型的整体twig查询算法TwigstackFast，它是个单阶段算法，采用ExtendedDewey编码，能够处理带A．D关系、P．C关系的查询，而且是CPU和I／O最优的。TwigStackFast算法没有第二

3、阶段的合并连接操作，因而可以消除了大量的时间和空问开销。(3)通过把TwigStackFast算法与四个经典的twig查询算法TwigStack、HolisticTwigStack、Twi92Stack、TJFaSt进行实验对比后可以看出，TwigStackFast具有更优越的性能。关键词：XML；整体twig查询；ExtendedDewey编码AbstractBecauseofthecharacteristicsofself-description，extensibilityandopennes

4、s，XMLhasbecomethefactualstandardofthedatarepresentationandexchangeintheweb．WithXMLdatarapidlyincreasing，especiallywiththelargeXMLdataemerging,XMLqueryresearchisbecomingthehotspotinbo廿lindustryandacademia．Withthecharacteristicofsemi—structure，thetradit

5、ionalsqlqueryalgorithmsfortherelationaldatabasearenolongerapplicabletoXMLdata．SohowtoefficientlyqueryXMLdatabecomesanewstudy．InordertoachievetheXMLdataqueryoptimization，inrecentyearsresearchershaveproposedalotofalgorithms，suchastreeenumerationbasedonp

6、athindexes，approachesbasedonsequences，structuraljoinsandholistictwigjoins．Holistictwigjoinalgorithmsyieldsignificantlylessintermediateresultsthanstructuraljoins，SOalotofresearchhasbeenmadeonthis．Inthispaper,researchhasbeendoneinthefollowingaspects：(1)

7、ThispaperproposesDBLSortalgorithm，whichdecidestheorderforprocessingleafquerynodesandplaysanimportantroleinfilteringXMLdementswhichdon’tmakecontributiontoqueryresults．(2)ThisPaperproposesTwigStackFast，anovdone-phaseholistictwigjoinalgorithm，whichusesEx

8、tendedDeweyencoding．ItcallsupportefficientevaluationofquerieswithP—CorA—Drelationship．ItisCPUandI／Ooptimal．Itdoesn’tneedtoperformmergeoperationofthesecondphasethatotheralgorithmsdo，whicheliminatessignificantamountsoftimeandspaceoverheads．(3)Th