Science &Technology Vision
科技视界0引言
近年来，随着计算机网络和数据库技术的发展，对分布式数据库的应用越来越广泛；随着应用不断扩大，数据的查询也越来越复杂，对查询的效率要求也越来越高，因此查询处理成为分布式数据库系统中的一个关键性的问题[1]。在分布式数据库中，由于数据的分布与冗余，使得查询处理中一般需要站点间的数据传递及通信费用，成为查询优化的主要矛盾；另一方面，数据的分布与冗余也增加了查询的并发处理的可能性，从而可以缩短查询处理的响应时间，提高处理速度。总之，分布式查询的规模与优化的因素，都与集中式查询优化不同，因此许多数据库专家学者致力于研究分布式数据库查询优化技术这一重要课题，并且己经在这一领域作了大量的工作，也到了规律，包括一些大家公认的经典算法；然而由于分布式数据库本身的灵活性，要想设计一个算法对于各种情况都是最优的几乎不太现实，只能说设计一个较优的优化算法，它可以解决某一类型的问题[2]。分布式数据库中查询优化是一项复杂问题，已经被证明属于NP 完全问题，至今都没有得到彻底地解决，里面尚有许多问题值得研究和探讨。
1分布式查询优化的目标
分布式数据库系统的查询优化有两种不同的目标：一种目标，是以总代价最小为标准；另一种目标，是以查询响应时间最短为标准，这一点在分布式数据库系统中具有重要的意义。因为分布式数据库系统是
由多台计算机组成的系统，数据的分布和冗余也增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间，加快查询处理速度。在分布式查询优化中也常同时使用这两种标准，根据系统应用的不同，一种作为主要标准，另一种作为辅助标准[3]。在分布式数据库系统中，查询优化包括两个内容：查询策略优化和局部处理优化，而查询策略优化尤为重要。分布式查询策略的优劣将直接影响计算机网络资源耗费的多少。
在集中式数据库系统中，查询优化的目的可以总结为以下三个方面:
1)为每个用户查询寻求总代价最小的执行策略;
2)总代价是以查询处理期间的CPU 代价和I/O 代价来衡量的;3)总代价最小就意味着查询的响应时间最短。
从上可看出，在集中式数据库系统中，一个查询策略的选择是以执行查询的预期代价为依据的。由于系统大都运行在单个处理器的计算机上，所以查询执行总代价为CPU 代价加I/O 代价[4]。而在分布式数据库系统中，由于数据的分布在多个不同的站点上，使得查询处理中需要考虑站点间传输数据的通信费用，所以除了考虑CPU 代价和I/O 代价之外，还应该包括数据在网络上的传输代价。所以在分布式数据库系统中，常以两种不同的目标来考虑查询优化：以总代价最小为标准和以每个查询的响应时间最短为标准。这样分布式查询优化可用以下四个参数来衡量:
1)CPU 代价，即占用的CPU 处理周期，记做Ccpu;2)I/O 代价，记做Ci/o;
3)通信代价，记做Cmsg;
4)传输的数据代价，记做Cbt。
2分布式查询优化的基本方法
在分布式查询处理技术中，查询优化有两种基本方法：第一，是查询转化，即以不同的顺序执行关系操作，如连接和投影操作：第二，是查询映射，即使用一系列高效的算法来存取各种设备和实现关系操作。查询转化是指关系运算集合运算顺序的改变，对查询的性能有重要影响[5]。在多站点下，查询转化可以减少通信量，从而达到减少查询代价的目的[6]。查询映射则是针对关系的存取方法和操作的执行算法进行决策。
2.1查询转化的处理过程
查询转化处理一般经历三个阶段:
1)建立关系代数表达式。根据查询问题，编写关系代数表达式。2)建立查询语法树。根据关系代数表达式，生成查询语法树。3)全局优化。按照优化策略，对查询语法树进行全局优化。优化策略：查询优化策略按以下步骤进行:1)将关系代数表达式转换成选择串接形式。
2)尽可能把选择和投影操作移近树的叶端，即尽可能早地执行选择和投影策略，以得到较小的中间关系，减少运算量。
3)把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择和投影能同时执行或在一次扫描中同时完成。
4)将上述步骤得到的查询语法树的内结点分组。每个二元运算结点与其直接祖先的一元结点分为一组。如果它的子孙结点一直到叶结点都是一元运算符，则并入该组。
5)生成一个程序，每一组结点的计算是程序中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组之前计算。2.2查询优化的三种典型算法2.2.1INGRES 算法
INGRES 算法是动态的优化算法。这个算法主要分为两个步骤:(1)将含有多个变量的查询分解为一系列的只含有一个变量的单关系查询。
(2)通过执行其每一个单关系查询：用启发式的方法选择一个初始化的执行计划，通过中间关系的大小来确定查询执行的顺序。
首先来看分解的详细过程：用一系列的单关系查询qi 取代n 个变量的查询q，就比如:q1->q2->…->qn，其中qi 使用qi-1的执行结果。
它主要有两个基本的动作：分离与元组替换。
分离：查询q 分解成q’和q’’，当q’和q’’有一个共同的量在q’的结果里。
查询分解算法:
break query q into q’->q’’
q:SELECT R2.A2,R3.A3,……,Rn.An FORM R1,R2,R3,……,Rn WHERE P1(R1.A1’)
分布式数据库查询优化方法
赵荣
sql优化的几种方式(中国矿业大学图书馆，江苏徐州221116)
【摘要】本文介绍分布式数据库系统查询优化的目标、策略，着重讨论了一种分布式数据库系统查询优化策略是如何影响查询的，并对分布式数据库系统的查询优化的典型方法进行了分析、总结。分布式数据库系统由于数据的分布和冗余使得分布式查询处理增加了许多新的内容和复杂性，对于一个给定的查询，通常会有多种可能的策略，查询优化就是从这许多策略中出最有效查询计划的一种处理
过程。并针对分布式数据库系统的查询优化，讨论了三个典型的算法:INGRES 算法、System R*算法、SDD-1算法。
【关键词】分布式数据库；分布式查询；查询优化；查询处理策略；算法
【Abstract 】This text introduce the goal and tactics of distributed query optimization,Distributed database system has dealt with and increase a lot of new content and complexity because of distribution and redundancy of data distributed to inquire,it focused on discussing how to impact query on a distributed database system query optimization strategy,and distributed database system of a typical query optimization method has been analyzed and summarized.For a given enquiries,there are usually a variety of possible strategies,query optimization is to identify the most effective plan of a process from the many strategies.On the basis of optimization to the inquiry of the distributed database system,discussed three typical algorithms:NGRES algorithm,SystemR*algorithm,SDD-1algorithm.The goal of this paper is telling us about the problems of distributed database systems such as query processing.
【Key words 】Distributed database;Distributed query;Query optimization;Query processing strategy;Algorithm
120. All Rights Reserved.
Science &Technology Vision 科技视
界AND P2(R1.A1,R2.A2,……,Rn.An)
q’:SELECT R1.A1INTO R1’(R1’是一个临时关系)FORM R1
WHERE P1(R1.A1’)
q’’:SELECT R2.A2,R3.A3,……,Rn.An FORM R1’,R2,……,Rn
WHERE P2(V1.A1,……,Vn.An)
元组替换：用元组的实际值来替换并且简化查询,q (R1,R2,…,Rn)被{q’(t1i,R2,…,Rn),t1i∈R1}2.2.2System R*算法
System R*算法是源于美国CA 州的IBN San Jose Research Laboratory 开发System R*系统,System R*系统是采用直接连接作为查询处理策略的分布式数据库系统，其最重要的目标是提供地点自主权。
当每个地点既能控制由另一个地点上对其数据的访问，也能在不受任何其它地点限制的条件下处理自己的数据时，也就实现了地点自主权。R*系统完全实现了第一个目标。但它仅仅是部分地实现了第二个目标。
R*系统由3个主要部分组成：局部DBMS、提供信息传输的数据通信部分和能协调实现多地点事务处理的事务处理管理程序。局部DBMS 可分为两个部分：存储系统(用于数据的存储与检索)和数据库语言处理器(用于将高级SQL 语句转换成存储系统上适用的操作命令)。R*方案中采用的存储系统叫RSS*，是以系统R 的存储系统为基础。R*各地点通过CICS 的系统间通信(ISC)设备进行通信。每一个R*地点都在一个CICS 地址空间运行，而CICS 控制终端I/O 和信息通信。假定该通信是不可靠的(不能保证所传输的信息总能送到)，但可以假定所送到的信息是正确的、不重复的，并以与发送它们的相同次序接收。一个应用程序在其局部地点执行所有对R*系统的数据库访问请求。所有地点间的通信均在不同地点的R*系统之间进行。因为是R*、而不是应用程序负责为分布式数据定位。这样，在R*环境中不需要远程应用程序。应用地点的事务处理管理程序，把未包括在明确定义的事务处理中的第一个SQL 语句看作是事务处理的开始，隐含地执行一个开始一一事务处理。当用户完成一次会话后，就假定一个隐含的结束一一事务处理，并提交所有已经完成的工作。
R*系统的另一个重要问题是位置透明性(用户并不知道数据的实际位置)。这样，从程序员的观点来看，使用R*系统与使用集中式系统基本一样。虽然在R*系统中引入的附加语言特性极少，但R*系统的
主要成就是在分布式环境中提供了SQL/DS 的大多数功能。在R*系统中,SQL 查询既可以静态地进行编译(n 个执行编译一次)，也可以动态地进行编译(在单个执行前立即进行编译)。前一种情况用于重复查询；后一种情况用于预先不知道的查询。在R 方案中，重复查询的重要性比预先不知道的查询高得多。在这两种情况下，非过程型SQL 语句被转换成访问计划，该计划规定访问关系的次序进行访问的地点，完成每一个操作的方法及在RSS*中检索或处理元组的访问路由。2.2.3SDD-1算法
SDD-1算法由两部分组成：基本算法和后优化。基本算法是根据评估所缩减程序的费用，效率，收益估算等几个因素，给出全部的半连接缩减程序集，决定一个最有益的执行策略，但效率不一定理想。主要包括三个基本步骤:
(1)初始化：已准备好从查询数转换的优化模型，且所有关系已完成局部缩减。
(2)优化：根据初始条件，构造可能的半连接缩减程序；按半连接缩减程序的静态特性表，分别计算其代价和产生的益处，从其中选取一个半连接程序，设为S；以S 完成缩减以后，又用重新产生的一组新的静态特性表再进行计算，再从其中选取一个合适的半连接程序，但每一个都只做一次；循环下去，直到没有半连接缩减程序为止。
(3)结束：以最后一次缩减关系的静态特性表为基础，进行费用计算，选择场地。后优化是将基本算法得到的解进行修正，已得到更合理
的执行策略。包括两种修正：一种，是如果最后一次半连接程序缩减关系的所在场地恰好是被选中的执行场地，则最后一次半连接可以取消；另一种，修正是在基本算法的流程图进行修正，因为某一个半连接缩减程序的代价可能很高，就必须修正半连接的操作序。
SDD-l 算法:
input:QG:querygraph with n relations;statistics for each relation output:ES:execution strategy begin
Es←local-operations(QG)
modify statistics to reflect the effect of local processing Bs<-∮
For each semijion SJ in QG do if cost(SJ)<benefit(SJ)then BS<-BS∪SJ end-if end-for
while Bs≠∮do begin
SJ←most-beneficial(BS){SJ:semijion with max(benefit—cost)}BS←BS-SJ {remove SJ from BS}
Es←ES+sJ {append SJ to e ecutJon strategy}......
SDD-1算法支持关系数据模型。全局关系能以两个步骤分段(首先水平分段，然后垂直分段)，能以冗余
方式存储各段。SDD-1能提供段存储透明性(用户不知道段和段的分配)利用数据语言，即适用于数据计算机的高级过程语言实现关系控制。
SDD-1算法的体系结构是基于三个相对独立的虚拟机：数据模块、事务处理模块和可靠的网络。这种体系结构允许把分布式数据库管理问题分成三个系统，以限制相互的影响。
SDD-1算法存在一个严重问题，那就是它的算法的复杂性。当元组数目很大时，进行查询搜索的代价进迅速增加，使系统无法承受。当然，对于这种搜索模式，可以到最佳的路经去进行查询。为此，我们在此基础上对它进行改进，降低它的时间复杂度。在人工智能里面的A*算法可以引入到SDD-1算法中来，当元组数目不是很大时，可以采用A’算法的思想对它进行查询优化，在此基础上能到最优的方法去进行路径搜索和优化，而当元组数目非常多的时候，还是用以前的方法。
3结束语
分布式数据库系统的查询处理是用户与分布式数据库系统的接口，查询处理策略的好坏直接影响到系统的执行速度。本文通过实例重点讨论了在分布式数据库系统中应用优化策略，减少运算数据量和网络资源的耗费，提高了查询效率。至于对于给定的查询，应该怎样选择好的查询策略，进行分布式查询优化，我们可以根据已有的优化算法和分析各种查询策略的特点来选择一个较好的查询策略。
[1]徐俊刚，邵佩英.分布式数据库系统及其应用[M].北京：科学出版社,2012,4.[2]申德荣，于戈.分布式数据库系统原理与应用[M].北京：机械工业出版社,2011,8.
[3]王丽艳，郑先锋，刘亮.分布式数据库系统及其应用[M].北京：机械工业出版社,2013,2.
[4]吴溥峰，张玉清.数据库安全综述[J].计算机工程,2006,32(12).
[5]O’NeilP,O’NeilE.数据库原理、编程与性能[M].北京：机械工业出版社,2002.[6]王月海，何丽，孟丹，张艳苏.数据库基础教程[M].北京：机械工业出版社,2011,8.
[责任编辑：王迎迎
]
(上接第176页)果。试验后采集参数的二次论证工作是取得好的地震资料的重要保证。
[1]吕公河，等.黄土塬地区地震勘探采集技术[J].石油物探,2001,40(2)..
[2]程建远，等.三维地震在西部戈壁地区的应用[J].中国煤田地质,2001,40(2).[3]程建远，等.矿井多元地质信息集成系统及其应用[M].北京.煤炭工业出版社,2004.[4]邓志文.复杂山地地震勘探[M].北京：石油工业出版社,2006.
[5]李学慧，译.采集方向对叠前深度偏移成像的影响[J].石油物探译丛,2001,3.
[责任编辑：王迎迎]
121
. All Rights Reserved.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。