(1) 根据预计算产生的映射文件，对q进行映射。
(2) 扫描映射后的q，确定q所在的层次。
(3) 打开q所在层次的对应上界文件。
(4) 从目前打开文件的第一条上界开始扫描，判断该上界是否被q所覆盖。如覆盖，则记下该上界的位置，在相应的度量值文件中找到该上界的度量值，返回度量值。如不覆盖，则继续扫描下一条上界，判断是否被q覆盖。
(5) 假如在当前打开的层次文件中扫描不到被q所覆盖的上界，且当前层次已经是第d层，则返回查询不命中。如果当前层次还不是第d层，则打开当前层次的下一层次文件。然后跳转到(4)。
文献[LW05]对于商立方体的查询性能进行了分析。对于查询算法的第(5)步，假如在q所在层次文件扫描不到上界，便需要扫描下一个层次，当每个层次的数据量都很大的时候，这种查询不命中就会产生额外的开销，使得查询程序性能下降得很厉害，而对于数据立方体类似的顺序查询则不会造这种额外层次扫描的开销。
4.4 小结目前基于数据立方体元组间关系的压缩技术分成了两类，一类是以原有立方体存储结构为基础，如精简立方体；另一类则是通过分析立方体元组间的逻辑关系，构造出新的立方体存储结构，如Dwarf和商立方体。
商立方体的主要思想是把数据立方体中覆盖相等的单元全部分成一类，使得只需保存这个类的上界便可保留数据立方体的信息，这样便达到了压缩数据立方体的目的。
第五章 并行化算法的设计
本章将描述本文提出的基于数据分组方法的并行预计算，以及在该预计算方法产生的商立方体数据上，并行地进行查询的方法，并对这种做法的正确性进行初步的分析。
5.1 基于数据分组的预计算基于数据分组的预计算方法的主要思想是数据的分布性。并行预计算程序使用主从模式进行编程。主要的处理步骤如下所示：
(1) 基表由主进程读入，主进程一边读入基表元组，一边完成对各维数据的映射处理，映射关系文件存储在主进程所运行的机器上。
(2) 当主进程载入内存的数据元组条数到达一定数量时（由用户决定），主进程将这部分数据发送给相应的从进程，从进程在接收数据完毕之后，立即开始对所接收到数据进行商立方体预计算。主进程在将分配给某个从进程的数据发送完毕后，继续将基表中的数据载入内存，直到所有元组都被载入和所有的从进程都接收好数据以后，主进程开始对留在本地内存中，没有分派给任何从进程的元组数据进行预计算。
(3) 每个进程都独立地进行预计算工作，它们预计算所产生的商立方体上界分层地存储在进程运行机器的本地磁盘中。
(4) 所有进程都完成预计算后，并行程序退出。
主进程数据分发示意图如图5.1所示。
SHAPE \* MERGEFORMAT
图5.1 数据分发示意图
5.2 在立方体分布式存储情况下的并行查询上一小节所描述的预计算算法，在完成预计算之后，将会把商立方体数据分布式地存储在各台机器的本地磁盘中。对于这种情况，应该要并行地对各个独立存储的立方体进行查询，并且最终各个查询结果要经过汇总处理后才能得到与串行查询程序一样的查询结果。本文提出的在立方体分布式存储情况下的并行查询也是基于MPI，以主从模式为实现方式，基本步骤如下：
(1) 主进程读入多条查询语句，并根据主进程本地存储的映射关系文件对查询语句进行映射，映射后的查询语句都存放在主进程的内存中。
(2) 主进程将所有的查询语句广播给各个从进程后，主进程开始进行查询。从进程在接受完查询语句后，也开始对本地的立方体数据进行查询。
(3) 每条查询语句都会返回一个结果，各个进程将这些查询结果存放在一个大小为查询语句条数的数组中。在所有查询都完成查询后，主进程开始接收来自各从进程的查询结果，从进程则开始向主进程发回它们的查询结果。
(4) 主进程在接收完各从进程的查询结果后，将所有查询结果整合在一起，便得到最终的查询结果。
5.3 正确性分析本节将用来说明在5.1和5.2节中所提出的基于数据分组的并行预计算和查询方法的正确性。主要说明在立方体数据分布式存储情况下，并行查询程序得到的结果，与在立方体数据集中式存储情况下的串行查询程序所得到的结果是相等价的。
对于查询语句q，它的查询结果R(q)是决定于q的覆盖集Cov(q)的。假设基表为B，有m条元组，q在B上的覆盖集为Cov(q)。
随机地将B中的元组分为2部分，分别为B′和B′′。由于是以元组为单位划分，同一条元组不可能同时出现在两部分中，q在B′、B′′上的覆盖集分别为Cov′(q)、Cov′′(q)。可知：
设a机的输入基表是B′，b机的输入是B′′。在预计算完成后，分别生成立方体QC(B′)和QC(B′′)。在并行查询中，分别使用q对QC(B′)和QC(B′′)进行查询。假设查询命中的上界分别是u′和u′′。根据本文4.3节中提到的查询算法的原理，可知：
在QC(B′
