本文首先介绍了分布式数据库系统的基本概念,然后简要描述了分布式查询的处理过程;重点描述了各种分布式数据库的查询处理及优化算法,如基于关系代数等价变换规则的优化算法、基于连接的优化算法、基于半连接的优化算法等。然后对基于Hash划分的分布式连接算法进行了详细讨论。特别是对CHAIN算法和Kruskal启发式算法的优缺点进行了较深入的分析和研究,以此为切入点,采用回溯法思想,对原有算法进行了改进。该优化算法对查询图进行深度优先搜索,产生各个边界点及相应的查询块。然后利用Kruskal启发式算法对特定的查询块进行优化。当一轮遍历结束后,算法将重新构造一个新的查询图,接着对该查询图以深度优先搜索,重复以上各步操作,直到查询图不能再分割为止。论文最后对本算法进行了实验验证,实验结果表明使用该算法产生的关系连接序列花费的代价比传统的Kruskal启发式算法更小。