（计算机应用技术专业论文）自适应查询处理技术研究.pdf

河海大学硕士研究生毕业论文 自适应查询处理技术研究 摘要 本文主要从查询处理自适应性方面进行研究，在已经存在的适应性查询处理 技术基础之上，将自适应性与遗传算法相结合，提出自适应性遗传算法，并给出 实验结果。本文的主要研究成果如下： 1 、首先综合分析了适应性查询处理研究现状和发展趋势，介绍了 m e d i a t o r w r a p p e r 集成系统体系结构，针对数据集成系统查询处理过程的特点设 计了一个查询优化器，该优化器具有支持系统进行动态查询优化的能力，可以有 效提高系统的查询处理性能。 2 、提出自适应性遗传算法一种基于遗传算法的多数据源连接查询优化 问题的方法以及与此相适应的交叉变异概率、编码方法、交叉算子和变异算子。 该算法适用于集成系统中具有约束模式的数据源。我们将遗传算法与数据源的约 束模式有效地结合起来，将查询优化分成两个阶段进行，第一阶段利用数据源的 查询处理能力划分搜索空间，第二阶段利用第一阶段的结果作为启发式信息，采 用遗传算法寻找最优解或次优解。该方法不仅可用于左深度树搜索空间，同样适 用于混合搜索空间。同时还引入了n c i g 缸b o x 结构以解决传统遗传算法局部收敛 速度慢的缺点，有效的缩短了计算时问，提高了系统的查询效率。 本文详细地描述了自适应性遗传算法的具体算法和实验结果，对算法的性能 进行了分析，给出了有说服力的结果比较，并指出了未来的研究方向。 关键词：自适应性，遗传算法，查询处理 河海大学硕士研究生毕业论文自适应查询处理技术研究 a b s t r a c t t h er e s e a r c ho ft h i sp a p e ri sb a s e do i lt h ea d a p t a b i l i t yo fq u e r yp r o c e s s i n g ，f o c u s i n go nt h e s e l f - a d a p t i v eq u e r yp r o c e s s i n g a ni m p r o v e da r i t h m e t i cc a l l e ds e n - a d a p t i v eg a i sp r o p o s e d t h e m a i nc o n t r i b u t i o n so f t h i st h e s i sa l ea sf o m o w s f i r s t , t h ec u r r e n ta p p r o a c h e so fq u e r yp r o c e s s i n ga r es u m m a r i z e d w em a k ea no v e r v i e wo n t h em e d i a t o r w r a p p e ri n t e g r a t i o ns y s t e m s t h e nan e w q u e r yo p t i m i z e ri sd e s i g n e db a s e d 0 1 1t h e a n a l y s i st h eq u e r yp r o c e s s e sa n do p t i m i z a t i o n i nt h ed i ，t h i so p t i m i z e rc a n s u p p o r td y n a m i cq u e r y o p t i m i z a t i o na n d e n h a n c et h ep e r f o r m a n c eo fs y s t e m s e f f e c t i v e l y s e c o n d ，a ni m p r o v e dm e t h o dc a l l e ds e r f - a d a p 咖eg at os o l v em u l t i - j o i nq u e r y o p t i m i z a t i o n b a s e do ug a i s p r o p o s e di nt h i st h e s i s a c c o r d i n gt om u l t i - j o i nq u e r ye x p r e s s i o n s ，e n c o d em e t h o d c r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ra r ei n t r o d u c e d i nd a t ai n t e g r a t i o ns y s t e m ，m a n yd a t a s o u r c e sh a v el i m i t e dq u e r yc a p a c i t yw h i c hc a nb ee x p r e s s e db yb i n dp a t t e r n s oo u rm e t h o di s p a r t i t i o n e di n t ot w op h a s e s ，i nt h ef i r s tp h a s et h es e a r c hs p a c eo fg ac a l lb er e d u c e d b yt h eb i n d p a a e m o fd a t as o i l r c c sa n di nt h es e c o n d p h a s e ，g ae x p l o i t st h ei e s i l l to f p h a s e1a sh e u r i s t i c sa n d s e e k st h eo p t i m a lq u e r ye x e c u t i o np l a n t h i sm e t h o dc a nb eu s e dn o to n l yf o rs e a r c hs p a c eo f l e f t d e e pb u ta i s of o rh y b r i ds e a r c hs p a c e s t h er e s u l t ss h o wt h a to u ra l g o r i t h mi sm o r ee f f i c i e n t w h i l et h e r ea r em a n yd a t as o u r c e s i n t e g r a t e d a l lt h ed e t a i l so ft h es e l f - a d a p t i v eg a a r ed e s c r i b e di nt h i sp a p e ra n d p r o m i s i n gr e s u l t sa l e g i v e n w ea l s oi n d i c a t e dt h ef u t u r ew o r ka tt h ee n do ft h i sp a p e r k e yw o r d s ：s e r f - a d a p t i v e ，g a ，q u e r yp r o c e s s i n g i i 河海大学硕士研究生毕业论文 自适应查询处理技术研究 1 1 背景 第1 章绪论 传统数据库系统的查询优化技术的基础是基于统计的代价估计。但随着基于 i n t e r n e t 的数据查询系统的发展与普及，有几方面的因素导致查询代价的估计很 难做到准确： 1 、硬件和系统负载的复杂性； 2 、数据本身的复杂性( 对象一关系数据的出现、w e b 数据的复杂性、远程数据 源的数据1 ： 3 、用户接口的复杂性( 长时间的连续查询需要联机的聚集操作，或者需要根 据部分结果的输出实时调整查询的属性1 。 目前的i n t e m e t 可以看作一个庞大的分布式和异构化数据库，各个数据源具 有自治性，加上广域网网络传输带宽的限制，各个数据源数据的可访问性以及传 输速度是经常变化和不可预测的。因此需要建立一种自适应系统，使用新的查询 引擎，新的查询优化机制，能自适应地处理针对变化数据的所有联机复杂查询， 这就是自适应性查询处理。 一个自适应的系统必须具备3 种能力 1 、能够感知环境的信息； 2 、能够根据环境信息做出反馈： 3 、能够不断地重复前两个步骤。 对适应性的评价也有3 个方面： 1 、频率一接收信息并改变行为的频率： 2 、效果一能改变什么行为； 3 、时长一能持续多长时间。 1 河海大学硕士研究生毕业论文 自适应查询处理技术研究 而适应性和自适应性又有很大的不同： 适应性( a d a p t i v e ) ：通过收集运行时间环境信息来决定后来的行为；随着时 间的变化，信息收集和行为修改过程不断变化，在运行时间环境和系统行为之间 产生反馈。对每一种查询，运行时间环境信息可能包括详细数据源的统计，当时 的网络状态。这些信息都是人为的。 自适应性( s e r f - a d a p t i v e ) ：信息和反馈控制的收集或了解都是通过系统来自 动的完成，而不是通过人机交互提供；系统会对收到的反馈立即做出特殊环境的 改变。 1 2 自适应查询处理技术发展纵览 现在我们简单地回顾一下迄今为止已经出现在数据处理中的自适应技术，看 看自适应技术的发展现状和趋势。我们发现自适应性发展的基本趋势是适应的频 率越来越高。 先看看早期的关系系统。在s y s t e m r 的查询优化器中，和现在的大多数关系 系统一样，是通过周期性地大规模地重新收集系统的统计信息，来影响以后的查 询计划的生成。我们把这称为批量适应。在i n g r e s 系统中，通过“查询分解”技 术，在多表连接时，根据每一轮n e s t e d 1 0 0 p sj o i n 的情况，动态地确定下一个要 j o i n 的表或中间结果。这里的适应频率相对较高，达到了查询内部甚至操作( j o i n ) 内部的适应性。但是它的时长较短，只在一次查询内部有效。 另一种自适应技术是关于后期绑定策略。在s y s t e m r 中以及现有的商用 d b m s 中有一种技术是生成带参数的查询计划，可以被多条相同的查询反复使 用。而在8 0 年代末到9 0 年代初，出现了一系列论文论述了这种策略的弱点：在 接下来的查询中，运行时环境参数可能会存在很多的改变，包括用户输入的常量 变化从而引起选择性的变化，可用内存的变化等。为了解决这个问题，g r a e f e 和c o l e 提出了动态查询计划【2 l ，对环境可能的变化给出一定的约束，使优化器 丢弃那些在所有情况下均是次优的计划，优化的结果就得到一个执行计划的集 河海大学硕士研究生毕业论文 自适应查询处理技术研究 合，等到执行的时候再根据环境参数选择一条最适合的进行执行。这种策略专注 于将部分决策推迟到执行时，但在适应性的频率和时长上与早期的关系系统没有 区别，仍然属于批量适应。 再来看看“每查询”的适应性。针对s y s l e mr 等系统在适应性方面的弱点， c h i n 和r o u s s o p o u l o s 提出了“自适应选择性估计”( a s e l 策略来增强系统的适应 性。当一个查询在被执行的过程中，中间结果的大小会被系统记录和跟踪，从而 可以用来更新系统的统计信息，从而有利于对后续的查询做出更优的查询计划。 这种策略可以逐渐适应系统环境的变化，适应性反馈的频率是“每查询”，粒度 比原先s y s t e mr 系统要小得多了。 迄今为止，最为少见的查询优化器是d e c 的( 后来是o r a c l e 的) r d b 系统。 r d b 是第一个引入“竞争”机制的系统。它同时执行多种可选的查询计划，在 短时间内选出最快的，结束其它计划的执行。这点与后来的数据处理中的e d d y 机制有类似之处，植仍然属于“每查询”的适应性。 以上介绍的技术在查询优化的水平上进行适应：访问方法的选择，j o i n 算法， 以及j o i n 的顺序选择。然而适应的水平还可以进一步在单独的操作上进行。这 种操作内部的适应性甚至可以在固定的查询计划下达到。例如，对内存大小自动 适应的排序和h a s h 算法【3 一】，能够自动的根据可用内存的大小对算法进行调整。 近来，在对于数据查询处理的研究过程中，出现了流水线式的j o i n 操作。包括 x j o i n 5 l 和r i p p l ej o i n 6 等，将适应的程度大大增加，适应的粒度达到“每元组” 的水平。 自适应性查询处理可以分为四类： 基于时序的方法一保存了查询计划的逻辑结构，通过c p u 处理操作来重新确 定顺序。很明显的，这种方法掩盖了延迟，或者导致某一结果提前出现。像适应 性连接算子【3 5 ，3 6 t 3 7 1 ，不规则查询【3 8 l 和动态重组【3 9 l 都是这样的方法。 冗余计算方法使用多种查询计划处理同一数据【蚰1 。某段时间间隔或是完全 河海大学硕士研究生毕业论文 自适应查询处理技术研究 到达临界值的时候，只有一个计划继续进行，其它所有的计划终止。 计划分割方法一在某个中间具体状态或者封闭操作( 如：集合) 之后，试图 改变物理计划。查询引擎可以选择嵌入式子计划【4 1 l 或者运行时重新优化触发器 【4 2 】。 数据分割方法一发送数据的不同部分到不同的计划。e d d i e s 决定本地行程安 排，通过一系列查询算子、潜在的唯一路径发送烈每个元组 4 3 , 4 4 1 。s t a t e m o d u l e s ( s t e m s ) 提炼行程安排粒度，这样两个数据项目可以得到不同的存取方 法和连接算法【4 5 】。( 由于e d d i e s 和s t e m s 同时执行多重算子，补偿延迟，所以它 们也获取时序方法的某些方面) 1 - 3 相关的研究成果及原形系统 由于越来越多的i n t e m e t 应用需要进行自适应性查询处理，该技术正在成为 一个热点。很多研究机构和团体都在对这一课题进行系统地研究，并开发了一些 原型系统来验证技术的可行性与有效性。这些原型系统的共同特点是支持适应性 查询处理，但又各有其侧重点，以下是对它们的简单总结，读者如感兴趣，可以 阅读参考文献以获得进一步细节。 威斯康星大学的n i a g a r ai n t e m e t 7 查询系统关注在广域环境中的多数据源集 成，通过重构查询引擎，设计非阻塞操作符来产生部分查询结果，并采用同步信 息包引发部分查询结果的产生，同时设计校正机制逐步修正部分查询结果，最终 产生正确的完整查询结果。由于该系统的设计目的为i n t e m e t 查询，因此支持x m l 查询。华盛顿大学的t u k w i l a l 8 , 9 1 数据集成系统，也将适应性内建于核心中，通过 交织查询计划生成和执行动态调整和优化查询计划。与n i a g a r a 系统采用同步信 息包控制部分结果的产生不同，t u k w i l a 系统采用“事件条件。动作”规则协调 适应性行为。该系统也支持x m l 查询，并设计了特殊操作符c o l l e c t o r 来删除冗余 数据。 布朗大学，麻省理工学院和b r a n d e i s 大学合作的a u r o r a 【1 0 系统，主要为流式 数据监控应用设计，如网络状态数据，股票数据等。这类应用重在查询结果产生 4 河海大学硕士研究生毕业论文自适应查询处理技术研究 的实时性。a u r o r a 系统中适应性查询操作符的设计借鉴了一些计算机网络领域的 技术，如滑动窗口技术。系统基于q o s 描述的变化调整查询的执行。加州大学 伯克利分校的t e l e g r a p h 1 1 】项目旨在关注分布式查询处理及并行查询处理，开发 可以高频率地收集反馈并据以作出反应连续式适应性查询处理引擎。亚利桑那州 立大学的h a v a s u 1 2 j 系统是一个应用于w e b 数据集成的多目标适应性查询处理架 构，根据用户的要求调整查询计划。 国内的有华中科技大学计算机科学与技术学院研制的基于c o r b 刖x m l 的 多数据库原型系统p a n o r a m a 和东南大学研制的v e l s a t i l e 系统以及g a l a x y 系统等。 p a n o r a m a 是种扩展的多数据库集成系统，不仅可以集成各种异构的数据库管 理系统，还可以集成w e b 上的一些文件系统。此外该系统支持常用的查询，修 改等操作以及基本的事务处理命令。除以上原型系统外，因为产生部分查询结果 的关键是生成非阻塞查询计划，亦即设计非阻塞查询操作符。由于大部分多元操 作符都是阻塞的，如j o i n ，适应性查询处理的研究工作也包括设计非阻塞操作符， 如多种非阻塞j o i n ，包括x j o i n ，对称式哈希j o i n 等。 河海大学硕士研究生毕业论文 自适应查询处理技术研究 1 4 本文的工作以及论文的组织 本文主要从查询处理自适应性方面进行研究，在已经存在的适应性查询处理 技术基础之上，将自适应性与遗传算法相结合，提出自适应性遗传算法，并给出 实验结果。本文的主要工作如下： 1 、首先综合分析了适应性查询处理研究现状和发展趋势，介绍了 m e d ia _ t 0 泐p e r 集成系统体系结构，针对数据集成系统查询处理过程的特点设 计了一个查询优化器，该优化器具有支持系统进行动态查询优化的能力，可以有 效提高系统的查询处理性能。 2 、提出自适应性遗传算法一种基于遗传算法的多数据源连接查询优化 问题的方法以及与此相适应的交叉变异概率、编码方法、交叉算予和变异算子。 该算法适用子集成系统中具有约束模式的数据源。我们将遗传算法与数据源的约 束模式有效地结合起来，将查询优化分成两个阶段进行，第一阶段利用数据源的 查询处理能力划分搜索空间，第二阶段利用第一阶段的结果作为启发式信息，采 用遗传算法寻找最优解或次优解。该方法不仅可用于左深度树搜索空间，同样适 用于混合搜索空间。同时还引入了n c j g h b o r 结构以解决传统遗传算法局部收敛 速度慢的缺点，有效的缩短了计算时间，提高了系统的查询效率。 本文将在接下来的第2 章介绍本文的技术基础：数据集成系统中的 m e d l a t o r w r a p p e r 系统体系结构和查询处理讨程，设计了一个查询优化器；第3 章将介绍多数据源连接查询优化存在的问题，给出了遗传算法的流程；第4 章详 细介绍自适应遗传算法以及与此相适应的交叉变异概率、编码方法、交叉算子和 变异算子；第5 章给出仿真试验结果；第6 章绪论和未来的研究方向。 6 河海大学硕士研究生毕业论文 自适应查询处理技术研究 第2 章数据集成中查询处理介绍 介绍了m e d i a t o r w r a p p e r 集成系统体系结构，针对数据集成系统查询处理过 程的特点设计了一个查询优化器，该优化器具有支持系统进行动态查询优化的能 力，可以有效提高系统的查询处理性能。 2 1 m e d i a t o r w r a p p e r 系统体系结构 随着i n t e r n e t 和w w w 的迅速发展，数据集成系统除了集成存储在数据库中 的结构化信息，还要集成w e b 数据源中的半结构和非结构化信息，基于传统模 式集成的多数据库系统己不适用于这种新的要求。目前的大多数数据集成系统通 过对异构数据源封装，形成了m e d i a t o r w r a p p e r 数据集成系统，参见图2 1 ，通 过在中介( m e d i a t o r s ) 乘l 包装器( w r a p p c r s ) 之间分割任务，提高查询处理的并发性， 减少响应时间。包装器对数据源进行封装，将其数据模型转换成为系统采用的公 共模型，作为其输出模式，并提供一致的物理访问机制。中介负责全局查询处理、 分解和优化，它通过调用包装器或其它中介来集成数据源中的信息，解决数据冗 余和不一致性，提供一致协调的视图和统一的查询语言。 图2 1 m e d i a t o r w r a p p e r 系统体系结构 用户 河海大学硕士研究生毕业论文 自适应查询处理技术研究 2 2 数据集成系统中的查询处理过程 基于m e d i a t o r w r a p p e r 体系结构的数据集成系统为用户和全局应用提供了中 间模式0 订e d i a t e ds c h e m a ) ，其目的是支持用户对多个自治的、分布的和异构的数 据源进行查询。为此，m e d i a t o r 必须具有查询分解，综合查询结果等能力。其查 询处理过程参见图2 2 。 m e d i a t o r 查询重写模块 查询处理模块 查询语句 数据源选择 _ l 查询优化 查询结果 查询重写 查询执行 2 2 1 数据源 图2 2 数据集成系统中的查询处理过程 数据集成系统中的数据源包括各种类型的数据库( 如关系数据库，面向对象 数据库等等) ，电子邮件，h t m l 和x m l 文档以及普通文件等结构化、半结构 化和非结构化信息。各种数据源都有其自身的特点，除数据模型不同外，有些数 据源没有一个稳定的模式，有些数据源还包含一些半结构化和非结构化数据，例 如图像等。此外，还有些数据源包含自描述的数据，如h t m l 和x m l 文档，文 献【1 3 】统称这些数据源为没有预知模式的数据源。 不同的数据源之间存在着语义匹配问题，相同的实体( e n t i t y ) 在不同数据源 中可能有不同的表示方法，不同的实体在不同的数据源又可能有相同的表示方 河海大学硕士研究生毕业论文 自适应查询处理技术研究 法，如何判定两个实体是否相同，大多数数据集成系统采取了一种比较直接和简 单的方法，即定义一个公共数据模型( c d m ：c o m m o n d a t am o d e l ) ，并规定c d m 到各局部数据源的数据模型之间的转换，由于x m l 的出现以及其具有的特性， 给数据集成系统注入了新的解决思路，许多研究者纷纷提出了面向x m l 的 c d m 。 2 2 2 语义匹配 在数据集成系统中，m e d i a t o r 为用户和全局应用提供了统一的中间模式，并 且还规定了中间模式到各数据源之间的语义匹配，目前主要有两种实现方法，均 采用了一阶逻辑语句的形式，将中间模式( 数据源模式) 定义成数据源模式( 中介模 式) 上的视图：g a v ( g l o b a l a sv i e w ) 和l a v ( l o c a la s v i e w ) 。 两种集成方法各有利弊，g a v 方法在查询重写阶段比较简单，可以根据中 间模式的视图定义将查询语句展开，其缺点是如果增加新的数据源，则需要重新 定义视图。l a v 方法是目前大多数数据集成系统采用的方法，l a v 在查询重写 阶段较为复杂，需要在每次查询的时候根据视图计算出相应的查询规划，但是该 方法比较灵活，增加，删除和修改数据源中的信息只增删修改相应的数据源模型， 因此特别适用于i n t e m e t 上的动态环境。针对w e b 上不规则的数据结构可采用 l a v 和g a v 相结合的方法。 2 2 3 查询重写 查询重写模块根据用户提交的查询语旬以及语义匹配方式选择参与查询的 数据源。目前对查询重写算法及查询重写阶段的优化方法研究的人比较多，如 f l o r e s c u 等人定义了数据源中信息冗余的推理模型，采用概率形式描述了在已知 数据源s 1 包含数据d 的情况下，数据源s 2 包含数据d 的概率，该推理模型可 以作为查询重写模块选择参与查询的数据源的依据1 1 4 】。l e v y 等人在i n f o r m a t i o n m a n i f o l d 系统中根据数据源的查询处理能力采用了b u c k e t 查询分解算法1 1 5 】： d u s c h k a 等人在i n f o m a s t e r 系统中采用t 删l j ( i n v e r s e r u l e s ) f r 燃。p o t t i n g e t 在上述两种分解算法的基础上提出了m i n i c o n 算法，以解决前两种算法存在的 9 河海大学硕士研究生毕业论文 自适应查询处理技术研究 缺陷【1 6 1 。 2 2 4 查询处理与优化 查询处理模块对查询重写产生的查询规划进行优化并将查询语句分配给各 个数据源的w r a p p e r 来提取数据，基于代价的查询优化主要涉及到三方面的工 作：首先，设计一个查询规划( q e p ) 表示模型m ，任意一个查询q 可以用模型m 中若干等价的规划表示，每个规划就是一个操作树，其非叶子节点为查询操作符 及相应的执行算法，叶子节点为关系或分片及访问它们的方法，这些等价的规划 构成了查询q 的规划搜索空间s ；其次，设计一个代价模型c m ，为模型m 中 的任意一个规划计算一个代价指标c o s t ( q e p ) ，与集中式查询优化不同，数据集 成系统中c m 必须同时考虑节点之间的通讯代价以及可以利用的并行机制，在两 者之间进行权衡；最后，给出高效的搜索策略，从s 中搜索出一个规划p 咄来执 行，该规划满足条件；c o s t ( p l i n ) = m i n p 。s i c o s t f p ) ，对于数据集成系统，由于它 集成了w e b 上大量数据源，查询执行规划的搜索空间会异常庞大，采用穷尽搜 索方法是不现实的，必须采用适当的方法对搜索空间的规模进行限制，尽量排除 不可能优化的查询规划，如结合启发式知识的搜索算法，有关各种搜索算法，我 们将在后面进行详细讨论。此外，由于集成的数据源分散在i n t e r a c t 上，对数据 源的查询请求往往会由于网络中断，网络堵塞或数据源自身负载等原因而得不到 即时响应，因此，数据集成系统中的查询重写和查询处理模块对这些环境变化应 该能够做出快速反应，及时将查询语句分配给其它具有相关内容的数据源执行， 参与查询的数据源也能根据其本身的负载情况来转移查询任务。 2 2 5 查询优化器 综上所述，在数据集成环境下，全局查询处理分成4 个执行步骤：首先把 定义在中介模式上的查询q 分解成为局部数据源上的等价查询q ；其次将q ， 转换成包含多个局部查询请求的查询执行规划q e p 并进行优化：接着将局部查询 请求传递给多个数据源执行查询请求；最后将结果进行合并处理后返回给提交查 询的用户。针对数据集成系统的特性，可以设计一个查询优化器，其体系结构模 型如图2 3 所示。其中主要组成部分的功能描述如下： 】0 河海大学硕士研究生毕业论文 自适应查询处理技术研究 查询转换器：负责将分解后的q 转换成查询单元( q u e r yu n i t ) ，每个查询单元 对应于查询处理的一个基本操作，并构建查询单元图。 规划器：在查询单元图的基础上，生成q e p 空间。根据统计信息和元数据管 理器中的信息，采用适当的搜索算法找出代价最小的规划p ，交给查询调度器负 责执行。 执行监控器：负责监控子查询的执行过程，收集相关的统计信息( 包括子查询 类型，参与查询的数据源成员，实际完成子查询的时间等) 提交给统计信息管理 器。如果查询响应时间明显大于预期响应时闻，执行监控器刚通知规划器和查询 调度器，对查询未完成的部分进行重新规划。在查询优化器中增加执行监控的功 能，是为了充分考虑到集成数据源的自治性，增强查询优化器的动态优化能力。 元数据管理器：存储与查询规划，代价计算等操作相关的全局信息，包括查 询所牵涉到的数据的存储位置，数据源的访问权限、负载特性和计算能力，以及 各数据源与子查询代价计算相关的统计信息。元数据管理器负责维护这些统计信 息，在全局查询处理结束后，根据统计信息管理器提交的内容对全局数据进行修 改，增加和删除。 杳询优化器+ 查询转换器 理器管ll 1 规划器lh i l 1 j ll 一i 调度器l ， 土 _ j 篓计信息h 执行监控器卜_ l 管理器l 图2 3 查询优化器的体系结构模型 1 1 河海大学预士研究生毕业论文自适应查询处理技术研究 第3 章遗传算法 w e b 上的新环境使得多数据源的连接查询处理和优化需要考虑许多新的因 素。本章详细分析了求解多数据源连接查询优化存在的问题，给出遗传算法的流 程。 3 1 引言 查询是指根据丰富的语义信息在有效数据组织模式下找出更准确的信息。如 何有效处理和优化用户的查询语句，缩短查询响应时间，减少查询代价是查询处 理中一个备受关注的课题。在多数据库集成系统中己有许多查询处理和优化方法 如：分解查询，代数表达式的等价变换，执行次序、执行结点以及连接方法的选 择。这些方法在数据集成系统中同样适用。但是n t c r n c t 上的新环境使得多数据 源的处理和优化需要考虑以下因素： 1 、参与查询的数据源较多数据量较大，并且多个数据源之间存在数据冗余； 2 、数据源在各数据源之间的传输需要网络代价并且由于网络环境不稳定等 因素，各数据源之间的连接会出现中断； 3 、各种数据源的查询处理能力差别较大，数据集成系统中的数据源各种各 样，从简单的文件系统，电子表格到功能强大的关系型数据库以及面向对象数据 库，每个数据源对查询处理，支持的查询模式都有其本身的特殊限制。 针对因素1 ，许多研究工作倾向于采用随机算法来处理和优化大规模的查询 语句，主要针对多连接操作的优化。如文献 1 7 1 采用结合启发式信息( 避免笛卡儿 乘积) 的遗传算法来优化多连接查询，将优化问题变成了一个带约束的组合优化 问题。文献【1 8 】把查询处理和优化看成是人工智能领域的规划问题，提出了基于 重写的规划方法p b r ( p l a n n i n g b y r e w r i t i n g ) ，首先快速产生一个初始规划，然后 应用一组重写规则反复转换和优化当前规划，直到满足性能要求，该方法采用了 局部搜索方法一梯度下降法来寻找最优解。 河海大学硕士研究生毕业论文 自适应查询处理技术研究 针对因素2 的研究工作主要有s a d a l i 等人提出的基于智能缓存和代价估计 的查询优化技术 i 9 】，智能缓存指的是对于某些特殊的查询( 如用户经常提交的查 询，或查询代价较高的奁询) ，数据集成系统中的m e d i a t o r 可以在本地缓存查询 结果以提高以后的查询效率，并根据以前查询结果的统计进行代价估计。a s h i s h 等人根据对用户查询语句的模式匹配来有选择性的物化视图。【2 0 , 2 i 等文献研究 了x m l 数据查询语义重写问题，其目的都是尽量减少对数据源的频繁访问，缩 短查询响应时间，提高查询效率。 针对因素3 ，目前有两种方案，一种方案是利用包装器( w r a p p e r ) 实现数据源 未提供的查询处理能力，对于查询处理能力很弱的数据源( 弱数据源) 来说， w r a p p e r 的设计非常复杂；另一种方案是仅向各数据源发送它们均能完成的查询， 其余查询由集成系统中的中介来完成。如果各数据源的查询处理能力相差较大， 均能完成的查询往往只是一些简单查询，则查询的大部分工作由中介完成，一方 面不能充分利用功能强大数据源的查询处理能力，另一方面造成中介的负担过 重，影响查询效率。 目前一些大学和研究机构对弱数据源问题进行了研究，如t s i m m i s 系统采 用了说明法( d e c l a r a t i v ea p p f o a c h ) ，利用预先给出的说明寻找全局查询中各数据 源支持的查询语句。i b m 公司的g a r l i c 系统采用了封装法( e n c a p s u l a t i o n a p p r o a c h ) ，由w r a p p e r 封装各数据源的查询处理能力。这两种方法各有其不足之 处，说明法的缺点是很难用统一的语言描述各种数据源的查询处理能力以及各数 据源对查询处理的特殊限制，封装法虽然不受具体描述语言表达能力的限制，但 是加重了w r a p p e r 的负担。文献【2 2 将说明法和封装法结合起来，提出了一种复 合法，复合法利用说明法简单说明数据源的基本查询处理能力，而各数据源对查 询处理的特殊限制则采用封装法，因此，复合法既不局限于具体描述语言的表达 能力，又减轻了w r a p p e r 的负担，在一定程度上弥补了说明法和封装法的不足。 河海大学硕士研究生毕业论文自适应查询处理技术研究 本章在深入研究数据库系统中查询优化器工作机理的基础上，针对上述的数 据集成系统中需要考虑的因素1 和因素3 ，首先利用数据源的查询处理能力划分 搜索空间，其次采用结合启发式的遗传算法来寻找最优执行规划或次优解。从而 使得用户在进行全局查询时，数据集成系统能够以最优的效率和最短的时间来实 现用户的查询请求。 本章组织如下：3 2 节介绍数据库系统中查询处理和优化的基本工作原理； 3 3 节给出数据集成系统中查询处理和优化问题的描述及提出该问题的实际背景 和重要意义；3 4 节介绍了遗传算法的组成要素和基本流程。 3 2 查询处理和优化的基本原理 在关系数据库中，一个查询可以等效地用一个关系代数表达式表示，利用代 数表达式的等价变换可以简化查询，因此关系代数表达式及其等价变换是查询处 理的常用方法。关系代数表达式通常采用语法树来表示，称为查询树，树中的叶 结点表示表达式中的关系，除叶结点以外的其它结点为表达式的运算符，子结点 运算结果关系为父结点运算的操作数。 查询优化是查询处理中研究的主要问题，在集中式数据库中，查询优化主要 考虑i o 和c - p u 时问，其目的是降低i o 次数。在数据集成系统中，一个查询 涉及到多个数据源，需要在不同数据源之间传输数据，查询代价除考虑, o 和 c p u 代价外还有通信代价t = c o + x + c l ，c o 为两个数据源启动一次数据传输所需 要的时间，在确定的系统中一般是一个固定值，x 为传输数据量，传输系数c 1 为单位数据传输所需要的时间。由于在n t e m e t 环境中，通信代价较大，因而减 小通信代价是数据集成系统中主要考虑的问题。在计算查询代价的时候，需要估 计关系的大小，属性值的频率分布，索引以及查询结果，这些估计值的精确程度 决定了查询代价的准确性，传统的查询优化器在估计结果大小及分布的时候，通 常假设关系中的属性是相互独立的，这在现实中通常是不成立的。目前研究人员 提出了多种技术用来估计结果的大小和频率分布，其中，最为常用的是直方图法， 例如等宽直方图，等高直方图以及边缘有偏直方图，其中边缘有偏直方图在优化 1 4 河海大学硕士研究生毕业论文 自适应查询处理技术研究 性能和实用性两者之间做了较好的折中，此外，文献【2 3 】提出了一种基于小波的 直方图方法，在考虑多属性相互关联的情况下，取得了较为准确的估算结果。 查询优化器通常需要采用某种搜索算法来寻找代价最小的查询执行规划，给 定查询q ，其可能的查询执行规戈i j ( o e p ) 空间( 即搜索空间) 为s ，对于其中的 q e p s 。s ，都有一个执行代价c o s t ( s ) ，优化器需要在搜索空间里查找代价最小的 q e p ，即采用某种算法，找到s o ，使得等式e o s t ( s o ) = m i n s e s c o s t ( s ) 成立。目前 经常采用的搜索算法主要有动态规划法( d 固，随机算法( 吣以及遗传算法( g a ) 和遗传编程( g p ) ，s a 包括模拟退火法( s s i m u l a t e da t m e a t i n g ) ，迭代改进法a i ： i t e r a t i v ei m p r o v e m e n t ) , 以及两阶段优化法, ( 2 p o ：t w op h a s eo p t i m i z a t i o n ) ，2 p o 将 i l 和s a 两种随机算法相结合，第一阶段采用方法举行局部优化，找到局部最 小点，作为第二阶段s a 的起始点，s a 以一定的概率执行爬山动作，以跳出局 部最小点，继续搜索最优解。 此外，研究人员还提出了多种搜索算法【2 4 】，如i b a r a k i 和k a m e d a 针对嵌套 循环连接方法( n e s t l o o p j o r e ) ，提出了一个复杂度为o ( n 2 l o g n ) 的优化算法，k b z 算法采用了类似的技术，其算法复杂度为0 0 崎2 ) ；a b 算法采用k b z 算法作为其 子程序，对于随机产生的查询图的子图执行该子程序0 ( n 2 ) 次，其时间复杂度为 0 ( 印) ；在人工智能领域广泛研究的a 启发式算法，可以被视为d p 算法的扩展， 它采用启发式信息，搜索到最优查询执行规划的速度要快于d p 法。 河海大学硕士研究生毕业论文 自适应查询处理技术研究 3 3 多数据源连接查询优化问题 3 3 1 问题的提出 w e b 上大量的数据源即使通过w r a p p e r 包装成关系型数据库，出于以下两个 原因往往只能提供有限的查询处理能力：数据源是文件系统或其原有的访问界面 只允许用户进行有限的操作；从系统安全保密或运行性能等方面考虑，系统仅向 外界提供有限信息。此外，许多基于连通有向图的半结构数据模型，通常只允许 前向路径搜索，而不提供扫描图中的所有对象以及后向路径搜索等操作。在上述 两种情况下，数据源的有限查询处理能力都可以采用约束模式( b 证d 协g p a t t e i n ) 来 描述。约束模式b ，f 规定了访问数据源时必须提供哪些属性的值。 给定数据源的约束模式，文献【2 5 】给出了一种基于数据源查询处理能力的查 询分解算法，将用户在中介模式上提交的全局查询分解成对局部数据源的可执行 子查询语句集合，文献 2 6 】称该子查询集合为逻辑查询规划( l q p ：l o c a lq u e r y p l a n ) ，l q p 与源查询语句在语义上是等价的。如果采用l a v 方法集成数据源， 则查询分解本质上类似于传统数据库中利用物化视图来响应查询的方法。即使通 过查询分解算法能够得到参与查询的最小数据源集合，由于数据源可具有多种访 问方式以及各操作之间连接顺序的不同，也存在多个代价不同的物理查询执行规 划( p q e p ：p h y s i c a lq u e r ye x e c u t i o np l a n ) 。在数据集成系统查询处理和优化过程中， 我们需要解决问题是：给定一个逻辑查询规划以及各数据源的约束模式，寻找代 价最小的有效物理查询执行规划。 3 3 2 问题定义 定义3 1 查询表达式：采用d a t a , l o g 规则来定义查询表达式。规则包括规则 头和规则体，规则头描述查询结果，规则体描述数据源应该满足的条件，其形式 为q ( 均：一e 1 ( x - ) ，e 。( ) ( n ) ，其中e 1 ( x 1 ) 。e 。( ) ( n ) 称为查询子目标，q ( 蜀为查 询结果。x ，x 1 x n 为查询表达式中的变量集合，如果x c - x 1 ux 2 u ux n ， 则称上述d a t a l o g 查询定义是安全的。c n t = x j i c j i x ic x l u x 2 u ux n ，其 中c i 为常量，c n t 中的 x i ) 称为约束变量集合，记为b i n d ( c n t ) 。 1 6 河海大学硕士研究生毕业论文 自适应查询处理技术研究 定义3 2 逻辑查询规：2 f j ( l q p ) ：l q p 表达形式为：p ( 砷：一s , ( u 0 ，s 。( u 。) ， 其中s i 为数据源d s i 中的关系，u i 为包含常量和变量的元组。s 1 ( u 1 ) ，s 即n ) 称为数据源查询子目标。元组x 与q ( x ) 中的x 相对应。如果p ( x ) c - q ( x ) ，则 称该l q p 为可行l o p 。 定义3 3 物理查询执行规划( p q e p ) ：p q e p 可以表示成为一个连接操作树， 其叶子节点为数据源中的关系，中间节点为操作运算符，图中的边表示数据流向。 所有的连接操作树构成了搜索空问。如果在q e p 的每个节点上标注 ，则称该q e p 为带标注q e p ，其中c o r 0 ( n ) 为在节点n 处执行 的查询操作，a d o r n ( n ) 将查询变量映射成 中的一种约束状态。 根据操作树中间节点的子节点是否至少有一个是叶子节点，可以将连接操作 树划分为线性树( 左深度树：l e f t d e e pt r e e 或右深度树：r i g h t d e e pt r e e ) 汞l l 浓密树 ( b u s h t r e c 、。 定义3 4 代价模型( c m ：c o s tm o d e l ) ：在数据集成系统中，查询代价表达式 通常可以表示为c o s t = c m + c 冉c w ，称为执行查询的代价模型c m ，c k 为m e d i a t o r a g e n t 分解查询及初始化子查询的代价；c t 为查询中间结果集的网络传输代价， c t 的大小取决于数据的单位传输代价以及数据传输量； c w 为w r a p p e r 及其所 包装数据源的局部查询处理代价。针对不同的应用环境，可以采用侧重点不同或 简化的代价模型。 定义3 5 多数据源连接查询优化问题：给定全局连接查询q ( x 1 ，经m a 查询 分解得到l q p ，在l o p 的基础上，查询优化器生成物理查询执行规划p q e p 。 如果一个p q e p 包含了l q p 中所有予查询语句，且其叶子节点处的a d o r n ( n ) 与 b i n d ( c n 0 相匹配，则称该p q e p 为有效p q e p 。在数据集