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

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