（计算机应用技术专业论文）一种保持语义的数据立方体技术研究与应用.pdf

摘要 如何迅速从海量数据中获得准确的决策信息在现代企业日常决策活动中起 着至关重要的作用，作为解决这个问题关键的o l a p 技术中最核心的概念，数据 立方体的实现已经引起了广泛的关注。经过这些年的研究与发展，已经出现了很 多不同的数据立方体实现技术。 研究发现，数据立方体中存在着很多冗余信息，去除这些冗余信息不仅可以 节约存储空间，而且有利于立方体的快速建立与更新。有鉴于此，出现了很多从 不同角度去除冗余的压缩算法，但是这其中很多算法在立方体构建过程中导致了 立方体结构的混乱、语义模糊，增加了计算的复杂性。 本文在侏儒立方体研究的基础上，对能够保持语义的立方体进行了研究，提 出了一种新的立方体结构，这种结构改变了侏儒立方体对聚集数据的存储方式， 能够在保持基本立方体上卷、下钻语义的前提下，尽量的去除前缀冗余、后缀冗 余，节约存储空间，保证立方体清晰的格结构，并且拥有比侏儒立方体更高的存 储效率和查询响应速度。对点查询和范围查询能够快速的返回结果。对大数据量 情况下的稀疏立方体具有良好的支持。本文提出了新数据立方体结构的构建算 法、查询算法和增量更新算法，对其相应的冰山立方体形式也进行了研究。在此 基础上，设计了天津市建委1 2 3 1 9 热线分析系统。 美目奠阅i 联机分析处理数据立方体侏儒立方体冰山立方体 a bs t r a c t h o wt oq u i c k l yg e ti n f o r m a t i o nf r o mm a s sd a t ap l a y sa ni m p o r t a n tr o l ei nt h e d e c i s i o n - m a k i n gp r o c e d u r eo fm o d e r ne n t e r p r i s e a sam e t h o do fs o l v i n gt h i sp r o b l e m ， d a t ac u b e ，w h i c hi st h ec o r ec o n c e p to fo l a p ，h a sa t t r a c t e dw i d ea t t e n t i o n s a f t e r y e a r so fr e s e a r c ha n dd e v e l o p m e n t ，m a n yd i f f e r e n td a t ac u b et e c h n o l o g yh a sb e e np u t f o r w a r d s c i e n t i s t sf o u n dt h a tt h e r ew a sal o to fr e d u n d a n ti n f o r m a t i o ni nt h ed a t ac u b e t h er e m o v a lo ft h e s er e d u n d a n c i e sc a nn o to n l ys a v es t o r a g es p a c e ，b u ta l s om a k ei t c o n v e n i e n tf o rt h er a p i dc r e a t i o na n du p d a t e + o f t h ed a t ac u b ea tt h es a m et i m e f o rt h i s r e a s o n , al o to fc o m p r e s s i o na l g o r i t h m sw e r ep u tf o r w a r dt or e m o v er e d u n d a n c i e so f d a t ac u b ef r o md i f f e r e n ta s p e c t s ，b u t m a n yo ft h e mi nt h ep r o c e s so fc r e a t i n gt h e i r s t r u c t u r e sh a v el e dt oc o n f u s i o n , s e m a n t i ca m b i g u i t y , a n di n c r e a s e dt h ec o m p l e x i t yo f d a t ac u b ec a l c u l a t i o n b a s e do nt h er e s e a r c ho fd w a r fc u b e ，t h i sp a p e r ，w h i c hm a k e sf u l ls t u d yo f d i f f e r e n td a t ac u b ew i t hs e m a n t i c ，p u t sf o r w a r dan e ws t r u c t u r eo fd a t ac u b e t h i s c u b es t r u c t u r ec h a n g e sd a t as t o r a g em o d eo fd w a r fc u b e ，c a l lk e e pt h eb a s i cr o l l - u p a n dd r i l l - d o w ns e m a n t i cc u b e ，r e m o v et h ep r e f i xr e d u n d a n c ya n ds u f f l xr e d u n d a n c y a sf a ra sp o s s i b l e t h i ss t r u c t u r ec a ns a v es t o r a g es p a c e ，e n s u r eac l e a rc u b i cl a t t i c e s t r u c t u r e ，a n dp o s s e s sh i g h e rs t o r a g ee f f i c i e n c ya n dl e s sq u e r yr e s p o n s et i m et h a n d w a r fc u b e f o rp o m tq u e r i e sa n dr a n g eq u e r i e s ，i tc a nr e t u r nq u e r yr e s u l t sv e r y q u i c k l y t h i sd a t ac u b es t r u c t u r es c a l e sw e l lo nt h ec o n d i t i o no fs p a r s ec u b ew i t h l a r g ea m o u n to fd a t a t h i sp a p e rp r o p o s e st h ec o n s t r u c t i o na l g o r i t h m , s e a r c h a l g o r i t h ma n di n c r e m e n t a lu p d a t ea l g o r i t h mo f t h en e w d a t ac u b e ，a n da l s os t u d i e st h e c o r r e s p o n d i n gi c e b e r gc u b e o nt h eb a s i so ft h i sn e wd a t ac u b es t r u c t u r e ，t i a n j i n 1 2 319h o t l i n ed a t aa n a l y s i ss y s t e mh a sb e e nd e v e l o p e d k e yw o r d s , o l a p , d a t a c u b e ，d w a r fc u b e ，i c e b e r gc u b e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞基堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：殆守签字日期：加。夕年万月f 日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：弓钣宇 签字日期：知抄尹年g 月日 导师签名： 似岬 答字日? ：3 1 年i ；b 月罗日 第一章绪论 1 1 研究背景和意义 第一章绪论 天津市建委1 2 3 1 9 话务受理平台建设运行之后，每天会产生大量记录，包括 出租汽车、公共汽车、轻轨、地铁、供水、供气、供热、排水、中水、道路桥梁 等十多个行业的信息，管理人员如果想要全面了解整个系统的工作情况，需要对 各个行业的咨询、报修、抢险、举报、情况反映、投诉、建议、表扬等信息进行 分析，本文涉及实现的1 2 3 1 9 数据分析子系统可以提供对这些信息进行不同维度 的汇总分析功能，以帮助建委领导获得足够的决策支持信息，做出科学的决策。 此子系统可以集中城建领域信息资源信息，及时有效的分析城市管理中的存 在问题，增强处置各类城市管理惘题的能力，逐步形成应对城市管理突发事件快 速反应机制，从而提升城市管理的能级和水平。 其中及时有效分析城市管理中的存在问题是最重要的方面。对于1 2 3 1 9 的领 导来讲，需要的是对整个系统的全面了解，能够从不同的角度维度对整个1 2 3 1 9 运行情况进行查看。 1 2 3 1 9 城建服务热线现有系统经过运行后积累了大量的业务数据。面对这些 数据，原有的报表系统不足以提供足够的信息来进行决策。为方便市民生活、为 提升行业管理和服务水平、为了能够给政府科学决策提供支持，需要在现有系统 数据的基础上，进行数据分析子系统的设计与实施。 这一子系统的主要功能是对1 2 3 1 9 热线服务的受理工单进行统计分析。能够 统计大量的情况反应信息并支持对信息进行多维特征分析；能够支持对多个维度 的组合分析，可以快速给出符合分析条件的工单统计结果；能够处理大量的数据 统计工作并支持对工单进行特征分析和行为分析例如：可以按照行业维度分 析经常投诉的问题特征、投诉的时间分布、平均处理时长等等。 另外还需要生成不同分析粒度的年报、月报：可以按照行业、二级分类、行 政区域、不同时间段分布情况等分别进行汇总。管理人员需要能够对行业、地区、 事件类型等维度中的一个或多个进行分析。 以上这些情况表明，实际上需要的是一个高效的o l a p 系统。联机分析处理 ( o l a p ) 的概念首先由关系数据库之父e f c o d d 于1 9 9 3 年提出的，是专门设 计用于支持复杂的分析操作，主要侧重用于决策人员和高层管理人员的辅助决策 第一章绪论 支持，可以按照分析人员的要求快速灵活地进行大数据量的复杂查询处理，并且 以一种直观易懂的形式将查询结果提供给决策人员。自从e f c o d d 提出联机分 析处理的概念至今o l a p 技术已经经过了十多年的发展，逐渐成熟并得到了广泛 的应用。许多大的厂商纷纷推出自己的o l a p 产品，如o r a c l e 、m i c r o s o f t 、 i n f o r m i x 、i b m 等公司都纷纷推出了相应的o l a p 决策支持产品，许多企业也纷 纷采用这些产品构建自己公司内部的决策支持系统来为本企业的决策方针制定 提供支持。 为了能够构建性能良好的1 2 3 1 9 城建服务热线o l a p 系统，非常有必要对 o l a p 实现技术进行深入的研究，同时很多其他的数据挖掘功能：分类、预测、 关联分析等，都可以与o l a p 操作集成，而数据立方体是o l a p 中最重要的元 素和概念，很多时候甚至可以认为0 l a - p 技术和数据立方体是等价的。本论文对 各种数据立方体技术进行了深入研究，并提出了一种改进的数据立方体结构，在 此立方体结构的基础上，对整个o l a p 系统进行了设计。 1 2 研究现状与思路 数据立方体的实现是目前o l a p 中最引人关注的问题。问题的焦点在于如何 平衡查询响应速度和资源消耗之间的矛盾。单独的计算每一个格节点并存储所有 的计算结果( 完整物化) 被认为是一种理想但不实用的方法一可以很快速的响 应查询但是计算和存储立方体完整格结构具有指数级( 相对于事实表的维度) 的 复杂度，这对于现代的企业大数据量的情况是极不适合的，并且随着维度的增加 这种情况会不断恶化。 为了克服这个缺点，科研人员已经提出了一系列的有效实现立方体的方法， 这些方法能够在一定程度上提高计算效率或者存储效率。这些方法有基于关系型 数据结构的，有基于多维数据结构的，还有基于图形结构的。有些方法采用预计 算技术或者外壳技术等来提高查询的响应速度，有的通过一系列算法对目标查询 确定需要物化的最佳方体，甚至有些方法为了追求高的计算和存储效率，对立方 体采用近似计算的方式，只计算和存储某个粒度以上的立方体，牺牲了准确性和 完整性。为了能够在一定范围内有效的减小立方体体积，提高存储效率，立方体 压缩技术也受到了广泛的研究，然而几乎所有这些方法都是语法上的，甚至上卷、 下钻的基本语义都在压缩过程中丢失了。不论是应答查询还是立方体查看，都需 要一个解压缩过程，导致了额外的计算开销，并往往需要额外的存储空间来存放 中间结果。 2 第一章绪论 数据立方体中单元格结构表示的语义关系很重要，可以为查询操作提供重要 的信息，保持语义的最直接的方法是将单元格的所有语义关系完整的存储下来， 但是实际上单元格规模非常庞大，语义关系通常十分复杂，使得实际操作起来很 不现实。近年来能够保持语义的数据立方体技术受到了很大关注，作为数据立方 体压缩存储技术的一种，由于其能够保持数据立方体结构中内在的上卷和下钻的 基本语义，因此不需要解压缩过程，可以直接进行查询，兼有缩小存储空间和提 高查询速度的优点。 上述这些方法都从某个方面对立方体的实现进行了研究，并在一定程度上兼 顾了资源消耗和查询响应速度，但是由于部分物化的方法本身对于响应速度的不 可预期使得其并不实用，不能保持语义的压缩方法会增加额外的计算开销，而现 有的保持语义的立方体技术在其格结构上面表现为结构复杂，对于语义表现不够 清晰，同时对于稀疏立方体的消除冗余方面压缩算法做的并不好，对于维度极高 的情况下没有明确的对算法的存储进行估算，使得算法实用较低。 y a n n i ss i s m a n i s 等提出的侏儒立方体【l j 和l a k sv s l a k s h m a n a n 等提出的商 立方体【2 j 是两种可保持语义的数据立方体。侏儒立方体采用前缀压缩和后缀合并 的方式，可以部分保证语义并实现存储空间的缩减，但是其在高维度大数据量情 况下，格结构复杂，语义关系不够清晰，事实表有所更新的情况下往往需要对后 缀合并进行重新计算，而由于复杂的格结构，重新计算往往涉及很多的递归操作， 并且立方体结构中仍然存在着冗余。商立方体使用覆盖划分技术，将数据立方体 中聚集值相同且上界相同的单元划分为等价类，对类与类的划分遵循凸划分和弱 一致性的方式，但是在保持语义的处理过程中，如果上界相同的单元被认等价类 只存储一次的话，会造成部分语义的丢失，同时按照它的逻辑结构来看类与类间 存在着后缀冗余，可以进一步的合并来减少存储空间。 本文遵循着语义立方体的潮流，对于现今影响力比较大的能够保持语义的立 方体实现技术进行研究，尤其是商立方体技术和侏儒立方体技术，在研究这些立 方体技术的基础上，提出了一种新的语义立方体，这种结构改变了侏儒立方体对 聚集数据的存储方式，能够在保持基本立方体语义的前提下，尽量的去除前缀冗 余、后缀冗余，节约存储空间，保证立方体的清晰的格结构，并且拥有比侏儒立 方体更高的存储效率和查询响应速度。对点查询和范围查询能够快速的返回结 果。对大数据量情况下的稀疏立方体具有良好的支持。 1 3 论文结构 本论文共分为六个部分，各章节的具体安排如下： 3 第一章绪论 第一章对论文课题的研究背景和意义进行了介绍，阐述了数据立方体的研究 现状和思路，同时对论文的整体篇章结构进行了说明。 第二章对o l a p 以及数据立方体的研究现状进行了全面综述，对当前数据立 方体实现方法按照不同的存储形式进行了归纳，并分析了这些方法的优缺点。在 这其中重点介绍了保持语义的立方体实现技术及其存在的问题，对能够大幅减小 立方体存储空间的冰山立方体技术也进行了研究。 第三章详细介绍了数据立方体中存在的各种冗余，在对侏儒立方体研究的基 础上设计了改进的数据立方体结构，提出了立方体的生成算法。 第四章描述了改进立方体结构的点查询和范围查询策略和算法，给出了这种 立方体结构优势的实例说明，提出了立方体结构的增量更新算法。 第五章设计了改进立方体的物理存储实现，并且为了查询的快速响应，对聚 簇优化算法进行了研究。结合1 2 3 1 9 系统的具体环境建立了o l a p 数据分析系统 的模型，将前面提到的立方体方法应用于实践中。设计了整个系统的工作流程， 并对部分功能模块和工作流程进行了详细介绍。通过原型系统的实现验证了该模 型的可行性和有效性。 论文最后一部分对全文的研究工作进行了总结，并陈述了目前研究中存在的 不足及未来需要努力方向。 4 第二章立方体实现技术研究 第二章立方体实现技术研究 数据立方体的实现是o n - l i n ea n a l y t i c a lp r o c e s s i n g ( o l a p ) q b 非常重要的过 程，但是它通常需要耗费大量的时间来进行。最简单直观的方法是单独的计算并 存储所有的结点，然而对于事实表的维度来说，由于具有对于事实表的维度来说 指数级别的时间和空间复杂度，在实际应用中是不可取的。为了克服这个缺点， 科研人员已经提出了很多方法。这其中包括基于关系型数据结构、多维数据结构、 图形数据结构的实现方法，甚至为了能够提高计算和存储效率提出了一些牺牲准 确性的算法，而仅仅计算和存储完整数据立方体的一个近似结果。 2 1 数据立方体基本概念 2 1 1 数据立方体的定义 当我们试图从大量无序数据中提取信息时，单纯的人工获取信息的方法会使 得我们的精力淹没在大量的信息中，需要工具来帮助我们找到那些重要的信息以 及探讨不同的情景。一份报表通常是数据的二维表示，是行和列构成的表格。在 我们只有两个因素要考虑时，这是可行的，但是现实世界中往往我们需要考虑的 是更复杂的情形。我们需要从不同的角度对数据进行探索，或者说需要不同粒度 的聚集汇总数据，能够自由的由粗粒度数据向细粒度数据转换视角，对数据的探 索可能也往往需要多级汇总的数据，而实现这些这些功能的工具就是o l a p ( o n - l i n ea n a l y t i c a lp r o c e s s i n g ) 。 尝试通过传统的s q l 在生产用数据基础上实现o l a p 是不现实的，o l a p 工具是基于多维数据模型的，通常这种模型将数据看作数据立方体的形式。数据 立方体首先是在1 9 9 6 年由j i mg r a y 等人定义的【3 】。最初的定义中数据立方体 ( d a t ac u b e ) 是当作一种操作符来使用的，是g r o u pb y 的多维扩展，定义为在 维度的所有组合上进行g r o u pb y 操作。随着研究的发展，慢慢的数据立方体成 为了c u b e ( d a t ac u b e 的缩略形式) 操作的结果集的代名词，从这个结果集中， 我们可以方便的浏览数据，从最详细的数据一直到各粒度的聚集结果，能够对某 些维度给予特定关注，也就说可以从不同角度探索数据，这也是o l a p 的本质所 在。 第二章立方体实现技术研究 数据立方体是一种允许从多维对数据建模和观察的数据形式，更通俗的讲可 以认为数据立方体是数据的一种组织形式，这种形式保存有数据多个维度的观察 信息，我们可以方便的采用不同的视角对数据进行查看，同时从一个视角到另外 一个视角进行转换。 数据立方体由维和事实共同定义。维是指人们对数据进行观察的角度，是视 图的某一属性。每一个维都有一个维表与之关联。多维数据模型围绕中心主题组 织，该主题用事实表示，事实是数值度量的。事实表包括事实的名称或度量，以 及每个相关维表的关键字。 数据立方体是二维表格的多维扩展，如同几何学中立方体是正方形的三维扩 展一样。“立方体”这个词让我们想起三维的物体，我们也可以把三维的数据立方 体看作是一组类似的互相叠加起来的二维表格。后面我们将介绍之所以称这种扩 展的结构为数据立方体的原因。 尽管我们经常把数据立方体看成是三维结构，但是数据立方体不局限于三个 维度。太多数联机分析处理( o l a p ) 系统能用很多个维度构建数据立方体，例 如，微软的s q ls e r v e r2 0 0 0a n a l y s i ss e r v i c e s 工具允许维度数最多可以为6 4 个， 虽然我们无法在空间或几何范畴想象出这么多维度的实体的样子。 作为对立方体的直观的描述，我们以天津市建委1 2 3 1 9 工单受理量汇总的简 化表2 1 ( 后文中很多例子都采用此表数据) 作为事实表：表中的区县( 后文中 将缩略为s ) 、涉及行业( 后文中缩略为t ) 、事件类型( 后文中缩略为e ) 即 为这个事实表的维度，它表示我们将分别从这三个方面来看待数据。数量为这个 事实表的度量，即这个观察主题的目标，从不同的角度观察最终所要获得的对象 ( 后文缩略为m ) 。 表2 1 事实表t ( 取自某个季度的数据) 区县涉及行业事件类型 数量( 百件) s 1t 2e l2 0 s lt 3e 25 0 s 2t le l7 0 s 2t le 26 0 s 3t 3e 1 1 0 在o l a p 中所说的数据立方体是n 维的( n = 2 ) ，并不特指我们所熟悉的三 维的情况。为了进行说明，我们考虑一个维度为2 的情况，事实上这种情形就是 6 第二章立方体实现技术研究 我们通常见到的数据报表。以事实表t 的数据为例说明，我们观察区县和事件类 型两个维度下的工单受理数量，通常可以得到如表2 2 的报表。 表2 2 事实表t 的区县和事件类型维度的2 d 方体 事件类型 区县 e l e 2 e 3 s 12 05 0 o s 26 007 0 s 31 000 这样显示的报表事实上为g r o u pb y 操作在区县和事件类型维度上的结果， 计算的度量函数为s u m ( m ) 。通常我们称这样的一个结果为一个方体( c u b o i d ) 。 但是这个仍然不符合我们通常情况下对立方体的印象，考虑三维的情况，我们根 据区县、涉及行业和事件类型来观察数据。正常情况下我们不可能按照事实表中 给定的方式直接呈现数据，因为他们是关系型的，数据是琐碎的、事务性的，不 是我们进行报表汇总的情况，但是如果我们按照表2 2 的形式进行呈现的话，至 少需要在行或者列上增加一个维度进行扩展，使得报表呈现出复杂的结构，不容 易对数据得到一个清晰认识，所以我们往往采用空间的形式呈现，即3 d 数据立 方体，如图2 1 所示。 t 1 t 2 t ( 涉及行奶 图2 1 事实表t 的3 d 方体 这种表现形式就是我们通常所认同的立方体结构，作为一种典型的表现形 式，很多文献都采用了这种形式，并且都不约而同的称之为方体( c u b o i d ) 或小 立方体，这也正是数据立方体名称的来历，并推广而统称这种由不同的维度 g r o u pb y 汇总的结果为立方体( c u b o i d ) 。 7 第二章立方体实现技术研究 但是往往现实中的情形的复杂程度远远超过三维的情况，很多企业的生产经 营所涉及的数据库维度都是n ( 1 p = 4 ) 维的，我们很难用简单的手段来呈现数据， 从数学上来说，对高维数据的描述不是一件容易的事情。一种最简单的呈现方式 可以对三维的数据立方体进行扩展，假如要考虑四维的情况，按照第四维的维值 分别构建对应的3 d 方体。按照这种方式下去，可以把任意的方体呈现出来。数 据立方体是对多维数据存储的一种比喻，这种数据的实际物理存储可能完全不同 于它的逻辑表示。 由于本文的研究重点并不在于高维数据的可视化显示，作为归纳，我们用一 种比较直白的方式呈现出来表2 1 对应的完整的数据立方体，如图2 2 ，按照不 同的聚集分别呈现： s 1t 2 e 1 2 0 s e l e c ts 。t 巴s l i ml m ) s 13 2f _ 25 0 f r o m t g r o u p8 vs 。t s 2t 1日7 0 乙 s 2 1 1e 1 6 0 s 3 t 2 f 11 0 sm s 1n2 0 s 1 e 25 0 s 2 h6 0 s 2e 37 0 s 3e 11 0 鲈 锄7 ：7 懈缓 s l7 0 s 21 3 0 s 31 0 图2 - 2 事实表t 对应的数据立方体 缪滚7i蠢缓 f 19 0 f 25 0 f 37 0 图2 2 中的每一个表对应一个视图，是g r o u pb y 操作在维度的不同组合即不 同汇总级上的执行结果。在语义上来讲，每一个视图代表我们从相应角度对数据 的一个观察。在o l a p 的研究文献中，每个视图都被称作一个方体( c u l x ) i d ) 。 给定维度的每个可能的子集都能产生一个方体，而这些方体放在一起按照方体间 定义的包含关系( 或者维度集的包含关系) 形成方体的格结构，这个方体的格称 作数据立方体( d a t ac u b e ) 。图2 3 显示了维度s 、t 、e 对应数据立方体的方 体格结构。 8 第二章立方体实现技术研究 旧( 顶点) 方体 l 曲方体 2 一d 方体 3 - d ( 基本) 方体 图2 3 维度s 、t 、e 形成的3 d 数据立方体 存放最顶层基本汇总的方体称为基本方体( b a s ec u b o i d ) ，通常对应着基本 的事妻表。上图中的3 - d 方体就是对应给定3 维的基本方体，它是对数据最细粒 度的汇总。0 一d 方体是对数据最高层次的汇总，也称为顶点方体( a p e xc u b o i d ) 。 这里我们将项点用a l l 标记，表示对事实表所有数据的最高汇总。 2 1 2 数据立方体中的基本操作 数据立方体能够支持的基本操作是o l a p 的功能得以实现的关键。典型的基 本多维分析操作有钻取( r o l l - u p 和d r i l l d o w n ) 、切片( s l i c e ) 和切块( d i c e ) 、 以及转轴( p i v o t ) 、钻过( d r i l la c r o s s ) 、钻透( d r i l lt h r o u g h ) 等。 钻取是改变维的层次，变换分析的粒度。它包括上卷( r o l lu p ) 和下钻( d r i l l d o w n ) 。 上卷( r o l l - u p ) ：上卷操作，有些文献中可能会称之为上钻( d r i l l u p ) 操作。上卷 是在某一维上将低层次的细节数据概括到高层次的汇总数据。主要有两种情况： 或者通过一个维的概念分层向上攀升或者通过维归约在数据立方体上进行聚集。 通常情况下维是具有概念分层的，例如某个事实表包含维度地址( a d d r e s s ) ，地址 的维层次为s t r e e t d i s t r i c t p r o v i n c e c o u n t r y ，是一个全序关系。沿着维 层次向上攀升，等于是站在更高的角度对数据进行观察，换一句话说，结果数据 立方体如果按c o u n t r y 而不是按p r o v i n c e 对数据分组就是一种上卷操作。当用维 归约进行上卷时，原立方体一个或多个维的维值将被泛化为特殊的a l l ，或者 说被删除。例如在图2 - 3 中，由涉及两个维度s 、t 的2 d 方体进行上卷操作到 1 d 方体s ，就是删除了t 维，导致整个工单数量按s ( 区县) 而不是s ( 区县) 9 第二章立方体实现技术研究 和t ( 涉及行业) 聚集，相对应的就是说g r o u pb y 只对s ( 区县) 汇总，这是 从更高的角度对数据进行观察。 下钻( d r i l l - d o w n ) ：下钻是上卷的逆操作，它由更高汇总级的数据得到更详细 的数据。它从汇总数据深入到细节数据进行观察，同样的或者通过个维的概念 分层向下探索或者通过增加观察的维来实现。沿着维层次向下探索，是站在更细 粒度对数据进行观察，对应上面的例子来说，结果数据立方体如果按p r o v i n c e 而不是按c o u n t r y 对数据分组就是一种下钻操作。当用添加维的方式进行下钻时， 原聚集视图中一个或多个泛化维值将被具体化为某一值。同样的例如在图2 3 中， 由1 d 方体s 进行下钻操作就可以得到两个维度s 、t 的2 d 方体，就是说这里 扩展了t 维，导致整个工单数量按s ( 区县) 和t ( 涉及行业) 而不仅仅是s ( 区 县) 聚集，相对应的就是说g r o u pb y 对s ( 区县) 和t ( 涉及行业) 汇总，从 而我们可以站在更详细的角度对数据进行观察。 切片和切块：切片和切块是在一部分维上选定值后，关心聚集数据在剩余维 上的分布。切片( s l i c e ) 操作在给定的数据立方体的一个维上进行选择，产生一个 子方体。例如对图2 1 显示的数据立方体按照维e ( 事件类型) 的切片操作，使 用条件e = ”e 1 ”，产生一个事件类型为”e 1 ”限定下的二维表( 当然也是一个广义 上的子方体) ，表中为涉及维度s 、t 的数据，如图2 4 所示。切块( d i c e ) 操作可 以看作是很多切片操作的组合，通过对两个或多个维执行选择，定义一个子方体。 s 1 喇 l e ls 2 s 3 02 0 6 0 o 0 1 0 t ( 觳昔亍韭) 图2 4 事实表t 的数据立方体在e = ”e l ”条件下的切片结果 转轴( p i v o t ) ：有的文献中也称为旋转( r o t a t e ) ，是一种可视化操作，它转动数 据的视角，即在表格中重新安排维的放置( 例如行列互换) ，提供数据完全相反 的表示方式。图2 5 给出一个对图2 - 4 所示的方体的转轴操作，这里维度s 和t 在一个2 d 切片上转动。当然转轴操作不仅仅用于2 d 方体，也包括转动3 d 数据立方体，或将一个3 d 立方转换成2 d 平面序列等操作。 1 0 第二章立方体实现技术研究 爱 妞n 篓r 2 f - 1 06 00 l 2 0o1 0 s 1s 2s 3 s ( 区县) 图2 - 5 转轴图2 4 的结果 其他o l a p 操作：有些o l a p 还提供其他钻取操作。例如，钻过( d r i l la c r o s s ) 执行涉及多个事实表的查询；钻透( d r i l lt h r o u g h ) 操作使用关系s q l 机制，钻 到数据立方体的底层，到达后端关系表。o l a p 还可能提供包括列出表中最高或 最低的n 项( t o pn ) ，以及计算移动平均值、增长率等统计功能。 2 1 3 数据立方体实现的难点 j i mg r a y 等人提出用c u b e l 3 1 操作符生成数据立方体，在多维空间中保存对基 本表聚集产生的实视图。多维数据分析的核心是有效地计算多个维集合上的聚集 ( 即g r o u pb y ) ，每一个聚集将产生一个方体，所有的方体的集合形成一个格 结构即为数据立方体。对于事实表2 1 ，其中有三个维度和一个度量值，可以由 该事实表计算的方体总数为三个维度的任意组合数，为2 3 = 8 个。可能的分组依 次为f ( s ，t ，e ) ，( s ，t ) ，( s ，e ) ，( t ，e ) ，( s ) ，( t ) ，( e ) ， ( 口) ) ，其中仍指的是不对任何维进行g r o u pb y ，相当于对事实表所有的数据进 行汇总。这些分组形成了具有格结构的数据立方体，如图2 3 所示。 对于不同的查询，联机分析处理可能会访问到不同的方体。因此，提前计算 数据立方体中的所有方体将是对查询最优的方法，看起来是一个不错的主意，不 仅带来最快速的查询响应，也避免了重复的进行聚集计算。然而这里面存在的主 要问题是，对一个具有n 个维属性的基本表的c u b e 操作相当于对该表的所有维 组合进行g r o u pb y 操作，如果没有概念分层的话，包括基本方体一共会产生的 2 n 个方体，所需计算时间和存储空间是呈指数级别增长的，特别的当维度具有 概念分层的时候，情况会变得更加严重。假如与这n 个维相对应的概念层数为 l i ，可能产生的方体总数将为： 方体总数= 兀( 厶+ 1 ) 公式( 2 1 ) i = 1 第二章立方体实现技术研究 其中加l 是因为包含虚拟的顶层a l l ( 方体中一个维度泛化到a l l 等于在g r o u p b y 聚集中去掉该维) 。我们注意到计算方体的聚集时每个维只有一个或零个概 念层次出现在方体中，也就是说出现在g r o u pb y 中，基于这样的观察得出上面 的公式【4 1 。假设某一立方体有l o 个维度，每维5 层，则可能产生的方体总数将 是5 1 0 印7 7 x 1 0 6 个。这将是非常庞大的，同时每个方体的大小取决于事实表中 每个维不同值的个数。最终随着维数、概念分层、不同维值数的增加，要存储 的立方体的大小将远远超过事实表的大小。这样在高维、大数据量的事实表情 况下，预计算并存储完全立方体是不现实的，会浪费大量的计算时间和存储空 间。 。一方面存储和计算所有的方体在效率上是不现实的；另一方面，o l a p 使用 人员可能对方体中的很多单元不感兴趣，比如图2 1 事实表t 的方体中，每个 单元都记录了一个聚集值，但是这些值中很多都是0 。稀疏方体就是指这种很 多方体单元都是空值的情况，如果一个立方体包含很多稀疏方体，则称该立方 体为稀疏立方体。稀疏立方体的大量单元对于o l a p 使用人员是冗余的，计算 并存储这样的单元完全没有意义，并且会带来对响应查询的影响。这些问题的 存在，使得我们需要更好的方法来计算并存储立方体，以便于在计算、存储效 率和查询效率上都能够得到一个最佳平衡。 2 2 数据立方体实现技术研究现状 2 2 1 立方体物化策略与主要技术路线 数据立方体的实现是目前o l a p 中最引人关注的问题。问题的焦点在于如何 平衡查询响应速度和资源消耗之间的矛盾。立方体的计算和存储过程和在一起 被称为数据立方体的物化( m a t e r i a l i z a t i o n ) 。给定一个事实表，数据立方体的 实现策略通常有三种选择【4 】： ( 1 ) 不物化任何方体。不预先计算除了基本方体( 也就是事实表) 以外的 任何方体，即不进行任何聚集操作，但是这样导致在应答查询时候才进行聚集 计算，有些可能会非常缓慢，不符合数据分析人员对响应速度的需求。并且某 些查询可能会被多次重复进行，在计算资源上浪费很大。 ( 2 ) 完全物化。预先计算所有方体，这是通常能够想到的方法，计算的结 果能够实现完整的方体的格结构，可以快速的对查询进行响应。但是由上文分 析可知，这样的策略一次的物化过程需要计算大量的方体，占用大量的计算资 源，并且需要远超过基本方体的海量存储空间，这样被认为是不可接受的。同 第二章立方体实现技术研究 时如果基本事实表有所更新的话，同样需要重复进行这个过程。另外立方体中 可能有大量的单元并不是o l a p 使用人员所关心的，这部分完全不需要占用计 算和存储资源。 ( 3 ) 部分物化。有选择的计算整个立方体的一个适当的子集，这种方法或 思路目前已经引起科研人员极大地兴趣，很多相当文献都是依据这个思路而展 开的，并由此引入了一个目前很重要的研究领域：物化视图的选择问题。最终 目的是使得选择物化的方体能够满足通常的o l a p 查询请求，不需要总是进行 重新计算，还能够尽量的节省存储空间。部分物化是存储空间( 计算时间) 和 响应时间二者之间的很好折中。 在确定了物化策略的基础上，数据立方体的实现过程实际上还包含两个主要 的问题【5 j ： ( 1 ) 如何对方体进行有效的计算。计算过程需要扫描整个事实表，并且在 维度的各个组合上应用聚集函数，如何优化计算过程是个很值得考虑的问题： 各个方体之间如何分派计算过程使得能够利用之前的聚集结果而不需要重复的 多次扫描事实表。这将影响最终立方体的生成过程。 ( 2 ) 如何合理选择数据立方体的子集进行存储。选择问题的合理解决可以 根据一些标准避免存储不符合要求或者不是o l a p 分析人员需要的数据，这个 是在立方体的实现和查询响应速度之间折中的关键所在。 当然数据立方体计算和存储选择问题在立方体实现过程中并不是割裂的两 部分，存储选择策略的选定可能直接影响方体的计算过程和计算方法，甚至很 多算法在实现过程中同时进行聚集计算和存储子集的选择。 上面的这些问题，科研人员在过去几年的研究中已经都从某种程度上进行了 尝试解决。下面部分将对过去科研人员的研究结果进行简要的介绍。 过去几年中，科研人员针对立方体的实现提出了一系列方法【5 】，这些方法有 基于多维数据结构的，有基于关系型数据结构的，还有基于图形结构的。有些 方法采用预计算技术或者外壳技术等来提高查询的响应速度，有的通过一系列 算法对目标查询确定需要物化的最佳方体，甚至有些方法为了追求高的计算和 存储效率，对立方体的采用近似计算的方式，只计算和存储某个粒度以上的立 方体，牺牲了准确性和完整性。为了能够在一定范围内有效的减小立方体体积， 提高存储效率，立方体压缩技术也受到了广泛的研究。 2 2 2 基于多维数据结构与图形数据结构的立方体实现方法 基于多维数据存储结构的立方体实现方法，把数据立方体存储为多维数组的 形式，支持数据的多维视图。它们将多维视图直接映射到数据立方体数组结构。 第二章立方体实现技术研究 使用多维数组存储数据立方体的优点是使用直接数组寻址，不需要空间存放查找 关键字，能够对预计算的汇总数据快速索引。主要不足在于使用多维数据存储， 在现实环境中，数据集以及生成的数据立方体通常是稀疏的，有很多聚集单元包 含空值或者不需要关心的值，存储利用率可能很低。 在这种情况下，应当使用稀疏矩阵压缩技术。于是一种被称为c h u n k - b a s e d m e t h o d s 6 的技术被提出用来解决立方体的稀疏性，在这种技术中，大部分包含 空值的单元被去掉，仅仅存储被称为c h u n k 的子数组阵列。a r r a y c u b e 就是这种 技术的结果。同样的在这种思路的激发下，为了改进以往的多位数据存储结构的 方法只能针对稀疏或稠密一种立方体的情况，m m - c u b i n g 算法【7 】被提出。 m m c u b i n g 算法把立方体利用立方体本身所包含的数据的分布信息来把格空间 分为两个子部分：一个稠密的子部分和一个稀疏的子部分。m m c u b i n g 算法本 身对稀疏性和稠密性的数据集的处理具备同样的高适用性。2 0 0 4 年提出的多维 文件结构c u b e f i l e t 引，提供了对多维数据结构的物理存储支持，可以被应用在任 何的多维数据结构计算生成算法中，本身具有根据方体维层次性建立的索引，在 o l a p 查询中可以显著的减少i o 开销。 基于图形的立方体实现技术采用某种图形结构或者树形结构作为辅助来快 速计算立方体以及减小对存储空间的需求，达到对高查询响应速度的要求。这方 面的研究包括基于r - t r e e s 的c u b e t r e e s 9 】方法，使用b t r e e s 的c u b ef o r e g s 1 0 】 方法，可以有效应答查询的s t a t i s t i ct r e e s t l l 】方法等。本文重点研究的侏儒立方体 和本文提出的立方体结构严格来说也属于基于图形的立方体范畴，可以看作是基 于树形结构的一种变种，借鉴了树形结构对方体的良好归纳和结构上的对冗余易 处理的特性，但是由于其最主要的特点的保持语义，所以将其归为语义立方体范 畴。 2 2 3 基于关系型数据结构的立方体实现方法 基于关系型数据结构的立方体实现因为可以利用关系数据库中的排序、散列 技术而备受关注。数据立方体可以很容易的存储与组织，可以方便的由以前计算 的聚集计算新的聚集，而不必由事实表计算。基于关系型数据结构的立方体实现 可以很容易的被整合到现在的主流关系型数据库服务器中，不需要花费太大努 力，数据分析人员可以很容易得到个强大的分析工具，这是基于多维数据结构 或者图形结构的数据立方体技术难以比拟的优势。通常很多立方体实现算法都可 以在关系型数据结构下获得良好性能，这些算法可能在提出时并没有明确指出是 基于关系型数据结构，但由于容易在关系型数据结构中实现，所以本文将此种算 法归于基于关系型数据结构的立方体实现算法中。 1 4 第二章立方体实现技术研究 g b l p t 3 】算法是对简单计算完整立方体算法的第一次改进优化：当计算某一个 方体时，使用立方体格结构中的已经计算的最小父母方体而不是多次重复的扫描 基本事实表。在如图2 3 所示的立方体格结构示意图中，从3 d 方体开始向上逐 渐计算各子方体的过程中，方体的计算规模会随之而减小，这是因为随着聚集层 次的增加，方体仅由下面层次的子方体计算，而子方体的数目远比方体所能覆