分布式数据库系统是数据库系统与计算机网络相结合的产物,它主要研究在计算机网络上如何进行数据的分布和处理。对于查询操作,若是在分布式环境中,由于查询涉及的关系通常被分片或复制在多个站点中,所以计算代价时不仅要考虑CPU 和I/O 的速度,还要考虑数据在站点间通信时产生的网络传输代价。由于查询中的连接操作需要的通信代价较高,所以,为了使分布式数据库能更有效地处理连接,国内外学者一直在进行这方面的研究,形成了各种不同的算法。其中,广泛使用的一种方法就是基于哈希划分的连接优化算法。经过哈希划分后的每一个关系根据哈希函数值被划分到不同的片段,并存储在不同的站点中。不同关系通过相同的HASH 划分后,在连接时将保持站点依赖。但是,当多个关系连接时,一般又都存在着重哈希划分问题。重哈希划分将大大地增加站点间的通讯代价。虽然前人也提出了一些代价模型和算法,以减少重哈希划分次数,但这些算法要么存在局限性,要么在查询规模变大时得不出满意的优化结果。本论文通过阅读大量文献,首先描述了各种分布式数据库的连接算法,然后对基于哈希划分的分布式连接算法进行了详细讨论,特别是对CHAIN 算法和Kruskal 启发式算法进行了较深入的分析和研究,并在此基础上引入了一种基于查询图分割的启发式哈希划分连接算法。该算法将查询图分割成若干查询块,然后对相应查询块分别进行优化,以获得较好的优化结果。它的主要特点为:①分别引入了边界点和查询块的概念;②在对查询图进行分割时,引入了判断边界点的两个准则;③算法中所有连接操作的费用都是以基于哈希划分的代价模型来计算的;④整个算法运用了回溯的思想;⑤算法应用了Kruskal 启发式算法和CHAIN 算法对相应查询块进行优化;⑥利用算法得出的优化结果,连接操作可在站点间并行执行。该算法对查询图进行深度优先搜索,产生各个边界点及相应的查询块。然后利用Kruskal 启发式算法对特定的查询块进行优化。当一轮遍历结束后,算法将重新构造一个新的查询图,接着对该查询图以深度优先搜索,重复以上各步操作,直到查询图不能再分割为止。论文最后对本算法进行了实验验证,实验结果表明使用该算法产生的关系连接序列花费的代价比传统的Kruskal 启发式算法更小。