-
题名基于F&B索引的XML查询处理算法
被引量:2
- 1
-
-
作者
王洪强
李建中
王宏志
-
机构
哈尔滨工业大学计算机学院
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2010年第5期866-877,共12页
-
基金
国家自然科学基金项目(60473075)
黑龙江省自然科学基金项目(zjg03-05)
-
文摘
XML已成为信息交换和表示的标准.对XML数据的查询将返回满足特定约束的XML节点子集.对于大文件的XML数据的查询处理通常分为两步:1.为该XML数据建立一个索引;2.在索引上完成查询处理无需访问源文档.XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.提出了一种素数序列标记法,这种标记法不仅有助于快速地建立F&B索引,更可以高效地完成F&B索引上的查询处理.此外,还给出了F&B索引上的区间标记法与CCPI的创建过程,这两种编码创建过程无需在建立F&B索引后二次创建,仅需与F&B索引创建过程一起对文档使用SAX解析器分析一次即可得到.这样,可以在F&B索引的区间标记法上使用TwigStack算法执行查询处理,在F&B索引的CCPI标记法上使用关联路径连接算法执行查询处理.还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效地判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和TwigStack算法.
-
关键词
XML
索引
F&B索引
素数序列标记法
CCPI
twigstack
-
Keywords
XML
index
F&B-index
prime sequence labeling
CCPI
twigstack
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-