（计算机应用技术专业论文）数据仓库中实视图选择技术的研究.pdf

哈尔滨理t 大学t 学硕卜学位论文 数据仓库中实视图选择技术的研究 摘要 数据仓库是近年来兴起的一种新的数据库技术，它面向分析型环境，弥 补了传统关系型数据库对分析型环境的支持不足，对企业的分析决策提供了 强有力的支持。数据仓库是多个分布的、异质的、自治的数据源的集成信息 库，信息以实视图的形式存储在其中，通过物理上的预先存储，有效地加快 了数据仓库系统对用户的查询响应时间。本文主要对数据仓库中实体化视图 选择算法进行了研究，并提出了若干更为高效、适用性更强的新算法。 实视图选择是数据仓库开发中的重要问题，目前已建立多个模型用于该 问题的研究，其中a ov i e wg r a p h 模型应用最广泛。本文提出基于a o v i e wg r a p h 模型并利用不同算法进行实视图选择，为解决该问题，给出了 a ov i e wg r a p h 模型的定义，并对其中涉及的重要概念和代价模型进行形式 化工作。 基于给出的a ov i e wg r a p h 模型，提出了一个考虑维护代价并具有固 定比值界的贪心算法，来实现实视图的选择。 为了使算法能够处理更大规模的输入，提出了使用遗传算法解决实视图 选择问题，针对给定的a ov i e wg r a p h 模型，将其转换为遗传算法中的二 进制编码，以及对应的遗传操作，同时定义了适应度函数，给出了一个依据 a ov i e wg r a p h 结构进行染色体编码并考虑对无效后代进行自动修正的遗传 算法，这些算法显著地改善已有算法的适用性及执行效果。最后通过实验证 明这些算法的有效性。 针对贪心算法和遗传算法所存在的不足，提出了一个基于a ov i e w g r a p h 的实视图动态管理算法，通过一系列定理证明了该算法所产生结果的 优秀性，并以实验验证了动态管理算法的有效性。 此外为方便对算法进行测试，开发了一个算法测试系统。该系统能够根 据用户输入的数据仓库描述信息模拟生成a ov i e wg r a p h 模型，对所设计 的基于a ov i e wg r a p h 的各种静态算法和动态算法进行测试。 关键词数据仓库；o l a p ；实视图选择；算法设计；a ov i e wg r a p h i o ：垒堡矍：查耋二兰矍：茎堡竺兰 r e s e a r c ho nm a t e r i a l i z e dv i e w s s e l e c t i o ni nd a t aw a r e h o u s e a b s t r a c t t h et e c h n o l o g yo fd a t aw a r e h o u s e ( d v oi san e wb r a n c ho fd a t a b a s e t e c h n o l o g y i tf a c e st oa n a l y t i c a le n v i r m m e n ta n dc o v e r st h el i m i t a t i o no f t r a d i t i o n a ld a t a b a s e s y s t e ma b s o l u t e l y , p r o v i d i n gs t r o n g l ys u p p o r t i n g t o e n t e r p r i s e s a n l y s i sa n dd e c i s i o n t h ed a t aw a r e h o u s ei s ar e p o s i t o r yo f i n f o r m a t i o nc o l l e c t e df r o mm u l t i p l e ，p o s s i b l yh e t e r o g e n e o u s ，a u t o n o m o u s ， d i s t i l b u t e dd a t a b a s e s t h ei n f o r m a t i o ns t o r e da tt h ed a t aw a r e h o u s ei si nf o r mo f v i e w s ，r e f e r r e dt oa sm a t e r i a l i z e dv i e w s t h eq u e r yr e s p o n d i n gt i m ec a nb e s p e e d e db yp r e - s t o r i n g t h i st h e s i ss t u d i e st h es t a t i ca n dd y n a m i cm e t h o do f m a t e r i a l i z e dv i e ws e l e c t i o n ，a n dg i v e ss o m ee f f e c t i v ea n dp r a c i t i c a la l g o r i t h m t h es e l e c t i o no ft h em a t e r i a l i z e dv i e w si so n eo ft h em o s ti m p o r t a n t d e c i s i o n si nd e s i g n i n gad a t aw a r e h o u s e m a n ym o d e l sa r eb u i l tt os t u d yt h e m a t e r i a l i z e dv i e ws e l e c t i o np r o b l e m ，a n dt h ea ov i e wg r a p hm o d e li so n eo f t h e m o s tu s e f u lm o d e l s d i f f e r e n ta l g o r i t h m sf o rt h em a t e r i a l i z e dv i e ws e l e c t i o n b a s e do na ov i e wg r a p hm o d e la r eg i v e n i no r d e rt os o l v ei t ，t h ed e f i n i t i o no f a ov i e wg r a p hm o d e la n ds o m ei m p o r t a n tn o t i o n sa n dc o s tm o d e l sa r e i n t r o d u c e d b a s e do nt h ea ov i e wg r a p hm o d e l ，t h em e t h o da n ds t r a t e g yu s i n gg r e e d y a l g o r i t h mf o rs e l e c t i n g m a t e r i a l i z e dv i e w sa r ep r o p o s e d w eg i v eag r e e d y a l g o r i t h mw i t hf i x e dr a t i ob a n da n dm a i n t e n a n c er e s t r i c t i o n t h em e t h o df o rm a t e r i a l i z e dv i e w ss e l e c t i o nb yu s i n gg e n e t i ca l g o r i t h mi s p r e s e n t e d t h es o l u t i o no fp r o b l e ms h o u l db ec o n v e r t e di n t oab i n a r ys t r i n gi n t e r m so fa ov i e wg r a p hg i v e n g e n e t i co p e r a t i o ni sp r e s e n t e d ，a n df i t n e s s f u n c t i o ni sd e f i n e d ag e n e t i ca l g o r i t h mi sp r o p o s e dw h i c hc a na u t o m a t i c a l l y a m e n di n v a l i dg e n e sp r o d u c e db yt h ep r o c e s so f c r o s s o v e ra n dm u t a t i o n f o rs o l v i n gt h es h o r t a g eo ft h es t a t i ca l g o r i t h m s ，t h em e t h o d so fd y n a m i c m a n a g e m e n to fm a t e r i a l i z e dv i e w sa r es t u d i e d t h ev a t i d i t yo ft h i sa l g o r i t h mi s 竺竺鎏量三奎兰三耋矍：兰竺竺三 p r o v e db yas e r i e s o ft h e o r e m e x p e r i m e n t ss h o wt h ee f f e c t i v e n e s so ft h e a l g o r i t h m s i no r d e rt ot e s tt h ef u n c t i o na n de f f i c i e n c yo ft h es t a t i ca n dd y n a m i c a l g o r i t h m so fm a t e r i a l i z e dv i e w ss e l e c t i o n , a na l g o r i t h mt e s ts y s t e mi sd e v e l o p e d a c c o r d i n gt ot h ed e s c r i p t i o ni n f o r m a t i o no fd a t aw a r e h o u s eb yu s e r , t h i ss y s t e m c a ns i m u l a t em u l t i d i m e n s i o n a ld a t aa n da 0v i e wg r a p hm o d e la n dt e s ta l lt h e a l g o r i t h m sm e t i o n e da b o v e k e y w o r d sd a t aw a r e h o u s e ；o l a p ；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 md e s i g n ； a ov i e wg r a p h 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文数据仓库中实视图选择技 术的研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名： 狃叩朱 日期：刃衫年乡月日 哈尔滨理工大学硕士学位论文使用授权书 数据仓库中实视图选择技术的研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨 理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权哈尔 滨理工大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文 的全部或部分内容。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 孝够挈 日期：勿衫年；月日 导师签名：l 抑确 日期：州年弓月，占日 哈尔泞理t 大学t 学硕+ 学位论文 第1 章绪论 1 1 课题背景及研究意义 在市场激烈竞争的今天，任何一个企业的决策者必须能够从有效收集到的 数据中获得有价值的信息，并用之于决策，使企业获得最大的效益和竞争优 势。传统的数据库( d a t a b a s e ，d b ) 虽然在数据共享、数据与程序的独立性、 维护数据的一致性和完整性以及数据的安全保密方面已很成熟，但随着应用的 发展、数据量的急剧扩大、用户的需求越来越复杂，无法对数据的合成、分析 和综合提供强大的功能，数据仓库技术应运而生。它面向分析型环境，对企业 的分析决策提供了强有力的支持“”。 经过近几年的发展，数据仓库技术已日臻完善，大多数大型数据库供应商 都己在其产品中集成了数据仓库的功能，例如o r a c l e 、i b md b 2 、s y b a s e 都已 经向用户提供了比较成熟的数据仓库产品。同时，数据仓库在实际应用中取得 了显著的效果。i d c 公司1 9 9 9 年对西方发达国家6 2 个实现数据仓库的企业进 行的调查表明，在这些企业中，9 家企业的r o i ( r e t u mo ni n v e s t m e n t ，投资回 报率) 值在1 8 5 7 一1 6 0 0 0 ，8 家企业的r o i 为负，4 5 家企业的r o i 值在 3 一1 8 3 8 之日j 。而且这4 5 家企业，他们3 年的投资回报率平均值为4 0 1 ，收回投资的平均时间为2 、3 年。，。 实视图技术是数据仓库系统中的个关键性技术，它是一种将视图所对应 数据加以实际物理存储的技术。其目的是通过预计算来加快数据仓库系统对用 户查询的响应速度。然而视图的实体化既需要占用可观的磁盘空间，又需要耗 费大量的系统资源以对其进行维护，所以如何选择一组合适的视图集合加以实 体化，从而使系统能够利用有限的资源，最大限度的提高数据仓库系统对用户 查询的响应速度，是一个极为重要的问题“1 。本文以其作为研究的方向来提商 数据仓库的性能，具有一定的理论意义和较强的实际价值。 1 2 本领域发展概况 自9 0 年代初w h i n m o n 给出数据仓库的定义后，数据仓库技术就成为研 究的热点”1 。许多专家开始研究数据仓库及其关键技术。很多大型企业利用已 哈尔滨理- 大学t 学硕卜学位论文 有数据跟踪市场需求、预测企业发展趋势，也利用数据仓库的先进技术，研究 和实现数据仓库的方案。 国外，世界著名的数据库专家a s i i b e r s c h a t z 、m s t o n e b r a k e r 和斯坦福大 学的j u l l m a n 等发表了一份权威性报告，题目是数据库研究：面向2 1 世纪 的机遇与成就，讨论了数据仓库的问题，引起广泛的反响。世界上的大公司 都投入了巨资和重要力量去研究和开发，并有一些相关解决方案和产品。如 s y b a s e 公司、i n f o r m i x 公司、i b m 公司和o r a c l e 公司”1 都推出了自己的数据仓 库产品和方案。 在国内，中国银行省、市两级金融管理信息系统示范系统( f m i s ) ，率先引 进和应用了数据仓库、联机分析处理、多维数据库等先进理论与技术，在统一 的基础系统网络上，建立起实用的数据仓库原型”1 。上海庄臣有限公司受国外 成功案例的启发也建立了数据仓库系统。p l a t i n u mt e c h n o l o g y 为中国国际航 空公司计划处建立一个完全实际运行的数据仓库系统，并在该数据仓库的基础 上建立面向最终用户的基于决策支持的统计分析应用系统。 工业界大都考虑数据仓库的实现问题，学术界一般考虑数据仓库的关键技 术的实现。作为一个新兴的研究领域，数据仓库和联机分析处理发展很快，许 多大学和公司都正在这个领域进行着广泛而深入的研究，如探讨数据仓库的建 立、维护等方面，研究实视图的技术等。斯坦福大学正在进行一个名为 “w h p s ”的科研项目，提出了一个基本的数据仓库模型和一些高效的算法， i b ma l m a d e n 和微软在进行一个称为“q u e s t ”的项目，主要研究多维数据 库。威斯康辛大学和a t & t 也在研究实视图、o l a p 数据组织等方面的问题。 下面我们主要阐述和本文研究相关的实视图技术及研究现状。 传统上，视图是数据库中一个或多个基本表导出的表，其记录没有存储在 数据库中，而是在需要时根据视图定义计算出来。而实视图( m a t e r i a l i z e dv i e w ) 是物理上存储视图定义的数据，在数据仓库中，它是一张实实在在的表。数据 仓库可以简单看成一系列异质复制的关系表和需要周期性进行维护的实视图。 对于大规模的数据集，分析用户希望能够迅速得到查询结果。在查询频率很 高，而且视图很复杂的情况下，每次对查询藿新计算视图是不可能的。一个很 有效的方法就足利用数据仓库中存放的大量的实视图，在用户进行查询处理 时，无须实施计算复杂视图，而是利用这些实视图就可以快速得到查询结果， 比普通的查询修改方法快的多。目前，实视图技术的研究足数据仓库研究的一 个热点问题”1 。实视图技术己经在实视图的维护、实视图的选择等方面得到广 泛的应用。 略尔滨理t 大学t 学毋 学位诊文 1 2 1 实视图维护的研究现状 数据仓库中存放大量的实视图，以使用户快速得到查询结果，供o l a p 分 析之用。为了保持和基本关系的一致性，数据仓库中的实视图也要相应更新， 这就是实视图维护问题。对于实视图维护，许多研究者提出了实视图维护的算 法”。 a g u p t a 等介绍了实视图的概念、为什么使用实视图等问题，给出实视图 维护问题的分类“。后来a g u p t a 等又进一步讨论了视图重新定义后实视图维 护的技术和应用”。t o kw a n g 等人利用版本号对视图维护给出一个算法，解决 了从数据源的信息在传送的过程中丢失或延迟的情况下，怎样正确维护视图问 题“”。j o l l nw - t k e 等利用两种方法( 附加视图和摘要表技术) 的综合进行实视 图的维护，并应用于金融数据仓库系统中“”。 近几年对对实视图维护问题采用增量维护的方法比较多。所谓的视图的增 量维护即是当数据源中的数据发生变化时报告给集成器，集成器计算相应的变 化，然后将这些变化通告给数据仓库。 斯坦福大学的y z h u g e 提出用e c a ( e a g e rc o m p e n s a t i n ga l g o r i t h m ) “来实 现视图的增量维护。该算法设计只针对单个数据源的情况，基于f i f o 队列模 型，每次针对数据源中原始数据的变化，构造补偿请求来查询原始数据，并将 查询的结果反映在数据仓库的实视图中。其后，y z h u g e 打破了e c a 算法中单 数据源的限制，提出了s t r o b e 算法“”，它基于多数据源环境视图一致性维护， 要求所有基本关系的关键字都包含于视图中j 还要求实视图更新时必须保证信 息源是静止的，实现了多种数据源情况下实视图的增量维护。此外对于多数据 源的视图维护算法，a g r a w a l 等人提出了s w e e p 算法“，利用临时查询结果解 决数据仓库中视图一致性维护出现的异常问题。和s t r o b e 算法相比，它对视图 的定义更灵活，它不要求基本关系的关键字必须保存在视图中。另外，它不要 求视图更新时系统是静止的。 由于数据仓库与其数据源在物理上是独立的，其存储位置通常是分散的， 因此当在数据仓库端对实视图进行维护时，如果所涉及的原始数据全部需要通 过网络从数据源传过来，那么当数据仓库的维护频度较高或者维护工作所涉及 的原始数据量很大时，网络将成为维护工作的瓶颈。视图的自维护算法就是基 于这一思想，以牺牲数据仓库端的存储空间为代价，将部分原始数据的拷贝直 接放到数据仓库端。但这样会导致大量的额外存储空间和费用，因此确定最小 量的相关数据存储是数据仓库研究的一个重要方面。a g u p t a 等使用主属性信 息决定视图对于某一类的修改的自维护能力“”。r h u l l 等通过降低选择条件和 目标并把结果存在数据仓库中来考虑视图的自维护1 。后来。d q u a s s 等扩展 了文献 2 0 】的结果，给出算法去选定附加视图，将其存放在数据仓库中维护 s p j ( s e l e e t i o n - p r o j e c t - j o i n ) 视图，将关键字和参照完整性约束考虑进去来进一步 减少附加视图中元组的数目”。这些视图自维护方法处理的都足单个视图的情 况。对于多视图的自维护，w e i f a nl i a n g 等给出一个算法，利用附加视图和实 视图之日】的共享信息去得到一个附加视图集，以使附加视图和s p j 视图一起足 自维护的，同时考虑了随着数据仓库的发展带来的自维护问题2 1 。y z h u g e 等 也给出关于多视图维护的算法，并提出多视图维护的一些关键问题。“。 实视图维护是数据仓库的关键技术之一，实视图的维护效率直接影响数 据仓库的整体性能。 l 二 1 2 2 实视图选择的研究现状 对于视图的选择问题( v i e ws e l e c t i o np r o b l e m ) ，最初的动机来源于数据仓 库的设计，要决定哪些视图存储在数据仓库中能得到最优的性能”。后来几 个商业数据库系统提出另一个动机是支持实视图增量修改，使用实视图加速查 询估算”1 。总之，为了快速响应o l a p 查询，数据仓库中存储的实视图占据 着大量的存储空间，而且它们的一致性维护也需要占用大量的c p u 时间。在 存储空间有限，用于维护的视图的c p u 时间有限，同时又要最大限度缩短 o l a p 查询时间的情况下，对所有视图部进行实体化耗费的空间代价和维护代 价又是十分巨大的”，也是不合理的，因此需要选择部分视图进行实体化，这 就是实视图选择问题。 为了解决v s p 问题，很多研究人员提出了一些解决方法”。一个最显而 易见的算法就是在一系列查询中应用完全搜索算法进行实视图选择。然而，如 果搜索空日j 很大时，这种算法代价很商，是不切实际的。h g u p t a 给出了实视 图选择的理论框架，提出在空间限制下，使查询响应时间和视图维护代价总和 最小的实视图选择代价模型，同时使用了贪心算法解决这个问题1 。它检查一 小部分状态空间，使实视图满足空间的条件限制，达到了时间要求，但这种方 法性能不是很好的。后来，h g u p t a 又提出在维护代价一定的条件下，使总查 询时间最小的代价模型，给出a 算法来解决这个问题”。s r l u r i 根据一个 视图的选择可能影响其他视图的利益，从而影响总查询代价和维护代价，因此 定义了视图关联的概念，给出视图关联矩阵，提出在视图关联上的代价模型和 哈尔滨理_ 大学t 学硕十学位论文 算法。同时和贪心算法作了比较，证明在空间限制和修改频率很高时，该算法 有更好的性能1 。 j y a n g 另辟蹊径，给出了一个结构和算法，其基本思想是依据多视图处理 计划( 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 ，然后从m v p p 中选择视图实体化“”。后来，m i n d u l s k a 提出这个结构和算法的几点限制：首先，分组属性在查询树中不明确：其次， 确认“共享”结果的方法在某些情况下不是总有效的。因此，对此扩展，扩充 了查询树的定义，解决了包含不同维、不同粒度上查询共享结果的问题，证明 属性级别可提高共享结果的确认，从而提高实视图选择的性能1 。 s l i g o u d i s t i a n a s 等将实视图选择作为数据仓库的构造问题，将其描述为基 于视图和查询的状态空间搜索算法，给出一个新的贪心算法r - g r e e d y 算 法，通过实验评定表明在访问有限状态空间下，其性能较好。目前遗传算法 也已经在实视图选择问题中得到了广泛的应用“。 实视图的动态管理是一个比较新的研究方向“1 ，d t h e o d o r a t o s 提出了一 种基于a ov i e wg r a p h 的动态实视图管理算法，但该算法的描述主要是基于图 上作业的，并且没有提供关于算法有效性的证明。c z h a n g 提出了一个基于 m v p p 模型( 相当于a ov i e wg r a p h 模型的一个子集) 的实视图动态管理算法 1 ，同样在这篇文章中作者也没有给出关于其所提出算法的有效性的证明。 y k o t i d i s 提出了一个基于缓存思想的动态实视图管理系统及相应算法，是一个 比较完善的系统。 实视图的选择影响数据仓库的效率和o l a p 分析质量，目前它成为重要的 研究热点问题。 1 3 本文研究内容 本论文来源于黑龙江省重点科技攻关项目。 论文完成过程中，作者查阅了大量有关数据仓库、实体化视图方面的文献 资料，对实体化视图的选择算法进行了研究。 针对给定工作负载并基于相应的a ov i e wg r a p h 进行实视图选择是一种可 行且有效的实视图选择模式，学术界在该模式下已经进行了广泛的研究。但是 目前的工作仍然存在着某些尚可改进之处：一是目前仍然缺少一个考虑维护费 用的，针对a ov i e wg r a p h 的，具有固定比值的近似算法。二是遗传算法已经 在实视图选择问题中得到了广泛应用，但是目i ； 提出的算法大多没有考虑对交 哈尔泞理t 大学t 学硕卜学位论文 叉变异过程中所产生的无效基因进行修正，或修正时末考虑到实视图间维护代 价所具有的依赖性，这些因素将增加算法的执行时间，并且在一定程度上降低 算法求解的优化程度。针对这些不足，本文将设计基于a ov i e wg r a p h 模型的 考虑维护代价的并且具有固定比值界的贪心算法。本文还将设计一个根据a o v i e w g r a p h 结构进行编码的、考虑对无效基因进行自动修正的遗传算法。 ，一 在实际应用中，用户提交查询的模式和所涉及的范围将不断发生变化，现 有的静态实视图选择算法不能很好的适应用户提交查询的这种动态性，所以本 文将对实视图集合的动态管理算法进行研究，设计了基于的a ov i e wg r a p h 模 型的实视图动态管理算法。 本文对数据仓库中的实视图选择的问题进行了比较全面的研究，在该研究 过程中，本文在很大程度上得益于对研究模型的形式化工作，这些工作使本文 能够有效的将所研究模型的性质映射到算法的分析搜索空间之上，这种映射不 仅使人们增进了对算法搜索空间性质的认识，还促使本文设计出了更好的算 法，并证明了这些算法所产生结果的优秀性。 1 4 论文结构 本文第一章概述了数据仓库研究的目的和意义，分析需要进一步研究的内 容，提出本文主要研究工作。第二章着重研究了数据仓库技术和实视图技术， 重点阐述了实视图维护和实视图选择的研究现状，提出要解决的问题，为深入 研究提供理论依据。论文的第三章将针对基于a ov i e wg r a p h 的实视图选择算 法进行研究，这一部分将针对已有工作的不足，设计了基于a ov i e wg r a p h 模 型的考虑维护代价的并且具有固定比值界的贪心算法和依据a ov i e wg r a p h 结 构进行编码，并考虑对无效基因进行自动修正的遗传算法。第四章将对实视图 的动态管理算法进行研究。第五章将对算法测试系统进行介绍。最后，对本文 的工作进行总结，提出未来进一步的工作展望。 哈尔滨理t 大学t 学硕十学位论文 第2 章数据仓库及实视图技术 本章主要阐述了数据仓库技术和实视图技术，着重研究了数据仓库中实视 图选择技术的关键问题和分类方法，认真分析了各种选择算法的优缺点、进行 性能比较，从而引出有待进一步研究和完善的内容，为深入的研究提供理论依 据。 2 1 数据仓库技术 典型的数据仓库系统的体系结构如图2 1 所示2 “。组成数据仓库系统各 个模块包括：信息源、数据仓库、数据仓库、仓库管理工具和分析工具。 图2 - i 数据仓库系统的体系结构 f i g u r e 2 1a r c h i t e c t u n ：o f d a t aw a r e h o u s es y s t e m 信息源是数据仓库的信息来源，它们可以是传统的关系数据库，非关系数 据库，网络上的信息源，或者是其它的信息源。这些信息源往往是分散的、自 治的和异构的。 数据仓库负责建立并管理其中的数据，是该体系结构的核心，它肩负多项 任务。首先该数据仓库负责对数据源的信息进行集成，其中包括对信息源中的 信息进行提取、过滤、重整、综合并将经过综合后的信息向数据仓库进行广 播，接到广播后，数据仓库将根据需要对自身存储的内容进行修改，升级相应 的元数据信息，并对信息进行存储。元数据是数据仓库的核心，它是对数据库 中各个对象的描述，它遍及数据仓库的所有方面。 数据仓库管理包括对数据的安全、归档、维护、备份、恢复等工作，这些 工作需要数据库管理系统的支持。 数据仓库是面向分析的，所以分析工具是数据仓库系统的一个重要组成部 哈尔演理t 大学t 学硕十学伊论文 分。分析工具包括用于完成决策问题所需的各种查询工具、检索工具、o l a p 分析工具和数据挖掘工具等，以实现决策支持系统的各种要求。 “数据仓库( d a t aw a r e h o u s e d w ) ”这一术语最初是由b a r r yd e v l i n 使用， 但9 0 年代初期，公认的数据仓库之父，美国著名工程学家w h i n l t l o n 将其作 了详细的介绍和定义如下：“数据仓库是支持管理决策过程的、面向主题的、 集成的、稳定的、随时间不断变化的数据集合”。 数据仓库具有以下基本特征： 1 面向主题面向主题是数据仓库中数据的组织方式，就是在较高层次上 将企业信息系统中的数据综合、归类并进行分析利用的抽象，可以根据最终用 户的观点组织和提供数据。 2 管理大量信息数据仓库要在不同的粒度层次上提供概括和聚集机制来 对巨大的数据容量进行分类和管理，要管理所有的历史数据和当前数据，信息 量远远大于一般数据库。 3 信息存储在多个存储介质上因为要管理大量信息，因此数据仓库的数 据要存在多个介质上。 4 跨越数据库模式的多个版本数据仓库存储和管理了大量的历史数据， 他们在不同时间的数据库模式的不同版本中，因此要处理来自不同数据库的信 息。 5 信息的概括和聚集数据仓库主要用于决策分析，它要将信息进行概括 和聚集，以人们可以理解的方式提供出来。 6 许多数据源中将信息集成并使之关联由于要管理历史数据，并且涉及 到多个应用程序和多个数据库，所以要数据仓库收集和组织不同来源的信息。 自9 0 年代初w h i n t o o n 给出数据仓库的定义后，数据仓库就成为研究的 热点。 2 2 实视图维护 对多个，分布的、异质数据源和其他信息源的访问己经成为数据库研究的 重要问题之一。对这个问题传统的解决方法足接受查询请求，产生在每个数据 源上的子查询，然后从这些信息源中采集结果，将他们合并组合，给用户返回 最终的结果。这种方法叫l a z y 方法“”，通常采用虚拟视图技术。 目前的方法是从每个数据源选取和集成相关信息，然后放到数据仓库中， 当有查询请求时，就可以在数据仓库中直接进行查询，而无需存取原始信息 哈尔漳珲t 大学t 学硕+ 学位论文 源，从而提高查询效率。这种方法使用的技术叫实视 ( m a t e r i a l i z e dv i e w ) 技 术。 实视图就是数据仓库针对o l a p 可能的查询对原始数据进行投影、连接、 分组等预处理，建立起来的存储在数据仓库中的一张张实实在在的表。它是已 经过计算建立的、含有大量的数据，这些数据通常来源于几个独立的、分布 的、异质的数据源，在数据仓库中以实视图的形式存在，以便对集成的数据进 行快速的存取。 通过预计算，o l a p 基本上不再需要对原始数据进行复杂处理，而只需在 实视图的基础上进行一些简单的计算便可完成复杂的查询，从而大大提高系统 性能，缩短了数据仓库的响应时间，但同时也带来了许多新问题。 当基础数据库关系表因元素的插入、删除和修改发生变化时，如何保持实 视图与源数据一致性。这种对源数据发生变化后，保证实视图也进行更新的过 程叫视图维护( v i e wm a i n t e n a n c e ) 。 实视图的维护策略决定什么时候对视图进行更新，以及更新时采用什么方 法。对视图的更新也可以在对相应关系表进行修改的同一事务中进行，这称为 直接视图维护。直接视图维护与更新关系表相关的实视图数目成比例，这种视 图更新策略将减慢数据更新事务的处理速度。 我们可以推迟对视图的更新，先将更新数据存储在日志中，然后再对实视 图进行更新。延迟视图维护的策略有几种： 1 惰性的视图维护当查询处理需要使用实视图，并且实视图中的数据已 经和相应关系表数据不一致时才对其进行更新。和直接视图维护方法比这种方 法减慢了查询处理的速度。 2 周期性的视图维护定期的，如每天，对实视图进行更新。 3 强制性的视图维护当相应的关系表发生了一定数目的数据更新后对实 视图进行更新。 在数据仓库中实视图的维护的方法主要有两种：重新计算实视图和增量维 护。 2 2 1 重新计算实视图 数据仓库一般采用定期维护( 晚问或周末) 。重新计算实视图的方法是，在 维护期间，所有视图要从数据源莺新导出，每次从快照中重新计算视图进行更 新。这种方法简单，在操作期间对数据的变化不需处理。但存在的缺点足： 哈尔演理t 夫学t 学硕十学位论丈 1 对应用有限定。假定应用能接受使用“过期”数据，则实视图不能及时 反映基本数据库的变化情况。 2 当数据源数据变化量很小时，重新计算视图的方法开销很大。 3 这种方法假定有足够长的时间去完成维护过程，当维护的时间过长，而 用户希望数据仓库处于操作状态，这种方法就不再有效了。 2 2 2 增量维护 上面的方法中需要重新计算每个视图，而视图的增量维护则是通过计算视 图的变化部分来修改实视图。 这种方法的优点是： 1 当数据源变化不是很大时，该方法开销较小。 2 减少了维护的时间。数据仓库是定期维护，但视图的维护采用增量维 护，使得在操作期间，发生在数据源上的变化能被记录下来，和重新计算相 比，大大减少了完成维护的处理时间。 3 维护可以是动态的。一旦数据源发生变化，视图修改就能反映这种变 化，数据仓库提供的视图是基于。新鲜”数据的。 增量的视图维护有二个基本方法： 1 不限制对基本数据源的存取的方法这种方法对实视图的维护方法简 单，还可以访问底层的数据源，但能导致实视图更新异常问题。 2 附加视图的自维护方法上述视图维护技术需要对基本关系表进行存取 以维护实视图，即当集成器从监视器接受到一个修改通告后，为了在数据仓库 反映其变化，不仅要修改对应数据，还要访问其它源数据。但在数据仓库中， 存取基本关系是很难的，这些基本关系数据可能属于同一个数据源，也可能属 于不同场地的分布的数据源。访问这些数据可能因网络通信需要很长的延迟， 或因场地故障根本不能实施处理。一种解决方法是在数据仓库中预先保存所有 相关数据，视图不通过存取源数据，使所有计算都可能通过在数据仓库端使用 实视图本身和附加信息来维护实视图，这种方法叫视图的自维护。 2 3 实视图的选择 为了快速响应o l a p 查询，数据仓库中存储的许多实视图占据着大量的存 储空间，而且它们的一致性维护也需要占用大量的c p u 时间。在存储空间有 限，用于维护视图的c p u 时b j 有限，同时又要最大限度缩短o l a p 查询时间 哈尔滨理t 大学t 学够卜学位论文 的情况下，对所有视图都进行实体化耗费的空间代价和维护代价又是十分巨大 的，也是不合理的，因此需要选择其中一部分视图进行实体化，这被称为实视 图选择问题。 一般v s p 问题是选择视图实体化以满足给定的设计目标1 。设计目标有 两种：一种是代价函数最小；一种是在一定的限制下。 代价函数最小分为： 1 查询估算代价最小。 2 维护代价最小。 3 操作代价最小。 限制又被进一步分为：面向系统的限制和面向用户的限制。 面向系统的限制有： 1 视图维护代价限制。 2 自维护限制。 3 从实视图回答查询的限制。 面向用户的限制有： 1 数据传输限制。 2 查询处理代价的限制。 实视图选择问题要根据数据仓库的初始设计要求满足给定的所有限制，它 的一般框架是”1 ： i n p u t ： 一组源关系r 在关系r 上的一组查询q 查询频率和源关系变化传播频率f 面向系统或面向用户的限制 代价模型和代价函数 o u t p u t ： 一组实视图，满足所有限制条件，使代价函数最小。 对实视图的定义不仅反映了数据仓库的初始设计要求，也包含了开发中的 要求：数据仓库包含满足条件的一组实视图。因此，实视图选择是数据仓库中 的重要问题，它影响数据仓库的效率和决策支持的数据质量。 学术界对实视图的选择问题已经进行了广泛深入的研究，并且已经建立了 多个模型用于该问题的研究。目前比较典型的模型有：网格模型( 1 a t t i c e m o d e l ) 、a n d - o rv i e wg r a p h ( a ov i e wg r a p h ) 模型、m v p p 模型( m u l t i p l e 哈尔滨珲t 大学t 学碗十学位论文 v i e w p r o c e s s i n g p l a n m o d e l ) 和m u l f i q u e r y g r a p h 模型。其中网格模型被最早用 于实视图选择问题的研究中，该模型结构简单，可以有效的对数据仓库中的多 维数据模型进行描述。但是这种模型的表达能力有限，对一般关系数据模型中 的视图及视图之间的关系无法进行有效的描述。目前a ov i e wg r a p h 模型是应 用最广泛的模型，该模型的特点是结构简单清晰，表达能力强，该模型不仅能 对多维数据模型进行描述，而且还能对普通关系模型中的视图及视图日j 关系进 行有效的描述，该模型为实体化视图选择问题的研究提供了强有力的支持。另 外m v p p 模型和m u l t i q u e r y 模型也被一些学者用于实体化视图选择的研究， 但m v p p 模型实际上是a ov i e wg r a p h 模型的一个子集，而m u l t i q u e r yg r a p h 则缺乏直观，所以这两种模型并没有得到广泛的使用。无论在何种模型下，数 据仓库中的实体化视图选择问题都是n p 问题“1 ，而使用近似算法是解决该 问题的一个有效途径，目前学者们已经将贪心算法、遗传算法、退火算法等一 系列方法应用于该问题的解决之中，并得到了比较好的结果。 通过研究了目i ； 该方向上的已有工作，本文得到了这些工作的具体分类方 法。按照其对实视图的管理方式，现有的实视图选择方式可以分为静态选择算 法和动态管理算法，表2 - i 对该分类方法进行了表述。静态选择算法的特点 是：算法由数据仓库管理员启动，对实视图集合的选择是一次性的，除非下一 次由数据仓库管理员手动启动，否则它不会自动运行。静态算法的缺点是：用 户所提交查询的模式和涉及的范围是随时间而不断变化的，但静态算法却无法 适应用户查询的这种变化。实视图动态管理算法能够比较有效的解决这一问 题，这种算法的特点是：由系统自动运行，并根据用户提交查询模式及所涉及 范围的不同对实体化视图集合进行动态调整，从而适应用户需求的变化。实视 图动态管理算法的设计难度比较高，思想也比较新，属于一个比较新的研究方 向。 根据静态选择算法在选择时是否具有针对性，静态选择算法可以被进一步 细分，本文将算法按照其选择实视图时是否有选择指导，将静态算法划分有针 对的静态实视图选择算法和无针对的静态实视图选择算法。无针对的静态实视 图选择算法，一般是早期设计的实视图选择算法，这种算法一般根据某种代价 模型遍历所有可选视图，并选出其中具有最大实体化收益的视图，作为实体化 对象。这种方法往往耗费大量的系统资源，而产生的结果却不理想，所以这种 方法在一般情况下并不实用。有针对的静态实视图选择算法通常在某种指导下 ( 如通过工作负载对不同视图的重要性进行加权，从而将实际需求引入到考察 范围) 进行实视图的选择。其选择的实视图集合能和实际需求很好的相适应， 尔滨理丁丈学t 学硕十学位论文 在用户提交查询的模式和数据涉及的范围不发生很大变化的情况下，该方法是 一种比较实用的方法。 表2 - 1 实视图选择算法的分类 t a b l e 2 lt h ec l a s s i f i c a t i o no f t h em 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 有针对的选择：基于给定的w o r k l o a d 选择 实 静态选择算法实视图集合 视s t a t i c 无针对的选择：基于给定的存储空问，对 图 所有可能情况进行考虑，多基于网格模型 选 基于缓存原理的实视图选择方法：对查询 择 动态选择算法 结果加以保存以期再利用 算 d y n a m i c 基于工作负载的实视图选择方法：动态的 法 修改工作负载，并据此修改实视图集合。 动态实视图管理算法也可以被继续细分为两类，即基于缓存原理的实视图 管理算法和基于工作负载变更的动态实视图管理算法。前一种方法的核心思想 是通过对用户的查