多維數據立方體的分塊與壓縮設計

何 平

（湖北襄陽職業技術學院，襄陽441021）

多維數據立方體的分塊與壓縮設計

何 平

（湖北襄陽職業技術學院，襄陽441021）

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

多維數據；分塊設計；降維存儲；數據庫；高維空間；壓縮算法

1 引 言

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

2 多維數據立方體的分塊設計

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

2．1 分塊算法

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

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

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

2．2 分塊設計

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

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

圖1 用于Time和Type的二維數據塊

3 多維數據立方體的分塊

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

圖2 劃分后的多維數據立方體

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

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

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

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

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

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

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

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

圖3 多維數據立方體分塊類圖

4 多維數據立方體的壓縮

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

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

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

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

（2）查找度量數據表，是否存在該組合對應的度量數據；

（3）若該稀疏維成員組合沒有對應的度量數據，則返回重新進行下一種成員組合的判斷若；該稀疏維成員組合有對應的度量數據，則進行下一步；

（4）創建該稀疏維組合對應的數據塊；

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

輸出：有效數據塊列表。

5 結束語

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

［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－），女，湖北省襄陽市人，講師，主研方向：計算機網絡、物聯網，數據庫。

2014－12－25