第三章分布式数据库中的查询处理和优化发布订阅系统.ppt
《第三章分布式数据库中的查询处理和优化发布订阅系统.ppt》由会员分享,可在线阅读,更多相关《第三章分布式数据库中的查询处理和优化发布订阅系统.ppt(70页珍藏版)》请在三一办公上搜索。
1、第三章 分布式数据库中的查询处理和优化发布/订阅系统,王静 张洪梅 王蕾,主要内容:3.1 分布式查询优化概述3.2 分布式查询优化中的基础知识3.3 分布式查询的分类和层次结构3.4 基于关系代数等价变换的查询优化处理3.5 基于半连接算法的查询优化处理3.6 基于直接连接算法的查询优化处理3.7 直接连接操作的常用策略3.8 小结,3.1 分布式查询优化概述 分布式查询处理是用户与分布式数据库系统的接口,也是分布式数据库研究的主要问题之一。,3.1.1 分布式查询优化的目标总代价最小 集中式CPU,I/O 代价 分布式CPU,I/O通讯代价时间代价 响应时间,3.1.2 分布式查询优化的准
2、则和代价估算1.查询优化的准则 分布式查询优化的准则是使通信费用最低和响应时间最短,即以最小的总代价,在最短的响应时间内获得需要的数据。2.查询代价分析(1)在远程通信网络中 常常以减少传输的次数和数据量作为优化的重要目标。,(2)在高速局域网中 以响应时间作为优化目标 在某些情况下,查询处理同时以减少通信费用和响应时间为优化目标。,3.查询代价的估算方法设一个查询执行的预期代价为QC,则代价公式集中式:QC=I/O 代价+CPU 代价 分布式:QC=I/O 代价+CPU 代价+通讯代价通信代价(粗略计算)TC(X)=传输延迟时间C0+(数据传输速率C1*传输数据量X),3.1.3分布式查询策
3、略的重要性 在分布式数据库系统中,查询优化包括两个内容:查询策略优化和局部处理优化,而查询策略优化尤为重要。例3.1 在教学数据库里,有 S(S#,SNAME,AGE,SEX)有104个元组,在站点A存放 C(C#,CNAME,TEACHER)有105个元组,在站点B存放 SC(S#,C#,GRADE)有106个元组,在站点A存放假定:若每个元组的长度均为100b 通信系统的传输速度为104 b/s 通信延迟时间为1s问题:要求查出所有选修MATHS课的男同学的学号和姓名。,解:SQL语句是:SELECT S#,SNAME FROM S,C,SC WHERE S.S#=SC.S#AND C.C
4、#=SC.C#(连接条件)AND SEX=男 AND CNAME=MATHS(选择条件)通讯代价的估算公式:T=传输延迟时间C0+(传输数据量X*数据传输速率C1)=(传输次数*1)+(传输的bit数/104)为了实现这一查询,可以有六种可能的查询策略,下面分别对六种策略进行代价估算。,策略1:A 传C B 把关系C传输到A地,在A地处理 查询T1=1+(105*100/104)S,SC 通信1次 C 103秒16.7分钟策略2:A 传S,SC B 把关系S和SC传输到B地,在B地 处理查询T2=2+(104+106)*100/104 S,SC 通信2次 C 10100秒2.8小时策略3:A
5、问105 B 先在A地求出男学生的成绩元组有 105,再根据C#的值询问B地,核 答105 实是否C=MATHS,T3(2*105*1)S,SC C=2*105秒2.3天,策略4:A 问10 B 先在B地求出MATHS的元组,有10 个,再根据C#的值询问A地的S,SC 答10 的连接,核实是否为选修MATHS的 S,SC C 男生,T4(2*10*1)=20秒策略5:A 传输105 B 先在A地求出男生选课元组,有105 个,再把结果传输到B地,在B地执 S,SC 通信1次 C 行查询,T5=1+(105*100)/104 1000秒=16.7分钟策略6:A 传输10 B 先在B地求出MAT
6、HS的元组,有10个,再把结果传输到A地,在A地执行查 S,SC 通信1次 C 询,T6=1+(10*100)/104 1秒,3.2分布式查询优化中的基础知识3.2.1用关系代数表达式和SQL语句表示一个查询 例3.2 三个全局关系:学生信息表:S(S#,SNAME,AGE,SEX)课程设置关系:C(C#,CNAME,TEACHER)选课关系:SC(S#,C#,GRADE)查询选修课程号为C03的学生姓名。SQL语句与关系代数表达式的等价描述SELECT SNAME FROM S,SC WHERE S.S#=SC.S#AND SC.C#=C03;代数描述 E1=sname(s.s#=sc.s#
7、and sc.c#=C03(SSC),SELECT SNAME FROM S WHERE S.S#IN(SELECT SC.S#FROM SC WHERE C#=C03)代数描述 E2=sname(s.s#=sc.s#(S(sc.c#=c03(SC)SELECT SNAME FROM S,(SELECT SC.S#FROM SC WHERE C#=C03)SC WHERE S.S#=SC.S#;代数描述 E3=sname(S(sc.c#=c03(SC)E3的执行效率最好。,3.2.2 查询树 对一个关系代数表达式表示查询,进行语法分析,可以得到一棵语法树。树的叶子是已知的关系,树的各个节点是关
8、系代数操作符,树的根是查询的结果,所以也称操作符树。用语法树来描述一个查询要求,更加清晰、更加直观,且易于分析和调整查询问题的具体操作次序。因此,语法树又称查询树。对于例3.2中的查询要求,对应于三个关系代数表达式的查询树如下图:,用查询树表示的查询要求:,s.s#=sc.s#SC.c#=c03,S,SC,sname,sname,s.s#=SC.s#,S,c#=c03,SC,sname,S,c#=c03,SC,对于E1的查询树,对于E2的查询树,对于E3的查询树,3.2.3等价变换规则的概念和术语1.关系代数表达式的等价 E1E22.一元操作与二元操作一元操作 选择(),投影()二元操作 并(
9、),交(),差(-),除(),迪卡儿积(),连接(),连接(),半连接(),3.2.4 等价变换规则空值的变换 R R R-R-R R R R R R R F()其中F为选择条件A()其中A为投影的属性集自身操作的等价R R R R R R R R R一元操作选择的串接:F1(F2(E)F1 F2(E)(R)(R)投影的串接:A1,An(B1,Bm(E)A1,An(E)这里要求A1,An必须是B1,Bm中的属性,一元操作交换律 1(2(R)2(1(R)条件:1 2 是选择操作时总成立 1 2 是投影操作时,要求其属性集合相等 1 与 2 是选择和投影操作符时地交换:A1,An(F(R)F(A1
10、,An(R)的条件是 F中的属性是 A1,.An 的子集二元操作交换律 RBSSBR(B,B为二元操作符)二元操作结合律 RB(SBT)(RBS)BT,一元操作对二元操作的分配律(RBS)(R)B(S)(1)选择对笛卡儿积的分配律 F(RS)F(R)S(F只涉及R中的属性)如果F形为F1 F2,且F1只涉及R的属性,F2只涉及S的属性,那么可以得到下面的定律:F(RS)F1(R)F2(R)如果F形为F1 F2,且F1只涉及R的属性,F2只涉及R和S的属性,那么可以得到下面的定律:F(RS)F2(F1(R)S)(2)选择对并的分配律 F(RS)F(R)F(R)这里要求R和S有相同的属性名,或涉及
11、的关系的属性有对应性。,(3)选择对差的分配律 F(RS)F(R)F(S)这里要求R和S的属性有对应性。(4)选择对自然连接的分配律 F(RS)F(R)F(S)(5)投影对笛卡儿积的分配律 B1,Bm,C1,Ck(RS)B1,Bm(R)C1,Ck(S)这里要求B1,Bm是R中的属性,C1,Ck是S中的属性。(6)投影对并的分配律 A1,An(RS)A1,An(R)A1,An(S)这里要求R和S的属性有对应性。,3.3 分布式查询的分类和层次结构3.3.分布式查询的分类局部查询只涉及本地、单个站点的数据,优化同集中式远程查询也只涉及单个站点的数据,但要远程通讯,选择站点注:为了减少远程查询的通信
12、代价,如果数据是冗余分 配,应尽可能选择距发出查询应用的站点最近的 站点上的数据或数据片断作为查询的对象。全局查询涉及多个站点数据,优化复杂,为了执行全局查询并确定一个好的查询策略,需要做许多判断和计算工作。这些工作大致可归为如下四类:(1)具体化 确定查询使用的物理副本,落实查询对象 非冗余具体化 冗余具体化(2)确定操作执行的次序 主要是确定二元操作连接和并操作的次序(3)确定操作执行的方法 包括把若干个操作连接起来在一次数据库访问中执行,确定可用的访问路径,以及确定某种计算方法等。(4)确定执行站点 主要考虑通信代价和执行效率,一般选择离提供数据的站点较近的站点,而考虑到查询速度的因素,
13、还应尽量选择空闲的站点执行查询操作。,分布查询处理的层次模式,分布式查询问题,查询分解,全局模式,数据本地化,全局优化,局部优化,优化的局部查询,全局查询代数表达式,片段查询,包括通信操作的优化片段上的查询,分片模式,片断统计,局部模式,3.4基于关系代数等价变换的查询优化处理1.基本原理 把查询的问题转变为关系代数表达式,分析得到查询树(语法树),进行全局到片段的变换得到基于片段上的查询树,然后利用关系代数表达式规则的优化算法,尽可能先执行选择和投影操作。关系代数等价变换规则的优化算法:利用关系代数等价变换规则,把查询树中的连接和合并操作尽可能上提(向树根方向移),选择和投影操作尽可能下移(
14、向树叶方向移)到片段的定义处。注:尽可能先执行选择操作和投影操作。,2.实现步骤和方法(1)将一个查询问题转换成关系代数表达式(2)从关系代数表达式到查询树的变换 方法:查询树的根节点是最终的查询结果,叶节点是查询 涉及的所有关系或片断,中间节点是按代数表达式 中的操作顺序组成的一组关系操作符。(3)从全局查询到片段查询的变换 典型方法:把基于全局关系的查询树中的全局关系名,用 其重构该全局关系的各片段名替换,变换成相应片 段上的查询树。(4)利用关系代数等价变换规则的优化算法,对片段上的查询树进行优化处理,最后达到优化查询的目的。,3.4.2 基于关系代数等价变换的查询优化处理举例例3.3
15、数据库中的全局关系S(s#,sname,age,sex)和SC(s#,c#,grade)被水平分片,如图所示:S SC h hS1:sex=M S2:sex=F SC1:c#20 SC2:c#20男学生全体 女学生全体 课程号20 课程号20 图:3.4全局关系S和SC的水平分片查询问题:查找至少有一门功课的成绩在90分以上的男同学 姓名。SQL语句:SELECT DISTINCT sname FROM S,SC WHERE S.s#=SC.s#AND sex=M AND grade 90,关系代数表达式:sname(sex=M grade90(s.s#=SC.s#(SSC)查询树:图:3.5
16、等价变换规则用于水平分片的情形 sname 变换 S.S#=SC.S#s#,sname grade90 s#,sname grade90 sex=M U sex=M SC U SC1 SC2 S S1 S2 C#C20 C#C20 SEX=M SEX=F a.全局关系上的查询树 b.对应片段上的查询树,sname,sname sname 产生矛盾去掉一只 S.S#=SC.S#S.S#=SC.S#U U s#,sname Us#,sname s#,sname grade90 grade90 S1sex=M sex=M sex=M SC1 SC2 SC1 SC2 C#C20 C#C20 C#C20
17、 C#C20 grade90 grade90 S1 S2sex=M sex=Fc.把投影和选择下移后的查询树 d.简化的查询树,水平分片关系优化的基本思想:首先,尽可能把选择条件下移到分片的限定关系处,再把分片的限定关系与选择条件进行比较,然后去掉它们之间存在矛盾的相应片段。如果最后剩下一个水平片段,则重构全局关系的操作中,就可以去掉“并”操作(至少可以减少“并”操作的次数)。,例3.4有全局关系EMP(emp#,ename,salary,dept#,dname),如果被垂直分片,分成如下两个片段:E1(emp#,dept#,dname)E2(emp#,ename,salary)查询:雇员的姓
18、名和工资情况。SQL语句:SELECT ename,salary FROM EMP关系代数表达式:ename,salary(EMP)它的查询树如下页所示:,图3.6 等价变换规则用于垂直分片的情形ename,salary ename,salary 移植到片段上 EMP E1.EMP#E2.EMP#emp#,dept#,deptname E1 E2:emp#,ename,salary 去掉无关的片段ename,salary ename,salary 去掉连接E2:emp#,ename,salary emp#,ename,salary,垂直分片关系优化的基本思想:把垂直分片所用到的属性集,与查询条
19、件(查询表达式)中的投影操作所涉及的属性集相比较,去掉无关的垂直片段。如果只剩下一个垂直片段与查询有关时,去掉重构全局关系的“连接”操作(至少可减少“连接”操作的次数)。,3.5基于半连接算法的查询优化处理选择、投影和连接是最常用的三种操作。选择:关系(R),如果R是一个全序关系,那么简单地在包 含R的站点上执行选择操作,然后再把结果发送给用 户站点。如果R被分片,那么在每一个包含R片段的站 点上执行选择操作,然后再将这些结果合并得到最后 的结果,发送到用户站点。投影:它与选择操作处理的唯一不同之处在于投影操作所得 到的结果中可能包含重复的元组,需要作删除操作。连接:是常用而且代价较高的一种操
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 分布式 数据库 中的 查询 处理 优化 发布 订阅 系统
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5147114.html