论文部分内容阅读
XML作为Web发展所带来的新技术中的代表,已经成为网上数据表示和交换的标准,并逐渐成为了学术界和工业界所关注的焦点。由于XML数据具有不同于传统数据形式的特点,因此,在各种基于XML的应用中,如何有效地查询XML数据已经成为一个重要的研究课题。近年来,小枝模式匹配问题已经被广泛地研究。一个小枝模式查询O在XML文档树T中的匹配,也就是找到这个查询模式Q在T中出现的所有情况。以前的工作比如Holistic Twig和TJFast都是把小枝模式分解成多个从根结点到叶子结点的单个路径,然后把这些路径模式的匹配结果合并起来以得到小枝模式查询Q的匹配结果。它们能够有效地删除不可能的路径模式来避免产生大量的中间结果,但合并这些线性路径会花费很高的计算代价。为了解决这个问题,最近又提出了Twig2Stack和TwigList算法,但它们都需要遍历所有的输入节点,另外,它们也没有考虑有些查询节点是不需要进行处理的。本文对XML路径查询处理中尚存在的难点问题进行了深入的研究,并且在汲取了各种小枝模式匹配算法优点的基础上,提出了一种新的小枝模式匹配算法TwigEN。本文的主要工作如下:(1)研究分析了现有的小枝模式匹配算法,并总结其实现方法;(2)根据XML文档的结构特点提出了一种新的小枝模式匹配算法TwigEN,该算法只处理有解扩展的元素结点,因此,能够较大限度的跳过输入流中无用的元素结点;(3)对算法TwigEN的复杂度和可行性进行了分析,给出了TwigEN算法在最坏情况下的时间和空间复杂度;(4)最后构建一个实验系统,实现了本文提出的小枝模式匹配算法,然后通过实验把TwigEN算法同Twigstack算法和TwigList算法进行了比较,并对实验结果进行了分析。实验证明,本文提出的小枝模式匹配算法的效率有了较大的提高。本文提出的小枝模式匹配算法能够根据XML文档的结构特点跳过那些在结构连接中无用的元素结点,这样不仅减少了待处理结点的数目,缩短了查询处理时间,而且也节省了内存空间。该算法的时间复杂度和空间复杂度与查询结点的标签流中结点总数呈线性关系。