基于小枝模式匹配的XML数据查询处理算法研究

摘要

随着因特网的飞速发展,半结构化式的Web数据大量涌现,使得HTML标记语言已经不能满足用户日益增长的需求,XML作为一种自描述的半结构化数据为Web数据管理提供了新的数据模型,得到了广泛的应用,并已发展成为Internet上数据表示和交换的事实上的标准。但由于XML本身是一种嵌套的树型结构,如何从大量的XML数据源中查找感兴趣的信息成为XML数据库研究领域的一大热点。小枝模式整体匹配是XML查询处理方法中效率较高的一种,近年来相继出现了许多小枝模式整体匹配算法,例如TwigStack、TJFast、TwigList和TwigNM算法等。这些方法对于只包含祖先-后代关系的查询效率很出色,但它们要按序遍历输入数据流中的每一个元素结点,对于那些很显然不会构成匹配的元素结点仍然在扫描和判断范围之内,当要扫描的标签流较长时,需要花很长的时间,而且对于含有父子关系的查询,它们的查询效率并不高。另外,这些算法只能满足无序查询的需求,对于含有有序轴的Xpath表达式查询无法实现。
　　 本文对XML路径查询处理中尚存在的问题进行了深入研究,在汲取了各种小枝模式匹配算法优点的基础上,针对目前算法存在的不足,研究了两种有效的非归并整体匹配算法TwigTL和OrderedTwigPM。主要内容包括：⑴研究一种有效的小枝模式匹配算法TwigTL,该算法使用Tag+Level流模型,并在进行查询处理之前先进行无用数据层的剪枝,以减少待处理结点的数目,缩短处理时间；⑵为了支持有序小枝模式查询,研究一种新的整体匹配算法OrderedTwigPM,支持Xpath表达式中的有序轴,以扩展查询类型；⑶构建实验系统,实现算法TwigTL和OrderedTwigPM,并通过实验结果和同类算法进行比较分析。