基于SDD-1算法的分布式数据库查询优化策略的研究

摘要：分布式数据库系统由于数据的分布和冗余使得分布式查询处理增加了许多新的内容和复杂性，因此分布式查询处理的策略显得尤为重要。本文介绍了基于SDD-1算法的查询策略的特点，并提出存在的问题及改进方法。

关键词：分布式数据库；查询策略；SDD-1算法

中图分类号：TP311文献标识码：A文章编号：1007-9599 (2010) 16-0000-01

The Distributed Database Query Optimization Strategy Research on SDD-1 Algorithm

Li Ertao

(Economics&Management College of Anhui,Hefei230059,China)

Abstract:Distributed database system has dealt with and increase a lot of new content and complexity because of distribution and redundancy for data distributed to inquire,so the query strategy seems particularly important.This text introduced the characteristics of query strategy which based on the SDD-1 algorithm and discuss the defeat and improving methods.

Keywords:Distributed database;Query strategy;SDD-1 algorithm

分布式数据库系统是数据库系统与计算机网络系统结合的产物，具有数据独立性、集中与自制相结合的控制机制、存在适当的数据冗余度、事务管理的分布性等特点。在分布式数据库系统中，数据独立性除了数据的逻辑独立性与物理独立性外，还有数据分布透明性。数据分布透明性指用户不必关心数据是如何被逻辑分片的（数据分片透明性），不必关心数据及其片段是否被复制及复制副本的个数（数据复制透明性），也不必关心数据及其片段的物理位置分布的细节（数据位置透明性），同时也不必关心局部场地上数据库支持哪种数据模型。有了分布透明性，用户的查询程序书写起来就如同数据没有分布一样，使系统使用起来更简单、有效。

一、分布式查询策略的基本特点

在分布式查询处理技术中，查询策略的基本类型通常包括两类：针对查询执行代价的策略和针对查询响应时间的策略。针对查询执行时间代价进行优化策略的目标是使查询执行所使用的系统资源尽量地少，从而降低整个系统开销。针对查询响应时间优化策略的目标是尽量减少查询的响应时间，而不计较系统资源的耗费。

查询优化有两种基本方法：第一是查询转化，即以不同的顺序执行关系操作，如连接和投影操作；第二是查询映射，即使用一系列高效的算法来存取各种设备和实现关系操作。即查询映射是针对关系的存取方法和操作的执行算法进行决策，而查询转化则是针对操作执行的顺序及不同站点之间数据流动的顺序进行决策。

二、SDD-1算法

SDD-1算法由两部分组成：基本算法和后优化。基本算法是根据评估所缩减程序的费用，效率，收益估算等几个因素，给出全部的半连接缩减程序集，决定一个最有益的执行策略。主要包括三个基本步骤：（1）初始化：已准备好从查询数转换的优化模型，且所有关系已完成局部缩减。（2）优化：根据初始条件，构造可能的半连接缩减程序；按半连接缩减程序的静态特性表，分别计算其代价和产生的益处，从其中选取一个半连接程序，设为S；以S完成缩减以后，又用重新产生的一组新的静态特性表再进行计算，再从其中选取一个合适的半连接程序，但每一个都只做一次；循环下去，直到没有半连接缩减程序为止。（3）结束：以最后一次缩减关系的静态特性表为基础，进行费用计算，选择场地。后优化是将基本算法得到的解进行修正，已得到更合理的执行策略。包括两种修正，一种是如果最后一次半连接程序缩减关系的所在场地恰好是被选中的执行场地，则最后一次半连接可以取消。另一种修正是在基本算法的流程图进行修正，因为某一个半连接缩减程序的代价可能很高，就必须修正半连接的操作序。

算法：SDD-l-QOA

input：QG：query graph with n relations；statistics for each relation

output：ES：execution strategy

begin

Eslocal-operations（QG）

modify statistics to reflect the effect of local processing

Bs

For each semijion SJ in QG do

if cost（SJ）

BS

end-if

end-for

while Bs≠∮ do

begin

SJmost-beneficial（BS）{SJ：semijion with max（benefit―cost）}

BSBS-SJ {remove SJ from BS}

ESES+SJ {append SJ to e ecutJon strategy}

但是，SDD-1算法存在一个严重问题，那就是它的算法的复杂性。当元组数目很大时，进行查询搜索的代价迅速增加，使系统无法承受。为此，我们在此基础上对它进行改进，降低它的时间复杂度。我们提出的改进算法描述如下：假设已经建立执行策略ES，有益半连接存储表BS表。

（一）置ES为空，读取并行参数值P；

（二）计算所有的有益半连接并加入BS表中；

（三）选择最有益半连接x和比x小P范围内的有益半连接，若这些有益半连接涉及到的关系有重复者，则去掉其中较小的有益半连接，将最终得到的有益半连接从BS表中删除并加入ES中；

（四）判断ES是否包含所有有益半连接，是则输出此执行策略，否则执行下一步；

（五）调整统计数据；

（六）转到第（二）步。

三、结束语

经过实验验证，采用改进的SDD-1算法对多关系查询进行优化后，不但减少了通信代价，而且提高了查询执行的并行能力。所以当查询涉及到的连接个数较多时，应用改进的SDD-1算法，通过在优化过程中添加并行参数，能很好的提高了SDD-1算法的并行执行能力。

参考文献：

[1]解飞,唐培丽,魏宁.基于数据立方体的关联规则挖掘方法研究[J].气象水文海洋仪器,2008,1

[2]于红,王秀坤.基于值的分布式查询优化算法[J].大连理工大学学报,2005,3