Xtwig连接:基于流的对无根树查询模式的高效处理

为了提高对XML文档的查询能力,提出了一种Xtwig查询模式. Xtwig模式可以被表达成无根标签树,它在选择谓词中包含反向轴,可以从当前节点向后和向前查找指定的模式.现在已有很多处理Twig模式查询的经典算法,然而这些算法只能处理只包含前向轴的查询模式;许多重写规则也被提出来将带反向轴的XPath定位路径转化为等价的只包含前向轴的定位路径,但是转化后的定位路径在执行时是非常低效的.提出了一个高效算法XtwigStack来处理同时具有正向轴和反向轴的查询模式.实验结果表明,算法是有效的、高效的,它避免了大量无用中间结果,其执行效率不受反向轴个数影响.