（计算机软件与理论专业论文）实化视图匹配算法的研究与实现.pdf

华中科技大学硕士学位论文 = = = ；= = ；= j 自；= = ；g = = ；= ； = = ；= ；= # 目；= = ；= j = l 摘要 决策支持查询通常要汇总大量的、较低层数据，并且包含较复杂的计算过程。对利 用实化视图快速响应查询的问题的研究将有利于提高决策支持查询的响应速度。 利用实化视图快速响应查询首先要解决视图替代问题。实化视图匹配算法的主要思 想是将一个s p j g 查询或者视图分为s p j 部分和聚集部分两个部分。首先作视图和查询 的s p j 部分的匹配，其方法是判断视图是否可以替代查询的某个子表达式，如果可以就 构造替代表达式。然后再扩展到聚集视图以及带多余表的情况。 在拥有大量实化视图的实际系统中，如果采用顺序搜索的策略来寻找匹配的视图， l 效率会很低。利用过滤树和格索引，能有效地缩小可能响应查询的候选视图的范围。过 滤树是一个多路搜索树，每一层次对应着视图的不同的条件，叶子结点对应着满足从树 根到叶结点的路径上的各种条件的所有视图。过滤树递归地将视图集合划分成越来越小 的分区。对过滤树搜索时，是否继续沿着某结点的指针继续前进，这是由搜索条件决 定的。为了对过滤树的线性搜索，把结点组成一个格结构，以便快速地找到下一个搜索 路径上的结点。过滤树的同一层次上各结点关键字之间的子集和超集关系可以用偏序表 i 示，它们一起形成了搭结构，每个层次都可以包含一个格结构。尹一 视图匹配算法还必须集成到整个的优化处理过程中，生成所有的重写查询，估算代 价找出最优或者较优的重写查询。提出了一个简单的代价模型，并结合该模型提出了能 更快找出较优重写查询的启发式算法，这个算法的时间复杂度是查询涉及关系数的平 方。 关键词： 联机分析处理；查询优化：实化况图；况图匹配：延垂西；基辜萄、) ，夕 l 华中科技大学项士学位论文 a b s t r a c t d e c i s i o ns u p p o r t i n gq u e r i e sa l w a y sg a t h e ram a s so fd a t a ，a n di n c l u d es o m ec o m p l e x c o m p u t i n go p e r a t i o n s i t sh e l p f u l t om a k er e s e a r c h e so n a n s w e r i n gq u e r i e su s i n g m a t e r i a l i z e dv i e w sf o ri n c r e a s i n gt h ee f f i c i e n c yo fd e c i s i o ns u p p o r t i n g q u e r i e s t oa n s w e r q u e r i e su s i n gm a t e r i a l i z e dv i e w s w em u s t f i n das o l u u o nt ov i e ws u b s t i t u t e s t h em a i ni d e ao fa l la l g o r i t h mo fm a t e r i a l i z e dv i e wm a t c h i n gi st os e p a r a t eas p j gv i e wo r q u e r y i n t oas p jp a r ta n da l l a g g r e g a t i o np a r t f i r s t l y , m a t c ht h e i rs p jp a r t s i td e c i d e s w h e t h e rt h es p jq u e r yc a nb ec o m p u t a b l ef r o mt h es p jv i e w i fi ti s t r u e ，c o m p u t et h e s u b s t i t u t ee x p r e s s i o n t h ea l g o r i t h mc a nb ce x t e n d e dt oa g g r e g a t i o nv i e w sa n dt h ev i e w sw i t h e x t r at a b l e s i na s y s t e mo f l o t so fm a t e r i a l i z e dv i e w s ，i f ss l o wt os c a nt h ew h o l ev i e ws e t so r d e r l yt o f i n dm a t c h e dv i e w s t h ef i l e rt r e ea n dt h el a t t i c ei n d e xa r ep r e s e n t e dt on a r r o wt h es e a r c h s p a c e o fp o t e n t i a lu s e f u lv i e w s t h ef i l t e rt r e ei sam u l t i w a ys e a r c ht r e e e v e r yl e v e li s c o m p o s e do fd i f f e r e n ts u b s t i t u t e c o n d i t i o n s al e a fc o r r e s p o n d st oav i e wt h a ts a t i s f ya l l c o n d i t i o n so nt h ep a t h w a yf r o mt h er o o tt oi t s e l f af i l t e rt r e er e c u r s i v e l ys u b d i v i d e sv i e ws e t s i n t os m a l l e ra n ds m a l l e rp a r t i t i o n s w h e t h e rt oc o n t i n u ea l o n gap o i n t e rw h i l es e a r c h i n gi na f i l t e rt r e ei sd e t e r m i n e db y a p p l y i n ga s e a r c hc o n d i t i o no nt h ek e ya s s o c i a t e dw i t lt h ep o i n t e r t oa v o i dt h el i n e a rs c a no nt h et r e e ，w eo r g a n i z et h ep o i n t si nal a t t e rs t r u c t u r et of i n dn e x t p o i n tq u i c k l yt h es u b s e tr e l a t i o n s h i pb e t w e e n t h ek e y so ft h ep o i n t si nt h es a m el e v e lo ft h e t r e ei m p o s e sap a r t i a lo r d e re v e r yl e v e lh a sas i n g l el a n i c ei n d e x w em u s ti n t e g r a t et h ev i e wm a t c h i n ga l g o r i t h mi n t oq u e r yo p t i m i z a t i o n as i m p l ec o s t m o d e li s p r e s e n t e da n dah e u r i s t i ca l g o r i t h mu s i n g t h a tm o d e li s p r o p o s e dt o c h o o s ea b e t t e r r e w f i t t e nq u e r y t h et i m ec o m p l e x i t yo ft h eh e u r i s t i ca l g o r i t h mi st h es q u a r eo ft h e n u m b e ro f r e l a t i o d sr e f e r e n c e db yt h eq u e r y k e yw o r d s ：o n l i n ea n a l y t i c a lp r o c e s s i n g ；q u e r yo p t i m i z a t i o n ；m a t e r i a l i z e d v i e w s ；v i e w m a t c h i n g ；f i l t e rt r e e ；l a t t i c ei n d e x 华中科技大学硕士学位论文 1 绪论 1 1 研究背景、目的和意义 随着我国社会信息化进程的飞速发展，成千上万的大型数据库已经被广泛地应用 在企业、政府和科研等等部门。如何充分利用这些日益积累起来的大量数据资源，发 现隐藏在其中的有用知识，更好地把握未来发展趋势，就成为迫切的需要。解决的办 法就是建立决策支持系统( d e c i s i o ns u p p o r t i n gs y s t e m ，d s s ) ，以及面向分析的数据仓 库( d a t aw a r e h o u s e ，d w ) ，利用联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a f ) 和 数据挖掘工具，来挖掘其中的有用知识。 在华中科技大学计算机学院达梦数据库正在承担的国家科技部电子政务工程子 项目“科技信息决策支持系统的研究与开发”中，要整合各种科技历史数据资源，建 立科技信息数据仓库，通过一般决策支持查询、o l a f 多维分析以及数据挖掘等工具 对数据仓库中的数据进行分析，获得有用信息，从而帮助科技都领导提高决策效率和 决策质量。 决策支持查询通常要对大量的低层数据进行分组( g r o u p i n g ) 和聚集( a g g r e g a t i o n ) ， 计算开销很大。为了快速响应复杂的决策支持查询，一个基本的优化技术就是：根据 用户的查询模式预先计算大量的查询，当后续相同的查询或类似的查询到来之时，我 们不必再次从头计算，而是充分利用先前的结果进行快速响应。预先计算的查询就称 为实化视图( m a t e r i a l i z e dv i e w s ) ，在不引起混淆时也简称为视图。r a l p hk i m b a l l 指出 提供一组适当的聚集实化视图能影响一个大型数据仓库的性能【i i 。 最近的t p c - r 基准测试和实际的用户经验都表明，正确使用实化视图可以使决 策支持查询处理时间改进几个数量级。 本文的工作就是研究和实现这项关键技术利用实化视图快速响应查询 ( a n s w e r i n gq u e r i e su s i n g m a t e r i a l i z e dv i e w s ) 。通过实化视图技术设计并实现o l a p 查询 优化工具。结合科技信息决策支持系统项目，为国产数据库d m 3 提供一种新的、有 效的查询优化机制，提高电子政务系统的分析效率。 一一 l 华中科技大学顽士学位论文 ；目_ 自= l s = 目_ _ ；= = 自- i 目_ i 目- 目_ ；目_ _ 目1 _ _ 目_ 目日 _ 目l l = | 1 2 国内外研究概况 数据仓库技术中，查询优化、数据物理独立性的维护、数据集成、数据仓库设计 等数据管理问题都与利用视图响应查询的问题相关。利用视图来重写查询必须是等价 的重写以保证查询的执行方案的正确性。视图只是减少方案的代价，而不要改变方案 的逻辑正确性。查询优化问题中，利用实化视图对查询进行重写可以提供一种更有效 的查询方案。数据库设计中，为了维持数据的逻辑和物理视图的分离性，存储模式可 以看成逻辑模式上的视图。视图的定义提供了一种机制来维护数据的物理视图和逻辑 视图的独立性。数据集成系统中数据源可以看成中介模式上的预先计算好的视图。 在数据仓库设计中需要实化一些视图，先要保证这些实化视图能够有效地响应查 询，这个问题又转化为视图重写闯题。本文主要对利用实化视图响应查询进行了研究， 因此这一节重点介绍它的研究情况。 为了实现实化视图的潜在好处，需要关于以下三个问题的有效解决方案l 2 1 。1 视 图选择：选择实化哪些视图，包括如何存储和索引它们。2 视图利用：有效地使用 实化视图来加速查询处理。3 视图维护：当基表发生变化时，有效地维护实化视图。 决定何时和怎样利用实化视图来处理查询是一个关键性的工作。 视图替代就是利用实化视图替代查询的某个子表达式，它可以看作查询优化中的 一个转换规则。目前提出的视图替代算法在如下几个方面有所差别：所考虑的查询表 达式的类型；所支持的实化视图类型：所考虑的替代表达式类型；是否和如何处理多 个替代表达式：基于包语义( 有重复元组) 还是集语义( 没有重复元组) ：是否利用了 某种约束。 l a r s o n 和y a h g 首先提出了对s p j ( s e l t n d j e c t j o i n ) 查询和视图的匹配算法【3 假设的情况是集语义、单表替换、没有约束条件。但产生的替换结果不能由s q l 语言 或者标准的关系代数表示出来。后来，他们对这个算法进行了扩展【5 1 ，考虑替换由视图 联接组成的情况，能找到所有有效的重写，但没有提到如何找到最好的重写 c h a u d h m i 等人研究的是一种限定描述形式的s p j 查询和视图、集语义的情况睁”。 2 华中科技大学硕士学位论文 = = ；= ；= ；j _ l 目口_ ；_ | 目；z = l = 目_ l ；_ 他们提出的匹配算法没有考虑谓词包含或者约束，并且使用了一个图表( m a pt a b l e ) 来指定视图可以完成对查询的哪一次替换。 g u p t a 、h a r i n a r y a n 和q u a s s 提出了一个广义的投影运算符【扪，它能在统一结构中 获取副本消除、聚集、群聚以及副本保存的投影。他们还提出了这种新算符的转换规 则，利用转换规则来生成利用聚集视图来重写的表达式。 s r i v a s t a v a 等人提出了的关于s p j g ( s e l e c t - p r o j e e t - j o i n g r o u p b y ) 查询与视图的视图 匹配算法 9 1 考虑了包语义但没有考虑约束，考虑了选择谓词的包含但没有详细描述如 何进行比较。除了单视图替代，还考虑了由视图联合替代的情况。但他们要求视图和 被替代的表达式引用相同的表，也没有讨论怎样在多个重写中进行选择。 o r a c l e 是第一个支持实化视图的商业数据库系统1 1 0 1 ，要求视图包含联接、聚集， 但不包含选择条件。在o r a c l e8 i 资料中提出了一个简要的查询重写算法。这个算法考 虑一个s p j g 查询的一部分或者全部由一个实化视图替换的情况。替换表达式中可能 用到多视图。如果可能是多路重写的话，根据启发式的原则基于视图的尺寸选择一种 重写方案，然后优化选择的重写方案而且和没有用实化视图的最佳方案进行比较。 p o t t i n g e r 和l e v y 设想了数据集成中对于s p j 查询和视图的视图匹配问题f 1 1 i 。在 这种环境下，视图描述可以从某个数据源得到的数据，查询只能由视图来响应。这样 就可能找不到等价于查询的重写。取而代之地，目标就是尽可能地接近查询结果。 j o n a t h a no o l d s t e i n 和p e r - a k el a r s o n 提出的基于s p j g 视图作单视图替换的视图 匹配算法【2 】引进了列等价类的概念，由查询和视图的选择条件的列等值判定表达式计 算等价类集合，还提出了从一个视图计算出一个查询要满足的几个条件。 z a h a t i o u d a k i s 等人提出了一个在d b 2u d b 上实现的视图匹配算法【”l 。这个算法 执行一个自下至上的查询图表的匹配，不需要精确的匹配。 一个查询的分组列必须是一个视图的分组列的子集，这一条件是充分的但不是必 要的。p a r k 、k i m 和l e e 利用这些函数依赖关系定义了o l a p 查询和视图之间的偏序 关系，即格h 1 。从中观察到的一个关键点在于：对于一个视图，只有当它和查询在格 的同一层或比查询的层次低，他们的算法可能会生成包括联合与联接的替代，他们利 华中科技大学项士学位论文 用启发式规则来选择最好的重写。 l e v y 、m e n d e l z o n 和s a g i 等人研究了利用视图重写s p j 查询的算法复杂性问题【”l ， 并且证明许多相关问题是n p c o m p l e t e 问题。 利用实化视图响应查询时，还需要用到查询优化的相关技术。在查询优化的策路 方面，p i r a h e s h 等人提出了扩展的基于规则的查询重写方法【i6 1 ，g r a e f e 等人提出了“瀑 布”( c a s c a d e ) 结构【17 1 。在查询优化器的设计上，m i t c h e l l 等人提出了可扩展的优化器【埽1 ， g r a e f e 等人提出了一个优化器的生成器v o l c m m 1 9 1 ，k a b r a 等人用面向对象的方法设计 了一个可扩展的查询优化器的生成器【2 0 】。 视图选择问题的最初动机来自数据仓库设计，我们需要决定把哪些视图存放在仓 库中以获取最佳性能。目前，已经提出了一些面向数据仓库的视图选择算法。g u p t a l 2 1 t 、 t h e o d o r a t o s 等人嘲提出了几种视图选择的框架和选择算法以优化查询响应时间，但 这些算法不适合候选视图数较多的情况。a g r a w a l 等人【2 3 1 提出了多种方法预先筛选候 选视图，然后再进行视图选择，使视图选择具有可扩展性，他们还把视图选择与索引 选择结合起来考虑。h a r i n a r a y a n 等人【2 4 】证明基于数据立方的视图选择问题是一个 n p - h a r d 问题，并提出一种多项式贪心算法b p u s 。1 9 9 8 年s h u k l a 等人【2 5 1 又提出了一 种简单快速的计算方法p b s ，并且证明对一个s r - - h y p e r c u b e 格，p b s 所选出的视图 配置与最优的视图配置的比值不小于( o 6 3 f ) 。r o s s 等人 2 6 1 还提出基于内存的数据立 方的视图选择问题和相应的算法。 k a r l o 等人曙7 】和c h i r k o v a 等人阱1 还研究了视图选择问题的复杂性，证明了视图选择 问题也是一个n p 问题。r o s s 等人1 和g u p t a 等人1 3 0 1 还把视图选择与视图维护结合起来 考虑，使所选视图满足查询的执行代价与视图的维护代价总体上最小。 为了选择视图，还必须在视图未实化之前事先估计每个视图的大小。s h u k l a 等p ” 提出了基于数据立方的聚集视图大小的估算方法，包括了三种策略：基于采样、基于 数学近似以及基于概率统计。并且证明了基于概率统计的方法可以确定出估算错误的 边界。h 豁s 等人提出了基于采样的方法圈，a s t r a h a n 等k t 3 3 1 和f l 萄o l e t 等人瞰1 则提出了 基于概率统计的方法估计一个属性中不同值的个数。 华中科技大学硕士学位论文 另外。a g r a w a l 等人进一步把视图选择问题与索引选择问题结合起来加以考虑，并 提出用视图合并的方法减少待选择视图数量。 1 3 本文研究内容 利用实化视图响应查询的问题是国家科技部电子政务工程项目的子课题。本文的 目标在于利用实化视图技术设计并实现o l a f 查询优化工具，提高电子政务系统的分 析效率，结合科技信息决策支持系统项目，也为国产数据库管理系统d m 3 提供一种 新的、有效的查询优化机制。 本文相关的主要研究内容有以下5 个方面。 1 研究目前数据仓库中实化视图技术发展的国内外概况，研究和比较国内外利 用实化视图快速响应查询的有效解决方案。 2 研究决策支持系统的多维数据模型，包括星型模式、雪花模式和数据立方等 基本概念，描述科技信息决策支持系统基本框架，以及本课题在其中的任务与功能。 3 提出一个视图匹配算法。这个算法主要研究实化视图和查询的匹配和产生重 写查询的问题。将一个查询或者视图按几个替代条件分成几个部分。每一个部分分别 匹配，而且还要结合其它的替代条件，最后计算出重写查询。 4 介绍视图匹配算法的实现。在有大量实化视图的实际系统中，如果对实化视 图集合采用顺序扫描的话会增加搜索可用视图所需的内存空间和搜索时间。因此，这 个过程中将引入一个过滤树以及格索引结构。过滤树将实化视图集合按照某些分解条 件存储起来。格索引提供一种在过滤树中搜索视图的机制，用来快速地搜索可能响应 查询的候选视图的范围。 5 结合一个简单的代价模型，提出快速寻找较优重写查询的启发式算法。 一一_ - - _ 一 5 华中科技大学硕士学位论文 2 系统概述 2 1 引言 在决策支持之类的o l a p 应用中通常采用的概念模型是多维数据模型，它符合人 们从多个角度( 即维) 分析问题的r 常习惯。在这一模型中。有一组数值度量( n u m e r i c m e a s u r e s ) 作为分析的对象，与之相关的则是一组维，维提供了度量所依赖的分析上 下文。例如，给定汽车销售表( 颜色、厂商、生产年份、销售额) ，其中的销售额就 是度量，而颜色、厂商、生产年份就是决定销售额这一度量的3 个维。 对于多维数据模型，一种基本方式是采用多维数组童接实现，建立多维联机分析 处理服务器m o l a p ( m u l t i d i m e n s i o n a lo l a p ) 。另一种方式则是用传统的关系表以星 型或雪花模式进行模拟，建立关系型联机分析处理服务器r o l a p ( r e l a t i o n a lo l a p ) 。 r o l a p 的好处在于可以充分利用关系数据库管理系统处理超大规模数据的各种能 力，而m o l a p 只能快速处理小批量的数据。因此r o l a p 是目前联机分析处理服务 器的主流。 下面我们将首先介绍星型模式，包括雪花模式和数据立方等基本概念，然后基于 这些基本概念，描述科技信息决策支持系统基本框架，以及本课题在其中的任务与功 能。 2 2 星型模式与雪花模式 绝大多数数据仓库都使用星型模式来表示多维数据模型。一个星型模式由一个事 实表与若干维表组成。事实表中每条元组包含指向每一维表中与之对应的那个元组的 外键( f o r e i g nk e y ) ，并且保存与这些外键相连的度量值。每个维表则包含了描述该维的 对应属性。星型模式并不明确地支持维层次。所谓维层次就是表达维属性不同粒度大 小的概念层次。比如说，对于时间维日一月一年即是它的一个维层次。也就是每一 一_ 一 再 华中科技大学硕士学位论文 = 霉皇昌暑宣j 兰胄_ 暑_ 盲窖= _ i i i _ l 囊墨_ e 葺_ - - _ _ _ _ _ - _ _ 一 日必然对应唯一的那个月份，同样该月份对应唯一的那个年份。通过对维表进行规范 化，雪花模式可以改进星型模式。从而明确地支持维层次。雪花模式有利于维表的维 护，但星型模式更方便对维的浏览，因为与该维相关的属性在没有规范化的情况下都 保留在同一个关系表中。 图2 1 即是一个雪花，星型模式的例子，它表示的就是t p c - h r 基准所采用的模 式。t p c - h 是对决策支持应用中即席查询( a dh o cq u e r i e s ) 的评测基准，t p c r 则是它 的增强，用于对决策支持应用中复杂报表能力进行评测。 图2 1 雪花，星型模式例子 在这一例子中，l i n e i t e m 就是所谓的事实表，其中的销售额( 1 _ e x t e n d e d p r i e e + l q 咖畦劬就是令人感兴趣的一个度量。维表o r d e r s ，p a r t 和s u p p l i e r 分别通过 各自的外键与之相连。r e g i o n 和n a t i o n 则是一个维层次的例子，即一个地区对 应唯一的那个国度。 在后续章节中讨论利用实化视图响应查询技术时，我们都将上述模式为基础a _ _ _ _ _ 一 ， 华中科技大学硕士学位论文 = ；目= = = ；j ；_ _ ；- _ - _ _ _ 自；_ e 自l _ _ i _ 目 2 3 数据立方 数据立方本质上就是定义在事实表上的视图。j i mg r a y 等人在1 9 9 6 年首次提出 了数据立方概念和数据立方计算问题f 3 6 1 ，并用c u b eb y 算子表示数据立方的计算。 c u b e 算予扩展了通常的g r o u pb y 操作，用于计算c u b eb y 子句中各属性的所有 可能组合所对应的g r o u pb y 。例如，考虑一个关系基表s a l e s ( d a t e ，p r o d u c t ， c u s t o m e r , a m o u n t ) ，数据立方查询： s e l e c t d a t e p r o d u c t , c u s t o m e r , s u m ( a m o u n o f r o ms a l e s c u b eb y d a t e ，p r o d u c t ，c u s t o m e r 将对c u b e b y 的属性d a t e ，p r o d u c t 和c u s t o m e r 的所有组合所对应的8 个g r o u p b y 上进行u n i o n 计算，b i j ( d a t e ，p r o d u c t , c u s t o m e r ) 、( d a t e ，p r o d u c t ) 、( d a t e ，c u s t o m e r ) 、 ( p r o d u c t ，c u s t o m e r ) 、( d a t e ) 、( p r o d u c t ) 、( c u s t o m e r ) 和a l l ( 即g r o u pb y 属性为空的 那个聚集) 。总之，对于含n 个c u b eb y 属性的c u b e 操作，将要计算2 8 个不同的 g r o u pb y 。在o l a p 术语中，c u b eb y 子句中各属性又被称作维( d i m e n s i o n ) ；而 被聚集计算的属性则被称作度( m e a s u r e ，或度量) ，如s u m ( a m o u n o 中的a m o u n t 即度 a m o u n t ：一个g r o u p b y 也被称作一个数据小方( c u b o i d ) 。 数据立方算子一经定义，就引起了学术界和工业界的广泛关注。工业界的主要数 据库厂商无一不把数据立方作为其o l a p 服务器的构建基础，如m ss q ls e r v e r 2 0 0 0o l a ps e r v e r ，i b md b 2o l a ps e r v e r7 2 和o r a c l e9 ie x p r e s ss e r v e r 等等。 事实上，数据立方算子与上钻( r o l l u p ) 算子一起作为s q l - 9 2 标准在o l a p 方面的扩展， 已经正式被s q l 9 9 标准 m a t t 9 9 采用。在科技信息决策支持系统中，我们的联机分 析处理服务器同样也以数据立方为核心 o l a p 服务器预先计算整个数据立方或者有选择的计算其中一部分作为实化视图 用来快速响应复杂的决策支持查询。 8 华中科技大学硕士学位论文 = = 鲁重譬毒害昌皇_ _ = 嗣_ l 宣_ l 兽- _ 曩- _ _ i _ 置皇l i 昌宣_ 鼍_ 一 一- 一 _ - _ _ l 一l _ 2 4 科技信息决策支持系统基本框架 整个科技信息决策支持系统采用如图2 2 所示的三层结构。 j上层：前端工具 l 查询版衰数据立方定灿测览 数据挖掘 l 丁 中间层：d m - o l a p 服务器 视图匹配模块查询处理模块视图选择模块 数据立方计算模块数据立方索引，存储模块 t 底层：d m d w 数据仓库服务器 元数据定义器视图定义器 元数据存储器 圈圈圆 圈2 2 科技部信息决策支持系统结构图 1 底层是基于d m 3 的数据仓库服务器( d i d w ) 【3 7 铡，以集成数据源的原始数据， 并在需要的时候，对任意查询做底层的支撑。它负责管理数据和元数据，元数据包括 了实化视图的定义及描述信息和其它用于查询优化的统计信息。d m d w 通过元数据 华中科技大学硕士学位论文 = ；= = j = l ；= = 自_ i e e ；= 自目自i l 目i _ | _ _ i e t _ l 目= _ # e _ 自_ i i _ | - _ _ - _ - l l _ _ l - - l _ _ _ _ 自| _ _ 目 定义器单独定义和管理关于数据源的元数据。 ( 1 ) 元数据定义器 数据源元数据的作用是用来集成数据源上的数据，它的特点是在各数据源上本来 存在，但内容和格式差别很大，难于自动集成，需要通过人工或半自动的方法进行整 合。系统管理员是通过手工方法利用元数据定义器来说明数据源的相关信息，并作为 元数据存放在元数据存储器中。例如，关于关系型数据源的元数据一般要包括数据源 的位置、数据源名、数据库名、表名和表的属性，另外还需要说明对每个表的数据的 集成方法。 ( 2 ) 视图定义器 d m d w 采用s q l 语言定义实化视图。视图定义器专门用于定义实化视图，并且 把实化视图定义和实化视图所构成的过滤树作为元数据保存起来。对用户输入的视图 定义，首先作词法和语法分析。通过查看元数据存储器中的数据源信息对它进行分析， 实化视图定义涉及的数据源基表信息必须事先在元数据中说明，否则视图定义将判为 不正确。正确的实化视图定义将存放在元数据存储器中。同时，视图定义器还把分析 结果转换成的视图描述信息也作为元数据保存起来，并且在过滤树中插入这个视图。 在利用视图响应奁询时将要用到过滤树和视图描述信息。 由于以下3 个方面的原因，d m - d w 与d m 3 采用了松散耦合的方式进行集成。 ( 1 ) 数据立方计算要消耗大量的资源，直接在d m 3 中计算将影响d m 3 处理其它事 务的效率。 ( 2 ) 在利用实化视图响应查询时采用基于规则的查询优化方法找出较优的重写查 询，可以不使用数据库管理系统的查询优化器。 ( 3 ) d m 3 已经提供了o d b c 、j d b c 和o l e d b 等标准化的接口，使用这些接口可 以方便地从相关数据源中提取数据。 因此，把d m 3 则作为底层数据库负责保存数据仓库数据和处理查询等工作， 一一一 1 0 华中科技大学硕士学位论文 d m d w 与d m 3 就以松散耦合的方式实现了集成。d m d w 可以看作d m 3 的一个插 件，为d m 3 提供了决策支持平台。 2 中间层为联机分析处理服务器( d m - o l a p ) 。联机分析处理工具将数据仓库中的 数据组织成多维数据立方的形式，支持复杂的多维分析。d m o l a p 从d m d w 中的 基表导出数据立方或数据小方，支持多维联机数据分析。实化后的数据立方以及建立 在它们之上的多维数据立方索引都直接保存在d m o l a p 中。 当有用户查询提交给d m o l a p 时，先判断能否完全由它响应查询。 ( 1 ) 如果不行则进行相应的查询分解，形成d m - d w 可以执行的一组查询或子查询 传递给d m - d w 来响应，查询结果经d m - d w 作可能的进一步处理之后返回给用户。 然后利用视图选择模块确定是否将这次查询的结果保存在d m - o l a p 之中，以备后用。 ( 2 ) 对于能直接利用d m - o l a p 中已经实化的数据立方或数据小方( 部分实化的数 据立方) ，经视图匹配模块改写后的用户查询，交给查询处理模块执行。数据立方存储 与索引模块提供物理存取支持。 3 ) 某个查询可以由d m - o l a p 部分响应，则需综合前两种情形的处理， 3 最后是顶层前端工具，包括数据挖掘工具，智能报表工具、一般决策支持查询 工具以及其它办公自动化工具等等。 前端负责向d m o l a p 提交查询，并向用户展现结果集。d m - o l a p 接收来自客 户端的查询。首先，分析词法和语法，构造语法树，并在数据字典的帮助下，傲一定 的语义分析。然后，在数据字典的帮助下，将各个维上的限制条件翻译成值区间。因 为查询的粒度不一定能够得到匹配，就涉及到下钻到更细粒度的视图来回答查询，即 要求将较粗粒度的区间转换到较细粒度的区间。最后，访问存储接i z l ，提取数据，做 相应的聚集计算和连接操作，并格式化结果集，发送给客户端。 4 数据提取：对于建立在本身具有o d b c 和j d b c 接口的数据库管理系统( 如： _ _ _ - _ _ - _ _ _ - _ _ _ 一 l l 华中科技大学硕士学位论文 = = = ；l # = 目口t = 目_ 自；_ l = ；_ l = _ _ l 目- z _ l 目；t _ _ll m s s q ls e r v e r , o r a c l e ，d b 2 ，s y b a s e 等) 之上的各个数据库，可以通过o d b c 或j d b c 接口提取出来，在经过数据清理与整合之后，再通过o d b c 或j d b c 接口导入数据仓 库a 对于不具备o d b c 和j d b c 接口的数据库( 如：直接以一般的文本文件集合构 成的数据库) ，则通过基于x m l 的中间件提取数据和导入数据仓库。因为d m 3 是具 有o d b c 和j d b c 接1 3 的数据库管理系统，所以采用前一种方式进行数据提取。 j 数据清理与集成：处理脏数据。消除重复数据，为不完整的数据添补丢失的 字段值，解决数据之间的所有矛盾之处，如字段的同名异义、异名同义、量纲不统一、 字段长度不一致等等。 6 数据加载与刷新：经过数据提取、数据清理与集成之后，数据就加载到数据 仓库之中。在加载过程中可能需要同时进行一些额外的处理：检查数据完整性约束， 排亭，汇总以及建立索引等等。数据刷新就是将各个数据来源中发生的更新传播到数 据仓库。 2 5 小结 我们建立的决策支持系统的联机分析处理原型系统会以数据立方为核心。本章首 先介绍了星型模式、雪花模式和数据立方等基本概念，然后描述了科技信息决策支持 系统的基本框架，包括前端工具，中间d m o l a p 服务器、底层d m d w 数据仓库管 理系统。 华中科技大学硕士学位论文 = = = ；= = = = - e = 4 _ ；l _ _ _ i _ 目j _ e = _ _ l _ _ _ _ - l _ i - _ _ _ l _ ej= 3 实化视图匹配算法的研究 3 i 引言 实化视图的结果已经被存储了，在计算查询时能直接利用实化视图，就可以避免从 基表重新计算提高查询处理的效率。利用实化视图响应查询，首先应该解决视图替代 问题。为了解决视图替代的问题，本章重点介绍视图匹配算法。 3 视图的典型定义 典型的视图由s q l 语句定义，s q l 语句由选择( s e l e c t ) 、投影( p r o j e c t ) 、连接 ( j o i n ) 和分组( g r o u p b y ) 子句组成，这样的视图称作s p j g 视图。如果没有g r o u b y 子句，称作s p j 视图。f r o m 子句必须引用基表，即不允许有予查询。s p j g 视图的 s e l e c t 子旬由两个部分组成：非聚集列和聚集列。聚集列可以包含s u m ，c o u n t 聚集函数。而且，如果查询的分组列表非空，那么非聚集输出列必须是分组列表的子 集，而实化视图中所有的g r o u b y 表达式必须包含在输出列表中以保证每一元组有唯 一的关键字，所以非聚集输出列表和分组列表要求是相同的。 咧3 1 是一个视图的典型定义，以图2 1 的星型模式为基础。 例3 1 ：c r e a t e v i e wvw i t hs c h e m a b i n d i n g 勰 s e l e c t p _ p a r t k e y , p n a m e ，c o u n t _ b i g ( + ) a sc n t ， s u m ( 1 _ e x t e n d e d p r i c e + l _ q u a n t i t y ) a sg r o s s _ r e v e n u e f r o m l i n e i t e m ，p a r t w h e r e p _ p a r t k e y w v 成立。 l s 华中科技大学硕士学位论文 因此，问题的关键在于判断w q = w v 是否成立。将谓词重写成 w q = p q 1 “p q 2 “p q m 以及w v = p v 1 “p v 2 “p v m 的形式。一个最简单的想法就是 w v 中的每一个合取式p v i 是否与w q 中的某一个合取式p v i 相匹配。如果采用纯句法 上的匹配，将每一个合取式转换成一个字符串，即该合取式的s q l 文本，然后匹配字 符串。这个方法的缺点是句法上的小差别就会得到不同的字符串。如谓词( a b ) 和 ( b w v ) 改写成( p e q “p r q “p u q = p e v p r v p u v ) 。p e q 由查询中 的列等值谓词组成，p r q 包含列范围约束谓词，p u q 是包含了w q 中除了p e q 和p r q 的所有合取式组成的剩余谓词。w v 也类似划分。一个列等值谓词的基本形式是 t i c 刚c q ，这里c p 和c q 都是属性列。一个列范围约束谓词的基本形式是( t i c po p c ) ，这旱c 是一个常量，o p 是操作符“ ”。然后w q = w v 就被分成了三个部分：( p e q “p r q p u q = p e v ) “( p e q “p r q p u q 2 p r y ) a ( p e q “p r q p u q = p u v ) 。一个蕴涵式如果去掉前提的某些合取式，会彼加强( 用一般形式表示，对于 任何a 、b 、c ，( a = c ) = = ( a b = c ) 。也就是说如果推论出a 蕴涵c ，那么a 和b 一 起也蕴涵c ) 。检查视图中是否包含了满足查询条件的所有元组，总结为下面三个检测： ( p e q = p e v ) ( 等值联接包含检测) 、( p e q p r q = p r v ) ( 范围约束包含检测) 、 ( p e q p u a = p u v ) ( 余项包含检测) 。第一个检测之所以叫等值联接包含检测，是因为 实际上大部分列等值谓词都来自等值联接，而所有的列等值谓词都包含在p e 中，甚至 是在同一个表中出现的引用列。在后面的两个蕴涵式中p e q 出现在前提中，所以可以 通过查询的等价类来替换引用列。 以上的强化过程可能会导致某些情况的遗漏。例如，在等值联接检测蕴涵式的前 提中去掉p r q ，在出现了查询中两列等于同一常量的情况时会出错，即( a _ 2 ) ( b ：2 ) ， 视图中包含了较弱的谓词约束( a = b ) 。剩余包含检测会有类似的情况，例如，查询包含 了谓词( a - 2 ) n ( b _ 3 ) ，而视图中包含了谓词( a + b ) - 5 ，将会错误的推断出视图不能提供 一_ _ - _ _ _ _ _ _ - - 一 1 6 华中科技大学硕士学位论文 查询所需要的元组。这是速度和完全性的折衷。 ( 1 ) 等值联接谓词包含检测 等值联接包含检测相当于要求所有在视图中相等的列在查询中也必须相等( 但不 是反之亦然) 。进行这个检测首先要用前面的方法计算查询和视图的列等价类，然后 检查每一个视图非平凡等价类是否是某一查询等价类的子集。另外，由于传递性，只 检测p e v 中的所有列等