（计算机应用技术专业论文）数据仓库性能优化之物化视图选择算法研究.pdf

湖北3 - 业大学硕士学位论文 摘要 数据仓库的构建是一个复杂，庞大，循环往复的过程。要构建一个优秀的数 据仓库平台涉及到很多技术，需要考虑很多方面。本文就数据仓库中的优化问题 提出探讨。 本文首先介绍一些常用的优化技术，如数据抽取中的优化策略，物理建模中 可以利用的分区和索引技术等。 然后引出本文的核心研究内容一一物化视图的选择。联机分析处理的难题是， 在海量的数据中要对用户的复杂查询做出快速的响应。而物化视图由于它的灵活 性，响应时间短，方便维护等优势，正好解决了这一难题。物化视图的本质是以 牺牲存储空问和维护代价来换取快速响应时间。由于存储空间的限制，如何在有 限的空间中选择视图进行物化，以达到最高效率的查询，是本文研究的主要内容。 接着就目前常用的物化视图选择算法之一，遗传算法提出讨论。分析了它的 不足和应用的局限性，并提出了一种改进的算法：一般遗传算法和模拟退火算法 相结合的遗传退火算法。该算法充分利用一般遗传算法的全局把握能力强和模拟 退火算法的局部搜索能力强的特点。同时提出了物化视图选择的代价模型，这种 代价模型充分的考虑到了物化视图在选择时的查询代价和维护代价。最后利用遗 传退火算法的思想，结合代价模型，具体的阐述了物化视图的选择过程。在物化 视图的具体选择过程中，本文还引入了多项式求解约束的思想，来解决选择过程 中产生的无用解。 最后，本文引入了物化视图的动态调整。由于常见的视图选择方法都是基于 用户事先提出查询，而且查询分布均匀，并长久不变的情况。但是在大型的数据 仓库项目中，用户不可能一下提出所有的查询需求，而且随着时间推移，用户的 查询需求也会发生改变。而推翻以前的物化视图，重新进行物化视图选择的代价 是相当大的i 而且也不是即时的。所以本文提出一个比较全面的动态调整方案。 结合物化视图的收益模型和调整时机，该方案不仅能够及时的调整物化视图，还 能够防止由于频繁更新物化视图集合而带来的负面影响。并且通过实验验证了方 案的有效性。 关键词：数据仓库，优化，物化视图选择，遗传退火算法，动态调整 湖北工业大学硕士学位论文 a b s t r a c t c o n s t r u c t i o no fd a t aw a r e h o u s ei sac o m p l e x h u g ep r o c e s s t ob u i l da ne x c e l l e n t d a t aw a r e h o u s ep l a t f o r mi n v o l v e sal o to ft e c h n o l o g y w bn e e dt oc o n s i d e rm a n y a s p e c t s i nt h i sp a p e r , w ew i l ld i s c u s st h et o p i co fd a t aw a r e h o u s e so p t i m i z a t i o n a tf i r s t ，t h i sp a p e ri n t r o d u c e ss o m ec o m m o no p t i m i z a t i o nt e c h n i q u e s ，s u c ha s o p t i m i z a t i o ns t r a t e g yo fd a t ac o l l e c t e d ，t h ep a r t i t i o na n di n d e x i n gt e c h n o l o g yu s e di n p h y s i c a lm o d e l i n g t h e nw ei n t r o d u c et h ec o r er e s e a r c h ：m a t e r i a l i z e dv i e ws e l e c t i o n t h ek e y p r o b l e mo fo n l i n ea n a l y t i c a lp r o c e s s i n gi sh o w t og e tar a p i dr e s p o n s et ou s e r s q u e r yi n af l o o do fd a t a b e c a u s em a t e r i a l i z e dv i e wh a sa d v a n t a g e so ff l e x i b i l i t y , q u i c kr e s p o n s e ， e a s yt om a i n t a i n ，a n ds oo n ，i ti u s ts o l v e st h ep r o b l e m t h ee s s e n c eo fm a t e r i a l i z e d v i e wi st os a c r i f i c et h es t o r a g es p a c ea n dm a i n t e n a n c ec o s t si ne x c h a n g ef o rf a s t e r r e s p o n s et i m e b e c a u s eo fs t o r a g es p a c e sr e s t r i c t i o n s ，h o wt oc h o o s ev i e w st ob e m a t e r i a l i z e di nal i m i t e ds p a c et oa c h i e v em a x i m u me f f i c i e n c yi st h em a i nc o n t e n to f t h i sp a p e r i ns u c c e s s i o n ，t h ep a p e rd i s c u s s e st h ec u r r e n tc o m m o n l yu s e da l g o r i t h mo f m a t e r i a l i z e dv i e w , g e n e t i ca l g o r i t h m s i ta n a l y s e sg e n e t i ca l g o r i t h m s s h o r t c o m i n g s a n dl i m i t a t i o n so ft h ea p p l i c a t i o na n d p u tf o r w a r da ni m p r o v e da l g o r i t h m ：c o m b i n a t i o n o fg e n e t i ca l g o r i t h m sa n ds i m u l a t e da n n e a l i n ga l g o r i t h m ，g e n e t i ca n n e a l i n ga l g o r i t h m t h eg e n e t i ca n n e a l i n ga l g o r i t h mt a k e sf u l l a d v a n t a g eo ft h ec o m m o ng e n e t i c a l g o r i t h m ss t r o n ga b i l i t yo fg r a s p i n gt h eo v e r a l ls i t u a t i o na n dt h es i m u l a t e da n n e a l i n g a l g o r i t h m sa b i l i t yo fl o c a ls e a r c hf e a t u r e s i tt h e nr a i s e st h ec o s tm o d e lo ft h es e l e c t i o n o fm a t e r i a l i z e dv i e w , w h i c hf u l l yt a k e si n t oa c c o u n tt h eq u e r yc o s ta n dm a i n t e n a n c ec o s t f i n a l l y , w i t ht h eg e n e t i ca n n e a l i n ga l g o r i t h ma n dt h e c o s t m o d e l ，i td e s c r i b e s s p e c i f i c a l l yt h ep r o c e s so fm a t e r i a l i z e dv i e ws e l e c t i o n i nt h es p e c i f i cs e l e c t i o np r o c e s s ， t h ep a p e ra l s oi n t r o d u c e st h es o l u t i o no fp o l y n o m i a lb o u n dt od e a lw i t ht h ei n v a l i d a n s w e r a tl a s t ，t h ep a p e ri n t r o d u c e sad y n a m i ca d j u s t m e n to fm a t e r i a l i z e dv i e w c o m m o n a l g o r i t h m so fv i e ws e l e c t i o na r eb a s e do nt h eu s e r st om a k ei n q u i r i e s ，w h i c ha r e d i s t r i b u t e du n i f o r m l y , a n du n c h a n g e df o ral o n gt i m e h o w e v e r ，i nl a r g e - s c a l ed a t a w a r e h o u s ep r o j e c t s ，i ti si m p o s s i b l ef o rt h eu s e r st op r o p o s ea l lt h ed e m a n d s ，a n dw i t h t h ep a s s a g eo ft i m e u s e r sw i l lc h a n g et h e i rd e m a n d s o n c et h eu s e r s d e m a n d sa r e c h a n g e dl a r g e l y , t h ep r e v i o u sm a t e r i a l i z e dv i e w sw i l l n o tb ea b l et om e e tu s e r e n q u i r i e s i ti st o oe x p e n s i v et oo v e r t u r na l lt h ep r e v i o u sm a t e r i a l i z e dv i e w sa n d r e b u i l dn e wm a t e r i a l i z e dv i e w s ，a n di ti sn o ti m m e d i a t e t h e r e f o r e ，t h i s p a p e r p r o p o s e sac o m p r e h e n s i v ed y n a m i c a ls o l u t i o n i nc o n j u n c t i o nw i t ht h er e v e n u em o d e l a n da d j u s t m e n to p p o r t u n i t y , t h es o l u t i o ni sn o to n l ya b l et om a k et i m e l ya d j u s t m e n t st o m a t e r i a l i z e dv i e wp o o l ，b u ta l s oa b l et op r e v e n tf r e q u e n tu p d a t e so fm a t e r i a l i z e dv i e w p o o lt ob r i n gt h en e g a t i v ei m p a c t a n dw ev e r i f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h mb y 湖北工业大学硕士学位论文 t h ee x p e r i m e n t s k e y w o r d s ：d a t aw a r e h o u s e ，o p t i m i z a t i o n ，m a t e r i a l i z e dv i e w , g e n e t i ca n n e a l i n g a l g o r i t h m ，d y n a m i ca d j u s t m e n t h i 溯办j 堂大謦 学位论文原创性声明和使用授权说明 原创 生声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：荡氇b 日期：沙召年s 月西日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：苏求坠 日期：沙萨5 月l 2 5 0 0 0 ； 高效：s e l e c t 书f r o mc u s t o m e rw h e r es a l a r y 2 5 0 0 0 1 2 ； 如果使用前者，列s a l a r y 上的索引不会发生作用，需要在列s a l a r y 上进行全表扫描，效率比较低。而后者则不一样，索引能够产生作用。 3 ) 避免在索引列上使用n o t 和“! = ”，索引只能告诉什么存在于表中，而 不能告诉什么不存在于表中，当数据库遇到n o t 和“! = 时，就会停止使用索引 转而执行全表扫描。 4 ) 索引列上用 = 替代 ，例如： 高效：s e l e c t 书f r o mc u s t o m e rw h e r ea g e = 3 1 低效：s e l e c t 书f r o mc u s t o m e rw h e r ea g e 3 0 两者的区别在于，前者d b m s 将直接跳到第一个a g e 等于3 1 的记录而 后者将首先定位到a g e = 3 0 的记录并且向前扫描到第一个a g e 大3 0 的记录。 5 ) 如果一定要对使用函数的列启用索引，o r a c l e 9 i 以上版本新的功能：基 于函数的索弓 ( f u n c t i o n b a s e di n d e x ) ，比普通的索引效率高，但该类型索引的缺点 是只能针对某个函数来建立和使用，对其它函数无效。例如： c r e a t ei n d e xc u s t o m e r _ io nc u s t o m e r ( u p p e r ( c n a m e ) ) ； s e l e c t 木f r o mc u s t o m e rw h e r eu p p e r ( c n a m e ) = t o m ： 上面的c r e a t e 语句在c n a m e 列上建立了基于函数u p p e r 的索引 c u s t o m e ri ，因此s e l e c t 语句在限定条件u p p e r ( c n a m e ) = t o m 中将会使 用索引c u s t o m e ri 。 1 2 湖北工业大学硕士学位论文 2 合理使用游标 当在海量数据表中进行数据的删除、更新和插入操作时，用游标处理的效率 是最慢的方式，但它在e t l 过程中的使用又必不可少，而且有着及其重要的地位， 所以游标的正确使用尤为重要。对数据仓库维表的数据进行维护时，因为需要保 证维表i d 的一致性，所以采用游标是数据维护完整性的最好方式。由于它的效率 低，如果按照普通的方式将无法处理大数据量的维表数据维护( 一般是指1 0 万条 记录以上的维表) ，以下是处理这种情况的有效方式： 1 ) 在数据抽取的源表中使用时间戳，这样每天的维表数据维护只针对更新日 期为最新时间的数据来进行，大大减少需要维护的数据记录数。 2 、在i n s e r t 和u p d a t e 维表时都加上一个条件来过滤维表中已经存在的 记录，实例为： i n s e r ti n t od i m c u s t o m e rs e l e c t 半f r o mo d s c u s t o m e r w h e r e o d s c u s t o m e r c o d en o te x i s t s ( d i m _ c u s t o m e r c o d e ) 其中o d s c u s t o m e r 为数据源表；d i mc u s t o m e r 为维表。 3 ) 使用显式的游标，因为使用隐式的游标将会执行两次操作，第一次检索 记录，第二次检查t o om a n yr o w s 这个e x c e p t i o n ，而显式游标不执行第 二次操作。 3 w h e r e 子句中的连接顺序 o r a c l e 采用自下而上的顺序解析w h e r e 子句，根据这个原理，表之间的 连接必须写在其它w h e r e 条件之前，那些可以过滤掉大数量记录的条件必须写 在w h e r e 子句的末尾。例如： 低效：s e l e c t 丰f r o mc u s t o m e rcw h e r es a i 。a r y 5 0 0 0 0a n ds e x = m a l e a n d2 5 5 0 0 0 0 和s e x = m a l e 过滤掉了大量的数据。 4 删除全表时用t r u n c a t e 替代d e l e t e 当d e l e t e 删除表中的记录时，有回滚段用来存放可以被恢复的信息，而当 运用t r u n c a t e 时，回滚段不再存放任何可被恢复的信息，所以执行时间也会很 短。同时需要注意t r u n c a t e 只在删除全表时适用，因为t r u n c a t e 是d d l 而不是d m l 。 湖北工业大学硕士学位论文 5 尽量多使用c o m m i t e t l 中同一个过程的数据操作步骤很多，数据仓库采用的是数据抽取后分析 模型重算的原理，所以对数据的c o m m i t 不像业务系统为保证数据的完整性和一 致性而需要某个操作过程全部完成才能进行，只要有可能就在程序中对每个 d e l e t e 、i n s e r t 和u p d a t e 操作尽量多使用c o m m i t , 这样系统性能会因为 c o m m i t 所释放的资源而大大提高。 6 用e x i s t s 替代i n 在许多基于基础表的查询中，为了满足一个条件往往需要对另一个表进行联 接，例如在e t l 过程写数据到模型时经常需要关联1 0 个左右的维表，在这种情况 下，使用e x i s t s 而不用i n 将提高查询的效率。 7 用n o t e x i s t s 替代n o t i n 子查询中，n o ti n 子句将执行一个内部的排序和合并，无论在哪种情况下， n o ti n 都是最低效的，因为它对子查询中的表执行了一个全表遍历。用n o t e x i s t s 替代n o ti n 将提高查询的效率。 8 优化g r o u p b y g r o u pb y 语句在执行过程中非常消耗系统资源，所以为了提高它的执行效 率，尽量将不需要的记录在g r o u pb y 之前过滤掉。例如： 低效：s e l e c ta d d r e s s ，a v g ( a o e ) f r o mc u s t o m e rg r o u p b y a d d r e s sh a v i n ga d d r e s s = b e i j i n g o ra d d r e s s = s h a n g h a i 高效：s e l e c ta d d r e s s ，a v g ( a g e ) f r o mc u s t o m e rw h e r ea d d r e s s = b e i j i n g o ra d d r e s s = s h a n g 心g r o u pb ya d d r e s s 上面两条s q l 语句中，前者是先执行分组操作，然后在分组以后的结果中进 行过滤，而后者一开始就进行过滤操作，之后的分组操作是在一个结果集比较小 的情况下进行，这样就提高了效率。 9 有条件的使用u n i o n a l l 替换u n i o n e t l 过程针对多表连接操作的情况很多，使用u n i o n u 上替换u n i o n 的 前提是：所连接的各个表中无主关键字相同的记录，因为u n i o n u 上将重复输 出两个结果集合中相同记录。 当s q l 语句需要u n i o n 两个查询结果集合时，这两个结果集合会以 u n i o n a l l 的方式被合并，然后在输出最终结果前进行排序。如果用u n i o n 6 血 替代u n i o n ，这样排序就不是必要了，效率就会因此得到提高3 5 倍。 1 0 分离表和索引 总是将表和索引建立在不同的表空间内，决不要将不属于o r a c l e 内部系统 1 4 湖北工业大学硕士学位论文 的对象存放到s y s t e m 表空间里。同时确保数据表空间和索引表空i 、日j 置与不同 的硬盘控制卡控制的硬盘上。 3 20 l a p 优化 物化视图技术是0 l a p 常用的提高查询性能的重要技术之一。物化视图就是为 了使0 l a p 系统能够在尽可能短的时间内回答用户查询而被广泛采用的策略之一。 所谓物化视图就是经过一些简单的数据预处理，譬如，联接、投影、分组等生成 的存储在数据仓库中的实实在在的表n 0 。 数据仓库物化视图主要是三个子问题：视图维护、视图选择、用物化视图进 行查询优化。视图维护是在源数据改变时保持视图与数据源的一致性；视图选择 主要是根据一定条件( 比如大小限制) ，预先选择一批符合条件的视图进行物化操 作，从而最大化提高用户查询效率；用物化视图进行查询优化是指如何将提交的 查询转换为对物化视图的查询，并尽可能的提高效率。这三个子问题还包括一些 具体的相关问题，如视图大小评估佑j 3 、计算视图的依赖性口1 、视图存储的有效结 构喊8 l 。 视图维护：因为物化视图是通过预计算并存储查询结果的，所以当视图定义 中的源表发证变化时，物化视图数据就可能出现与源表不一致的情况。保持物化 视图和源表的一致性是至关重要的。 物化视图的维护策略常见的有两种： 1 重新计算法：直接按照视图的定义，每次更新时重新生成数据。这种策略 很简单，但对系统压力比较大，尤其是当视图的数据量比较大，并且更新较为频 繁时，这种策略可能因为开销过大无法及时满足用户需求，甚至导致服务器崩溃。 2 增量计算法：根据视图的定义和基表的变化，计算出视图的变化，通过简 单的更新，实现视图的维护。 通常情况下，增量计算法比重新计算法会更有效。不过增量算法因为算法复 杂，所以应用也有局限性。 视图选择：在给定查询发在的情况下，选择一组视图进行物化操作，从而达 到最好的查询效率。 在第四章和第五章中将着重讲述物化视图的选择算法。 1 5 湖北工业大学硕士学位论文 3 3 其它优化技术 3 3 1 粒度的选择 在数据仓库逻辑模型设计时，我们采用多重粒度设计。粒度层次划分的适当 与否将直接影响到数据仓库中的数据量和所适合的查询类型。确定数据仓库中的 粒度划分时，可以通过估算数据行数和所需的存储单元数来确定是采用单一粒度 还是多重粒度，在磁盘允许情况下，使用三重粒度结构，最低级的粒度是详细数 据；第二级的粒度是轻度汇总数据；第三级粒度是高度汇总数据。在数据仓库中， 存储的粒度越细，数据仓库回答问题的能力就越强。对于不活跃的数据可以分离 ( 备份到磁带或磁盘上) ，减轻数据仓库刷新和维护的难度。 3 3 2 混合型数据结构 在数据仓库概念模型设计过程中，我们要确定数据模型。目前广为应用的是 星型和雪花型结构。 1 星型结构 星型结构是以事实表为中心，一组维表在星型结构的顶尖，事实表和维表通 过键连接在一起。 星型结构是非范式的、以查询为中心的模型，它的最大优点是能够提供所谓 的星连接，即通过一次连接就可以获取大部分所需要的信息，并很快得到输出结 果。 星型模型图如下图3 1 所示： 1 6 湖北工业大学硕士学位论文 图3 1 星型模型图 2 雪花型结构 雪花型结构是星形型结构的扩展，在实际建模过程中常常会出现这样的情况， 单纯的星形结构已不能满足实际应用的需求，特别是在有效的描述维表的复杂层 度和层次时会出现困难。可选择的解决办法是，在星形结构基础上对某些维进行 扩展，即用一组或多组数据表与某些维相连接。这样即由星形结构进一步演变成 雪花型结构。 雪花模型图如下图3 2 所示： 1 7 湖北工业大学硕士学位论文 图3 2 雪花型模型图 二者相比，不难发现，星形模型有比较高的查询效率，而雪花模型则有更加 清晰的层次结构，更适合做多维分析( 上卷，下钻) 。因此，我们采用星型模型和 雪花模型的一种折中模式，即混合型数据结构。在混合型数据结构中只有最大的 维表才进行标准化。目前也可以根据一些算法来解决星型模型和雪花模型的选择 问题。 3 3 3 索引技术和分区技术 出于数据仓库的特点：数据量庞大，数据比较稳定，很少有更新和删除操作， 建立索引会带来很大的好处。但是，索引是一把双刃剑，能提高读取速度，也会 使数据更新速度降低，并占用大量磁盘空间。索引的建立与查询和数据更新有直 接关系。对记录庞大的事实表查询符合条件的记录时，依据相关条件建立索引， 系统性能一般会有巨大改进，但是，如果索引对数据的区分度太差，没有此索引 反而更好。增加索引，将使数据插入与删除性能降低，数据更新速度则可能提高。 所有这些需要综合考虑，以建立合适的索引。 常用的索引主要包含两类：b t r e e 索引和位图索引。b t r e e 索引就是通常所见 的唯一索引、聚簇索引等等。b t r e e 一般用在高基数( 即列的数据相异度大) 。因为 查询速度比较快，主要用于o l t p 系统中。位图索引的基本原理是在索引中使用位 图而不是列值。通常情况下，索引都要耗费比较大的存储空间，位图索引采用压 1 8 湖北工业大学硕士学位论文 缩技术缩减磁盘空间。同时，位图索引将比较，连接和聚集都变成了位算术运算， 大大减少运行时间。所以，在数据仓库中我们一般采用位图索引，目的在于加快 查询速度，节省磁空间。 索引建立通常遵循以下原则： 1 要考虑索引对加载效率的影响。可以在加载时先删掉索引，待加载完成再 建立索引。 2 大表不宜建立多个索引。 3 必要的时候，将少量经常需要访问的数据都包含在索引中。 4 经常用做查询的列作为索引列。 5 分阶段建立索引，通过监视系统性能确定要建立索引的表跟列。 在事实表上建立索引遵循的原则有： 1 在全部的主键上要建立b t r e e 索引。 2 建立组合索引。在组合键中，经常用于查询的列作为组合中级别高的键。 3 包括指标的列也有建立索引的可能性。 4 位图索引不适用于事实表，因为事实表中基本没有低选择性的列。 在维度表上建立索引遵循的原则有： 1 在单一主键上建立唯一的b t r e e 索引。 2 在查询经常用到的列上建立位图索引。 3 在经常被一起访问的列上建立索引，维度表中层次比较高的列在多列索引 中有较高的位置。 4 在经常用于连接的列上建立单独的索引。 数据分区技术是数据仓库中有效的存储管理技术。数据分区是为了将数据仓 库中的大表和它的索引分成可管理的几个部分。从而使得它们的维护和操作简单 迅速。分区包括水平和垂直分区。在数据仓库中经常做基于日期的水平分区。在 建立分区后，查询只需要访问必要的分区而不是整个表。如何进行适当的分区， 对分区如何进行并行查询和维护，如何分区才能使得更加易于加载数据及管理， 这些都是目前研究的重点。 3 4 本章小结 本文针对数据仓库中数据建模、数据抽取、联机分析这几个方面给出了一些 常用的优化方法。着重是针对数据抽取中的优化技术进行研究，通过在数据经营 分析系统中的实践经验，并结合已有的优化规则，整理出了比较全面的优化技术。 1 9 湖北工业大学硕士学位论文 第4 章基于遗传退火算法的物化视图选择 在上一章中提出了联机分析处理中采用物化视图进行优化。物化视图中可待 研究的内容比较多，而且每个方向要深入研究难度也很大。现在研究的比较多的 是物化视图的增量维护算法和物化视图的选择算法。本文就后者一一物化视图的 选择算法进行研究。 数据仓库中的物化视图选择问题己被证明是一个n p h a r d 问题。其算法的复 杂度会随着维度数量的增加呈指数上升。前人对此提出了很多解决方案及算法。 然而已有物化视图选择的研究并没有为工程的实际应用提供很大帮助，现有研究 跟工业中所要求的稳定性、健壮性有一定的距离，因而数据仓库的商业产品对物 化视图自动选择支持不够好。基于此，本文对物化视图选择问题进行研究，并考 察了现有的数据仓库物化视图选择理论，探寻更具可实现性的物化视图选择方案。 4 1 物化试图选择算法的必要性 显然，物化视图的数量越多，使用物化视图能够回答的查询就越多，从而越有 利于缩短系统响应查询时间，提高效率。然而物化视图选择还要考虑很多负面因 素。 首先物化视图需要占用存储空间，物化视图技术属于一种空间换时间的技术。 物化很多的视图，对于存储空间的要求肯定是很难接受的。对于有n 个维的数据 立方体，假设每个维只有一个级，其所有的视图个数为2 n ，全部物化的大小可能 为所有基表的几倍，甚至几十倍。 其次，当物化视图的源数据发生变化时，建立在其上的物化视图需要维护，以 保持数据的一致性。对于数据量巨大的数据仓库来说，维护物化视图是不小的开 销。 因此，物化视图并不是越多越好，物化所有的视图更是不可行的。不但会占用 大量的存储空间，而且会有很大的维护开销。但是，如果不采用任何物化措施， 那么查询响应时间会很长，也不可取。通常的做法是通过一定的算法，选择出部 分视图进行物化，寻求一种效率与开销之间的平衡。在可以接受的开销内，达到 最好的性能。 2 0 湖北工业大学硕士学位论文 4 2 现有物化试图选择算法 4 2 1 简单贪心算法 文献 1 5 ，1 6 中提出了简单的贪心算法。它每次选择一个当前看来是最优的 视图，即相对当前己选定的物化视图集来说单位空间物化收益最大的那个视图， 直至所选择的物化视图的总空间超过事先给定的空间限制为止。 算法4 1 简单贪心算法 输入：空间限制s ，视图集v ，视图集v 中每个视图v 的查询频率f ( v ) ，结果 集长度l ( v ) ，结果集所占空间s ( v ) 。 输出：满足空间限制的物化选择m 。 开始： m _ t o pv i e w ； s = s s ( t o pv i e w ) ； w h i l e ( s 0 ) m a x b e n e f it = o ；m a x b e n e f it 表示最大效益 f o re a c hu v ，u 硅md o i f ( m a x b e n e f i t 0 ) v = f i r s t ( v ) ： v = v - v ) ： m = mu v ) ； s = s s ( v ) ： ) 结束 对于一个视图集包含n 个元素的问题，排序算法的复杂度主要由排序过程采 用的算法决定，可以采用快速排序，时间复杂度为0 ( n l o g n ) ，相比前面的简单贪 心算法要低得多。p b s 算法的复杂度虽然有了极大的改善，但该算法是以损失物化 选择解的质量为代价，因而在实用性上依然没有根本的改进。 湖北工业大学硕士学位论文 4 2 3 一般遗传算法 为了弥补上面算法的不足，文献 1 8 提出了用遗传算法来解决物化视图选择 问题，并用实验证明了用遗传算法解决物化视图选择问题，会比上面提到的算法 更加优化。 一般遗传算法是通过模拟生物进化的自然选择和遗传机制的一种寻优算法 h 引。它模拟了生物的繁殖、交配和变异现象，从任意初始种群出发，产生一群新 的更适应环境的后代。这样一代代不断繁殖、进化，最后收敛到一个最适应环境 的个体上。遗传算法对于复杂的优化问题无需建模和进行复杂运算，只需利用遗 传算法的算子就能寻找到问题的最优解或满意解。 遗传算法中，将n 维决策向量x = x 。，x 。，ex 。 t 用n 个记号x 。( i = 1 ，2 ，ee 9n ) 所 组成的符号串表示： x = x 1 x 2 x 。= x = x i ，x 2 ，x n 1 把每一个x ；看作一个遗传基因，它的所有可能取值称为等位基因，这样，x 就可以看作是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度n 是固定的，但对有些问题n 也可以是变化的。根据不同的情况，这里的等位基因 可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。最简 单的等位基因是由0 和1 这两个整数组成的，相应的染色体就可以表示为一个二 进制符号串。这种编码所形成的排列形式x 是个体的基因型，与它对应的x 值是 个体的表现型。通常个体的表现型和基因型是一一对应的。染色体x 也称为个体x ， 对于每一个个体x ，要按照一定的规则确定出其适应度。个体的适应度与其对应的 个体表现型x 的目标函数值相关联，x 越接近于目标函数的最优点，其适应度越大； 反之，其适应度越小。 遗传算法的运算过程是一个反复迭代的过程，第t 代群体记做p ( t ) ，经过一 代遗传和进化后，得到t + l 代群体，记做p ( t + 1 ) 。这个群体经过不断的遗传和进 化操作，并且每次都按优胜劣汰规则将适应度高的个体更多遗传到下一代，这样 最终在群体中将会得到一个优良的个体x ，它所对应的表现型x 将达到或接近于问 题的最优解。 生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与 此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓 的遗传因子作用于群体p ( t ) ，从而得到新一代群体p ( t + 1 ) 。 选择：根据各个个体适应度，按照一定规则或方法，从第t 代群体p ( t ) 中选 择一些优良的个体遗传到下一代群体p ( t + 1 ) 中。 湖北工业大学硕士学位论文 交叉：将群体p ( t ) 内各个个体随机搭配成对，对每一对个体，以某个概率交 换他们之间的部分染色体。 变异：对群体p ( t ) 中每一个个体，以某一概率改变某一个或某一些基因座上 的基因值为其它的等位基因。 尽管一般遗传算法以其独特性，在解决物化视图选择上取得了很好的效果。 但是它也存在着一些不足之处： 1 ) 早熟现象 在遗传算法的初期阶段，群体中可能会出现少数几个个体适应度相对其他个体 来说非常高。若按照常用的比例选择算子来确定个体的遗传数量时，则这几个相 对较好的个体将在下一代群体中占有很高的比例，在极端情况下或群体规模较小 时，新的群体甚至完全由这样的少数几个个体组成。这时产生新个体作用较大的 交叉算子就起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永 远不会产生出新的个体，如下所示： a ：101010 ：1010a ：101010 ：1010 单点交叉一 b ：10101o ：1010b ：101010 ：1010 这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象，使遗传算 法所求到的解停留在某一局部最优点上。 劲局部搜索现象 在遗传算法运行的后期阶段，群体中所有的个体的平均适应度可能会接近于群 体中最佳个体的适应度。也就是说，大部分个体的适应度和最佳个体的适应度差 异不大，它们之间无竞争力，都会有以相接近的概率被遗传到一代的可能性，从 而使得进化过程无竞争性可言，只是一种随机的选择过程。 从生物的自然进化角度讲，虽然进化的最终结果是使物种向最适应于环境的 方向发展，但是遗传和进化的中间结果并非总是优良的，在进化过程中也可能会 出现一些比优良品种要差一些的个体，它们不能排除在物种之外，而应是物种整 体中的一员。 4 2 4 各算法的不足 从上面的描述可以看出，目前已经有很多算法被运用在物化视图的选择上。 但是都有各自的缺陷。简单贪心算法【1 5 , 1 6 1 复杂度太高，在由n 个维组成的多维数 据集中，其复杂度为o ( k 2 2 n ) 。排序算法【1 7 】的复杂度为o ( n l o g n ) ，相比简单贪心算 法其复杂度要低得多。但该算法是以损失物化选择解的质量为代价，因而在实用 湖北工业大学硕士学位论文 性上没有根本的改进。 而在文献【1 8 】中提出了，用遗传算法来解决物化视图的选择问题。但是，应用 研究表明，目前一些常规遗传算法并不一定是针对某一问题最佳求解方法。而将 遗传算法与问题的特有知识集成到一起构成的混合遗传算法，却有可能产生出求 解性能极佳的方法。一般的遗传算法已经被证实了在物化视图的选择上能够很好 提高性能。但是当多维数据集变得非常复杂，即维度数量非常大时，一般的遗传 算法的搜索速度会大大降低，还会产生早熟和局部搜索现象。而且一般的遗传算 法在针对物化视图选择过程中产生的无效解没有很好的处理办法。它们通常的做 法是控制遗传因子，使得只能产生有效解；或者是允许产生无效解，但在适应度 函数中加入惩罚函数。前一种方法可以防止产生无效解，但会影响解的多样性， 得不到全局最优解；而后者在选择合适的惩罚函数难度也很大【19 1 。因此，在物化 视图的选择问题上，我们引入遗传退火算法，在以后的章节中，证实了它能够很 好的解决一般遗传算法中存在的不足。 4 3 遗传退火算法 在遗传算法中引入模拟退火算法，而形成的遗传退火算法能够解决基本遗传算 法中的很多不足。一般遗传算法的局部搜索能力较差，但把握搜索过程总体能力 比较强；而模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程 进入最优希望的搜索区域，从而使得模拟退火算法的运算效率不高。但如果二者 结合，取长补短，则能开发出性能优良的全局搜索算法。 4 3 1 模拟退火算法概述 在金属热加工工艺中，退火是指将金属材料加热到某一高温状态，然后让其 慢慢冷却下来这样一个金属热处理过程h3 1 。模拟退火算法就是基于金属退火的机理 而建立的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标 函数的全局最小点。模拟退火算法的构成要素如下： 1 搜索空间q 搜索空间也称为状态空间，它由可行解的集合所组成，其中一个状态x 就代 表一个可行解。 2 能量函数e ( x ) 能量函数也就是需要进行优化计算的目标函数，其最小点为所求最优解。 3 状态转移规则p 湖北工业大学硕士学位论文 状态转移规则是指从一个状态x 。l d ( 一个可行解) 向另一个状态x n 州( 另一个 可行解) 的转移概率，它与当前的温度参数t 有关。 4 冷却进度表t ( t ) 冷却进度表是指从某一高温状态向低温状态冷却时的降温管理表。假设时刻t 的温度用t ( t ) 来表示，则经典模拟退火算法的降温方式为： t ( t ) = ! ! 。l g o + f ) 而快速模拟退火算法的降温方式为： t ( t ) ：旦 l + t 这两种方式都能够使得模拟退火算法收敛于全局最小点。 在实际应用中，为计算简便起见，也可以用下式进行温度管理： t ( t ) = k 宰t ( t 1 ) 其中，k 是约小于1 0 的系数。 模拟退火算法在搜索过程中可能会陷入局部最优点，这时为了能够到达全局 最优点，必须允许能量函数的值可以一时增大。假设在状态x o l d 时，系统受到某种 扰动可能会使其状态变为x n 鲫。与此相对应，系统的能量也会从e ( x o l d ) 变成 e ( x n 一。系统由状态x o l d 变为x n c w 的接受概率可由下面的规则来确定： f p = 1 ，e ( x n e w ) e ( x o l d ) 1p = e x p ( 堕掣) ，e ( x n e w ) e ( x o l d ) l l 模拟退火算法描述如下： 1 ) 随机产生一个初始最优点，以它作为当前最优点，并计