一种分布式数据库多元连接查询优化算法及改进

《一种分布式数据库多元连接查询优化算法及改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种分布式数据库多元连接查询优化算法及改进胡枫#陶世群!#（青海师范大学计算机系，西宁?#"""?）!（山西大学计算机系，太原"("""%）@’A:4B：+/CDE!%($-,F摘要论文对于分布式数据库中的多元连接查询提出了一种优化算法。该算法产生的操作序列具有全局优化特征。在远程网中，采用最小生成树算法，生成最佳的连接序对能使得总的代价达到最小。而在局域网中，采用改进的最小生成树算法，生成尽可能多的并行连接序对，最大程度地应用并行性，使得响应时间最小。关键词分布式数据库多元连接查询优化最小生成树并行性文章编号#""!’?((#’（!""#）#%’"#!1’"(文

2、献标识码G中图分类号HI(##!"#$%&%’($%)*!+,)-%$.&(*/0&#-)12/3)-45+$%67)%*852-%29)3:%9$-%;5$2/:($(;(92<5=2*,>?()@.%A5*B#（5,JF$3D93AJ/F,;，K4-L+:4M3;A:BN-4O,;=4FP，Q4-4-L?#"""?）!（5,JF$3D93AJ/F,;=94,-9,，R+:-S4N-4O,;=4FP，H:4P/:-"("""%）!;9$-(C$：H+4=J:J,;J;,=,-F=:-,T3JF4A4>:F43-:BL3;4F+AD3;A/BF4’U34-V/,;

3、4,=3D<4=F;4W/F,<<:F:W:=,$H+,:BL3;4F+A+:=LB3W:B3JF4A4>:F43-J;3J,;FP4-F+,93/;=,3D<,F,;A4-4-LU34-=,V/,-9,=$X-F+,F,B-,F，Y,/=,F+,:BL3;4F+A3DA4-4ZA/A=J:--4-LF;,,，:-,F+,F3F:B93=F$，X-F+,B39:B-,FT3;[，T,L,FJ:;:BB,BU34-=,V/,-9,=:FA3=FWP/=4-L4AJ;3O,<:BL3;4F+A，/F4B4>4-LA3=F93-9/;;,-9P;,

4、,;,=J3-=,F4A,$D2EF)-/9：54=F;4W/F,<<:F:W:=,，/BF4’U34-V/,;4,=，K/,;P3JF4A4>:F43-，4-4A/A=J:--4-LF;,,，I:;:BB,B#引言化的算法——最小生成树算法和改进的最小生成树算法。多元查询优化是分布式数据库系统中的核心问题。分布式查询查询即涉及多个片段上的查询。由于分布式数据库数据分布与处理就是将一个分布式数据库上的高级查询翻译成局部数据冗余的特征，多元连接查询会涉及多个不同的结点上的片段，库上的一个有效的低级执行计划。翻译要做到以下两点：第一，而且最大程度地考虑各个结点的并

5、行性。查询优化也变得更为必须产生输入查询的正确表示，以便执行计划能产生预期的结复杂。等值连接与自然连接是应用最多的连接操作。自然连接果。这方面的形式化基础是关系演算和关系代数，以及和关系与等值连接无本质区别，可以通过修改关系的属性名把等值连代数相关的转换，规则之间的等价性。第二，必须对执行计划进接操作转化为自然连接操作。所以研究自然连接操作的查询处行优化，即必须对代价函数最小化。对以上两个方面孤立成两理具有普遍意义。多元自然连接操作是具有##]#!]⋯]#-个顺序的步骤：数据的局部化和全局化。数据局部化是将一个的关系代数表达式。由于连接操作满足结合律和交换律，多重

6、分布式数据库上的代数查询转换成一个等价的段查询，并通过连接操作可以按任何的顺序执行。寻找最佳的一个执行顺序使代数转换来作进一步的简化。全局查询优化通过决策操作的顺总代价最小是全局优化的关键。因此，对于多元自然连接操作，序，结点间的数据移动，以及数据库操作的分布和局部算法的在远程网中，作者提出最小生成树算法生成一种连接操作的顺选择来为输入的分段查询计划产生一个优化的执行计划，其关序使总代价最小，而在局域网中提出改进最小生成树算法生成键是如何选择操作的执行顺序。选择查询操作的重点是连接操尽可能多的并行连接序对以使响应时间最小。作的顺序，因为这类操作可能会涉及多个结点上

7、的片段，是最费事的操作。!数据库的统计模型在文献&#’()中，*+,-和./提出了一种新的等连接操作结设567##，#!，⋯，#-8为关系的有序集合，$67$#，$!，⋯$%8是果的估算模型，并借助它来估算连接操作作为缩减器带来的收系统所包含的场所集合，每一个关系都是根据一定的分布准则益，他们采用局部优化方法。文献&0’1)在此基础上分析了收益划分为若干个段分布在多个场所中，且假定各段之间无冗余分之和与234-缩减器执行次序的关系，提出了复杂度为!（"!）的布。用以下统计数据库近似描述数据库的一个剖面：优化算法，该算法除考虑采用局部收益最大的234-操作作为（#）

8、每个段#&