随着“信息爆炸”时代的到来，分布式数据库得到了广泛应用。查询作为数据库应用的核心功能，在分布式环境中更具有复杂性。如何在分布式环境上进行优化查询，是衡量分布式数据库系统性能的关键。数据冗余存储的增加，局部站点处理数据能力的差异，逐渐成为当前分布式数据库应用中不可回避的问题，这对只注重传输代价的查询代价传统模型提出了新的“挑战”。另外，当连接关系个数较多时，应用传统优化算法，解决分布式查询优化问题，存在效率差或易陷入局部最优等缺点。 在国内外研究的基础上，本文提出了一种新的查询执行计划代价模型。它包括关系副本选择、查询多连接次序、操作站点的选择、数据的传输及数据局部处理等因素，更能准确地表示分布式数据库查询执行代价。然后，对模型进行了详细设计与分析，应用构建全局数据字典和状态动态数据字典的方法，研究了模型的实现。 针对遗传算法解决多连接查询优化问题时，容易陷入局部最优等缺点，从遗传算子优化组合的角度，把具有良好全局搜索性能的遗传算子与具有良好局部搜索性能的遗传算子优化组合应用，采用分阶段搜索策略，构造了优化组合遗传算法。并从理论上分析了搜索性能的提高，证明了算法的全局收敛性，大量仿真实验表明，该算法改进了遗传算法的整体寻优性能，同时有效地控制了早熟收敛。 最后，应用优化组合遗传算法，从算法的每个环节进行分析与设计，精心组织数据结构，实现了基于新查询代价模型的分布式数据库查询优化。与动态穷尽规划经典算法进行比较，实验结果表明了此查询代价模型的有效性和优越性，本文的查询优化算法具有更好的寻优能力。另外，通过对时间复杂度的分析，表明算法是符合多项式收敛的。