区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.

Range query is a very important operation to support On-Line Analytical Processing (OLAP) in data warehouses. Although several cube storage structures for range sum queries and dynamic updates have been introduced recently. However, the complexities of both space and time are too higher to realistic. To solve this problem, a hierarchical data cube (HDC) and corresponding algorithms are provided in this paper. Both of the range query and update costs of HDC are O(log^dn), and the overall cost is O((logn)^2d) (under the C_qC_u model) or O(K(logn)^d) (under the C_qn_q+C_un_u model). The analytical and experimental results show that the costs of HDCs range queries, dynamic updates, storage space and the overall performance of HDC are superior to other cubage storage structures.

Supported by the National Natural Science Foundation of China under Grant No.60273082 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA415410 (国家高技术研究发展计划(863)); the National Grand Fundamental Research 973 Program of China under Grant No.G1999032704 (国家重点基础研究发展规划(973)); the Natural Science Foundation of Heilongjiang Province of China under Grant No.F0208 (黑龙江省自然科学基金)