（计算机软件与理论专业论文）数据立方的存储组织与索引.pdf

华中科技大学硕士学位论文 摘要 数据立方的巨大尺寸为它的存储和维护带来许多难题，并且导致了巨大的查询 代价。为了从根本上解决这些问题，需要探索有效的存储组织方法，尽可能缩小数 据立方的存储开销：同时辅以适当的索引机制，进一步加速数据立方查询响应，并 且方便对数据立方进行快速的更新维护。 b u b s t 浓缩数据立方是一种有效缩小数据立方尺寸的浓缩机制，它被进一步 扩展为b u e s t 浓缩数据立方，两者的本质都是将那些由相同基表元组集合聚集得 到的立方元组浓缩到一条。b u b s t 浓缩数据立方只能发现相同基表元组集合仅包 含一条基表元组的情形，而事实上这个相同基表元组集合还可能包含多条元组， b u e s t 浓缩数据立方可以发现这种情形并进行相应的浓缩因此具有更好的浓缩 效果。 对数据立方的任一范围查询事实上可最终归结为针对其中特定数据小方的范围 查询，因此迫切需要将立方元组按数据小方进行聚簇。c u b o i d t r e e 就是基于上述事 实提出的一种高效数据立方索引机制，同时考虑到数据立方的多维特性，c u b o i d t r e e 在每个数据小方内以z o r d e r 保持立方元组的空间临近性。在b u b s t 浓缩数据立 方中，基本单元组对应的单值维集的作用类似于普通立方元组对应的分组维集。只 要知道对应的单值维集，就可确定基本单元组所有取a l l 值的维，同时确定所有可 能包含了它所浓缩立方元组的数据小方。此外，对基本单元组按照单值维集进行分 类组织也将有利于查询。基于b u b s t 浓缩数据立方的这些优点，主要研究了利用 c u b o i d t r e e 对其进行索引。 ， 研究了利用c u b o i d t r e e 更新b u b s t 浓缩数据立方的问题，并且实现了大批量 增量更新的方法，保证更新结果等价于完全重新计算的结果，且提高了更新效率。 实验结果表明：利用c u b o i d t r e e 索引b u b s t 浓缩数据立方，可以减小数据立 方的存储开销，提高数据立方查询效率，同时还易于进行更新维护。 关键词：联机分菥珏理；数据兰方：浓缩数猫立方；数据求方；多维数据方索目 范围查询；z 顺序；大批量增量更新 华中科技大学硕士学位论文 a b s t r a c t t h e h u g es i z em a k e s i td i f f i c u l tt os t o r e ，q u e r ya n dm a i n t a i nad a t ac u b e ，t os o l v et h e s e p r o b l e m s f r o mt h er o o t w en e e dt of i n da 1 1e f f i c i e n tw a yt oo r g a n i z et h ed a t ac u b ew h i c h c a ns a v em o r es t o r a g ec o s t s ；w h a t sm o r e ，w es h o u l db u i l ds o m e p r o p e ri n d e xt oi m p r o v e t h ep e r f o r m a n c eo f a n s w e d n g d a t ac u b e q u e r i e s a n dt of a c i l i t a t eu p d a t i n gt h ed a t ac u b e b u b s tc o n d e n s e dc u b ei sa ne f f e c t i v ea p p r o a c ht or e d u c i n gd a t ac u b es i z e ，i tc a nb e e x t e n d e dt ob u e s tc o n d e n s e dc u b e b o t ho ft h e mc o n d e n s e dt h o s ec u b e t u p l e s a g g r e g a t e df r o mt h es a m eb a s et u p l es e ti n t o o n ep h y s i c a lt u p l e ，b u b s tc o n d e n s e d c u b ec a no n l yf i n dt h ec a s et h a tt h es a m cb a s et u p l es e tc o n s i s t so f o n l yo n eb a s et u p l e w h i l et h es a m eb a s e t u p t e s e tm a yc o n s i s to fm o r et h a no n eb a s e t u p l e s b u - e s t c o n d e n s e dc u b ec a ne x p l o i tt h i sc a s ea n dh e n c ei tw a sm o r ee f f e c t i v et or e d u c i n gt h e d a t ac u b es i z e w h e n e v e raq u e r ya g a i n s ts o m ed a t ac u b ei si s s u e d ，i t sn a t u r a lt od e c o m p o s ei ti n t o s e v e r a ls u b q u e r i e s r e s p e c t i v e l ya g a i n s ts o m ep a r t i c u l a rc u b o i d ，s o i t s i m p e r a t i v et o c l u s t e ra l lt h ec u b et u p l e sb e l o n g i n gt ot h es a j t l ec u b o i d ，c u b o i d t r e ei sa ne f f i c i e n tc u b e i n d e xm e c h a n i s m p r o p o s e di nt h i sp a p e rb a s e do nt h i sf a c t c o n s i d e r i n gt h a td a t ac u b ei s am u l t i d i m e n s i o n a lv i e w , c u b o i d t r e eu s e sz o r d e rt op r e s e r v et h es p a c ea p p r o x i m a t i o n b e t w e e nt h o s ec u b et u p l e si ne a c hc u b o i d i nab u b s tc o n d e n s e dc u b e ，t h e s i n g l e d i m e n s i o ns e to fab a s es i n g l et u p l ei ss i m i l a rt ot h eg r o u p i n gd i m e n s i o n so fan o r m a l c u b et u p l e ab a s es i n g l et u p l ec a no n l yc o n d e n s ec u b et u p l e si nt h o s ec u b o i d sw h o s e g r o u p i n gd i m e n s i o ns e t t a k e si t s s i n g l ed i m e n s i o ns e t a sap r e f i x ，a n dh e n c et h o s e d i m e n s i o no nw h i c hi t 。v a l u ei sa l la r ei d e n t i f i e db yi t ss i n g l ed i m e n s i o ns e t w h a t s m o r e ，c l a s s i f y i n g b a s e s i n g l e t u p l e sb y t h e r e s i n g l e d i m e n s i o ns e tw i l lf a c i l i t a t e a n s w e r i n gq u e r i e s s i n c eb u b s tc o n d e n s e dc u b eh a ss u c ha d v a n t a g e s ，w em a i n l y s t u d yh o w t oi n d e xb u b s tc o n d e n s e dc u b e u s i n gt h ec u b o i d t r e e w ea l s os t u d i e dh o wt ou p d a t eb u - b s tc o n d e n s e dc u b eu s i n gt h ec u b o i d t r e e ，a n d p r o p o s e da na p p r o a c ht ob u l ki n c r e m e n t a lu p d a t i n gi t i tg u a r a n t e e dt h a tt h er e s u l to f i i 华中科技大学硕士学位论文 u p d a t i n gi s t h es a m ea st h er e s u l to ff u l l yc o m p u t i n gt h er e n e w e db a s er e l a t i o n ，a n d i m p r o 、t e dt h eu p d a t i n gp e r f o r m a n c e i nc o n c l u s i o n ，i n d e x i n gb u b s tc o n d e n s e dc u b eb yc u b o i d t r e ec a nn o to n l ys a v e s t o r a g ec o s t s ，b u t a l s o i m p r o v eq u e r yp r o c e s s i n g a n db u l ki n c r e m e n t a l u p d a t i n g p e r f o r m a n c e k e ：，w 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 o n d e n s e dc u b e ；c u b o i d m u l t i d i m e n s i o n a lc u b e i n d e x ；r a n g eq u e r y ；z - o r d e r ：b u l ki n c r e m e n t a lu p d a t e i l l 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 近年来，商业智能在企业决策中正扮演着日益重要的角色。越来越多的企业丌 始借助决策支持系统( d e c i s i o ns u p p o r ts y s t e m ，d s s ) 对企业的海量历史数据进行 复杂分析。d s s 从各种统计和汇总数据中发现市场运营规律或发展趋势，为企业决 策提供重要依据，从而可以使企业在运作的过程中扬长避短，节约运营成本的同时 尽可能获得更多的经济利益。另一方面，传统的事务型数据库管理系统已不能满足 企业从多角度分析数据的要求，因此e f c o d d 于1 9 9 3 年提出了联机分析处理 ( 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 u l t i d i m e n s i o n a l v i e w ) 作为各种前端分析工具的概念模型，为用户从多个角度考察和分析数据提供 直观的支持。j i m g r a y 在i c d e 9 6 大会上提出的数据立方( d a t a c u b e ) 1 2 1 f 是这 样一种多维视图，它把基本关系表中用户考察的目标属性称为度量( m e a s u r e ) ，而 把那些作为用户观察角度的属性称作维( d i m e n s i o n ) ，数据立方对基本关系表中的 数据在所有可能的维属性组合之上计算聚集。 在华中科技大学数据库与多媒体技术研究所承担的科技信息决策支持系统中， 需要对历史数据进行分析，从中发现规律并为各个职能部门提供决策依据。与传统 应用中强调的联机事务处理( 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 ) 不同，决策支 持应用中的数据处理模型主要为联机分析处理。为了进行决策，用户需要从各个角 度观察汇总数据，因此最常见的o l a p 查询就是分析型的复杂聚集查询。与o l t p 应用中多都预先给定可能的查询不同，o l a p 应用中多是用户根据不同分析需求提 出的即席查询，并且用户通常都要求提交的查询能够在可接受的时间内得到响应， 这就对系统的查询性能提出了较高的要求。 o l a p 查询的新特性也要求有新的查询优化策略来加速响应查询。因为数据立 方包含了所有可能角度的数据汇总，所以通常预先计算并保存数据立方，从而无需 即时计算即可响应各种聚集查询，大大缩短查询响应时间。但是存储大量的冗余信 息也使得数据立方的尺寸相对而言非常巨大，带来了更多的存储开销。为了解决这 华中粹技大学项士学位论文 一问题，目前国内外学者己提出了多种压缩数据立方或缩小数据立方尺寸的方法。 而另一方面，对大尺寸数据集进行查询的代价也是不容小视的。众所周知，对大量 数据进行有效地存储组织并构建适当的索引是缩小查询代价的一种重要手段。本文 也将针对o l a p 查询的特性，探索数据立方的有效存储和索引机制，提高利用数据 立方响应o l a p 查询的性能，从而提高o l a p 应用系统的整体性能。重要的是：本 文将结合一种有效的数据立方浓缩手段来实现数据立方的存储和索引机制，尽可能 在缩小数据立方尺寸的同时，不致破坏利用数据立方无需即时计算即可响应查询的 优势，并且通过构建索引进一步加速查询响应。 i 2 国内外概况 数据立方通常是为了加速响应o l a p 查询而被预先计算的。自j i mg r a y 提出立 方算子( c u b eb y ) 的概念以后，国内外许多学者起初都把研究工作集中于寻求数 据立方计算的高效算法，而忽略了数据立方的大尺寸问题。事实上数据立方的巨大 尺寸是许多相关问题的根源，正是它导致了数据立方查询的不菲代价，而且即使是 在数据立方计算所耗费的时间代价中，占支配性地位的也是存储巨大的数据立方所 带来的大量i o 操作1 3 4 1 。为了从根本上解决数据立方相关的许多问题，国内外学者 也进行了一系列的研究工作，以寻求数据立方大尺寸问题的适当解决方案，另一方 面，作为加速查询响应的一种有效手段，索引始终都是数据库界学者研究工作的重 点，对数据立方索引机制的研究工怍也同样如此。许多学者都将研究重点侧重于以 上两个方面之一，却很少有研究工作试图在缩小数据立方尺寸和加速数据立方查询 响应之间寻求恰当的平衡。 1 2 1 部分计算数据立方 由于数据立方包含了多个数据小方，所以解决数据立方大尺寸问题的一种直接 的想法就是：当不需要或者受存储空间、计算时间等条件限制时，考虑不要完整计 算整个数据立方，而是选择部分数据小方或数据小方中的部分元组进行计算。数据 小方的选择，实质上是实化视图选择( m a t e r i a l i z e dv i e w ss e l e c t i o n ) 问题在数据立方 框架下的特饲1 5 棚。v h m i n 郴m 等人首先在文献【5 】中讨论了数据小方的选择问题， 2 华冲科技大学硕士学位论文 并且证明这一问题是n p 完全问题( n p c o m p l e t e ) 。基于某个数据小方能从另一个数 据小方进一步聚集而来的偏序关系所构成的数据立方格( c u b e l a t t i c e ) ，他们提出了 一个贪心算法b p u s 。随后，a s h u k l a 等人提出了一个比b p u s 快上几个数量级的 启发式算法p b s l 6 1 ，而且它也能达到b p u s 同样的选择优化保证。p b s 算法简单地 按尺寸从小到大的顺序选择数据小方来实化。由于聚集程度高的数据小方通常尺寸 较小，上述策略也就等价于优先选择聚集程度高的数据小方。p b s 算法的另一个优 点就是很容易与数据立方计算方法b u c 进行集成，文献 9 】重点探讨了这方面的工 作。此外，文献【6 还考虑了只选择某个数据小方的一部分，以及数据立方元组的查 询概率等问题。 1 2 2压缩存储数据立方 数据压缩是减小数据尺寸的经典技术，文献 1 0 】从体系结构的角度讨论了数据 压缩技术对数据库的影响，重点在于如何选择适当的压缩算法。也有学者提出利用 数据压缩技术，将整个数据立方压缩后再存储，从而缩小存储开销。在统计数据库 ( s t a t i s t i c a ld a t a b a s e ) 领域，经常采用的是转置表( t r a n s p o s e dt a b l e ) 。文献【1 1 1 进 一步提出：利用小段二进制位串来编码属性值以减小存储空间。此外，对于重复出 现的子序列，可以采用r u nl e n g t he n c o d i n g 编码方法来进行压缩。在o l a p 领域中， 也采用了各种各样的压缩技术，主要用来处理数据稀疏问题【1 2 , 1 3 1 。数据立方压缩存 储方案的问题在于：响应查询的时候需要进行解压缩运算，因而可能与聚集值的即 时计算样，带来用户无法忍受的响应延迟。 1 2 3估计聚集值响应查询 估计聚集值响应查询可以被看作从另一个角度来解决数据立方大尺寸问题的一 种技术。文献 1 4 】提出了大纲数据结构( s y n o p s i s d a t as t r u c t u r e ) ，可以在许多应用中 快速提供近似查询结果。在数据仓库环境中，近似查询处理技术尤为流行，诸如： 小波( w a v e l e t ) 1 5 l ，多元多项式( m u l t i v a r i a t ep o l y n o m i a l s ) 1 6 1 ，多元高斯混合模型 ( m i x e dm o d e l b ym u l t i v a r i a t eg a u s s i a n s ) 0 7 1 ，直方图( h i s t o g r a m ) f 1 引，抽样( s a m p l i n g ) ”9 l 等等a 此外，针对特殊的查询类型，还提出了一些特别的数据结构来进行快速处 华中科技大学项士学位论文 理。文献【2 0 】利用一个预先计算好的、大型前缀立方( p r e f i x c u b e ) ，针对限定范围 求和的查询( r a n g e s 1 l r r l q u e r i e s ) ，提出了前缀和( p r e f i x s l a m ) 与相对前缀和( r e l a t i v e d r e f i xs u m ) 方法。而文献 2 h 提出了层次紧凑立方( h i e r a r c h i c a lc o m p a c tc u b e ) ，它 可以回答限定范围求极大值的查询( r a n g e m a xq u e r i e s ) 。显然，通过估计聚集值来 响应查询只能给出近似的回答，对某些要求精确回答的查询就无能为力了。 1 2 4浓缩数据立方及其相关工作 数据立方中每一条立方元组都是在基表元组的某个子集上聚集计算得到的，由 于数据立方通常是高度稀琉的，所以这个子集可能只包含一条元组，显然这样的立 方元组无需计算即可从这条基表元组得到，文献 2 2 】把这条基表元组称为基本单元 组( b a s es i n g l et u p l e ，b s t ) ，并且指出：不需保存可直接由基本单元组聚集得到 的那些立方元组，而只是在基本单元组后附上数据小方对应分组维集的信息，因为 基本单元组在度量和这个维集上投影就可得到这些立方元组，这就是浓缩数据立方 ( c o n d e n s e dc u b e ) 的概念。由于不同数据小方中的立方元组可能是由同样的条 基本单元组聚集计算得到的，而这些立方元组都可浓缩到一条基本单元组，所以浓 缩数据立方大大缩小了数据立方的尺寸。浓缩数据立方的突出优势表现在它不需即 时计算即可响应数据立方的查询，而且度量值是精确的而非估计的，它对o l a p 应 用中常见的上卷和下钻操作更是提供了有利的支持。文献 2 2 】中给出了发现基本单 元组并利用其对数据立方进行浓缩的一种启发式算法b o t t o m u p b s t ，以及发现所有 基本单元组的m i n c u b e 算法。 浓缩数据立方是缩小数据立方尺寸的一种新机制，它注意到了数据立方的特性， 能够在缩小数据立方尺寸的同时不破坏数据立方的完整性，完全保持了数据立方无 需即时计算即可响应查询的优势但文献 2 2 r 给出了浓缩数据立方的计算算法， 并未提出适合浓缩数据立方的具体存储和索引机制。浓缩数据立方可以称作是解决 数据立方大尺寸问题的开创性发现，继它之后又有两种类似方法被提出，此后相关 研究工作得到了迅速的发展。 i ) w a 一叫是在随后不久的s i g m o d2 0 0 2 上由y s i s m a n i s 等人提出的一种数据 立方存储组织结构。它首先以前缀树的方式组织数据立方，一个维的数据立方被 4 华中科技大学硕士学位论文 组织成一棵高度为的树，树的每个层次对应数据立方的一维。而某个层次上的每 个节点都储存着该层次所对应维的一个可能取值( 包含数据立方为每个维扩充的 a l l 值) ，所有从树的根节点到达叶节点的路径都分别代表了一条立方元组，相应 的度量值存储在叶节点中。然后所有路径的相同后缀被合并，最终得到的纺锤形结 构就是d w a r f 。文献【2 3 1 中也给出了由基表构建d w a r f 的算法，究其根本，d w a r f 中 可以合并后缀的情形同样是由文献 2 2 1 中提出的基本单元组引起的，因此也可以大 大缩小数据立方尺寸。某些时候前缀树的存储结构也能在相当程度上带来存储空间 的节省，所以d w a r f 在这些情形下节省存储空间的效果较浓缩数据立方更为明显。 在2 0 0 2 年的v l d b 会议上，v s l a k s h m a n a n 等人又提出了一种新的数据立方 表示方法q u o t i e n tc u b e 2 4 1 ，它能够在缩小数据立方尺寸的同时保持数据立方的完整 语义。q u o t i e n tc u b e 强调了数据立方的语义完整性，保持了数据立方天然的格的结 构，本质上与c o n d e n s e dc u b e 并无太多区别。文献 2 4 1 的主要工作也只是提出了 q u o t i e n tc u b e 的基本概念与计算方法，基于q u o t i e n tc u b e 的高效索引、范围查询 ( r a n g eq u e r y ) 、增量式更新等等问题都还有待于进一步的研究。 1 2 5 数据立方的存储组织与索引 文献【2 5 】提出了c u b e t r e e 作为数据立方的存储抽象( s t o r a g e a b s t r a c t i o n ) ，并且 用基于多维空间划分的r t r e e 2 6 1 的一个变体p a c k e dr t r e e s l 2 7 1 来加以实现。 c u b e t r e e 通过尚可接受的存储开销获得了较好的数据聚簇( d a t ac l u s t e r i n g ) ，但其 最好的特点在于大批量的增量式更新，对于高过4 维的可伸缩性测试结果尚未见报 导。事实上r t r e e 较多地应用于空间数据库中，在维数过高的情况下的确未有较好 的性能表现。文献【2 8 】提出了尤其有利于对数据立方进行点查询( p o i n tq u e r i e s ) 的 层次分裂立方森林( h i e r a r c h i c a ls p l i tc u b ef o r e s t s ) 。不过，它是一个高度冗余的数据 结构，并不适合大型数据库应用。 d w a r f 可以看作是一个自索引的、高度浓缩的数据立方存储结构，它天然的层 次索引结构非常有利于对数据立方进行点查询。但是如果限定中间或接近叶节点的 层次对应维的取值范围，而对接近根部的层次对应维的取值不加限制，则相应的范 围查询以d w a r f 来响应将显得非常吃力。 华中科技大学硕士学位- 论文 数据立方是为了给多维数据分析提供便利而被提出的，研究任何数据立方相关 课题都不能忽视其与生俱来的多维性。d w a r f 的不足之处也正在与此，相较之下， 浓缩数据立方并未给出具体的存储组织方案，可以借鉴已有的数据立方索引机制， 以多维敢方式对其进行存储组织并构建适当的索引。 虽然多维索引机制的研究工作在国内外都开展得非常广泛，但事实上，对高维 数据进行有效地索引，目前仍然是一个开问题( o p e np r o b l e m ) 1 2 ”。vg a e d e 博士 在文献 2 9 1 中指出：之所以难以设计良好的多维索引机制，关键在于不存在一种可 以完全表现出多维空间邻近性的全序关系。但是总有一种顺序，可以使得多维空间 中邻近的点至少在这种顺序下有很大的可能性是相邻的。因此可以选取适当的多维 填充曲线把多维空间映射到一维空间，然后利用成熟的一维索引技术，从而有效地 对多维空间进行索引。vg a e d e 同时还指出这种方法的优势就在于它对维数的增加 是不敏感的，也就是说它相对于维数有良好的可伸缩性。h vj a g a d i s h 在文献 3 0 1 中对已经提出的几种空间填充曲线z o r d e r 、g r a y c o d i n g 和h i l b e r t 曲线进行了分析， 并模拟了使用这些曲线将多维空间映射到一维空间后可能获得的范围查询性能。结 果表明h i l b e r t 曲线能够最好地保持多维空间中点的邻近性，从而可以获得最好的平 均性能。但是另一方面，在高维情况下h i l b e r t 和g r a yc o d i n g 编码的计算都需要很 大的代价，而z - o r d e r 编码的计算却非常简单，并且在查询性能上的表现也相当不 错，所以基于z o r d e r 映射方法的多维索引机制讨论得最多。j a o r e n s t e i n 等人将 z o r d e r 和b t r e e 结合，提出了z k db t r e e l 3 1 i 。r b a y e r 则在文献【3 2 】中提出了z k d b t r e e 的一个改进的变体u b t r e e 。r t r e e 及其各种变体由于并发控制和故障恢复 等方面的复杂性，很难与商业数据库管理系统内核进行紧密集成。而z k db t r e e 和 u b - t r e e 由于是基于事实上的商业标准索引机制b t r e e 而实现得，因而可以平滑地 与商业数据库管理系统内核进行紧密集成。u b t r e e 目前已经成功地集成到了商业 数据库管理系统t r a n s b a s eh y p e r c u b e 的内核之中【矧。此外，o r a c l e 公司也已经在它 的空间数据库插件o r a c l e9 is p a t i a l 中应用了z o r d e r 3 4 】。 1 3 课题主要研究工作 华中科技大学达梦数据库与多媒体技术研究所承担了科技部科技信息决策支持 6 华中科技大学硕士学位论文 j ，目j 一i i 自| 自= 目目e ；= = | 皇 系统的研发工作，同时还负责武汉华工达梦数据库有限公司的联机分析服务器 d m 3o l a p 原型系统的设计和开发，这两个系统中都要利用预先计算数据立方来加 速对o l a p 查询的响应。为了对o l a p 服务和应用提供有效支持，需要对数据立方 进行物理存储，而要更进一步地提高查询效率，则构建适当的索引往往是必要的。 同时为了避免完全重新计算数据立方的高额代价，还应当考虑对数据立方进行更新 维护，本课题作为上述两个系统的公共子系统“数据立方的存储组织与索引”， 所要研究和解决的主要问题正是对数据立方进行有效的存储组织，构建适当的索引 结构并基于索引进行增量式更新维护。本文拟研究的主要工作可以归纳为5 个方面。 1 研究数据立方浓缩的机制，减小数据立方存储开销，同时保持数据立方无需 即时聚集计算即可响应o l a p 查询的优势。 2 重点分析b u b s t 浓缩数据立方并进行相关扩展工作。 3 对几种数据立方浓缩机制进行对比分析，选择合适的浓缩机制作为有效的数 据立方存储组织方案。 4 研究数据立方索引机制，针对数据立方查询的特性，提出高效的数据立方索 引机制。有效地结合数据立方的浓缩和索引机制，运用本文提出的方法对浓缩数据 立方进行索引。 5 设计并实现基于索引的浓缩数据立方的增量式更新方案。 7 2 数据立方的浓缩 o l a p 服务器通常会预先计算数据立方，以加速响应可能的聚集查询。但是出 于数据立方尺寸巨大，不可避免地带来了巨额的存储开销，并进而导致：完全计算 并物理化数据立方以及针对数据立方进行查询都可能需要频繁的磁盘i l o 操作。丽 i 0 操作通常被认为是影响数据库性能的决定性代价，因此可以认为数据立方的大 尺寸问题是许多数据立方相关问题的根源，并且在利用数据立方响应o l a p 查询的 实现疗案中已成为瓶颈问题。本章就着重研究如何从根本上解决数据立方大尺寸问 题，同时也是以加速查询响应为最终目标，而非一味地寻求最大限度缩小数据立方 尺寸的方法。接下来首先从数据立方的基本概念出发，分析数据立方之所以具有巨 大尺寸的原因：然后对目前国内外学者解决此问题的几种方法进行简单介绍，并提 出了我们基于其中一种方法的扩展；最后对比几种不同方案，寻求在缩小数据立方 尺寸和加速o l a p 查询之间达到较好平衡的方案。 2 1 数据立方的巨大尺寸 j i m g r a y 等人于1 9 9 6 年提出了数据立方的概念，它将数据仓库( d a t a w a r e h o u s i n g ) 中的数据组织成多维形式，用以直观地支持联机分析处理所需的复杂 多维分析。数据立方算子c u b eb y 是传统的g r o u pb y 算予的多维扩展，用于计 算c u b eb y 子句中各属性的所有可能组合所对应的g r o u pb y 。考虑一个基本关 系表s a l e s ( d a t e ，p r o d u c t ，c u s t o m e r , a m o u n t ) ，查询2 1 是在s a l e s 上计算数据立方 的一个例子。 查询2 1s e l e c t d a t e , p r o d u c t , c u s t o m e r , s u m ( 区辨d 口尼f ) f r o ms a l e s c u b e b y d a t e ，p r o d u c t , c u s t o m e r 查询2 1 将对d a t e ，p r o d u c t 和c u s t o m e r 的所有组合所对应的8 个g r o u pb y 进行求和聚集计算，分别为( d a t e ，p r o d u c t ，c u s t o m e r ) ，( d a t e ，p r o d u c t ) ，( d a t e ，c u s t o m e r ) ， ( p r o d u c t ，c u s t o m e r ) ，( d a t e ) ，( p r o d u c t ) ，( c u s t o m e r ) 和( ) ( 即g r o u pb y 属性为空的 那个聚集) 。这里整个查询的结果被称为一个数据立方，可记为c u b e ( d a t e ，p r o d u c t ， 华中科技大学项士学位论文 c u s t o m e r a m o u n t ) ，s a l e s 则称为它的基表。在o l a p 术语中，c u b e b y 子句中各 属性又被称作维( 观察数据的角度) ，如d a t e ：而被聚集计算的属性则被称作度( 或 度量，考察目标) ，如s u m ( a m o u n t ) 中的a m o u n t 。总之，对于含个属性的c u b eb y 算子，将要计算个不同的g r o u pb y 。一个g r o u pb y 也被称作一个数据小方 ( c u b o i d ) ，类似地，对应( d a t e ，p r o d u c t ) 的数据小方可以记为c u b o i d ( d a t e ，p r o d u c t ， a m o u n t ) 。文献 2 】申为数据立方的每个维扩充了一个a l l 值( 通常记为+ ) ，用以 表示执行分组聚集操作时被投影掉的维，从而提供了一种以二维表来表示整个数据 立方的简单方法。 o l a p 应用中的分析型查询多是复杂的聚集查询，因此o l a p 服务器通常预先 计算数据立方来加速响应查询。假设尺是一个有个分组属性的基本关系表( 简称 基表) ，对于在r 上计算的一个t 维( js ls ) 数据小方，它的元组数目就是r 中所有元组在这k 个分组属性上所有可能取值的数目，将分组属性集记为s d ，则以 上表述的形式化描述见公式2 1 。 c u b o i d t u p l e s n u m ) = l 兀r l 2 1 ) 记r 的个分组属性蔓( d l ，屯a n ) ，分别对应的基数为( c ，c a ，c v ) 。如 果基表r 相对它的个分组属性非常稀疏，即r 的大小远小于它所有维的基数的乘 积( 1 r i n c ) ，那么l 兀。r l 可能接近于旧，也就是说某个数据小方的大小有可 l l 能接近r 的大小。由于一个维的数据立方包含个数据小方，整个数据立方的 大小将远远大于基表。而在真正的o l a p 应用中，基表多数情况下都很稀疏，而且 其本身的尺寸都可能非常巨大，所以整个数据立方的尺寸是极其惊人的。数据立方 的巨大尺寸使得保存和维护一个经过完全计算的数据立方可能显得不切实际。 2 2 基于基本单元组的浓缩数据立方 浓缩数据立方是最近提出的一种有效缩小数据立方尺寸的途径。不同于以往的 缩小数据立方尺寸的方法，浓缩数据立方中所有的立方元组都不需要任何即时计算 或解压缩即可得到，并且结果是精确的而非估计的。从本质上讲，它只是把那些由 9 华中科技大学硕士学位论文 _ 曩目_ _ _ i i 目_ _ _ 目_ _ _ 目，_ t | ，_ _ = 目e l ；目_ _ 葺目_ _ 目- _ e = 目= ；目= = j = = ；g = 自霉 完全相同的基表元组集合聚集计算得到的立方元组浓缩到一条。 如果一个基表元组f 在维集s d = ( d t ，出。矾】上的取值在整个基表中是唯一 的，那么元组t 就是维集s d 上的一个基本单元组，s d 则被称为基本单元组f 的单 值维集(。显而易见的是，如果一个基表元组f 在某个维集如 上是一个s 基i n 本g l e 单d 元i m 组e n ，s i 则o n ，s 在e t ) 。妒和度量上的投影即为。孓d 对应的数据小方( 也可记 为c u b o 消s d ) ) 中一条相应的立方元组。显然这条立方元组无需保存，因为它所包 含的信息完全可以直接由f 得到，也就是说可以把这条立方元组浓缩到基本单元组f 。 文献 2 2 1 把使用这种浓缩机制得到的数据立方称为基于基本单元组的浓缩数据立方 ( 或简记为b s t 浓缩数据立方) 。 表2 i 个基本关系表r l 我们以表2 1 给出的基表r i 似，ec d 为例，来简要说明b s t 浓缩数据立方的 基本思想。在这个例子中，元组如在维集 a 和维集 脚上都是基本单元组，但在维 集 c 上却不是。这是因为f ，在似 和 b ) 上的取值8 和1 都是唯一的，但r f 在 c ) 上的取值i 却不是唯一的，因为元组t 2 在维集 c 上同样取值l 。 基本单元组的一个天然特性就是：当我们在它的单值维集上对基表进行分组时， 它是对应划分( p a r t i t i o n ) 中唯一的元组。因此，对于有这条基本单元组的单值维集 参与分组所得到的任意划分，只要包含此基本单元组，则一定仅包含此元组，于是 它的度量值也一定等于这条基表元组的度量值。假定计算数据立方的聚集函数为 s u m ，则包含维b 的数据立方元组( 这里是指在维b 上不会取a l l 值的立方元组) ， 例如a b c ，a b + ，b c 和忸+ ，当b 的取值为l 时，它们的聚集值都是一样的，即 1 0 0 。换句话说- 也就是数据立方元组( 8 ，l ，1 ) ，( 8 ，l ，) ，( ，1 ，1 ) 和( ，l ，) 的聚集值 都相同。因此我们就可以将这4 条立方元组浓缩到条立方元组( 8 ，1 ，1 ，1 0 0 ) ( 可以 称其为“代表“元组) ，并且记住 b 是它的单值维集。当要从这一“代表”元组导 出它所表示的那4 条立方元组时，我们只需简单地保持元组的度量值1 0 0 和它在维 集 埘上的取值l 不变，同时将其它各维的取值相应地取a l l 或者这条“代表”元 l o 华中科技大学项士学位论文 组的对应维值即可，这里我们不需要再做任何聚集。相反， c ) 不是元组t t 的单值 维集，则上述特性不成立：比如说虽然数据立方元组( + ，l ，1 ，1 0 0 ) 和( + ，8 ，l ，5 0 ) 在 c 上的值都是l ，它们却具有不同的聚集值。 在现实世界中，用来计算数据立方的基表绝大多数都是很稀疏的。从上面的简 要描述中，我们可以看出，当基表很稀疏时单元组的数量应该很大，因而数据立 方尺寸的减小比例将会是很可观的。文献 2 2 1 采用一个实际数据集进行了实验，该 数据集为气象观测数据选取9 个维，包含l ，o l5 ，3 6 7 条元组，由这一基表计算得到 的b s t 浓缩数据立方的尺寸只有未完全计算的普通数据立方的1 1 3 。 通过数据立方浓缩，一方面我们可以减少数据立方的计算时间，因为计算代价 的主体部分就是将数据立方元组写到外存的开销：另一方面，由于浓缩数据立方尺 寸较小，从外存读取数据立方元组到内存的开销相应也较小，从而可以提高查询响 应速度。在理想的情况下，即：一个数据立方在经过浓缩之后可以整个装入内存， 而未经浓缩却不能的时候，所能获得的性能提高将是极其明显的。 需要注意的是：一个基本单元组可能有多个单值维集，例如元组，在维集 4 上也是一个基本单元组。同样地，我们可以将聚集值都等于1 0 0 的4 条数据立方元 组( 8 ，l ，1 ) ，( 8 ，l ，+ ) ，( 8 ，+ ，1 ) 和( 8 ，+ ) 浓缩到同一条“代表”元组( 8 ，1 ，1 ，1 0 0 ) ，并 且记住p ) 是它的单值维集。如果我们同时记住基本单元组t ，的这两个单值维集 4 和 彤，就可以将总共6 条不同的数据立方元组浓缩到同一条“代表”元组，而其 中元组( 8 ，l ，1 ) 和( 8 ，l ，) 被两个单值维集重复表示。如果不物理地存储那些被基本单 元组所浓缩的数据立方元组，我们就得到了个b s t 浓缩数据立方。文献 2 2 】首先 给出了计算b s t 浓缩数据立方的一种启发式算法b o t t o m u p b s t ( 简记为b u b s t ) ， 它以固定的维顺序进行计算，该算法计算输出的结果被称为b u b s t 浓缩数据立方； 然后又给出了一种可以发现所有基本单元组的b s t 浓缩数据立方计算算法 m i n c u b e ，它的计算结果即为最小的b s t 浓缩数据立方( 或简称为m i n c u b e ) 。 2 2 1 b o t t o m u p b s t 算法 通常用立方格图来描述各个数据小方之间的关系。图2 1 给出了一个4 维数据 立方的立方格图，其中每一个节点对应一个数据小方，以其对应的分组维集来表示。 华中科技大学硕士学位论文 马g d ，、 ? 冬笔篷j 棼冀 - ：弋专；乏；：0 ba , c _ d & cb , d c d j 蠢s 毒豢j yo 一：毒丢：7 ab