一种采用扩展Dewey编码非归并的小枝模式查询算法  

Extended Dewey Encoding Algorithm of Twig Pattern Query Without Merging

作　　者：赵圣猛[1] 赵雷[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《小型微型计算机系统》2011年第5期837-839,共3页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61073061)资助

摘　　要：小枝模式查询是XML查询中重要的操作,已经有许多种算法提出,如TwigStack和TJFast算法等,但是他们都是基于归并思想的,不能避免大量的不必要的路径归并.本文提出的TwigWM(Twig Without Merging)算法使用部分栈与链表的结构来实现非归并查询,由于从扩展Dewey编码中能够直接得到祖先元素结点的编码,所以TwigWM算法采用扩展Dewey编码.实验结果表明,TwigWM算法要优于TJFast、Twig2Stack等算法.Finding all the occurrences of a twig pattern in an XML document is important to the operation of XML query.Many algorithms such as TwigStack and TJFast were proposed in the past.However,they are all based on merging,without avoiding a large number of unnecessary path merging.TwigWM（Twig Without Merging） algorithm with extended Dewey code is proposed in this paper,which uses part of the stack and list structure to realize the non-merged query.Experimental results have showed that TwigWM is better than TJFast,Twig2Stack etc.

关 键 词：XML 查询 小枝模式 归并 扩展Dewey 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]