本文首先介绍了分布式数据库系统的基本概念，如分布式数据库系统的模式结构及体系结构、数据分片的原则及分类、数据分布的策略等；然后简要描述了分布式查询的处理过程和分布式查询的一些优化方法，如基于关系代数等价变换规则的优化算法、基于连接的优化算法、基于半连接的优化算法，接着本文重点研究了分布式查询的常用优化算法，基于查询图的启发式算法和基于查询图划分的启发式算法。分布式数据库系统是与计算机网络相结合的产物，其中一个主要研究问题是在计算机网络上如何进行分布式数据的查询处理。对于分布式查询操作，由于查询涉及的多个关系通常被分片或复制在多个站点中，所以查询时需要对多个站点上的关系进行连接操作，那么在计算查询代价时不仅要考虑CPU和I/O的速度，还要考虑数据在站点间通信时产生的网络传输代价。分布式数据库系统的查询代价的估算方法一般表示为：查询代价=I/O代价+CPU代价+通信代价。在远程通信网或数据传输率较低的系统中，站点间的数据通信往往会比查询执行中的I/O及CPU开销大的多，因而作为首要的优化目标来考虑。论文中的查询算法优化也是针对站点之间的通信代价。 由于分布式查询中站点间的连接操作需要的通信代价较高，所以，为了使分布式数据库能更有效地处理连接，国内外学者一直在进行这方面的研究，形成了各种不同的算法。其中，广泛使用的一种方法就是基于哈希划分的启发式连接优化算法。经过哈希划分后的每一个关系根据哈希函数值被划分为不同的片段，并存储在不同的站点中，这些关系在连接时将保持站点依赖。但是，当多个关系连接时，一般又都存在着重新哈希划分的问题。重新哈希划分将大大地增加站点间连接的通讯代价。虽然前人也提出了一些代价模型和算法，以减少重新哈希划分次数，但这些算法在查询规模变大时得不出满意的优化结果。 本论文首先描述了各种分布式数据库的查询连接算法，然后对启发式连接算法和基于查询图划分的启发式连接算法进行了详细讨论。在分布式查询中，针对基于哈希划分的查询优化问题在理论上都是采用启发式算法来解决的。然而启发式算法仅在查询图是重连通且结点数较小的情况下才能取得较为理想的结果，而对于那些拥有较多结点数或组织结构较复杂的查询图，往往就得不到满意的结果。基于查询图划分的启发式连接算法在查询拥有较多结点数时可以对查询图进行划分，然后对划分后的子查询图并行连接，减少查询的时间，提高查询效率。本文详细研究了这两种算法，并编写程序实现了这两种算法。最后，在这两种算法的基础上进行了改进，改进后的算法在边数为1的查询块较多的条件下能够提高关系连接的并行性，获得较好的优化结果。 改进后算法与原来的基于查询图划分的启发式算法作比较，在基于查询图划分的启发式算法中，只是将查询块边数大于1的查询块并行连接，而改进后的算法将边数为1的查询块也并入并行连接范围，从而使查询时间更小，查询效率更好。 论文最后给出对基于查询图的Kruskal启发式算法、基于查询图划分的启发式连接算法和本文所做的改进算法的主要函数。并对这三种算法进行了实验验证，实验结果表明在某些情况下使用改进算法产生的关系连接序列花费的代价比传统的启发式算法和基于查询图划分的启发式连接算法更小。