简介:适合算法划分论文写作的大学硕士及相关本科毕业论文，相关算法划分开题报告范文和学术职称论文参考文献下载。
孙东海 张 杨 魏东平
（中国石油大学（华东） 东营257061）摘 要：简单阐述了分布式数据库中查询优化的查询目的,并简单介绍了直接连接优化算法中的Hash划分和Partition算法.通过分析,指出Partition算法的不足,并加以改进.在改进算法中提出了查询图划分方法,缩短查询操作的响应时间.关键词：分布式数据库直接连接Partlition算法响应时间 查询优化
1. 引言
分布式数据库系统是数据库技术与网络技术两者相互渗透和有机结合的结果.分布式数据库系统在体系结构上与集中式数据库系统有很大的不同‘纠,具有数据分布性、逻辑整体性等特点.
整数划分算法:DT大数据梦工厂大数据IMF传奇行动绝密视频（泄密版）第34课：Stage划分和Task最佳位置算法源码彻底解密
在分布式数据库中,查询执行的开销除了要考虑I/O代价和CPU代价外还要考虑通信代价,即总代价等于 I/O代价+CPU代价+通信代价.在远程通信网中,数据的传输速率较低,在这种情况下,通信代价要比I/O及CPU开销大很多,通常在查询优化时优先考虑通信代价；而在高速局域网中,传输速率要快得多,则此时通常将查询的响应时间作为优化的目标.
查询优化有两个出发点,一个是以通信论文范文最小为准则,另一个是以响应时间最短为准则.针对不同的查询优化目标,出现了基于半连接和基于直接连接两种常用的查询优化算法.其中基于直接连接优化算法通常是在高速局域网环境中以追求响应时间为目标的优化算法,一般是利用站点依赖和数据复制相结合方法来缩短响应时间的,下面简单介绍一下基于直接连接优化常用的Hash划分和Partition算法.
2.Hash划分
在基于直接连接的查询优化中,Hash划分是一种常用的方法.Hash划分是利用Hash函数对分片关系上的连接属性作站点依赖计算,再据此分片,以获取站点依赖的连接算法.
如表1所示,现有两个关系Rl和R2,假设对Rl和R2进行分片操作,对Rl分片后生成片段Fll和F12,分别放到站点SI和S2,同样R2的片段F21和F22也分别放到SI和S2,则Rl等于Fii U F12、R2等于F21 UF22.若关系Rl和R2在属性x上满足条件Flioo x F2j、中（其中i≠j）,即片段F1i和F2j在属性x上进行连接操作的结果为空集,则称Rl和R2在属性x上站点依赖.
了解了站点依赖,下面就通过一个例子简单介绍一下Hash划分.假设现有关系Ri(i 等于1,2),对于Ri的每一个元组,在x属性列上运用下面的Hash函数
3.Partition算法
Partition算法通过对两个或多个关系在同一连接属性上进行片段划分,来提高连接操作的并行性,以此来加快整个查询的查询速度.
假设现有查询要执行以下一系列的连接操作：Rl∞x R2,R2 00y R3,R3∞ R4.则Rl和R2可以在属性x上进行划分,R2和R3可在属性y上进行划分,R3和R4可在属性z上进行划分,这样就形成了三种划分方案.
Partition算法只能选择划分方案的其中一种,若选择了让Rl和R2在属性x上进行划分,则其他两种划分方案则不会进行.假设现共有d个站点,这样可将关系Ri(i 等于l,2)在x属性划分成d个不相交的片段( Fil,Fi2,等．Fid)(i_l,2),根据站点依赖原则,将片段Fij放到站点j(j等于1等d)上,与此同时,也将R3、R4的副本放到站点j上.这样,每个站点执行的查询为Flj.F2j∞R3∞R4(j等于l等d),最后将各个站点的查询结果取并集即可得到查询的最终结果.
这种方法的目的就是利用分布式数据库的分布性特点,使得查询操作能够在多个站点上并行进行.但是对于海量信息及关系较多连接属性各不相同的查询而言,这种方法的效果仍然不理想,因此下面利用查询图划分方法与Partition算法相结合,对Partition算法进行改进.
4. Partition的改进算法
通过以上对Partition算法的介绍可知,在Partition算法中,在多种划分方案中只用到了其中的一种,仅对该方案中的关系进行了划分,而其他剩余的参加查询的关系被整个复制到其他站点上.针对此问题,本文引入了一种查询图划分方法,通过查询图的划分可以将整个查询图划分为多个子查询图,这样再对子查询图中的连接应用Partition算法,这样就避免产生大量剩余关系的情况.
首先介绍本文中所用到的查询图划分（用到了图论的相关知识）：
(1)首先选择节点度（算法引进了节点度的概念,即节点的边的个数）最小的节点,如有多个,则随机选取一个.按照深度优先进行遍历,两个为一组,并以l、2、3等进行顺序进行组的编号.如图所示,由A点开始,进行深度优先遍历,A、B划为1组,C、D划为2组,E、F化为三组,至此,没有可以再划分的组了.
(2)经过以上的过程,大部分节点都是两两一组,对于其他未被划分到组的节点,我们将其并人与其相连的节点所在的组编号最小的组,这样可以保持各组中节点个数的近似平衡.如图,H与D和F都有相连,选择其相连的节点所在的组编号最小的组即为2组,于是将H划分到2组,同理G划分到3组.
(3)至此,整个划分就被划分成多个子查询图.
介绍完查询图划分方法后,下面就是本文的算法步骤：
(1)进行查询图划分,对节点进行分组.
(2)每一组都进行Partition算法操作.假设现有Rl和R2在连接属性X上进行操作,而该组内的站点个数为d,则在属性X上划分为d个不同的片段,即Fil,Fi2,等Fid(i_l,2).将这d个片段分别放到d个站点上进行连接操作,得到R121,R122,等R12d,将结果合并即得到Rl和R2的连接结果,这样该组可视为一个点,但站点数不变,仍为d.
(3)所有的子查询图内的连接操作都进行完后,继续执行步骤(1)和(2)直到产生最终结果为止.
与Partition算法相比,该方法对于大部分（甚至全部）的关系都进行了划分,因此在一定程度上减小了每个站点的连接论文范文,并充分利用了分布式数据库分布性的特征,缩短了响应时间.不过从算法也可看出,由于整个过程是递归进行的,所以在进行连接操作的关系较多时会显得繁琐,这些不足还需要进一步的研究加以改善.
5. 算法实验结果分析
由于条件所限,本实验是模拟进行的,操作系统WindowsXP,使用数据库为Oracle.在实验中,每个站点只有一个关系,各关系的大小都近似相等.由于实验环境所限,只对以下三组查询进行了分析比较：
(1)R1∞.xl R2,R2∞x2 R3,R3∞x3 R4
(2)R1∞xl R2,R2∞x2 R3,R3∞x3 R4,R4∞x4 R5
(3)R1∞xl R2,R2∞x2 R3,R3∞ x3 R4,R4∞x4 R5 ,R5∞ x5 R6
表2为实验结果,响应时间均为多次结果平均值,单位为秒,本文算法和Partition算法的响应时间分别用Tthis和Tpartition来表示.
从表2中可以看出,随着连接关系的增加,本文算法比Partition算法的响应时间有了较明显的减少.
6.结束语
本文主要对分布式查询中基于直接连接的优化算法研究,分析了Partition算法的不足,并针对Partition算法引入了查询图划分的方法对其进行了改进.最后通过实验对本文方法与Partition算法的响应时间进行了比较,证明了本文方法与Partition算法相比有一定的改进,说明了本方法在高速局域网中有一定的可用性.
参考文献
[l]王珊．数据库系统概论[M]．北京：高等教育出版社,2006.
[2]陈建荣,严隽永,叶天荣,分布式数据库设计导论[M]．北京：清华大学出版社,1992．
[3]张宋传,陈瑞典．分布式数据库多元连接查询优化的研究[J].微计算机应用,2005,4(3)：391-392
[4]王菲菲,郑刚．基于多连接属性划分的分布式数据库查询优化算法[J]．现代计算机,2007,(11)：20 -22
[5]毛君国．高级数据库原理与技术[M]．北京：人民邮电出版社,2004.
作者简介
孙东海,男,副教授,硕士生导师,研究方向：数据库应用技术、计算机网络.
张杨,男,硕士研究生,研究方向：数据库应用技术.
魏东平,男,副教授,硕士生导师,研究方向：计算机应用软件开发、数据库应用技术、计算机网络系统.
总结：本论文可用于算法划分论文范文参考下载，算法划分相关论文写作参考研究。
整数划分算法引用文献:
[1] 优秀计算机算法分析论文题目 计算机算法分析论文标题怎么定
[2] 计算机算法专业论文选题 计算机算法论文题目选什么比较好
[3] 计算机算法论文参考文献推荐 计算机算法专著类参考文献哪里找
