基于素数序列标记法的XML查询处理算法  

Query processing based on prime sequence labeling

作　　者：王洪强[1] 李建中[1] 王宏志[1] 

机构地区：[1]哈尔滨工业大学计算机学院,哈尔滨150080

出　　处：《哈尔滨商业大学学报（自然科学版）》2009年第5期540-545,552,共7页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：国家自然科学基金项目(60473075);黑龙江省自然科学基金项目(zjg03-05)

摘　　要：XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询的最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.本文提出了一种素数序列标记法,这种标记法不仅有助于快速的建立F&B索引,更可以高效的完成F&B索引上的查询处理.此外,我们还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效的判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和Tw igStack算法.XML Index provides high efficiency for XML query processing. F＆B - Index is the smallest index that supports twig query processing. However, few researches are pro- posed on how efficiently create F＆B -Index and how to process queries based on F＆B -Index. This paper proposes a new labeling scheme called prime sequence. This labeling scheme helps not only on creating an F＆B - Index but also on efficient query processing. With prime sequence labeling, creates an F＆B -Index by parsing the XML document only once with a SAX parser, further, proposes an efficient algorithm named division match over F＆B -Index, the algorithm can efficiently judge relationship between two nodes based on a property of prime sequence labeling. Experiments show that prime sequence labeling provides high efficiency on creating F＆B- Index and high efficiency on query processing on different datasets.

关 键 词：XML 索引 F&B索引 素数序列标记法 

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