一种非归并不确定XML小枝模式查询算法  

Matching Twig Patterns in Uncertain XML without Merging

作　　者：刘立新[1] 张晓琳[1] 吕庆[1] 张换香[1] 褚艳华[1] 

机构地区：[1]内蒙古科技大学信息工程学院,包头014010

出　　处：《计算机科学》2013年第5期198-200,228,共4页Computer Science

基　　金：国家自然科学基金(61163015);内蒙古科技大学创新基金(2011NCL024;2010NC041)资助

摘　　要：针对目前不确定XML小枝模式查询需要存储大量中间结果和归并中间结果的情况,提出一种非归并不确定XML小枝模式查询算法ProTwigList。该算法查询之前通过Tag+Level流进行剪枝,以减少待处理节点的数目;并扩展了区间编码来对剪枝后剩余的普通节点进行编码,用一定规则对分布节点进行标识;查询时采用公共分布节点路径的方法处理分布结点,最后结合最低公共祖先节点的概率计算查询结果的概率值。理论分析和实验结果证明了ProTwigList算法的查询效率。In order to avoid storing large amounts of intermediate results and merging those intermediate results when matching twig patterns in uncertain XML, this paper proposed the algorithm ProTwigList. First, it uses Tag＋ Level stream pruning to reduce the number of nodes to be processed. Second, it extends the range encoding to encode the re- maining ordinary nodes, and adopts rules to mark distributed nodes. Third,it uses the path of common distributed node to deal with distributed nodes. Finally, it utilizes the probability of the lowest common ancestor node to calculate the probability of every result. The theoretical analysis and experimental results prove the efficiency of ProTwigList.

关 键 词：不确定XML P-文档 分布节点 区间编码 小枝模式 

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