资源描述：
《分布式数据库系统及其应用课件第3章 分布式数据库中的查询处理和优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、徐俊刚（xujg@gucas.ac.cn)分布式数据库系统及其应用2007年2月——2007年6月分布式查询优化概述分布式查询优化基础知识分布式查询分类和层次结构基于关系代数等价变换的查询优化处理基于半连接算法的查询优化处理基于直接连接算法的查询优化处理直接连接操作的常用策略分布式数据库中的查询处理和优化第3章查询处理问题集中式查询转换为代数表达式从所有等价表达式中选择最优的代数表达式分布式除了集中式问题外，还有站点之间交换数据的操作选择最优的执行站点(分布）数据被传送的方式1.1分布式查询优化的目标1分布
2、式查询优化概述1.1分布式查询优化的目标1分布式查询优化概述目标总代价最小响应时间最短集中式分布式CPU代价（相对固定）I/O代价（可变的，优化的目标）CPU代价I/O代价（访问磁盘）通讯代价数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间主要标准辅助标准1.2分布式查询优化准则和代价分析1分布式查询优化概述准则：使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。通讯费用与所传输的数据量和通信次数有关响应时间和通信时间有关，也与局部处理时间有关查
3、询代价分析远程通讯网络局部处理时间可以忽略不计，减少通讯代价是主要目标高速局域网传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键例子S(s#,sname,age,sex)104元组SiteAC(c#,cname,teacher)105元组SiteBSC(s#,c#,grade)106元组SiteA每个元组长度100Bit,通讯传输速度104bit/sec,通讯延迟1secS,SCCSiteASiteB1.3分布式查询策略的重要性1分布式查询优化概述查询:所有选修maths课的男生学
4、号和姓名.SELECTs#,snameFROMS,C,SCWHERES.s#=SC.s#ANDC.c#=SC.c#ANDsex=‘男’ANDcname=‘maths’;1.3分布式查询策略的重要性1分布式查询优化概述代价公式QC=I/O代价+CPU代价+通讯代价通讯代价TC=传输延迟时间C0+(传输数据量X*数据传输速率C1)1.3分布式查询策略的重要性1分布式查询优化概述1.3分布式查询策略的重要性1分布式查询优化概述策略1:A传CB把关系C传输到A地,在A地处理查询○○T1=1+(10**5*100/1
5、0**4)S,SC通信1次C≈10**3秒≈16.7分钟A传S,SCB把关系S和SC传输到B地,在B地处理查询○○T2=(2+10**4+10**5)*100/10**4S,SC通信2次C≈10100秒≈28小时A问10**5B先在A地求出男学生的成绩元组有10**5○○再根据C#的值询问B地,核实是否C=‘MATHS’S,SC答10**5CT3≈(2*10**5*1)=2*10**5秒≈2.3天策略2:策略3:六种查询策略S,SCCAB1.3分布式查询策略的重要性1分布式查询优化概述A问10B先在B地求出
6、‘MATHS’的元组,有10个○○再根据C#的值询问A地的S，SC的连接，S,SC答10C核实是否为选修‘MATHS’的男生T4≈(2*10*1)=20秒A传输10**5B先在A地求出男生选课元组，有10**5个○○再把结果传输到B地,在B地执行查询，S,SC通信1次CT5=1+(10**5*100)/10**4≈1000秒≈16.7分A传输10B先在B地求出为‘MATHS’的元组，有10个○○再把结果传输到A地,在A地执行查询，S,SC通信1次CT6=1+(10*100)/10**4≈1秒策略4：策略5：
7、策略6：六种查询策略S,SCCAB相关表述记号⒈设关系模式为R(A1,A2,…,An)。它的一个关系设为R。t∈R表示t是R的一个元组。t[Ai]则表示元组t中相应于属性Ai的一个分量。⒉若A={Ai1,Ai2,…,Aik}，其中Ai1,Ai2,…,Aik是A1,A2,…,An中的一部分，则A称为属性列或域列。t[A]=(t[Ai1],t[Ai2],…,t[Aik])表示元组t在属性列A上诸分量的集合。则表示{A1,A2,…,An}中去掉{Ai1,Ai2,…,Aik}后剩余的属性组。A2.1关系代数知识回顾
8、2分布式查询优化中的基础知识⒊R为n目关系，S为m目关系。tr∈R，ts∈S。trts称为元组的连接。它是一个(n+m)列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组。⌒相关表述记号⒋给定一个关系R(X,Z)，X和Z为属性组。我们定义，当t[X]=x时，x在R中的象集（ImagesSet）为：Zx={t[Z]
9、t∈R,t[X]=x}它表示R中属性组X上值为x的诸元组在Z上分量的集合。2.1关
