分布式数据库查询处理和优化算法

张引红

(咸阳职业技术学院，咸阳 712000)

0 引言

分布式数据库系统是基于集中式数据库技术的计算机网络技术，其和集中式数据库的主要区别就是：分布式数据库数据为分散性存储到网络不同场所中，而且不同场地数据库的处理能力各有不同。还能够在局部完成功能应用，另外每个场地都要参与到全局应用程序执行过程中，全局应用程序是利用已有网络拓扑实现通信，从而对各场地数据进行访问。在实际应用及操作过程中是无法感受到分布式网络存在，操作也属于整体数据库。以此表示分布式数据库物理方面是在各网络节点中分散，但是在逻辑方面还是相同数据库系统数据集。以此就使其在优化过程中和集中数据库系统不同。因为分布式数据库系统数据冗余性和分散性，从而就导致查询处理优化存在复杂性。在实际使用过程中，分布式查询处理与优化在项目周期中具有重要的作用。

1 分布式数据库查询优化代价

分布式数据库技术具有集中性和分布性的特点，其分布性主要指的是在数据在网络中属于跨结点物理存储，集中性指的是用户逻辑中属于简单且同构数据库。和分布式进行对比，集中式数据库管理系统要求逻辑和物理两方面都相互集中。所以，分布式数据库还能够定义成为物理中分布，逻辑中集中的共享数据集合。分布式数据库管理系统属于数据管理软件，利用分布式数据库管理系统能够提高分布式数据库分布特点的透明度。

在集中式数据库中，因为系统大部分都是在单个处理器计算机中运行，一个查询执行预期代价属于I/O代价与CPU代价结合。在分布式数据库系统中，一个查询包括多电站，查询处理还要对站点之间数据传输的通信费用进行全面的考虑，对于不同通信类型具有不同的查询处理算法。在远程通信网络中，查询局部处理时间和通信时间进行对比，可以不对其进行计算。所以，一般都是将降低传输次数及数据量作为优化的主要目标。在高速局域网中，传输时间要比处理时间短，所以一般都要将响应时间作为主要的优化目标。响应时间不仅和通信时间具有密切的联系，并且还和局部的处理时间具有密切的联系。但是局部处理时间属于关键内容，所以此问题的主要内容就是要降低局部的处理时间。

通过以上描述就可以了解到，分布式查询总代价包括通信代价、CPU代价和I/O代价，那么通信代价就能够通过CO+C1*X进行计算。其中CO指的是两个站点之间通信初始化的一次花费时间；X指的是数据传输的量，C1指的是传输速率[1]。

2 分布式数据查询的处理模式

集中式数据库系统主要包括内模式、外模式和概念模式构成，分布式数据库系统的模式结构主要包括局部数据模式和全局数据模式，分布式数据库的结构，如图1所示。

图1 分布式数据库的结构

局部数据模式指的是各个站点中局部数据库系统模式的结构，其中具备集中式数据库系统三级模式结构。全局数据模式的主要目的就是对局部数据模式进行有效的协调，使其能够成为整体模式结构。

全局数据模式包括全局外、全局概念和分片模式、分布模式构成，其中全局外模式指的是全局使用的用户视图，属于全局概念模式逻辑的子集；全局概念指的是分布式数据库全局数据逻辑的结构；分片模式指的是使全局关系分解成为多个不相交部分，也就是数据分片。分片模式指的是片段和全局关系之间的映象，此种映象指的是一对多，也就是每个片段都是全局关系，但是全局关系能够分解成为多个片段；其中分布模式指的是通过数据分片得出的片段还是分布式数据库数据，其属于全部关系逻辑的部分，每个分片物理中都能够一个或者多个站点中进行分配或者定位。分布模式能够以选择的数据实现策略有效分配，对片段物理存放站点进行定义。分布模式中定义映象的类型能够对分布式数据库数据分配的冗余进行有效确定，如果映象属于一对多，也就是片段到多站点充分存放进行分配，那么此数据分配属于冗余。相反，就是不冗余。

分布式环境查询类型主要包括远程查询、本地查询及全局查询，本地查询也就是局部查询，其和集中式数据库优化技术相同。其中远程查询指的是单点数据远程通信，如果数据属于冗余分配，要降低查询处理通信代价，就要选择距离查询节点发出最近节点中的数据，或者还可以将数据片实现查询。全局查询指的是实现多点数据查询，其主要流程为：对查询对象进行确定，之后以可用访问路径及算法对二元操作连接进行有效确定，最后实现执行节点的确定，要对通信代价、查询速度及执行效率进行全面的考虑。

总而言之，要实现查询处理策略的有效荀泽，对必要物理片段进行确定从而有效实现查询，并且还要对查询过程中各个操作的执行站点进行确定。另外，实现分布式数据库查询的优化还与算法操作具有密切的联系[2]。

3 分布式数据库查询优化算法

3.1 查询树和生成树

对关系模式R进行定义，使其为有限属性集{A1，A2，…,An}，在关系模式中的实例R属于从模式R到数据域的映射，此映射表示为{t1，t2，…，tn}。假如B属于R的属性，那么就表示为t.B。此表达式指的是等值相互连接的条件：R.B=S.C，为了能够寻找最优连接策略，将查询语句q进行定义。虽然两个数据之间可能会具有一个或者多个连接条件，但是并不对查询图是否为多边图进行全面考虑。另外，将查询语句中两个关系R和S在连接的过程中所使用条件变动为clauses(e，q)，查询图如图2所示。

图2 查询图

3.2 代价模型

在实现查询连接操作的过程中，在关系R的某个属性及属性集中实现哈希划分，那么此属性就为part(R)，在对其进行假设查询执行之前，此属性只包括单个的元素几何，也就是在一个属性中实现哈希划分。为了能够对分布式查询策略有效性进行分析，创建模型将查询过程中的关系连接代价进行全面反映。在分布式查询过程中，为了能够使响应时间缩短，就可以寻找查询图小代价单条件生成树QGTreeq，因为QGTreeq代价不仅与连接操作关系大小和哈希划分过程中参照属性具有密切的联系，其还与多个条件表达式中两两关系连接顺序具有密切的联系。那么要寻找最佳条件表达式序列。单条件生成树QGTreeq最小的代价为：

QGTreeq=min{Cost(cs)} cs∈CS

假如查询条件表达式通过查询语句中其他的表达式进行推导，那么此条件表达式就是冗余条件表达式。全面考虑QGTreeq冗余表达式，就能够得到最佳的条件表达式序列，分别为{R.A,T.D},{T.E,S.C},{T.E,U.F}，其总代价为8k。以此表示，分布式查询优化过程中只考虑查询图QGTreeq并不够，所以就要使用优化算法实现。

3.3 优化算法

定义查询q属于QGq中的一条链，其就是链查询。本文使用动态编程技术CHAIN算法有效解决链查询中的MRP问题。通过此算法，能够对查询使用的关系最佳连接徐磊进行计算，以此降低连接代价，缩短查询响应时间。

比如，QGq最小的代价条件表达序列为c5、c3、c4，和其相互对应的查询图优化结果为R、T、S、U。简单来说，最优关系连接顺序就是，R/T，其连接条件为c5，其次为RT/S，其连接条件为c3，最后为RS和U相互连接，其连接条件为c4。

在根据查询语句条件表达式对两条关系相互连接的过程中，要选择最小代价表达式实现连接，并且代价和本地连接使用的代价与划分代价相同。本地连接代价与两个关系大小的和具有密切的关系，在确定连接关系之后，此部分代价就是固定的，并且条件表达式没有关系。

3.4 算法实例

使用以下查询，其包括的条件表达式为：

c1={R1.A,R2.B}

c2={R2.C,R3.D}

c3={R2.E,R3.F}

c4={R2.G,R4.H}

另外，CHAIN算法的实例数据，使用CHAIN算法寻找最小代价和相应关系连接顺序，如表1所示。

表1 CHAIN算法的实例数据

查询优化结果表示，如表2所示。

表2 实验结果

需要优化的最小代价为1 470，其中的关系连接顺序为：{R2.C,R3.D}、{R3.G,R4.H}、{R2.B,R1.A}[3]。

4 总结

查询优化算法指的是分布式数据库研究过程中的主要问题，本文对分布式查询优化代价及处理过程进行了全面的分析，掌握了对分布式查询优化影响的优化因素，并且对分布式查询优化中的策略及算法进行了有效的阐述。一般，查询优化算法并不是万能且通用的，对于查询算法选择主要包括：是否满足大数据量需求、是否能够满足异构数据库需求；是否能够为全局或者局部优化；是否能够满足高复杂性需求。对于分布式数据查询问题，相应查询优化策略能够使用到不同应用中，从而选择最省的代价方案。