多維數(shù)據(jù)立方體的分塊與壓縮設(shè)計

何 平

（湖北襄陽職業(yè)技術(shù)學(xué)院，襄陽441021）

多維數(shù)據(jù)立方體的分塊與壓縮設(shè)計

何 平

（湖北襄陽職業(yè)技術(shù)學(xué)院，襄陽441021）

目前提出的關(guān)于多維數(shù)組存儲組織的有效方法，沒有有效解決存儲空間的浪費(fèi)和存儲維內(nèi)部層次信息問題，導(dǎo)致存儲浪費(fèi)。采用Fragment分塊方法將高維空間進(jìn)行降維存儲，分別分為稀疏維和密集維，數(shù)據(jù)塊建立在稀疏維成員組合的基礎(chǔ)之上，即將稀疏維相同的度量數(shù)據(jù)存儲在一個數(shù)據(jù)塊中，每個數(shù)據(jù)塊有唯一的標(biāo)識。對多維數(shù)據(jù)立方體進(jìn)行了分塊處理，并獲得了每個數(shù)據(jù)塊的標(biāo)識。對于是否需要創(chuàng)建該數(shù)據(jù)塊，只需要在生成數(shù)據(jù)文件時判斷該數(shù)據(jù)塊是否為空，若為空則不需要創(chuàng)建該數(shù)據(jù)塊；若不為空，則創(chuàng)建該數(shù)據(jù)塊。最后給出多維數(shù)據(jù)立方體的壓縮算法。

多維數(shù)據(jù)；分塊設(shè)計；降維存儲；數(shù)據(jù)庫；高維空間；壓縮算法

1 引 言

目前雖然已經(jīng)有大量文獻(xiàn)提出了關(guān)于多維數(shù)組存儲組織的有效方法，但是這些方法都沒有完全解決存儲過程中存在的一些問題。第一，數(shù)組過于稀疏會導(dǎo)致大量存儲空間的浪費(fèi)，而使用壓縮技術(shù)不但會增加存儲的復(fù)雜性，而且會給OLAP查詢處理帶來額外開銷［1］。第二，大多數(shù)多維數(shù)組存儲結(jié)構(gòu)沒有充分考慮如何存儲維內(nèi)部層次信息，而事實上許多OLAP操作多是針對維內(nèi)部層次進(jìn)行的［2］。所以需要對與數(shù)據(jù)倉庫存儲結(jié)構(gòu)相關(guān)的技術(shù)進(jìn)行深入的學(xué)習(xí)研究，對原有的存儲模式進(jìn)行改進(jìn)，克服目前存在的問題。

2 多維數(shù)據(jù)立方體的分塊設(shè)計

對多維數(shù)組進(jìn)行存儲通常是將其線性化為一維數(shù)組，由坐標(biāo)確定數(shù)據(jù)單元的位置后再進(jìn)行順序存放。不過這種方法不利于數(shù)據(jù)的多維分析，所以采用分塊存儲方法，首先將數(shù)據(jù)立方體劃分為小的立方體，然后以小的立方體為基本單位進(jìn)行存儲，從而可以保持?jǐn)?shù)據(jù)的多維性。

2．1 分塊算法

采用Fragment分塊方法，即將高維空間進(jìn)行降維存儲。如多維數(shù)據(jù)立方體建立在n維空間Ω之上，則將其劃分為兩個不相交的子空間Ψ（m維）和Φ（n－m維）。對于子空間Φ，計算每一個可能的維組合，每一個組合對應(yīng)子空間一個m維立方體。因此，如果從空間Ω（D0，D1，……，Dm－1，Dm，……，Dn－1）選取S＝｛D0，D1，……，Dm－1｝作為空間Ψ的坐標(biāo)系，則Ω空間中任一個點Q（p0，p1，……，pn－1）將映射到Ψ中的點Ψ（q0，q1，……，qm－1）和Φ中的點Φ（r0，r1，……，rn－m－1）之中，有如下關(guān)系：

式中｜Di｜是維Di的基數(shù)，0≤i＜m。

式中｜Di｜是維Di的基數(shù)，0≤i＜n－m。

2．2 分塊設(shè)計

采用文獻(xiàn)［3］提出的稀疏維和密集維劃分策略對維空間進(jìn)行劃分。對于某一空間內(nèi)大多數(shù)維的成員組合都沒有度量值，可用空間位置填充量比較低，則可將這些維設(shè)為稀疏維。而密集維是每一種維組合都可能包含一個或多個度量值的維。這種劃分方法，首先保持了數(shù)據(jù)的多維性，符合數(shù)據(jù)倉庫和OLAP的基本要求；另外將維度劃分為稀疏維和密集維，便于數(shù)據(jù)的壓縮存儲，提高空間利用率。

例如對于一個包含四個標(biāo)準(zhǔn)維：Time、Type、Region和Product的多維數(shù)立方體來說，空間Ω為｛Time，Type，Region，Product｝；設(shè)Time和type為密集維，region和product為稀疏維，則兩個子空間分別為Ψ｛Time，Type｝和Φ｛Region，Product｝。圖1顯示的是一個二維數(shù)據(jù)塊表示密集維Time和Type中的數(shù)據(jù)值，Time中的成員為J、F、M和Q1，Type維中的成員為Retail和Batch。圖2顯示的是將整個多維數(shù)據(jù)立方體劃分后得到的所有數(shù)據(jù)塊，Region維中的成員為West、East和South，Product維中的成員為P1、P2和P3。

圖1 用于Time和Type的二維數(shù)據(jù)塊

3 多維數(shù)據(jù)立方體的分塊

對多維數(shù)據(jù)立方體進(jìn)行分塊存儲既保持了數(shù)據(jù)的多維性，又可以提高系統(tǒng)的I／O操作效率［4］。采用Fragment分塊算法，將高維數(shù)據(jù)降維存儲。多維數(shù)據(jù)立方體中的維度被劃分為稀疏維和密集維，分別對應(yīng)兩個低維空間，數(shù)據(jù)塊建立在稀疏維成員組合的基礎(chǔ)之上，即將稀疏維相同的度量數(shù)據(jù)存儲在一個數(shù)據(jù)塊中，每個數(shù)據(jù)塊有唯一的標(biāo)識。

圖2 劃分后的多維數(shù)據(jù)立方體

實現(xiàn)多維數(shù)據(jù)立方體分塊的類圖如圖3所示。在按照稀疏維組合對多維數(shù)據(jù)分塊以后，又對每個塊按照密集維最高層成員組合對其進(jìn)行子塊劃分，每個數(shù)據(jù)塊中子塊的大小和個數(shù)都是統(tǒng)一的［5］。

多維數(shù)據(jù)立方體分塊類圖中各個類的功能如下：

（1）SubBlockHead類是子塊頭信息類，定義了一個getSubHead（）方法用來根據(jù)稀疏維最高層次成員組合情況獲得子塊ID。

（2）SubBlockDataField類是子塊數(shù)據(jù)域類，YearSales（）方法、QuarterSales（）方法和MonthSales（）方法分別用來獲得年銷售量、季度銷售量和月銷售量，Sales（）方法則用來獲得所有層次的銷售量，并使用getfieldString（）方法將所有數(shù)據(jù)轉(zhuǎn)換成字符串的形式返回。

（3）SubBlock類是創(chuàng)建子塊的類，是SubBlock-Head類和SubBlockDataField類的聚合，即每個子塊包含子塊頭和數(shù)據(jù)域兩部分，getSubBlock（）方法將子塊轉(zhuǎn)化成字符串形式返回。

（4）BlockDataField類是數(shù)據(jù)塊中的數(shù)據(jù)域類，每個數(shù)據(jù)塊包含一個數(shù)據(jù)域，這些數(shù)據(jù)域由若干個子塊組成。該類將數(shù)據(jù)塊中包含的所有子塊對象放入ArrayList，并使用getBlockDataField（）方法將子塊對象列表轉(zhuǎn)換成字符串類型返回。

（5）BlockHead類是數(shù)據(jù)塊頭信息類，數(shù)據(jù)塊頭信息中關(guān)鍵的內(nèi)容是數(shù)據(jù)塊的ID，getBlockHead（）方法根據(jù)密集維組合信息計算并以字符串形式返回數(shù)據(jù)塊的ID。

（6）Block類是數(shù)據(jù)塊類，每個數(shù)據(jù)塊包括數(shù)據(jù)塊頭信息和數(shù)據(jù)域兩部分，所以該類由BlockHead類和BlockDataField類聚合而成，getBlock（）方法將數(shù)據(jù)塊轉(zhuǎn)換成字符串形式返回。

圖3 多維數(shù)據(jù)立方體分塊類圖

4 多維數(shù)據(jù)立方體的壓縮

將多維數(shù)據(jù)立方體的維空間按照稀疏維和密集維的規(guī)則進(jìn)行劃分以后，會獲得如圖2所示的一些空白數(shù)據(jù)塊。對這些空白的數(shù)據(jù)塊不需要再進(jìn)行存儲，而只需存儲有效的數(shù)據(jù)塊和數(shù)據(jù)塊標(biāo)識［6－7］。

對多維數(shù)據(jù)立方體進(jìn)行了分塊處理，并獲得了每個數(shù)據(jù)塊的標(biāo)識。對于是否需要創(chuàng)建該數(shù)據(jù)塊，只需要在生成數(shù)據(jù)文件時判斷該數(shù)據(jù)塊是否為空，若為空則不需要創(chuàng)建該數(shù)據(jù)塊；若不為空，則創(chuàng)建該數(shù)據(jù)塊。具體算法如下：

輸入：所有稀疏維成員編碼

（1）確定稀疏維成員的組合；

（2）查找度量數(shù)據(jù)表，是否存在該組合對應(yīng)的度量數(shù)據(jù)；

（3）若該稀疏維成員組合沒有對應(yīng)的度量數(shù)據(jù)，則返回重新進(jìn)行下一種成員組合的判斷若；該稀疏維成員組合有對應(yīng)的度量數(shù)據(jù)，則進(jìn)行下一步；

（4）創(chuàng)建該稀疏維組合對應(yīng)的數(shù)據(jù)塊；

（5）將有效數(shù)據(jù)塊添加到數(shù)據(jù)塊列表中，返回繼續(xù)進(jìn)行下一種成員組合的判斷，直到所有組合情況判斷完畢。

輸出：有效數(shù)據(jù)塊列表。

5 結(jié)束語

對于多維數(shù)據(jù)立方體的存儲主要有兩種模式：關(guān)系表和多維數(shù)組。關(guān)系表模式建立在RDBMS的基礎(chǔ)之上，具有成熟的存儲和查詢技術(shù)支持，但是不能表現(xiàn)數(shù)據(jù)的多維性，不利于數(shù)據(jù)倉庫的OLAP操作。多維數(shù)組與多維數(shù)據(jù)立方體在形式上具有一致性，適用于數(shù)據(jù)的多維分析，但是其存儲技術(shù)還不完善。對多維數(shù)組進(jìn)行存儲時，一般情況下是將多維數(shù)組線性化為一維數(shù)組后再進(jìn)行存儲，這樣就又打亂了數(shù)據(jù)的多維性，文章提出的分開與壓縮算法對多維數(shù)據(jù)存儲有一定的應(yīng)用價值。

［1］ Paul Gray，Hugh J Watson．Present and Future Directions in Data Warehousing［J］．The DATA BASE for Advances in Information System，1998，29（3）：83－90．

［2］ Matthis Jarke，Manfred A Jeusfeld，Christoph Quix，Panos Vassiliadis．Architecture and Qualityin Data Warehouses：An ExtendedRepositoryApproach［J］．Information Systems，24（3）：229－253．

［3］ Nenad Jukic．Modeling Strategies and Alternatives for Data Warehousing Projects［J］．COMMUNICATIONS OF THE ACM，2006，49（4）：83－88．

［4］ Venky Harinarayan，Anand Rajaraman，Jeffery D Ullman．Implementing Data Cube Efficently［J］．ACM SIGMOD Record，1996：205－216．

［5］ Tatsuo Tsuji，Akihiro Hara，Ken Higuchi．An Extendible Multidimensional Array System for MOLAP［J］．SAC，2006：503－510．

［6］ E JOtoo，DoronRotem，SridharSeshadri．Optimal Chunking of Large Multidimensional Arrays for Data Warehousing［J］．DOLAP，2007（11）：25－32．

［7］ TatsuoTsuji，AkihiroHara，TeruhisaHochin，Ken Higuchi．An Implementation Scheme of Multidimensional Arrays For MOLAP［J］．Computer Socitey，2007：1－6．

Design on Block and Compression of Multidimensional Data Cube

He Ping
（Hubei Xiangyang Vocational and Technical College，Xiangyang 441021，China）

The methods proposed by the multidimensional array storage organization have no effective solution to solve the storage space waste and internal hierarchical information storage．This paper adopts Fragment partition method to fragment the block to high－dimensional space dimension reduction of storage，which is respectively divided into sparse and dense，block of data is set up based on sparse group，i．e．the same sparse dimension measurement data is stored in a data block，each block has a unique ID．The block processing of multidimensional data cube is conducted and the identity of each data block is obtained．For the data block creating，the situation，whether the data block is empty or not，should be judged when the data file is generated．The data block is not be required if it is empty，and if not null，then the data block should be created．The multidimensional data cube compression algorithm is given as well．

Multidimensional data；Block design；Dimension reduction storage；Database；High dimensional space；Compaction algorithm

10．3969／j．issn．1002－2279．2015．04．010

TP301

A

1002－2279（2015）04－0039－03

何平（1976－），女，湖北省襄陽市人，講師，主研方向：計算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)，數(shù)據(jù)庫。

2014－12－25