何 平

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

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

何 平

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

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

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

1 引 言

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

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

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

2．1 分塊算法

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

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

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

2．2 分塊設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

［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－），女，湖北省襄陽(yáng)市人，講師，主研方向：計(jì)算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)，數(shù)據(jù)庫(kù)。

2014－12－25