分布式数据库数据查询的优化处理方法

1、第28卷第4期长春理工大学学报Vo l 128No 142005年12月Journal of Changchun University of Science and Technol ogyD ec.2005收稿日期:2005-07-20作者简介:李华,女(1977-,硕士,讲师,主要从事计算机教学工作。分布式数据库数据查询的优化处理方法李华赵建平(长春理工大学计算机科学技术学院,长春130022摘要:本文根据局域网下分布式数据库数据分布的模型,分析了在局域网下分布式数据分布的问题,阐述了分布式数据库中数据的优化查询操作与应用环境、节点处理能力间的关系,及查询方式对查询效率的影响,进而提出了对数

2、据的全局优化问题的基于连接的优化算法模型,可以有效地提高分布式环境下数据查询的效率。关键词:分布式数据库;查询;优化;模型中图分类号:TP3111132文献标识码:A 文章编号:1672-9870(200504-0085-03Opti m i zed M ethod for Dat a Query I n D istri buted Dat abaseL I Hua ZHAO J ianping(School of Co m puter Science and Technology of Changchun U niversity of S cience and Technology Abst

3、ract:This paper discusses and analyzes the model of data distributi on in distributed database on LAN.The result indicates the relati onshi p s bet w een op ti m ized inquire of data and app licati on envir onment &node p r ocessing ability in the distributed database which can affect the effici

4、ency of query,then brings f or ward an op ti m ized algorithm model based on j oint way f or the overall op ti m izati on .It can advance the efficiency effectively of data query under distributed envir on ment .Key words:distributed database;query;op ti m ize;model分布式数据库是数据库技术和计算机网络技术相结合的产物,是数据库技术的

5、一个新领域,它是分布式数据库系统中各节点上数据库的逻辑集合,即能将物理上分散在不同地点的各个数据库在逻辑上统一为一个集中的数据库,实现一种更高层次的数据库服务。分布式数据库构成的分布式数据库系统(DDBS 具有普通的集中式数据库和C /S 方式(客户机/服务器方式所不具备的数据存储和处理方式。对分布式数据库的研究涉及系统结构、查询优化、并发控制、事务管理等,围绕如何提高分布式数据库的性能和效率,本文对数据查询的优化处理方法进行了研究。从整体来看,分布式数据库系统中每个节点结构如图1所示。1分布式查询处理分布式查询处理可分为四个层次:(1查询分解将待查询问题转化成一个定义在全局关系上的关系代数表

6、达式或S QL 语句,本层转换所需要的信息在全局概念模式中获得。(2数据本地化把一个在全局关系上的查询具体化,落实为一相应物理片段上的查询。这一变换所需要的信息在分布式数据的分片模式和片段分配模式中获得。(3数据的全局优化根据查询语句,寻找一个近于最优的执行策略,确定查询的相关节点,以实现用最少的时间执行查询。(4数据的局部优化由拥有与查询有关的片段的各个节点具体执行。在一个节点上执行的子查询,被称为局部查询,并由该节点上的DBMS 进行优化。查询处理的层次模式如图2所示。长春理工大学学报2005年 图1DDB S系统结构图 图2分布式查询处理层次模式2分布式查询的优化对于一个查询语句,可在查

7、询分析后,根据所得到的属性名、表名等信息,在数据字典中确定它所需要访问的片断(FSCODE ,其后便是确定存取方案,即,在分析优化查询操作与应用环境及节点处理能力间的关系及其对查询效率的影响的基础上,以所付时间代价最小为标准,确定采用怎样的传输方法更有效。以教学数据库为例,教学数据库中有三个表:学生信息表:S (S #,S NAME,SEX,AGE 有104个元组在A 场地存放。课程信息表:C (C#,CNAME 有103个元组在B 场地存放。学生成绩表:SC (S#,C #,SCORE 有105个元组在A 场地存放。假定,若每个元组长度为100bit;通信系统的传输速度为104bit/s;通

8、信延迟时间为015s;需要查询所有选修"Multi m edia"课的男学生的学号和姓名。那么,在分片透明性的DDBMS 支持下,S QL 语句为:SELECT S#,S NAME FROM S,SC,C WHERE S 1S#=SC 1S#AND SC 1C#=C 1C#AND SEX =M AND CNAME =Multi m edia 相应的通信代价估算公式为:T =传输延迟时间C 0+(传输的数量X 3数据传输速率C 1=(传输次数31+(传输的位数/104为实现这一查询,有六种可能的查询策略:策略1:把关系C 全部传到A 场地处理查询,其时间代价为:T1(1033

9、100/1040.16分钟;策略2:先在B 地求出为"Multi m edia"的元组,经统计共有10个,再根据C#的值询问A 地的S 1SC 的连接,核实是否为选修"Multi m edia"的男生,其时间代价为:T2(01231031=2秒;策略3:先在B 地求出为"Multi m edia"的元组,经统计共有10个,再把结果传输到A 地,在A 地执行查询,其时间代价为:T31+(103100/1041秒;策略4:把关系S 和SC 传输到B 地,在B 地处理查询,其时间代价为:T4(2+104+1033100/1041.7分钟这样

10、的查询可以有六种,不同的查询策略对查询的速度有很大的影响。所以要对关系中的各种操作找到合理的传输和解决方案,在分布式数据库中主要的关系代数表达符有选择、投影和连接。以全局关系R 上的选择操作为例:在包含R 的节点上执行选择操作,然后把结果发送给用户节点;如果R 被分片且分布在几个节点上,那么在每个包含R片段的节点上执行选择操作,然后再将这些选择操作的结果合并到最终结果,发送给用户节点。对于投影操作,可用同样的方法,只是在投影所得到的结果中可能有重复的元组,需要做删除操作。连接操作通常是代价比较高的操作,因此为了使分布式数据库系统能有效地处理连接操作,人们进行了大量的研究,形成了各种不同的算法,

11、一般可以分为两类:基于半连接的查询优化算法和基于直接连接的查询优化算法。结合分布式系统的具体应用情68第4期李华等:分布式数据库数据查询的优化处理方法况,如果局部处理响应时间比传输时间更重要,就应该采用直接连接的物理优化算法。下面,在对分布式教务管理系统的相关分析基础上,给出了与分片复制方法相结合的直接连接的物理优化算法。 图3基于连续的优化算法流程图3直接连接的物理优化算法直接连接的物理优化算法主要利用节点间的信息依赖关系,节点依赖是指:如两个片段关系R i 和R j 在属性A 上满足条件F is F jt =。其中s t,则称R i 和R j 在属性A 上节点依赖。根据节点依赖的定义,可以

12、得到以下的观察:(1如果R i 和R j 在属性A 上节点依赖,则R i和R j 在任何包含A 的属性集B 上也节点依赖。(2如果R i 和R j 在属性A 上节点依赖,另一个属性B 函数决定A,且A ,则R i 和R j 在属性B 上也节点依赖。(3若R i 和R j 有节点依赖A,且R j 和R k 有节点依赖B ,则R i A R j B R k =(F is A F jsB F ks ,其中,s 为所有包含R i 、R j 、R k 的片段的任何一个节点,或者说,所有的连接操作可以在本地完成而无须数据传送。因此,可首先判断查询的连接操作是否需要数据传送,若无数据传送,则直接就可以进行数

13、据连接,否则,要考虑怎样的数据传送可以使得费用最小。这里采用了与分片和复制算法相结合的一种方法。该算法是这样的:假如分布式教务管理中的学籍关系有如下的分布(见表1。表1信息分布表关系站点Site <0>Site <1>Site <2>学籍关系R 1R 11R 12R 12成绩分析R 2R 21R 22(下转第70页78长春理工大学学报2005年6实验结果及结论文中提出的算法均在M icr os oft 1NET 平台上利用M icr os oft V isual C#1NET 语言实现。其结果显示,算法对书写工整的汉字可进行有效的笔划提取,其结果是令人满意的

14、。提出的手写汉字笔划直接抽取法是以组成字符的像素为基础,通过计算像素的游程长度,用笔划厚度作为阈值对游程长度进行分类。同时省去细化过程,充分利用汉字点阵信息。既提高了笔划抽取速度,又增强了笔划抽取过程中的抗干扰能力。这种笔划抽取法简单、易行,其原理具有普遍意义。随着中文信息处理技术的发展,计算机科学技术水平的不断提高,笔迹鉴别和汉字识别技术都将得到更加广泛的应用,手写体单笔划提取算法也将得到更大的发展空间。参考文献1孙星明,杨茂江.完全基于结构知识的汉字笔划抽取方法J .计算机研究与发展,2000,37(5:97-102.2张世辉,孔令富.一种新的基于细化的汉字笔划抽取方法及其在汉字识别中的应

15、用J .计算机工程与应用,2002,46(16:105-110.3刘成林,戴汝为.简化的W igner 分布及其在笔迹鉴别中的应用J .计算机学报,1997,(11:68-72.4林峻,李介谷.离线中文签名鉴别的特征提取及预处理J .上海交通大学学报,1996,(9:112-118.5Kenneth R Castle man 著,朱志刚,林学闻,石定机,等译.数字图像处理J .北京:电子工业出版社,1998.6Cheng F H,H su W H.Three str oke extracti on methodsfor recogniti on of hand written Chinese

16、characters J .I nt .Comput .Sy mp.,Tai w an,1986,191-195.7Tseng L Y,Chen R C .Seg mentati on hand written Chinesecharacters based on heuristic merging of str oke bounding boxes and dyna m ic p r ogra mm ing J .Pattern Recogniti on Letters,1998,19:963-973.8Chen Hong .Seg mentati on and recogniti on o

17、f continuoushand writing Chinese Text J .I nternati onal Journal ofPattern Recogniti on and A rtificial I ntelligence,1998,12(2:223-233.(上接第87页假定一个查询要进行学籍关系和成绩分析的连接,而学籍关系被分成两个片段:R 11和R 12。其中片段R 12是冗余分配在Site <1>和Site <2>上,成绩分析也经过收益分析,把它的两个片段分别存放在场地Site <0>和Site <2>上。分片和复制算法的基本

18、思想是:首先,任意选择一个关系R i ,使其保持分片状态,且用包含R i 各片段的节点作为处理节点。这些节点之一,比如S j ,有最大估计完成时间。其次,对每一个节点S t (包括初始的处理节点和不含R i 的片段的节点,如果片段R ij 由节点S j 转移到S t ,估计在节点S t 处理字查询的完成时间;如果存在一些节点S t ,其估计完成时间低于节点S j ,则选择具有最小估计完成时间的节点S t0。由于查询响应时间由所有节点的最大完成时间决定,以S t0替换S j 作为处理节点将不会增大响应时间。这样,对R i 的每个不同片段重复做这种处理,直到这种改变不能进一步降低单个节点的完成时间。再分别使每个不同的关系保持分片并重复以上处理过程,通过启发性方式跟踪每一个关系保持分片状态来估计最小的响应时间,最后选择这些关系中具有最小响应时间者作为查询优化策略的保持分片状态的关系。基于连接的优化算法流程如图3所示。5结束语本文提出了局域网环境下分布式数据库的数据查询的优化处理方法,并在此基础上结合分布式教务管理系统的