多維數(shù)據(jù)立方體的存儲設(shè)計

馬潔

多維數(shù)據(jù)立方體的存儲設(shè)計

馬潔

多維數(shù)組進(jìn)行存儲通常是將其線性化為一維數(shù)組的方式進(jìn)行存放，這種方法不利于數(shù)據(jù)的多維分析。首先，采用分塊存儲方法，將數(shù)據(jù)立方體劃分為小的立方體為基本單位進(jìn)行存儲，然后，為每一個多維數(shù)據(jù)立方體創(chuàng)建一個數(shù)據(jù)文件，將劃分后得到的有效數(shù)據(jù)塊依次存放在數(shù)據(jù)文件的數(shù)據(jù)域中，在文件結(jié)束部分創(chuàng)建數(shù)據(jù)塊的索引，即數(shù)據(jù)塊在文件中的起始位置。

數(shù)據(jù)倉庫；數(shù)據(jù)立方體；多維數(shù)據(jù)存儲

0 引言

目前雖然已經(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)，克服目前存在的問題。

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

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

本文采用 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。數(shù)據(jù)塊的標(biāo)識由稀疏維成員的二進(jìn)制編碼拼接而成，每一個成員的二進(jìn)制編碼都是唯一的，成員組合后拼接而成的二進(jìn)制編碼也是唯一的，完全可以作為該組合對應(yīng)數(shù)據(jù)塊的唯一標(biāo)識。設(shè)稀疏維 Di 中的成員 Dik的二進(jìn)制編碼為 BDik，長度為 DBiti，則表示稀疏維組合（D1k，D2k，……，Dnk）對應(yīng)數(shù)據(jù)塊的唯一標(biāo)識 pos=(……((BD1k〈〈DBit2)| BD2k)|……)| BDnk。

2 多維數(shù)據(jù)立方體的存儲

在確定了有效的數(shù)據(jù)塊及其唯一標(biāo)識以后，就需要對這些數(shù)據(jù)塊進(jìn)行物理存儲[4]。本文采用的數(shù)據(jù)倉庫物理存儲模型大致如下所述，首先，為每一個多維數(shù)據(jù)立方體創(chuàng)建一個數(shù)據(jù)文件，將劃分后得到的有效數(shù)據(jù)塊依次存放在數(shù)據(jù)文件的數(shù)據(jù)域中，在文件結(jié)束部分創(chuàng)建數(shù)據(jù)塊的索引，即數(shù)據(jù)塊在文件中的起始位置。

2.1 數(shù)據(jù)文件結(jié)構(gòu)設(shè)計

數(shù)據(jù)文件的結(jié)構(gòu)如圖1所示：

圖1 數(shù)據(jù)文件結(jié)構(gòu)圖

文件頭信息包括文件中數(shù)據(jù)塊的個數(shù)和數(shù)據(jù)塊索引起始位置等信息。

2.2 數(shù)據(jù)塊結(jié)構(gòu)設(shè)計

因為，數(shù)據(jù)塊是建立在某個稀疏維成員組合之上，一個數(shù)據(jù)塊中包括所有密集維成員組合所對應(yīng)的度量值，同樣具有多維數(shù)據(jù)立方體的特征，所以，可以將數(shù)據(jù)塊劃分成更小的塊分別存儲[5]。數(shù)據(jù)塊結(jié)構(gòu)圖如圖2所示：

圖2 數(shù)據(jù)塊存儲結(jié)構(gòu)圖

數(shù)據(jù)塊頭信息包括數(shù)據(jù)塊 ID，數(shù)據(jù)塊大小，每個子塊大小，子塊的個數(shù)。因為，所有密集維成員的組合都對應(yīng)一個數(shù)據(jù)子塊，所以，按照某種維次序依次存儲這些子塊，其位置可有維坐標(biāo)直接確定，而不需要在建立子塊的索引。

數(shù)據(jù)塊 ID是該數(shù)據(jù)塊的唯一標(biāo)識，由稀疏維成員組合確定，所以，數(shù)據(jù)塊的ID可由稀疏維成員的二進(jìn)制編碼拼接而成。

若有 n 個稀疏維，每個稀疏維有 Hi個層次，每個層次有Mi個成員，能表示 Di 維的最小二進(jìn)制位數(shù)為 DBiti，則至多創(chuàng)建 H1×M1×…… Hn×Mn個數(shù)據(jù)塊，數(shù)據(jù)塊 ID的長度為 DBit1+DBit2+……+DBitn。

若有 m個密集維，每個密集維的最高層次的成員個數(shù)分別為 DT1，DT2，……，DTm，則一個塊中的子塊數(shù)=DT1 ×DT2×……×DTm；若每個密集維有 k 個非最高層次，每個非最高層次有DSi個成員，則每個子塊中存放 DS1× DS2 ×……×DSk+1個聚集數(shù)據(jù)，從而可確定子塊以及數(shù)據(jù)塊的大小和起始位置。

2.3 索引結(jié)構(gòu)設(shè)計

為了便于查詢，在文件尾部創(chuàng)建數(shù)據(jù)塊索引，記錄數(shù)據(jù)塊在文件中的起始位置，基本格式為：數(shù)據(jù)塊 ID，數(shù)據(jù)塊起始地址[6]。

根據(jù)上一節(jié)所述，可以由密集維層次及該層成員個數(shù)確定子塊個數(shù)和數(shù)據(jù)塊的大小，由稀疏維層次及該層成員個數(shù)可以確定數(shù)據(jù)塊的個數(shù)，所以每個數(shù)據(jù)塊以及文件索引部分的起始位置也可以確定。

創(chuàng)建數(shù)據(jù)文件的流程圖如圖3所示：

圖 3 創(chuàng)建數(shù)據(jù)文件流程圖

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

本文對每個數(shù)據(jù)立方體創(chuàng)建一個數(shù)據(jù)文件，用來存儲經(jīng)過分塊和壓縮以后的多維數(shù)據(jù)。文件大致分為3個部分：文件頭、數(shù)據(jù)域、數(shù)據(jù)塊索引3部分[7]。

3.1 數(shù)據(jù)文件頭

文件頭信息包括數(shù)據(jù)塊索引在文件中的起始位置，數(shù)據(jù)塊的個數(shù)等信息。創(chuàng)建數(shù)據(jù)文件頭的類圖如圖4所示：

圖 4 數(shù)據(jù)文件頭信息類圖

FileHead類用來實例化文件頭信息，主要包括文件中數(shù)據(jù)塊索引起始位置和數(shù)據(jù)塊的個數(shù)。文件頭的大小是固定的，由數(shù)據(jù)塊的個數(shù)和數(shù)據(jù)塊的大小又可確定文件數(shù)據(jù)域的大小，從而可以得到數(shù)據(jù)塊索引的起始位置。

3.2 數(shù)據(jù)域

關(guān)于數(shù)據(jù)塊的創(chuàng)建和壓縮在之前已介紹，這部分只需根據(jù)稀疏維成員的組合情況依次創(chuàng)建相應(yīng)的數(shù)據(jù)塊。具體的實現(xiàn)方法如下所示：

1） public string createDataFiled(List SparesDim_1,..., List SparesDim_n) {

2） String datafield = "";

3） for(String item_1:SparesDim_1){

4） ……

5） for(String item_n:SparesDim_n){

6） if(GetDataByRP (item_1,……, item_n)){

7） Block ablock=new Block();

8） datafield += ablock.getBlock();

9） }

10） }

11） }

12） return datafield;

13） }

GetDataByRP( )方法用來判斷稀疏維成員組合對應(yīng)的數(shù)據(jù)塊是否為空，若不為空返回 true，創(chuàng)建該數(shù)據(jù)塊，調(diào)用Block 對象的 getBlock( )方法將 Block 對象以字符串的形式返回給datafield變量；否則繼續(xù)對下一組合進(jìn)行判斷，直到所有的稀疏維成員組合都判斷完以后，則整個數(shù)據(jù)域就創(chuàng)建完畢，返回 datafield。

3.3 數(shù)據(jù)塊索引

在文件尾部創(chuàng)建數(shù)據(jù)塊索引，記錄數(shù)據(jù)塊在文件中的起始位置，基本格式為：數(shù)據(jù)塊 ID：數(shù)據(jù)塊起始地址。

數(shù)據(jù)塊索引類圖如圖5所示：

圖5 數(shù)據(jù)塊索引類圖

數(shù)據(jù)文件頭信息的大小是固定的，因此，每創(chuàng)建一個數(shù)據(jù)塊，便可以根據(jù)該數(shù)據(jù)塊的ID和pos值計算出它在數(shù)據(jù)文件中的起始位置，即為該數(shù)據(jù)塊的索引。將所有數(shù)據(jù)塊的索引添加到一個列表中，該列表的內(nèi)容就是文件中數(shù)據(jù)塊索引部分。

3.4 數(shù)據(jù)文件的創(chuàng)建

每個數(shù)據(jù)文件由文件頭、數(shù)據(jù)域和數(shù)據(jù)塊索引，3部分組成，上述3節(jié)分別對這3部分的生成做了介紹。創(chuàng)建整個數(shù)據(jù)文件的類圖如圖6所示：

圖 6 數(shù)據(jù)文件類圖

一個MultiDimFile對象由FileHead、FileDataField和FileIndex對象聚合而成，CreateFile( )方法用來生成整個多維數(shù)據(jù)文件。

4 總結(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 Extended Repository Approach[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]Otoo E.J., Doron Rotem, Sridhar Seshadri. Optimal Chunking of Large Multidimensional Arrays for Data Warehousing[J]. DOLAP, 2007, 11:25-32.

[7]Tatsuo Tsuji, Akihiro Hara, Teruhisa Hochin, Ken Higuchi. An Implementation Scheme of Multidimensional Arrays For MOLAP[J]. Computer Socitey, 2007:1-6.

Storage Design of Multidimensional Data Cube

Ma Jie
(Baoji Professional Technology Institute, Baoji 721000,China)

The multi-dimensional array is usually made into a one-dimensional array for storage by linearization, which is not fit for the multi-dimensional analysis of data. This paper adopts a new method of block storage, which divides the data cube into small blocks as the basic units for storage. Then it creates a database file for every multidimensional data cube and stores the valid data get by division into the data field of database file successively. Finally it creates the index of data blocks at the end of the file, namely the starting position of data blocks in the file.

Data Warehouse; Data Cube; Multidimensional Data Storage

TP311

A

2014.12.31)

1007-757X(2015)04-0055-03

馬 潔（1980-）女，寶雞職業(yè)技術(shù)學(xué)院，碩士，講師，研究方向：計算機(jī)應(yīng)用技術(shù)，寶雞，721000