xml树模式查询研究

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

1、同济大学软件学院硕士学位论文XML树模式查询研究姓名：许翼申请学位级别：硕士专业：软件工程指导教师：张苗苗;季向东20081201摘要XML是可扩展标记语言(ExtensibleMarkupLanguage)的简称，为Web上半结构化文档和数据提供了通用格式。随着Internet的发展尤其是Web技术的广泛应用，越来越多的应用采用了XML技术作为信息表示和数据交换的标准，这使得通过数据库技术对XML数据进行存储、查询等操作变得越来越重要。由于XML文档可看作树型，对XML的查询可以看成是基于值谓词的子树

2、Twig匹配，也就是从XML文档找到和给定查询条件相匹配的子树，因此能够高效找到子树匹配成为XML中的一个核心问题。本文在介绍了XML查询的研究现状和研究成果的基础上，针对TwigStack算法在多层嵌套的XML文档下性能不高的情况，提出了改进算法NestTwig，并证明行之有效。NestTwig算法和TwigStack算法都是基于分解一匹配一合并的步骤来进行查询匹配处理，容易产生大量无用的中间结果或者会对一些子模式树进行重复匹配。为了解决这个问题，本文引入自动机思想，对Twig查询自动机与路径模式树的

3、匹配进行了讨论，提出了改进算法PatternMatch。对PatternMatch算法和NestTwig算法进行了实验对比证明基于自动机的方法在性能上具有较大优势。关键词：XML，树模式，XML查询，结构连接，自动机AbstractABSTRACTXML，(ExtensibleMarkupLanguage)providesgeneralformatforsemi。structureddocumentsanddataOiltheWeb，NowadaysXMLplaysmoreandmoreimportan

4、troleinWebbasedapplications．InXML，tagsareusedtodescribethestructureinformationofdocuments．XMLiswidelyusedasastandardlanguageforrepresentingandexchangingdatainWebsiteconstruction，distributedapplicationplatformsandothersystems．Therefore，itbecomesmoreandmor

5、eimportanttomanageXMLdatathroughdatabases．ForXMLqueryCanbeseenasapredicatebasedonthevalueofthesub．treeTwigmatch，thatisfindasub—treefromXMLdocumentswithagivenquery．Sotheabilitytofindasub—treematchingwithhighperformancebecomesanXML∞reissues．Thisarticledesc

6、ribesthestatusofXMLqueryresearch，andpointoutthatTwigStackalgorithmisnothi。ghperformanceforthemulti．nestedXMLdocument．ThengiveanimprovedalgorithmcalledNestTwigtosolvetheproblemandproveditmoreeffective．BothNestTwigandTwigStackalgorithmsfortreepatternmatchi

7、ngaledecomposition‘matching·mergingprocesses，whichmayproducemassiveuselessintermediateresultOrrequirerepeatedmatchingofsomesub-patterns．ThisthesisproposesaflexibleautomationmatchingalgorithmcalledPatternMatchtofindalldistinctmatchingofaquerytreepatterndi

8、rectly．TheexperimentalcontrastsofPatternMatchalgorithmandNestTwigalgorithmprovethattheAutomata-basedapproachintermsofperformancehaveagreateradvantage．KeyWords：XML，TreePattern，XMLQuery,StructuralJoin,AutomationII学位论文版权使用授权书