（计算机应用技术专业论文）基于agent的并行数据库查询优化.pdf

华中科技大学硕士学位论文 摘要 当前并行数据库系统的研究基本围绕着关系数据库进行，主要包括并行数据库 的物理组织、并行数据操作算法的设计与实现、并行数据库的查询优化处理等三个 领域。 并行数据操作算法，如基于嵌套循环的并行连接算法、基于s o r t - m e r g c 的并行 连接算法、基于h a s h 的并行连接算法等，很多人已经进行了研究与探讨。并行数据 库技术中的查询处理及优化方法，如基于左线形树的查询优化算法、基于右线性树 的查询优化算法、基于片段右线性树的查询优化方法、基于浓密树的查询优化算法、 基于操作森林的查询优化算法等都各有优劣；作者提出了一种基于m u m 赴e n t 技术 的语义查询模型( s q m a s ) ，并以此模型为基础建立了一种基于a 粤e n t 的并行数据库 语义查询方法，同时为了保证系统组内、组间a g e n t 之间的高效通信，建立了树型 拓扑结构a s ) 的通信模型，系统内各a g e n t 使用通信原语高效通信、协作，从 而在并行数据库技术的查询优化领域做出了有益的探索和贡献。 语义查询优化方法不是简单摒弃传统的查询优化方法，而是采用m u n i a g e n t 技 术自动查找与给定查询有关的完整性约束条件，然后，修改给定的查询为更有效的 等价查询，使得多个关系间连接操作的效率得到很大的提高，从而达到查询所期望 达到的减少连接操作、缩短查询时间的优化效果，实现了基于a g c n t 的语义查询优 化。 s q m a s 查询模型基于多触e n t 技术，结构组成中包括查询监测组 ( q l l e r y d e t e c t g r o u p ) 、内核组( k e r n e l g r o u p ) 、知识库组和规则集组( i ( d 嗽u l e s e t g r o u p ) 、 输出组( e x p o r t g r o u p ) 、系统级命名服务a g e n t ( n a i i l e s e r v e r _ 蟾e n t ) 、辅助通信 旭e n t ( a s s c 0 n 那u k e n t ，含组内通信门户g g a ，系统通信门户m a s g a ) 等功能组和系统 a g e n t ；另外，为了保证查找效率，设计了一个基于“黑板”模型的树型拓扑通信模 型t t m a s ，使用通信原语实现了s q m a s 系统组内a g e m 以及不同组间a g e t 的单 播、多播、选播、广播通信，且满足a g e n t 间的通信路由最优，从而保证了s q m a s 的查询效率。 关键词： 并行数据库，查询优化，归结原理，a g e n t ，s o m a s ，t t m a s 华中科技大学硕士学位论文 a b s t l a c t c u n e n tr e s e a r c ho nt h ed a t a b 鹤es y s t e mb a s i c a l l ya m u n dw e a r t h er e l a t i o nd a t a b a s e ， i tm a j l l l yi n d u d e st h r c er e a l m s ：p h y s j c a lo r g 粕i z a t i o n s0 fp a r a l l e l 出i t a 由鲳e ，p 盯a l l e ld a t a m a i l i p u l a t i o na 1 9 0 r i t h l n sd e s i g na l l dr c a l i z a t i o n ，q u e f yo p t i m i z a l i o np f o c e s s i n go fp a m l l e l d a t a b a s e m a n yp e o p l ch 酷a l r c a d yc a i e do nt i l ef e s e a r c ha n ds t u d yo nt h ep a r a l l e lo p e r a t i o n a l g c 时t h mo ft l l ed a t a b a s es u c h 鹬b 鹪e do nt h en e s t i n gc i r c u l a t i o np 盯a l l e lc o n n e c t i o n a l g 嘣m m ，b a s e do nt h es o n - m e r g ep a f a l l e lc o n n e c t i o nd 1 9 0 f i t h m ，b 懿e do nt h eh 硒h p a r a l l e lc o n n e c t i o na l g o r i t h m ，a i l ds oo n t h eq u e f yp r o c e s s i n g 锄do p t i m i z a t i o nm e t h o d s i np a f a l l e ld a t a b a s et e c h n o l o g y ，s u c h 觞t r e e st l l eq u e r yo p t i m i z a t i a l 酬t l l mb a s e do n l e f t d e 印仃e e s b a s e do nr i g l l t _ d e 印t r e e s ，b a s e do n 加g m e n tt y p er i g l l t - d e e p 仃e e s ，b a s e d o nb u s h yt f e e s ，b a s e do no p 盯a t i o n a lf o r e s ta n ds oo n ，a l lh a v et h e i rm c r i t sa n d s h o n c o m i i l g s ；t l l e nt h ea u t h o ro p e nan c wm a df o rh e r s e 域p r o p o s e d 仰e1 【i n ds e m 粕t i c q u e r ym o d e lb a s e do nm u l t i - a g e mt e d l n o l o g y ( s q m a s ) ，a n dt a l 【i n gt l l i sm o d e l 鹤t h e f o u n d a t i o n ，h eh a se s t a b l i s h e do n el 【i n dp 盯a n e ld a t a b a s es e m 锄t i c sq u e r ym e t h o db a s e d o nt h ea g c n t ，a i l dt oe n s u r et h eh i g he f f i c i e n c yo fc o m m 吼i c a t j o n sb e 呐e 明t i l ea g e n t so f t h cs y s t e m sg r o u p s h eh a sa l s oe s t a b l i s h c dac o m m u n i c a t i o nm o d e lb yn e et o p o l o g y m u l t i a g e n ts y s t e m ( m a s ) ，e v e r ya g e n t i i lt h i ss y s t e mc o m m u n i c a t e sa n d l la _ b o r a t e s a th i g l le f f i c i e n tb yu s i n gc o m m u n i t i p r i m i t i v e ，t h u sh eh a sm a d et h eb c n e f i d a l e x p l o r a t i 咖a i i dt h ec o n t f i b u t i o nt om ep a r a l l e ld a t a b a s eq u e r yo p t i i n i z a t i o nt e c h n o l o g y d o m a i n 1 1 l es e m a n t i cq u e r yo p t i m i z a t i o nm e t h o dj sn o ts i m p l ya b a i l d o n st 量l e 打a d i t j o n a lq u c r y 叩l i m i z a t i o nm e t h o d ，b u ti su s i n gt h et h e o r e ma u t o m a t i cp r o o ft e c h n o l o g yi n l h ea l d o m a i n ， u s i f l gt h er e s o l u t i o np r i n c i p l e t os e a r c ha u t o m a t i c a l l yi n t e 孕i t yc o n s t r a j n t c o n d j t i o nc o m ew i t ht h ea s s i g n e dq u e f yr e l a t e d ，t h e n ，m o d i f y i n gt h e 百v e nq u e r yt om o r e e i c c t i v ee q u i v a l e n c eo n e s ，t h u so b t a i n i n gam o r ee f f e c t i v eq u e r ye x e 饥t i o ns t r a t c g y t h es q m a sm o d e lb a s e do nt h em u l t i a g c n tt e c h n o l o g y ，i n d u d i n gt h eq u e r y d e t e c t i n gg r o u p ( q u e r y d e t e c t g m u p ) ，t h ek e m e lg r o u p ( k c m e l g f o u p ) ，t l l ek n o w l e d g e l l 华中科技大学硕士学位论文 b a s e 蛐dr u l e ss e tg r o u p ( k d b r u l e s e t g m u p ) ，t h ee x p o r tg r o u p 但x p o n g r o u p ) ，t h e s y s t e m l e v e ln a m i n gs e n r i c e sa g e t 吖锄e s e n r e r _ a g e n t ) ，a s s o c i a t ec o m m u n i c a t i o n a g e n t ( 触s c o m m u a g e n t ，i n d u d i i l gt h eg r o u pc o m m u l l i c a t i o n sg a t e w a ya g e n t ( g g a ) ， t h em a sc o m m u i l i c a t i o ng a t e w a ya g e t ( m a s g a ) ) a n ds o0 nf u n c t i o n a lg r o u p s 趾d s y s t e m - l e v e la g c n t ；f i l n h e 珊o r c ，t oe 璐u r et h ee f f i c i c yo fs e a r c h ，a1 1 r e et o p o l o g y m u l t i - a g c n ts y s t 啪( 明m a s ) b a s e do nt h e ”b l a c k b o a r d ”m o d e lh 龉b e e nd e s i 鲫e d ，i t f i t s m o s t l yt h e 啪m u n i c a t i o nb e t w e c na l la g e n t s ，r e a l i z e st h ec o m m l l l l i c a t i o n so f u n i c a s t ，m u l t i c 硒t 铀y c a s t ，b r o a d c a s tb e t w e e nt l l ea g e n t s0 f as 卿eg r o u po rd i f i = ；e r l 铲o u p si n t h es q m a sb yu s i n gc o m m u n i c a t i o np r i m i t i v e ，t h e r c b ye n s u r i n gt h eq u e r y e f f i c i e n c yi ns q m a s k e y w o r d s ：t h ep a r a l l e ld a t a b a s e ，t h eq u c r yo p t j m i z a t i o n ，t l i er c s o l u t i o np r i n c i p l e ，a g e n t ， s o m 协s ，t n 订a s i l l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知。除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：j ! ； 谚年 日期：加。年步月易日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论丈的规定。即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在 年解密后适用本授权书。 本论文属于 不保密区 ( 请在以上方框内打“”) 指导教师签名： 日期6 年9 柘十、 务日 诸嘭：矿 鹳 年 者，b 倍 文 0 墓； 瓤 挚 日 华中科技大学硕士学位论文 1 1 本课题研究的背景 1 绪论 并行数据库系统( p a r a 儿e 1r e l a t i o n a ld a t a b a s es y s t e m ) 的研究可以追溯到 数据库机器“1 的研究，数据库机器试图通过减少软件的复杂性来提高系统的效率和可 靠性，通过增加专用硬件的并行性和处理能力来改善数据库系统的性能。遗憾的是， 数据库机器没有取得成功。 但是，随着通用并行计算机系统的出现，并行数据库管理系统的研究取得了引 人注目的进展。几个并行数据库原型系统己经成功地运行在通用并行计算机上，并 行数据库系统已经成为并行计算机的主要应用之一。很多研究者认为，在具有数千 个处理机的并行计算机上建立高性能数据库系统是可行的。1 。 进入2 0 世纪9 0 年代以来，由于微处理技术和网络的高速发展，以高性能的大规 模并行处理机m p p ( m a s s i v ep a r a l l e lp r o c e s s i n g ) 为代表的并行计算机结构受到了 越来越普遍的重视，例如出现了p a r a g o n ，c m 2 ，c m 5 等著名的并行处理系统，并且由 于高速通信网络技术和操作系统的进展，基于网络的多计算机集群并行计算环境开 始出现，如m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) ，p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 等 系统。但相应的软件系统的发展远远落后于硬件系统的发展，这在数据库技术应用 领域中体现得更加明显。随着基于网络的多计算机机群并行计算环境，如p v m ，m p i 等系统的出现。使得在m p p 基础上建立并行数据库系统成为可能。为满足日益扩大的 应用需求，人们己在并行数据库系统方面开展了大量的研究，主要包括三个方面：数 据是如何在多节点中存储分布的，如何利用多机和多i o 设备设计出高效的并行操作 算法，如何对查询处理操作进行优化以获取最快的响应速度。 并行数据库系统也引起了学术界”3 和工业界的密切关注，许多著名的国际学术会 议和学术刊物( 如v l d b ，a c ms i g m o d ，i e e ed a t ae n g i n e e r i n g ) 都开设了并行数据库 系统专题。大量的研究工作者做了不少的研究工作，并开发出了许多著名的原型系 统，国外比较著名的有美国威斯康新大学在2 0 世纪8 0 年代开发的著名的并行数据库 系统原型系统g a 唧a 系统“1 ，该系统基于s n ( s h a r e dn o t h i n g ) 体系结构，同时采用基 于h a s h 分布的并行算法实现复杂的关系操作，采用数据流调度技术执行查询，采用 华中科技大学硕士学位论文 水平分段技术对众多磁盘上的数据进行划分使得访问数据可以采用并行i 0 技术， 从而使得该系统得以支持数百个处理器互连；美国c ( m i c r o e l e c t r o n i c s a n d c o m p u t e rt e c h n o l o g yc o r p o r a t i o n ) 公司研制的一个基于s n 结构的并行数据库原型 系统b u b b a 系统。1 ，该系统具有模块化扩充的能力，提高了事务处理吞吐量，增强了 存储能力，具有高可靠性和高可用性，整个设计工程在设计、建模和原型化三个阶 段不断反复，是一个相当成功的性能价格比高的数据库原型系统；其它著名的并行 数据库系统还有加州b e r k l e y 大学的x p r s 系统汹，t a n d e m 数据库公司的n 0 n s t o p s q l 系 统。这些系统探讨了并行数据库理论和实现中的若干重要问题，为数据库的进一步 发展奠定了基础。此外，许多著名数据库厂商也纷纷推出相应的并行数据库系统。 0 r a c l e 公司推出的0 p s 并行服务器，i b m 公司推出的并行版本d b 2 等。华中理工大学自 主研制的p a r o 系统0 1 ，以及在“8 6 3 计划”的资助下，中国人民大学数据和知识工程 研究所研制和开发的并行数据库系统p 队se 8 。p b a s e 1 是s m ( s h a r e dm e m o r y ) 结构的 并行数据库原型系统：p b a s e 2 是s n ( s h a r e dn o t h i n g ) 结构的。p b a s e 2 系统立足于理 论研究和技术攻关，并以我国的曙光并行系列机为基础，是自主研制的实用化的并 行数据库管理系统。p b a s e 2 系统可以实现事务间并行、操作间独立并行、操作间流 水线并行、操作内并行等多种粒度的并行性，达到并行数据库管理系统所追求的高 事务吞吐量和低响应时间的目标。 当前并行数据库系统的研究基本围绕着关系数据库进行，主要包括以下三个领 域： 1 并行数据库的物理组织数据库中数据的划分及其在多处理器或多磁盘之间 的分布； 2 并行数据操作算法的设计与实现； 3 并行数据库的查询优化处理。 这三个领域中的问题是并行数据库系统的关键问题，也是建立并行数据库系统 的重要基础。并行数据库的物理存储结构可以分为三类9 3 ：第一类是一维数据划分方 法，第二类是多维数据划分方法，包括c m d 方法，b e r d 方法等，第三类是传统数据结 构的并行化，包括二种栅格g r i d 文件和并行b 树。 并行数据库查询优化问题与传统数据库查询优化问题( 关系数据模型由于存取 路径对用户透明，查询效率往往不如非关系数据模型，因此为了提高性能，必须对 用户的查询请求进行优化) 不同。在传统数据库系统中，给定一个查询q ，查询优化 2 华中科技大学硕士学位论文 算法只需找到q 的一个具有最小工作量的执行计划( q e p ) ，这样的计划必然具有最 快的响应时间。这是因为在具有单处理机的计算机系统中，一个计算任务的响应时 间与这个任务的工作量成正比。在并行数据库系统中，情况就不同了。q 的具有最小 工作量的执行计划可能具有很强的固有顺序性，难以并行化。在并行数据库系统中， 查询优化的目标是寻找q 的具有最小响应时间的执行计划，执行计划( q e p ) 的工作 量不是最重要的。于是，在并行数据库系统中，我们需要新的查询处理算法和新的 查询优化技术。 1 2 国内外研究现状 查询优化不仅是顺序数据库系统的重要组成部分，也是并行数据库系统的重要 组成部分。目前，无论是在顺序数据库系统领域还是在并行数据库系统领域，查询 优化的研究主要围绕着具有多个j o i n 操作的复杂关系数据库查询( 简称m j 查询) 的 优化问题进行。并行数据库查询优化的研究分为两个方面：查询执行计划( 简称q e p ) 模型和查询优化算法，查询优化算法与查询计划模型密切相关。下边我们按查询计 划模型分类介绍并行数据库查询优化方面的主要研究成果，首先介绍查询树模型。 1 9 9 0 ，s c h n e i d e r 等研究了查询树模型“，提出了左线性树( l e f t d e e pt r e e s ) 、 右线性树( r i g h t d e e pt r e s s ) 和浓密树( b u s h yt r e e s ) 的概念。一个m j 查询可以表 示为一个查询树g ：( v ，e ) ，其中，v 是结点集合，e 是边集合。每个叶子结点表示一 个关系，每个内结点表示一个j o i n 操作，同时表示这个j o i n 操作的结果关系，每 条边表示一个j o i n 操作，j o i n 谓词也可以由边来表示，显然，m j 查询的查询树是 一个二叉树。查询树可以分为三类：左线性树、右线性树和浓密树。左线性树是一 个特殊的查询树，每个内结点( 包括根结点) 的右子结点必须是一个j o i n 关系，左子 结点是一个内结点或一个j o i n 关系；右线性树也是一个特殊的查询树，每个内结点 ( 包括根结点) 的左子结点必须是一个j o i n 关系，右子结点是一个内结点或一个j o i n 关系；除了左线性树和右线性树以外的查询树皆称为浓密树。 1 2 1 基于左线性树的查询优化算法 文献“”给出了一种以左线性树和h a s 卜_ j o i n 算法为基础的m j 查询的优化方法， 以下简称l d t 方法。l d t 方法把两个j o i n 关系分为内关系和外关系，把h a s h j o i n 分为b u i l d 和p r o b e 两个基本操作，b u i l d 操作扫描内关系，建立h a s h 表；p r o b e 华中科技大学硕士学位论文 操作扫描外关系，搜索匹配h a s h 表，完成j o i n 操作。l d t 方法使用数据相关图的概 念模拟h a s h j o i n 的处理过程，确定左线性树的优化执行计划。图卜1 给出了具有 n 个j o i n 操作的砌查询的左线性树及其数据相关图，所指框必须在箭尾所连框之后 执行。给定m j 查询q ，q 的每个左线性树都包含唯一一个具有最高并行性的查询计 划，称为q 的左线性树优化并行查询计划。 图卜l 左线性树 图卜l 中的左线性树及其数据相关图给出的优化并行查询计划如下： 1 并行执行s 。，b 】 2 并行执行s ：，p 。，& 3 并行执行s 。，r ，b 3 n 并行执行s 。，r 。b 。 n + 1 并行执行：s 。p 。 使用文献 1 0 的方法，我们可以得到如下的m j 查询优化算法( 简称l d t 算法) ： 1 搜索给定m j 查询的左线性树空间，选择具有最小响应时间的优化左线性树t ； 2 由t 产生数据相关图d g ： 3 根据d g 产生优化并行查询执行计划p ； 4 运行优化并行查询计划p 。 l d t 算法存在3 个问题：( 1 ) 由于仅考虑了h a s h j o i n 算法和m j 查询的左线性树 查询计划，难以保证产生高效率的查询计划；( 2 ) 由于至多有两个j o i n 操作可以并 4 华中科技大学硕士学位论文 行执行，数据操作问的并行性得不到充分的发挥；( 3 ) 町查询的左线性树空间搜索算 法需要进一步研究。 1 9 9 2 年，g a n g u l y 等以左线性树为基础，提出了一种支持多种j o i n 算法的查询 优化方法“，研究了并行数据库查询优化的几个基本问题，提出了表示查询计划的 操作树概念，建立了以操作树为基础的两种并行查询计划复杂性模型：无资源竞争 的响应时间模型和有资源竞争的响应时间模型。 1 2 2 基于右线性树的查询优化算法 显然，由于m j 查询的左线性树优化并行查询计划最多只允许两个j o i n 操作并 行执行，这种方法不能充分发挥数据操作间的并行性。为此，s c h n e i d e r 等研究了基 于右线性树的m j 查询优化问题，给出了使用数据相关图概念确定右线性树豹优化执 行计划的方法。图卜2 给出了具有n 个j o i n 操作的m j 查询的右线性树表示及其数 据相关图。下面是相应的具有最高并行性的执行计划，称为右线性树优化并行查询 计划： 1 并行执行s 。，b 。，s 。，b 2 ，s 。儿，b n 2 s c a ns l ，p 1 ，p 2 ，p 。 使用文献 1 0 给出的方法，我们可以得到基于右线性树的查询优化算法( 简称 r d t 算法) 。r d t 算法类似于l d t 算法，r d t 算法产生的查询执行计划具有相当高的并 行性，所有n 个j o i n 操作皆可并行执行。一种方法称为静态右线性树调度方法，这 种方法首先使用优化程序或查询计划调度执行程序，把右线性树分成多个不相交的 可执行片段，使得每个片段的存储要求不超过可用的存储空间；然后，使用右线性 树和数据操作相关图方法为每个片段确定具有最高并行性的执行计划；最后，顺序 地执行各个片段。这种方法需要把每个片段的执行结果暂存到磁盘上，作为下一个 片段执行的输入。 另一种方法是一个动态自底向上的调度方法。它的基本思想是：令查询计划调 度执行程序动态地检查是否具有足够的存储空间并行执行多个j o i n 操作，保证在可 用的主存空间上并行执行尽可能多的j o i n 操作。 第三种方法的基本思想是：在b u i l d 阶段，每个j o i n 关系被分成两部分，一部 分进入内存，建立h a s h 表，另一部分留驻外存，待以后处理；在p r o b e 阶段，每个 j o i n 操作的结果也被分成两部分，一部分宜接用来进行下一个j o i n 操作的 华中科技大学硕士学位论文 图卜2 右线形树 p r o b e 处理，另一部分存入外存，待以后处理。 1 2 3 基于片段式右线性树的查询优化方法 对左线性树和右线性树查询计划的性能进行比较，我们可以发现，右线性树查 询计划优于左线性树查询计划。然而，右线性树查询计划仍然很受限制，除了要求 内存量大以外，还可能排斥很多具有更高性能的查询计划。在这方面，浓密树要比 右线性树优越，但对应的查询计划空间非常大，相应的优化算法的开销也相当大。 为了克服右线性树和浓密树的缺点，c h e n 等提出了一种界于右线性树和浓密树之间 的片段式右线性树( 简称s r d 树) 模型“，并以h a s h j o i n 为基础给出了基于s r d 树 的查询优化算法。s r d 树是一种特殊的浓密树，由一组右线性树连接而成，每个右线 性树张为一个片段，每个片段中的一个j o i n 操作称为一个阶段。 图卜3 给出了一个s r d 树的实例，图中的阴影结点( j 3 、j 。、j b ) 表示各片段的 根结点，未加标记的结点表示关系，j j 是第i 个j o i n 操作。c h e n 等给出了如下的 s r d 树调度执行策略：以片段为单位顺序执行，每个片段按右线性树的方式并行执行， 其结果作为下一个片段的输入关系，一个片段未结束之前，它的上一级片段( 即其根 结点所连接的片段) 不能执行。他们还提出了一种启发式优化s r d 树生成算法，基于 s r d 树的查询优化算法的效率高于前面介绍的算法，但是，它也不能保证产生高效率 的查询计划。 华中科技大学硕士学位论文 圈卜3 1 、s r d 树 1 2 4 基于浓密树的查询优化算法 1 9 9 1 年，h 等提出了基于浓密树f 1 3 】的m ，查询优化算法，他们把查询计划分为 同步和非同步两类。在同步查询计划中，一个m j 查询的处理过程划分为多个同步执 行阶段，各个同步执行阶段顺序执行。在每一同步执行阶段，多个j o i n 操作并行执 行，其它的查询计划称为非同步执行计划。文献f 1 3 】以同步执行计划为目标，提出了 三种产生优化同步执行计划的启发式m j 查询优化算法。第一个算法称为g p 算法， 是一种贪心算法。算法的核心是同步执行段的划分，这个算法循环地为每一同步执 行阶段选择尽量多的可并行执行的j o i n 操作。为了减少g p 算法的时问复杂性，他 们提出了另外两个启发式贪心算法。一个算法称为g p t ，它仅产生如下类型的计划： 只有第一同步执阶段并行执行多个j o i n ，其余同步执行段仅执行一个j o 玳操作。 另一个算法称为g p p ，它简化了g p 查询计划的代价模型，其余皆与g p 相同。以 上三种算法具有4 个问题，一是丢弃了同步执行阶段之间的流水线并行性；二是增 加了读写中间结果的“o 开销；三是由于同步的原因，某些较早完成j o i n 任务的处 理结点必须空闲等待，降低了处理结点的利用率：四是由于仅考虑了同步查询计划 并使用了可能排除高效查询计划的启发规则，难以保证产生高效率的查询计划。 1 2 5 基于操作森林的查询优化算法 李建中等提出了一个以操作森林为基础的s e l e c t p r o j e c t j o i n 查询( 简称s p j 查询) 的并行查询优化算法。1 ，这个算法比上面介绍的算法更具有一般性，因为它不 华中科技大学硕士学位论文 仪支持m j 查询也支持应用程序最经常使用的s p j 查询。s p j 查询的操作森林由多个 操作树组成，这里的操作树有一组操作集合构成，操作集合包括下列基本操作： s c a n ：扫描一个关系，对应于s e l e c t 、p r o j e c t 等数据再分布操作； s o r t ：对输入关系元组集合进行排序； h a s h ：由输入关系元组集合建立h a s h 表： p r o b e ：使用输入关系元组集合搜索匹配h a s h 表，输出匹配的元组； m e r g e ：合并两个排序的输入关系元组集合； n e s t e d 一1 0 0 p s ：按照给定规则比较两个关系的元组，输出匹配的元组。 基于操作森林的查询优化算法由三部分组成：( 1 ) 生成操作森林；( 2 ) 为每个操 作树分配系统资源；( 3 ) 调度森林中各树并行运行。 给定一个s p j 查询，操作森林生成算法如下： 1 生成s p j 查询的语法树； 2 转化s p j 查询的语法树为操作树： 在每个关系与其父结点之间插入一个s c a n ； 在直接相连的每对j o i n 结点间插入个s c a n ( 表示数据分布) ； 选择实现j o i n 操作的算法，把每个j o i n 结点用一个由基本操作组成的树 代替； 3 在操作树上标记顺序执行边：若b 是a 的父结点，b 必须在a 完成之后才能 开始运行，则边( a ，b ) 标记m ，即顺序执行； 4 删除操作树中标记“m ”的边，形成操作森林 给定一个操作森林，资源分配算法如下( 书架分配法) ： 1 根据数据相关性，对操作森林中所有操作树进行拓扑排序，确定操作树的执 行顺序图，执行顺序图中的结点是一个操作树： 2 计算每个操作树t 的工作量w ( t ) ，即t 在单处理机上的执行时间； 3 在执行顺序图中确定关键路径，即最长路径； 4 从书架的第一格开始，把关键路径的各结点按执行顺序图由叶到根的顺序分 别存入不同的格子： 5 按规则把执行顺序图中其余节点分配到各个格子中； 6 在每个格子中的所有操作树之问分配系统的所有处理节点。 资源分配结束后，各个子操作树的运行很简单，只需从第一格开始顺序运行各 华中科技大学硕士学位论文 格子的所有树，每个格子中操作树并行运行。 1 3 本文的主要工作和贡献 本课题旨在对并行数据库的物理组织、并行数据操作算法进行研究与探讨，重 点在于并行数据库技术中的查询处理及优化，然后作者提出一种基于a g e n t 的语义 查询模型( s e i r i a n t i cq u e r ym u l t 卜a g e n ts y s t e m ，简称s q m a s ) ，并以此模型为基础 提出了一种a g e n t 并行数据库查询方法，同时，为保证查询效率，提出了一个树型 拓扑结构( t r e et o p 0 1 0 9 ym u l t i a g e n ts y s t e m ，简称t t i a s ) 的通信模型，从而对并 行数据库技术中的查询优化领域做出了有益的探索。 作者所述语义查询的研究新思路是，在分析、总结前人研究成果的基础上，运 用语义查询的优化方法，使用人工智能中的定理证明技术，采用m u l t i - a g e n t 技术 来实现约束条件的自动查找。预期目标是建立一个s q 雌s 语义查询模型和树型拓扑 结构( t r e et o p o l o g ym u l t i a g e n ts y s t e m ，简称t t 姒s ) 的通信模型，能够在查找约 束条件的过程中花费较少的时间，从而提高语义查询的效率，实现基于a g e n t 的并 行数据库查询优化技术。 1 4 论文结构 本课题拟定基本内容和文章结构如下：第一章是绪论，介绍本课题研究的背景和 本课题所作的主要工作和主要贡献；第二章系统地介绍并行数据库技术的相关内容， 包括并行数据库的并行处理体系结构、枫群系统；接下来介绍并行数据库中的并行 数据操作算法，重点讨论了连接算法；第三章介绍人工智能、谓词逻辑和归结原理； 第四章在上述研究的基础上，重点介绍a g e n t 、姒s 的概念和应用，提出了一种基于 a g e n t 的并行数据库语义查询模型( s q m a s ) 和树型拓扑结构( t t m a s ) 的通信模型；最 后，第五章是结束语，对本课题的工作做出了一个小结，并展望需要进一步解决的 问题。 9 华中科技大学硕士学位论文 2 并行计算体系结构和并行连接算法 2 1 并行计算的体系结构 早期的d b m s 全部运行在单机上，被称之为集中式数据库系统( c e n t r a l i z e d d a t a b a s es y s t e m ) 。为了达到数据共享的目的，需要单机上的数据库系统能够连接 起来进行通信和合作，这样产生了分布式数据库系统( d i s t r i b u t e dd a t a b a s e s y s t e m ) ，其中每个单机上的数据库系统具有完备和独立的数据库功能。随着新硬件 技术的发展，多处理机系统的计算机体系结构应运而生，这些计算机系统拥有多个 处理机节点，依靠高速网络连接，适应了对高性能处理的应用要求，于是在此基础 上产生了并行数据库系统( p a r a l l e ld a t a b a s es y s t e m ) 。它与分布式数据库系统的 主要区别有三点“4 1 ： 1 应用目标不同分布式数据库系统以追求数据共享为目的，而并行数据库 系统以追求高性能为目的： 2 实现方式不同并行数据库中，各节点间采用高速网络互连，分布式数据库 系统各节点间网络带宽较低； 3 各节点的地位不同并行数据库系统是一个单一的数据库系统，它的每个节 点不具有自治性，分布式数据则是由多个数据库系统的组合而成。 自7o 年代出现了关系数据模型以后，关系数据库成为应用最为广泛的数据库 系统，尽管当前出现了更先进的数据模型( 如面向对象数据模型等) ，但关系模型仍 然倍受重视并不断被研究，特别是人们发现关系模型非常适合于并行处理，其自身 存在的固有并行性成为建立并行数据库系统的理论基础，所以当前的并行数据库系 统都是并行关系数据库系统。 关系模型提供了一系列关系代数操作，选择( s e l e c t i o n ) ，投影( p r o j e c t i o n ) ， 连接( j o i n ) 。并行查询方面的关键技术包括：并行处理的体系结构、并行处理的连 接算法、并行查询及其优化技术、数据偏斜及其处理技术等，其中并行处理的连接 算法和并行查询及其优化技术必须考虑系统的体系结构，发挥这种结构的长处，并 且要具有良好的抗数据偏斜的能力，以提高整个系统的性能。 1 0 华中科技大学硕士学位论文 2 1 1 三种计算机并行处理逻辑结构 并行数据库系统研究所依赖的并行计算机结构主要包括三种：共享主存储器结 构( s h a r e dm e m o r y ，以下简称s m 结构) 、无共享资源结构( s h a r e dn o t h i n g ，以下简 称s n 结构) 、共享磁盘结构( s h a r e d d i s k 以下简称s d 结构) 。1 9 8 6 年，s t o n e b r a k e r 提出s n 结构是支持并行数据库系统的最好并行结构“。目前，这个观点已经被普遍 的接受。s n 结构的优点主要有三个，首先，s n 结构通过最小化共享资源使得由资源 竞争带来的系统干扰最小化；其次，s n 结构具有高可扩充性，处理机个数可扩展到 数百甚至上千个而不增加处理机问的干扰；第三，s n 结构在复杂数据库查询处理和 联机事务处理过程中可获得接近线性的加速比。以下，我们称s n 结构中每个由单处 理机、主存储器和磁盘构成的单处理机系统为处理结点。 并行数据库系统有三种并行结构“” 1 共享主存储器结构( s h a r e dm e m o r y ，以下简称s m 结构) 在s m 结构中，多处理机共享主存储器，每个处理机具有独立的磁盘存储器，多 处理机和共享主存由高速通讯网络连接，处理机之间的通讯可以通过主存间接实现， 也可以通过高速通讯网络直接实现，i b m 3 7 0 多处理机系统、v a x 多处理机系统和 s e q u e n t 系统是具有s m 结构的典型并行计算机系统。见图2 一ls m 结构并行计算机。 图2 1s m 结构并行计算机 2 共享磁盘结构( s h a r e dd i s k ，以下简称s d 结构) 在s d 结构中，处理机共享所有磁盘存储器，每个处理机具有独立的主存储器， 处理机之间的通讯可以通过磁盘存储器间接实现，也可以通过高速通讯网络直接实 现，i b m 的s y s p l e x 系统就是一个基于s d 结构的并行计算机系统。见图2 2s d 结 华中科技大学硕士学位论文 构并行计算机。 图2 2s d 结构并行计算机 3 无共享资源结构( s h a r e dn o t h i n g ，以下简称s n 结构) 在s n 结构中，没有任何共享硬件资源，每个处理机都具有独立的主存储器和磁 盘存储器，处理机之间的通讯由高速通讯网络实现，t e r a d a t a 系统、t a n d 肼系统、 n c u b 系统和较新的v a x c l u s t e r 系统都具有s n 结构。见图2 3s n 结构并行计算机。 图2 3s h 结构并行计算机 在实际应用中，目前均采用s n 结构。简而言之，三种结构之优劣比较，在可扩 充性和可用性方面s n 结构显然要优于其他两种结构；而在负载平衡、设计的简单性 等方面，则是s m 结构的优点要突出一些。对于节点数目较多的配置，s n 结构比较好 的适应了高伸缩性的要求，他通过最小化公共资源来最小化资源竞争带来的系统干 扰。对于中小型系统的配置，s m 结构由于其设计的简单性和负载易于均衡，也许就 华中科技大学硕士学位论文 表2 1 三种并行数据库体系结构比较“4 s h a r e d 研e m o r ys h a r e d - d ；s k s h 8 r e d n o t hin g 性能最佳较佳较佳 可用性低 较高高 可扩充性差较好好 负载均衡易做到易做到难做到 实现技术容易较复杂复杂 成本高 较低低 处理机数数十个数百个数千个 规模中小系统中小系统 大系统 更为合适一些。此外还有混合结构，即整个系统是s h a r e q n o t h i n g 结构而每个结点 是s h a r e d _ m e m o r y 结构，这种结构综合了s m 和s n 的优点。 2 1 2 机群并行计算枧系统与并行软件环境 上一节三种并行结构是逻辑并行计算机结构，与通常物理并行计算机的分类有 所不问。但是，m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 计算机和机群( c l u s t e r ，见 图2 4 ) 并行计算环境完全可以按照这三种结构分类。实际上，机群并行计算环境 就是一个典型的s n 结构，它是随着计算机网络技术的发展而产生的一种