路鈺瑩，高茂庭

（上海海事大學信息工程學院，上海 201306）

0 引言

隨著大數(shù)據(jù)時代的到來，越來越多的企業(yè)對于企業(yè)智能決策提出了更高的需求，數(shù)據(jù)倉庫與聯(lián)機分析處理成為企業(yè)的重點發(fā)展方向。而隨著企業(yè)的不斷發(fā)展，積累下的歷史數(shù)據(jù)越來越多，一些大型數(shù)據(jù)倉庫可能達到TB、PB甚至更高的級別。對于海量數(shù)據(jù)，如何存儲以及合理運用成為一大難題。近年來，針對數(shù)據(jù)倉庫存儲壓縮等方法層出不窮，聯(lián)機分析處理針對數(shù)據(jù)倉庫在商業(yè)智能領域的決策方法也被廣泛使用。

OLAP是數(shù)據(jù)倉庫和決策支持系統(tǒng)中的一項關鍵技術。OLAP支持終端用戶對數(shù)據(jù)進行動態(tài)多維分析，OLAP分析的過程是：首先，根據(jù)數(shù)據(jù)分析的需求，在原始數(shù)據(jù)中選取需要的維度屬性，從而生成許多數(shù)據(jù)立方體。然后對立方體執(zhí)行相關操作。最后，將運算結果返回給用戶。因此，整個查詢過程是對數(shù)據(jù)立方體執(zhí)行某種操作，對于立方體的優(yōu)化以及壓縮成為了這個領域里更受關注的問題。

數(shù)據(jù)立方體的計算是數(shù)據(jù)倉庫實現(xiàn)過程的基礎。數(shù)據(jù)立方體的預計算可以減少查詢響應時間，提高聯(lián)機分析處理的性能。Gray等人提出了2D算法[1]通過對事實表執(zhí)行GROUP-BY語句，直接創(chuàng)建數(shù)據(jù)立方體。但是由于空間以及時間復雜度，2D算法的效率并不高。盡管如此，2D算法仍然被認為是數(shù)據(jù)立方體結構的引入算法。Kotsis等人提出的BUC算法[2]基于稀疏的冰山立方體（Iceberg-Cube），計算基于一些預先設定的最小支持度閾值的聚集值。此算法采用自下而上的搜索策略，從粗粒度立方體開始，遞歸劃分共享順序，細化粒度。Kotsis等人提出了Key算法[3]，忽略包含“完全冗余元組”的結點，從而達到節(jié)約了85%存儲空間的效果。V-Aggregator算法[4]在Key算法的基礎上提出改進，在搜索冗余信息的同時建立數(shù)據(jù)立方體，并且忽略“部分冗余元組”，也可以大大減少存儲空間。不過此算法即使并不存儲全部元組，也要求立方體完全物化。Beyer等人提出了MinCube算法[5]，從而計算出BST-Condensed Cube緊湊立方體，其中，BST是基本單元組，即在事實表中，某些屬性組合有著唯一的元組，在存儲時可以只存儲一次這些基本單元組，從而達到減少冗余的效果。Lakshmanan等人提出了商立方體（Quotient Cube）[6]的概念，采用劃分（Partition）方法將數(shù)據(jù)表中的屬性劃分成一些等價類來存儲。劃分方法的依據(jù)不固定，所以之后有許多基于此結構的新算法陸續(xù)被提出。Sismanis等人提出的Dwarf立方體[7]是一種樹形數(shù)據(jù)結構，將完全物化的數(shù)據(jù)立方體壓縮到一個非常密集的樹形結構中。由一系列實驗結果可以看出，Dwarf立方體在數(shù)據(jù)結構壓縮方面效果最為顯著，然而Dwarf在解決數(shù)據(jù)存儲冗余的過程中也造成了一些冗余，因此本文將對這一方法進行詳細介紹，并且提出一些改進。

Dwarf對于每一個結點都建立了ALL單元格，其結果相當于數(shù)據(jù)庫結構中的group by操作，其中的約束內(nèi)容為該結點的上層結點，因此ALL單元格存儲的內(nèi)容為其所有“兄弟”單元格，而對于部分結點來說，只存儲了一個單元格，因此在結構上會造成一定程度的冗余，而這種冗余對于大型的數(shù)據(jù)倉庫來說更加明顯，改進之后的R-Dwarf樹減少了這種冗余。另外在算法的時間復雜度上也提出了改進，提前對此類結點進行預計算，減少Dwarf樹生成所需要的時間。

1 Dwarf立方體

1.1 Dwarf立方體簡介

Dwarf立方體是一種用于計算、存儲和查詢數(shù)據(jù)立方體的高度壓縮結構。Dwarf通過消除前綴和后綴冗余的方式，并縮減了存儲空間。前綴冗余由事實表中的前面部分的元組由一個簡單的GROUP-BY查詢產(chǎn)生的，前綴冗余一般發(fā)生在Dwarf立方體的建立時期。后綴冗余發(fā)生在兩個或更多GROUP-BY查詢之間共享一個共同的后綴（如abc和bc）。和前綴冗余一樣，如果結果共享相同的值，則只存儲一次唯一的后綴。在構建Dwarf立方體時產(chǎn)生后綴冗余，通過合并后綴冗余節(jié)約空間。

表1 事實表

例如，表1所示的事實表包含了4個維度，以及一個度量值?？梢钥闯觯樵儾僮鱃ROUP BY（A1）與GROUP BY（A1,B1）的查詢結果相同，于是這種冗余被看做是前綴冗余，在Dwarf中只存儲一次。

再例如，在表1的前五行中，C1只出現(xiàn)在B3之后，如果C1只出現(xiàn)一次，那么GROUP-BY（A2,B3,C1,x）和（B3，C1，x）以及（C1,x）總是有著相同的查詢結果，其中x是任意的D列值，于是這種冗余被看做的后綴冗余，在Dwarf中將合并這些冗余。

1.2 Dwarf的存儲結構

Dwarf立方體可以看做是一個有向無環(huán)圖，只有一個根節(jié)點，它的高度D等于立方體的維數(shù)。在i層的結點中包含的關鍵字是相應的立方體的第i維的值。每個結點都包含一個特殊的ALL單元，如果該結點是非葉子節(jié)點，它包含一個指向下一級的指針；如果該結點是葉子結點，ALL單元中存儲聚合值。如果存儲的結點發(fā)生合并，稱為聚集結點，它將能通過多個路徑到達根結點。如果結點N是一個聚集結點，那么N的后代結點X也將是一個聚集結點，因為它可以也可以通過多條路徑到達根結點。

圖1顯示了基于表1的Dwarf立方體結構，整個結構可以看成是一棵樹或一個有向圖。事實表是已經(jīng)排序的，聚合函數(shù)是SUM。根結點包含事實表的第一個屬性和對下一級的鏈接。葉子結點包含事實表的最后一個屬性以及聚合值。Dwarf樹的高度等于屬性的數(shù)量，屬性與樹中顯示的層數(shù)相對應。

圖1 Dwarf立方體的存儲結構

Dwarf立方體完全改變了原始事實表的存儲結構，樹形結構決定了Dwarf不能像其他壓縮技術那樣將結果存儲在關系數(shù)據(jù)庫中，因為結點沒有固定格式?？梢愿鶕?jù)ER模型對結點的存儲進行建模，并將它們分解為數(shù)據(jù)庫中的關系存儲（Dwarf中的存儲單元和結點、結點和結點實際上對應于一對多的關系）。通過實驗，Dwarf有很好的壓縮效果，它用于存儲超大型數(shù)據(jù)非常適合，尤其是Peta（1024T）規(guī)模數(shù)據(jù)。

1.3 Dwarf立方體建立過程

Dwarf立方體的建立過程分為兩步：前綴擴張和后綴合并。圖2表示了Dwarf立方體的建立過程，輸入有序的事實表之后執(zhí)行前綴擴張操作，在獲取前綴冗余之后，在子Dwarf樹下判定是否存在后綴冗余，同時建立ALL單元格，關閉結點，生成Dwarf樹。

Dwarf的實現(xiàn)過程實際上是減少前綴和后綴冗余的處理，算法分為前綴擴張和后綴合并兩部分。算法的生成結果與樹相似。前綴冗余的消除是通過與根節(jié)點接近的節(jié)點共享來實現(xiàn)的，而消除后綴冗余則是通過與葉子節(jié)點共享的節(jié)點來實現(xiàn)的。

圖2 Dwarf立方體建立過程

1.4 Dwarf存在的問題

Dwarf通常以平面文件的形式存儲，這使得構建立方體時更高效，但更新更加困難。其原因是用戶必須維護文件本身的物理存儲，而在關系數(shù)據(jù)庫中，這是DBMS的職責。而且，在查詢時，每個結點都會讀取相應的連接操作，因此效率不高。

Dwarf對于事實表中的數(shù)據(jù)沒有進行預先的判斷，對于每個元組都執(zhí)行相同的操作，導致了一些存儲冗余，以及生成時間的浪費。根據(jù)原文描述，對于密集數(shù)據(jù)，Dwarf結構中的主要冗余是前綴冗余，而對于稀疏數(shù)據(jù)而言，后綴冗余是Dwarf結構中的主要冗余。如果預先對事實表中的屬性進行統(tǒng)計操作，在后續(xù)實驗中有針對性地建立Dwarf立方體，從而達到縮短生成時間的效果。

除此之外，對于如圖1中的結點（2），結點中只存在C1一個值，包含指向結點（3）的一個索引，此時的ALL單元格也指向（3）結點，造成了一定程度上的冗余，在本文考慮將此類冗余去除。

2 R-Dwarf算法

2.1 R-Dwarf的改進思路

為了更加有效地減少算法執(zhí)行時間，以及節(jié)約存儲空間，針對前文提到的原始算法中存在的問題，在保持原有結構的基礎上，對只存儲單獨單元的結點進行處理，不創(chuàng)建ALL單元格，減少其中的存儲冗余。另外，由于前綴冗余多數(shù)發(fā)生在密集立方體，而后綴冗余多數(shù)發(fā)生在稀疏立方體，因此在算法開始之前先對事實表進行統(tǒng)計判斷，在算法執(zhí)行時增加判定條件，預先判定結點層數(shù)與數(shù)據(jù)密集程度的關系，從而實現(xiàn)減少時間復雜度的效果，節(jié)約立方體的生成時間。

在之后的實驗中，將使用標準數(shù)據(jù)集對算法進行測試，包括測試生成結果是否準確，以及算法的執(zhí)行效率，生成結果的大小等因素。

2.2 R-Dwarf的存儲結構

R-Dwarf立方體在Dwarf立方體的基礎上提出了改進，存儲結構與Dwarf立方體大致相似，與原始結構不同的是，并不是每一個結點都存儲了ALL單元格，改進之后的立方體結構如圖3所示。對于一個結點來說，如果只存在唯一的值，無需創(chuàng)建ALL單元，因為該ALL結點的指向鏈接與原始單元所指向結點或者聚合值完全相同。對于規(guī)模較大的數(shù)據(jù)表，結點中存在唯一的值的情況是很常見的，這種方法可以減少很大一部分冗余，從而縮小存儲空間。

R-Dwarf立方體的存儲結構在Dwarf立方體的基礎上進行了優(yōu)化，例如圖3中的（2）結點，只包含一個存儲單元，因此省略掉ALL單元格以及冗余的指向下一級的索引，而對于葉子結點（4）和（5），只包含唯一的值和聚合值，同樣將ALL單元格省略。同理結點（8）、（10）和（11）。

2.3 R-Dwarf立方體建立過程

正如前文分析所指出，R-Dwarf算法解決了Dwarf原始算法中存在的一部分結構冗余的問題，對輸入數(shù)據(jù)增加了判定條件來達到減少原始數(shù)據(jù)結構存儲空間，以及生成時間消耗的效果。R-Dwarf算法輸入密集維度數(shù)d，即在對事實表的每列屬性進行統(tǒng)計之后，得出一部分基數(shù)與事實表總行數(shù)相等的維度。在算法執(zhí)行過程中，只對D-d層的結點進行處理。

圖3 R-Dwarf立方體的存儲結構

圖4 R-Dwarf立方體建立過程

圖4解釋了R-Dwarf的改進過程，與原始算法不同的是，在算法輸入部分輸入密集維度數(shù)d，獲得準確的事實表信息，減少算法執(zhí)行過程中的判斷處理，從而減少算法的執(zhí)行時間。另外，在對結點創(chuàng)建ALL單元格時執(zhí)行判斷，如果結點內(nèi)只存在唯一的值，則不創(chuàng)建ALL單元，這種操作減少了算法生成結果的大小，較原始算法進一步減少了冗余。

R-Dwarf立方體的建立算法分為兩步：前綴擴張和后綴合并。算法針對一個有序的事實表，包含一個唯一的主鍵和一系列相關屬性，其中屬性值按照基數(shù)（即每個屬性列中不同的值的數(shù)量）由小到大排序，屬性的順序影響了整個Dwarf立方體的大小，基數(shù)大的維度應處于Dwarf樹的高層。

算法輸入有序的事實表F，最大維度D，密集維度數(shù)d，對于高度大于D-d的結點不進行任何操作，直接關閉結點。

在前綴擴張過程中，創(chuàng)造了D-|P|-1個新結點，其中D是立方體的維度總數(shù)，|P|是相同前綴的長度。同時，相同數(shù)目的結點將被關閉。前綴擴張過程按順序掃描有序的事實表，讀取一個元組，通過比較當前元組和前一個元組，創(chuàng)建必要的結點和單元格。當葉子結點關閉時，ALL單元格中存儲關于其他格的聚集值。當一個內(nèi)部結點關閉時，ALL單元格被創(chuàng)建，而與原算法不同的是，當結點中除ALL單元格之外只包含一個唯一的單元格時，ALL單元格不被創(chuàng)建。然后，調(diào)用后綴合并算法來實現(xiàn)子Dwarf的創(chuàng)建。

后綴合并過程創(chuàng)建一個結點的ALL單元格的子Dwarf。如果是葉子結點，將直接調(diào)用聚集函數(shù)來計算結果單元格的聚集值。它要求輸入一組Dwarf，然后合并它們來構造最終的Dwarf樹。對于Dwarf的根結點來說，結點中存儲的是合并下層子Dwarf結點中的聚集值或索引，而對于子Dwarf結點中的ALL空間，存儲內(nèi)容為其兄弟Dwarf的合并。如果只有一個Dwarf需要合并，那聚集操作立刻發(fā)生，因為合并的結果就是Dwarf本身。另外，在合并過程中，如果出現(xiàn)結點中只有一個單元格的情況，也不會創(chuàng)建ALL單元。

3 實驗結果及分析

3.1 數(shù)據(jù)集與實驗環(huán)境

實驗采用適用于OLAP的基于TPC-H的星型模式基準（Star Schema Benchmark），TPC為 Transaction Processing Performance Council的簡稱，TPC提供的TCP-H是一個決策支持的測試基準，由一系列面向商務應用的查詢和并發(fā)數(shù)據(jù)修改組成，其選擇的查詢和組成數(shù)據(jù)庫的數(shù)據(jù)在商業(yè)上都具有廣泛的代表性并且易于實現(xiàn)。TPC-H用于生成模擬商業(yè)數(shù)據(jù)，對數(shù)據(jù)庫產(chǎn)品進行測試，在學術和工業(yè)領域被廣泛使用。

文獻[8]中描述的SSB星型模式基準包括一個事實表——Lineorder，以及四個維度表——customer，part，supplier，date。本實驗根據(jù)星型模式基準建立事實表，包含29個屬性維度，其中包括多種數(shù)據(jù)類型（整型、字符型、浮點型），1個主鍵，1個值為1的聚合值。事實表包含5,620,999萬行數(shù)據(jù)。

本文的實驗環(huán)境為64位Windows 10操作系統(tǒng)，AMD A8處理器和8GB內(nèi)存，開發(fā)語言為Python，數(shù)據(jù)庫使用MariaDB實現(xiàn)。實驗的聚合函數(shù)使用SUM函數(shù)。

3.2 改變維度個數(shù)的實驗結果分析

實驗設置一定的元組數(shù)，通過改變維度數(shù)量來測試生成結果所需要的時間，以及占用空間大小。

圖5 算法生成結果大小和生成消耗時間與維度的關系

圖5表示保持元組數(shù)量不變，改變維度個數(shù)的結果，其中圖（a）表示隨著維度的增加，生成樹的空間占用大小變化，圖（b）表示隨著維度的增加，生成樹所需時間的變化。元組數(shù)量約為560萬條，維度選擇從2到8，可以看出，生成的Dwarf樹的大小隨著維度的增多呈指數(shù)增長，改進后的結果較原始結果略有減小，但與原始結果相差不大，原因是改進算法減少了部分結點中存儲單元的數(shù)量，而結點依舊被創(chuàng)建了。Dwarf樹的生成時間隨維度的增加而增長，而且可以清晰地看出，改進算法的生成時間較原始算法有了比較明顯的改善。

3.3 改變元組個數(shù)的實驗結果分析

實驗設置一定的維度數(shù)，通過改變元組數(shù)量來測試生成結果所需要的時間，以及占用空間大小。

圖6 算法生成結果大小和生成消耗時間與元組數(shù)量的關系

圖6表示保持維度數(shù)量不變，改變元組數(shù)量的生成結果，其中圖（a）表示隨著元組數(shù)量的增加，生成樹的空間占用大小變化，圖（b）表示隨著元組數(shù)量的增加，生成樹所需時間的變化。維度數(shù)量選定5個，為了測試算法對于稀疏立方體的改進功能，本實驗特地選定了事實表中第一個維度，以及最后四個維度，在本實驗進行測試的事實表中，第一個維度基數(shù)為1，即只有一個屬性值，而最后四個維度的基數(shù)與元組總數(shù)相等，即沒有重復的屬性值。由實驗結果可以看出，隨著元組數(shù)量的增加，Dwarf樹的大小和生成時間較原始算法都有著一定的改善。

4 結語

在本文中，我們總結了一些關于數(shù)據(jù)倉庫與數(shù)據(jù)立方體壓縮的知識，比較了一些數(shù)據(jù)立方體的建立算法，詳細介紹了一種數(shù)據(jù)立方體壓縮技術——Dwarf算法，并且對算法提出了改進，在保持輸出結果準確的基礎上，減少了一部分冗余。實驗結果證明，算法在存儲空間消耗以及生成時間方面都有了一定的改進。

隨著當代科技的進步，信息膨脹，需要處理的數(shù)據(jù)變得更多，數(shù)據(jù)倉庫與OLAP技術被越發(fā)廣泛地應用到各個領域，關于Dwarf算法的研究也還有許多問題，例如如何存儲Dwarf樹、如何根據(jù)Dwarf樹還原事實表，以及如何根據(jù)Dwarf索引數(shù)據(jù)等。

關于數(shù)據(jù)倉庫存儲與OLAP決策分析的研究還在持續(xù)，不同的數(shù)據(jù)壓縮技術也將盡快投入實際應用中。