摘要: 区域查询是数据仓库支持多维OLAP分析的一类重要查询。它在多维数据集合的多维空间中某一指定子空间范围内对度量属性执行聚集操作(如sum等)。设计有效的多维数据集合的辅助存储结构，有效地支持OLAP区域查询处理，已经成为数据仓库领域的关键问题之一。由于多维数据集合的存储结构应该同时支持高效率的数据查询和数据更新，因此，评价一个多维数据集合存储结构的性能不能单纯地考察区域查询代价或数据更新代价，需要综合考虑两者的性能。文献3利用前缀和技术提出了单机环境下多维数据集合的辅助存储结构Prefix Cube（简称PC）。PC方法虽然提供O(2d)的区域查询处理复杂性，但却带来了严重的数据维护代价，最坏情况下，数据维护复杂性为O(nd)，其中nd为多维数据集合空间的大小。目前许多实际应用环境要求对多维数据集合中的数据不断进行动态维护。在这种环境下，数据维护的时间开销与区域查询的时间开销同样重要。为了进一步降低区域查询处理的综合代价，研究者们在基于单机处理环境的区域查询方面开展了很多的研究工作。随着数据仓库中数据量的急剧增长，高于1012字节的海量数据仓库已经随处可见。而现有的技术和方法难以有效地应用于海量数据仓库。研究海量数据上的区域查询与数据更新就成为海量数据仓库面临的一个挑战性问题。并行计算技术是提高数据仓库性能的一个重要途径和手段。近几年来，人们逐渐认识到并行计算在解决海量数据仓库问题的重要性，并开展了研究工作。问题是，大部分研究工作是基于SN或SD并行计算结构，并且据我们所知，到目前为止，还没有文章讨论支持OLAP区域查询的多维数据集合的并行辅助存储结构以及相应的海量数据上的并行区域查询与动态更新问题。本文研究了并行计算环境下，特别是基于SN结构的并行计算环境下，海量cube上的区域查询与动态更新处理技术。提出了一个基于机群并行计算系统的并行cube存储结构，简称PHC，可以有效地支持cube上的区域查询与动态更新。本文所提出的PHC是第一个在并行环境下处理区域查询的并行辅助存储结构。同时，本文还给出了基于PHC存储结构的并行区域查询和动态更新算法，这两个算法的时间复杂性均均为O(logdn/P)。理论分析与试验结果表明，本文提出的PHC以及相关的并行算法具有很高的性能，PHC不仅具有最小的空间代价，而且PHC上的并行区域查询和动态更新均可达到较高的性能加速比。当处理结点数P=1（即单处理机系统）时，本文提出的方法在时间复杂性空间复杂性两个方面都远优于目前所有同类方法。