厦门大学计算机科学系省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,分布式数据库 厦门大学计算机科学系 林子雨 ziyulin,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,厦门大学计算机科学系 年11月,林子雨,厦门大学计算机科学系,E-mail:ziyulin,分布式数据库技术专题三 分布式查询处理,厦门大学计算机科学系硕士课程,1/69,专题三 分布式查询处理,第4章 分布式查询处理,4.1 分布式查询特点,4.2 全局查询转换基础知识,4.3 全局查询到逻辑查询转换,4.4 逻辑查询到物理查询转换,4.5 联接操作,2/69,4.1.1 分布式查询处理定义,4.1.1.1 集中式数据库查询基本原理,4.1.1.2 分布式查询处理,4.1.1.3 三种查询之间联络,4.1.1.4 分布式查询定义,4.1.2 分布式查询代价原因综述,4.1 分布式查询特点,3/69,4.1.1 分布式查询处理定义,4.1.1.1 集中式数据库查询基本原理,在集中式数据库环境中查询处理，是将用户查询（由查询语言表示）转换成物理查询处理，其中包含了物理优化和逻辑优化两个层次。,物理优化,：对关系（数据库）基本操作符运算在实现中优化（,如索引、排序、聚集（聚簇）等）,逻辑优化,：在进行物理优化前先应有一个合理（最优）操作符次序或一些操作策略选择,4/69,4.1.1 分布式查询处理定义,4.1.1.2 分布式查询处理,分布式数据库环境是由虚拟全局数据库和实际存在各局部数据库组成。DDB分布性，使虚拟全局数据库在抽象时还有逻辑数据库（LgDB)和物理数据库（PDB）概念；,DDB四层模式结构,中局部概念层是由物理数据库映射到局部场地上，即形成局部数据库；,分布式查询处理包含了全局查询处理和局部查询处理两个部分。不过，对使用 DDB 来说，用户（应用）只看到 GDB，且也只在全局关系上执行查询。而用户这种查询是经过查询语言表示，并由系统将其转换。因而在查询执行过程中，实际上最终要包括到详细场地上物理关系查询。,所以，分布式查询对应全局层三种数据库有三种查询：,用户查询、逻辑查询和物理查询,。,5/69,4.1.1 分布式查询处理定义,集,中,式,三,层,摸,式,结,构,图,分,布,式,四,层,摸,式,结,构,图,6/69,4.1.1 分布式查询处理定义,4.1.1.2 分布式查询处理,用户查询（Q,u,）：,是DDB中在全局数据库（GDB）上查询；,逻辑查询（Q,L,）：,是DDB中在逻辑数据库（LgDB）上查询；,物理查询（Q,p,）：,是DDB中在物理数据库（PDB）上查询。,7/69,4.1.1 分布式查询处理定义,4.1.1.3 三种查询之间联络,上述三种查询之间有一定联络，这种联络依赖于DDB分片模式定义和分配模式定义，我们可用以下定理来描述：,定理 4.1,：,对于任一用户查询Q,u,，,对应逻辑查询为Q,L,=Q,u,FS,-1,，,对应物理查询为Q,P,=Q,u,FS,-1,AS,1,。,证实：,由3.1节分片模式定义，有GDB=FS,-1,(LgDB)，,所以，有Q,u,(GDB)=Q,u,(FS,-1,(LgDB)=Q,u,FS,-1,(LgDB)；,一样，由3.1节分配模式定义，有LgDB=AS,-1,(PDB)；,所以有 GDB=,FS,-1,(LgDB),=FS,-1,AS,-1,(PDB)，,因而，有Q,u,(GDB)=Q,u,(FS,-1,AS,-1,(PDB)=,Q,u,.FS,-1,AS,-1,(PDB),。,8/69,4.1.1 分布式查询处理定义,4.1.1.4 分布式查询定义,定理4.1讨论是全局层查询处理，其中对用户查询，在系统中实际存在了两次转换：,全局查询到逻辑查询转换,和,逻辑查询到物理查询转换,。以下列图所表示：,FS,AS,GDB LgDB PDB,转换1 转换2,Q,u,Q,L,Q,p,9/69,4.1.1 分布式查询处理定义,定义4.1,：,分布式数据库系统查询处理Q是一算法：算法输入是用户查询Q,u,，算法输出是对应物理查询Q,p,;算法功效是将用户查询按照每个全局关系分布结构转换成一个最优物理查询。,DDB查询优化主要讨论以下问题：,全局查询处理转换、优化,因为分布性引发数据在场地间移动时数据副本选择和查询操作序确实定等策略,对于物理查询详细执行，就相当于在一个集中式数据库上操作（即对局部数据库操作），其上查询处理属于局部查询处理。集中式数据库所讨论查询处理及优化策略是本专题技术基础。,10/69,4.1.2 分布式查询代价原因综述,分布式查询代价原因以下：,IO代价（即估算输入/输出操作次数）,CPU使用情况,传输代价（包含数据量传输费用、传输延迟时间，以及包括,传输数据控制信息及控制次数）,分布事务处理管理策略（事务可串行化、分布式并发控制、分,布式恢复）,分布查询操作方法（如联接操作、,并操作、二元操作以及全局查,询和局部查询不一样操作）对效率影响,11/69,4.2 全局查询转换基础知识,4.2.1 查询表示式等价性,4.2.2 查询树,4.2.3 等价变换规则,4.2.4,限定关系简化表示,4.2.5,谓词合取性,4.2.6,扩充关系代数规则,12/69,4.2.1 查询表示式等价性,关系数据模型有三种查询语言：,代数语言、元组演算语言、域演算语言,，这三种语言是等价,用代数语言表示查询处理最为方便,SQL,语言是关系数据库标准语言，它是完备，对用户而言，提供非过程查询语言最为方便,这里假设,DDBMS,提供完全透明,全局用户能够用,SQL,语言操纵语句来,表示全局查询，SQL语句是对DDB进行查询外部表示式,13/69,4.2.1 查询表示式等价性,查询要得到结果，必须对关系进行详细操作：,五种基本操作,并（）、差（）、迪卡尔积（）、选择（,）、投影（,）,五种导出操作,交（）、商（）、联接（）、自然联接（）、半联接（）,ij,为了便于查询处理转换，将上面十种关系操作数分为两类：,一元操作，用U表示,二元操作，用B表示,属于一元操作只有和，而其余操作都是二元操作,14/69,4.2.1 查询表示式等价性,例：,对全局关系 Emp,有以下SQL查询表示式,Select ENAME,DNO,From Emp,Where DNO=15;,（4-1）,其对应代数操作表示式为：,ENAME，DNO,（,DNO=15,Emp）（4-2）,或,DNO,=,15,（,ENAME，DNO,Emp）,（4-3）,本例,表示了不一样操作次序仍可取得相同结果。这就是等价概念。,定义4.2：,两个查询表示式 E1 和 E2 是等价，假如其,查询结果是相同，记为 E1,E2。,15/69,4.2.2 查询树,定义4.3：,查询树是一棵树 T=(V,E)，其中：,1,）,V是节点集，每个非叶结点是关系操作符，叶节点是关系名（即查询包括关系）；,2）E是边集，二节点有边（V,1,V,2,），当且仅当 V,2,是 V,1,操作分量。,通常，人们用查询树表示查询表示式内部结构。,16/69,例,4.1,：,有查询,Q,1,：查询北部地域（,AREA=,North,）所属部门发出订单供给商号。这里包括两个全局关系,Dept(D#,DNAME,MGTRSSN,AREA),和,Sp(S#,P#,D#,QUAN),，,SQL,表示式为：,Select S,From Dept,Sp,Where Sp,D,=Dept,.,D,And AREA=,North;,（,复习多表连接内容,）其对应代数表示式为：,S#,AREA,=,North,（Sp,Dept）,D,=D,其对应查询树以下：,s#,AREA=,Nouth,D,=D,Sp Dept,4.2.2 查询树,显然，边为 E,1,（,，,Sp）,D,=D,时，则,Sp是非叶节点,分量。,17/69,4.2.2 查询树,例子：多表连接操作,StudentID,StudentName,StudentAge,1,张三,25,2,李四,26,3,王五,27,4,赵六,28,5,无名氏,27,表Student，存放学生基本信息,BorrowBookID,BorrowBookName,StudentID,BorrowBookPublish,1,马克思主义政治经济学,1,电子工业出版社,2,毛泽东思想概论,2,高等教育出版社,3,邓小平理论,3,人民邮电出版社,4,大学生思想道德涵养,4,中国铁道出版社,5,C语言程序设计,5,高等教育出版社,表BorrowBook，存放学生所借书,18/69,4.2.2 查询树,例子：多表连接操作,Select,Student.StudentName,Student.StudentAge,BorrowBook.BorrowBookName,BorrowBook.BorrowBookPublish,FROM,Student,BorrowBook,WHERE,Student.StudentID=BorrowBook.StudentID,运行结果以下：,StudentName,StudentAge,BorrowBookName,BorrowBookPublish,张三,25,马克思主义政治经济学,电子工业出版社,李四,26,毛泽东思想概论,高等教育出版社,王五,27,邓小平理论,人民邮电出版社,赵六,28,大学生思想道德涵养,中国铁道出版社,19/69,用查询树表示愈加复杂查询表示式：,E=,A,(S,（R）),A,（TRS）,A,A,S ,T ,R R S,4.2.2 查询树,查询树能够了解为全局查询树，其叶节点是全局关系。,依据等价定义，可用三种方式描述查询：,SQL表示式（查询语句）,代数表示式,查询树,注意:查询树不一样于,分解树,20/69,4.2.2 查询树,图 分解树,21/69,4.2.3 等价变换规则,利用等价性定义，等价规则能够归纳为两类,（1）单个关系代数操作变换规则,R,RR R,R,R,R,R,RR R,R,R,R,RR R,P,（,）,R,R,R,A,（,）,其中，关系R与空关系进行操作（联接）表示了一个空操作，在查,询转换过程中是能够消去操作（某种程度优化）,例4.2：（）,（,）,22/69,4.2.3 等价变换规则,（2）多个关系模式操作变换规则,设有多个关系，其关系模式分别为R,，,S，T，在一定条,件下有以下规则：,一元操作交换律：U,1,（,U,2,（R)U,2,（,U,1,（R),二元操作结合律：(R)B(S)B(T)(R)B(S)B(T),二元操作交换律：(R)B(S)(S)B(R),一元操作幂等律：U(R)U,1,U,2,(R),一元操作对二元操作分配律：U(R)B(S)(U(R)B(U(S),一元操作因式分解律：(U(R)B(U(S)U(R)B(S),利用等价变换规则能够改变操作序实现查询优化,23/69,4.2.4 限定关系简化表示,逻辑关系（逻辑片段）是对全局关系进行、,操作得到,从对关系操作而言，逻辑关系是带有,一定限定条件,关系，我们可称它为,限定关系,，它限定条件是谓词或属性集,定理 4.1,指出用户查询必有对应对逻辑关系和物理关系查询，,其中对逻辑关系查询就是对这种限定关系操作，也就是说，对关系操作能够深入地再作用到限定关系上,给出,限定关系简化表示为,R:Q,，其中：R是全局关系；Q是限定关系即逻辑关系应满足谓词。,R:Q读作“全局关系,R,对应于限定条件,Q,逻辑关系（即限定关系）”,限定关系,R:Q,被作为一个操作数，所以，它能够被关系代数所操作，这是一个扩充操作,24/69,4.2.5 谓词合取性,什么叫谓词合取性,假设有,全局关系模式 R，F 是一谓词，Q 是关系所满足限定条件，也是一谓词；在关系运算中由 Q 与 F 共同组成谓词，即称含有谓词合取性质。比如 Q,R,F、Q,R,Q,S,F 等。,这种合取性本身可能引发一些矛盾：,如例3.1中，Supplier划分为两个逻辑关系就有两个限定关系，其中Q,1,：CITY=London，Q,2,：CITY=Paris，就可能有表示式：,CITY=Paris,S1：CITY=London=,即，当限定关系谓词合取是含有矛盾限定条件，实际上将是一个空操作。,这种,谓词合取可能为空性质,对查询转换（执行）时很有用，我们能够依据逻辑片段所含有内涵性质，对其操作可能遗留下一些有矛盾表示式为空情况以,简化查询,执行。,25/69,4.2.6 扩充关系代数规则,对,RQ,操作是关系代数操作一个扩充，其中使用限定关系作为操作数。将关系代数操作作用到限定关系上有,以下八条扩充规则,能够依据八个对限定关系操作规则，讨论扩充关系代数表示式转换等价性,两个限定关系是等价，即当它们两个基础关系是等价，且其限定条件都表示了相同真值函数（即当对同一元组用两个限定条件时，能得到相同真值）,用于限定关系命题：,命题4.l：,所相关系代数含有等价转换一样适合用于限定关系。,26/69,直观地说，对一个全局关系进行选择操作（谓词为Q,R,）得到逻辑关系再做选择操作（谓词为F），相当于对全局关系做了一次选择操作，但其谓词为F AND Q,R,，即谓词合取性;,4.2.6 扩充关系代数规则,RQ,R,RFQ,R,规则（1）,规则（2）,对限定关系投影出一些属性（A），即使计算谓词条件属性不在A中，所得到限定关系谓词不会改变，仍是Q,R,。,A,RQ,R,A,RQ,R,27/69,4.2.6 扩充关系代数规则,RQ,R,SQ,S,（R）（S）Q,R,Q,S,一样有谓词合取性。,规则（3）,规则（4）,RQ,R,SQ,S,（R）,（S）Q,R,两个限定关系差操作是不对称。,规则（5）,RQ,R,SQ,S,（R）（S）Q,R,Q,s,两个限定关系并操作，其谓词含有合取性。,规则（6）,RQ,R,SQ,s,(R)(S)Q,R,Q,S,两个限定关系交操作是由差操作推导出。,规则（7）,R:Q,R,S:Q,S,(R),(S):Q,R,Q,S,F,两个限定关系联接操作也是导出操作,。,R:Q,R,S:Q,S,(R),(S):Q,R,Q,S,F,规则（8）,F,F,28/69,4.3 全局查询到逻辑查询转换,讨论“查询转换”，是讨论分布式数据库查询处理优化。即在转换过程中，利用等价变换规则，综合并充分地考虑分布查询代价原因，使分布查询处理逐步实现优化。,4.3.1 全局查询到逻辑查询转换步骤,4.3.2 等价转换准则,4.3.2.1 全局查询转换成查询树,4.3.2.2 生成优化逻辑查询树,29/69,4.3.1 全局查询到逻辑查询转换步骤,标准上能够按两步实现分布式查询第一次转换（全局查询到逻辑查询），每一步可恪守一些转换规则，以实现部分优化：,第一步：,将全局查询表示式（SQL语法和代数操作表示式）转换成,全局,查询内部结构形式,（查询树）,在其转换过程中需要,利用等价变换规则,及其所归纳出来,两个转换准则（C1，C2）,第二步：,将全局查询树与模式分解树合并转换成部分优化,逻辑关系查询树,，或称分解树化简操作。其中包含：将全局查询树叶节点按分片模式定义逻辑关系名，取代全局关系名（查询树与分解树合并），并分别利用变换规则，化简成部分优化逻辑查询树。,其实现过程中，除了应用转换准则C1，C2以外，,还有C3C6准则,。,30/69,4.3.2.1 全局查询转换成查询树,例4.4：对例4.1查询树(a)，利用代数操作等价变换规则可有如图4.4所表示。,图4.4 全局查询树转换范例,31/69,4.3.2.1 全局查询转换成查询树,分析,：,图4.4（a）是以下代数表示式查询树：,S#,AREA=North,（Sp Dept）,D=D,图4.4,（b）是利用,一元操作对二元操作分配律规则：,U(R)B(S),把,一元操作向下移动,，这时代数操作表示式为：,(U(R)B(U(S)，,S#,（Sp ,AREA=North,（Dept）,D=D,图4.4（c）是利用一元操作幂等律：U(R)U1 U2(R),对“操作数关系”分解为多个一元操作，以缩减“操作数关系”,。即经过替换运算得：,S#,（,S#，D#,（Sp）,S#,AREA=North,（Dept）,D=D,32/69,准则C1,：缩减二元操作数关系，利用一元操作对二元操作分配律，将一元操作向下移动。,U(R)B(S),(U(R)B(U(S),准则C2,：用一元操作幂等律对操作数关系产生适当一元操作或分解成多个一元操作，以缩减操作数关系。,U(R)U,1,U,2,(R),4.3.2.1 全局查询转换成查询树,结论：,查询树相当于对一个集中式数据库查询，集中式数据库逻辑优化技术能够作用于其上。详细说是要：,对全局查询树中一元操作尽可能下移到叶节点；,假如查询树中有二元操作，则应尽可能先缩减二元操作操作数。由此，可取得等价转换准则C1和C2。,33/69,4.3.2.2 生成优化逻辑查询树,生成优化逻辑查询树，就是把查询树与全局模式分解树一起来考虑，需要用到限定关系等价变换性质。这一步操作比较复杂，基本上分为以下几个子过程：,4.3.2.2.1 分解树化简处理过程,4.3.2.2.2 分解树与查询树合并过程,4.3.2.2.3 一元操作合并过程,4.3.2.2.4 分布联接化简过程,4.3.2.2.5 一个实例,34/69,4.3.2.2.1 分解树化简处理过程,分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合,。,要将全局查询转换成逻辑查询，需要对分解树进行处理。对于一个全局查询而言，并非组成全局关系全部逻辑关系都将包括到，往往只使用其中某一些，所以应依据查询树对分解树进行处理。我们称它为,分解树化简处理,。,图 分解树结构,35/69,4.3.2.2.1 分解树化简处理过程,当全局查询用查询树表示，经过C1、C2 准则处理后，查询要用到逻辑关系条件在查询树中就表现出来了。接着，能够依据这些条件消去一些与查询无关逻辑关系，即去掉一些操作为空子树。,假设在查询树中，存在一棵关于全局关系R（U，True，T）一元操作U,n,U,n-,1,U,1,子查询树。令F为U,l,，U,n,中全部选择操作谓词逻辑合取，即有 F=。假如没有选择操作，则F=True，令A为U,1,，U,n,中全部投影操作中属性和谓词P,j,中所包括属性并，即有：,令Q,s,=U,n,U,1,(R)为关系R上子查询，下面给出分解树化简定义：,定义4.4：,一个关系R,i,（U,i,，Q,i,，S,i,）对于子查询Q,s,是无用，,当F,Q,i,=False，U,i,A=；,不然是有用。,假如R,i,是诱导分片所得关系，当其主关系是无用，它也是无用,。,36/69,4.3.2.2.1 分解树化简处理过程,例4.5,设相关系R,0,上,子查询Qs=,其查询子树如图4.7（a）所表示，R,0,分解树,见图3.6,，有 F=P,1,P,2,，A=A,1,A,2,A（P,1,）A（P,2,）。,(R,0,),，,假设有FQ,1,=Flase，AU,221,=,则化简后分解树如图4.7（b）所表示。,图4.7 分解树化简,37/69,4.3.2.2.1 分解树化简处理过程,图3.6 独立分片操作后分解树结构,38/69,4.3.2.2.1 分解树化简处理过程,依据上述叙述，可从中归结两个化简分解树时有用准则C3，C4：,准则 C3,：在全局查询转换成逻辑查询过程中，能够,消去谓词合取含有矛盾子树，即可消去选择操作结果为空子查询树,。,准则C4,：在全局关系转换成逻辑关系查询过程中，也能够消去联接操作结果为空子树。,39/69,4.3.2.2.2 分解树与查询树合并过程,在分解树简化处理后应该与查询树合并。,这是两种性质不一样树，但因为,分解树是由全局关系经过分片操作形成，即一组代数操作,。,查询树是对全局关系查询操作，也是一组代数操作,。所以，我们能够用以下算法实现转化。,算法4.2：,简化分解树转化为逻辑查询树,。,输入：已经化简后分解树。,输出：从全局查询转换为逻辑查询树。,方法：从根节点开始：,(1)假如节点上操作Oj=H或DH，则将其转换为U（一元）操作节点；,(2)假如节点上操作Oj=V，则将其转换为联接操作节点，联接属性是k；,(3)假如节点操作Oj=AO，则无须转换；,(4)直至将全部节点处理完成，最终输出（取得）对逻辑片段查询树。,(5)当然，当得到了逻辑片段(关系)查询树后，还应按C1、C2准则重复变换，使得一元操作下移，二元操作操作数尽可能缩减。,40/69,4.3.2.2.3 一元操作合并过程,一元操作合并,在得到逻辑查询树后可能还有一些性质，如在逻辑关系与二元操作之间或在二元操作之上存在若干一元操作。这时，就应按集中式数据库逻辑优化中一些技术，使对同一逻辑关系多个选择、投影，应合并成一个选择操作后接一个投影操作，且尽可能使查询树上相连一元操作最多只有2个。,41/69,4.3.2.2.4 分布联接化简过程,所谓分布联接是指含有两个以上（含两个）全局关系联接（尤其是它们不在同一场地上）。,比如：在查询树中，假如有两个全局关系R，S联接时，对R，S全部元组都应进行比较；当这两个全局关系逻辑关系不在同一场地上，就须经通讯形成份布联接。图4.8中，节点表示全局关系逻辑关系（分片后），边表示两节点间联接不为空。,图4.8（a）是R，S全联接图，,即R全部逻辑关系（R,1,，R,n,）与S全部逻辑关系（s,1,，S,n,）进行完全分布联接。对于DDB来讲，,这种联接代价是极大。所以，在设计DDB时，对于有两个联接操作关系（经常表达在实体间关联性质）应尽可能使其划分合理,。,图4.8 分布联接图,42/69,4.3.2.2.4 分布联接化简过程,对于完全联接化简法有两种：,一个是部分分布联接图如图4.8（b），,其中部分节点间没有联通，使完全联接图形成两个或两个以上子图。,另一个是简化为简单分布联接图如图4.8（C），每对节点间只有一条边。,图4.8 分布联接图,43/69,4.3.2.2.4 分布联接化简过程,DDB中分片操作支持,诱导操作实际上是这种简单分布联接,，R与S逻辑关系只存在一对一联接，这就能够,先做局部联接，再完成份布联接，其通讯开销一定会降低,。所谓先做局部联接，就是先在逻辑关系之间完成联接，然后再合并。,例4.6 设有图4.9（a）所表示查询树，S,1,，S,2,是按R,1,，R,2,诱导分片操作所得到逻辑关系，该查询树能够依等价变换规则转换成图4.9（b）所表示。图4.9（c）表示简单分布联接查询树。,图4.9 简单分布联接,44/69,内容回顾（3.2.2.4 诱导分片）,45/69,4.3.2.2.4 分布联接化简过程,从例4.6我们能够看到：对于图4.9（c）查询树表示了先做联接操作再做并操作，有利于深入优化查询树，其中使用了一些等价改变规则。所以可归纳出分布联接转换准则C5。,准则C5,：在全局查询中含有分布联接时，可将联接下属并操作上推。,附：,二元操作结合律：(R)B(S)B(T)(R)B(S)B(T),二元操作交换律：(R)B(S)(S)B(R),46/69,4.3.2.2.5 一个实例,例子,：至此，我们能够将,例4.4,全局查询转换再依据上述准则进行优化。假设全局关系Dept按部门号水平分片，其谓词为：,Q1：D110,Q2：D1120,Q3：D2130,且D=110在“North”地域。同时有约定；North地域零件由London供给者供给。图4.10是利用上列准则对图 4.4深入转换。,图4.4 全局查询树转换范例,47/69,4.3.2.2.5 一个实例,图4.10是例4.l全局查询到逻辑查询最终查询树，其中经过了从C1C5准则。,准则C1,：缩减二元操作数关系，利用一元操作对二元操作分配律，将一元操作向下移动。,准则C2,：用一元操作幂等律对操作数关系产生适当一元操作或分解成多个一元操作，以缩减操作数关系。,准则 C3,：在全局查询转换成逻辑查询过程中，能够,消去谓词合取含有矛盾子树，即可消去选择操作结果为空子查询树,。,准则C4,：在全局关系转换成逻辑关系查询过程中，也能够消去联接操作结果为空子树。,准则C5,：在全局查询中含有分布联接时，可将联接下属并操作上推。,48/69,4.4 逻辑查询到物理查询转换,逻辑转换是把注意力集中于怎样将一元操作尽可能合并，先选择后投影提取公共因子、消去无用子表示式（子树）、降低二元操作数等方面，最终取得简化了查询树和操作表示式。,那么，物理查询转换内容是什么呢？转换策略是什么呢？转换方法是什么呢？,本节讨论以下内容：,4.4.1 物理转换中基本内容和方法,4.4.2 物理转换策略与方法分析,49/69,4.4.1 物理转换中基本内容和方法,一、什么是物理查询转换？,所谓从逻辑查询到物理查询转换，是指将逻辑查询转换得到简化了查询树，转换成详细每个场地上局部操作命令和数据传输命令过程。,也就是说，全局查询须两次转换后才形成一个详细分布执行计划（DEP），然后才是交付给各个局部场地去执行。,在实际执行过程中也一样存在查询处理优化，这就是前面提到过分布式查询处理中局部层优化。,50/69,4.4.1 物理转换中基本内容和方法,二、物理转换基本内容和策略综述,物理查询转换过程，将包括到物理副本和查询处理场地，即执行环境。尤其对于二元操作数不在同一场地时或者有多个副本可选择情况时，其“执行环境”概念更为主要。所以，物理转换时普通注意以下原因：,操作副本选择,操作执行次序选择,操作方法选择,通讯代价,评定数据量,51/69,4.4.2 物理转换策略与方法分析,4.4.2.1,选择操作副本标准和策略,4.4.2.2,操作执行次序选择,4.4.2.3,操作方法选择,4.4.2.4,通讯代价计算,4.4.2.5,操作场地选择,52/69,4.4.2.1 选择操作副本标准和策略,操作副本选择,是选定逻辑关系相对应物理关系有多个副本时详细化。标准上，对不一样查询有不一样详细选择。各个物理关系副本其使用情况、路径代价和使用要求不完全一样，若按随机选定显然不合理，应该恪守一定协定，选择一个理想（合理）副本。,副本使用状态,可分为可用和不可用。不可用指是可能副本所在场地出现故障或到该场地通讯有了故障；可用则又可能处于繁忙或轻松状态，这主要是指对副本可用时等候查询多少。,为此，能够给出副本选择普通标准：,本场地物理关系优先。假如查询始发场地上有逻辑关系一个对应物理关系，就应尽可能选择该物理关系,同场地上有二元操作，则应尽可能选择同一场地上对应物理关系完成二元操作，以降低数据传送,在查询等候中数据最小物理关系应被优先选中,代价最小应优先选中,53/69,4.4.2.2 操作执行次序选择,在全局查询到逻辑查询转换时产生,查询树已经部分地蕴含了部分操作次序，如执行时从叶到根向上执行。然而，这并没有全部地给出最好执行次序。,首先，从叶子到根向上执行未必会产生最好效果；,另首先，对查询树上有二元操作如并操作联接操作时，其执行次序还有许多方面能够“优化”。,另外，为了对数据库存取进行定量分析，需要定义数据库统计信息，以确定数据量大小。,即利用一个统计方法使查询执行前后对物理关系尺寸改变能有所预计，给出一个满意执行次序。,一个行之有效方法是计算物理关系静态特征，估算出对物理关系操作后改变，从而决定中间关系特征,。,54/69,4.4.2.3 操作方法选择,关于操作方法选择，更多地取决于对局部数据库存取方式,在物理转换时应尽可能注意到对同一次数据库存取中一些代数操作是否能组合在一起完成,尽可能防止屡次内/外存调用，这与局部层优化有很大关系,普通来说，在物理转换时，对同一场地上数据库存取时要注意对同一物理关系全部操作序列统一考虑，对于怎样完成对应数据库存取，能够由局部层去考虑,55/69,4.4.2.4 通讯代价计算,这里介绍分布式数据库最特殊代价原因：场地间信息传输费用估算。,在传输过程中普通有两种影响：费用（cost）和延迟（delay）,。,一次传输传输费用（TC）和传输延迟（TD）能够用函数法表示，它们与数据量大小成线性关系：,TC（X）C0+XC1 （4-9a）,TD（X）D0+XD1 （4-9b）,其中，C0，C1，D0，D1对均是与系统相关常数。C0相当于场地间传输数据初始（开启一次）所需固定费；C1是网络传输数据统一费用；D0是两场地建立一次连接所需固定时间；D1是网络传输数据统一单位传输速率。,56/69,4.4.2.5 操作场地选择,场地选择包含在逻辑关系转换为物理关系过程中，选择了物理关系，逻辑关系就有了确定场地。,不过还需考虑一系列问题，比如，查询结果场地是否就是查询始发场地呢？中间每个操作在何处完成？完成后送何处？,场地确定也包含有优化策略。依据系统设计总目标和对应优化策略，有详细场地选定算法。,57/69,4.5 联接操作,4.5.1 联接操作主要性,4.5.2 联接操作,4.5.3 半联接操作原理和不对称性,4.5.4 半联接操作缩减作用,4.5.5 半联接程序作用,4.5.6 半联接程序详细过程,58/69,4.5.1 联接操作主要性,关系数据库由许多关系组成，关系与关系之间联络主要经过联接操作表现出来，因而在二元操作中，联接操作远比其它操作用得多。,讨论联接，其实包含了“选择投影联接”综合问题，即二元操作和一元操作综合优化问题。,分布式查询处理联接操作，更是影响分布式查询效率最关键原因。,在DDB中，联接操作大量数据会引发场地间传输，它直接影响整个系统性能。,当前对联接操作优化有两种趋向：,一个是采取半联接技术来降低联接操作操作数，以降低通讯费用；,另一个是直接进行联接操作代价计算,59/69,4.5.2 联接操作,联接操作,是从两个关系笛卡尔积中选取属性间满足一定条件元组。记作：,其中A和B分别为R和S上可比属性组。,自然联接,（Natural join）是一个特殊等值联接，它要求两个关系中进行比较分量必须是相同属性组，而且要在结果中把重复属性去掉。即若R和S含有相同属性组B，则自然连接可记作：（,实例,）,等值连接,（equi-join），为“”连接运算称为等值连接。它是从关系R与S笛卡尔积中选取A、B属性值相等那些元组。即等值连接为：（,实例,）,60/69,（回顾）自然联接,图 自然联接实例,自然联接,结果是在 R 和 S 中在它们公共属性名字上相等全部元组组合。例以下面是表格“雇员”和“部门”和它们自然联接:,61/69,（回顾）等值联接,图-联接实例,-联接和等值联接,假如我们要组合来自两个关系元组，而组合条件不是简单共享属性上相等，则有一个更普通形式连接算子才方便，这就是-联接(或 theta-联接)。是在集合,中二元关系。,结果由在,R,和,S,中满足关系 元素全部组合组成。只有,S,和,R,表头是不相交，即不包含公共属性情况下，-连接结果才是有定义。,实例：,考虑分别列出车模和船模价格表“车”和“船”。假设一个用户要购置一个车模和一个船模，但不想为船花费比车更多钱。在关系上-联接,CarPrice,BoatPrice,生成全部可能选项一个表。,62/69,4.5.3 半联接操作原理和不对称性,半联接操作,是关系代数操作中联接（JOIN）操作一个缩减，关系R和S半联接记为RS。,其结果关系是R和S自然联接（Natural JOIN）后，在R属性上投影,，可用下述表示式表示：,RS=,R,（RS）,等价方法：将S中与R有相同属性名属性集投影出来，然后与R完成自然联接，其等价公式为：,RS=R,（,B,S）,具不对称操作性：RSSR。,半联接操作是一个导出操作：,一个关系分片是依据另一个与其相关联性质关系属性来划分，即诱导分片。而诱导分片就是用“半联接”概念实现，即诱导分片是两个相关关系半联接产生。或者详细地说，是两个相关关系实现自然联接后，在主关系属性上投影。,一个半联接操作实例,63/69,（回顾）半联接,图 半联接实例,半联接,结果只是在,S,中有在公共属性名字上相等元组全部,R,中元组。,实例：,“雇员”和“部门”和它们半联接表:,64/69,4.5.4 半联接操作缩减作用,例4.17,有R（A,B）和 S（B,C），依据半联接计算公式有：和 。假如有图 4.21（a）实例，则 R S结果如 4.21（b）所表示，S R结果如图4.21（C）所表示。,图4.12 半联接操作不对称性与缩减作用,从图4.21（b）、（c）可得出结论：半联接操作,对操作数R或S有缩减作用,，且因为,其不对称性则各自缩减程度不一样,。半联接操作缩减性与在联接操作前先对操作数关系做选择和投影有相同效果。尤其在分布式环境中，可用半联接操作降低网上数据传送量。,65/69,4.5.5 半联接程序作用,半联接程序,是用半联接技术实现联接操作程序，即用一组含有半联接与联接操作，映射出含有与等值联接相同结果过程。,(4-11a),(4-11b),（411a）、（411b）式说明半联接程序与两个关系直接等值联接等价。,一样，在分布式数据库中，当R，S两个关系不在相同场地上时，用（411a）公式或（411b）,公式处理，可,以降低联接操作数据传送量，而且半联接程序技术能够缩减它操作数。,66/69,4.5.6 半联接程序详细过程,以式（4-11a）为例，且假定 R和S不在同一场地：,在s场地对S关系做投影操作，使S关系缩减为S：,将S送往r场地；,在r场地上完成R与S半联接操作，使R关系缩减为,R,：,将R关系送回S场地；,在S场地完成R与S联接操作。,图4.22 半联接程序操作,图4.22关键技术思想是只将联接操作相关操作分量在网上进行传输。R与S关系在A=B条件下联接，R、S关系只有公共属性值相等那些元组才有意义。,67/69,附件：主讲教师和助教信息,单位：厦门大学计算机科学系,E-mail:ziyulin,个人网页：of Computer Science,Xiamen University,Nov,69/69,