随着数据库规模的日益增大，使用并行处理能力提高数据库的性能已成为数据库发展的必然趋势，这其中并行数据查询优化是一个重要的研究课题。同时数据仓库技术的出现和分析查询应用的剧增，使得数据库中多连接查询优化(MJQO)的重要性越来越突出。多连接查询优化是一个NP问题，是提高数据库系统有效性的关键，同时也是数据库领域的一个没有很好解决的问题，面对日渐复杂的查询应用，传统的system-R优化技术显得更加无能为力。本文的主要内容是采用遗传算法解决并行数据库环境下多连接查询的优化问题。通过对并行多连接查询优化问题的抽象建模，以左深树作为搜索空间，采用有序串编码，设计了适用于MJQO遗传算法的遗传算子和算法结构，并通过实验讨论了算法的有效性以及各种参数设置的合理性，并针对数据仓库典型查询应用提出了启发式改进方法。最后采用多种群的并行遗传算法思想，基于并行数据库的特有并行结构，对通用MJQO遗传算法进行并行设计，并通过模拟实现伪并行遗传算法实验证明了其对解决MJQO问题的诸多改进作用。