（计算机应用技术专业论文）基于rolap的数据仓库实现图选取算法研究.pdf

摘要 数据仓库是一个面向主题的、集成的、相对稳定的且随时问不断变化的数据集合， 用来支持管理人员的决策。它是面向查询、分析用户的，其中存储着大量的多维历史数 据。用户提交的查询语句通常是需要搜索大量的数据、涉及到多个数据表的复杂的连接 查询语句。面对这种复杂请求，数据仓库必须给予快速响应。实视图技术就是提高数据 仓库查询响应性能的有效方法。然而实视图需要占用系统空间来存储，并且需要花费系 统代价来维护。因此，在有限的空间内选取一个适当的实视图集来提高数据仓库的查询 响应性能就成了一个重要的研究课题。它通常需要先使用静念实视图选取算法得到一个 实视图集合，然后再使用动念实视图选取算法对生成的集合进行动态调整，以保持它的 时效性。 本文分别从静态和动态两个方面对实视图选取算法做出改进。前者在引入接收概率 的基础上，提出基于改进型遗传算法的静态实视图选取算法。它依一定的概率来接受适 应度变低的个体，这样可以给遗传算法一个跳出局部最优的机会。此外，它在个体进行 遗传操作之后立即计算其适应度，并对其进行处理，使得算法能够沿着指定的方向进行 搜索。实验结果表明，该算法不仅解决了经典遗传算法的“早熟”问题，而且避免了经 典遗传算法盲目搜索的不足。 后者在给出实视图相似度的基础上，提出基于聚类的动念实视图选取算法。它首先 对实视图进行聚类，然后对聚类后的实视图集进行动态调整，从而消除了动态选取算法 的“抖动”性。实验结果表明，该算法不仅从整体上提高了查询响应的性能，而且降低 了更新实视图时所花费的计算代价。 关键词：数据仓库，实视图，静态实视图选取算法，动态实视图选取算法 r e s e a r c ho fm a t e r i a l i z e dv i e ws e l e c t i o na l g o r i t h m i nd a t a 厮lr e h o u s eb a s e do nr o l a p z h a ow e i ji n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rd u a ny o u x i a n g a n da s s o c i a t ep r o f e s s o rg o n ga n a b s t r a c t ad a t aw a r e h o u s ei s 巩b yd e f i n i t i o n ，s u b je c t o r i e n t e d ，i n t e g r a t e d ，n o n - v o l a t i l ea n d t i m e v a r i a n t r e p o s i t o r y o fd a t at o s u p p o r t d e c i s i o nf o rm a n a g e ni ts t o r e sm a s s i v e m u l t i d i m e n s i o n a lh i s t o r i c a ld a t aa n di ti sf o rr o g a t o r ya n da n a l y t i c a lu s e r t h eq u e r y s t a t e m e n tw h i c hu s e rs u b m i t si su s u a l l yn e c e s s a r yt os e a r c hm a s s i v ev o l u m ed a t aa n di n v o l v e c o m p l e xm u l t i t a b l ej o i no p e r a t i o n a st ot h e s ec o m p l e xq u e r i e s ，d a t aw a r e h o u s em u s tg i v e f a s tr e s p o n s e i ti sw e l lk n o w nt h a tm a t e r i a l i z e dv i e wt e c h n o l o g yi sa ne f f e c t i v em e t h o dt o e n h a n c eq u e r yr e s p o n s ep e r f o r m a n c e h o w e v e r , m a t e r i a l i z e dv i e wn e e d st oo c c u p ys y s t e m s p a c et os t o r e ，a n di ts p e n d ss y s t e mc o s to nm a i n t a i n i n g t h e r e f o r e ，h o wt oc h o o s e a n a p p r o p r i a t eg r o u po fm a t e r i a l i z e dv i e wi nt h es p a c ec o n s t r a i ni s a ni m p o r t a n tr e s e a r c h t o p i c g e n e r a l l ys p e a k i n g ，i tn e e d st oa p p l ys t a t i cm a t e r i a l i z e dv i e ws e l e c t i o na l g o r i t h mt o o b t a i n i n gam a t e r i a l i z e dv i e ws e t ，a n dt h e na p p l yd y n a m i cm a t e r i a l i z e dv i e ws e l e c t i o n a l g o r i t h mt oa d j u s t i n gt h e s e tf o ri t st i m e l i n e s s t h ep a p e rm a k e si m p r o v e m e n tt om a t e r i a l i z e dv i e ws e l e c t i o na l g o r i t h mf r o mt w o a s p e c t s ，s t a t i ca n dd y n a m i c ，r e s p e c t i v e l y t h ef o r m e rp r o p o s e s s t a t i cm a t e r i a l i z e dv i e w s e l e c t i o na l g o r i t h mb a s e do ni m p r o v e dg e n e t i ca l g o r i t h mw i t ht h eb a s eo fi n t r o d u c i n ga c c e p t p r o b a b i l i t y i ta c c e p t st h ei n d i v i d u a lw h o s ef i t n e s sb e c o m e sl o w e rw i t hac e r t a i np r o b a b i l i t y , a n dg i v e sg e n e t i ca l g o r i t h ma no p p o r t u n i t yt oe s c a p el o c a lo p t i m u ma n da c h i e v eg l o b a l o p t i m u mf i n a l l y i na d d i t i o n ，i tc a l c u l a t e si m m e d i a t e l yi n d i v i d u a l f i t n e s sa f t e r g e n e t i c o p e r a t i o na n dp r o c e s s e si n d i v i d u a l ，w h i c hm a k e si ts e a r c hi na s s i g n e do r i e n t a t i o ni n s t e a do f b l i n ds e a r c h t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h ei m p r o v e dg e n e t i ca l g o r i t h mn o to n l y s o l v e st h e “p r e m a t u r e ”p r o b l e mo fc l a s s i cg e n e t i ca l g o r i t h m ，b u ta l s oa v o i d st h eb l i n ds e a r c h o fc l a s s i cg e n e t i ca l g o r i t h m w i t ht h eb a s eo fp r o p o s i n gm a t e r i a l i z e dv i e ws i m i l a r i t yf u n c t i o n ，t h el a t t e rp r o p o s e s c l u s t e r i n g - b a s e dd y n a m i c m a t e r i a l i z e dv i e ws e l e c t i o na l g o r i t h m i t f i r s t l y c l u s t e r s m a t e r i a l i z e dv i e w , a n dt h e nd y n a m i c a l l ya d j u s t sm a t e r i a l i z e dv i e ws e t s o ，i te l i m i n a t e st h e j i t t e r ，w h i c hd y n a m i c m a t e r i a l i z e dv i e ws e l e c t i o n a l g o r i t h mg e n e r a l l yh a s t h e e x p e r i m e n t a lr e s u l ts h o w st h a tt h ea l g o r i t h mn o to n l yi m p r o v e st h eo v e r a l lq u e r yr e s p o n s e p e r f o r m a n c e ，b u ta l s or e d u c e st h ec o m p u t a t i o n a lc o s tw h i c hw i l lb es p e n td u r i n gu p d a t i n g m a t e d a l i z e dv i e w k e yw o r d s ：d a t aw a r e h o u s e ，m a t e r i a l i z e dv i e w , s t a t i cm a t e r i a l i z e dv i e ws e l e c t i o n a l g o r i t h m ，d y n a m i cm a t e r i a l i z e dv i e ws e l e c t i o na l g o r i t h m 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他入已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：盘融盈 闩期：) 。7 年岁月) 箩同 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盘融鱼 指导教师签名： 只期： 同期： 5 , e l 】i ：t 厂月2 署，同 ， 中固钉油人学( 挣东) 颐i ：学位论文 第一章绪论 1 1 课题的提出及研究意义 在市场激烈竞争的今天，任何一个企业的决策者必须能够从有效收集到的数据中获 得有价值的信息，并用之于决策，使企业获得最大的效益和竞争优势。传统的数据库 ( d a t a b a s e ) 虽然在数据共享、数据与程序的独立性、维护数据的一致性和完整性以及数 据的安全保密方面已很成熟。但随着应用的发展、数据量的急剧扩大、用户的需求越来 越复杂，传统的数据库技术已经无法对数据的合成、分析和综合提供强大的功能，用户 的决策分析需要对关系数据库进行大量计算才能得到结果，所以数据仓库技术应运而 生。它面向分析型环境，对企业的分析决策提供了强有力的支持1 1 】。 数据仓库概念的提出者及相关技术的主要倡导者是美国著名信息工程学家w i l l i a n i n m o n 博士。9 0 年代初，i n m o n 根据数据库技术己趋于成熟化，结合市场经济发展之需 首次提出了数据仓库概念的一个表述。他提出的数据仓库的解释是：一个数据仓库通常 是一个面向主题的、集成的、不同时间的、稳定的数据的集合，用以支持经营管理中的 决策制定过程i 2 | 。 与数据仓库紧密联系在一起的是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 ) ，它是基于数 据仓库的信息分析处理过程，是数据仓库的用户接口部分，最早由e e c o d d 提出【3 1 。根 据o l a p 委员会的定义，o l a p 是使分析人员、管理人员或执行人员能够从多种角度对 从原始数据中转化出来的、能够真正为用户所理解的、并真实反映维数据特性的信息进 行快速、一致、交互地存取，从而获得对数据更深入了解的一类软件技术。o l a p 的目 标是满足决策支持或多维环境特定的查询分析需求，它的核心技术是“维 的概念。因 此，o l a p 也可以说是多维数据分析工具的集合【4 1 。 建立数掘仓库的目的是为决策支持提供服务! 数据仓库中存储的数据是面向决策分 析的、经过提炼加工后的数据集合，这种数据的存储结构为o l a p 实施提供了理想的环 境；而o l a p 作为一种多维查询和分析工具，是数据仓库功能的自然扩展，也是数据仓 库中的大容量数据得到有效利用的保障。 o l a p 一般以两种方式组织数据。一种是建立专用的多维数据库系统，称之为 m o l a p 。另外一种是利用现有的关系数据库技术来模拟多维数据，称之为r o l a p 。其 中m o l a p 能够提供较快的查询响应速度，但是在进行数据更新时通常需要重构多维数 组，额外开销比较大。另外，在多维数组非常稀疏时，即使使用数据压缩技术也可能浪 第一章绪论 费大量的磁盘存储空间。这使得在现有的关系型数据库基础上探索数据仓库的有效实现 成为一种必然。目前，大多数情况下还是使用r o l a p 技术来对数据仓库中的数据进行 分析处理的【5 】，而且已经出现了一些提高r o l a p 查询响应速度的方法，如新的索引技 术删、实视图技术等：r o l a p 查询语句通常都是需要搜索大量的数据、涉及到多表连 接的复杂查询语句【9 】。面对用户的这种复杂请求，数据仓库能以较少的时间对查询给予 响应确实是一个不小的挑战。采用实视图技术来提高数据仓库的查询响应性能就是其中 的一种解决方案。 传统上的视图是数据库中一个或多个基本表导出的表，其记录没有存储在数据库 中，而是在需要时根据视图定义计算出来。而实视图( m a t e r i a l i z e dv i e w ) 是物理上存储视 图定义的数据，在数据仓库中，它是一张实实在在的表。数据仓库可以简单看成一系列 的关系表和需要周期性进行维护的实视图。对于大规模的数据集，分析用户希望能够迅 速得到查询结果。在查询频率很高，而且基本表很复杂的情况下，每次执行查询都重新 计算基本表的代价是十分高昂的。一个很有效的方法就是利用数据仓库中存放的大量的 实视图，在用户进行查询处理时，无须计算复杂的基本表，而是利用这些实视图就可以 快速得到查询结果，比普通的查询方法快得多。其本质是通过预计算的方式来提高数据 仓库系统对用户查询的响应速度。然而视图的实体化既需要占用可观的磁盘空间，又需 要耗费大量的系统资源以对其进行维护，所以如何选取一组合适的视图集加以实体化， 从而使系统能够利用有限的资源，最大限度地提高数据仓库系统对用户查询的响应速度 成为一个关键问题。该问题已经被证明是n p h a r d 问题【1 0 1 ，而且它直接影响到数据仓库 的查询响应性能。 综上，本课题在比较分析各种算法的基础上，分别对静态实视图选取算法和动态实 视图选取算法做出改进，提高了实视图选取的效率，并从整体上提高了数据仓库的查询 响应性能。 1 2 国内外研究现状 ( 1 ) 国外研究现状 1 9 9 7 年h g u p t a 给出了实视图选取的理论框架，提出在空间限制下，使查询响应时 间和视图维护代价总和最小的实视图选取代价模型，同时使用了贪心算法解决这个问题 【1 0 1 。它检查- - d , 部分状态空间，使实视图满足空间的条件限制，达到了时间要求，但这 种方法性能不是很好。后来，h g u p t a 又提出在维护代价一定的条件下，使总查询时间 2 中固“油人学( 华东) 颂l j 学位论文 最小的代价模型，给出a 枣算法来解决这个问题i l 。 1 9 9 7 年j y a n g 另辟蹊径，给出了一个结构和算法，其基本思想是依据多视图处理 计划m v p p ( m u l t i p l ev i e wp r o c e s s i n gp l a n ) ，通过合并可以“共享”的公共子视图得到最 好的m v p p ，然后从m v p p 中选取视图实体化i l2 1 。后来在2 0 0 0 年m i n d u l s k a 提出这个 结构和算法的几点限制：首先，分组属性在查询树中不明确；其次，确认“共享”结果 的方法在某些情况下不总是有效的。因此，对此扩展，扩充了查询树的定义，解决了包 含不同维、不同粒度上查询共享结果的问题，证明属性级别可提高共享结果的确认，从 而提高实视图选取的性甜j 。 1 9 9 8 年s l i g o u d i s t i a n a s 等将实视图选取作为数据仓库的构造问题，将其描述为基 于视图和查询的状态空问搜索算法，给出个新的贪心算法r - g r e e d y 算法，通过实验 评定表明在访问有限状态空间下，其性能较好【1 4 1 。 1 9 9 9 年c z h a n g 等人将遗传算法运用到了实视图选取问题中，并且显示出了比贪婪 式算法和启发式算法更好的求解能力【1 5 】。2 0 0 1 年他们又对算法做出了改进，提出了一 种混合的遗传算法，该算法分为3 个步骤。首先对查询进行优化，其次从多个全局的执 行计划中选取一个最好的全局执行计划，最后按照这个全局执行计划选取实视图集。实 验结果表明，该算法具有更好的实视图选取性能【| 6 】。 实视图的动态管理是一个比较新的研究方向，1 9 9 9 年d t h e o d o r a t o s 提出了一种基 于a ov i e wg r a p h 的动态实视图管理算法，但该算法的描述主要是基于图上作业的，并 且没有提供关于算法有效性的证明【1 7 1 。2 0 0 3 年c z h a n g 提出了一个基于m v p p 模型( 相 当于a ov i e wg r a p h 模型的一个子集) 的实视图动态管理算法，同样在这篇文章中作者 也没有给出关于其所提出算法的有效性的证明【阍。 ( 2 ) 国内研究现状 2 0 0 3 年张晓辉等学者结合启发式算法的快速收敛能力和遗传算法的全局优化能力， 提出了两层实视图的求解方案。这种分层的结构使得复杂问题简单化了，它先使用启发 式算法快速地生成m v p p 集合，然后再用遗传算法在m v p p 集合中进行实视图选取， 最终获得实视图集合【1 9 1 。 2 0 0 4 年张柏礼等学者提出了实视图选取的预处理算法p m v s ，其中包括用户查 询集动态调整算法q s d m 、候选视图格构造算法c v l c 和候选视图筛选算法c v f ，该 算法在预处理过程中对视图数量进行在线压缩，从而降低了静态算法的视图空间搜索代 价和时间复杂度【2 0 1 。 3 第一章绪论 2 0 0 6 年张柏礼等学者又提出用动态c a c h e 优化算法来处理实视图的选取问题。它在 保持静态算法获取最优实视图集能力的基础上，将c a c h e 机制直观、快速的动态特性结 合进来，以提高数据仓库的动态自适应性能。其实质是动态选取策略和贪心算法的结合。 并在c a c h e 机制具体实现中提出了一种新颖的空间申请方法，可以充分利用系统剩余空 问提高查询响应性能。同时算法还可以在一定程度上克服静态实视图集存在的空间性 能饱和效应( s p a c e - p e r f o r m m l c es a t u r a t i o ne f f e c t ，s p s e ) ，使通过增加实空间进一步提高数 据仓库对查询的响应速度成为可能【2 1 1 。 2 0 0 6 年周丽娟等学者在a n d o rv i e wg r a p h 模型的基础上提出用遗传算法来处理 实视图的选取问题。实验结果表明遗传算法表现出了很好的性能【2 2 1 。 2 0 0 7 年王自强等学者在此基础上对遗传算法进行进一步的改进。首先运用一个基于 单位空间最大收益值的预处理算法来生成初始解。然后，该初始解采用多种优化策略进 行提高，这些优化策略包括基于改进的锦标赛和精英选取相结合的选取算子、基于半均 匀交叉算子及自适应变异算子。并且在进化过程中产生的无效解用损失函数加以修补， 从而提高了遗传算法的求解能力【2 3 j 。 1 3 主要研究内容 数据仓库实视图选取的一般思路是：先使用静态实视图选取算法得到一个实视图集 合，为了使该集合始终保持较好的时效性，随后还需要启用动念实视图选取算法对其进 行调整。最终使得数据仓库系统的查询响应性能有所提高。 本文在对数据仓库、r o l a p 技术及实视图选取算法作了深入研究之后，在数据仓 库静态实视图选取算法及动态实视图选取算法方面主要作了以下几个方面的工作： ( 1 ) 深入研究和分析了数据仓库和r o l a p 技术的研究现状。 ( 2 ) 深入研究各种实视图选取模型，这是迸一步研究各种实视图选取算法的基础。 ( 3 ) 深入分析各种实视图选取算法，并对其进行比较，得出各种算法的优缺点。 ( 4 ) 深入研究各种静态实视图选取算法，提出改进型遗传算法，并将其运用在实视 图选取问题中，以提高搜索的效率。 ( 5 ) 深入研究各种动态实视图选取算法，提出基于聚类的动态实视图选取算法。它 先对实视图进行聚类，然后再对聚类后的实视图集进行动态调整，从而消除了“抖动” 性。实验结果表明，该算法不仅从整体上提高了查询响应的性能，而且降低了更新实视 图所花费的计算代价。 4 中国白油人学( 华东) 硕i ：学位论义 1 4 论文组织结构 本文围绕数据仓库和基于r o l a p 的数据仓库实视图选取算法展丌论述，其组织结 构如下： 第一章绪论。 主要介绍本课题的提出、目的、意义，以及当前数据仓库实视图选取算法的国内外 研究现状，并提出数据仓库实视图选取算法的研究内容与思路。 第二章数据仓库。 本章首先对数据仓库做了系统的介绍，包括数据仓库的定义、特点及其体系结构。 然后介绍了r o l a p 数据仓库的数据组织形式，这也是进行多维数据分析的基础。最后 介绍了常用的0 l a p 分析操作。 第三章实视图选取算法。 本章首先介绍了目前比较流行的实视图选取模型，在此基础上对现有的静念选取算 法和动态选取算法分别进行了分析研究，并对这几个算法的优缺点进行了比较。 第四章基于改进型遗传算法的静态实视图选取算法。 针对经典遗传算法存在“早熟”的不足，本章提出了改进型遗传算法。它依据一定 的概率来接受适应度变低的个体，这样可以得到跳出局部最优的机会。同时本章还提出 在个体进行遗传操作之后立刻计算其适应度，并对其进行处理，使得算法能够沿着指定 的方向进行搜索，而不是盲目地进行搜索。最终将该算法用于实视图选取问题，实验结 果表明该算法确实比经典遗传算法具有更好的搜索能力。 第五章基于聚类的动态实视图选取算法。 针对动念选取算法普遍存在“抖动 的不足，本章在给出实视图相似度的基础上提 出了基于聚类的动态实视图选取算法。它首先对实视图进行聚类，然后对聚类后的实视 图集进行动态调整，从而消除了动态调整算法的“抖动”性。实验结果表明，该算法不 仅从整体上提高了查询响应的性能，而且降低了更新实视图时所花费的计算代价。 总结 总结本文的工作和创新点，对于提出的实视图选取算法进行归纳、总结，同时针对 本课题中出现的未完成的问题做下一步的规划。 5 第二章数据仓库 第二章数据仓库 2 1 数据仓库定义及特点 传统的数据库在联机事务处理( 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 ) 中取得了巨大 的成功，但是基于事务处理的数据库在帮助决策分析时却碰到了很大的困难。主要原因 是传统数据库的处理方式与决策分析中的数据需求不相称，导致传统数据库无法支持决 策分析活动。数据仓库在这种情况下应运而生。 数据仓库之父w i l l i a m h i n m o n 在其( ( b u i l d i n gt h ed a t aw a r e h o u s e ) ) 一书中定义了数 据仓库的概念，数据仓库( d a t aw a r e h o u s e ) 是个面向主题的( s u b j e c to r i e n t e d ) 、集成的 ( i n t e g r a t e ) 、相对稳定的( n o n v o l a t i l e ) 、反映历史变化( t i m ev a r i a n t ) 的数据集合，用于支 持管理决策【2 j 。根据数据仓库的定义，数据仓库具有以下四个特点： ( 1 ) 面向主题。数据仓库是按照面向主题的方式进行数据组织的，也就是在较高层 次上对分析对象的数据作一个完整、一致的描述，能有效地刻画出分析对象所涉及的各 项数据及数掘问的联系。这种数据组织方式更能适合子较高层次的数据分析，便于发现 数据中蕴涵的模式和规律。 ( 2 ) 集成的。数据仓库中每一主题对应的源数据在原有的各分散数据库中可能是重 复出现的、不一致的，数据仓库中的数据不能从原有数据库系统中直接得到。事务处理 系统中的操作型数据在进入数据仓库之前，必须经过统一和综合，演变为分析型数据。 这是数据仓库建设中最复杂的一步，需要完成的工作包括：处理字段的同名异义、异名 同义、单位不统一、长度不一致等问题。然后对源数据进行综合和计算，生成面向主题 分析用的高层、综合的数据。 ( 3 ) 相对稳定的。数据仓库中存放的是供分析决策用的历史数据，而不是联机事务 处理的当前数据，涉及的数据操作主要是数据查询，一般不进行数据的增、删、改操作， 业务系统中的数据经集成进入数据仓库之后极少或根本不再更新。如果对数据仓库中的 数据进行了修改，就失去了统计分析f 确性的基础数据的真实性。由于数据仓库中 的数据量往往很大，因此数据仓库系统要采用各种复杂的索引技术，以提高数据查询的 性能。而在这样一种稳定的数据环境中使用索引技术也是非常适合的。 ( 4 ) 随时间变化的。数据仓库中的数据不是永远不变的。数据仓库数掘是随时间变 化的，数据仓库系统需要不断获取联机事务处理系统不同时刻的数据，经集成后追加到 数据仓库中，因此数掘仓库中数据的码( 键) 都包含时间项，以表明数据的历史时期，并 6 中国石油大学( 华东) 硕士学位论文 可在时间维度上对数据进行分析。此外，数据仓库中的数据也有时间期限，在新数据不 断进入的同时，过时的数据也要从数据仓库中排除出去。 2 2 数据仓库的体系结构 数据仓库通常采用三层结构【2 4 】，如图2 - 1 所示： l i i l l i l 习廿 端 。1 ： 具 埔女。 螽罨 珑 精辩 数攒仓盼数捌墅i i 娃 日曰日望日品 嫩弘最影i ：姊锚数魏；池： 图2 - 1 数据仓库体系结构 f i 9 2 - 1 d a t aw a r e h o u s ea r c h i t e c t u r e ( 1 ) 数据仓库服务器，它通常是一个关系型数据库系统。数据仓库的数据来自多种 7 第二章数据仓库 数据源，包括企业之前创建的事务处理型数据库系统和各种文本、文档之类的外部数据。 这些数据的质量问题通常表现在正确性、完整性、一致性、完备性、有效性、时效性和 可获取性等几个特性。为了获得一致统一的数据，它们必须要经过复杂的e t l 处理过 程。e t l 是数据抽取( e x t r a c t ) 、数据转换( t r a n s f o r m ) 、清洗( c l e a n i n g ) 和装载( l o a d ) 的过 程。数据仓库服务器就是通过e t l 过程从数据源中提取数据的。 ( 2 ) o l a p 服务器，它利用数据仓库中的数据将数据组织成多维数据集，即就是数据 立方的形式。数据立方是o l a p 分析处理的核心，因为最终获得的分析结果都是对数据 立方进行各种操作得来的，所以它的结构直接决定了数据仓库系统能够进行什么样的多 维分析，能从哪些维度进行查询和分析等重要功能。 ( 3 ) 前端展示工具。它将o l a p 服务器处理的结果以用户希望的方式展示给用户。 它不但提供一般的数据访问功能，如查询、汇总、统计等，还要提供对数据的深入分析 功能，如数据的比较、趋势分析、模式识别等，即所谓的“数据挖掘”功能，并从中获 得一些潜在的规律。 2 3r o l a p 数据仓库的数据组织形式 为了实现从多个维度对数据进行查询，r o l a p 数据仓库中采用了特有的多维数据 模型，该模型将数据看作数据立方体( d a t ac u b e ) 形式。数据立方体允许以多维对数据建 模和观察。它由维和事实定义 2 4 , 2 5 】。维是关于一个组织想要记录的透视或实体。例如， 数据仓库s a l e 记录商店的销售，涉及维t i m e ，i t e m ，b r a n c h 和l o c a t i o n 。这些维使得商店 能够记录商品的月销售，销售商品的分店和地点。每一个维都有一个表与之相关联。该 表称为维表，它进一步描述维。例如，i t e m 维表可以包含属性i t c r n _ n a m e ，b r a n d 和t y p e 。 事实是数值的度量，例如，数据仓库s a l e 的事实包括d o l l a r s _ s o l d ( 销售额) ，u n i t s _ s o l d ( 销 售量) 和a m o u n tb u d g e t 。事实表中包括事实的名称或度量，以及每个相关维表的关键字。 数据仓库中的多维数据模型有星型模型、雪花模型和事实星座模型。星型模型是最 常见的，它由一张巨大的事实表和多张相对较小的维表构成。每一个维对应一张维表， 维表中的字段之间通常具有一定的层次关系。事实表是由各个维表的主关键字和具体的 一些度量值构成的。每一个维表都通过外键来与处于中心的事实表相关联，形成种星 星爆发的样子，故得名星型模式，如图2 2 所示。 另外一种常用的模型是雪花模型，它是星型模型的变种。它与星型模型的主要区别 在于雪花模型中某些维表可能是规范化的形式，以减少冗余。这种维表易于维护，并节 8 省存储空间。然而，与巨大的事实表相比，这种空间的节省可以忽略。此外，由于执行 查询时需要更多的连接操作，雪花模型可能降低系统的性能，结构如图2 3 所示。 t i m e 维表 i t e m 维表 t i m e 维表 图2 - 2 星型模式 f i 9 2 - 2 s t a rm o d e l i t e m 维表 s u p p l i e r 维表 图2 - 3 雪花模型 f i 9 2 - 3 s n o wm o d e l 有了多维数据模型，就可以从多个角度来分析同一个度量值了。例如，对于星型模 9 第二章数据仓库 型考察某年某种商品的销售量，其s q l 语句为：s e l e c tu n i t s s o l df r o ms a l ei n n e r j o i nt i m e o ns a l e t i m ek e y = t i m e t i m e _ _ k e yi n n e rj o i ni t e mo ns a l e i t e mk e y = i t e m i t e m _ k e yw h e r e t i m e y e a r = 2 0 0 7 a n di t e m i t e m 。同时也可以考察某地某种商品的销售name=computer 量，其s q l 语句为：s e l e c tu n i t s s o l df r o ms a l ei n n e rj o i ni t e mo ns a l e i t e m _ k e y = i t e m i t e m _ k e yi n n e rj o i nl o c a t i o no ns a l e l o c a t i o nk e y = l o c a t i o n l o c a t i o n _ k e yw h e r e l o c a t i o n c i t y = l o sa n g e l e s a n di t e m i t e m _ n 锄e = c o m p u t e r 。显然，在多维数据模型中可 以轻松且灵活地从多个角度对数据进行考察。此外，o l a p 还有一些特有的操作，常用 的有切片、切块、上卷、下钻和旋转。借助于这些o l a p 操作可以实现从多个角度和多 个层次对度量值进行考察，从而实现决策分析的功能，下面对其进行介绍。 2 4r o l a p 的多维数据分析 ( 1 ) 切片、切块 选定多维数组的一个二维子集的操作叫做切片，即选定多维数组( 维1 ，维2 ， 维n ，变量) 中的两个维：如维i 和维j ，在这两个维上取某一区间或任意维成员，而将 其余的维都取定一个维成员，则得到的就是多维数据在维i 和维j 上的一个二维子集， 称这个二维子集为多维数组在维i 和维j 上的一个切片，表示为( 维i ，维j ，变量) 。 切块可以看成是在切片的基础上，进一步确定各个维成员的区间得到的片段体，即 是由多个切片叠合起来。对于时间维的切片( 时间取一个确定值) ，如果将时间维上的取 值设定为一个区间( 例如，取“1 9 9 0 年到1 9 9 9 年 ) ，而非单一的维成员时，就得到一 个数据切块，它可以看成是由1 9 9 0 年到1 9 9 9 年1 0 个切片叠合而成的。 ( 2 ) 上卷、下钻 在当前数据对象基础上再减少一个维做聚合操作，或是在具有层次关系的属性中从 底层属性切换到上层属性做聚合操作称为上卷，随着上卷的进行，看到的数据细节越来 越少；下钻操作则刚好与之相反，在当前数据对象基础上再增加一个维，或是从具有层 次关系的属性中从上层属性切换到底层属性，以便获知当前数据在该维上是如何构成 的，随着下钻的进行，看到的数据细节逐渐增加。 ( 3 ) 旋转 选择两个维并对度量进行聚合操作，聚合后的度量值可以被填在一个二维表格中， 位于( x ，y ) 位置的那个值是由所有那些每第一个维取值为x ，每第二个维取值为y 的那些 行计算而得的，而x ，y 的值则出现在相应行、列的表格中。一个简单的旋转操作是：改 1 0 中国石油大学( 华东) 硕士学位论文 变二维表格的方向，使y ，x 出现在相应行、列的表格中。旋转操作并不改变数值的聚集 方式和聚集结果，但是它体现了用户视角的变化。 2 5 小结 本章介绍了数据仓库的背景知识，定义和特点，然后又从整体上给出了数据仓库的 体系结构。最后为了在关系数据库中实现多维数据分析，给出了两种常用的多维数据组 织模型以及常用的o l a p 操作。为了提高数据仓库的查询响应性能，下一章将引入实视 图的概念，并对数据仓库实视图选取算法作详细介绍。 第三章实说幽选取算法 第三章实视图选取算法 r o l a p 数据仓库中通常存储了大量的历史数据，而且在进行o l a p 操作的时候通 常需要进行复杂的多表连接，因此数据仓库中的查询处理是相当耗时的。为了提高数据 仓库的查询响应性能，快速地响应用户提交的查询请求，本文采用实视图技术。所谓实 视图技术就是预先计算出需要频繁查询的视图，把它们存储起来，以便将来使用，实视 图是数据仓库系统建设中的一个关键性技术【2 。其目的是通过预计算来提高数据仓库系 统对用户查询的响应速度。然而视图的实体化既需要占用可观的磁盘空间，又需要耗费 大量的系统资源以对其进行维护，所以如何选取一组合适的视图集加以实体化，从而使 系统能够利用有限的资源，最大限度地提高数据仓库系统对用户查询的响应速度，是一 个极为重要的问题。 3 1 实视图选取模型 为了对实视图问题进行定量的研究求解，h i m a n s h ug u p t a 、j i a ny a n g 和h a r i n a r a y a n 分别给出了a n d o rv i e wg r a p h 模型1 1 0 , 2 3 ) 、m v p p 模型1 1 2 】和多维数据格模型【2 6 1 ，它们是 至今最为流行的三种实视图模型，下面分别进行介绍。 3 1 1a n d o rv i e wg r a p h 模型 定义3 1 ( 表达式a d a g ) 一个查询或视图的表达式a d a g ( a n d d a g ) 是一个有 向无环图，该图以基础关系( 表) 作为“最下端的节点”( 没有输出的节点) ，且以节点v 作为“源节点，( 没有输入的节点) 。如果一个节点( 视图) u 有输出的边指向节点巧，砭，圪， 于是在计算u 之前，所有的节点k ，圪，圪都需要进行计算，并且这种依赖关系用一种 称为a n d 弧对经过( “，m ) ，( “，吃) ，( 甜，k ) 的边用半圆进行标识，每个a n d 弧都有一个 操作符和由巧，。，圪计算u 所产生的代价与之相联系，并且在表达式a d a g 中节点 u 的代价是其子孙的a n d 弧相关的代价总和。 定义3 2 ( 表达式a o d a g ) 一个视图或查询v 的表达式a o d a g ( a n d o r - d a g ) 是一个有向无环图，该图以v 作为源节点，以基础关系作为最下端节点，每个非最下端 节点都有一个或多个a n d 弧与之相联系，每一个约束着它的输出边的子集，按照前面 的定义，每个a n d 弧都有一个操作符和代价与之相关。于是，在一个节点中的多个a n d 弧刻画了计算那个节点的多种方式。 1 2 中国缸油人学( # 东) 顾l ? 学位论文 定义3 3 ( a n d o r 图) 一个图g 称作视图( 查询) k ，k ，圪的a n d - o r 图，需满足 的条件为：对于每个形，都存在一个图g 的子图g ，是巧的表达式a o d a g 。在a n d o r 图中的每个节点u 都有下列参数与之相联系：对u 的查询频率丘，被u 占据的空间瓯， 更新1 1 的频率。 根据上面的定义，一个数据仓库的a n d o r 图可以通过被数据仓库支持的给定查 询集加以定义和构造。对于给定的查询集，按照如下步骤构造a n d o r 图。首先，构 造对应于每个查询q 的a o d a g 表达式口；接着，把对应于日，d 2 ，包的所有 a o d a g 表达式进行合并，便得到了整个查询集的a n d o r 图g 。值得说明的是，在 a n d o r 图g 中的每个节点表示一个将被选作物化的视图，并且进行物化时，仅仅考 虑这些视图。 给定一个a n d o r 图g 和由数据仓库支持的可用存储空间大小s ，视图选取问题 就是选取g 中的一个子集( 即，视图集m ) ，以便在被m 占用的存储空间小于s 的条件 约束下，使得总的查询响应时间和总的维护代价最小。下面给出视图选取问题的数学模 型。 设q ( u ，m ) 表示在给定图g 情况下，使用实视图集m 回答查询u ( g 的一个节点) 的 代价，q ( u ，m ) 是g 中嵌入在表达式u 中的最小花费代价，并且g 的最下端节点属于集 合m u l ，其中l 表示g 中的最下端节点集合。不失一般性，假设g 中的最下端节点 在进行计算时总是可得的，原因是它们表示源节点中的基础表。因而，q ( u ，o ) 表示从 源节点直接回答查询u 所花费的代价。设u (