-
题名一种高效非归并的XML小枝模式匹配算法
被引量:9
- 1
-
-
作者
陶世群
富丽贞
-
机构
山西大学计算机与信息技术学院
-
出处
《软件学报》
EI
CSCD
北大核心
2009年第4期795-803,共9页
-
基金
国家自然科学基金No.70471003
高等学校博士学科点专项科研基金No.20050108004~~
-
文摘
在XML数据库中,小枝模式查询是XML查询处理的核心操作.近几年,研究人员已提出许多种算法,如Holistic Twig和TJFast算法等.然而它们都是基于归并的,会有很高的计算代价.已提出的Twig2Stack和TwigList算法虽然可以克服这一点,但算法非常复杂.针对这一问题,尤其是考虑了通常查询表达式中只有少数几个结点是最终的输出结点这一特点,提出了TiwgNM算法及其扩展算法TiwgNME算法.算法不需要归并,且只用了少数栈来实现.实验结果表明,这些算法优于以前算法,尤其是对查询中只有祖先-后裔关系的表达式更有效.
-
关键词
小枝模式匹配
归并
主路径
主结点
谓词结点
-
Keywords
twig pattern matching
merging
main path
main node
predicate node
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-