###
DOI:
Journal of Software:2009.20(7):1812-1824

一种支持高效XML 路径查询的自适应结构索引
张博,耿志华,周傲英
(复旦大学 计算机科学与工程系,上海 200433;复旦大学 计算机科学与工程系,上海 200433;华东师范大学 海量计算研究所,上海 200062)
Adaptive Structural Index for Efficient Processing of XML Path Queries
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3222   Download 4449
Received:November 15, 2007    Revised:March 14, 2008
> 中文摘要: 提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index 建立在F&B-Index 的基础之上,其索引结构包括F&B-Index,Query-Table 和Part-Table.Query-Table 能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table 的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table 用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML 元素节点,调整过程往往需要遍历整个文档.而AS-Index 是基于F&B-Index 节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index 在查询和调整性能上优于现有的XML 结构索引.同时,相比于现有的自适应结构索引,AS-Index 针对大规模文档具有更加优良的可扩展性.
中文关键词: XML  自适应索引  结构索引  查询处理
Abstract:This paper proposes an adaptive structural index: AS-Index (adaptive structural index), which can avoid the problem of the existing indexes. AS-Index is based on F&B-Index. It consists of F&B-Index, Query-Table and Part-Table. Frequent queries are kept in Query-Table avoiding redundant operations in query processing. Based on Query-Table an efficient bottom-up query processing is also proposed for answering infrequent queries using the frequent queries in Query-Table. Part-Table is used for optimizing the queries with descendant edges. The existing adaptive structural indexes need to traverse the whole document for adaptation, and their adaptation granularity is XML element node. For AS-Index, the adaptation granularity is F&B-Index node which includes a set of XML element nodes, and its adaptation is an efficient and incremental process that supports branch queries. The experimental results demonstrate that this index significantly outperforms the previous structural indexes in terms of query processing and adaptation efficiencies. For large XML documents, compared with the existing adaptive structural indexes, AS-Index is more scalable
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60673137 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z103 (国家高技术研究发展计划(863)) Supported by the National Natural Science Foundation of China under Grant No.60673137 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z103 (国家高技术研究发展计划(863))
Foundation items:
Reference text:

张 博,耿志华,周傲英.一种支持高效XML 路径查询的自适应结构索引.软件学报,2009,20(7):1812-1824

.Adaptive Structural Index for Efficient Processing of XML Path Queries.Journal of Software,2009,20(7):1812-1824