概率xmltwig查询处理算法的研究和实现的论文

《概率xmltwig查询处理算法的研究和实现的论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据AThesisinComputerArchitectureResearchandImplementationofTwigQueryEvaluationAlgorithmsonProbabilisticXMLByLIUSiqiSupervisor：ProfessorWANGGuorenNortheasternUniversityJune2012万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论

2、文中作了明确的说明并表示谢意。学位论文作者签名：训崤日期：加}2．6．1(『学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半西两年口学位论文作者签名：南啤青签字日期：刃协．‘．f7万方数据东北大学硕士学位论文摘要概率XML的Twig查询处理算法的研究与实现摘要近年来，对于概率XML数据管理，已经有不少理论研究。但是，对twig查

3、询处理，仍然缺少着比较高效的算法。因此，本文中针对概率XML的twig查询处理算法进行研究。首先，本文提出一种新的针对概率XML文档的编码策略，pDewey编码策略，来对文档中的普通节点和分布节点的标签和概率进行编码。从而根据编码可以高效地计算：任意一个节点的所有祖先节点的编码、标签和概率；任意两个节点的公共祖先节点的编码、标签和概率。这些性质对twig模式匹配与匹配结果的概率计算都是至关重要的。接着，本文提出一种新的针对概率XML文档的分流策略，Tag+Probability分流策略。它不仅根据节点的标签，而且根据节点的概率，将编码后的节点集合划分成多个节点流，使得同一个节点流中的节点，

4、具有相同的标签和相近的概率。从而能在查询处理时，对输入数据进行剪枝，从而节省I／O代价，显著地提高查询处理的效率。最后，基于提出的编码策略和分流策略，本文提出一种新的概率XML文档twig查询处理算法，pTJFastTP算法。作为一种holistictwigjoin算法，它能够高效地对概率XML文档进行twig模式匹配。在连接阶段，算法利用pDewey编码，对匹配结果的概率计算，并且，一边连接一边根据概率阈值对中间结果进行剪枝，从而进一步提高效率。本文进行详尽的实验，评价pTJFastTP算法的性能。实验中，采用各种不同结构的数据和twig查询，将pTJFastTP与目前效率最高的概率XM

5、L的twig查询处理算法，ProTwig算法，进行比较。实验结果均表明，在I／0和CPU代价上，pTJFastTP算法显著地优于ProTwig算法，并且，pTJFastTP算法具有更好的数据可伸缩性和查询可伸缩性。关键词：概率XML；Twig；查询处理万方数据ResearchandImplementationofTwigQueryEvaluationAlgorithmsonProbabilisticXMLAbstractInrecentyears，therehavebeenmanytheoreticalstudiesonthemanagementofprobabilisticXMLdata

6、．Butfortheevaluationoftwigqueries，thereisstillalackofefficientalgorithms．Therefore，thisthesisstudiestwigqueryevaluationalgorithmsonprobabilisticXML．First，thisthesisproposesanewencodingscheme，pDeweyencodingscheme，forprobabilisticXMLdocuments，toencodethetagsandprobabilitiesofordinaryanddistributiona

7、lnodesindocuments．pDeweycodesCanbeusedtoefficientlycompute：Thecodes，tagsandprobabilitiesoftheancestorsofanynode；Thecodes，tagsandprobabilitiesofthecommonancestorsofanytwonodes．Thesepropertiesarecrucialformatchingt