摘 要：本文对最小生成树法在分布式数据库多元连接中的应用进行了阐述和分析，并利用分布式数据库数据的分布性对最小生成树法进行了改进。提出了基于最小生成树法的连接图划分方法将连接图划分成多个子连接图，提高连接操作的并行性，从而使得响应时间得到减少。
关键词：分布式数据库；多元连接；查询优化；最小生成树；并行性
1，引言
分布式查询处理是用户与分布式数据库系统的接口，也是分布式数据库主要研究的问题之一。在分布式数据库系统中，常以两种不同的目标来考虑查询优化，一种目标是以总代价最小为标准，总代价包括CPU代价、I／O代价和数据通过网络传输的代价，另一种目标是以每个查询的响应时间最短为标准[1]。在远程通信网络中，各站点之间的数据传输速度比单机情况下内存与磁盘访问的数据传输速度要慢，在这种情况下，通常以减少传输的次数和数据量作为优化的目标；在高速局域网中传输时间比局部处理时间要短得多，在这种情况下，以响应时间作为优化目标。
在分布式数据库中，分布式多元连接查询处理占有很大的比重，一个连接算法的好坏直接关系到分布式数据库的执行效率[2]。对于多元连接操作，有人利用图论中的最小生成树算法来生成一种连接操作的顺序以使总代价最小，但是这种方法并没有利用数据的分布性特点。本文将利用分布式数据库的这一特点，在最小生成树法的基础上进行改进，提高查询的并行性。
2，最小生成树法
给定查询Q，设其所涉及到的待连接的关系为{Rl，R2，⋯ R n}，用图G(V，E)来表示这个关系以及它们可能的连接，其中V={R1，R2 ⋯ R n}，E={< Ri ，Rj>}，估算连接代价作为边上的权。对于n个关系的连接图可以建立许多不同的生成树，每一颗生成树都代表一种连接方案。
最小生成树法可分为如下两个过程[1]：
(1) 预处理；根据半连接操作和直接连接操作代价估算模型分别计算Ri 和Rj 的连接代价，在所估算的两种代价中选取小的连接代价作为连接图相应边上的权值。
(2) 构造最小生成树；对于边稀疏的连接图可选择Kruskal算法构造最小生成树，反之可用Prim算法构造最小生成树。
整个算法描述如下[1]：
(1) 计算并依据连接代价最小的原则确定连接图各边的权。
(2) 输入连接图信息。
(3) 用Kruskal算法求最小生成树，并输出。
算法的主要步骤是每次从边集中选取一条未经处理的有最小权的边<Ri ，Rj >
3, 改进的最小生成树法
由于最小生成树法未利用到分布式数据库数据的分布性，因此本文将提出一种基于最小生成树的连接图划分方法来将连接图划分为多个子连接图，这样不同子连接图内的连接操作可以并行进行，这样就提高了查询的并行性，也就减少了响应时间。
连接图的划分方法描述如下：
(1) 根据半连接操作和直接连接操作代价估算模型分别计算各边的连接代价，在所估算的两种代价中选取小的连接代价作为连接图相应边上的权值，然后选择所有连接代价中最小的一个边（设为RiRj），将它划为一组T1。
(2) 在剩下的连接中选择代价最小的一个边（假设为RmRn），若该边的两个节点中有一个节点已属于已有的组Ti，而另一个节点不属于任何一组，则将这一条边并入Ti；若两个节点均不属于任何一组，则单独作为新的一组Tj；若两个节点均属于不同的组，则去掉该边。
(3) 重复步骤(2)直到所有的边都已分到相应的组。
经过以上处理，就将连接图划分为多个子连接图，子连接图中的连接按照最小生成树法进行。所有子连接图中的连接操作都可以并行进行，随着连接操作的进行，子连接图中的节点最终将合为一个，这样又形成一个连接图，然后利用最小生成树法即可将整个查询操作进行完毕。整个过程如图1所示。
改进最小生成树算法对连接图进行了划分，提高了整个连接操作的并行性，减少了响应时间，但由于各边的权值随着连接的进行是在动态变化的，而改进最小生成树算法在划分连接图时将连接图划分为并行操作的多个连接图，所以很有可能使总代价并非是最小的。不过由于整个方法从头至尾都遵循最小生成树法选择最小权值边的特点，这样就保证了总的代价并不会是最大的。
4，结束语
本文对最小生成树法在分布式数据库多元连接中的应用进行了阐述和分析，并对最小生成树法进行了改进以提高连接操作的并行性，由此来减少响应时间。通过实践验证，这种方法不仅可以应用到局域网的查询中，而且对于要求事务并行处理的系统同样适用。
参考文献：
[1] 闫丽,华彦涛,王艳辉. 一种基于半连接的分布式数据库多元连接查询优化算法. 通化师范学院学报. 第26卷第6期:22-23
[2] 胡枫,于福溪. 最小生成树算法在多元连接中的应用及算法分析. 青海师范大学学报(自然科学版), 2004年第2期:38-40
[3] 胡枫,陶世群. 一种分布式数据库多元连接查询优化算法及改进. 计算机工程与应用,2001(16):125-127
[4] 钟武,胡守仁. 一种改进的多连接查询优化方法. 软件学报,1998(2)
[5] 王意洁,王勇军,卢锡成. 基于半连接的并行查询处理算法的研究. 软件学报,2001(2)
