xml数据的twig模式查询匹配算法研究

《xml数据的twig模式查询匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文XML数据的twig模式查询匹配算法研究姓名：雷欣申请学位级别：硕士专业：计算机软件与理论指导教师：高集荣20090520论文题目：XML数据的twig模式查询匹配算法研究专业：计算机软件与理论硕士生：雷欣指导教师：高集荣副教授摘要近年来，随着数据库和网络技术的发展，XML已经成为Internet上数据表示和交换的标准。随着XML技术的不断普及，Interact上以XML技术作为载体的数据越来越多，从而对这些XML数据的有效管理和查询也越来越受到国内外研究者的关注。对于XML文档的查询，目前提出的算法主要是基于如下两种思想：第一种是路径分解思想，这种方法将产生大

2、量的不可避免的无用的中间结果。另一种是新近提出的整体小枝(holistictwig)模式查询匹配方法，它把用树结构建模的查询表达式—刊g模式(twigpattern)作为一个整体来处理。这种方法往往与一些特殊的编码和索引技术相结合，避免了大量不必要数据节点的扫描，使得算法的I／O代价、CPU时间复杂度和空间复杂度大大降低，从而提高了查询效率。自从BrunoN等人于2002年提出holistictwig概念以来，研究者们已经提出了一系列twig模式查询匹配算法。其中TJFast算法基于ExtendedDewey编码，只要访问twig模式中的叶子节点的输入集合流就可以有效地处理XML文

3、档查询，是一种效率较好的holistictwig模式查询匹配算法。但是ExtendedDewey编码不支持XML文档的动态更新操作，且TJFast算法设计思想上的缺陷也使得算法执行效率上可以进一步提高。本文在总结和分析了主流的XML文档编码方案的基础上改进了ExtendedDewey编码，使其能有效支持XML文档的动态更新操作。提出了一种新的基于新ExtendedDewey编码的twig模式查询匹配算法—州gMatch算法，进一步提高了twig模式查询匹配算法的效率。该方法分三个步骤来处理一个twig查询模式，大大减少了查询路径匹配操作，提高了查询效率。同时本文还重组了传统的两阶段

4、算法，恰当地选择中间结果的归并时机，获得了较好的内存利用率。多组实验数据对比表明，本文的方法在效率上有较大的提高。关键字；XML文档、twig模式查询匹配、XML编码、Holistictwig算法、ExtendedDewey编码nTitle：ResearchonTwigPatternQueryMatchingAlgorithmforXMLDataMajor：ComputerSoftwareandTheoryName：XinLeiSupervisor：JirongGaoAssociateProfessorAbstractInrecentyears，谢tllthedevelopment

5、ofdatabaseandnetworktechnology，XMLhasbecomethestandardofdatarepresentationandexchangeontheInternet．Withtheever-growingpopularityofXMLtechnology,therearemoreandmoredatawhichemploysXMLasthevectorintheIntemet，SOmanydomesticandforeignscholarspaymoreandmoreattentionstotheXMLdatamanagementandquery．F

6、orthequeryinXMLdocument，thealgorithmwhicharealreadygivenathomeandabroadnowadaysalemainlybasedonthefollowingtwoideals：11lefirstistodecomposethequeryexpressiontoseveralsimplepathsexpression．Tmsmethodcannotavoidlargeamountofuselessintermediateresults．Theothermethodisanewlyproposedholistictwigquer

7、ypatternmatchingapproach，whichprocessesthetwigpattem嬲awhole．Themethodusuallycombines谢thsomespecialencodingandindexingtechnology,avoidslargeamountofunnecessaryscanningofnodes，reducestheI／Ocost、CPUcomplexityandspacecomplexity,improvesthee