多维数据立方体的存储设计

马洁

多维数据立方体的存储设计

马洁

多维数组进行存储通常是将其线性化为一维数组的方式进行存放，这种方法不利于数据的多维分析。首先，采用分块存储方法，将数据立方体划分为小的立方体为基本单位进行存储，然后，为每一个多维数据立方体创建一个数据文件，将划分后得到的有效数据块依次存放在数据文件的数据域中，在文件结束部分创建数据块的索引，即数据块在文件中的起始位置。

数据仓库；数据立方体；多维数据存储

0 引言

目前虽然已经有大量文献提出了关于多维数组存储组织的有效方法，但是，这些方法都没有完全解决存储过程中存在的一些问题。第一，数组过于稀疏会导致大量存储空间的浪费，而使用压缩技术不但会增加了存储的复杂性，而且，会给OLAP 查询处理带来额外的开销[1]。第二，大多数多维数组存储结构没有充分考虑如何存储维内部层次信息，而事实上许多OLAP 操作多是针对维内部层次进行的[2]。所以，需要对与数据仓库存储结构相关的技术进行深入的学习研究，对原有的存储模式进行改进，克服目前存在的问题。

1 多维数据立方体的分块

对多维数组进行存储通常是将其线性化为一维数组，由坐标确定数据单元的位置后再进行顺序存放。不过这种方法不利于数据的多维分析，所以，本文采用分块存储方法，首先，将数据立方体划分为小的立方体，然后，以小的立方体为基本单位进行存储，从而可以保持数据的多维性[3]。

本文采用 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。数据块的标识由稀疏维成员的二进制编码拼接而成，每一个成员的二进制编码都是唯一的，成员组合后拼接而成的二进制编码也是唯一的，完全可以作为该组合对应数据块的唯一标识。设稀疏维 Di 中的成员 Dik的二进制编码为 BDik，长度为 DBiti，则表示稀疏维组合（D1k，D2k，……，Dnk）对应数据块的唯一标识 pos=(……((BD1k〈〈DBit2)| BD2k)|……)| BDnk。

2 多维数据立方体的存储

在确定了有效的数据块及其唯一标识以后，就需要对这些数据块进行物理存储[4]。本文采用的数据仓库物理存储模型大致如下所述，首先，为每一个多维数据立方体创建一个数据文件，将划分后得到的有效数据块依次存放在数据文件的数据域中，在文件结束部分创建数据块的索引，即数据块在文件中的起始位置。

2.1 数据文件结构设计

数据文件的结构如图1所示：

图1 数据文件结构图

文件头信息包括文件中数据块的个数和数据块索引起始位置等信息。

2.2 数据块结构设计

因为，数据块是建立在某个稀疏维成员组合之上，一个数据块中包括所有密集维成员组合所对应的度量值，同样具有多维数据立方体的特征，所以，可以将数据块划分成更小的块分别存储[5]。数据块结构图如图2所示：

图2 数据块存储结构图

数据块头信息包括数据块 ID，数据块大小，每个子块大小，子块的个数。因为，所有密集维成员的组合都对应一个数据子块，所以，按照某种维次序依次存储这些子块，其位置可有维坐标直接确定，而不需要在建立子块的索引。

数据块 ID是该数据块的唯一标识，由稀疏维成员组合确定，所以，数据块的ID可由稀疏维成员的二进制编码拼接而成。

若有 n 个稀疏维，每个稀疏维有 Hi个层次，每个层次有Mi个成员，能表示 Di 维的最小二进制位数为 DBiti，则至多创建 H1×M1×…… Hn×Mn个数据块，数据块 ID的长度为 DBit1+DBit2+……+DBitn。

若有 m个密集维，每个密集维的最高层次的成员个数分别为 DT1，DT2，……，DTm，则一个块中的子块数=DT1 ×DT2×……×DTm；若每个密集维有 k 个非最高层次，每个非最高层次有DSi个成员，则每个子块中存放 DS1× DS2 ×……×DSk+1个聚集数据，从而可确定子块以及数据块的大小和起始位置。

2.3 索引结构设计

为了便于查询，在文件尾部创建数据块索引，记录数据块在文件中的起始位置，基本格式为：数据块 ID，数据块起始地址[6]。

根据上一节所述，可以由密集维层次及该层成员个数确定子块个数和数据块的大小，由稀疏维层次及该层成员个数可以确定数据块的个数，所以每个数据块以及文件索引部分的起始位置也可以确定。

创建数据文件的流程图如图3所示：

图 3 创建数据文件流程图

3 多维数据立方体的压缩

本文对每个数据立方体创建一个数据文件，用来存储经过分块和压缩以后的多维数据。文件大致分为3个部分：文件头、数据域、数据块索引3部分[7]。

3.1 数据文件头

文件头信息包括数据块索引在文件中的起始位置，数据块的个数等信息。创建数据文件头的类图如图4所示：

图 4 数据文件头信息类图

FileHead类用来实例化文件头信息，主要包括文件中数据块索引起始位置和数据块的个数。文件头的大小是固定的，由数据块的个数和数据块的大小又可确定文件数据域的大小，从而可以得到数据块索引的起始位置。

3.2 数据域

关于数据块的创建和压缩在之前已介绍，这部分只需根据稀疏维成员的组合情况依次创建相应的数据块。具体的实现方法如下所示：

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( )方法用来判断稀疏维成员组合对应的数据块是否为空，若不为空返回 true，创建该数据块，调用Block 对象的 getBlock( )方法将 Block 对象以字符串的形式返回给datafield变量；否则继续对下一组合进行判断，直到所有的稀疏维成员组合都判断完以后，则整个数据域就创建完毕，返回 datafield。

3.3 数据块索引

在文件尾部创建数据块索引，记录数据块在文件中的起始位置，基本格式为：数据块 ID：数据块起始地址。

数据块索引类图如图5所示：

图5 数据块索引类图

数据文件头信息的大小是固定的，因此，每创建一个数据块，便可以根据该数据块的ID和pos值计算出它在数据文件中的起始位置，即为该数据块的索引。将所有数据块的索引添加到一个列表中，该列表的内容就是文件中数据块索引部分。

3.4 数据文件的创建

每个数据文件由文件头、数据域和数据块索引，3部分组成，上述3节分别对这3部分的生成做了介绍。创建整个数据文件的类图如图6所示：

图 6 数据文件类图

一个MultiDimFile对象由FileHead、FileDataField和FileIndex对象聚合而成，CreateFile( )方法用来生成整个多维数据文件。

4 总结

对于多维数据立方体的存储主要有两种模式：关系表和多维数组。关系表模式建立在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 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-）女，宝鸡职业技术学院，硕士，讲师，研究方向：计算机应用技术，宝鸡，721000