（计算机软件与理论专业论文）数据立方的计算.pdfVIP

华中科技大学硕士学位论文 摘要 决策支持人员往往从多个角度，在多个层面上观察和分析企业的历史数据。数 据立方以多维方式组织企业的历史数据，提供了数据的多维逻辑视图，适应了决策 支持人员的分析需要。o l a p 分析服务器预先计算数据立方，不必通过在线计算即 可回答数据立方查询，从而大大加快了查询的响应速度。 数据立方的定义是数据立方计算的前提，在数据立方六元组定义的基础之上， ：考虑到维的层次关系在数据分析中的广泛使用，我们提出了一个七元组形式的数据 立方定义，以体现维的层次关系。数据立方的定义从逻辑角度描述了数据立方，而 在物理实现上，我们可以采用三种完全不同的方法，比较起来，关系数据立方在技 术成熟度和数据适应性方面优于多维数据立方和混合数据立方，是目前常用的数据 立方实现方案。、 数据立方计算问题一般可以采用立方格图来描述；在数据立方计算中可以结合 多种优化计算的技术，以提高数据立方计算的速度；用于数据立方计算的聚集函数 的性质则限制了优化方法的使用环境。通过研究和比较各种数据立方计算算法，我 们指出b u c 算法最适合于计算现实中常常出现的稀疏数据立方。 维层次关系的存在使得数据立方计算变得更加复杂，通过扩展b u c 算法，我 们提出了可以计算维上带层次数据立方的h b u c 算法。h b u c 算法巧妙地编码了维 上的层次关系，从而可以结合共享排序的优化技术。h b u c 算法自底向上计算各个 g r o u p b y s ，结合并扩展了b u c 算法中的c o l l a p s i n g 和w r i t e a n c e s t o r s 优化技术， 大大提高了数据立方的计算速度。经过完全计算后，数据立方存储需要大量的磁盘 空间，为此，我们设计了分类加索引的存储结构，大大降低了存储空间的开销。 关键词：在线分析处理；数据立方； c u b e 算子；立琴楚：自底诗k | 一 一i 一 华中科技大学硕士学位论文 a b s t r a c t d e c i s i o ns u p p o r tu s e r so f t e nv i e wa n da n a l y z ee n t e r p r i s eh i s t o r i c a ld a t af r o md i f f e r e n t a n g l e s ，a t d i f f e r e n tl e v e l s d a t a c u b e o r g a n i z ee n t e r p r i s e h i s t o r i c a ld a t ai n a m u l t i d i m e n s i o n a lw a y , p r o v i d i n gm u l t i d i m e n s i o n a ll o g i c a lv i e wo fe n t e r p r i s eh i s t o r i c a l d a t a ，w h i c hs a t i s f i e sa n a l y t i c a lr e q u e s tp r o p o s e db y d e c i s i o ns u p p o r tu s e r s o l a ps e r v e r p r e v i o u s l yc o m p u t e sd a t ac u b e ，w i t ht h er e s u l t t h a td a t ac u b eq u e r i e sc a nb ea n s w e r e d w i t h o u to n l i n ec o m p u t a t i o n ，s os p e e d i n gu pq u e r yp r o c e s s i n ge f f e c t i v e l y d a t ac u b ed e f i n i t i o ni st h e p r e m i s e o fd a t ac u b e c o m p u t a t i o n c o n s i d e r i n g t h a t h i e r a r c h yo f d i m e n s i o ni sw i d e l yu s e di nd a t aa n a l y s i s ，a n db a s e do na6 - t u p l ed a t ac u b e d e f i n i t i o n ，w ep r o p o s e d a 7 - t u p l ed a t ac u b ed e f i n i t i o nt oc o m b i n eh i e r a r c h yo f d i m e n s i o n i n t od a t ac u b ed e f i n i t i o n d a t ac u b ed e f i n i t i o nc h a r a c t e r i z e sd a t ac u b el o g i c a l l y , f o ra l o g i c a ld a t ac u b ed e f i n i t i o n ，t h e r ea r e3 d i f f e r e n ti m p l e m e n t a t i o nm e t h o d s c o m p a r e d w i t ht h eo t h e rt w om e t h o d s ，r e l a t i o n a ld a t ac u b ee x c e l si nt e c h n i c a lm a t u r i t ya n dd a t a a d a p t a t i o n ，s om o s t d a t ac u b ei m p l e m e n t a t i o np r e f e rt or e l a t i o n a lm e t h o d d a t ac u b ec o m p u t a t i o np r o b l e mi so f t e nd e s c r i b e db yc u b el a t t i c e w h i l ec o m p u t i n g d a t ac u b e ，w ec a nt a k ea d v a n t a g eo fm a n yo p t i m i z i n gt e c h n i q u e st oa c c e l e r a t ed a t ac u b e c o m p u t a t i o n p r o p e r t i e s o fa g g r e g a t ef u n c t i o nr e s t r i c tt h ec o n t e x to f o p t i m i z i n g t e c h n i q u e s b yr e s e a r c h i n ga n dc o m p a r i n gd a t ac u b ec o m p u t a t i o na l g o r i t h m s ，w ef o u n d t h a tb u c a l g o r i t h mi sm o s tp r o p e rt oc o m p u t es p a r s ed a t ac u b e ，a n dd a t ac u b e si nr e a l w o r l da r eo f t e ns p a r s e e x i s t i n go fh i e r a r c h ya l o n gd i m e n s i o nm a k e s d a t ac u b ec o m p u t a t i o nm o r ec o m p l i c a t e b ye x t e n d i n gb u ca l g o r i t h m ，w ed e v e l o p e dh b u ca l g o r i t h m ，w h i c hc o m p u t e sd a t a c u b ew i t hh i e r a r c h ya l o n gd i m e n s i o n i no r d e rt oc o m b i n e s h a r i n g s o r t so p t i m i z i n g t e c h n i q u ei n t od a t ac u b ec o m p u t a t i o n ，h b u ca l g o r i t h ma r t f u l l ye n c o d em a p p i n g r e l a t i o n o fh i e r a r c h ya l o n gd i m e n s i o n h b u ca l g o r i t h mb o t t o m u pc o m p u t e sa l lg r o u p b y s ， a n dw h e nc o m p u t i n gag r o u pb y , h b u c a l g o r i t h mc o m b i n e sa n de x t e n d sc o l l a p s i n g a n dw r i t e a n c e s t o r so p t i m i z i n gt e c h n i q u e si n t r o d u c e di nb u c a l g o r i t h m ，w h i c hs p e e du p l t 华中科技大学硕士学位论文 d a t ac u b ec o m p u t a t i o ng r e a t l y a f t e rc o m p l e t ec o m p u t a t i o n ，d a t a c u b es t o r a g er e q u i r e sa l o to fd i s ks p a c e ，t h e r e f o r e ，w ed e s i g n e dac l a s s i f y i n d e xs t o r a g es t r u c t u r e ，r e s u l t i n gi na g r e a td e a lo f d i s ks p a c es a v i n g k e yw o r d s ：o n l i n ea n a l y t i c a lp r o c e s s i n g ；d a t ac u b e ；c u b eo p e r a t o r ； c u b el a t t i c e ；b o t t o m - u p 一一 一i i i 华中科技大学硕士学位论文 1 绪论 1 1 课题背景 在激烈的市场竞争中，数据对于企业的生存和发展起着至关重要的作用，表达 信息的数据会随着时间的推移而不断积累，企业迫切需要分析这些累积下来的历史 数据，分析出影响企业发展的关键因素，辅助企业的决策。数据分析市场在过去的 几年中增长迅速，吸引了众多的数据库厂商投身其中，一些著名的数据库厂商相继 推出了它们的在线分析处理( o n l i n e a n a l y t i c a lp r o c e s s i n g ，o l a p ) 服务器，比如说， m i c r o s o f ts q ls e r v e r2 0 0 0a n a l y s i ss e r v e r 、i b md b 2o l a p s e r v e r7 2 和o r a c l e9 i e x p r e s ss e r v e r 等等，这些在线分析处理服务器无一不把数据立方( d a t ac u b e ) 作为构 建的基础。面对国内越来越大的数据分析市场，对于国产的、安全的达梦关系数据 库管理系统( d mr d b m s ) 来说，以数据立方为核心的在线分析处理服务器将是一个 重要的开发方向。 在华中科技大学数据库与多媒体技术研究所承担的科技部电子政务工程中，科 技部信息数据仓库( d a t aw a r e h o u s e ) 提供了一个整个科技部内面向主题的、集成 的、稳定的、不同时间的数据集合i l l ，从而搭建了面向决策支持的数据环境。建立 在科技信息数据仓库之上的在线分析处理服务器以数据立方为基本单元，面向分析， 组织来自数据仓库中的相关数据，支持科技部管理中的决策制定过程。 不同于传统的在线事务处理( o n l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) ，在新的 在线分析处理环境中，数据立方查询往往是复杂的、即席的，同时涉及到大量的数 据，另外，决策支持人员希望大多数的查询在秒级时间内得到响应，只允许少数查 询的响应时间在分钟级别，否则，他们会觉得难以忍受，或者认为系统死机而放弃 查询。所以，提高数据立方查询的响应速度是在线分析处理服务器能否应用于商业 分析的关键所在。在硬件方面，提高c p u 的处理速度、增加主存的容量和加速i o 处理时间当然可以提高查询的响应速度，但是，硬件性能的改善远远落后于企业数 据量的增长速度，因此，我们有必要在软件方面采取措施，数据立方计算就是目前 业界所通用的方法，即预先计算数据立方上的聚集。数据立方计算包括部分计算和 全部计算，本文讨论数据立方的全部计算问题，即预先计算数据立方上的所有聚集， 华中科技大学硕士学位论文 从而加快所有的数据立方查询的响应速度。目前，已经有很多应用建立在数据立方 基础之上，如数据可视化( d a t a v i s u a l i z a t i o n ) 和数据挖掘( d a t a m i n i n g ) n ，作为计 算数据立方的c u b e 算子已经被纳入s q l 标准，被商用数据库和在线分析处理应 用所采纳。 1 2 国内外概况 自从d r j i mg r a y 等人于1 9 9 6 年提出c u b e 算子2 】概念以来，高效的数据立方 计算方法一直是一个研究的重点，其中，i b m a l m a d e n 研究中心和 。 w i s c o n s i n m a d i s o n 大学的研究人员在他们的联合论文 3 】中总结了数据立方计算中 表1 1 数据立方计算算法 序号算法 参考文献时间 华中科技大学硕士学位论文 多种可能的优化技术，大大加快了数据立方计算算法的研究步伐。表1 - l 给出了迄 今为止主要的数据立方计算算法及其参考文献和发表的时间”，图1 1 则描述了这 些算法之间的演化关系。 曰曰曰曰曰日曰 图1 1 数据立方计算算法的演化 不规则矩形表示并行数据立方计算算法 华中科技大学硕士学位论文 处理数据立方查询的在线分析处理服务器有多维型( m u l t i d i m e n s i o n a l ) 和关系 型( r e l a t i o n a l ) 两种不同的体系结构，在这两种不同的体系结构中，数据立方中的数 据组织是截然不同的，因此，我们可以将表1 1 中的数据立方计算算法分为多维数 据立方计算算法和关系数据立方计算算法两类。 1 2 1 多维数据立方计算算法 d r j i mg r a y 在给出c u b e 算子的同时，也给出了一种计算数据立方的方法： 2 ”算法。该算法首先为事实表对应的多维空间里的每一个单元分配一个标识，然后 把这些标识组织成多维数组装进主存之中。每当读入一个新的元组，2 “算法调用函 数i t e r ( h a n d l e ，v ) 2 “次。当处理完所有的输入元组后，2 “算法为每一个单元调用一次 函数f i n a l ( & h a n d l e ) 。2 “算法没有结合排序和散列方法，只是要求事实表对应的多 维数组可以完全装入主存，这对于稀疏的数据立方是一个不现实的要求。 a r r a y c u b e 算法是第一个比较实用的多维数据立方计算算法，同2 “算法比较起 来，a r r a y c u b e 算法采用了多维数组的分块机制和复杂的主存管理机制，如最佳维 顺序技术和块偏移压缩技术等【2 2 1 ，大大减少了对于主存的容量要求。a r r a y c u b e 算 法是一个多趟多路流水线型算法，同关系数据立方计算中的o v e r l a p 算法有点类似， 其基本思想就是为主存里的一些g r o u pb y 构造聚集累加器，然后一块一块的扫描 输入，以流水线的方式计算相应的聚集。尽管a r r a y c u b e 算法采取了种种措施来减 少主存需求和提高计算速度，但是，如果数据立方过于稀疏，使得每一个块中非空 单元太少，将导致计算效率过低，不能满足实际的需要。 1 2 2 关系数据立方计算算法 在d r j i mg r a y 提出c u b e 算子不久，i b m a l m a d e n 研究中心的s a r a w a g ie ta l 提出了p i p e s o r t 算法和p i p e h a s h 算法，w i s c o n s i n m a d i s o n 大学的p r a s a d m d e s h p a n d e 提出了o v e r l a p 算法。其中，p i p e s o r t 算法是第一个使用立方格图描 述数据立方计算问题的算法，基于立方格图描述数据立方计算的问题被后来的数据 立方计算算法所广泛接受。 p i p e s o r t 算法是基于代价和排序的流水线型算法，它主要结合了“最小父母”、 4 华中科技大学硕士学位论文 r ，缓存结果”和“批处理”三种优化方法。该算法可以保证在计算每一个立方格图 的子图时排序的代价最小，但并不能保证对于整个立方格图的排序代价最小，因此， 对于一个实际的数据立方，p i p e s o r t 算法往往生成一个代价很高的立方格图划分方 案。 p i p e h a s h 算法基于代价、散列( h a s h ) 和划分的思想计算数据立方，它主要结 合了“最小父母”、“缓存结果”、“批处理”和“共享划分”四种优化方法。在p i p e h a s h 算法中，基于属性划分立方格图的技术被首次采用，后来的数据立方计算算法大多 借鉴了这种划分技术。但是，p i p e h a s h 算法在共享计算的程度上赶不上p i p e s o r t 算 法，同时需要较多的主存来存放散列表。 o v e r l a p 算法是一个基于排序的流水线型算法，该算法主要结合了“共享划分” 和“共享排序”两种优化技术。o v e r l a p 算法的主要目的是在父母g r o u p b y 和儿 子g r o u pb y 之间重叠最多的前缀属性，从而减少对于整个立方格图排序的次数。 另外，流水线的计算方式减少了对于主存尺寸的要求。o v e r l a p 算法是第一个固定 立方格图中维顺序的数据立方计算算法，这为后来的许多数据立方计算算法所采用。 但是，如果数据立方过于稀疏，导致某些划分尺寸太大，以致装不进主存，将大大 降低o v e r l a p 算法的效率。 p a r t i t i o n e dc u b e 算法是一个分而治之，基于代价的流水线型算法，它主要结合 了“共享排序”、“共享划分”和“缓存结果”三种优化技术，是第个适合于计算 稀疏数据立方的算法。p a r t i t i o n e d 算法首先基于某些属性把输入数据划分成_cube 主存大小的块，然后调用一个m e m o r yc u b e 过程计算这些块上的所有聚集。同 p i p e s o r t 算法一样，m e m o r yc u b e 过程设计了一种立方格图的划分方案，保证以最 少路径数目覆盖立方格图中的所有节点，因此，p a r t i t i o n e dc u b e 算法着重强调的 是排序代价，以共享排序来提高算法的效率。 b u c 算法是一个基于排序和划分，自底向上计算的数据立方计算算法。b u c 算法自底向上计算各个g r o u p b y , 首先计算个维上的g r o u p b y ，然后计算两 个维上的g r o u pb y ，如此等等。b u c 算法是第一个，也是目前唯一的自底向上 计算数据立方的算法，自底向上的计算使得b u c 算法可以采用共享划分的优化技 术，并结合了特别适合于稀疏数据立方 2 3 1 计算的单元组优化方法，因此，b u c 算法 5 华中科技大学硕士学位论文 是目前为止最适合于计算稀疏数据立方的算法。 d w a r f 算法是一个比较新的算法，不同于以前提出过的所有的数据立方计算算 法，严格的讲，d w a r f 算法可以看作是一个用于计算，存储和查询的高度压缩的数 据结构。该算法依次扫描所有的输入元组，把该元组的不同维分量插入到d w a r f c u b e 结构的相应节点中，在插入一个元组后，计算对应于已经扫描过的元组的所有聚集。 d w a r f 算法注意到前面的一些算法在存储数据立方时存在前缀和后缀冗余，采用了 一种高度压缩的数据结构存储数据立方，从而大大减小了计算后数据立方的尺寸。 但是，这种压缩结构并不适合于范围查询。另外，d w a r f 算法在计算数据立方时需 要频繁的文件定位操作，计算效率也不是很高。 1 2 3 数据立方计算算法的扩展 数据立方计算是一个复杂的操作，需要消耗大量的计算机资源，并行则是提高 数据立方计算的效率和对付不断增长的数据立方尺寸的一个自然而然的方法。由于 通信开销的存在，并行数据立方计算的性能并不因为节点的增加而线性提高。每一 种数据立方计算方法都有相应的并行扩展算法，如并行a r r a y c u b e 算法，并行b u c 算法等等。 维一般是含层次关系的，因此有必要扩展数据立方计算算法，使之可以计算维 上带层次关系的数据立方。文献 3 在提出p i p e s o r t 算法和p i p e h a s h 算法的同时也讨 论了如何扩展它们以计算维上带层次关系的数据立方，其主要思想是扩展立方格图， 使之包含层次粒度上的聚集，然后分别修改p i p e s o r t 算法中的排序过程和p i p e h a s h 算法中的划分过程。至于o v e r l a p 、a r r a y c u b e 和p a r t i t i o n e d c u b e m e m o r y c u b e 和 b u c 等算法，尚未有计算维上带层次数据立方的算法扩展的报道出现。 1 3 课题主要研究工作 本课题是科技部电子政务科技信息决策支持系统和我们自主研制的d m o l a p ( 基于达梦数据库管理系统的在线分析处理) 分析服务器系统原型中的一个公共子 课题：“数据立方的计算”，主要目的是研究当前的各种流行的数据立方计算算法， 丌发出支持维上带层次数据立方的快速计算算法，用以支持对于维上带层次数据立 6 一 华中科技大学硕士学位论文 方的复杂查询的快速响应。本课题拟开展的主要工作如下： ( 1 ) 研究和比较各种数据立方模型，提出一种简单直观的数据立方模型，从维、 度量、维的层次关系、维到度量的映射等方面定义将要计算的数据立方，作为数据 立方计算的输入。 ( 2 1 研究和比较国内外主要的数据立方计算算法，包括这些算法的主要思想、结 合的优化技术、优缺点、适用的范围等。 ( 3 ) 重点研究b u c 算法，包括b u c 算法的思想、计算的过程、采用的优化技术 等，并代码化b u c 算法。 ( 4 ) 扩展b u c 算法，使之可以高效地计算维上带层次关系的数据立方。 f 5 ) 设计维及其层次关系的编码方法，使之可以支持的层次之间的快速映射，从 而加快维上带层次数据立方的计算速度。 ( 6 ) 设计计算后数据立方的存储方案。使之能够有效降低存储空间的开销，提高 查询的速度，并方便于索引的建立。 7 华中科技大学硕士学位论文 2 数据立方模型 2 1 数据立方的概念和特征 数据立方是o l a p 分析服务器的核心，它作为o l a p 分析服务器中代数操作 的基本单位，即操作的输入是数据立方，输出也是数据立方，如同关系数据库中的 表一样。数据立方也被称作多维数据集( m u l t i d i m e n s i o n a ld a t as e t ) ，它强调提供用 户数据的多维视图，即允许用户从各个角度观察和分析感兴趣的数据 2 。在o l a p 分析环境下，我们把观察数据特定的角度称作维( d i m e n s i o n ) ，例如，企业常常关 心产品的销售数据随时间推移而产生的变化情况，这时，他是从时间的角度来观察 产品的销售情况，所以时间就是一个维( 时间维) ，企业也常常关心自己的产品在不 同地区的销售情况，所以地理分布也是一个维( 地理维) 。把所观察的目标称作度量 ( m e a s u r e ) ，一般情况下，度量总是一个数值量，例如：“销量”、“利润”、“成本” 等，因此，用户可以对度量进行必要的计算，如平均、综合等等。通常，人们观察 度量的维存在细节程度不同的多个描述方面 2 5 】，我们将维的多个描述方面称作维的 层次( h i e r a r c h y ) 关系，如时间维的年、季度、月份和日期构成时间维上的一个层次 关系，同样，国家，地区和城市构成了地理维上的一个层次关系。层次关系反映了 用户观察和分析数据时的一种习惯，即从大粒度级数据着手，逐步下钻到细粒度级 数据。以时间维为例，用户首先观察年度上的销售数据，看看年度的销售数据是否 有异常情况发生，如果某年的销售数据异常，那么下钻到该年的季度销售数据，看 看是某个季度还是所有的季度出现了销售情况异常，如此等等。 图2 1 是一个超市数据立方的示例。时间，产品和地理是图2 1 所示的数据立 方中的3 个维，在时间维上面有4 个层次粒度：y e a r q u a r t e r m o n t h d a t e ：在产 品维上有3 个层次粒度：i n d u s t r y 一 c a t e g o r y p r o d u c t ：在地理维上有3 个层次粒度： c o u n t r y 一 s t a t e 一 c i t y 。在图2 1 所示的多维空间中，每一个单元( c e l l ) 是由不同的 ( p r o d u c t ，c i t y , d a t e ) 取值所决定的度量s a l e s 。 - 8 华中科技大学硕士学位论文 氕 j u i c e 兰c o l a 勺0 l v l i l k q _c r e a m t o o t h p a s t e s o a p y o 。g ti n d u s t r y c o u n t r 歹 lil q u m ：te r c a x e g o r y s t “e ill l o n t h p r o & c c c i t y i d a y l23 l567d i m e n s i o n ：嫩e r a r c h i e a l d a t e s u r 艘i z a t i o np a th s 图2 i 超市数据立方 9 0 年代初期，e f c o d d 在文献【2 6 】中首次提出了o l a p 概念，同时给出了评 价o l a p 产品的十二条准则。如今，o l a p 的概念已经在商业数据库领域得到了广 泛的使用，o l a p 的特征已经得到广泛的验证和确认。作为一个原则，即o l a p 产 品应能支持o l a p 所具有的特征，已经得到广泛的认可。在这十二条准则中，下面 的几条很好地描述了数据立方的特征。 ( 1 ) 数据的多维视图 企业分析的目的不同，决定了分析和衡量企业的数据总是从不同的角度进行的， 所以企业的数据空间本身是多维的。从用户分析员的角度来看，整个企业的视图本 质上是多维的，因此，用于分析企业数据的数据模型也应该是多维的。 ( 2 ) 高效的数据存取 数据立方应该提供高效的数据存取策略，使得o l a p 用户针对数掘立方的查询 得到快速响应。另外，应使o l a p 用户仅仅存取与指定分析相关的数据，避免多余 的数据存取。 ( 3 ) 稳定的报表性能 当数据立方的维数和层次关系的高度增加时，提供给o l a p 用户的报表能力和 速度不应该有明显的降低和减慢，这对于维护数据立方的易用性和低复杂性至关重 要。 9 华中科技大学硕士学位论文 f 4 ) 维的等同性原则 每一个维在数据结构和操作能力上都是等同的。系统可以将附加的操作授给所 选的维，但必须保证该操作能力可以授给任意其它的维，即要求施加给维的任何操 作都是公共的。 ( 5 ) 不受限维和层次高度 虽然在实际的分析中，为了分析的方便，维的数目和维的层次关系高度总是在 一定的范围内，但是，数据立方应该支持o l a p 用户建立任意多个维，在维上建立 任意高度的层次关系。 在后来的数据立方研究和实践中，许多学者和厂商建议维之间应该是正交的， 即各个维互相独立，不存在维间的依赖关系”i 。需要指出的是，m i c r o s o f ls q ls e r v e r 2 0 0 0a n a l y s i ss e r v e r 允许将维的层次属性独立出来作为一个新的维，比如说，把顾 客的受教育程度独立出来，作为顾客维之外的一个新的维，这将导致数据立方中维 的数目过多，干扰用户分析的视线，不利于用户分析的展开。 2 2 数据立方的模型 目前，学者们对于数据立方模型并没有统一的认识，先后提出了多种数据立方 模型2 8 琊】，其中，文献 2 8 给出了数据立方的形式化描述，以六元组的形式简单直 观地定义了数据立方。六元组形式的定义从多维空间的角度考虑数据立方，体现了 数据的多维本质。但是，该数据立方定义没有考虑维上的层次关系。基于这个六元 组形式的数据立方定义，我们提出了维上带层次关系的数据立方定义。 。 定义：数据立方是o l a p 分析服务器的核心部件，是定义在o l a p 分析服务器 上的各种代数操作的输入输出单元。实际上，o l a p 分析服务器就是由1 个或者多 个数据立方加上一些必要的管理组成的。数据立方被定义成一个七元组 ，其中： ( 1 ) d 是维的集合，d = d l ，d 2 ，d 。 ，其中d i ( 凼d ，1 i n ) 表示第i 个维的名 字，其值域为d o m d ( d i ) ，f d f 兰1 。 ( 2 ) m 是度的集合，m = m l ，1 2 1 2 ，m 。 ，其中m ( m m ，1 i n ) 表示第i 个度量 的名字，其值域为d o m m ( m i ) 。维集和度集是不相交的，即d n m = 中，i m i 三1 。 一 1 0 华中科技大学硕士学位论文 ( 3 ) a 是维的属性的集合，a = a l ，a 2 ，a 。 ，其中a i ( a a ，l i n ) 表示第i 个属 性的名字，其值域为d o m a ( i ) 。 f 4 ) e 是数据立方中单元的集合，e = e l ，e 2 ，e 。) 。 f 5 ) f 是一个一对多的映射关系，f ：d a 。也就是说：每给定一个维名，存在 多个属性名与之对应。对于任何两个不同的维，它们对应的属性集是不相交的，即 v i ，j ，i j ，则f ( d i ) n f ( d j ) = o 。 ( 6 ) h 是维的层次关系的集合，h = h b h 2 ，h 。) ，其中，h ，是维d ，上的一个层次 关系，h i = ，其中，a i 是维d i 上的一个属性，即a f ( d i ) ：每一个维的 层次关系至少包含一个属性，即m = 1 ；另外，如果i i ，那么，属性a 的粒度大于 属性a j 的粒度。 ( 7 ) v 是一个一对一的映射关系，v ：d e ，也就是说，在各个维上设定一个值 后，存在唯一的度量单元与之对应。 显然，上述数据立方的七元组定义本质上是一个多维空间中的定义。任取维值 d j ，d 2 ，d n 的组合，根据映射v 的定义，存在e i e ，使得，v ( d f d 扣，d 。) = e ，。反过 来，若e i e 是数据立方空间中的一个单元，根据映射v 的定义，存在维值d t , d 2 ，d 的组合，使得e i = v ( d l ，d 2 ，d 。) 。这里，d i 也表示维d 。的一个取值。e 取o 或n 元组 形式，0 表示在给定的维值组合上，没有产生我们感兴趣的度量数据，n 元组形式 只是度集m = m l ，m 2 ，m 。) 中元素的一个排列而已，也就是说，如果 x 。是n 元组的第i 个成员，那么存在m i m ，使得m ，= x 。我们常常采用k ( i ) 表示 数据立方单元n 元组集合的第i 个成员对应的度量。 下面我们提供一个超市销售的例子来解释上述关于数据立方的定义，超市数据 立方见图2 2 所示，为了方便，我们没有标注为0 的单元。在超市数据立方中，我 们感兴趣的是商品的销量s a l e s ，因此，度集m = s a l e s l ：我们通常从日期( d a t e ) 、 商品( m e r c h a l l d i s e ) 和供应商( s u p p l i e r ) 三个方面来分析销量数据，所以，维集d = d a t e ， m e r c h a n d i s e ，s u p p l i e r ) ：目期维由日( d a y ) 、月( m o n t h ) ； b 年( y e a r ) 来描述，商品维由 商品名( m _ n a m e ) 、商品颜色( m _ c o l o r ) ； 1 商品重量( m w e i g h t ) 来描述，供应商维由供 应商名( s _ n a m e ) 和供应商地址( s a d d r e s s ) 来描述，所以，属性集a = d a y ，m o n t h y e a r , m n a m e ，m _ c o l o r ，m _ w e i g h t ，sn a m e ，s _ a d d r e s s ) ；维到属性的映射f 定义如下： 1 1 华中科技大学硕士学位论文 s u p p h c r 图2 2 超市数据立方 f ( d a t e ) 2 d a y , m o n t h ，y e a r ； f ( m e r c h a n d i s e ) = m _ n a m e ，m _ c o l o r , m - w e i g h t ； f ( s u p p l i e r ) 2 sn a m e ，s _ a d d r e s s 。 各个维上的层次关系是： h ( d a t e ) 2 ； h ( m e r c h a n d i s e ) = ； h ( s u p p l i e r ) 2 。 数据立方空间中的单元集合代表了任一时刻，由任一供应商供应的任一商品的销量 的集合，而映射v 表示在某一时刻d i ，由供应商s j 供应的商品m k 的销量e 。是多少， 即e t = v ( d i ，s j ，m k ) 。在这里，e t 可能是0 ，这说明在时刻d i ，由供应商s j 供应的商品 m k 没有售出记录：也可能是一元组 集合的形式，它表示在时刻d 。，由供应商 s j 供应的商品m k 存在销售记录，销量由一元组 给出。 对应于上述的多维数据立方模型，有一套完备的代数操作，以求剖析数据，使 最终用户能从多个角度，多侧面地观察数据立方中的数据，从而深入地了解包含在 数据中的信息和内涵。数据立方操作迎合了人的思维方式，从而减少了混淆并且降 低了出现错误解释的可能性。下面，我们来描述施加给数据立方的三个主要的代数 一 1 2 华中科技大学硕士学位论文 操作： ( 1 ) 切片( s l i c e ) 在数据立方中选定两个维，固定其它维的取值，在选定的两个维上各取一个区 间，这就是数据立方的切片。不管数据立方中原来有多少个维，切片的结果是一个 二维的“平面”。 ( 2 ) 切块( d i c e ) 在数据立方中选定三个维，固定其它维的取值，在选定的三个维上各取某一个 区间，这就是数据立方的切块。不管数据立方中原来有多少个维，切片的结果是一 个三维的“空间”。从另一个角度来讲，切块可以看成是在切片的基础上，进一步确 定某一个维的区间得到的片段体，即多个切片的叠合。 ( 3 ) 旋转( r o t a t e ) 数据立方反应的是多维空间，而用户习惯于观察二维平面上的数据，因此，对 于数据立方的分析，用户只能一次观察二个维。旋转即改变维的显示方向，使用户 能够观察指定的维，允许用户从多个侧面进行快速，一致和交互的数据存取。 2 3 数据立方的实现方案 在逻辑上，数据立方以多维方式组织企业中的历史数据，并提供一套完备的多 维代数操作，用以操作数据立方。但是，在物理实现上，数据立方既可以基于多维 数据库技术，也可以建立在关系数据库技术之上口6 1 。多维型数据立方是近来应多维 分析的要求而产生的，它以多维数据库为核心，直接支持数据的多维视图，多维数 据库在数据存储，检索以及综合上有着关系数据库不可比拟的优势，但是，多维型 数据立方在适应分析维数动态变化，适应数据变化，适应大数据量和适应软硬件能 力方面赶不上关系型数据立方。关系型数据立方以广泛应用的关系数据库技术为基 础，使用关系表存储数据立方的数据，在技术成熟度以及各方面的适应性上较之多 维型数据立方占有优势，是目前常用的数据立方实现方案。但是，关系型数据立方 也有它固有的缺点，即数据立方提供的多维模型和多维代数操作必须转换成相应的 关系表和s q l 查询。一种折衷的数据立方实现方案是综合上述两种数据立方实现方 案的长处，采用关系数据库存储海量的基表数据，采用多维数据库存储聚集数据， 13 华中科技大学硕士学位论文 这就是混合数据立方。对于混合数据立方来说，如果钻取到事实表，那么响应速度 比较慢，但它可以迅速从聚集中获取信息。许多公司把他们的历史数据分成两组， 即现存历史数据和存档历史数据。现存历史数据使用率高，覆盖期不超过2 年；存 档期历史数据使用较低，覆盖期为2 年以前。由于存档期历史数据一般要跨越许多 年，甚至几十年，数据量可以很多，由于这些数据不会被经常查询，因此，与使用 关系数据立方存储所具有的优势相比，关系数据立方较低的效率则显得无关重要。 而现存历史数据的分析频率较高，对效率的要求是第一位的，因此，一般采用多维数 据立方。在目前的o l a p 分析服务器市场上，s y b a s ei q 、i n f o m i xm e t a c u b e 和o r a c l e 9 ie x p r e s ss e r v e r 中的数据立方是关系型的，而e s s b a s e 选择多维数据库实现数据立 方；而m i c r o s o f ts q ls e r v e r2 0 0 0a n a l y s i ss e v e r 支持3 种方式的数据立方实现技术， 用户可以根据实际的需要选择相应的数据立方实现技术。 应该说，关系型结构能够较好的适应多维数据的表示和存储。关系数据库将数 据立方体现的多维结构组织成两类表，一类是事实表( f a c tt a b l e ) ，用来组织度量值 以及各个维的码值，事实表往往很大，经常存储上十年的历史数据：另一类是维表 ( d i m e n s i o nt a b l e ) ，分布在事实表的周围，用以组织在观察，分析度量信息时所使 用的维信息，相对于事实表来说，维表显得比较小。对于每一个维来说，有一个表 用来保存该维的元数据，即维的描述信息，包括维的层次属性以及其它属性等。事 实表通过每一个维的值和周围的维表联系在一起，该结构被称之为“星型模式”，采 用这样的结构能够体现数据的多维特征，图2 3 所示的就是一个星型模式的例子。 星型模式并没有对维的层次关系提供显式的支持，雪花模式对星型模式中的维 表进行了细化，维的层次关系清楚地展现在雪花模式中。从星型模式转到雪花模式 的方法就是规范化维表的过程，雪花模式的例子见图2 4 。采用规范化的雪花模式 使得维表占用较少的空间，同时，维表的维护变得更加容易。但是，规范化的关系 模型并不适合于o l a p 分析环境的，规范化的雪花模式要求更多的连接( j o i n ) 操 作，而连接操作是关系数据库中最费时的操作之一，因此，雪花模式大大降低了查询 响的速度。 一。 - 1 4 - 华中科技大学硕士学位论文 圆 l 型! 些d ， 图2 3 星型模式 图2 4 雪花模式 华中科技大学硕士学位论文 2 4 小结 本章首先给出了用于描述数据立方的一般概念，如维、度量和维的层次关系等， 并介绍了一个设计良好的数据