基于Dwarf立方體的數(shù)據(jù)倉(cāng)庫(kù)壓縮技術(shù)的研究與實(shí)現(xiàn)

路鈺瑩，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

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

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

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

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

1 Dwarf立方體

1.1 Dwarf立方體簡(jiǎn)介

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

表1 事實(shí)表

例如，表1所示的事實(shí)表包含了4個(gè)維度，以及一個(gè)度量值?？梢钥闯?，查詢(xún)操作GROUP BY（A1）與GROUP BY（A1,B1）的查詢(xún)結(jié)果相同，于是這種冗余被看做是前綴冗余，在Dwarf中只存儲(chǔ)一次。

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

1.2 Dwarf的存儲(chǔ)結(jié)構(gòu)

Dwarf立方體可以看做是一個(gè)有向無(wú)環(huán)圖，只有一個(gè)根節(jié)點(diǎn)，它的高度D等于立方體的維數(shù)。在i層的結(jié)點(diǎn)中包含的關(guān)鍵字是相應(yīng)的立方體的第i維的值。每個(gè)結(jié)點(diǎn)都包含一個(gè)特殊的ALL單元，如果該結(jié)點(diǎn)是非葉子節(jié)點(diǎn)，它包含一個(gè)指向下一級(jí)的指針；如果該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，ALL單元中存儲(chǔ)聚合值。如果存儲(chǔ)的結(jié)點(diǎn)發(fā)生合并，稱(chēng)為聚集結(jié)點(diǎn)，它將能通過(guò)多個(gè)路徑到達(dá)根結(jié)點(diǎn)。如果結(jié)點(diǎn)N是一個(gè)聚集結(jié)點(diǎn)，那么N的后代結(jié)點(diǎn)X也將是一個(gè)聚集結(jié)點(diǎn)，因?yàn)樗梢砸部梢酝ㄟ^(guò)多條路徑到達(dá)根結(jié)點(diǎn)。

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

圖1 Dwarf立方體的存儲(chǔ)結(jié)構(gòu)

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

1.3 Dwarf立方體建立過(guò)程

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

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

圖2 Dwarf立方體建立過(guò)程

1.4 Dwarf存在的問(wèn)題

Dwarf通常以平面文件的形式存儲(chǔ)，這使得構(gòu)建立方體時(shí)更高效，但更新更加困難。其原因是用戶必須維護(hù)文件本身的物理存儲(chǔ)，而在關(guān)系數(shù)據(jù)庫(kù)中，這是DBMS的職責(zé)。而且，在查詢(xún)時(shí)，每個(gè)結(jié)點(diǎn)都會(huì)讀取相應(yīng)的連接操作，因此效率不高。

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

除此之外，對(duì)于如圖1中的結(jié)點(diǎn)（2），結(jié)點(diǎn)中只存在C1一個(gè)值，包含指向結(jié)點(diǎn)（3）的一個(gè)索引，此時(shí)的ALL單元格也指向（3）結(jié)點(diǎn)，造成了一定程度上的冗余，在本文考慮將此類(lèi)冗余去除。

2 R-Dwarf算法

2.1 R-Dwarf的改進(jìn)思路

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

在之后的實(shí)驗(yàn)中，將使用標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試，包括測(cè)試生成結(jié)果是否準(zhǔn)確，以及算法的執(zhí)行效率，生成結(jié)果的大小等因素。

2.2 R-Dwarf的存儲(chǔ)結(jié)構(gòu)

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

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

2.3 R-Dwarf立方體建立過(guò)程

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

圖3 R-Dwarf立方體的存儲(chǔ)結(jié)構(gòu)

圖4 R-Dwarf立方體建立過(guò)程

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

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

算法輸入有序的事實(shí)表F，最大維度D，密集維度數(shù)d，對(duì)于高度大于D-d的結(jié)點(diǎn)不進(jìn)行任何操作，直接關(guān)閉結(jié)點(diǎn)。

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

3.2 改變維度個(gè)數(shù)的實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)設(shè)置一定的元組數(shù)，通過(guò)改變維度數(shù)量來(lái)測(cè)試生成結(jié)果所需要的時(shí)間，以及占用空間大小。

圖5 算法生成結(jié)果大小和生成消耗時(shí)間與維度的關(guān)系

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

3.3 改變?cè)M個(gè)數(shù)的實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)設(shè)置一定的維度數(shù)，通過(guò)改變?cè)M數(shù)量來(lái)測(cè)試生成結(jié)果所需要的時(shí)間，以及占用空間大小。

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

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

4 結(jié)語(yǔ)

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

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

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