（计算机软件与理论专业论文）数据仓库中物化视图的选择.pdf

数据仓库中物化视图的选择摘要 摘要y 4 16 8 7 0 数据仓库是一个面向主题的、集成的、不可更新的且随时间不断变化的数 据集合，用来支持管理人员的决策。它维护着海量的数据，所支持的查询形式 复杂，通常需要访问大量数据，而一个决策支持系统必须对查询做出快速响应， 要解决这对矛盾，一个好的数据仓库物理设计方案是至关重要的。 本文主要研究数据仓库物理设计的一个方面：物化视图的选择问题，提出 了分别用于构建数据仓库时和数据仓库运行时的物化选择算法。 ，构建数据仓库时，利用物化收益的单调性，使大部分情况下选择一个视图 之前所需要查看的结点数下降至i o 个以内，从而将贪心法的算法复杂度从o ( k n 2 ) 降至o ( n 1 ”) ：考虑分片查询，降低了选择的粒度，允许只选择视图的一部分， 并将贪心法推广运用于这种情况；通过实验，提出了一个更符合实际数据仓库 系统特征的查询代价模型，它不仅与所查询的视图大小有关，还与查询结果集 大小、查询本身的复杂度等因素有关。) 可 然后，本文阐明了在数据仓库运行期间，需要一个维护物化视图选择方案、 对其作进一步优化的长期算法，并提出了这个算法的特征要求。r 本文采用遗传 算法的思想来实现这个算法，根据物化视图选择问题的特征进行调整，取得了 较好的效果。随后，在分析算法选项对进化过程影响的基础上，提出了自适应 遗传算法，使算法能无需用户干预而长期运行。 本文最后对下一步研究方向作了展望，提出了若干努力方向。厂 关键字：数据仓库，物化视图，贪心算法，分片查询遗传算法 中图分类号：t p 3 1 1 1 3 蕾 馥 f t 雇 e 皇 为 t 目 j自_器件 竺塑竺! ! ! ! 竺些塑苎竺兰堡 ! ! ! ! ：! ：! 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 ，as u b j e c t o r i e n t e d ，i n t e g r a t e d ，t i m e v a r i a n t c o l l e c t i o no fd a t at oe n a b l ed e c i s i o nm a k i n ga c r o s s ad i s p a r a t e g r o u po fu s e r s d e c i s i o ns u p p o r t i n ga p p l i c a t i o n si n v o l v ec o m p l e xq u e r i e so nd a t aw a r e h o u s e s ，w h i c h c o n t a i n sl a r g ea m o u n t so fd a t a s i n c er e s p o n s et i m e ss h o u l db es m a l l ，ag o o dp h y s i c a l d e s i g no f t h ed a t aw a r e h o u s ei sc r i t i c a l t h i s t h e s i s w o r k s o n a n i m p o r t a n t a s p e c t o f p h y s i c a l d e s i g n i n g o f d a t a w a r e h o u s e t h es e l e c t i o no fm a t e r i a l i z e dv i e w s a l g o r i t h m st ob eu s e dw h i l eb u i l d i n gt h ed a t a w a r e h o u s ea n dw h i l et h ed a t aw a r e h o u s ei sr u n n i n ga r ed i s c u s s e ds e p a r a t e l y , w h e n b u i l d i n gt h ed a t aw a r e h o u s e ，ag r e e d ya l g o r i t h mw h i c h t a k e sa d v a n t a g eo f t h e m o n o p h o n y p r o p e r t y o f t h e b e n e f i t i s p r e s e n t e d s o t h a t u s u a l l y t h e c o u n t o f n o d e s n e e dc o n s i d e ra r e rs e l e c t i n ge a c hv i e wi sd e c r e a s e dt ol o w e rt h a n1 0 ，w h i c hd e c r e a s e s t h e a l g o r i t h mc o m p l e x i t y f r o mo ( k n 2 ) t o o ( n 1 5 8 ) t h e n ，a na l g o r i t h m ，w h i c h d e c r e a s e st h eg r a n u l a r i t yb yt a k i n gi n t oa c c o u n to f t h es l i c eq u e r y , i sp r e s e n t e d s p a c e c a nb eu s e dm o r ee f f i c i e n t l y , s i n c ew ea l l o wp a r t so fv i e w st ob es e l e c t e d f i n a l l y ， b a s e do nr e a lp l a t f o r mt e s t s ，am o r er e a l i s t i cq u e r yc o s tm o d e li sp m s e n t e d ，w h i c h d e p e n d s n o t o n l yo n t h es i z eo ft h er a wd a t a b u ta l s oo nt h es i z eo ft h er e s u l ts e ta n d t h ec o m p l e x i t yo ft h eq u e r yi t s e l f t h i sm a k e st h es o l u t i o n so fo u ra l g o r i t h m sm o r e a c c u r a t e t h e n ，t h en e c e s s i t yo fh a v i n gal o n g - t o ma l g o r i t h mt om a i n t a i no ri m p r o v et h e s e l e c t i o nd u r i n gt h er u n t i m eo ft h ew a r e h o u s ei sc l a r i f i e d b a s e do nt h ed i s c u s s i o no n t h ec h a r a c t e r i s t i co ft h el o n g t e r ma l g o r i t h m ，t h eg e n e t i ca l g o r i t h mi sc h o s e na st h e p r o t o t y p e a f t e rc a r e f u l l yt u n i n gt h ea l g o r i t h ma c c o r d i n gt ot h ef e a t u r eo f t h ep r o b l e m i t s e l f g o o dr e s u l t sa r eo b t a i n e d a f t e ra n a l y z i n gt h ei m p a c to fa l g o r i t h mp a r a m e t e r s a n do p t i o n so nt h ew h o l ee v o l u t i o n p r o c e s s ，as o l , a d a p tg e n e t i ca l g o r i t h m i s p r e s e n t e d s ot h a tm a n u a li n t e r f e r e n c ec a nb ea v o i d e d a tt h ee n do ft h i s t h e s i s ，f u t u r ew o r k i n gd i r e c t i o n so nt h i sr e s e a r c ht o p i ca r e m e n t i o n e d k e y w 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 , g r e e d ya l g o r i t h m ，s l i c eq u e r y , a n d g e n e t i c a l g o r i t h m 数据仓j 宰中物化视图的选择 0 l 言 第一章引言 1 1 数据仓库研究背景 数据库系统作为数据管理手段，从它诞生开始，就主要用于事务处理。经过 数十年的发展，在这些数据库中已经保存了大量的日常业务数据。传统的业务系 统一般直接建立在这种事务处理环境上，它以数据库为中心，从事事务处理、批 处理和部分相对简单的决策分析等数据处理工作。随着技术的进步，人们试图让 计算机担任更多的工作，希望计算机更多地参与数据分析与决策制定领域，实现 商业智能；而数据库技术也一直力图使自己能胜任从事务处理、批处理到复杂的 决策分析处理等各种类型的信息处理任务。然而人们逐渐认识到，事务处理和分 析处理具有不同的特征，事务处理系统无法解决分析处理系统必须解决的数据集 成、动态集成、历史数据和数据综合等问题，直接使用事务处理环境来支持决策 是行不通的。 要提高分析和决策的效率和有效性，分析型处理及其数据必须与操作型处理 及其数据相分离。必须把分析型数据从事务处理环境中提取出来，按照 d s s ( d e c i s i o ns u p p o r ts y s t e m ，决策支持系统) 处理的需要进行重新组织，建立单 独的分析处理环境。数据仓库正是为了构建这种新的分析处理环境而出现的一 种数据存储和组织技术。 数据仓库是用于帮助知识工作者( 包括企业执行经理、部门经理、分析师等) 更好、更快地做出正确决策的一整套决策支持技术的总称。 与传统的操作型系统不同，数据仓库中，概要的、总体的数据比细节的、单 条的记录更重要，其数据可能来源于多个操作型数据库，包含大量的( g 级甚至t 级) 历史数据，支持即席的、复杂的查询，这些查询通常需要访问大量记录，进 行复杂的连接、聚合运算，因此，在数据仓库中，查询吞吐量和查询响应时间比 事务吞吐量显得更重要。 数据仓库技术的提出引起了学术界和工业界的广泛关注，s t a n f b r d 大学、 w i s c o n s i n 大学、i b ma l m a d e n 研究中心等研究机构纷纷立项从事数据仓库技术 的研究，研究的方向覆盖了数据仓库的方方面面，如数据仓库的设计、数据清洗、 查询优化、元数据管理等。许多著名的数据库厂商，如i b m 、h p 、o r a c l e 等纷 纷推出了自己的数据仓库产品、解决方案，一些小企业也在该领域找到商机，推 出了一些有用的数据仓库工具，这些产品为大型零售业、制造业等食业所采用， 已有升i 少成功案例，财富5 0 0 强中已经有8 5 的企业建成或正在建立数据仓库， 数据仓库与i n t e r n e t 一样，正在成为最快的i t 增长点。1 9 9 6 年，全球企业在数 数据仓库中物化视图的选择三二 据仓库上的投资达到1 6 8 亿美元，并且每年以1 9 1 的速度增长。据i d c 调查， 数据仓库的平均投资回报率为4 0 1 。而在国内，诸如金融、证券、电信等计算 机应用较早、较成熟的行业也已经意识到采用数据仓库技术能够对数据进行更好 的加工处理，发现其内在的规律性，帮助决策者指导企业决策和发掘企业的竞争 优势，它们也纷纷建立了自己的数据仓库系统。 1 2 本文研究成果 本文主要研究数据仓库物理设计的一个方面：物化视图选择问题，特别是数 据方块的物化视图选择问题，主要研究成果如下： 利用物化收益具有单调性这个性质，使大部分情况下选择一个视图之前所 需要查看的结点数下降至1 0 个以内，从而将贪心法的复杂度从o ( k 。n 2 ) 降 至o ( n 1 5 8 ) ； 考虑分片查询的情况，降低物化选择的粒度，允许只选择视图的一部分， 并将贪心法推广运用于这种情况； 通过实验，提出了一个更符合实际数据仓库系统特征的查询代价模型，它 不仅与所查询的视图大小有关，还与查询结果集的大小、查询本身的复杂 度都有关。 阐明了在数据仓库运行期间，我们需要一个维护物化视阻选择方案，对选 择方案作进一步优化的长期算法，并提出了这个算法的特征要求； 将遗传算法的思想应用于物化视图选择问题，提出了符合该问题的遗传算 法实现，作为物化视图选择问题的长期算法； 通过分析算法选项对物化视图选择方案进化过程的影响，提出了自适应遗 传算法，使算法能无需用户干预而长期运行。 1 3 本文组织 本文的主要研究方向是数据仓库物理设计中，针对数据方块的物化视图选择 问题。 本文首先在第二章介绍了数据仓库出现的背景、基本概念、主要特征，以及 关键技术和难点。 为了能够对物化视图选择问题进行深入探讨和分析，本文第三章3 1 节阐述 了该问题所涉及的关键概念以及问题本身的形式化描述，3 , 2 节介绍了现有的研 究成果：在此基础上，3 3 节从几个方面入手，对现有的算法进行了改进：利用 物化收益的单调性在不影响解的质量的前提下减低了算法复杂度；降低物化选择 的粒度，将贪心法推广至考虑分片查询的情况；采用更接近实际数据仓库系统的 查询代价模型，提高了物化视图选择方案的质量，总之，第三章的研究使在短时 数据仓库巾物化视图的选择 引言 问内找到一个好的物化视图选择方案成为可能。 第四章中，4 1 节指出为了寻求更好的物化视图选择方案，同时在数据仓库 运行的过程中对选择方案进行维护，我们需要一个能够长期运行，不断搜索的长 期算法：4 2 节中我们采用了遗传算法的思想，根据物化视图选择问题本身的特 征作了适当的调整，提出了基于遗传算法的物化选择长期算法：在总结长期算法 的参数、选项对遗传进化的影响之后，4 3 节提出了一个自适应遗传算法，使遗 传算法的运行基本无需人工干预。 本文最后对物化视图选择问题的下一步研究工作如何开展提出了一点自己 的看法。 数据仓库中物化视图的选择 数据仓库概述 第二章数据仓库概述 数据仓库概念的起源可追溯至8 0 年代初期，关系数据库管理系统作为商业 产品出现的时候。关系数据模型凭借其简单清晰性和s q l 语言提供的强大的查 询能力，被越来越多的用户采纳，同时应用于业务处理和决策支持。通常，数据 从各组织机构的在线数据库中抽取出来，存贮至新创建的数据库系统中去，以支 持用户各种即席查询和报表功能，建立新系统主要是出于在线数据处理系统 ( o l t p ，o n - l i n e t r a n s a c t i o n p r o c e s s i n g ) 性能方面的考虑。在这些早期的数据仓库 系统中，抽取操作数据通常通过对操作数据取“快照”或子集的方法进行，通常 每星期或每月进行一次。数据仓库的数据模型通常与操作数据库的模型是一致 的，至多不过是按照范式要求规范化某些为提高效率故意设计的非范式化的模 型，以及消除那些会导致理解困难的“代码表”。 随着数据仓库的发展及其规模的扩大，人们开始意识到，在决策支持环境中， 从数据的抽取、数据模型的建立，到对用户查询的支持，其特征都与传统的操作 型数据库有所不同，数据仓库技术顺应这个需求应运而生，引起了学术界和工业 界的广泛关注，从各个方面进行了研究，并推出了一系列产品。 从数据仓库出现早期到现在，数据仓库在数据处理过程中的角色和目的已经 发生了非常大的变化，而且如今还在不断地演变。数据仓库不再只是支持用户查 询和报表的数据库系统，也不再是操作数据库的“快照”了，它应当被看作是一 个全新的信息与知识的来源口1 ，为整个企业或组织、有特定需求的用户，以及数 据分析师们所使用。 2 1 数据仓库的定义及其特点 2 1 1 数据仓库定义 美国斯坦福大学数据仓库研究小组是这样定义数据仓库的：数据仓库是集成 信息的存贮中心，这些信息可用于查询或分析。 i b m 的数据仓库红皮书口j 中说，数据仓库是管理和生成用于决策的、完整的、 适时的、精确的、可理解的信息的设计与实施过程、工具以及其他设施。它包括 这个组织为了创建、管理和维护一个数据仓库或数据集市的所有活动。 w h i n m o n 是业界公认的数据仓库概念的创始人。在他撰写的( ( b u i l d i n g t h e d a t a w a r e h o u s e ) ) 1 4 】一书中，他给出了数据仓库的定义：“数据仓库是一个面向主 题的、集成的、不可更新的且随时间不断变化的数据集合，用来支持管理人员的 数据仓库中物化视图的选择 数据仓库概述 决策”。”由于i n m o n 本人在数据仓库发展中的作用，上述对数据仓库定义的描 述不断被技术文献所引用，成为对数据仓库比较权威的定义。 与其他数据库应用不同，数据仓库更像一种过程，对分布在企业内部各处的 业务数据的整合、加工和分析的过程，而不是仅仅一种可以购买的产品。 数据仓库是面向决策支持系统的分析型数据库，它存放了大量的只读数据， 为用户分析判断决策提供所需的信息。数据仓库把业务处理信息系统中的事务数 据加以归纳整理，并及时提供给相应的决策分析人员。 数据仓库的用户称为决策支持( d s s ) 分析员，他们的主要工作是指出和发现 在企业决策中所需要使用的信息。他们在发现模式下工作，直到看到报表或屏幕 上的数据时，他们才开始探讨有没有必要进行下一步d s s 分析，以及如何进行。 这个过程和传统的需求驱动的软件开发生命周期( s o f t w a r ed e v e l o pl i f ec y c l e ， s d l c ) 是完全不同的。数据仓库系统由数据开始，一旦数据到手就集成数据。然 后，如果数据有偏差，再检查看看数据存在什么偏差，在针对数据写程序，分析 程序执行结果，最后，系统需求才得到了理解，有人把这个与传统的系统开发生 命周期完全相反的过程称为c l d s ( 与s d l c 顺序相反) ，也就是说，数据仓库是 由数据驱动的。 2 1 2 数据仓库的特征 由i n m o n 的数据仓库定义出发，我们可以知道，数据仓库与传统的联机事务 处理领域的数据库技术相比，具有以下特征： ( 1 ) 数据仓库的数据是面向主题的 传统的信息系统中的数据组织方式是面向应用的，数据库模式与实际业务处 理流程中所设计的单据或文档有较好的对应关系，如物资仓库管理中的进仓单、 出仓单，在物资仓库管理信息系统的数据库模式中具有直接的对应部分。但这种 方式使数据围绕着业务处理过程，不便于对数据作高层抽象的分析。 数据仓库中数据以面向主题方式组织。主题是某一分析领域所涉及的分析对 象，例如商场销售分析系统中“商品”是一个主题分析对象，有关“商品” 分析需要的数据围绕着这一主题组织，包括商品的基本信息、采购信息、销售信 息、库存信息等。面向主题的数据组织方式就是在较高层次上对分析对象的数据 作一个完整、一致的描述，能有效地刻画出分析对象所涉及的各项数据及数据间 的联系。这种数据组织方式更能适合于较高层次的数据分析，便于发现数据中蕴 涵的模式和规律。 ( 2 ) 数据仓库的数据是集成的 数据仓库的数据是从原有的、分散的事务处理系统数据库中抽取得来。联机 事务处理系统中的操作型数据和决策支持系统中的分析型数据有着较大的差别。 数据仓库中物化视图的选择 数据仓库概述 数据仓库中每一主题对应的源数据在原有的各分散数据库中可能是重复出现的、 不一致的，数据仓库中的数据不能从原有数据库系统直接得到，事务处理系统中 的操作型数据在进入数据仓库之前，必须经过统一和综合，演变为分析型数据。 这是数据仓库建设中最复杂的一步，需要完成工作包括：统一源数据中所有矛盾 之处，如字段的同名异义、异名同义、单位不统一、长度不一致等；对源数据进 行综合和计算，生成面向主题分析用的高层、综合的数据，例如根据商品销售原 始数据，计算生成每天、每月的销售综合数据等。 ( 3 ) 数据仓库的数据是不可更新的 数据仓库中存放的是供分析决策用的历史数据，而不是联机处理的当前数 据，涉及的数据操作主要是数据查询，一般不进行数据的增、删、改操作，业务 系统中的数据经集成并进入数据仓库之后极少或根本不再更新。如果对数据仓库 中的数据进行了修改，就失去了统计分析正确性的基础数据的真实性。由于 数据仓库中的数据量往往很大，因此数据仓库系统要采用各种复杂的索引技术， 以提高数据查询的性能。 ( 4 ) 数据仓库的数据是随时间变化的。 数据仓库的数据不可更新是对数据仓库的应用而言，即数据仓库的用户在进 行分析处理时不进行数据更新操作，但这不是说数据仓库数据是永远不变的。数 据仓库数据是随时间变化的，数据仓库系统需要不断获取联机事务处t 垂( o l t p ) 系统不同时刻点的数据，经集成后追加到数据仓库中，因此数据仓库中数据的码 ( 键) 都包含时间项，以表明数据的历史时期，并可在时间维度上对数据进行分析； 另外，数据仓库中的数据也有时间期限，在新数据不断进入的同时，过期的数据 也要从数据仓库中排除出去。 2 2 数据仓库的体系结构 作为一个系统，数据仓库至少应包括3 个基本的功能部分：数据获取、数据 仓储和管理，以及信息访问。斯坦福大学的数据仓库计划( w h i p s ) 提出了个具 有普遍代表性的数据仓库体系结构，并围绕这个体系结构的各个环节，开展了深 入的研究工作，图2 - 1 说明了w h i p s 数据仓库的基本体系结构【6 】： 数据仓库中物化视图的选择 数据仓库概述 图2 1w h i p s 数据仓库的基本体系结构 底部是信息源，这不仅包括常见的数据库，也包括文本文件、h t m l 文件、 知识库、遗留( l e g a c y ) 系统等各种信息源。 连接每个信息源的是包装器监视器( w r a p p e r m o n i t o r ) ，包装器负责把信息从 原信息源的格式转换为数据仓库所采用的数据格式和数据模型，而监视器负责自 动监测信息源中数据的变化，并把这些变化上报给集成器( i n t e g r a t o r ) 。 当有新的数据源进入数据仓库，或信息源发生变化时，集成器对这些新数据 或变化了的数据进行过滤、总结，或与其他信息源的信息进行合并处理，再安置 到数据仓库中去。在某些时候，集成器可能需要从原数据源或其他数据源获取进 一步的信息，图中向下的虚线箭头表示了这种行为。 随着数据仓库技术的发展，数据仓库技术涉及的范围有所扩展，一个更为全 面、复杂的数据仓库体系结构如图2 2 所示”j ： 图2 - 2 更全面、复杂的数据仓库体系结构 这个数据仓库体系结构包括以下八个主要组成部分： 数据源：为数据仓库提供源数据，如各种业务处理信息系统的数据库、联机 事务处理系统( o l t p ) 的操作型数据，以及其他相关文本、文档等。 数据抽取、转换、装载和刷新工具：其功能是从数据源中抽取数据，进行检 验和整理，并根据数据仓库的设计要求对数据进行重新组织和加工，装载到数据 仓库的目标数据库中，周期性地刷新数据仓库中的数据。 数据建模工具：用于为数据仓库的源数据库和目标数据库建立信息模型，以 描述数据检验、整理、加工的需求和相应过程及步骤。 监控和管理工具：对数据仓库的运行提供监控和管理手段，包括系统资源的 使用情况、用户操作的合法性管理、安全管理、存储管理等。 数据仓库中物化视图的选择 数据仓库概述 元数据仓储：用于存储数据模型和元数据，其中元数据描述了数据仓库中源 数据和目标数据本身的信息，定义了从源数据到目标数据的转换过程。 数据仓库和数据集市的目标数据库：存储经检验、整理、加工和重新组织后 的数据，数据集市即部门级规模的数据仓库。 o l a p ( o n - l i n e a n a l y s i sp r o c e s s i n g ，联机分析处理) 服务器：提供功能强 大的数据操作引擎，支持多维数据结构操作，为前端工具提供多维数据视图及服 务。 前端数据访问和分析工具：不但提供一般的数据访问功能，如查询、汇总、 统计等，还要提供对数据的深入分析功能，如数据的比较、趋势分析、模式识别 等，即所谓的“数据挖掘”功能。 从以上所述的数据仓库的体系结构，可以看出数据仓库系统的一般应用过 程：从业务处理信息系统等外部数据源获取数据，经加工整理后进入数据仓库， 根据数据分析挖掘的需求特性对数据进行建模和组织，用户利用各种前端数据分 析和挖掘工具，或直接访问数据仓库，或通过o l a p 服务器，对数据仓库中的 数据作各种查询、分析、挖掘工作。 2 3 数据仓库的概念设计 2 3 1 多维数据模型 多维视图是目前流行着的，并为各种o l a p 的前端工具、数据库设计和查询 引擎所普遍采用的数据仓库概念模型。多维视图数据模型中，定义了一些作为分 析目标的数值型度量( m e a s u r e ) ，例如：销售额、预算、投资等，每一个这样的 数值度量的取值都取决于一组“维”( d i m e n s i o n ) ，这些维决定了度量的上下文， 例如，与销售额关联的维可能包括这笔销售发生的城市、日期以及所出售的产品。 通常我们认为所有这些维在一起唯一确定了度量的取值。由此，多维数据模型将 度量看成是这些维组成的多维空间内的一个值，每个维都各自拥有一些属性用于 描述这个维，例如，产品维可能包括如下4 个属性：种类、行业、生产日期和平 均利润率，如午后红茶属于软饮料类，食品行业，产于2 0 0 1 年3 月，平均利润 率为4 3 。这些维属性之间可能存在着层次关系，如上例中的种类和行业间就存 在层次关系。 o l a p 数据模型的另一个显著特征是它所支持的主要操作是那些按照一个或 多个维的取值、针对度量的聚合( a g g r e g a t e ) 操作，例如，计算每个分店( 或每年) 的总销售额。通常，时间是决策支持数据仓库中一个至关重要的维。 数据仓库前端工具支持的对数据仓库的典型操作包括： 旋转( p i v o t ) ：我们可以把多维模型看成是这样张表：每个维和度量分别对 数据仓库中物化视图的选择数据仓库概述 应一列，一个简单的旋转操作是：选择两个维并对度量进行聚合操作，聚合后的 度量值可以被填在一个二维表格中，位于“，y ) 位置的那个值是由所有那些第一 个维取值为x ，第二个维取值为y 的那些行计算而得的，而x 、y 的值则出现在 相应行、列的表头上。 上卷( r o l l u p ) 下钻r i l l d o w n ) ：在当前数据对象基础上再追加一个维作聚合 操作，或是在具有层次关系的属性中从底层属性切换到上层属性作聚合操作称为 上卷，随着上卷的进行，看到的数据细节越来越少；下钻操作刚好与之相反，在 当前数据对象基础上减少一个维，或是从具有层次关系的属性中从上层属性切换 到底层属性作聚合操作，以便获知当前数据在该维上是如何构成的，随着下钻的 进行，看到的数据细节逐渐增加。 分片或分块( s l i c e - a n d - d i c e ) ：进行聚合操作时，限定某一维( 或多维) 上的成员 的取值范围，这样的操作称为分片或是分块。常见的是按一维、二维和三维分片， 例如，在“城市、产品、时间”三维立方体中对城市维作分片，选定某一城市， 可得到该城市中各产品历年的销售情况。 世系回溯( l i n e a g et r a c i n g ) 阻】：给定一条概要数据记录，寻找生成这条概要记 录的所有相关的原始数据记录的操作称为世系回溯操作。例如，给定2 0 0 0 年利 润总额，世系回溯操作返回2 0 0 0 年1 月到1 2 月每月( 假设该数据仓库中粒度单 位为月1 的利润。 2 3 2 在r o l a p 上实现多维数据模型 目前数据仓库产品按其服务器进行查询处理的体系结构可以分成3 类： 1 专用的s q l 服务器：它提供在只读的环境下，针对星型模型和雪花模型 的高级查询语言和查询处理机制，r e d b r i c k 是这类产品的代表。 2 r o l a p 服务器：它在后端关系型服务器和前端工具之间放置了一个中间 服务器，用于扩展关系服务器使之能够有效地支持多维o l a p 查询。这 种做法的优势在于它充分利用了关系系统的可扩展性和事务特性，然而， o l a p 和s q l 内在的不匹配造成了r o l a p 固有的性能瓶颈。目前大多 数厂商提供的产品都采用了r o l a p 的方式。 3 m o l a p 服务器：通过多维存贮引擎直接支持数据的多维视图， e s s b a s e ( a r b o r ) 是这种类型服务器的典型产品，这种方式的优势在于能充 分发挥索引的作用，性能较高，但空间利用率不高，可扩展性差，因此 仅适用于规模不大的数据仓库。 上一节描述的多维模型能够直接在m o l a p 服务器上得以实现，然而，如果 采用的是专用s q l 服务器或是r o l a p 服务器，我们必须设法将多维数据模型 及其操作映射到关系模型和s q l 查询上来。 数据仓库中物化视图的选择 数据仓库概述 e r 关系图和范式理论在o l t p 环境下被广泛使用，然而，在数据仓库环境 中，由于查询和数据装载的效率变得异常重要，由e r 关系导出的数据库设计 并不适合于决策支持系统。 多数数据仓库采用星型模型( s t a rs c h e m a ) 来表示多维数据模型。相应数据库 包含一张事实表和多张维表，每个维对应于一张维表。事实表中的每个元组包含 一个度量值和一组指针，有多少维就有多少个指针。这些指针分别指向相应维表 中取值对应于该元组“坐标”的那条记录，这种指针在关系模型中通常使用外键 f f o r e i g nk e y ) 来实现；维表由描述这个维的各个属性组成。图2 - 3 给出了星型模 型的一个例子： 星型模型并不显式地支持属性间的层次关系，而雪花模霉 ( s n o w f l a k e s c h e m a s ) 在星型模型的基础上作了改进，通过对维表进行范式化，使维的层次关 系得以显式的支持。图2 - 4 给出了雪花模型的一个例子： 图2 - 4 雪花模型 数据仓库中物化视图的选择 数据仓库概述 雪花模型对维表进行范式化，使得维表的维护工作更容易；然而，星型模型 中维表的非范式化结构使浏览这些维变得更容易。 除了事实表和维表之外，数据仓库中可能还存在着一些概要表，用来存放一 些预先计算好的聚合结果，通常包括事实表在一个或多个维上的聚合运算结果。 这些概要数据可以由两种方式来存储，比如说按年、产品统计销量( 参见图2 2 ) ， 产品这一维的属性可以与事实表共用原有的产品维表，而“年”这一维，一种做 法是另外构造一个维表，它是时间维的子集，只包含与年有关的属性；另一种做 法是重用时间维，但在此维表中增加一列：层次( 1 e v e l ) ，表示年、月、臼等属性 中哪些是有效的，比如说，( 0 ，2 3 ，4 ，1 9 9 9 ) 表示1 9 9 9 年4 月2 3 日，( 1 ，n u l l ， 4 ，1 9 9 9 ) 表示1 9 9 9 年4 月，而( 2 ，n u l l ，n u l l ，1 9 9 9 ) 表示1 9 9 9 年，这样， 引用最后一条时间维记录就意味着这是按年统计的销售数据。引入层次列避免了 数据仓库中的表的数量激增，但在处理时应小心以免出错。 2 4 数据仓库的物理设计 数据仓库通常包含着g 级甚至t 级的海量数据，为了能够快速地对查询做出 响应，必须采用高效的访问方式和查询处理技术，可以从多个方面入手提高查询 效率：首先是采用数据冗余的办法，如为合适的表建立索引，物化一些常用的视 图。故决定在哪里建立索g l t 9 】【l o 】，物化哪些视图i l l 】【1 2 】【1 3 】 1 4 】【1 5 】就成了数据仓库物 理设计所需要解决的重要问题：与之相关的是如何充分利用这些索引和物化视图 来回答用户查询，这涉及如何优化复杂查询、如何高效地扫描索引等l l 叫7 1 。除 此之外，利用数据分块、动态缓冲【1 8 】等技术也能在一定程度上提高数据仓库服 务器的性能。 2 4 1 索引的结构及用途 不少查询处理技术尽可能地充分利用索引，如多条件的选择操作可以利用索 引相交( i n d e xi n t e r s e c t i o n ) 实现，有时候充分利用索引所隐含的信息可以避免扫描 基本表，大大提高查询效率。 数据仓库引入了一种新的索引：位图索引( b i t m a p i n d e x ) ，它使索引间的交、 并等操作变得更高效。在索引结构中，考虑一个对应取值为d 的叶结点页面，在 传统的索引结构中，这个叶结点页是相应列取值为d 的记录号的列表，而位图索 引采用了另一种表示方法：它是一个位矢量，每一位对应一条记录，若记录相应 列取值为d ，这一位取值为1 ，否则为0 。位图索引本身的结构与传统索引结构 是一样的，所不同的是它的表示方式，这种表示方式能够加快交、并、连接、聚 合操作的速度。这种索引方式不仅对于那些基数小的列( 比如说性别) 有效，通过 合适的编码、压缩处理，对高基数的列同样起作用。目前多数数据仓库产品都支 数据仓库中物化视图的选择 数据仓库概述 持位图索引，然而一个值得研究的问题是：在哪些属性上作索引会带来最大好处 呢? 这是一个在作数据仓库的物理设计时不可避免的问题。 除了在一个表上的索引外，星型模式使连接索引( j o i ni n d e x ) 在决策支持中显 得格外有用。连接索引维护着外键和与之相对应的主键之间的关系，在星型模式 中，这意味着维表的一个或多个属性与对应事实表记录之间的关系。利用多维连 接索引能够避免几个独立的索引作相交操作，进一步减少计算量。连接索引也可 以采用位图方式表示。 最后，决策支持数据库通常包含大量的描述性的文本，故用于全文搜索的索 引在数据仓库中也起着非常重要的作用。 2 4 2 物化视图及其用途 数据仓库中许多查询都要求得到概要数据，必须使用聚合运算，因此，除了 索引以外，如果将一些常用的概要数据作为物化视图预先计算并存贮，并将大大 提高典型查询的响应速度。例如，一个商业决策系统中，可能大部分查询都与最 近一季度以来各类商品销售情况有关，若将按相应维计算得的概要数据预先计算 好，肯定能大大提高查询处理速度。 物化视图带来的问题在于：( a ) 决定物化哪些视图；( b ) 怎样充分利用物化视 图来回答查询；( c ) 在数据仓库装载和刷新时高效地更新物化视图【1 9 】。在星型模 式下，常见的、比较简单的物化视图通常是事实表与一个或多个维表的连接，并 按照这些维对给定的度量作聚合操作所得的结果集。如果采用雪花模式，物化视 图的形式会更复杂些。 物化视图的选择范围是很大的，要做出一个好的物化选择方案，必须综合考 虑数据仓库负载特征、增量更新代价、空间上限、查询代价等因素。本文后两章 将对物化视图的选择问题作详细叙述，故此处暂不展开。 一个简单而又有效地利用物化视图的策略是：通过对合适的物化视图作选择 操作，或是追加、变换属性作上卷操作，来获得需要的概要数据。例如，假设有 一张存放着每季度每种商品销量的物化视图，要获得每年可口可乐的销售情况， 可以先按照产品必须是可口可乐作选择，然后从“季度”切换为“年”作上卷操 作，从而获得要求的概要数据。 2 5 数据仓库的其他关键技术 数据仓库的工作过程分为：数据的抽取、存储和管理、数据的表现以及数据 仓库设计四个方面。除了前一节中已经介绍的数据仓库设计以外，其余三个环节 也都包含不少关键技术。 1 数据清洗 数据仓库中物化视图的选择 数据仓库概述 数据仓库是用于决策支持的，所以其中的数据应当是正确的，然而，从多个 数据源抽取的大量数据中，难免会有差错或是异常，因此，用来检测数据异常并 加以纠正的工具是非常有用的。数据清洗需要解决的问题包括：域长度不一致、 描述不一致、取值不一致、丢失必要的项，以及违反完整性约束等，在很多情况 下，应用程序表单中可选的数据项是导致数据不一致的重要原因。数据清洗工具 可以大致分为3 类：( 1 ) 数据迁移工具：它允许指定简单的规则，如：将所有 “住址”替换成“地址”；( 2 1 数据擦洗工具：它能够利用领域知识，采用词法分 析、模糊匹配等技术，对来自不同数据源的数据进行清洗，如同样的地址由于采 用了缩写或是不同的词序，可能有不同的写法，这类工具能设法识别哪些地址实 际上是相同的；( 3 ) 数据审计工具：通过扫描数据，发现其中蕴含的规则或是关 系，这类工具可以看作是数据采掘的一种变体，它可以用于发现一些可疑的现象： 如某个汽车销售商没有收到过任何投诉。 2 数据装载 抽取数据，进行数据清洗和必要的形式转换后，这些数据必须装载到数据仓 库中去。数据装载需要进行一些预处理：检查数据完整性、排序、生成数据仓库 中的导出表、建立索引等。数据装载工具应当能够让系统管理员监控整个过程， 允许取消、暂停或是继续执行数据的装载过程。由于数据仓库数据量巨大，顺序 执行的数据装载可能需要运行几个星期甚至几个月之久，所以，通常必须采用流 水线技术和分块并行处理技术，尽可能缩短所需的时间。一次完整的数据装载可 以看作是建立一个新的数据库，而此时当前数据库仍可以用来支持查询，一旦装 载完成，它取代当前数据库来支持查询请求。 尽管采取了并行化等措施，完整地装载数据需要的时间还是太长，很多商业 化的产品在刷新数据仓库时采用了增量装载的方法，这使装载过程的管理变得更 难：装载过程必须分成很多个定时提交( 如每秒提交一次，或每1 0 0 0 条记录提 交一次) 的小事务，以免与用户正在执行的查询相冲突，但这些事务必须以一定 的顺序执行，以保证基本数据、导出数据和索引之间的一致性。 3 刷新数据仓库 刷新数据仓库将数据源处的数据变化传播至数据仓库中的基本数据及导出 数据，有两个问题需要考虑：什么时候刷新以及怎样刷新。通常数据仓库定期刷 新( 每星期或每月一次) ，但若某些o l a p 查询需要访问最新的数据，则每次原 始数据发生更新时都必须进行刷新。刷新策略由系统管理员根据用户需要、数据 流量、数据源能力等因素确定，刷新周期必须选择得合适，使刷新数据量不超过 增量更新的能力。 不同的数据源不得不采用不同的刷新技术：抽取整个数据文件或数据库开销 很大，但对某些早期的数据源来说这是唯一的选择；大部分当代的数据库产品提 数据仓库中物化视图的选择 数据仓库概述 供了增量式的数据复制服务，可为数据仓库的增量刷新过程所利用。数据复制技 术可以分成两种基本类型：数据传送( d a t as h i p p i n g ) 和事务传送( t r a n s a c t i o n s h i p p i n g ) 。数据运送方式中，数据仓库中的表被看作是数据源中表的一个快照， 数据源的变化通过a f t e rr o w 触发器被记录在日志表中，据此建立刷新计划将更 新传播至远端快照；而事务运送方式中，利用的是数据库本身的事务日志，通过 监听日志检测到副本表的更新，将相应的日志记录传输至复制服务器，复制服务 器将对应事务打包，用于更新数据仓库中的副本表。事务运送方式无需使用触发 器和日志表，能减轻操作数据源的工作负担，但由于没有访问事务日志的标准 a p i ，在多种d b m s 共存的环境下很难发挥作用。 除了刷新基本数据，导出数据、索引等也必须相应地加以更新，建立逻辑正 确的、高效的导出数据增量刷新过程也是一个重要的研究方向。 4 元数据和仓库管理 数据仓库反映企业的业务模型，故元数据管理是数据仓库体系结构中一个必 不可少的元素，它管理着不同种类的元数据：管理元数据包含建立、使用数据仓 库的必要信息，如源数据库的描述、前后端工具、数据仓库模式、导出数据、维、 维层次关系的定义、数据的物理组织、数据刷新策略等；业务元数据包括业务术 语和定义、数据所有者等信息；而操作元数据包括数据仓库的运作情况，如当前 数据状态、使用统计数据、错误报告和审计信息等。通常，数据仓库采用一个元 数据仓储来存贮和管理和数据仓库有关的所有元数据，它使不同的工具以及设 计、建立、使用、管理数据仓库的整个过程共享这些元数据。 创建和维护一个数据仓库系统不是一个简单的任务，许多不同的工具、技术 可以帮助完成这个任务的不同方面：开发工具可以用来设计和编辑模式、视图、 脚本、查询和报表；计划和分析工具可以帮助理解模式、刷新率的变化会导致的 对数据仓库的影响，辅助完成数据仓库的容量规划；数据仓库管理工具用来监测 数据仓库，收集诸如概要表的使用情况、查询响应时间和频率、负载峰值和平均 值等统计数据，并向管理员提出建议：系统和网络管理工具用来测定服务器和客 户端之间、数据仓库服务器和数据源之间的数据流量；近年来，工作流管理工具 也被采用，用于管理数据抽取、清洗、转换、装载和更新这整个过程。 5 对s q l 语言的扩展 为更好地表达和处理o l a p 查询，一些s q l 语言的扩展被提出，并在某些 扩展的s q l 服务器上实现。这些s q l 语言扩展包括： 扩展的聚合函数：诸如排名，百分比，期望值、中位数等。 针对报表特点的扩展，业务分析报表常常需要就