Abstract: How to quickly locate the interested information in the XML database under a certain twig pattern is a popular research topic. To solve the problem that the TwigStack algorithm for handling the case with parent-child nodes would come out with massive intermediate results, an improved twig pattern query algorithm of cTwigStack was proposed, which was based on caching the non-leaf nodes and delaying the leaf nodes output. The experimental results on Treebank dataset indicate that the proposed algorithm can achieve the most accurate results of the queries that contain the ancestor-descendant relationships below branching nodes. Besides, compared with the present algorithm, it is also highly effective when processing parent-child relationships below branching nodes.

Key words: twig pattern matching, XML database, XML pattern matching, XML document, XPath

摘要： 给定一个小枝模式查询,如何快速地在XML数据集中找到所有感兴趣的信息,已成为当前研究的热点。针对TwigStack算法在处理含有父子节点的情况下会产生大量的中间结果等问题,通过栈来对非叶子节点缓存和对叶子节点延迟输出的思想,提出了一种改进的小枝模式匹配算法——cTwigStack。采用Treebank数据集进行测验,结果表明该算法不仅仅在处理祖孙/后继节点时能使输出结果的准确性达到最优,而且在处理父子节点时,相对目前提出的算法,也是非常高效的。

关键词: 小枝模式匹配, XML数据库, XML模式匹配, XML文档, XPath