（计算机科学与技术专业论文）leolap中多维数据模型及聚合算法的研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：盆鹪日期：丝! ! ：兰：堡 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：垒三壁堕导师( 签名) ： 摘要 随着数据库技术的飞速发展，人们逐渐意识到信息的对于一个企业的重要 性，各大小企业都开始使用各种数据库管理系统来保存企业的数据。为了能够 有效的利用这些数据，人们通常会采用o l t p ( 联机事务处理) 技术不断地对这 些数据进行处理。随着数据的积累，企业决策人员希望能够更好地利用这些历 史数据，分析出其中的规律，用来指导企业的决策和发展，于是开始使用数据 仓库和o l a p ( 联机分析处理) 技术处理海量的历史数据，以得到有用的信息。 根据数据组织结构的不同，o l a p 可以分为r o l a p 和m o l a p 。其中r o l a p 是基于关系数据库的，对数据的处理依赖于关系表和s q l 查询。m o l a p 是基 于多维数据结构的，数据通常以数据立方体的形式组织，支持数据的多维视图。 目前大多数的o l a p 应用都是基于关系的r o l a p 系统，但是相比而言，m o l a p 具有更高的灵活性，能够提供快速的查询，让用户能够更方便的从多角度来观 察聚合的结果。 本文首先对m o l a p 的相关技术及国内外的研究现状进行了深入的研究， 然后选择一个可行的方案来设计实现l e o l a p 多维数据分析引擎。主要的研究 工作有以下几个方面： 1 对多维数据模型的建模与表示进行了充分的研究，结合实际的应用场景 提出了感兴趣的子立方的概念，建立了一个具有良好扩展性的通用的多维数据 模型。 2 通过对常见的数据立方体聚合算法进行研究，确定在l e o l a p 系统中 采用b u c 算法完成聚合计算的优势与可行性。然后介绍了b u c 算法，并基于 b u c 算法的特性，对b u c 算法进行了改进，在聚合计算过程中加入维度中的层 次信息和感兴趣的子立方，并在此基础之上用实现了多线程b u c 算法和分块 b u c 算法。 3 将改进后的b u c 算法应用到l e o l a p 系统中，通过实验对各种改进方 案的结果进行分析和比较。 关键词：多维数据模型，b u c ，联机分析处理，l e o l a p a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g y , p e o p l eg r a d u a l l yr e a l i z e d t h a tt h ei n f o r m a t i o ni s8 0i m p o r t a n tt oa r te n t e r p r i s e ，8 0c o m p a n i e sb e g i nt ou s ea v a r i e t yo fd a t a b a s em a n a g e m e n ts y s t e m s t os t o r et h ed a t ao ft h ec o m p a n y i no r d e rt o e f f e c t i v e l yu s et h ed a t a , p e o p l eu s u a l l yu s eo l t p ( 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 ) t e c h n o l o g yt o d e a lw i t ht h e s ed a t a w i t ht h ea c c u m u l a t i o no fd a t a , e n t e r p r i s e d e c i s i o n - m a k e r sw a n tt om a k eb e t t e ru s eo ft h e s eh i s t o r i c a ld a t a , a n da n a l y z et h el a w t og u i d ed e c i s i o n - m a k i n ga n dc o m p a n yd e v e l o p m e n tb e g a nt ou s et h ed a t aw a r e h o u s e a n do 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 ) t e c h n o l o g yt od e a lw i t l lt h ev a s ta m o u n t so f h i s t o r i c a ld a t at og e tu s e f u li n f o r m a t i o n o l a pc a nb ed i v i d e di n t or o l a pa n dm o l a pa c c o r d i n gt ot h ed i f f e r e n t o r g a n i z a t i o no ft h ed a t a r o l a pi sb a s e do nr e l a t i o n a ld a t a b a s e , a n dt h e d a t a p r o c e s s i n gd e p e n d so nt h er e l a t i o n a lt a b l e sa n ds q lq u e r i e s a n dm o l a p i sb a s e d o nt h em u l t i - d i m e n s i o n a ls t r u c t u r e , d a t aa r eu s u a l l yo r g a n i z e di nt h ef o r mo fd a t a c u b e s ，i tc a ns u p p o r tt h em u l t i d i m e n s i o n a lv i e w a tp r e s e n tm o s to l a pa p p l i c a t i o n s a r er o l a pw h i c hi sb a s e do nr e l a t i o n a ld a t a b a s e b u tc o m p a r e d 讥mr o l 他 m o l a pi sm o r ef l e x i b i l i t yt op r o v i d ef a s tq u e r y , a n da l l o wu s e r st oo b s e r v et h e a g g r e g a t i o nr e s u l t sf r o md i f f e r e n ta n g l e sm o r ee a s i l y i nt h i sp a p e r , f i r s t l y , d i s c u s st h er e s e a r c hs t a t u so fm u l t i d i m e n s i o n a lm o d e la n d o l 蝇a n dt h e ns e l e c taf e a s i b l es o l u t i o nt od e s i g na n di m p l e m e n tt h el e - o l a p m u l t i d i m e n s i o n a la n a l y s i se n g i n e t h er e s e a r c hw o r k sa r es u m m a r i z e da sf o l l o w s ： 1 m a k eat h o r o u g hs t u d yi nt h em o d e l i n go f m u l t i d i m e n s i o n a lm o d e l ，a n dp u t f o r w a r dt h ec o n c e p t i o ni n t e r e s t e dc u b e t h e ne s t a b l i s hag e n e r a lm u l t i d i m e n s i o n a l m o d e lw i t hg o o ds c a l a b i l i t y 2 b ys t u d y i n g t h ec o m m o nc u b ea g g r e g a t i o na l g o r i t h m , d e t e r m i n et h e a d v a n t a g ea n df e a s i b i l i t yo ft h eb u ca g g r e g a t i o na l g o r i t h mi nl e - o l a p t h e n i n t r o d u c et h eb u ca l g o r i t h m ，a n di m p r o v et h eb u ca l g o r i t h mb ya d d i n gt h el e v e l s a n di n t e r e s t i n gc u b et oa g g r e g a t ec a l c u l a t i n g ，a n dr e a l i z et h em u l t i t h r e a db u ca n d b l o c kb u c 3 a p p l yt h ei m p r o v e db u ca l g o r i t h mt ot h el e - o l a p , a n a l y z ea n dc o m p a r e t h ee x p e r i m e n t a lr e s u l t s k e y w o r d s ：m u l t i d i m e n s i o n a lm o d e l ，b u c ，o b 饵l e - o l a p 目录 摘要i a b s t r a c t i i 第l 章绪论1 1 1 课题研究的背景、目的和意义l 1 2 国内外研究现状2 1 3 多维数据模型的基本概念3 1 4 论文的组织结构5 第2 章l e o l a p 系统简介7 2 1l e o l a p 的体系结构7 2 2l e o l a p 的系统功能9 2 2 1 多维数据模型定义与解析9 2 2 2 聚合计算模块1 l 2 2 3数据存储模块l l 2 2 4查询模块1 3 2 3 本章小结1 4 第3 章l e o l a p 中多维数据模型的研究。1 5 3 1 多维数据模型的结构1 5 3 1 1模型中维的定义18 3 1 2模型中度量的定义1 8 3 1 3数据立方的定义1 9 3 2 多维数据模型的解析2 0 3 3 本章小结2 6 第4 章l e o l a p 聚合算法的研究及改进一2 7 4 1 常见立方体聚合算法2 7 4 1 1 多路数组聚集算法( m u l t i w a y ) 2 7 4 1 2 p i p e s o r t 和p i p e h a s h 算法2 9 4 1 3b u c 算法3l 4 2b u c 聚合算法的研究与改进3 3 4 2 1b u c 算法描述3 3 4 2 2b u c 算法改进之一3 8 4 2 3b u c 算法改进之二4 0 4 2 4b u c 算法改进之三4 6 4 3 实验和结果分析。4 6 4 3 1 引言4 6 4 3 2 实验环境4 7 4 3 3 实验一_ 4 8 4 3 4 实验二。4 9 4 4 本章小结。5 0 第5 章总结与展望5 2 5 1 工作总结5 2 5 2 下一步工作展望5 3 参考文献5 4 致谢5 7 附录：硕士期间发表的论文和参与的项目。5 8 武汉理工大学硕士学位论文 第1 章绪论 1 1课题研究的背景、目的和意义 随着计算机科学的快速发展和电脑在各行各业中的广泛应用，各行业中的管 理人员为了摆脱繁重的数据处理工作和制表业务，规范企业的管理工作，都开 始逐步引入信息化管理技术，随着时间的积累，数据库中的数据记录也越来越 多，特别是在银行、医院、大型超市等行业，每天都有大量的数据积累下来。 如何能够充分利用储存在数据库中的这些海量的历史数据，从中挖掘出对企业 发展有用的信息，对企业高层制定决策有着至关重要的作用【l 删。比如在银行业 中，不同的客户的价值是不同的，通过分析各种客户的盈利能力，银行可以制 定出不同的市场策略，同时，对客户群体进行分类分析，可以根据各类客户的 特点，提供具有针对性的服务和产品，这些都对银行保留已有客户和进一步扩 展市场有很大的帮助【4 】。对于医院来说，不仅能够预测医院应有的药物储备、合 理安排门诊药房工作时间，还可以根据每年流行病发病情况，给人们提供预防 措施。 从6 0 年代开始，联机事务处理( o l t p o n l i n et r a n s a c t i o np r o e e s s i n g ) j f l ：始发展 起来，那时候的数据量比较小，都是以表格形式存储，用户对它也只是进行简 单的查询操作。但随着数据的大量积累，更多的结果需要对数据进行分析处理 才能得到，o l t p 系统已经不能够满足终端用户的要求，用户在决策分析的时候， 需要对数据库中的海量数据进行大量的计算，才能得到用户想要查询的结果。 因此，关系数据库之父e e c o d d 提出了多维分析处理和多维数据库的概念，即 现在的联机事务分析( o l a p ) 。近年来，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 ) j 5 ，6 】 技术得到了充分的发展，在市场上已经出现了很多的o l a p 系统，现在常见的 o l a p 系统都是基于关系数据库的r o l a p ( 且pr e l a t i o n a lo l a p ) 7 ，它将待分析 的数据存储在普通的关系数据库中，然后根据应用的实际需要建立一些实视图， 将其也存放在关系数据库中。数据库中存放的都是大量的细节数据，缺少经过 处理的综合数据，由于r o l a p 系统的报表都是基于s q l 查询，当数据库中的 已有数据不能满足客户的查询要求时，需要进行大量的s q l 运算，系统的性能 受制于s q l 有限的功能和关系数据库的性能。再者r o l a p 系统还缺乏灵活性， l 武汉理工大学硕士学位论文 当报表的主题改变时，需要对原有的关系数据库进行大量的修改建立新的实视 图。m o l a p ( m u l t i d i m e n s i o n a lo l a p ) 贝j j 是将数据以立方体( c u b e ) 的形式存储进 来，所有的计算都在c u b e 生成的时候完成，用户还可以根据实际需要来定义需 要计算的c u b e ，提高了系统的查询效率和灵活性。同时m o l a p 系统的计算结 果可以不存储在关系数据库中，能够将o l a p 应用与底层数据库分离，降低了 系统的耦合度，有利于系统的维护和升级。然而由于国内对o l a p 的研究起步 比较晚，目前还没有成熟的m o l a p 产品。 本课题正是基于以上问题提出的，旨在利用多维数据库的思想，开发一个 m o l a p 数据分析引擎的原型一i ，e o l a p ( l i g l l t w e i g l a t e x p r e s so l a p ) ， 选用 一种有效的方法构建和存储多维数据模型，通过分析各种多维数据聚合算法， 选择一种合适的算法加以改进来完成系统中数据立方的预计算，并将计算的最 终结果组织存储。 1 2 国内外研究现状 到目前为止，学术界在多维数据库、数据立方体方面进行了很广泛的研究， 并且取得了很大的进展。并且针对立方体模型的建立、立方体模型的表示存储、 立方体的聚合计算、聚合结果的存储、聚合结果的查询等方面进行了大量的研 究，并发表了很多相关的论文。各个大公司也都看准了多维分析产品的市场， 开发出了自己的多维数据分析产品，将多维数据库技术应用到了各个领域。比 如：m m 、o r a c l e 、m i c r o s o f t 等。 i b m 的i b md b 2o l 蟑s e r v e r ，参考了h y p e d o ne s s b a s e 的功能，并结合了 d b 2 的可靠性、可管理性和访问能力；由于它包含了h y p e r i o ne s s b a s e 的o l 心 引擎，所有支持e s s b a s e 的应用程序都可以用在d b 2o l a ps e r v e r 上，而不用修 改。因而与其他o l a p 产品相比，赢得了更为广阔的市场。 o r a c l ee x p r e s s 是一个非常先进的计算分析引擎和数据高速缓存。它使用的 是多维数据模型，将普通电子表格中的行和列扩展成三维或者更多的维，数据 库中的数据也采用多维方式进行存储，使查询变得迅速。该服务器不仅支持多 维模型，而且还具备预测、分析、建模，及对数据库中的数据进行分析判断的 能力。同时，服务器还内置了用于财务、数理统计、时间序列管理等方面的功 能。o r a c l ee x p r e s s 具有强健性、伸缩性和基于应用的特性，并且能够支持多用 户同时访问，并为各种大型数据库提供数据完整性控制。同时，o r a c l e 公司的开 2 武汉理工大学硕士学位论文 放性策略允许那些安装了企业o l a p 系统的公司自由选择下层的关系型数据库、 前端用户界面和开发所使用的工具，从而获得很大的灵活性。 m i 趼o s o f l 公司随数据库s q l2 0 0 0 一起发布了o l a p 解决方案a n a l y s i s s e r v i c e ，之后又相继发布了m i c r o s o f ts q ls e r v 盯2 0 0 5a n 如i ss e r v i c e s 和 m i c r 0 rs q ls e r v e r2 0 0 8a n 如i ss e r v i e 鹤，a n a l y s i ss e r v i c 骼通过将客户端和服 务器技术组合在一起为客户提供数据挖掘和联机分析处理的功能，它允许用户 自己设计和管理包含从其他数据源( 比如关系数据库) 聚合而来的数据的多维 结构，然后使用各种行业标准的数据挖掘算法来完成相关的数据处理工作。 由于国内信息化建设起步相对较晚，对o l a p 的研究也还不够深入，并没有 开发出成熟的多维数据分析产品。同时，由于国外的这些产品已经比较成熟， 很多国内的企业通常都是直接使用国外已有的产品，但是由于用户习惯的不同， 在实际使用中，这些产品也不能完全满足国内企业的要求。 1 3多维数据模型的基本概念 平常我们所接触到的数据库，都是基于关系的关系数据库，它是数据表的集 合，每个表中都包含着一组属性，表中的数据都是以二维的形式表示，比如将 一个公司的销售数据制成一张关系表销售额( 时间，地点，产品，销售数量) ， 则可表示为： 表1 1 销售表 时间地点产品销售数量 2 0 1 0 年武汉电视 4 0 0 0 2 0 1 0 年武汉手机 5 0 0 0 但是用这种方式表示的数据，当数据量比较大的时候，就不利于从不同角度 来查看。如果我们把表的属性( 时间、地点、产品) 看成坐标轴，表中的属性 看成坐标轴上的点，立体空间中的点则是指标数据。这样就可以将表中的数据 以立体的形式展示出来，即用多维数据模型来表示( 如图1 1 所示) ，这样能够 对大量数据进行快速聚合和查询，并且从多个角度来展示给最终用户，以便得 出对企业管理决策有意义的信息。 3 武汉理工大学硕士学位论文 嬲糊2 0 虹 图1 1 三维立方体 在多维数据库中将数据模型看成立方体的形式，这里的立方体可以是3 维、 4 维、n 维。同时，多维数据模型中还引出了子立方、维、维分层、维属 性、度量、立方体物化等概念。 1 立方体：用三维或更多的维来描述一个具体的对象，其中的所有维度都 彼此垂直形成一个立体的结构。数据的度量值用各个维的交叉点上的值来表示， 它允许从多维的角度对数据建模进行查询和展示。 2 子立方：是立方体中的一个子集，是立方体中若干个维度的组合。对于 一个n 维的立方体，包含的子立方数为2 n 个。 3 维：是人们观察数据立方体模型中数据的特定的角度，是考虑实际问题 时的一类属性的集合( 比如产品维、时间维、地区维等) 。 4 维分层：某些维上的属性可以有不同的方法进行划分，每一种划分的方 法叫做一个维分层。( 如时间维可以分为年、季度、月份或者年、月份、日等) 。 5 维属性：维上的一个点，也就是一个具体的取值，用来描述数据元组在 某一个维中对应的位置。 6 度量：立方体的单元格中存放的数据，可以是一个数据，也可以是多个 数据，是要分析的主题的相关指标。 7 立方体物化：在多维数据模型中，为了能够提高系统的查询效率，通 常会提前对立方体进行计算，这种对数据立方体进行的预计算，就称为对立方 体的物化。 4 武汉理工大学硕士学位论文 在通常的立方体计算过程中，物化的方法主要有三种【s 】： 不物化：不对立方体中的数据进行任何的预先计算，在用户查询的时候临时 对原始数据进行计算，返回最后的结果。这种方法能够减少系统的存储空间开 销。当数据量比较小的时候，这种方法能够满足用户的需求，及时返回查询的 结果。但是当系统中的数据量很大的时候，在查询的过程中需要进行大量的计 算，系统的响应速度就很难满足用户的需求，无法满足大规模应用的需求。 完全物化：通过构建数据立方体，预先完成整个立方体的计算。这种方法显 然能够为系统提供最快的查询速度，但是由于现在的o l a p 系统中的数据量都 是非常大的，而在进行立方体聚合计算的时候，又会生成大量的聚合结果，这 样会需要很大的存储空间来保存计算的结果。同时，采用完全物化生成的子立 方中，并不是所有的组合都是有意义的，因此采用此种物化方法，会造成巨大 的空间浪费。 部分物化：部分物化就是由管理人员首先定义出某种选择的规则，在进行计 算的时候，根据计算规则来选取其中的一部分子立方完成预计算。这种方法为 系统的计算提供了更高的灵活性，管理人员可以根据业务需要来定义要计算的 子立方，能够很好的提高系统的运行效率。因此，现在的大多数应用中都是采 用的部分物化策略。 1 4 论文的组织结构 本文的主要研究目标：通过分析国内外的产品和技术，重点对多维数据模 型和聚合算法进行研究，选择一个可行的方案来设计实现l e - 0 l a p 多维数据分 析引擎。具体的论文组织结构概括如下： 第一章说明了课题研究的目的及意义，并介绍了o l a p 系统在国内外的使 用现状及多维数据模型的基本概念，最后给出了本文整体的组织结构。 第二章对l e o l a p 系统的体系结构及系统中各个模块的功能进行了总体 的介绍。 第三章介绍了l e o l a p 系统中多维数据模型的建立与表示的方法，并详细 描述了对模型的解析过程。 第四章首先介绍了几种常用的立方体聚合算法，并对他们的优缺点进行比 较，然后对b u c 算法进行了详细的介绍，并分成几步对它进行改进，用于本系 统中的立方体聚合计算部分，最后用多线程技术将其实现，提高了系统的效率。 s 第五章 出今后需要 6 武汉理工大学硕士学位论文 第2 章l e o l a p 系统简介 2 1l e - 0 l a p 的体系结构 l e o l a p 多维数据分析引擎是为了解决商业智能( b i ) 中传统的r o l a p 实时计算的响应速度无法满足客户的需求，而开发的一个多维数据分析引擎。 应用部署图如图2 1 所示： ； r e l a t i o n a ld b l 图2 1l e o l a p 的部署结构 7 s e r v e r l s e r v e r 2 s e r v e r 3 武汉理工大学硕士学位论文 整个系统主要分为三大部分，分别部署在三台服务器上。 b i r e p o r t 系统部署在服务器s e r v e r l 上，主要是面向最终用户的用户界面 部分，用户进入系统后，在系统界面上选择相应的操作，待执行完毕后，再将 查询结果以客户需要的形式展现出来。 l e o l a p 多维数据分析引擎部署在服务器s e r v e r 2 上，该部分主要负责数据 立方的计算、存储与查询，通过解析s e r v e r l 发送过来的指定，完成不同的操作。 这也是该系统中最核心的部分，本课题就是对该部分进行设计实现。 s e r v e r 3 上部署着关系数据库，也是整个系统的数据源，为s e r v e r 2 的计算提 供数据。 l e o l a p 多维数据分析引擎的主要功能如下： l 、接收b i r e p o r t 的x m l a 调用，解析发送过来的指令； 2 、访问关系数据库获取事实表和维表数据。在本课题中具体做法是 l e o l a p 读取多维数据模型的定义文件，解析出需要计算的立方体，用c + + 访 问关系数据库( 对于o r a c l e ，采用o c c i ，对于其它数据库采用o t l ，本课 题中选用的是o r a c l e 数据库) ，先采用关系数据库s q l 的g r o u pb y 操作初步进 行聚合，然后将处理后的数据取回，用于聚合计算； 3 、立方体c u b e 的聚合计算： 4 、计算结果存入b e r k e l e yd b 数据库； 5 、从b e r k e l e yd b 数据库加载立方体数据到c a c h e 中，供客户查询。 l e o l a p 多维数据分析引擎主要分为四大模块：模型定义模块、计算模块、 存储模块和查询模块。其系统结构图如图2 2 所示： 8 武汉理工大学硕士学位论文 图2 2l e - o l a p 系统结构 2 2l e - 0 l a p 的系统功能 程序启动后，由主控进程创建服务子进程，解析立方体定义文档，根据其中 定义的数据模型创建c a c h e 的结构，加载相关数据，然后监听客户端的请求。 当收到客户端发送过来的指令后，对其进行解析，然后调用相应的模块，执行 具体的操作。整个系统主要包括四大模块：多维数据模型定义与解析模块、聚 合计算模块、数据存储模块、查询模块。 2 2 1 多维数据模型定义与解析 在所有的o l a p 应用中，要处理的数据都是海量的，目前很多系统中的原始 数据已经超过了t b 级，要对如此庞大的数据量进行运算分析，实时计算显示已 经无法满足应用的需求。为了更快速的执行用户的查询，就需要对原始数据进 9 武汉理工大学硕士学位论文 行预计算处理，利用系统的空闲资源，把客户希望查询到的结果提前进行处理， 将计算结果存储在磁盘上，在用户查询的时候，就直接返回结果。要进行预计 算，首先要考虑的就是为待分析的目标进行建模，在系统运行的时候根据模型 中的定义来处理相关的数据，完成聚合操作。 在多维数据模型中主要涉及到的概念有：立方体、维、维分层、维属性、度 量等，其中着重考虑的是维和度量。维定义了一个事务的自然属性，是人们观 察事务的角度，维中的值都存储在与事实表关联着的维表中，记录所有与特定 维相关的所有信息。度量是用来记录需要考察的指标，与维的组合相对应，其 值都保存在事实表中。在模型定义的时候，应该将这些信息都记录到模型定义 文件中。 由于本课题中研究的l e o l a p 是一个通用性的多维数据分析引擎，应该能 够根据不同的用户提出的需求，不断完善和改进系统的模型，所以l e o l a p 中 的多维数据模型要有高度的独立性、灵活性和可扩展性，能够随着分析任务的 不同需求，建立不同的数据模型，而不影响后面的聚合计算部分。同时，对于 同一个主题的数据，不同的客户观察的角度和侧重点不同，如何在不用重新设 计数据模型的前提下，在一个模型定义文件中定义出不同的子模型来满足不同 客户的需求，这对提高系统的效率也是很有帮助的。 如果将数据模型用关系数据库中的表、视图和索引来定义，然后存储在关系 数据库中，需要额外建立多个表，而且由于立方体之间存在着层次关系，各个 关系表之间也会存在着复杂的连接，这样不仅浪费了存储空间，而且还会影响 数据的读取效率。 文献【9 】分别对数据仓库的多维数据建模进行了研究，从数学的角度来定义多 维数据模型，根据实际应用对常规的模型进行了改进，提出了新的多维数据模 型的建模方法。文献【l o l 提出了一种基于x m l 的o l a p 实现方式叫一o l a p ，利用 x m l 文档本身的层次结构来表示数据立方体中元组之间的聚集关系，能够以此来 有效地减小数据仓库的体积。文献【1 2 】【1 3 】贝l j 从多维模型的实现出发，用u m l 完成 数据立方的建模后将多维模型存储在x m l 文档中，并用r a t i o n a lr o s e 实现了 整个过程。在分析了相关资料中的做法之后，本课题参照开放源代码的r o l a p 服务器m o n d r i a n 系统和微软的m i c l o s o ts q ls e r v e r2 0 0 5a n a l y s i ss e r v i c e s 的做 法，最终选择使用x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 来定义和存储多维数据 模型，这样读取x m l 文件的时候只需要调用一个x m l 分析器即可。 x m l 还具备着以下的特点：x m l 是一种具备自描述能力的标志语言，可以 武汉理工大学硕士学位论文 很方便描述结构化数据、半结构化数据，x m l 能支持深层次的嵌套表达，可以 对结构很复杂的文档数据进行充分的描述，这些是传统的数据库所难以实现的； 另外，x m l 的语法简单、语义性很强，设计者可以自行设计有意义的标记；最 后，x m l 提供了丰富的编程接口，与其相关的技术也得到了快速的发展，比如： 结构验证技术s c h e m a 、文档解析和访问技术d o m 等，能够很方便地验证x m l 文档的合法性，并能利用d o m 技术对其进行解析。 2 2 2 聚合计算模块 由于l e o l a p 多维数据分析引擎处理的通常都是海量数据，聚合计算是整 个系统中最重要的部分，聚合计算的效率将直接影响着整个系统的效率，因此， 选择一个合适的算法来完成数据立方的聚合计算是至关重要的。在分析比较了 常见的几种立方体聚合算法之后，本课题选用了b u c 算法【l5 】来完成聚合计算， 并从几个方面对原始算法进行了改进，以提高聚合计算的效率。 在本课题中，聚合计算是作为一个单独的模块来完成的，当服务器端接收到 了计算命令之后，服务子进程创建一个新的计算进程，调用聚合计算模块，根 据数据模型的定义，从原始的关系数据库中加载待计算的数据，经过编码组织 后，利用聚合计算算法完成立方体聚合计算。 对于一个n 维的数据立方，其包含的不同的维度的组合( 子立方数) 为2 n 个，如果将其全部都计算出来，在用户查询的时候可以得到最快的系统响应时 间，但是随着维数和元组条数的增加，必然会导致数据爆炸，不但会浪费很大 的存储空间，系统的更新与维护也会变得困难。同时，在实际的应用中，并不 是所有的子立方都是有用的，如果在聚合计算过程中将2 n 个子立方的数据都计 算出来，显然是没有必要的。为了能达到查询效率和系统开销与维护之间的平 衡，在本课题中，引入了感兴趣立方的概念，用来表示一个n 维的数据立方体 中，有实际意义的、客户感兴趣的子立方。这样，在聚合计算过程中就只需要 根据模型定义文件中的定义，去计算感兴趣的子立方和它们所依赖的子立方， 这样不但能够提高系统的计算效率，还能够节约系统的存储空间。 2 2 3 数据存储模块 为了提高系统的查询速度，l e o l a p 采用了预计算技术，所有的计算结果 需要存储起来，这些海量数据的存储也会花费大量的时间，因此必须选用一种 1 1 武汉理工大学硕士学位论文 有效的方式来存储计算的结果。在本课题中，选用开源的内嵌式数据库管理系 统b e r k e l e yd b ( b d b ) 来存储聚合计算得到的结果。 b d b 是由美国的s l e e p y e a t 软件公司开发的一套开源的嵌入式数据库管理系 统，能够为应用程序提供高性能的、带事务保护功能的数据管理服务。同时， b d b 为多种计算机编程语言提供了简洁的a p i 接口。 b d b 主要有以下特性： ( 1 ) b d b 是开放源代码的，是一个高性能的数据库，在b d b 中对数据库的 所有操作都是对数据库中函数的调用，无论是通过网络连接的不同计算机之间 还是同一计算机中的不同进程之间，对数据库的操作都不需要有进程间的通讯， 因此大大提高数据库的读写速度。 ( 2 ) b d b 为各种计算机编程语言提供了简单易用的函数接口，这些语言包括 j a v a , c c + + ，p h p , p e r l ，p y t h o n ，t e l 等等，能应用到各种应用系统中。 ( 3 ) b d b 的函数库具有高度的可移植性。它能运行在几乎所有的u n i x 和 l i n u x 系统及其它们的变种系统之上，同时也支持w i n d o w s 以及很多种嵌入 式实时操作系统。b d b 能够应用到高端服务器，桌面系统，掌上电脑，网络交 换机以及其它的一些领域。 ( 4 ) b d b 具有强烈的可伸缩性。b d b 的函数库非常精简，只占用几百k 的空 间，但是它所管理的数据库的规模可以高达2 5 6 t b 。同时，它还具高强度的并 发性，允许数以千计的用户同时在同一个数据库上进行相关操作。 ( 5 ) b d b 数据库中所有数据的存储结构很简单，每个数据库都是作为一个单 独的文件存储在磁盘上，数据库中的每条数据元组都被称为一条记录，而每条 记录都是由两部分组成：关键字( k e y ) 和数据( v a l u e ) ，这两部分都可以是常见的简 单数据类型，比如整型、字符串等等，也可以是很复杂的结构，比如多个字段 的组合等，这些完全由程序员决定。 虽然o r a c l e 、m y s q l 等关系数据库在目前的数据库应用中占据着主流，但 是它们并不是在所有的应用场合都能发挥很好的性能。有的时候需要存储的数 据并没有复杂的结构，仅仅只需要将数据用类似普通文件的形式存储在磁盘上， 此时就不需要安装像关系数据库那样庞大的数据库管理系统，这样还可以简化 应用程序中数据库部分的设计。b d b 数据库正是基于这样的考虑，为了满足简 单的数据库需求而设计出来的。 那些主流的关系数据库在处理数据结构复杂的数据时能够占据优势，但在当 数据结构比较简单，对存储没有太多的要求的时候，b d b 数据库的优势就会很 武汉理工大学硕士学位论文 好的显示出来。b d b 提供的a p i 调用都很简单，对数据库的操作都是由函数来 直接实现，应用程序与数据库之间不需要有进程通信，同时还能够避免关系数 据库中对s q l 语句的解析，这样就能在很大程序上节省操作数据库的时间，能 够提高读写速度，对于一个对性能要求很高的应用程序来说，这一点是至关重 要的，能使应用程序变得更加高效。 在本课题中，所有的数据都是维度和度量值的组合，在存储的时候可以将维 度的组合作为数据库中的k e y 值部分，将度量的组合作为v a l u e 部分，每一个子 立方的数据存成一个数据库文件。这样就能够提高存储和后期查询的效率。 2 2 4 查询模块 由于l e o l a p 多维数据分析引擎最终还是要面向客户，为客户提供查询分 析服务，所以查询模块的性能直接影响着最终的用户体验。为了加快系统的查 询速度，几乎所有的o l a p 应用都会采用预计算技术【。7 1 ，预先计算出部分或者 全部的数据立方，并将结果存储到磁盘中，尽可能地避免进行复杂的实时计算 1 8 , 1 9 。然而随着内容容量的不断扩大和成本的降低，服务器上配备的内存也越来 越大，为了能够充分的利用大容量的内存，文献 2 0 _ 1 】中提出了基于内存的数据 立方查询方法，采用一个基于二级索引的内存数据结构来存储聚合结果中的最 细粒度的小方数据，能够有利于快速响应用户的查询。本课题在采用预计算的 基础上，对常用的数据元组进行内存中的实化。 本课题中所采用的方法是在内存中创建了一个三级的c a c h e 结构，第一级存 储数据立方体的名字，第二级存储感兴趣的子立方的名字的编码，第三级用 h a s hm a p 结构存储感兴趣子立方中的具体的数据，对每一个h a s hm a p 都预先 分配了一定的内存空间，用来保存该子立方中常用的数据元组。其内存结构如 图2 3 所示： 武汉理工大学硕士学位论文 h a s h m a l ) 图2 3 内存c a c h e 结构 在系统启动的时候，就根据多维模型定义文件中的描述在内存中建立c a c h e 结构，加载部分数据，然后等待用户的查询请求。服务器端接收到用户查询命 令后，通过解析查询命令，判断所查立方体是否已经定义，如果c a c h e 中没有 该立方体的信息，则返回错误提示。否则，找到该立方体，从c a c h e 结构中的 h a s hm a p 里面取出需要查询的数据，对于c a c h e 中没有保存的数据，再从磁盘 上的数据库中读取，在读取过程中，将新记录保存到h a s hm a p 结构中，如果总 的记录大小超过了分配给当前立方体的h a s h m a p 结构的空间，则调用内存淘汰 算法删除部分数据元组。待所有的数据读取完毕后，再将最终结果组织起来返 回给前端客户。在系统运行的同时，统计每个子立方体中数据的查询命中率， 动态调整给每个子立方分配的内存空间，对于查询命中率太低的子立方，则需 要适当加大它的内存空间，对于查询命中率过高的子立方，则可适当减小分配 给它的内存空间，最终达到一个平衡状态。这样不但可以提高内存的使用效率， 还可以提高系统的查询效率。 2 3 本章小结 本章首先对l e o l a p 多维数据分析引擎进行了总体的介绍，并给出了系统 的总体设计图。然后分小节介绍了系统各个模块的功能和实现的基本原理。在 本文中将要重点讨论多维数据模型定义与解析模块和聚合计算模块。 武汉理工大学硕士学位论文 第3 章l e o l a p 中多维数据模型的研究 3 1多维数据模型的结构 常用的多维模型有星形