（管理科学与工程专业论文）数据仓库环境下的物化视图选择研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 数据仓库的出现可以将海量历史数据以一致的视图提交给用户，方便用户对 其进行联机分析查询( o l a p ) ，但其往往包含了大量聚合操作，复杂度很高，如何 提高数据仓库性能以便快速响应o l a p 查询成为了研究热点。物化视图是克服这 一问题的关键技术之一，它将可能的查询进行预处理并将结果保存于数据仓库之 中，这样可以有效降低查询的代价，缩减回答查询的时间。但是在实际应用过程 中，这种物化受到了空间、时间等限制，不可能将所有视图都进行物化，而且不 同视图之间存在一定的依存关系，完全物化反而会带来冗余，因而必须对视图集 进行有选择的部分物化，这对提升数据仓库性能至关重要。本文正是基于这一问 题对数据仓库环境下的物化视图选择进行了研究，主要工作可以概括为以下四点： ( 1 ) 深入分析了物化视图选择问题的基本研究方法，对此问题进行了形式化描 述；对现有的研究成果进行综述，并且对比分析了这些算法各自的优缺点，指出 了现有算法中存在的不足。 ( 2 ) 提出了一种改进型b p u s 视图选择算法m q m v s ，它首先通过冗余视图压 缩的方式来化简原始视图格，并且将物化视图选择过程划分为两个阶段，即查询 视图选择和维护视图选择，实现了对查询和维护的全局优化，通过实验表明该算 法在效率和性能上均优于传统静态物化视图选择算法。 ( 3 ) 在静态物化视图选择的基础上提出了动态优化算法，该算法可以通过视图 索引来实现视图的动态特性，缓解了静态物化视图选择过程中出现的空间一性能 饱和问题，通过实验可以证明动态优化后的物化视图集性能优于单纯的静态物化 视图集。 ( 4 ) 结合超市数据仓库的开发实例，将本文提出的物化视图选择算法应用其 中，开发了o l a p 分析展现客户端对数据仓库进行分析展现，事实证明物化后的 数据仓库运行性能明显提升。 主题词：数据仓库o l a p 维护查询物化视图选择动态视图索引 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t d a t a w a r e h o u s ec a ni n t e g r a t et h em a g n a n i m o u sh i s t o r i a ld a t at oac o n s i s t e n tv i e w i no r d e rt oe x e c u t e0 l a p q u e r i e sc o n v e n i e n t l yf o r t h ee n du s e r s b u tt h e0 l a pq u e r i e s a l w a y sc o n s i s to fl o t so fa g g r e g a t i o no p e r a t i o n , w h i c hh a v eh i 曲c o m p l e x i t yf o r c a l c u l a t i o n h o wt oi m p r o v ep e r f o r m a n c eo fd a t a w a r e h o u s ef o ra n s w e r i n gt h e0 l a p q u e r i e si sah o ti s s u ei nd a t a w a r e h o u s er e s e a r c h m a t e r i a l i z e dv i e w sc a np r e c o m p u t e t h e0 l a pq u e r i e sa n ds t o r et h er e s u l ti nt h e i tc a nd e c r e a s et h ec o s to f0 l a pq u e r i e s a n dt h et i m eo fa n s w e r i n gt h e0 l a pq u e r i e se 伍c i e n t l y b u ti nt h er e a lw o r l d m a t e r i a l i z e dv i e w sw i l lb ec o n s t r a i n e db ys u c ha ss t o r a g es p a c eo rm a i n t e n a n c et i m e ，8 0 d a t a w a r e h o u s ec a n tm a t e r i a l i z ea l lp o s s i b l ev i e w s a sw ek n o w d i f f e r e n tv i e w sh a v e d e p e n d e n tr e l a t i o n s h i pb e t w e e ne a c ho t h o r m a t e r i a l i z e da l lv i e w sw i l lg e n e r a t e r e d u n d a n c e ，s ov i e w sm a t e r i a l i z a t i o ni nd a t a w a r e h o u s ei sak i n do fs e l e c t i o n m a t e r i a l i z a t i o n f i n d i n ga no p t i m a ls e to fm a t e r i a l i z e dv i e w si si m p o r t a n tf o rt h e d a t a w a r e h o u s e n l i sp a p e rf o c u s e so nm a t e r i a l i z e dv i e w ss e l e c t i o ni nd a t a w a r e h o u s e e n v i r o n m e n t ，t h em a i nc o n t r i b u t i o no ft h i sw o r kc a no u t l i n eb e l o w ： ( 1 ) i td e e p l ys t u d i e dt h em a t e r i a l i z e dv i e w ss e l e c t i o np r o b l e m ，a n dg i v et h e f o r m a l i z e df o r m u l a t i o no ft h i sp r o b l e m i to v e r v i e w e dp r e s e n tm e t h o dw h i c ha d d r e s s e d m a t e r i a l i z e dv i e w ss e l e c t i o np r o b l e m ，p o i n t e do u tt h ed r a w b a c k so ft h ed i f f e r e n t m e t h o d ( 2 ) i tp r o p o s e da na d v a n c e db p u sa l g o r i t h mn a m e dm q m v s i tf i r s t l ys i m p l i f i e s t h eo r i g i n a lv i e wl a t t i c eb yv i e wr e d u n d a n c e a n dt h e nd i v i d e ss e l e c t i o np r o c e s si n t ot w o p h a s e s o n ei sq u e r ym a t e r i a l i z e dv i e w ss e l e c t i o na n da n o t h e ri sm a i n t e n a n c e m a t e r i a l i z e dv i e w ss e l e c t i o n t i l i sm e t h o dc a ni m p l e m e n tt h eq u e r ya n dm a i n t e n a n c e g l o b a lo p t i m i z e d e x p e r i m e n tr e s u l t sd e m o n s t r a t et h ee f f i c i e n c ya n dp e r f o r m a n c eo ft h i s m e t h o di sb e t t e rt h a nt h ec l a s s i cs t a t i cm a t e r i a l i z e dv i e w ss e l e c t i o na l g o r i t h m ( 3 ) i tp r o p o s e dd y n a m i co p t i m i z e dm e t h o db a s e do ns t a t i cm a t e r i a l i z e dv i e w s s e l e c t i o n t h i sm e t h o du s e st h ev i e wi n d e xt e c h n o l o g yt oi m p l e m e n tt h ed y n a m i c c h a r a c t e r i s t i co fs t a t i cm a t e r i a l i z e dv i e w i tc a ns o l v et h ep r o b l e mo fs p a c e p e r f o r m a n c e s a t u r a t i o n e x p e r i m e n t r e s u l t ss h o wt h a tt h ed y n a m i c o p t i m i z e d s e to fs t a t i c m a t e r i a l i z e dv i e w si sb e t t e rt h a no n e st h a ta r es e l e c t e db yp u r em q m v s a l g o t i t h m ( 4 ) b a s e do nt h ec a s eo fs u p e r m a r k e td a t a w a r e h o u s e ，w ep r e s e n th o wt ou t i l i z e t h em e t h o dp r o p o s e di nt h i sp a p e r f i n a l l y ，t h ed a t a w a r e h o u s eo ft h i sc a s ei s r e p r e s e n t e db yao l a pc l i e n t ，a n dt h ep e r f o r m a n c ei sp r o m o t e de f f i c i e n t l y k e yw o r d s ：d a t a w a r e h o u s e o l a p m q m v s ( m a i n t e n a n c eq u e r y m a t e r i a l i z e dv i e ws e l e c t i o n d v l ( d y n a m i cv i e win d e x ) 第i i 页 国防科学技术大学研究生院硕士学位论文 表 表 表 表 表3 5 表4 1 表5 1 表5 2 表5 3 表5 4 表5 5 表5 6 表5 7 表目录 视图格结点大d , n 表2 9 查询视图选择过程表2 9 维护视图选择过程表31 c m v s 算法实验结果列表3 7 算法执行效率对比分析表3 7 某时刻视图状态信息列表5 0 商品维度5 5 客户维度5 5 时间维度5 5 供货商维度。5 6 销售事实表。5 6 字母定义表。5 7 m q m v s 参数设置表5 8 i i i 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 数据仓库架构2 图1 2 物化视图问题关系图3 图1 3 物化视图选择算法分类图4 图1 4 动态物化视图选择过程示意图6 图1 5 论文研究思路9 图2 1 三维h y p e r c u b e 格模型l3 图2 2m v p p 模型示例。15 图2 3a n d o r 图示例。16 图2 4d y n a m a t 算法示意图2 1 图3 1 冗余视图示例2 4 图3 2 冗余视图化简2 4 图3 3 维护视图示例3 0 图3 4 物化视图选择实验平台截图一3 6 图3 5不同物化视图选择算法结果对比3 7 图3 6 不同算法时间消耗分析图。3 8 图3 7 实时查询响应时间分析图一4 0 图3 8 查询集合平均响应时间分析图一4 0 图3 9 查询空间对查询维护性能的影响图。4 1 图3 1 0 最小视图门限影响图。4 2 图4 1 实际物化性能一4 3 图4 2 理想物化性能4 3 图4 3 动态与静态结合视图选择算法流程图。5 1 图4 4 实时查询响应时间分析图。5 2 图4 5 物化空间性能分析图5 2 图4 6 吞吐量测试分析图。5 3 图5 1超市数据仓库星型模型5 6 图5 2 超市数据仓库的视图格5 7 图5 3 选择结果5 9 图5 4o l a p 分析展现客户端模块图6 0 图5 5 超市数据仓库分析示例( a ) 6 1 图5 6 超市数据仓库分析示例( b ) 6 1 i v 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 学位论文作者签名： 日期：加，夕年，月移日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签名： 作者指导教师签名： 存羽 j 亨，字 7 7 l ， 日期：年月 日 慨研钏月哆日 国防科学技术大学研究生院硕十学位论文 第一章绪论弟一早珀t 匕 1 1 研究背景及意义 随着信息技术不断发展，大量m i s 系统已经应用于各行各业，它们对企业的 绩效产生了深远影响，与此同时，各种各样的数据也被不断的采集并存储于介质 当中。这些数据随时间快速增长，其数量和复杂度均超出了人的分析能力，显然， 通过传统的m i s 系统也无法很好的处理这些数据，这就意味着数据无法发挥其应 有的价值，因而如何从这些海量数据中提取信息成为了信息系统领域研究的重点。 为了解决“数据爆炸和“信息匮乏 的问题，人们提出了基于数据仓库的 数据辅助决策技术，它的核心技术正是数据仓库。通过数据仓库可以将分布异构 的各种数据源数据进行集成，提供给用户一致的多维视图，从而支持多种分析需 求，辅助用户对决策信息进行获取。数据仓库可以认为是数据库的一个延伸，它 将传统m i s 系统中收集的数据进行清洗转换，提高了数据的一致性，它可以在更 高层次对历史数据进行统计分析。在商务智能领域数据仓库也发挥了巨大作用， 现有的绝大多数数据库软件开发商均在产品中支持数据仓库的解决方案，例如m s s q ls e r v e r 的s s a s 以及o r a c l e 的e x p r e s s 等，它们可以帮助电信业、零售业 和金融业快速开发专用的数据仓库系统，为它们的战略决策提供汇总信息。从目 前的形势来看，数据仓库已成为信息社会中获得企业竞争优势的关键，据i d c 统 计l l j ：但凡进行数据仓库项目开发的公司在平均2 - - 3 年的时间内获得的回报率超 过4 0 0 。对于数据仓库的分析应用而言，联机分析处理( o l a p ) 其重要功能之一， 通过o l a p 查询可以快速发现数据背后隐藏的信息以用来辅助决策，但是o l a p 查询在执行过程中往往需要涉及大量的数据，并且需要计算许多复杂的聚合操作， 这是一个非常耗费时间的过程，它与o l a p 在线分析的特点相矛盾，因而为了解 决这个问题，还需要对数据仓库优化技术进行深入研究。 物化视图是目前应用较广的数据仓库优化技术，在数据仓库领域关于此问题 的研究已有数1 0 年历史。物化视图与数据库中的传统视图不同，它不是以虚拟的 方式存在，而是经过预计算，包含大量数据并进行物理存储的数据表。通过这些 预先计算好的物化视图，o l a p 查询计算就可以直接在物化视图上进行简单的处理 来得到结果，避免了在原始数据表上执行复杂操作。通过物化视图，数据仓库的 性能可以成倍提高，它也构成了实现o l a p 在线分析的重要手段。但是物化视图 的引入又会带来新的问题，因为物化视图是有代价的，它受到磁盘空间、计算和 维护时间等因素的制约，若是将所有查询的结果都予以物化，那么其高昂的代价 必然会超出数据仓库的开发成本。为了在性能和费用上取得折衷，往往采用选择 第1 页 国防科学技术大学研究生院硕士学位论文 部分视图进行物化的策略，这就需要在设计物化视图时给定约束条件，例如空间 或时间上的约束，同时还要制定视图的评估准则，通过这些准则可以定量分析每 个视图的收益，最后在满足约束条件下尽可能选择收益最大的视图集进行物化， 使整个数据仓库所支持的查询响应时间满足用户要求。本文的研究正是建立在此 问题之上，通过对物化视图选择问题的研究，提出了一种合理的物化视图选择算 法，它可以显著提高数据仓库的查询性能，并且该算法具有较好的通用性和较高 的实用价值，可用于数据仓库环境下的物化视图设计过程。 1 2 研究现状及发展趋势 1 2 1 数据仓库、o l a p 及物化视图技术 数据仓库的概念最早由i n i n o n 在构建数据仓库一书中提出，它是一个面 向主题( 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 ) l 拘数据集合，用于支持管理决策【1 训，它的基本架构可以用图1 1 表示： 图1 1 数据仓库架构 数据仓库把现实世界中各种不同的数据源进行了数据抽取、转换和装载，并 在原始数据源上构建了新的数据模型，即多维数据模型，这符合用户多角度分析 数据的需求。数据仓库的建立给人们提供了很好的数据分析平台，它包含了大量 的历史数据，十分有利于进行决策分析。 为了更好的对数据仓库中的数据进行分析，e f c o d d 在1 9 9 3 年又提出了联 机分析处理( o l a p ) 技术【孓7 1 ，与传统的o l t p 技术不同，它允许用户方便的对信息 以多种可能的观察角度进行快速、一致和交互性的存取，以获得对数据的深入理 第2 页 黾目 国防科学技术大学研究生院硕士学位论文 解，o l a p 强调数据组织必须是多维的，每个维度代表用户可能的分析角度，以这 种方式组织的数据在o l a p 中被形象地称之为多维数据立方体。在o l a p 中，数 据立方体包含了维度，度量，维层次以及聚合关系，针对多维立方体，o l a p 还定 义了一组运算集，分别为钻取，切片和旋转。正是由于钻取操作的引入，o l a p 查询需要频繁的对度量按照维层次进行聚合，它可以是s u m ，m a x ，m i n 等操作，而 数据仓库中的数据量十分巨大，重复的存取必然导致0 l a p 查询性能的下降，为 了解决查询的快速响应，物化视图技术被引入数据仓库领域。 物化视图有别于仅存储结构定义的虚拟视图，它是经过预计算并存储在数据 仓库中的物理数据表。在数据仓库中，物化视图往往由一组维的取值和聚合的度 量值构成，因而常常称之为汇总表。从软件工程的角度，数据仓库就是一组物化 视图的集合。关于数据仓库环境下的物化视图技术，它的研究范围可以用图1 2 表 示： 图1 2 物化视图问题关系图 通过图1 2 可以看出，物化视图选择问题是数据仓库环境下物化视图研究的核 心，它连接了其余的一些研究领域，将其构成一个整体。下文将对物化视图选择 算法的研究现状进行简要叙述。 1 2 2 物化视图选择算法研究现状 关于数据仓库中的视图物化选择问题最早由h a r i n a r a y a n 提出，他在文献 8 】 中对此问题进行了系统阐述，从而开启了此领域的研究，并且很快成为数据仓库 第3 页 国防科学技术大学研究生院硕士学位论文 研究领域的热点问题，出现大量的研究成果。对于数据仓库中物化视图选择算法 的分类，目前有较多种，例如：根据其约束条件 9 1 ，选用的代价模型【1 0 】等等，为了 简单起见，本文采用文献【1 1 】中的分类法，可用图1 3 表示： 图1 3 物化视图选择算法分类图 下面将按照物化视图选择问题的分类对现有方法进行分析研究，掌握当前的 研究现状。 1 2 2 1 静态物化视图选择算法 所谓静态物化视图选择算法，是指此算法所选择的视图一旦物化，在数据仓 库运行时就不再改变，它属于数据仓库设计时的物化视图选择算法，关于这方面 的研究成果非常多也相对成熟。 启发式算法 物化视图选择问题属于一类n p 完全问题，它无法在多项式范围内进行求解， 目前很多算法都采用了启发式算法的思想。h a r i n a r a y a n 在文献【8 】提出了b p u s 算 法，他通过视图依赖格模型和视图收益模型从定量角度实现了物化视图自动选择， 并且用理论推导证明了b p u s 算法所求解与最优解之间的收益比不低于0 6 3 。 b p u s 算法是物化视图研究领域很经典的算法，目前有很多改进算法，如文献【1 2 】 中提出的双向搜索算法a s e a r c h ，此算法在理论上可以取得最优解，但因其复杂 性过高导致实用性很低。文献【1 3 】提出一种p b p u s 算法，它在查询代价中考虑了 查询分布的影响，使得b p u s 算法的效率有所提高。文献 1 4 ，1 5 贝t j 从算法的复杂 度出发，提出一种p g a 方法，通过两轮循环计算，将算法的复杂度控制在多项式 级别，并且用实验证明算法的效率不亚于b p u s 算法。文献 2 3 2 5 研究了b p u s 及其改进方法实现技术并对它们进行了对比分析。 为了更进一步解决物化视图选择问题，g u p t a 在a n d o r 模型上利用了启发 式算法，提出了i n n e r l e v e lg r e e d y ，i n v e r tt r e eg r e e d y t l 9 - 2 3 1 ，解决了以维护代价作 为约束条件的物化视图选择问题。文献 2 3 禾r j 用m v p p 模型解决了分布式数据仓库 第4 页 国防科学技术大学研究生院硕十学位论文 的物化视图选择问题，并且提出了一套物化视图选择计算框架，它的基本思想仍 然是启发式算法。由于在文献 2 4 】中并未考虑维护问题带来的影响，因而文献 2 5 ， 2 6 q b 对其工作进行了完善，进一步考虑了维护因素的影响。 尽管上述方法可以提供较好的解，但其大部分算法复杂度都与维度成指数关 系，因而实用性不强，于是文献 2 7 】提出一种p b s 算法，该算法的复杂度仅为n l o g n ， 因为它只需按大小对视图进行排序，但是该算法的求解精度不高，作者指出只有 当立方体为s r - c u b e 时，p b s 的性能与b p u s 一致。 随机搜索算法 该类算法主要是将随机搜索算法应用于物化视图选择问题，国内外也对此类 算法进行了大量研究。k a l n i s 率先将众所周知的进化算法引入物化视图选择问题 2 8 】，近来研究人员又将两阶段优化算法 2 9 0 1 、模拟退火【3 l 】、遗传算法【3 2 。5 1 以及蚁 群算法【3 6 j 应用到了物化视图选择问题。关于将随机算法应用于视图选择问题的研 究成果还有很多，这里不再一一罗列。这些算法在经历多次迭代后可以获得较好 的解集，但其计算代价太高，算法的研究仅停留在理论阶段，如何加快算法收敛 是该类算法亟待解决的问题。 数据挖掘算法 这类物化视图选择算法有两种思路，一种是将所有可能的视图进行聚类，然 后将聚簇中视图的共同前缀予以物化【3 7 3 8 】；另一种则是对查询集进行聚类，主要 根据聚合属性确定查询的类别，然后将每一类的查询对应的视图进行物化【3 9 4 1 1 。 基于数据挖掘的视图选择算法属于较新的研究，目前的研究成果还较少。 混合算法 混合算法是指将物化视图选择问题与其它问题一同考虑，并行优化的视图选 择算法。一种方法是将物化视图选择与物化视图计算相结合，在选择物化视图的 同时考虑物化视图计算引起的开销，尽可能降低物化视图计算代价【4 2 ，4 3 1 ，典型的 研究有文献 4 4 4 8 ；另一种方法是将物化视图选择与索引相结合，在选择物化视 图的同时对索引进行选取，这样可以加快聚合时的连接操作，这方面典型的研究 有文献 1 9 ，3 9 ，4 9 5 2 】；还有则是将物化视图选择与查询重写相结合，在选择物化 视图的同时考虑如何利用物化视图来重写查询，典型的研究有文献 5 3 ，5 4 】。 其它算法 文献 5 5 1 提出了一种由视图相关性驱动的物化视图选择算法，通过视图之间的 相关性可以降低物化视图选择过程的复杂性；文献 5 6 】通过定义收益模型和损失模 型，每次选择视图时均根据二者的取值来判断，从而保证了算法求解的准确性； 文献【5 7 】提出的s o m e s ( u s e r o r i e n t e dm a t e r i a l i z e dv i e ws e l e c t i o n ) 算法考虑了不同 用户查询分析需求的差异，它可以为每个用户根据其需求设定不同的物化视图集； 第5 页 国防科学技术大学研究生院硕士学位论文 文献 5 8 】以查询响应时问作为约束条件来对物化视图进行选择，它可以将查询时间 限定在约束范围之内，符合特定应用的需求；文献 5 9 6 2 采用了基于框架的算法， 通过定义视图选择框架，可以将现有的算法嵌入其中，同时降低现有算法的复杂 度。关于静态视图选择还有很多方法，这里不再赘述。 1 2 2 2 动态物化视图选择算法 对应于静态物化视图选择算法，动态物化视图选择强调选择过程的动态性， 它可以随着数据仓库应用的迁移改变物化视图集，这种思路符合o l a p 随机分析 查询的特点。借助动态物化视图选择机制可以充分体现用户即时需求，这类算法 可以称为查询负载驱动算法。对于动态物化视图选择过程可用图1 4 表示： 图1 4 动态物化视图选择过程示意图 d y n a m a t 算法 d y n a m a t 6 3 算法由k o t i d i s 在1 9 9 9 年提出，它是动态视图选择算法当中最具代 表性的经典算法。它主要借鉴了内存管理的思想，o l a p 查询序列之间往往存在关 联性，如果将查询的中间结果保存，它很可能在下一次运算中被重复利用，这样 处理可以提高缓存中视图片段的命中概率。当即席查询较多时，这种算法的效率 很低，它常常需要访问原始数据来计算查询结果。 c 瑚k 算法 在文献 6 4 1 q b 提出一种基于c h u n k 块缓存的视图选择方法，它可以避免以查 询为粒度进行视图选择的缺陷，所有动态视图均以c h u n k 为单位进行缓存，每 个查询可以利用若干个c h u n k 来进行回答，这样可以很好的提高缓存空间利用 率。 c a c h e 算法 c a c h e 算法主要是通过预判查询可能需要的视图块并将其缓存来实现物化视 图动态选择，它需要分析用户的历史查询记录，得出用户未来可能进行的分析操 作。文献 6 6 q 鸭l , k ya s m ( a b s t r a c ts t a t em a c h i n e ) 来对查询进行建模，寻找查询 第6 页 国防科学技术大学研究生院硕士学位论文 之间的状念转移模式，从而预测未来可能的查询分析；文献【6 7 】通过查询序列前后 的关系来优化整个序列的查询时间，通过视图集状态转移构建有向无环图，最终 将问题转化为在有向无环图上求解最短路径；文献【6 8 分析用户查询模式，找出用 户查询中的m q t ( m a t e r i a l i z e dq u e r yt a b l e ) 并将其缓存，以便以后查询可以重复利 用。 谓词算法 基于谓词的动态视图管理算法【6 9 1 由c h o i 等人在2 0 0 3 年提出，它充分利用关 系数据库的特点，并且摒弃了针对多维数据碎片的约束。与c h u n k 算法和 d y n a m a t 算法不同，该算法根据用户谓词对视图表进行动态分区，对于实视图动 态管理问题，在文献 6 9 】中重点研究了以下几个问题：( 1 ) 为分区进行谓词选择；( 2 ) 重新分区；( 3 ) 视图替换策略。谓词算法是可以方便的在关系型d b m s 上实现，因 为它是基于r o l a p 的。谓词算法与c h u n k 算法m j 不同，后者使用多维数组对 数据进行存储，而谓词算法则采用关系表来存储视图，基于关系表的空间消耗要 比多维数组小得多。 1 2 3 物化视图选择算法发展趋势 无论是静态视图选择还是动态视图选择算法，它们均存在一些不足。对于静 态物化视图选择而言，其运行效率太慢而且不具有动态自适应性，无法应用于较 大的数据仓库设计开发当中；对于动态视图选择而言，往往需要耗费昂贵的缓存 空间，当缓存的视图片段无法命中时，其性能也会明显下降，这会导致查询时间 出现较大抖动。因为以上问题的存在，设计更加完善的物化视图选择算法依然十 分有研究价值，对于新型的物化视图选择算法而言，它需要实现以下4 个需求： ( 1 ) 提高易用性。在算法执行时尽可以的减少用户输入，例如视图的受访概率 或查询访问规则集。现有的多数改进算法均假设视图访问频率事先已知，通过视 图访问分布来化简视图空间，提高算法的执行效率，然而在数据仓库设计时视图 的访问频率很难预知，这个假设往往无法成立。 ( 2 ) 提高运行效率。算法应该可以快速处理大规模数据立方体的物化视图选择 问题，这就需要设计合理的视图筛选算法，及早删除不可能产生收益的视图，这 样可以有效简化搜索空间，提高运行效率。 ( 3 ) 提高视图性能。算法应该考虑视图的综合性能，包括其查询性能以及更新 性能，在选择物化视图时要一并考虑，不能只考虑其中一种性能的优化。 ( 4 ) 提高视图自适应性。算法应该可以自适应的调整所选视图集，使它可以反 映当前用户查询的规律，这样才可以很好的解决空间性能饱和问题。 正是基于这些需求，在最近关于物化视图选择问题的研究中开始聚焦于将静 第7 页 国防科学技术大学研究生院硕士学位论文 态与动态物化视图选择相结合的方法，将静态物化视图选择的结果进行动态优化， 使得所选物化视图具备了静态和动态物化视图的双重特性，从而取得更好的物化 效果。目前对于此类物化视图选择算法的研究已取得了一些成果，但还存在很多 不足之处，本文正是从静态与动态相结合的视图选择算法切入进行研究。 1 3 研究内容与思路 首先，认真分析现有的物化视图选择算法并将其进行对比，掌握不同算法的 优劣，然后根据现有方法的不足提出一种静态视图选择算法，通过实验验证本文 的算法优于现有的静态视图选择算法；其次，对静态视图选择的结果进行动态优 化，使得视图可以随时间实时调整，以适应查询分布的变化；最后通过实际案例 对本文提出的视图选择算法进行应用。 文中的研究主要从以下几个方面展开： ( 1 ) 在查询分布未知的情形下对静态物化视图选择算法进行研究，因为在数据 仓库设计阶段查询的分布很难预知，这样候选视图就无法依赖查询分布来确定。 本文采用的方法是利用数据立方体的稀疏性对原始视图格进行压缩，压缩之后可 以很好的化简原始视图格，使得物化视图选择过程的运行效率大幅提高。 ( 2 ) 在静态视图选择过程中同时考虑对查询代价和维护代价的共同优化，本文 采取的策略是分阶段选择，首先在第一阶段按视图的查询收益对视图进行选择， 保证物化视图集的查询收益最优，在选择过程中设置最小视图门限，当选择的视 图大小落于最小视图门限以内时，可以将其子孙视图排除选择过程，采用按需计 算的策略；其次在第二阶段按视图的维护收益对视图进行选择，此阶段所选视图 可以对前一阶段选择的查询视图进行快速更新，这样可以降低物化视图集的维护 代价。通过两阶段视图选择的方式，可以实现视图集查询与维护的共同优化，通 过实验表明该方法优于传统的静态物化视图选择算法。 ( 3 ) 在静态视图的基础上进行了动态优化算法研究。首先提出视图访问概率统 计模型，通过它可以对物化视图的受访概率进行实时统计，获取物化视图集合一 段时期内的访问分布；其次根据物化视图受访分布完成物化视图动态优化，本文 使用了动态物化视图索引技术，被索引的物化视图往往具备较高的动态收益，在 整个动态优化过程中，当未索引的物化视图动态收益高于索引物化视图时，索引 就会发生置换，即改变索引指向的物化视图。通过这种方式不需要额外的缓存空 间，是一种代价较小的静态物化视图动态优化算法，实验表明此算法可以避免静 态物化视图中出现的空间性能饱和现象。 ( 4 ) 结合超市数据仓库的开发案例，将本文提出的视图选择算法应用于其中， 并且针对应用设计了o l a p 分析展现原型，通过它可以直观的对o l a p 查询结果 第8 页 国防科学技术大学研究生院硕十学位论文 进行展现。 整体的研究思路如图1 5 ： 问题提出 背景分析 h 研究现状 h 研究思路 静态视图选择算法( t 1 0 m v s ) i 候选视图选择算法h 查询年； 萎孑图选h 实验分析 图1 5 论文研究思路 1 4 论文的组织结构 本文主要对数据仓库环境下的物化视图选择问题进行了研究，针对现有方法 中存在的不足，提出了一种静态物化视图选择算法和物化视图动态优化算法。 论文的组织结构如下： 第一章绪论。分析物化视图选择问题提出的应用背景，通过该问题的研究 发展，指明研究该问题的必要性以及研究该问题的可行思路。 第二章物化视图选择研究概述。首先详细阐述了物化视图选择问题以及与 之相关的研究模型；然后对现有的经典物化视图选择算法进行详细论述并且进行 了对比分析，指出了这些算法中仍存有的不足之处，为后文对算法的改进奠定了 基础。 第三章改进b p u s 的物化视图选择算法。通过对经典物化视图选择算法 b p u s 的研究，提出了一种新的静态物化视图选择算法，它可以不用预先假设查询 第9 页 国防科学技术大学研究生院硕士学位论文 分布向生成候选视图，同时它将物化视图选择划分为两个阶段，即查询视图选择 和维护视图选择阶段，避免了局部优化的问题，最后通过实验验证了算法的优越 性。 第四章静态物化视图动态优化算法。首先针对动态条件下的物化视图访问 概率进行研究，提出了一种物化视图受访概率统计模型，可以实时计算每个物化 视图的受访概率；其次对物化视图的动态收益进行研究，提出了基于索引的物化 视图动态优化算法，最后通过实验证明该算法可以进一步增强了数据仓库的性能。 第五章实例分析。通过零售超市的数据仓库系统开发案例，将文中设计的 物化视图选择算法应用于数据仓库设计阶段，最后通过o l a p 的前台展现工具对 物化后的数据仓库进行了分析展现。 最后，总结了全文的工作和研究的内容，并对未来在该领域的研究进行了展 望。 第1 0 页 国防科学技术大学研究生院硕士学位论文 第二章物化视图选择问题相关研究 对于数据仓库而言，物化视图的建立主要是为了加快o l a p 查询响应的时间， 使用户享有“在线 分析的体验。物化视图的思想是通过对查询的预先计算并将 其结果进行保存，以避免查询每次都要访问大量的细节数据，提高物化视图的重 用率。 理想状态下，如果将所有可能的查询对应的视图都进行物化，那么数据仓库 可以具备最优的查询响应性能。但是在实践过程中，往往无法实现全物化策略， 原因有以下两点： ( 1 ) 存在约束。如果将可能的查询对应的视图全部物化，那么计算机的资源将 会溢出，这其中包含存储空间的溢出和维护时间的超时。数据仓库是大规模的数 据集合，若对其全物化，数据量必定超出计算机的容量和处理能力，使得数据仓 库的成本大增。 ( 2 ) 大量冗余。事实上，所有查询对应的视图之间存在大量重叠，若是将其全 部物化，必然引起大量冗余。对于查询而言，若其拥有相同的谓词前缀，那么它 们可以共同对应于一个视图，因而不必对所有的视图都进行物化。 通过上面的分析可知，在数据仓库环境下必须采取部分物化的策略，研究的 重点是如何选择物化视图和选择哪些物化视图，这就构成物化视图选择问题的核 心内容。下面将对物化视图选择问题进行详细描述。 2 1问题描述 物化视图选择问题首先由h a r i n a r a y a n 在1 9 9 6 年提出，经过近十年的研究， 已经涌现了大量富有成效的研究成果。物化视图选择是指在一定约束条件下选取 一个视图子集并进行物化存储的过程，它的目标是在查询响应时间与计算机资源 消耗之间进行折衷。这个问题已被证明属于n p c o m p l e t e 问题【8 ，6 5 1 ，目前所有的方 法只能求解近似最优解而无法精确求解。 关于此问题的形式化描述如下： 【定义2 1 】物化视图选择：存在一个数据仓库模式r ，一组约束条件丁，一 组查询集合q 以及代价函数c ，物化视图选择的就是在r 上选取一组视图乃使 得c 俾，形9 最小，同时y 满足所有的约束条件。 利用数学模型描述如下： lm i n c ( r ，v ，9 j is t c 0 n s t r a i n f u n c t i o n ( v ) 第l l 页 国防科学技术大学研究生院硕士学位论文 物化视图选择问题是数据仓库优化技术中一个相对简单而又有效的方法，它 通过选择多维数据集中一组特定的视图集进行物化，尽可能缩短发生在该多维数 据集上的所有查询的响应时间。对于视图的选择需要借助视图代价模型，通过此 模型可以估算视图被物化后带来的收益，这些在后文中将会详细介绍。通过上述 的数学模型可以发现，物化视图选择问题属于一类目标规划问题，但是由于此问 题的目标函数和约束条件都无法用简单函数表达，所以问题的求解十分复杂，在 多项式域内无法求出最优解，只能逼近最优解。 2 2 视图联系模型 视图联系模型是指视图的组织方式，为了解决视图选择问题，必须对视图之 间的联系进行建模，现在主流的视图联系模型有三种，分别是格模型，m v p p 模 型和a n d o rd a g 模型。 2 2 1 格模型 格模型( l a t t i c e ) 最早由文献【8 】提出，它直观地表达了视图之间的关联，由于 o l a p 聚合存在偏序关系，即相互之间存在依存，而视图表达的正是一些聚合运算 的结果，因而视图之间也存在依存关系。 【定义2 2 1 视图依赖：若视图巧对应的查询g ，与视图巧对应的查询卯存在 聚合关系，即g ，经过g r o