分布式数据库的查询优化算法概论

程鹏 周小琳

沈阳理工大学 辽宁 沈阳 110000

1 数据库概述

分布式数据库系统是以集中式数据库作为基础的一种计算机网络技术，不同的是能够分散存储在网络不同场所，存储场所不同对数据处理能力也存在一定的差异。在目前有两种分布式数据库系统：一是在逻辑上结构完整而物理上应用网络技术使其分散的多个数据库集群连接，并通过使用数据库管理软件管理分布式系统。该系统用途比较单一，适合比较小的部门;另一种形式是在逻辑和物理上都是分散开的，该系统可容纳相比差异较大的多个数据库，适合较大数据库集成[1]。

2 分布式数据库查询优化的目的

有两个实现分布式数据库的查询优化的主要目的：一是缩短查询数据所需的时间；二是降低查询资料所需的费用。因为在分布式数据库的数据查询中数据量大且复杂，所以需要的时间、费用相比集中式来说是更多。因此优化分布式数据库查询以时间、费用为出发点，尽可能在缩短时间、降低费用的基础上实现优化。

3 优化分布式数据库查询的基本方法

3.1 基于半连接操作的优化算法

数据库中的连接操作会产生冗余数据，基于半连接操作优化算法是通过使用半连接操作减少不必要的数据传输，避免产生数据冗余。代表算法有：①二次劈开缩减算法[2]：通过使用二分劈开条件（二分条件选择将决定数据在两个站点是否等分），将完全半连接中的缩减关系分成两半。后将相同条件的数据传输到相同站点进行对应的连接操作，利用系统的并行性得到两个站点的连接结果，最终提高了整体查询效率。②SDD-1 算法[3]：基本算法是通过估计缩减程序的因素，使用迭代得到的有益半连接计算，得出半连接缩减程序集合，由合集给出最收益策略，后优化算法是对基本算法求得的解进行修正，最终查询结果将由所有站点的数据整合而成。

3.2 基于直连接操作的优化算法

对于半连接操作而言，在直接连接操作中局部处理代价更受重视,但比较少考虑数据传输的代价。该策略的代表算法有：①分片复制算法：首先选择数据库系统的一组站点，将查询中的某一个关系进行分片并将分片片段都传送到预定站点中，最终结果将是每个预定站点返回结果的集合。②Hash划分算法：首先选取合适的Hash 函数，后对关系的某一个属性或几个属性集合的元组值进行Hash 计算，把相同计算结果的关系元组存放在相同的站点上，关系元组因此都被分散放在不同的站点上，进而得到相应关系的水平片段。

3.3 基于查询图的优化算法

利用贪心算法构造出代价模型的查询图，并实现数据库查询是该类算法的基本思想。Kruskal 算法对非链接型查询图的优化效果较好，该算法对不同查询图中都需要构造最小生成树即在图中找到代价最小的序列。该算法对不同查询都可以找到最小代价序列，可以实现最大程度优化。

3.4 基于粒子群算法

在多表连接的查询特征基础上,将粒子树形编码的分布式数据查询方式。使用粒子群算法优化后的查询策略比原始的查询策略的执行代价低，有效地增加了系统的查询效率。为了进一步提升效率，又提出了多连接粒子群优化算法，该算法能够在更复杂多连接查询优化问题中得到应用。

3.5 遗传算法

分布式数据查询时不仅要考虑数据的分布与冗余，而且要考虑站点间的通信代价以及计算机的并行执行能力、时间成本等。近年来，学者们把粒子群算法、人工免疫算法、人工鱼群算法等应用于分布式数据库查询中。这些启发式算法在一定程度上提高了分布式数据库查询优化效果。遗传算法是一种并行、高效、全局搜索算法，在数据库查询优化过程中能够获取与积累经验，并能够在查询过程中自适应地对搜索过程进行控制，获得最优解。查询时遗传算法个体在求解，不断根据问题域中的适应度值，进行选择、交叉、变异等遗传操作，找到最优查询方案。步骤如下：①随机初始化n个个体作为初始种群，设置w、μ、α等参数的值，对初始种群进行评价，记录最佳个体的适应度值。②设置初始样本群为空。③判断是否需要重新取样，若需要，转到步骤4，不需要，转到步骤6。④根据条件采样方法进行取样，评价样本中的所有种群，标记所有比当前种群好的种群组成种群集合J。⑤得出当前最优的变异率。⑥交叉、变异操作。⑦更新当前种群，并对其进行评价，记录最佳个体的适应度值。⑧判断是否满足结束条件，若满足，结束，不满足，则转步骤3。按照步骤3～8进行3次迭代，在进化结束后，当前种群中的最佳个体即为要找的最优查询执行计划，按照该查询执行计划查询，整个查询过程得到优化。

4 结束语

本文主要叙述了分布式数据库的概念、查询优化的目的和优化查询的方法等内容，并且对查询优化中的方法策略进行了简单的介绍。查询优化算法不是通用的，影响查询算法效率的主要因素包括：是否可以满足大数据量的需求；是否可以为全局或局部优化；是否可以满足复杂性的需求等。在不同的查询问题中，选择方案使查询优化算法可以达到最优为目的。