分布式数据库查询优化算法的研究

吴军　张琳

【摘 要】由于分布式数据库需要在网络上传输数据，因而数据查询比较复杂，高效地查询是分布式数据库研究的热门问题。本文首先介绍了什么是分布式数据库，随后介绍了分布式数据库中查询优化的若干知识，最后总结了目前5种主流的查询优化策略。

【关键词】分布式数据库；查询优化；算法

1 分布式数据库概述

分布数据库是指数据分存在计算机网络中的各台计算机上的数据库，该数据库具备物理分散性和逻輯上集中性特征，可以将其看作计算机网络和数据库系统相结合的数据库系统。

2 查询优化概述

查询优化是数据库研究领域中一个热点问题。分布式查询处理问题最初是由E-Wong提出来的，其实质是通过数据分析和数据交互，将分布式查询这一问题转化为局部的数据条目查询。

全局查询的定义是使用者通过使用全局查询评议，能够对多个物理上分散的数据库同时进行有效查询的一种查询方式。分布式数据库的查询优化主要从两个方面来着手，一方面是降低查询总代价，另一方面是缩短响应时间。

1）总代价：与CPU代价、I/O代价和通信代价。

2）响应时间：主要和通信时间以及局部处理时间有关。

3 五种查询优化算法

3.1 基于关系代数等价优化算法

该类方法的基本思想是将查询问题等价转变为关系代数表达式，然后根据关系代数表达式生成相应的查询语法树。通过分析上述语法树的特点，可以利用相应的等价规则来进行优化查询[1]。

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

连接操作是分布式数据库中经常使用的操作，该操作时间代价很高。在一些算法中，通过正确使用半连接操作，可以大量减少与连接操作不相关的数据的传输，这些算法被统称为基于半连接操作的优化算法。代表算法有：

1）SDD—1算法[2]：通过迭代得到有益半连接运算，能够大量减少每个站点的运算操作数量，最后将所有站点得到的数据进行整合就能获取最终的查询结果。

2）WPERF+算法[3]：通过减少网络流量来优化查询，但必须保证结果的正确性。

3）二分劈开缩减算法[4]：通过正确的使用二分劈开条件，可以将完全半连接中的缩减关系分成两部分。随之，把具有相同条件的数据传递到一个相同的站点进行相应的链接操作即可。

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

直接连接操作相对于半连接操作而言更为重视局部处理代价，却较少考虑传输代价[5]。该策略的代表算法有：

1）分片复制算法：首先将查询中的某一个关系进行分片，随之将所有的片段都传递到一组预定的站点中，这些站点可以独立的处理该关系的连接操作，最终结果即是每个预定站点返回结果的集合。

2）Hash划分算法：首先选取一个合适的Hash函数，然后对某一个属性或几个属性集合进行Hash操作，根据Hash操作的结果将关系放置于相应的站点上，这样就能够得到相应关系的水平片段。

3）Partition 算法：在多个关系中，如果可以将同一连接属性进行有效的片段划分，便可以通过并行运行来降低响应时间。

3.4 基于查询图的优化算法

这类算法的基本思想是构造出代价模型的查询图，并利用贪心算法实现数据库查询的方法[6]。该算法有两种改进算法：

1）CHAIN算法：对于可以将查询转换为链形结构的查询图中，该算法能够找到最少的连接代价序列，从而便能够降低查询代价。

2）Kruskal算法：对于不同查询图，该算法都需要找到查询图中最少连接代价的序列。也就是说在分布式数据库中，找出查询图最少连接代价。

3.5 基于粒子群算法

以多表连接查询的特征为基础，对粒子进行树形编码的一种分布式数据查询方式。使用粒子群算法优化后的查询策略比原始查询策略的查询执行代价低，有效地增加了系统的查询效率。为了进一步提升效率，文献[7]又提出了多连接粒子群优化算法，该算法能够被正确应用于更为复杂的多连接查询优化问题中。

4 结论

在分布式数据库中，查询优化是一个热门研究问题。本文针对该问题综述了五种优化策略。虽然国内外学者在优化算法做出了大量的工作，但是这些优化策略都存在一定的局限性，还需要新的算法和策略来进一步提升查询优化的效率。

【参考文献】

[1]邵佩英.分布式数据库系统及其应用[M].2版.北京：科学出版社，2005.

[2]聂林娣.分布式数据库查询优化策略研究[J].电脑知识与技术：学术交流，2006（6）：5-6.

[3]冯祖洪，徐宗本.WPERF+：一种有效的分布式查询处理优化算法[J].工程数学学报，2004，21（5）：797-802.

[4]魏士伟，黄文明，康业娜，周娅.分布式数据库中基于半连接的查询优化算法研究[J].计算机应用，2007，27（S1）：34-36.

[5]于秀霞，赵建平.分布式数据库直接连接查询优化算法的研究[J].长春理工大学学报（自然科学版），2005，28（3）：55-57.

[6]尤沛泉.基于查询图的分布式数据库查询优化算法的研究与应用[D].长春理工大学，2011.

[7]陈一栋.分布式数据库查询优化算法研究与实现[D].长沙理工大学，2008.

[责任编辑：田吉捷]