基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預(yù)計(jì)算和查詢（二）

圖5.1

數(shù)據(jù)分發(fā)示意圖5.2在立方體分布式存儲(chǔ)情況下的并行查詢

上一小節(jié)所描述的預(yù)計(jì)算算法，在完成預(yù)計(jì)算之后，將會(huì)把商立方體數(shù)據(jù)分布式地存儲(chǔ)在各臺(tái)機(jī)器的本地磁盤中。對(duì)于這種情況，應(yīng)該要并行地對(duì)各個(gè)獨(dú)立存儲(chǔ)的立方體進(jìn)行查詢，并且最終各個(gè)查詢結(jié)果要經(jīng)過匯總處理后才能得到與串行查詢程序一樣的查詢結(jié)果。本文提出的在立方體分布式存儲(chǔ)情況下的并行查詢也是基于MPI，以主從模式為實(shí)現(xiàn)方式，基本步驟如下：(1)主進(jìn)程讀入多條查詢語句，并根據(jù)主進(jìn)程本地存儲(chǔ)的映射關(guān)系文件對(duì)查詢語句進(jìn)行映射，映射后的查詢語句都存放在主進(jìn)程的內(nèi)存中。(2)主進(jìn)程將所有的查詢語句廣播給各個(gè)從進(jìn)程后，主進(jìn)程開始進(jìn)行查詢。從進(jìn)程在接受完查詢語句后，也開始對(duì)本地的立方體數(shù)據(jù)進(jìn)行查詢。(3)每條查詢語句都會(huì)返回一個(gè)結(jié)果，各個(gè)進(jìn)程將這些查詢結(jié)果存放在一個(gè)大小為查詢語句條數(shù)的數(shù)組中。在所有查詢都完成查詢后，主進(jìn)程開始接收來自各從進(jìn)程的查詢結(jié)果，從進(jìn)程則開始向主進(jìn)程發(fā)回它們的查詢結(jié)果。(4)主進(jìn)程在接收完各從進(jìn)程的查詢結(jié)果后，將所有查詢結(jié)果整合在一起，便得到最終的查詢結(jié)果。5.3正確性分析

本節(jié)將用來說明在5.1和5.2節(jié)中所提出的基于數(shù)據(jù)分組的并行預(yù)計(jì)算和查詢方法的正確性。主要說明在立方體數(shù)據(jù)分布式存儲(chǔ)情況下，并行查詢程序得到的結(jié)果，與在立方體數(shù)據(jù)集中式存儲(chǔ)情況下的串行查詢程序所得到的結(jié)果是相等價(jià)的。對(duì)于查詢語句q，它的查詢結(jié)果R(q)是決定于q的覆蓋集Cov(q)的。假設(shè)基表為B，有m條元組，q在B上的覆蓋集為Cov(q)。隨機(jī)地將B中的元組分為2部分，分別為B′和B′′。由于是以元組為單位劃分，同一條元組不可能同時(shí)出現(xiàn)在兩部分中，q在B′、B′′上的覆蓋集分別為Cov′(q)、Cov′′(q)?？芍涸O(shè)a機(jī)的輸入基表是B′，b機(jī)的輸入是B′′。在預(yù)計(jì)算完成后，分別生成立方體QC(B′)和QC(B′′)。在并行查詢中，分別使用q對(duì)QC(B′)和QC(B′′)進(jìn)行查詢。假設(shè)查詢命中的上界分別是u′和u′′。根據(jù)本文4.3節(jié)中提到的查詢算法的原理，可知：在QC(B′)中，u′與q被劃分到同一類中，且u′是該類的上界，則u′和q是覆蓋相等的，有：同理：在QC(B′′)中，則有：串行查詢結(jié)果R(q)決定于Cov(q)所包含的元組信息。在并行查詢中，程序可以分別得到Cov(u′)和Cov(u′′)的信息，而Cov(u′)與Cov(u′′)包含了Cov(q)中包含的所有的元組信息，因此，并行查詢是可以得到與串行查詢相等價(jià)的查詢結(jié)果的。5.4小結(jié)本章概括性地描述了基于數(shù)據(jù)分組的并行預(yù)計(jì)算和并行查詢方法的實(shí)現(xiàn)過程，并對(duì)于這種方法的正確性進(jìn)行了初步