基于半连接的分布式数据库查询优化研究

1、基于半连接的分布式数据库查询优化研究余弋（安徽工程大学计算机与信息学院，芜湖241000关键词:分布式数据库；查询优化；半连接操作收稿日期:2010-06-23修稿日期:2010-07-23作者简介:余弋（1985-,女，安徽芜湖人，硕士研究生，研究方向为分布式数据库分布式数据库系统的分布和冗余使查询处理复杂化，因此分布式查询处理的优 化显得尤为重要。半连接操作是查询技术中的非常有效和重要的技术。分析分布式数据库 中半连接操作的过程以及执行代价，比较两种半连接操作的执行代价评估，介绍 SDD-1算法。摘要：0引言分布式数据库是把数据分布在不同的站点上，但这些数据片是建立在统一的逻辑框架上的，并

2、有高级的数据库管理系统进行统 一控制，它是统一性与自治性的完美结合。分布式查询处理是用户和分布式数据库 的接口，是分布式数据库的一项关键技术。由于数据的分布使得分布式数据库系统 中的查询问题比集中式数据库要复杂得多。不同的查询处理方法可能导致不同的通信费用、并行时间以及响应时间。要获得最小的查询开销 ，就要对数据进行合理分 布、查询优化。1分布式查询优化目标在集中式数据库系统中，由于系统大都运行在单个处理器的计算机上，所以查询总代价为CPU代价+I/O代价，查询优化的目标是 磁盘存取数，即要求产生最小磁盘数的查询执行计划。在分布式数据库系统中，由于数据的分布和冗余，使得查询处理除了考虑CPU代

3、 价和I/O代价之外，还需要考虑在网络上传输数据的时间开销以及多个节点并行执 行带来性能的提高，总代价=CPU代价+I/O代价+通信代价，查询执行时使其通信代价 最省是分布式数据库查询优化的目标之一，另一种目标是以每个查询的相应时间最 短为标准。在分布式查询优化中经常同时使用这两个标准。根据系统应用的不同，一种作为主要标准，一种作为次要标准。2半连接查询优化的基本方法在分布式数据库中，查询优化包括两个方面：查询策略优化和局部处理优化，而分布式查询策略优化尤为重要。在分布式数据库 中，查询的执行策略有很多种，不同的执行策略，系统资源耗费和响应时间也不同。查询优化有两种基本方法：查询转化，即以不同

4、顺序执行关系操作；查询映射， 以一系列高效算法访问各种设备和实现关系操作。目前，对查询处理出现了许多优 化算法，例如适用于多站点连接的基于半连接的优化算法和基于直接连接的优化算 法等。2.1基本原理采用半连接操作，在网络中只传输参与连接的数据，数据在网络中传输时，都是以 整个关系(也可以是片段传输，显然这是一种冗余的方法。在一个关系传输到另一场 地后，并非每个数据都参与连接操作或都有用。因此，不参与连接的数据或无用的数 据不必在网络中来回传输。用半连接技术实现连接操作的程序，即用一组具有半连接与连接的操作映射出 具有与等连接相同结果的过程。2.2操作过程(1半连接操作半连接操作是由投影和连接操

5、作导出的一种关系代数操作。假定有两个关系 R 和S，在属性R.A=S.B上做半连接操作可表示为：R 8S=nR (R 8 (IR 8S=R 00( nB (S(2(2采用半连接操作表示连接操作的过程'-i5-图1半连接方法表示连接操作过程(1在站点2作关系S在R和S公共属性集B上的投影IIB (S ;(2把n B (S结果送到站点1,代价为C 0+C 1刈ze (B vai (Bs;(3在站点1上计算半连接，设置其结果为R',则R'=R xA=B S ;(4把R'从站点1送到站点2的代价是:C 0+C 1 Size (R' card (R'(5在

6、站点2上执行连接操作：R'8A=B S2.3费用估计基于半连接程序的查询优化的主要目标是减少站点间的通信代价。通信代价与 分布式数据库所依附的计算机网络模型及其性能有关。对于不同的计算机网络应该 根据实际情况，设计对应的费用估计侧率和方法。如果假设网络中站点之间传递相同信息量的数据所花费的代价是相同并且忽略 站点之间的差异以及路由选择等费用，那么一个站点发送X个字节的信息到另一个 站点所花费的费用可以描述为 CX=C 0+C 1垓，其中C 0和C 1是网络性能相关的 参数。利用这个公式可以估计各种查询方案对应的传输费用。例如，对于全连接操作 R 8A=bs假如现在用下面的三种方案来解决

7、。(1采用S 8 a=b (Rxa=b ( n B S对应的半连接程序，费用有：在本地把S投影到B :假设nB S结果为X B个字节，投影费用为P B ;把X B个字节发送给R所在站点：费用为C B =C 0+C 1 * B ;和R执行半连接运算：假设结果为X RB个字节，半连接费用为S B ;把X RB个字节送到S所在的站点：费用为C RB =C 0+C 1 X RB ;和S执行连接运算：假设连接费用为J SRB，那么总的费用为：COST 1=P B +C B +S B +C RB +J SRB =(P B +S B +J SRB +(2C 0+C 1 (X B +X RB =COST 11

8、+COST 12。其中COST 11为本地运算费用，COST 12为站点传输费用(2采用R ooA=b (Sxa=b( nB R对应的半连接程序，费用有：在本地把R投影到A :假设HA R结果为X A个字节，投影费用为P A ;把X A个字节发送给S所在站点：费用为C A =C 0+C 1次A ;和S执行半连接运算：假设结果为X SA个字节，半连接费用为S A ;把X SA个字节送到R所在的站点：费用为C SA =C 0+C 1 >X SA ;和S执行连接运算：假设连接费用为J SRB，那么总的费用为:COST 2=P A +C A +S A +J RSA =(P A +S A +J R

9、SA +(2C 0+C 1 型 A +X SA =COST 21+COST 22。其中COST 21为本地运算费用,COST 22为站点传输费用。(3直接采用全连接R ooA=B S连接程序，一种可能解决办法和费用如下。把R全部发送给S所在站点：假设R为X R个字节，费用C R =C 0+C 1 * R ;和S执行连接运算：假设连接费用为J RS那么，总的费用为COST 3=C R +J RS =J RS +(C 0+C 1 X >R =COST 31 +COST 32。其中COST 31为本地运算费用,COST 32为站点传输费用。另外一种可能的方案是把S全部发送给R所在的站点并和R进

10、行全连接，那么 对应费用为 COST 4=J SR +(C 0* S =COST 41+COST 42,其中 COST 41 为本地运 算费用，Q ,COST42为站点传输费用。比较上面的COST1、COST2、COST3和COST4,可以选取代价最小的力口以执 行。点之间传递相同信息量的数据所花费的代价是相同的 ，这个假设在站点之间的 距离和发送/接收性能相当的情况下是合理的。如果站点之间以及路由选择等费用 差异很大时，需要重新考虑相关因素的影响因子，缺点合理的费用评估方法。2.4SDD-1 算法SDD-1算法有两部分组成：一是基本算法，根据评估缩减程序的费用、效益、收 益估算几个因素，给出

11、全部的半连接缩减程序集，决定一个最有益的（收益的执行策略, 但效率不一定高；另一个是后优化，将基本算法得到的解进行修正，以得到更合理的执 行策略。（1基本算法基础:已有了从查询数转换的优化模型且所有关系已完成局部缩减。方法：根据已得到的缩减关系的静态特性表，构造可能的半连接缩减程序；峨半连接缩减程序的静态特性表分别计算其费用和收益，从一组可能的静态特 性表中选取一个半连接程序，设为M；以M完成缩减后，又将产生一组新的静态特性表再进行计算，再从一组可取的 静态特性表中选一个半连接程序，但是每个半连接程序只做一次（避免导致缩减程序 太长，效率不高；反复直到无半连接缩减程序为止。结束：以若干次迭代以

12、后的最后缩减关系的静态特性表为基础，进行场地选择（费用计算，决定执行查询的场地（可能与原查询要求的场地不同。（2后优化在基本算法中，每次迭代时只考虑本次迭代时的改善，这种改善不一定最好。后 优化有两种修正：若最后一次半连接程序缩减关系的所在场地恰好是被选中的查询执行场地，则最后一次半连接可以取消；对基本算法的主迭代所构成的半连接程序的流程图进行修正。因为一开始的 （或某一个半连接缩减程序的代价很高，例如有R+S。这时可以把S缩减后在进行半 连接缩减，即可修正半连接的操作程序。3结语本文重点讨论基于半连接的查询优化技术在分布式数据库中的应用，证明了查询策略的好坏将直接影响计算机网络资源的耗费。但

13、分布式数据库系统的建立环境 和技术内容复杂，对于查询优化技术，还有许多问题有待进一步研究和解决。相信随 着计算机网络技术的飞速发展，分布式数据库技术也必将迅猛发展，并日趋完善。参考文献1陈建荣，严隽永，叶天荣.布式数据库设计导论（第一版M.清华大学出版社,2002:20782Bell D,Crimson J.Distributed Database SystemM.New Jer-sey:Addison Wesley Publishing,2004:5793邵佩英.布式数据库系统及其应用M.科学出版社2006, 1:3414贾焰,王志英.分布式数据库技术M.国防工业出版社,2005,32(3:

14、2002025毛国君.高级数据库原理与技术M.人民邮电出版社2004, 9(4:3013066萨师燎，王珊.数据库系统概论M.高等教育出版社,2005, 7(4:88947郑振楣.分布式数据库M.科学出版社，2004:1921,2028Wong E.Dynamic Rematerialization Processing Distributed Queries UsingRedundant DataJ.IEEE Trans Software Engi-neering2002,28(3:2282329SE.Goodman&ST.Hedetniem算法的设计和分析弓I论M.沙铁译才青华大学

15、出 版社,2001:668510Bernstein.P.A.,Chin.D-M.W.Using Semi-Joins to Solve Relational QueriesJ.JACM,2005,30(4:309317Research on Speech Recognition Call MatLabBased on HTKZHANG Ge,YAN Huan,YIN Jing-hua(Harbin University of Science and Technology,Harbin 150080Keywords:HTK;HMM Model;Acoustic ModelIntroduces t

16、he speech recognition call MatLab based on HTK under HTK theory.The HTK soft -ware is used to build up HMM which can train and recognise the recorded corpus.Modifies the parameters (including voice features,acoustic models and so on of the HMM which needs to take advantage of the compute speed and p

17、rogram to save time by means of the MatLab ,and shows the result of the various parameters in the simulation picture which analyzes the influence of rate on the speech recognition system,improves the rate of speech recognition so as to achievethe better effect.Abstract:Research on Query Optimizing i

18、n Distributed DatabaseBased on Semi-Join OperatingYU Yi(College of Computer and Information ,Anhui Polytechnic University ,Wuhu 241000Keywords:Distributed Database;Query Optimizing;Semi-Join Operating;The distribution of distributed database system and redundancy of data distributed has in -creased much complexity to the setting of enquiry,so the optimization for the setting of enquiry distributed seems