基于半连接策略的分布式数据库查询优化理论研究及应用

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

1.1课题背景和意义

1.2国内外研究现状与水平

1.3研究内容

第二章分布式数据库与分布式查询处理及优化

2.1分布式数据库的定义

2.2分布式数据库系统的组成

2.3分布式数据库系统的功能

2.4分布式查询处理

2.4.1分布式查询处理过程

2.4.2分布式查询优化的目标

2.4.3分布式查询优化的代价估算

2.5分布式查询的运算、分类与层次结构

2.5.1关系的运算

2.5.2分布式查询的分类

2.5.3分布式查询处理的层次结构

2.6分布式查询的一般优化过程

2.6.1查询树(Querytree)

2.6.2分布式查询的一般优化过程

2.7本章小结

第三章基于半连接策略的分布式查询优化

3.1直接连接策略

3.2半连接策略

3.3几种多关系半连接查询优化算法

3.3.1 AHY算法

3.3.2 SDD-1算法

3.3.3二分劈开缩减算法

3.4本章小结

第四章 KPSJ查询优化算法

4.1获益函数模型

4.2 PERF连接

4.3 Kruskal算法

4.4 KPSJ算法的实现

4.5 KPSJ算法的理论证明

4.6本章小结

第五章查询优化技术在进销存管理系统中的应用

5.1系统概述

5.2改进方案及传输代价分析

5.2.1 KPSJ算法的传输代价

5.2.2 PAP算法的传输代价

5.3实验结果

5.4本章小结

第六章总结与展望

6.1工作总结

6.2工作展望

参考文献

致 谢

攻读硕士学位期间研究成果