一种高效非归并的XML小枝模式匹配算法

富丽贞陶世群

山西大学;

摘要：

在XML数据库中,小枝模式查询是XML查询处理的核心操作.近几年,研究人员已提出许多种算法,如Holistic Twig和TJFast算法等.然而它们都是基于归并的,会有很高的计算代价.已提出的Twig2Stack和TwigList算法虽然可以克服这一点,但算法非常复杂.针对这一问题,尤其是考虑了通常查询表达式中只有少数几个结点是最终的输出结点这一特点,提出了TiwgNM算法及其扩展算法TiwgNME算法.算法不需要归并,且只用了少数栈来实现.实验结果表明,这些算法优于以前算法,尤其是对查询中只有祖先.后裔关系的表达式更有效.

关键词：小枝模式匹配、归并、主路径、主结点、谓词结点

所属期刊栏目：20

分类号：TP301(计算技术、计算机技术)

资助基金：the National Natural Science Foundation of China under Grant No.70471003;the Research Foundation for the Doctoral Program of the Ministry of Eduction of China under Grant No.20050108004

在线出版日期：2009-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：795-803