（计算机软件与理论专业论文）sdd1查询算法在分布式数据库中的应用.pdf

摘要 分布式查询优化的研究领域是分布式数据库中的研究热点。由于集 中式数据库和分布式数据库的区别在于，分布式数据库需要站点间的数 据传输。所以大多数研究分布式查询优化以减少通讯开销为目标。而分 布式数据库中查询优化是n p 完全问题，至今都没有得到彻底的解决， 里面尚有许多问题值得研究和探讨。既有理论上的问题，也有实际应用 中的问题。这些问题在当前显得尤为重要。 本文的研究主要集中于分布式查询优化策略。本文是以通信传输开 销作为主要优化目标，以半联接运算作为主要手段，研究了s d d 一1 算 法在分布式数据库查询中的应用，并在s d d 一1 算法的基础上提出了两 种改进的方法。一种是基于多关系半联接的优化算法，它适用于以分布 式数据库系统的缓冲区作为查询的中间结果的最后装配站点这种情况； 另一种是基于虚拟联接的优化算法，它兼顾了网络费用和局部处理费 用，并对选择度有自适应性。实验证明这两种方法都有很好的性能。 关键词：分布式数据库查询优化半联接虚拟联接 a b s t r a c t 璜s | f i b 毽| e d 醢e f ￥o p t 瓤 z 越i o 珏f e s o 鞭c h 主s 珏鞋d o rw 8 ￥i 珏珏撕v e f s i t e s ， r e s e a f c hl a b o r a t o r i e sa n ds i m i l a re s t a b l i s h m e n t s 1 ti sav e r va c t i v er e s e a f c h a r e aj nd i s 州b u t e dd a t a b a s es v s t 锄t h e r ei sd j 爿c r e n c eb e t 、r e e nc 蝴n 面i z e d d a t a b a s ea n dd i s t d b u t e dd a t a b a s e w h i c hd i s t f i b u t c dd a t a b a s en e o d sd a t a f a n s 掰嫩a t i 濑s om o s l 摊s o a 确o f 国s 蜮b m 积瑶毽e f vo 垃m 主z a t i o na ha 毛 糟d u c 主n g m u n i c 越i o nc o s t 髓l e 函s t 秭b u l e dq e f yo 辨i m i z a 壕磙p f o b 重e m i st l l ek e vp o i n ti nd i s t r j b u t e dd a t a b a s es v s t e m ，a di ti sa nn ph a r do n e t h ep a p e rf o c u s e sp r i m a r i l v0 nd i s t r i b u t e dq u e r vo p t i m i z a t i o n i i l d i s i 主b u t e dq u e r yo 撕m i z a t i o n ，t h i sp a p e ra 蛔sa th o wt of e d l l o e c 鲫m 珏n 勰t o 珏e 。s l ，a 酾p t | n gs 锄霉。魏p 笋a m 。强主sp 颦e f 季v e se m 露鑫s 至s t o | h er e s e a l c hs d d lo p t i m i z a t i o na l 盛o r i t h r na p p l y i n gi nt | l ed i s t r 主b u t e d q u e r y ，a i i db r i n g sf o n a r dt w oi m p r o v e da l g o r i t h m so nt 圭l eb a s i so ft h e r e s c a r c ho nt l l es d d - la l g o r i 毛l l m o n ei sb a s e do nt h cm u 圭t i p l ef e l a t i o n s s e 越莓。攮，w 魏i c hc 强b ea 1 ) p l 褪拇 h ec 至珏m s l a n e e 撅w 耋l 主e h 氆ec a e 珏eo f d d b si s 攮e 矗n a la s s e m b l ys i t eo ft e m p o r a r yq u e f yf e s u l l ；磕eo t h e fi sb a s e d o nv i n u a li o i ，w h i c hr e d u c et h ec o s to fb o t l lc o l n m u i c a t i o na n dl o c a l p r o c e s s i n g ，a i l di ti sa d a p t i v et od i 仃c r e n tv a l u e so fs e l e c t i v i t y e x p e r j m e n t f c s u 王t ss h o w e d 氆et w oi m 蛰f o v e da l 妒嫩h 翔sa r ee f 嚣e i e n t k e yw o r d s ： d i s t r i b u 如dd a t a b a s e q u e r y0 p t i m i 龆6 0 n s e m 嵇o i v i r t u a lj o i n 1 瓣， 第一章绪论 如今计算机的应用领域迅速扩大，数据库的规模也目益增长，用户 查询越来越复杂，对分布式数据库管理系统处理能力和速度的要求越来 越高，分布式查询处理的优化问题也就成为了分布式数据库的主要问题 之一。分布式查询处理是用户与分布式数据库之间的接口。在分布式数 据库中由于数据的分布与冗余，使得数据在各站点间的传输代价成为查 询处理的主要矛盾。另一方面，数据的分布与冗余也增加了查询的并发 处理的可能性，从而可以缩短查询处理的响应时间，提高处理速度。因 此，与集中式数据库相比，分布式查询处理增加了不少新内容与复杂性。 在分布式查询处理中，主要讨论复合查询的处理，在这种查询中， 由于涉及多个站点的数据，站点间的数据传递必不可少。通讯费用成为 算法优化的一个很重要的因素【1 】。而且与网络的通讯模型有关：不同的 网络通讯模型有不同的查询优化算法。此外，比集中式查询处理更加复 杂的是分布式查询处理中，需要随时了解所涉及的各站点的数据变化情 况。一般地说，需要静态地对此做出估计，这就需要数据库的统计模型， 数据库统计模型对查询处理算法有很大影响吲。 在这些模型的基础上，根据不同的优化目的来设计各种查询处理的 优化算法。一般地说，一个好的分布式查询处理算法，应该是通讯费用 低而且并行程度高。但是，这两者之间经常互相矛盾，任何分布式查询 处理算法必须在这两个性能指标之间做出权衡【3 l 。 通常分布式数据库系统是建立在远程通讯网络上的，各站点之间数 据传输率比单机情况下内存与磁盘间的数据传输速度要陧2 0 倍至3 0 倍 p l ，因此，查询的局部处理时间与通讯时间相比可以忽略不计，减少通 讯费用成为分布式查询处理的主要问题。又根据费用模型，通讯费用与 所传递的数据量成正比【5 】，因此，分布式查询处理通常以减少传递的数 据量作为优化目标。 在有限的网络资源上进行大型分布式数据库开发运行维护，如何 有效的利用网络资源，减小网络传输数据量，降低通讯费用，一直是需 要慎重考虑的问题。本文就是研究s d d l 查询优化算法足如何应用到 分布式数据库的查询模块中减少通讯费用的，并对该算法进行了改进。 1 1 本课题的来源 在数据库系统中，查询处理的效率是人们很关注的问题。随着计算 枫蝴终豹掇广与普及，尤其是融c f n e t 技术的快速发展，使得瞬络已澎 湃藏为人们工作、学习藏生活斡重要维藏郝分。丽辩，盘予羧攒痒蕊模 的不断扩大和地域分布的不断扩散，使得纂于网络环境下的分布式数据 库淼询的需求也越来越大。分布式数据库谶询处理追求的目标娥：最小 豹酾应辩阗莘羹最抵豹嘲终邋馈戴价。恧蘩予w 如一f 豹分毒式数据簿套 谗的簧求剃筵高强l 。嚣懿，掰搜麓豹能够蜜潍这稀鬻求静技拳都一定獠 度上存在藉缺陷，主螯袭现在系统缺乏跨平台性、开发难度大、效率较 羝籁薅爨维护等是令方颡。灏戮，势薄强兹这秘穗魏，选择一秘会遗鹣 授术实现这类的分布式数据席查询处理觏整得尤为重要。本论文主要 研究了基于半联接的s d d 一1 磷询算法在分布式数据库查询模块中的应 用，并对该冀法进行了潋进。 1 。2 本课题的国内外研究璐状 ( 1 ) a 瓣俊豫算法 a h y 算法【7 j 指的憝由a p e r s ，h e v n e r 和y a o 所发表的论文所提跬 的辣法。该算法适用于追求最小系统开销或最小通讯延迟的场合。a h y 算漩把壹询掰涉及豹关系先遗行零建楚理，然蓐铡爝半连接操终袋约筠 遂憋关系。激终遥箨一个套谕筏行瑟点，将约麓露鹣关系帮铸遴到这个 结点，实施这个查询。 ( 2 ) s 瓣一l 算法 s d d l 中首先掇滋了用半联接操作来代替联接操作的思想f “，并 且采取全局优化方法处理查询。其主要思路魁，首先用半联接来减少荚 系的元组数( 称为基数) ，在半联接施加到最大限腱时，取一个站点收 集裘谗瓣涉觳到静藏骞关系，在这拿羹点上执行这令查逡。在本论文中 主要研究介绍的就是s d d l 算法在分布式数据瘁中酌应雳，并在此綦 础上提燃两种改进的算法。 ( 3 ) 8 濑+ 算法 r + 的分布式查询髯法是对系统r 中优化器技术的扩充，采取编 译的方法：在编译时列举所有的查询方案，从中选择一种代价最小的焱 谗筑路。r + 中查询的编译是分布式执行的，执行的过程出套溺勰摄交 滔患，帮变站点受责诲调。主站点受责决爱全蝎的凌稳策略，簸涎点炱 爨确定各局酃站上的具体蓬询策略。r + 优化器的舀标是降低畿询的总 露镄( 包懿越部查询野销秘迢讽歹 二销) 。 ( ) c p o r e l 算法 c p o r e l 是一个建j 谚在局部网上的分布式关系型数据库系统，熟 网络通讯开销和局部处理开销处于同一数量级上f 1 0 1 。其中，关系可以 水平分布，即一个关系水平地划分为若干个子关系，且各个子关系是两 两无交的。 1 3 论文的研究内容和组织结构 在本文中，从分析分布式查询的特点入手，讨论了分布式查询优化 的目标及分类，通讯费用模型，半联接操作和s d d 一1 算法及其应用。 其中，重点研究了s d d l 算法在分布式数据库查询中的应用，并对该 算法做了改进。 本论文的组织结构如下： 第一章“绪论”：主要介绍了分布式数据库中查询优化算法的国 内外现状并简述了本论文的主要研究内容。 第二章“分布式数据库查询及其优化”：主要介绍了分布式查询 优化的目标，要考虑的问题等。 第三章“通讯费用模型”：主要介绍了关系的静态特性和本文所 使用的计算通讯费用的模型。 第四章 “s d d 一1 查询算法”：主要介绍了s d d l 查询算法使用 的半联接操作，对s d d 一1 算法进行了介绍和分析，并给 出在实际分布式数据库中的应用实例。 第五章“对s d d l 算法的改进”：主要介绍了两种在s d d 一1 算 法基础上的改进方法。一种是基于多关系半联接的改进， 另一种是基于虚拟联接的改进，实验证明这两种方法都 有很好的性能。 总结对全文进行了总结。 第二章分布式数据库查询及其优化 数据库系统研究的主要目标是尽可能的对用户隐藏数据结构的细 节，使数据库系统的应用更能面向各个领域。同样，分布式数据库研究 的主要目标之一是隐藏分布式环境的细节，使系统用起来更加简单有 效。 关系数据模型可以为集中式数据库提供一个数据无关的接口【1 “。 关系数据库语言是关系演算，使用该语言进行数据查询时，只需对要查 询的数据进行简单的描述，而无需说明如何获取这些数据，s q l 语言就 是其中之一。但是，使用这种语言，也要对搜索，存取操作以及数据传 输过程进行说明，因此，相应的查询优化技术的研究和发展也在不断进 行。 2 1 分布式查询优化的目标 讨论查询优化策略问题，也就是说，在各种可能的方案中选择一个 费用最少的方案。事实上，“优化”这个词不太准确，因为一般情况下 优化的方法并没有得到最优化，而只是寻求“好”的访问策略而已；而 且，它们取决于对处理环境所做的简化假定【1 2 】。 不管在集中式还是分布式环境中，查询优化策略都是根据对各种方 案的期望性能进行衡量来选择的。与集中式数据库相比，在分布式数据 库中，还必须考虑数据的传输量。然而，在传输的费用和本地i o 的费 用之间那个更为重要没有统一的看法。要看对处理环境的不同假定【1 ”。 在地域上分散的分布式数据库情况下，传输费用看来更为重要，那里的 带宽受到严重的限制【1 4 l ；但是在局域网情况下，站点之间的带宽接近 于本地的i o 操作。 传输的要求可以依据费用和延迟这两方面来评价： 1 当考虑费用时，一个应用的性能是用所有传输的费用之和来量度 的。这个方法相当于使通讯网络中的整个传输开销最小。 2 当考虑延迟( 响应时间) 时，一个应用的性能是用此应用从激活 到完成所经历的时间来度量的。减小延迟等于增加执行中的并行程度， 不一定相当于使整个传输开销最小。 两种代价的模型： 一次传输的费用t c 和传输延迟t d 一般可用函数来表示，它是传 送的数据量x 的线性函数： t c ( x ) = co + x c 1 x ) 慧de + x d 1 其中c 。，e ，d 。，d ，怒与系统有关的常数：c 。棚当于在两站点 间稿动一次传输所需要的固定赞用；c ，是网络中统一的传输费用；d 。魁 建立一个聪接所怨的固定时间；d ，是网络范围内统一的传输速率a 2 2 分布式数据库优化骤考虑的问蹶 分布式数据库存在于网络环境中，由于数据的分布性，一次查询所 搽缓豹对象可畿分毒于不羁豹瓣鼹节点孛，囊整豢寒憝开镶窝撬行速瀣 就会不一样，优化所要考虑的因素就更为簸杂汹l 。分布式查询处理模 块划分及处理流程如图2 1 。分布式数据库环境中的查询优化与集中式 数据库环境中的懑询优化相比较，要增加对以下两个关键问题的考虑： l 。数据稠信惑均要通过邋镶线路进行健辕，存在延遨的闽题将减慢 整个囊诲撬行遗襁。 2 网络中多处理器的存在提供了并行处理和传输的机会，应充分利 用w 以加快查询响应的速度。 在分布式数据库系统中，一方嚣，许多糨对独立的处理器可能参与 鼗攘疼撩捧【1 6 l 。分毒式数嚣簿霹戆提筷蓍予辊会： ( 1 ) 由于在处理一个问题时可以使用多台机器，并行以及加快查询 反威速度的可能性增大【1 ”。 ( 2 ) 由于数据可以在多个站点上存在副本，系统可能不会仅仅由于 一个节点或整传发生薮障囊不褥不箨止处爨。 另一方面，分布式处理增蕊了分布式黎统各个方西的复杂性，因戴 即使是d b m s 中最基本的组成部分的设计，也得重新考虑。在许多分 布式环境中，通俗开销可能远大于处理开销，因此问题是消息如何传送。 分匆式数据藤查询处理如圈2 ，2 ，分布特性的存在睃带来通信开销 羚矮彩稳至l 耱毽褒诲诗麓觞笺象犍帮可逸穷寨。在选择秘瑾查谗诗划瓣 必须考虑的问题包括1 1 8 】： ( 1 ) 如果某个所需关系r 有多个副本，那么应该从那个副本中获得 r 的值。 ( 2 ) 当在蘧个关系r 露s 一实蓬菜令搽体穗如联接辩，毒多令霹逸 方案丽且必须选择其中之一辩，+ 些可能的选项如下： ( a ) 可以将s 复制到r 所在站点，并在该站点执行计算。 ( b ) 可以将r 复制到s 所在站点，并在该站点执行计算。 ( c ) 可以憋r 取s 复制到：者各量蹶在站点之夕 的蘩三个站点，劳 在该站点执行计算。 嗣户妊 代覃y 一克困 壤器 爆受蠢两祷 磷未i 粉p 一一r 苎 ! 强局警淘优化、 一一o 。 压丽高蕊z 蛾 数据处 理嚣 窭吨 一千行譬蠢撑夸。 本避斑模式l 、一* 。7 l 一 倒21 分布式查滤处理模块划分及处理流程 哪种选择最好，这依赖于多个因素，其中包括哪个站点上有可用的 处理时问以及操作结果是否需要与第三个站点上的数据相结合等。例 如，如果我们计算( r 。s ) 。t ，那么可以将r 和s 都传送到t 所在站点， 并在该站点执行两个联接操作。 如果关系r 有分布在若干站点上的片断r ，r ：，r 。构成，那 么在选择逻辑查询计划时，还应该考虑用r ，ur ，u ur 。替代查询中 使用的r ，替代后的查询或许能很大程度的简化表达式。 对局域网来说，通讯代价有着跟数据库的磁盘i o 代价相比拟的重 要性。网络通信代价会随着用户数或负载的变化而改变，所以网络情况 变化的随机性对分布式查询处理来说，更应该考虑通信代价。但当某个 数据库的查询负载过高时，需要牺牲一定的通讯代价来提高执行的并行 性。此外局域网络的广播能力可以用于全局优化更新，收集信息。 控 制 节 点 本 地 站 占 在 在分布关系上的代数查询 分片查询 含有通信操作的 优化的分片查询 优化的本地查询 幽22 分布式数据库商询处理 厂、 ， 2 3 分布式数据库优化分类 1 查询优化的关键在于在所有可能执行策略的途径空间中选择一 个最佳的点1 1 9 j 。一种直接的方法就是从途径空间搜索所有可能途径， 选择一种最佳的途径。此种方法所需代价太高。 另一种减小代价的办法是随机策略，随机选择一种可能的途径。这 种执行途径可能不是最好的但它是相对比较好的，减小了内存和时间消 耗的代价。 再一种减小代价的办法是使用启发式选择，在方法空间中缩小查找 范围。无论在集中式还是分布式系统中，通用的办法是减小中间关系的 尺寸。它首先执行一元操作，然后对二元操作进行排序。在分布式系统 中，一种重要的启发式选择是通过把通信代价与半联接结合来替换传统 的联接操作。 2 另一种分类方法是根据优化与执行的不同时间来分：静态和动态 两种优化。 前者在执行前优化；后者在执行时优化。静态查询优化在编译时进 行，因此代价的分布存在于符合查询的各个步骤和阶段中，所以策略的 中问关系的大小无法知道，只有在运行时才知道，必须使用数据库统计 来估计代价的大小，而错误的估计将会影响子策略的优化途径。 动态查询优化在运行时进行。在执行的任何一点，最佳的下一个操 作的选择依赖于前一次操作执行的结果集的精确信息。因此，数据库统 计不必用来统计中间结果的大小。但是，它们对选择第一个操作仍然有 用。动态查询的主要优点在于查询处理器可以获得中间关系的实际尺寸 的大小，因此减小了错误选择的可能；主要缺点在于查询处理作为一种 高昂代价的任务，在每次查询完需要重复执行。因此这种办法只针对特 定的查询。 混合查询优化则致力于提供静态查询优化的优点而尽量避免不精 确估计带来的问题。这种方式是基于静态方式的，但在出现中间关系的 预测大小与实际大小有很大偏差时，可能进行运行时动态查询优化。 第三章通讯费用模型 3 1 关系的静态特性 为了对数据库存取进行定量分析，需要定义数据库的统计信息，以 确定数据量的大小。这也就是利用一种统计方法使查询执行前后对物理 关系尺寸的变化能有所估计，给出一个满意的执行次序。一种行之有效 的方法是计算物理关系的静态特征，估算出对物理关系操作后的变化， 从而决定中间关系的特性。 3 1 1 物理关系的静态特性 物理关系的静态特性包括： 关系的元组数( 或称基数) ：c a r d 鳓 属性的宽度：s i z e f a ) 关系的宽度：s i z e ( r ) = y s i z e ( a 。) 篇。 每个属性在关系中不同值的个数：v a l ( a ( r ) ) 物理关系所在场地：s i t e ( ri ) 这些信息应由系统自动维护。 例： 给出一个全局关系和它的片段( 物理关系) 的静态特性的实例，设 s u p p l i e r 是一全局关系，s u p p l i e r l 是它的一个物理关系，其静态特性可 分别如下表示： c a r d ( s u p p l i e r ) = 2 0 0 s i z e ( s u p p l i e r l ) = 3 6 c a r d ( s u p p l i e r l ) 2 7 0 s i z e ( s u p p l i e r l ) = 3 6 s i t e ( s u p p l i e r l 2 1 ) ( 站点1 ) 上例分别表示了全局关系及其物理关系的静态特性。由于s u p p l i e r 按s c r r y 水平分片，所以其属性个数不变，只是元组数有所变化。从 全局关系到物理关系实际上已经是经过了一次分片操作( 代数操作) 。 从这实例里我们可看到，逻辑关系与物理关系用静态特性来表示时，其 性质( 特性参数) 除站点参数外均相同，而全局关系与逻辑关系( 或物 理关系) 则不一样。所以可以理解：静态特性参数中r 可以是全局关系， 逻辑关系或物理关系，当指定是物理关系时就应有站点s i t e ( r ) 参数， 而是其它全局关系或逻辑关系时就不必有站点参数。从此亦可引申到任 何中间关系的静态特性均可以从上述参数表示。下面给出代数操作对静 态特性变化的计算( 估算) 方法。 3 1 2 代数操作对静态特性的影响 关系操作的结果仍然是关系，但其静态特性肯定有所变化，在优化 时评估其收益( 效率) 可以用静态特性来评估。 设一元操作的操作数为r ，其结果关系为s ，二元操作的操作数为 r 和s ，其结果关系为t 。下面分别讨论各种代数操作的静态特性评估。 ( 1 ) 选择操作os = o ，( r ) 基数。对于每个选择操作总存在一定的选择度，用p 或s f ( c ) 表示。 每次选择均会有一些相应的元组被选中，0 是满足选择条件的元组的一 部分。在简单的选择中有属性等于值( a = v ) ，所以q = 1 ，v a l ( a 【r 】) 。若 我们假设值是均匀分布，且值v 出现在a 中，则有：c a r d ( s ) = q c a r d ( r ) 关系的宽度。选择操作不影响关系的宽度，所以有：s i z e ( s ) = s i z e ( r ) 不同值的个数。即结果关系中非选择谓词属性b 的不同值的个数。 假设b 与选择属性无关且是均匀分布，则v a l ( b 【s 】) 可由下述统计导出， v a l ( b 【s 】) 的个数与v a l ( b 【r 】) ，c a r d 限) ，c a r d ( s ) 有关。设c = v a l ( b 【s 】) ， m = v a l ( b 【r 】) ，r = c a r d ( s ) ，n = c a r d ( r ) ，则可给出c ( n ，m ，r ) 值的一种 实用的近似值： r r ， 当r m 2 c ( n ，m ，r ) = ( r + m ) 3 ，当m 2 r 2 m ( 3 1 ) l m ，当r 2 m 这个统计式可用不同的数学近似方法给以解决。这类统计方法中， b 的不同值的个数必须基于上述假设；若不是，则上式不能使用。此外， 对于选择属性a 的个数也不能用此法求。 ( 2 ) 投影操作n 基数。投影会影响操作数的基数，因此可能从结果关系中消去冗余 元组。其影响度可从下述三条原则来考虑： ( a ) 投影只含r 的键属性，则c a r d ( s ) = c a r d ( r ) ( b ) 投影只含r 中的一个属性a ，则c a r d ( s ) = v a l ( a 【r 】) ( c ) 投影包含属性集，且其积小于c a r d ( r ) ， n v a l ( a i 【r 】) c a r d ( r ) ，其中a t t r ( s ) 是结果关系s 中包含的属 性，则c a r d ( s ) = v a l ( a 【r 】) 关系的宽度。关系的宽度投影以后的s 关系的宽度 s i z e ( s ) = 罗s i z e ( r ，a 。) a j 者品r s l 不同值的个数。投影结果s 关系的不同值个数与r 关系相同，有： v a l ( a 。【s 】) = v 砒( a j 【r 】) ( 3 ) 联接操作o ot = r s 基数。精确计算t 的元组数是一个相当复杂的问题。由于c a f d ( d c a r d ( r ) c a r d ( s ) ，所以我们可给出c a r d 的上界，但要有几种情况： ( a ) 假设r 中所有a 值也都出现于s 中的b 值，或反之亦然，即有： v a l ( a 【r 】) = v a l ( b 【s 】) 且两个属性在r 和s 中是均匀分布，则： ! 竖型堡! ! 里型堡1 2 v a l ( a 【r 】) ( 3 2 ) ( b ) 仍是上述假设，但若两个属性之一如a ，是r 的一个键属性，则： c a r d ( _ r ) = c a r d ( s ) ( 3 3 ) ( c ) 若上述假设不成立，则以上两式可以作为上界。 关系的宽度。有：s i z e ( t ) = s i z e ( r ) + s i z e ( s ) 但在自然联接时，由于它总能消去一个联接属性，则该属性就会从结 果关系中去掉，所以关系宽度会减少些。 不同值的个数。我们可以给出一些联接操作结果关系中不同值个数 的上界，也有几种情况： ( a ) 若a 是联接属性，有v a l ( a 【t 】) m i n ( v a l ( a r 】) ，v a l ( b 【s 】) ) ( b ) 若a 不是联接属性，有v a l ( a t 】) v a l ( a 【r 】) + v a l ( b 【s 】) ( 4 ) 半联接操作。ct = ro cs a b 基数。半联接操作与选择操作的估算相似，我们亦可给出半联接操 作的选择度p ，用来估算在结果关系中r 的元组数占的比例。 p = v i i ( a 【s d ，v a l ( d o m ( a ) ) 式中，v a l ( d o m ( a ) ) 表示在a 域中不同值的个数，有： c a r d ( i ) = p c a r d 【r ) 关系的宽度。与第一个操作数关系的宽度相同。 不同值的个数。其估算方式可采用与选择操作中相同的公式( 3 1 ) ， 其中n = c a r d ( r ) ，m = d ( a 【r 】) ，r = c a r d ( 1 ) 。若a 是在半联接条件中 唯一出现的属性，则有： v 甜( a 【t 】) = p v 酊( a 【r 】) 3 2 通讯代价的计算 这里主要介绍分布式数据库最突出的代价因素：站点间信息的传输 费用的估算。 在传输过程中一般有两种影响：费用( c o s t ) 和延迟( d e l a y ) 。若按费 用来考虑，表示一个应用的性能按所有传输费用之和来衡量，相当于要 使通讯网络中整个传输开销最小；若按延迟考虑，一个应用的性能是按 此应用从激活到完成所经历的时间来度量的，也就是可以增加执行的平 行度以减少延迟，不一定使整个传输开销最小。一次传输中，起决定作 用的当然还有数据量的多少。在本文中是按费用来考虑的。 一次传输的传输费用( t c l 可以用函数法表示，它与数据量的大小成 线性关系：t c ( 砷= c 。+ x c ， ( 3 4 ) 其中，c 。，c ，均是与系统有关的常数。c 。相当于站点间传输数据的 初始( 启动一次) 所需的固定费用；c ，是网络传输数据的统一费用。 第四章s d d 一1 查询算法 s d d 1 是美国计算机公司( c o m p u t e rc 0 r p o r a t i o no f a m e r i c a ) 第一 个分布式数据库管理系统的原型，它是在1 9 7 6 年到1 9 7 8 年间设计的， 并于1 9 7 9 年在d e c 一1 0 和d e c 一2 0 两个型号的计算机上实现【驯。它的 查询优化就是对逻辑关系使用选择、投影、半联接操作来缩减，有准备 好的缩减程序并且选定一个处理场地。在优化中，唯一考虑的代价是数 据的传输费用，因为他们采用的是a r p a n e t 远程网。s d d 一1 是一个 试验系统。s d d 1 支持数据分片，它支持水平分片和垂直分片；并支 持数据分片的重复存储，即支持可控制冗余；支持分片和位置透明性。 在查询处理优化方式方面采用了半连接技术并且采取全局优化方法处 理查询。在事务管理中采用时间印方法和由r e i t 提供虚拟机的假 脱机方式保证可靠性。s d d 一1 对研究分布式数据库系统的重要问题有 很重要的贡献，查询优化特别是用半联接程序作为缩减有一定特色。 4 1 半联接操作 当前对联接操作的优化有两种趋向【2 1 l ：一种是采用半联接技术， 一种是采用直接联接的技术。其特点是各自追求的优化目标不同。其中， 半联接技术是减少联接操作的操作数，以降低通讯费用，它主要考虑的 是传输代价。由于本文研究的s d d l 算法使用的是半联接技术，因此 这里主要介绍半联接操作，对直接联接技术不予说明。 用半联接进行优化的基本思想是把关系传输到另一站点之前，尽量 减少关系中的元组数【2 ”。表面上看，其思想是把一个关系r 的联接列 传输到另一个关系s 所在的站点上，然后把该列与s 进行联接，随后， 把联接属性和结果中要求的属性投影出来，并传输回原来的站点与r 进 行联接。因此，r 的联接列只在一个方向上传输，而无额外元组和属性 的s 子集则在另一个方向上传输，若只需要s 中的一小部分元组参与联 接，那么，这是一个十分高效的解决方法。由此使得数据传输量最小。 下面我们介绍半联接操作。 4 1 l1 半联接程序的性质 半联接程序是基于半联接操作的。半联接操作是一种导出操作，具 有不对称性。 例： 设r ( a ，b ) 和s ( b ，c ) ，根据半联接的不对称性有ro c s = r 。( n s ) b 和so cr = s 一( n 。r ) 。如果有图4 1 ( a ) 的实例，则ro cs 的结果如 b b 4 1 ( b ) 所示，so r 的结果如图4 1 ( c ) 所示。 关系r 关系r 4 1 ( a ) 关系s 关系s 4 1 ( b ) r 。cs 4 1 ( c ) so cr b b 从图可得出：半联接操作对操作数r 或s 有缩减作用，且由于其 不对称性则各自缩减的程度不一样。半联接操作的缩减性与在联接操作 前先对操作数关系做选择和投影有相似的效果。特别在分布式环境中， 可用半联接操作减少网上数据的传送量。 在分布式查询处理的联接操作中提出了一种半联接程序的技术缩 减它的操作数。 所谓半联接程序，是用半联接技术实现联接操作的程序，即用一组 具有半联接与联接的操作映射出具有等联接相同结果的过程： r s ( ro c b s ) 。os ( 4 1 a ) a ba ba b 或 ro 。s # ( s 。c r ) r ( 4 1 b ) a bb z ab ，a ( 4 1 a ) 与( 4 1 b ) 式与两个关系直接联接等价。 在分布式数据库中，当r ，s 两个关系不在相同场地上时用( 4 1 a ) 或( 4 1 b ) 式处理，可以减少联接操作的数据传送量。 半联接程序的具体过程如下 以式( 4 1 a ) 为例，且假定r 和s 不在 同一场地 ： 在s 场地对s 关系做投影操作，使s 关系缩减为s ： “b s s 将s 送往r 场地； 在r 场地上完成r 与s 的半联接操作，使r 关系缩减为尺 ro ( sjr a b 将r 关系送回s 场地： 在s 场地完成尺与s 的联接操作： t ：r 一si 0 c r 图4 2 半联接程序操作图 s 上图是半联接程序的操作图，其核心技术思想是只将联接操作有关 的操作分量在网上进行传输。r 与s 关系在a = b 条件下联接，r ，s 关 系只有公共属性值相等的那些元组才有意义。 上述操作步骤起到优化的作用。 4 1 2 半联接程序的代价计算 在上面的半联接程序操作中计算其费用代价时，对于本场地的一元 操作及二元操作没有传送代价，而，步将s ，发送至相应场地 上有传送代价，但其数据量或称关系的静态特性则是由，步操作而 被缩减了，利用上章介绍的静态特性和通讯代价的估算方法，则 步的通讯费用为：c 。+ c ，s i z e ( b ) v a l ( b s 】) 步的通讯费用为：c 。+ c ，s i z e ( r ) c a r d ( 尺) 整个费用为：c 。= 2 c 。+ c ，( s i z e ( b ) v a l ( b s 】) + s i z e ( r ) c a r d ( r ) ) ( 4 2 a ) 缀鼹然，半联接的不对称性还可以莉掰一个费用： c 。= 2 c o + c l 箨i z e a ) v 醵s 驺 + s i z 。箨xc a 蠢s 势 ( 4 。2 b ) 邀嚣令睾联接程序戆费焉霹麓毒掰不鬻，麓它锭送行魄较藏霉寝选定一 个较优的半联接程序来处瑾强，s 豹联接搽终。 为了说明用半联接程序来处理联按撵作，我们可以将直接联接操作 时的费用计算与式( 4 2 a ) ，( 4 2 b ) 比较。r 和s 两关系的联接操作也可 以有两种方式：将r 送s 场地或殿之。其费用分别为： c 。= co + c lx s i z e ( r ) c 棚_ d ( r ) ( 4 2 c ) c 。= c 。+ c 1 s i z “s ) c 甜d ( s ) ( 4 2 d ) 我们比较( 4 2 a ) ，( 4 2 c ) ，若c 。c 。，即 c o + c 1 ( s i z e ( b ) v h l ( b 【s 】) + s i z e ( r ) c a r d ( r 。) ) c o + c l s i z e ( r ) c a f d ( r ) ( 4 ，3 ) 煲| j 半联接翟序是谯化的。要使式( 4 3 ) 成立，只要c a r d f r ) 大予 e 酣d ( 霆+ ) 盈s 凌g 回，v a 篷b 【s 】) 投小辩。这拿象赞在许多壤嚣下是可以瀵 足懿。繇婆震半联接程滓采筑藏袋按攥露豹攥终鼗渡减少逶逶代赞是可 敬愆。 4 1 3 用半联接缩减关系 在查询转换中讨论的准则或规则无非都是为了达到以最小代价获 取最高效率。在分布式查询中，要研究逻辑关系( 物理关系) 缩减处理 的正确性和有效性。缩减处理的含义魑，查询是对数据库的一种操作， 般只涉及部分数据库( 部分关系) ，糕至部分关系的某些成分。如果 能将与查询无关的数据库成分都消去，只对感兴趣的成分有操作，则查 询效率肯定提高。所以在查询处理中研究如何设法消去与查询无关的数 据瘁戏分的处理称为缩减处理。术谲“缩减器( r e d u c e f ) ”，即是完成 壤减处理操终甄缀藏的程序。对r 关系凌逡薅经过缩减处理能将不满足 囊德条 孛数繇有元缝( 或j 曩瞧缀) 全帮瀵去，这一邃缭藏翟彦髂为r 豹 全缩减程痃。一个查落戆“缩减程净”可霉多令。为了送行谔惩，烈 嚣建立每耱搡 乍( 包括一元攥佟和二元撩作) 对数据库酶影响。摹予翦 馘讨论的关系静态特性计算可从赞粥( c o s t ) ，效率( e 蠢e c t ) ，收益 ( b e n e f i t ) 三方面来描述。 ( a ) 效率一元操作，二元操作以后关系静态特性信息的改变，主要看 关系的基数c a r d ( r ) 和关系宽度s i z e ( r ) 的变化。 ( h ) 费用局部操作的代价为零，即不计算同一场地上的选择，投影， 半联接操作所需的费用。只有半联接或联接操作在不同场地上时才计算 费用( 参见式4 2 ) 。也就是我们暂且只关心通讯费用。 ( c ) 收益这里收益的含意是对关系r 的操作，使关系的静态特性信息 有了变化有： c a r d ( r ) 一c a r d ( r ) s i z e ( r ) 一s i z e ( r 。) 若r 与r 值不同，则其相减值( 差值) 就是该操作的收益。如： 对于投影，投影操作不会改变关系基数( 假设不支持重复元组) ，即 c a r d ( r ) 不变，则其收益只表现在关系的宽度上有收益： ”。= s i z e ( r ) 一s i z e ( r 。) 对于选择，选择操作会影响关系的基数，且取决于选择度p ，所以其 收益为： oa kr = s i z e ( r ) c a r d ( r ) - s i z e ( r ) p = s i z e ( r ) x c a r d ( r ) ( 1 一p ) 对于半联接，半联接与选择相似也有选择度，但选择度的作用不一样， 为了区别，用p 。表示，其收益为： r o s = c 1 【s i z e ( r ) c a r d ( r ) - ps j s i z e ( r ) c 盯d ( r ) 】 = ( 1 一ps j ) s i z e ( r ) c a r d ( r ) c l 从上面的分析可看出，半联接可以减少操作数，也就是可用半联接 作为缩减器。 两个关系r ，s 可以进行半联接，就有r 3 f r = r o c s ) 。把这一性 质推广到具有三个关系的查询，允许在每对关系之间进行半联接，对于 任何关系r ，s ，t ，我们有： r ( r = r o c ( s 。c n ) 而且r ( r ；r o c ( t o c s 对于r ，可以有一半联接程序使其缩减，其中能否找到一个全缩减 器是我们关心的问题。 4 2s d d 一1 算法简介 s d d 一1 算法采用了半联接程序处理联接操作【2 ”。它的查询优化就 是对逻辑关系使用基本的运算( 如选择，投影，半联接) 操作来缩减。 s d d l 算法是基于爬山( h i hc l i m b i n g ) 算法而形成的。它有五个主要 特征，首先，采用半联接是最主要的，其次，各个局部站点没有重复， 也不进行分片。此外，在它的代价讨算中，不考虑最后一个站点传送代 价。这是由于在它的查询策略中当使用半联接来缩减操作数关系的基 数，当最大限度的缩减以后，把所有关系送到可执行查询的站点| = = ，这 个站点不一定是查询所要求的结果站点。譬如说，着s 是结果站点( 经 半联接缩减后建立的) ，r 是查询要求的站点，s ，r 可能相同，可能不同， 若不相同，则还有一次传送代价将s 送到r 。最后它还能同时减少最小 化总时间和响应时间。 s d d l 算法有两部分组成：基本算法和后优化。基本算法基于爬 山算法，是爬山算法的迭代。根据评估缩减程序的费用、效率、收益估 算几个因素，给出全部的半联接缩减程序集，决定一个最有益的( 收益 大的) 执行策略e s ，但效率不一定高，然后选择一个装配站点s a ，将 已缩减完的关系传送到装配站点s a 上进行联接：后优化，将基本算法 得到的解进行修正，以得到更合理的执行策略。 基本算法： ( 1 ) 基础：已有了从查询树转换的优化模型，且所有关系已完成局 部缩减。 ( 2 ) 方法： 根据已得到的缩减关系的静态特性表，构造可能的半联接缩减程 序； 按半联接缩减程序的静态特性表分别计算其费用和收益，从一组 的静态特性表中选取一个半联接程序，设为m ； 以m 完成缩减后，又将产生一组新的静态特性表再进行计算， 再从一组可取的静态特性表中选一个半联接程序，但是每个半联接程序 只做一次( 避免导致缩减程序太长、效率不高) ； 反复直到无半联接缩减程序为止。 ( 3 ) 结束：以若干次迭代以后的最后缩减关系的静态特性表为基础， 进行站点选择( 费用计算) ，决定执行查询的站点( 可能与查询要求的 站点不同) 。 后优化： 在基本算法中，每次迭代时只考虑本次迭代时的“改善”，这种“改 善”不一定最好。后优化有两种修f ； ( 1 ) 若最后一次半联接程序缩减关系的所在站点恰好是被选中的查 询执行站点，则最后一次半联接可以耿消； ( 2 ) 对基本算法的主迭代所构成的半联接程序的流程图进行修正。 因为一丌始的( 或某一个) 半联接缩减程序的代价很高，如有，这时可 以把s 进行缩减后再进行半联接缩减，即可修f 半联接的操作序。 在s d d l 算法中，采用一种启发式方法来完成一系列联接查询执 行的压缩阶段【2 。该算法由4 1 给出，这种算法可以产生一个“好的” 半联接执行序列。 算法4 一ls d d 一1 一o o a i n p u t ：q g ：q u e r yg r a p hw i t hnr e l a t i o n s ；s t a t i s t i c sf o re a c hf e l a t i o n o u t p u t ：e s ：e x e c u t i o ns t r a t e g y b e 酉n e s _ 一l o c a l o p e r a t i o n s ( q g ) m o d i f ys t a t i s t i c st or e n e c tt h ee f e c to fl o c a lp r o c e s s i n g b s 一由 s e to fb e n c f i d a ls e m 玎o i n s ) f o re a c hs e m 司o i n s j i n q g d o j fc o s t ( s j ) c o s t ( e s s j ) n e n e s - 一e s s j e n d i f e n d f o r e