论文摘要
尽管很多研究者做了大量的工作,相比传统的集中式关系型数据库技术的成功,分布式数据库查询优化依然面临很多未能得到很好解决的问题,如:在不知道中间结果的情况下,如何选择最好的半连接;如何选择最优半连接顺序;算法的时间复杂度及空间复杂度太大。这些正是本文要研究、解决的重点。本文首先介绍了国内外对于分布式数据库查询技术的研究状况和研究方向,以及国内外常用的一些典型优化算法,如SDD-1算法、二分劈开缩减算法、W算法、遗传算法等。阐述了分布式数据库的定义、功能及分布式查询优化的目标和查询总代价,总代价=CPU代价+I/O代价+通信代价。分析了连接分布式多关系查询的两种连接策略:直接连接和半连接的操作过程、适用场合,重点研究、比较了直接连接和半连接的传输代价。直接连接注重局部处理代价,较少考虑传输代价,半连接策略将传输站点所有数据变为只传输参与连接的中间数据,减少了网络传输量,从而大大减少了查询总代价。因此多关系半连接的查询优化是本文研究的重点。在研究了大量连接算法及相关文献的基础上,本文选择了半连接算法中的SDD—1算法、PERF算法以及直接连接算法中的Kruskal算法作为研究基础,分析了几种算法的特点,并结合其优点,提出了改进的分布式多关系半连接查询优化算法（本文简称为KPSJ算法）,最后分析了它的时间复杂度,证明了在获益正确的情况下,其半连接顺序是最优的。本文在本单位的进销存管理系统中使用了KPSJ算法,通过对原来使用的直接连接算法及PAP算法、KPSJ算法的传输代价的分析、计算,以及查询平均执行时间的实验,证明了KPSJ算法在减少中间结果数据量,降低网络通信代价,进而降低查询总代价方面效果明显。