硕士论文-XML复杂路径表达式查询处理技术研究.pdf

东北大学

硕士学位论文

XML复杂路径表达式查询处理技术研究

姓名：周博

申请学位级别：硕士

专业：计算机软件与理论

指导教师：于戈

20031201
龇复杂路径表达式查淘处理技术研究摘要查!坠!翌主兰堡垒墨塑墨XML是可扩展标记语言(Extensible特定的意义，可以创建出其它的标记语言。随着Interact的发展尤其是Web技术的广泛应用，越来越多的应用采用了XML技术作为信息表示和数据交换的标准，这使得通过数据库技术对XML数据进行存储、查询等操作变得越来越重要。提出的大多数查询方法都是在实例空间中进行的，也就是说，使用这些方法查询时，直接面对的操作对象是XML文档。这类方法中比较有代表性的是XML文档树遍历的方法和包含连接的方法。根据自动机技术，我们提出了一种通过用查询自动机匹配XML模式树来计算查询路径表达式的方法，称为自动机匹配算法动机匹配算法可以在模式空间内高效地计算路径表达式，因此这种方法可以适应在海量数据上执行复杂查询的需要。本文提出了如何将具有各种运算符的正则表达式转化为查询自动机的方法。针对XPath规范中规定的“／／”操作符，即祖先一后代关系操作符，我们提出了一Automata)的数据结构，模式自动机可以接收所有可能的路径模式：而传统的自动机要想支持包含连接这一类非正则运算符是非常困难的。为了进一步提高模式自动机的性能，本文还提出了两种优化方法PSA和RWS。前者将模式自动机作为索引的一部分存储在磁盘上，避免了每次计算都要生成模机中多余的状态和转换函数来达到提高查询效率的目的。为了支持自动机匹配算法，本文还提出了高效地支持自动机匹配算法的数据结构：路径模式树和路径实例树。通过与结构连接算法进行性能测试对比，我们发现自动机匹配算法的效率远远高于结构连接算法，PSA和RWS对自动机匹配算法的优化也很显著。到满足某些特定模式的节点。近来，在简单路径查询的问题得到较好解决的基础上，人们将注意力转移到Twig查询中来。本文提出了如何利用索引技术来更好地解决Twig查询的问题。根据路径模式树索引，我们给出了利用自动机匹配路径模式树索引解决这一问题的方法，围绕这一方法，本文对Twig查询自动机的构建，Language)的简称，它为Web}j半结构化文档和数据提供了通用格式。XML是一种元语言，通过对一组标签设定在众多XML查询语言中，路径查询是最重要、使用最频繁的组成部分。目前Match，AM)，来解决XML正则路径和复杂路径查询表达式的策略。自个称为模式自动机(Schema出现在XML文档中的片断，也就是说，它可以匹配任何可能出现在XML文档中式自动机的开销，后者则是通过following集合和preceding集合来过滤掉模式自动与传统的关系数据库中的查询不同，针对半结构化数据的查询更多的是要找(AutomataMarkup·Il·_—--___——’——————’—●————______—_-_—_●__-_—●_——-——————’●—__-_____●—_———-__-_-______-———————————、
Twig查询自动机与路径模式树的匹配等算法进行了讨论，并与用传统的结构连接方法解决Twig查询进行了实验对比，结果证明，基于自动机的方法在性能上具有较大优势。关键词：可扩展标记语言，自动机，模式自动机，路径表达式查询，Twig查询东北大学硕士学位论文摘要·III·
AbstractQueryXMLStudyProcessingTechniquesofjdimcultefficiency·Ⅳ·ComplexPathExpressionsMatchingRWA．Forjoin，andWebdocuments．XMLtime．WithRWA，we东北大学硕士学位论文XMI。(ExtensibleMarkupLanguage)providesWeb．ItXML，languages．MostfAMlAMRWSformoreinformationsmethodscomputeautomataschemacomputationcomplexcontainmentimproveoptimizationmatchalgorithmformatsemistructureddocumentsandsimpleflexibleoriginallydesignedelectronicpublishing．Nowadays，importantroleinbasedapplications．Inuseddescribetheiswidelystandardlanguagerepresentingexchangingdatasiteconstruction，distributedapplicationplat