连接树生成算法主要应用于数据库查询处理与优化过程中,对数据库的查询效率起着决定性的作用。算法将无序的查询图转化为不同连接顺序的连接树,并根据代价估算的方法选择最优连接树,从而缩短查询所需的时间。本文主要研究了关系数据库中多连接查询问题涉及的连接树生成算法,实现了两种基于动态规划的连接树生成算法DPsize和DPsub,并通过对两种算法结构和性能的分析,设计并实现了一种新型的基于动态规划的连接树生成算法DPccp。算法DPsize通过自底向上的增加关系集中基关系的数量生成连接树,算法DPsub以二进制数的形式表示不同的关系集,并按照二进制数增长的顺序生成连接树。本文通过对两种算法的实现与分析发现并没有一种算法能够同时对链型查询图、环型查询图、星型查询图、团型查询图都达到较高的效率,并由此设计和实现了算法DPccp。算法DPccp以提高两种算法最内层循环的效率为突破口,通过查询图连通子图的快速枚举有效的提高了连接树生成的效率,并以实验的方式对其性能进行了分析。实验结果表明:在以关系结点数为2到10,形状为链型、环型、星型、团型的查询图作为输入时,算法DPccp执行所花费的时间总能达到最优或接近最优,并且在实用性更高的星型查询图实验中,表现出了最优效率。