论文部分内容阅读
当前,XML(可扩展标识语言)已经成为万维网的数据表示和数据交换的标准。随着XML数据越来越多,针对XML数据的查询与处理引起了越来越多的关注。近来,大量基于将XML文档视作树形模型的XML查询算法被相继提出。然而,XML文档的半结构化性质和用户查询需求的日益复杂性又给XML数据的高效处理带来了如下新的挑战:(1) XML查询算法的输入集规模和执行时间将随着XML文档规模的增长而迅速增加;(2)由于XML的不规则性,算法返回的结果可能包含重复元素,需要后序的处理工作。因此,如何高效准确地查询大量的XML数据成为目前值得研究的一个重要课题。本文在返回结果为匹配枝和返回结果为无冗余的目标数据元素两种情况下分别提出了高效且可扩展的XML枝匹配算法Twig3Version和高效的AdvancedTwigVersion算法,针对其关键技术展开了研究,主要研究内容和特色如下:(1)在返回结果是所有匹配枝的情况下,提出了一种将已有的在原文档上的XML枝匹配算法应用于一个压缩的索引结构(版本树)的思想,并提出了简单高效的版本过滤模块和归并连接模块。在精简的版本树上执行结构匹配以及在精简的中间结果上执行版本过滤和归并连接大大提高了查询算法的性能。(2)在返回结果是无冗余的目标数据元素的情况下,AdvancedTwigVersion算法对TwigVersion算法进行了改进。通过尽可能多地利用祖先元素的标签信息,可以尽可能早地过滤掉不匹配的元素,加速了匹配的过程。另外,通过一系列的实验将其性能与一些代表性的XML查询算法在返回无冗余结果时的性能进行了比较。本文提供了理论证明和大量基于真实数据的实验结果,证实了Twig3Version算法在返回整个匹配枝和AdvancedTwigVersion算法在返回无冗余的目标数据元素的情况下均表现出了较好的性能。随着互联网的发展和时代的进步,针对XML的查询将会有更大的发展空间和更广泛的应用前景。