论文部分内容阅读
随着Internet和Web技术的迅猛发展,XML已经逐渐成为了数据表达和交换的主要标准和载体。日益增长的XML数据对已有的数据管理技术提出了新的要求,如何有效地对XML数据进行管理和查询已经成为了目前数据库领域的研究重点。本文工作围绕XML数据的树模式匹配进行,它可被看作是多步的结构连接,但这些连接操作被当成一个整体进行处理,避免了大量的无关结点参与运算,从而提高了查询效率。树模式匹配可作为XQuery查询的一个操作符,并且已经被普遍认为是XML查询的核心操作。目前在该方面已经提出了一系列有效的实现方法,早期的工作多是按两个阶段执行,首先将查询分解为多条从根到叶结点的子路径,通过索引或者其他过滤算法获取匹配的局部结果,然后再对这些结果进行归并。这种方式在查询包含父子关系时可能会产生不能构造最终输出的中间结果,同时路径归并会花费较多的时间开销。之后提出的算法,其设计思路大多是为了尽量减少执行过程中产生的无关结果,同时避免归并操作,但是它们采用的数据结构较为复杂,实现起来代价较高,特别的,最坏情况下可能要在内存构建整棵文档树。本文在研究已有树模式匹配算法的基础上,提出了新的解决方法。本文的主要工作如下：(1)研究分析了现有的树模式匹配算法,并总结其实现方法;(2)基于路径索引,同时考虑到查询通常只需要获取某几个结点的匹配结果,提出了针对输出结点的TwigFilter算法,算法过程根据要处理的输出结点进行,这样减少了参与运算的无关结点的数量,节省了相应的I／0和匹配开销,之后和TJFast算法的实验比较验证了TwigFilter算法的有效性；(3)对TwigFilter算法进行改进,考虑在DTD下的查询预处理问题,提出了改进后的patternFilter算法,同时考虑了处理多输出结点的情况,并且优化了算法的执行顺序,最后通过把patternFilter算法与TwigStack、TJFast和TwigFilter算法进行实验对比,进一步验证了改进算法的有效性。