同理：在QC(B′′)中，
则有：
串行查询结果R(q)决定于Cov(q)所包含的元组信息。在并行查询中，程序可以分别得到Cov(u′)和Cov(u′′)的信息，而Cov(u′)与Cov(u′′)包含了Cov(q)中包含的所有的元组信息，因此，并行查询是可以得到与串行查询相等价的查询结果的。
5.4 小结本章概括性地描述了基于数据分组的并行预计算和并行查询方法的实现过程，并对于这种方法的正确性进行了初步的分析。在接下来的章节中，将会详细地描述基于这种方法的并行程序的实现和使用实验数据来更进一步地表明该方法的正确性和有效性。
第六章 并行化算法的实现 6.1 串行预计算程序结构
在串行预计算程序中，一共有Cubing、DFHandle、QuotientCube和TupleHandle4个类，其中DFHandle和TupleHandle两个类是辅助功能类。它们的类图如图6.1所示。DFHandle的主要功能是打开关闭数据文件，将数据文件中的元组一条一条地读进来，然后将该条元组交给TupleHandle处理，TupleHandle将元组的各维数据分割开来，每次处理一维，并将该维数据存在程序指定的一个内存区域中。关于Cubing类和QuotientCube类的详细介绍，将在以下的章节中给出。
图6.1 DFHandle类和TupleHandle类
6.1.1 Cubing类Cubing类的类图如图6.2所示，其中loadData()的作用是使用DFHandle类，打开指定的数据文件，将元组读出之后，使用TupleHandle来将各个维度和度量值的数据拆分开来，然后对所有的维度做映射操作，写入映射文件，同时将映射后的维度数据存在data这个二维数组里，度量值存在msrdata中，直到把所有数据文件都读入data和msrdata中。在读数据之前，loadData还会先统计基表中有多少条元组，元组有多少维和多少个度量值，某度量值上的聚集操作分别是哪种，这些数据分别存在tuplesNum，dimsNum，msrsNum和aggFunOrder中。
avgFun()、maxFun()、minFun()、sumFun()和countFun()里面分别是平均、最大值、最小值、和、计数等聚集操作的实现。
图6.2 Cubing类
Cubing类的工作主要是完成预计算真正开始之前的准备工作，把所有数据都读入内存之后，QuotientCube类便可以使用这些数据来进行预计算工作。Cubing类的preCompute()函数是一个虚函数，它的具体实现在QuotientCube中。QuotientCube类是Cubing类的一个子类。
6.1.2 QuotientCube类QuotientCube类public继承于Cubing。它的类图如图6.3所示。通过调用preCompute()开始预计算工作。
图6.3 QuotientCube类
程序首先会创建dimsNum+1个aggDimDataX文件，用来存放不同层次的上界，同时也创建同样多个的aggMsrDataX文件，用来存放相对应的度量值。data[0]中存放Cubing从数据文件读出的data内容，同样msrData[0]中存放相应的度量值，data[1]和msrdata[1]中将存放的是将data[0]、msrdata[0]里数据排序后的结果，用来排序的算法在Partition()中实现。
preCompute()接下来便会调用DFS()开始计算上界并将上界与其所对应的度量值写入相应层次的文件中。DFS()的具体算法详见本文4.2节。
预计算程序的数据流图如图6.4所示。
图6.4 串行预计算程序中的数据流
6.2 预计算并行化并行预计算程序中，在串行程序的基础上增加了两个类：分别是DispatchManager类和DispatchWorker类。顾名思义，DispatchManager类中的方法是为主从模式中的主进程所调用，DispatchWorker类中的方法是在从进程中调用。根据本文5.1节中的描述，DispatchManger类主要的工作是完成数据读入、映射和数据分发工作。DispatchWorker的工作是接收主进程发送过来的数据。
6.2.1 DispatchManager类和DispatchWorker类DispatchManager类和DispatchWorker类的类图如图6.5所示。数据的读入工作将由Cubing类转移到DispatchManager类中，但由于从进程无法接触到文件信息，因此，主进程必须将与数据文件相关的数据预先得出并发送给每个从进程。DispatchManager在初始化时便会调用getDataFileNum()和getConfig()。
getDataFileNum函数使用DFHandle和TupleHandle来完成工作。首先打开数据文件，将第一行读出。数据文件的第一行是用来写明基表有多少个维度和度量值，每个维度和度量值的名称分别是什么。getDataFileNum里会根据里面的信息分辨出哪些是维度数据，哪些是度量值，分别有多少个，度量值以何种方式进行聚集操作等，然后把这些数据保存下来。最后是统计整个数据文件有多少条元组。这些操作基本和Cubing::loadData中前面部分的操作相同。
图6.5 DispatchManager和DispatchWorker类图
getConfig函数的作用是将保存着各个进程数据分配比例的配置文件内容读出，并根据getDataFileNum中得到的元组条数，计算出每个进程应当接收的元组条数。计算完之后，将这些信息保存在pConfig中。
接下来，DispatchManager便会将pConfig里的数据连同度量值
