厦门大学计算机科学系市公开课一等奖百校联赛特等奖课件.pptx

分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024厦门大学计算机科学系 11月林子雨林子雨厦门大学计算机科学系厦门大学计算机科学系E-mail:分布式数据库技术分布式数据库技术专题三专题三 分布式查询处理分布式查询处理 厦门大学计算机科学系硕士课程第1页分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024专题三 分布式查询处理第第4章章 分布式查询处理分布式查询处理4.1 4.1 4.1 4.1 分布式查询特点分布式查询特点分布式查询特点分布式查询特点4.2 4.2 4.2 4.2 全局查询转换基础知识全局查询转换基础知识全局查询转换基础知识全局查询转换基础知识4.3 4.3 4.3 4.3 全局查询到逻辑查询转换全局查询到逻辑查询转换全局查询到逻辑查询转换全局查询到逻辑查询转换4.4 4.4 4.4 4.4 逻辑查询到物理查询转换逻辑查询到物理查询转换逻辑查询到物理查询转换逻辑查询到物理查询转换4.5 4.5 4.5 4.5 联接操作联接操作联接操作联接操作第2页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.1 集中式数据库查询基本原理4.1.1.2 分布式查询处理4.1.1.3 三种查询之间联络4.1.1.4 分布式查询定义4.1.2 分布式查询代价原因综述4.1 分布式查询特点第3页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.1 4.1.1.1 集中式数据库查询基本原理集中式数据库查询基本原理集中式数据库查询基本原理集中式数据库查询基本原理 在集中式数据库环境中查询处理，是将用户查询（由查询语言表在集中式数据库环境中查询处理，是将用户查询（由查询语言表示）转换成物理查询处理，其中包含了物理优化和逻辑优化两个层次。示）转换成物理查询处理，其中包含了物理优化和逻辑优化两个层次。物理优化物理优化：对关系（数据库）基本操作符运算在实现中优化（：对关系（数据库）基本操作符运算在实现中优化（如如索引、排序、聚集（聚簇）等）索引、排序、聚集（聚簇）等）逻辑优化逻辑优化：在进行物理优化前先应有一个合理（最优）操作符次：在进行物理优化前先应有一个合理（最优）操作符次序或一些操作策略选择序或一些操作策略选择 第4页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.2 4.1.1.2 分布式查询处理分布式查询处理 分布式数据库环境是由虚拟全局数据库和实际存在各局部数分布式数据库环境是由虚拟全局数据库和实际存在各局部数据库组成。据库组成。DDB分布性，使虚拟全局数据库在抽象时还有逻辑数分布性，使虚拟全局数据库在抽象时还有逻辑数据库（据库（LgDB)和物理数据库（和物理数据库（PDB）概念；）概念；DDB四层模式结构四层模式结构中局部概念层是由物理数据库映射到局部中局部概念层是由物理数据库映射到局部场地上，即形成局部数据库；场地上，即形成局部数据库；分布式查询处理包含了全局查询处理和局部查询处理两个部分布式查询处理包含了全局查询处理和局部查询处理两个部分。不过，对使用分。不过，对使用 DDB 来说，用户（应用）只看到来说，用户（应用）只看到 GDB，且也，且也只在全局关系上执行查询。而用户这种查询是经过查询语言表示，只在全局关系上执行查询。而用户这种查询是经过查询语言表示，并由系统将其转换。因而在查询执行过程中，实际上最终要包括并由系统将其转换。因而在查询执行过程中，实际上最终要包括到详细场地上物理关系查询。到详细场地上物理关系查询。所以，分布式查询对应全局层三种数据库有三种查询：所以，分布式查询对应全局层三种数据库有三种查询：用户用户查询、逻辑查询和物理查询查询、逻辑查询和物理查询。第5页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义集集中中式式三三层层摸摸式式结结构构图图分分布布式式四四层层摸摸式式结结构构图图第6页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.2 4.1.1.2 分布式查询处理分布式查询处理 用户查询（用户查询（用户查询（用户查询（QQu u）：）：）：）：是是是是DDBDDB中在全局数据库（中在全局数据库（中在全局数据库（中在全局数据库（GDBGDB）上查询；）上查询；）上查询；）上查询；逻辑查询（逻辑查询（逻辑查询（逻辑查询（QQL L）：）：）：）：是是是是DDBDDB中在逻辑数据库（中在逻辑数据库（中在逻辑数据库（中在逻辑数据库（LgDBLgDB）上查询；）上查询；）上查询；）上查询；物理查询（物理查询（物理查询（物理查询（QQp p）：）：）：）：是是是是DDBDDB中在物理数据库（中在物理数据库（中在物理数据库（中在物理数据库（PDBPDB）上查询。）上查询。）上查询。）上查询。第7页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.3 4.1.1.3 三种查询之间联络三种查询之间联络 上述三种查询之间有一定联络，这种联络依赖于上述三种查询之间有一定联络，这种联络依赖于上述三种查询之间有一定联络，这种联络依赖于上述三种查询之间有一定联络，这种联络依赖于DDBDDB分片模式定义和分片模式定义和分片模式定义和分片模式定义和分配模式定义，我们可用以下定理来描述：分配模式定义，我们可用以下定理来描述：分配模式定义，我们可用以下定理来描述：分配模式定义，我们可用以下定理来描述：定理定理定理定理 4.1 4.1 ：对于任一用户查询对于任一用户查询Qu，对应逻辑查询为对应逻辑查询为QL=Qu FS-1，对应物理查询为对应物理查询为QP=Qu FS-1 AS1。证实：证实：证实：证实：由由3.1节分片模式定义，有节分片模式定义，有GDB=FS-1(LgDB)，所以，有所以，有Qu(GDB)=Qu(FS-1(LgDB)=Qu FS-1(LgDB)；一样，由一样，由3.1节分配模式定义，有节分配模式定义，有LgDB=AS-1(PDB)；所以有所以有 GDB=FS-1(LgDB)=FS-1AS-1(PDB)，因而，有因而，有Qu(GDB)=Qu(FS-1AS-1(PDB)=Qu.FS-1AS-1(PDB)。第8页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义4.1.1.4 4.1.1.4 4.1.1.4 4.1.1.4 分布式查询定义分布式查询定义分布式查询定义分布式查询定义 定理定理定理定理4.14.1讨论是全局层查询处理，其中对用户查询，在系讨论是全局层查询处理，其中对用户查询，在系讨论是全局层查询处理，其中对用户查询，在系讨论是全局层查询处理，其中对用户查询，在系统中实际存在了两次转换：统中实际存在了两次转换：统中实际存在了两次转换：统中实际存在了两次转换：全局查询到逻辑查询转换全局查询到逻辑查询转换全局查询到逻辑查询转换全局查询到逻辑查询转换和和和和逻辑逻辑逻辑逻辑查询到物理查询转换查询到物理查询转换查询到物理查询转换查询到物理查询转换。以下列图所表示：。以下列图所表示：。以下列图所表示：。以下列图所表示：FS AS GDB LgDB PDB 转换转换1 转换转换2 Qu QL Qp第9页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.1 分布式查询处理定义 定义定义4.1：分布式数据库系统查询处理分布式数据库系统查询处理Q是一算法：算法输入是用户查询是一算法：算法输入是用户查询Qu，算法输出是对应物理查询，算法输出是对应物理查询Qp;算法功效是将用户查询按照每个全局算法功效是将用户查询按照每个全局关系分布结构转换成一个最优物理查询。关系分布结构转换成一个最优物理查询。DDBDDB查询优化主要讨论以下问题：查询优化主要讨论以下问题：全局查询处理转换、优化全局查询处理转换、优化因为分布性引发数据在场地间移动时数据副本选择和查询操作序因为分布性引发数据在场地间移动时数据副本选择和查询操作序确实定等策略确实定等策略 对于物理查询详细执行，就相当于在一个集中式数据库上操作对于物理查询详细执行，就相当于在一个集中式数据库上操作（即对局部数据库操作），其上查询处理属于局部查询处理。集（即对局部数据库操作），其上查询处理属于局部查询处理。集中式数据库所讨论查询处理及优化策略是本专题技术基础。中式数据库所讨论查询处理及优化策略是本专题技术基础。第10页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.1.2 分布式查询代价原因综述 分布式查询代价原因以下：分布式查询代价原因以下：IO代价（即估算输入代价（即估算输入/输出操作次数）输出操作次数）CPU使用情况使用情况传输代价（包含数据量传输费用、传输延迟时间，以及包括传输代价（包含数据量传输费用、传输延迟时间，以及包括传输数据控制信息及控制次数）传输数据控制信息及控制次数）分布事务处理管理策略（事务可串行化、分布式并发控制、分分布事务处理管理策略（事务可串行化、分布式并发控制、分布式恢复）布式恢复）分布查询操作方法（如联接操作、分布查询操作方法（如联接操作、并操作、二元操作以及全局查并操作、二元操作以及全局查询和局部查询不一样操作）对效率影响询和局部查询不一样操作）对效率影响第11页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2 全局查询转换基础知识4.2.1 4.2.1 4.2.1 4.2.1 查询表示式等价性查询表示式等价性查询表示式等价性查询表示式等价性4.2.2 4.2.2 4.2.2 4.2.2 查询树查询树查询树查询树4.2.3 4.2.3 4.2.3 4.2.3 等价变换规则等价变换规则等价变换规则等价变换规则4.2.4 4.2.4 4.2.4 4.2.4 限定关系简化表示限定关系简化表示限定关系简化表示限定关系简化表示4.2.5 4.2.5 4.2.5 4.2.5 谓词合取性谓词合取性谓词合取性谓词合取性4.2.6 4.2.6 4.2.6 4.2.6 扩充关系代数规则扩充关系代数规则扩充关系代数规则扩充关系代数规则第12页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.1 查询表示式等价性关系数据模型有三种查询语言：关系数据模型有三种查询语言：代数语言、元组演算语言、域演代数语言、元组演算语言、域演算语言算语言，这三种语言是等价，这三种语言是等价用代数语言表示查询处理最为方便用代数语言表示查询处理最为方便SQL 语言是关系数据库标准语言，它是完备，对用户而言，提供语言是关系数据库标准语言，它是完备，对用户而言，提供非过程查询语言最为方便非过程查询语言最为方便这里假设这里假设 DDBMS 提供完全透明提供完全透明,全局用户能够用全局用户能够用SQL语言操语言操纵语句来纵语句来表示全局查询，表示全局查询，SQL语句是对语句是对DDB进行查询外部表示式进行查询外部表示式第13页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.1 查询表示式等价性查询要得到结果，必须对关系进行详细操作：查询要得到结果，必须对关系进行详细操作：五种基本操作五种基本操作五种基本操作五种基本操作 并（并（）、差（）、差（）、迪卡尔积（）、迪卡尔积（）、选择（）、选择（）、投影（）、投影（）pp 五种导出操作五种导出操作五种导出操作五种导出操作 交（交（）、商（）、商（）、联接（）、联接（）、自然联接（）、自然联接（）、半联接（）、半联接（）ijij为了便于查询处理转换，将上面十种关系操作数分为两类：为了便于查询处理转换，将上面十种关系操作数分为两类：一元操作，用一元操作，用U表示表示二元操作，用二元操作，用B表示表示 属于一元操作只有属于一元操作只有和和，而其余操作都是二元操作，而其余操作都是二元操作 第14页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.1 查询表示式等价性 例例：对全局关系对全局关系 Emp,有以下有以下SQL查询表示式查询表示式 Select ENAME,DNO From Emp Where DNO=15;（4-14-1）其对应代数操作表示式为：其对应代数操作表示式为：ENAMEENAME，DNODNO（DNO=15 DNO=15 EmpEmp）（4-24-2）或或 DNODNO=1515（ENAMEENAME，DNO DNO EmpEmp）（4-34-3）本例本例表示了不一样操作次序仍可取得相同结果。这就是等价概念。表示了不一样操作次序仍可取得相同结果。这就是等价概念。定义定义定义定义4.24.24.24.2：两个查询表示式两个查询表示式 E1 和和 E2 是等价，假如其是等价，假如其 查询结果是相同，记为查询结果是相同，记为 E1 E2。第15页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.2 查询树 定义定义4.34.3：查询树是一棵树查询树是一棵树 T=(V,E)，其中：，其中：1）V是节点集，每个非叶结点是关系操作符，叶节点是关系名是节点集，每个非叶结点是关系操作符，叶节点是关系名（即查询包括关系）；（即查询包括关系）；2）E是边集，二节点有边（是边集，二节点有边（V1,V2），当且仅当），当且仅当 V2 是是 V1 操作分操作分量。量。通常，人们用查询树表示查询表示式内部结构。通常，人们用查询树表示查询表示式内部结构。第16页分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024例例4.1：有有查查询询Q1：查查询询北北部部地地域域（AREA=North）所所属属部部门门发发出出订订单单供供给给商商号号。这这里里包包括括两两个个全全局局关关系系Dept(D#,DNAME,MGTRSSN,AREA)和和Sp(S#,P#,D#,QUAN)，SQL表示式为：表示式为：Select S From Dept,Sp Where SpD=Dept.D And AREA=North;North;（复习多表连接内容复习多表连接内容）其对应代数表示式为：）其对应代数表示式为：S#AREA=North（Sp Sp DeptDept）D=D 其对应查询树以下：其对应查询树以下：s#s#AREA=Nouth D=D Sp Dept4.2.2 查询树显然，边为显然，边为 E1（，Sp）D=D时，则时，则Sp是非叶节点是非叶节点 分量。分量。第17页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.2 查询树例子：多表连接操作例子：多表连接操作StudentIDStudentNameStudentAge1张三252李四263王五274赵六285无名氏27表表Student，存放学生基本信息，存放学生基本信息 BorrowBookIDBorrowBookNameStudentIDBorrowBookPublish1马克思主义政治经济学1电子工业出版社2毛泽东思想概论2高等教育出版社3邓小平理论3人民邮电出版社4大学生思想道德涵养4中国铁道出版社5C语言程序设计5高等教育出版社表表BorrowBook，存放学生所借书，存放学生所借书 第18页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.2 查询树例子：多表连接操作例子：多表连接操作Select Student.StudentName,Student.StudentAge,BorrowBook.BorrowBookName,BorrowBook.BorrowBookPublishFROM Student,BorrowBookWHERE Student.StudentID=BorrowBook.StudentID 运行结果以下：StudentNameStudentAgeBorrowBookNameBorrowBookPublish张三25马克思主义政治经济学电子工业出版社李四26毛泽东思想概论高等教育出版社王五27邓小平理论人民邮电出版社赵六28大学生思想道德涵养中国铁道出版社第19页分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024用查询树表示愈加复杂查询表示式：用查询树表示愈加复杂查询表示式：E=E=A A(S(S（R R）)A A（TRSTRS）A A A A S S T T R R S R R S4.2.2 查询树查询树能够了解为全局查查询树能够了解为全局查询树，其叶节点是全局关询树，其叶节点是全局关系。系。依据等价定义，可用三种依据等价定义，可用三种方式描述查询：方式描述查询：SQL表示式（查询语句）表示式（查询语句）代数表示式代数表示式 查询树查询树注意注意:查询树不一样于查询树不一样于分解分解树树第20页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.2 查询树图 分解树第21页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.3 等价变换规则利用等价性定义，等价规则能够归纳为两类利用等价性定义，等价规则能够归纳为两类（1）单个关系代数操作变换规则）单个关系代数操作变换规则 RRR RRR RR R R R RRR RRR R R RR RRR RRR R P P（）RRR R R A A（）其中，关系其中，关系R R与空关系进行操作（联接）表示了一个空操作，在查与空关系进行操作（联接）表示了一个空操作，在查 询转换过程中是能够消去操作（某种程度优化）询转换过程中是能够消去操作（某种程度优化）例例4.2：（）：（）（）第22页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.3 等价变换规则（2）多个关系模式操作变换规则）多个关系模式操作变换规则 设有多个关系，其关系模式分别为设有多个关系，其关系模式分别为R，S S，T T，在一定条，在一定条件下有以下规则：件下有以下规则：一元操作交换律：一元操作交换律：U U1 1（U U2 2（R)UR)U2 2（U U1 1（R)R)二元操作结合律：二元操作结合律：(R)B(S)B(T)(R)B(S)B(T)(R)B(S)B(T)(R)B(S)B(T)二元操作交换律：二元操作交换律：(R)B(S)(S)B(R)(R)B(S)(S)B(R)一元操作幂等律：一元操作幂等律：U(R)U U(R)U1 1U U2 2(R)(R)一元操作对二元操作分配律：一元操作对二元操作分配律：U(R)B(S)(U(R)B(U(S)U(R)B(S)(U(R)B(U(S)一元操作因式分解律：一元操作因式分解律：(U(R)B(U(S)U(R)B(S)(U(R)B(U(S)U(R)B(S)利用等价变换规则能够改变操作序实现查询优化利用等价变换规则能够改变操作序实现查询优化第23页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.4 限定关系简化表示逻辑关系（逻辑片段）是对全局关系进行逻辑关系（逻辑片段）是对全局关系进行、操作得到操作得到从对关系操作而言，逻辑关系是带有从对关系操作而言，逻辑关系是带有一定限定条件一定限定条件关系，我们关系，我们可称它为可称它为限定关系限定关系限定关系限定关系，它限定条件是谓词或属性集，它限定条件是谓词或属性集定理定理 4.1 指出用户查询必有对应对逻辑关系和物理关系查询，指出用户查询必有对应对逻辑关系和物理关系查询，其中对逻辑关系查询就是对这种限定关系操作，也就是说，对其中对逻辑关系查询就是对这种限定关系操作，也就是说，对关系操作能够深入地再作用到限定关系上关系操作能够深入地再作用到限定关系上给出给出限定关系简化表示为限定关系简化表示为R:QR:Q，其中：，其中：R是全局关系；是全局关系；Q是限是限定关系即逻辑关系应满足谓词。定关系即逻辑关系应满足谓词。R:QR:Q读作读作“全局关系全局关系R对应于对应于限定条件限定条件Q逻辑关系（即限定关系）逻辑关系（即限定关系）”限定关系限定关系 R:QR:Q被作为一个操作数，所以，它能够被关系代数被作为一个操作数，所以，它能够被关系代数所操作，这是一个扩充操作所操作，这是一个扩充操作第24页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.5 谓词合取性什么叫谓词合取性什么叫谓词合取性 假设有假设有全局关系模式全局关系模式 R，F 是一谓词，是一谓词，Q 是关系所满足限定条件，是关系所满足限定条件，也是一谓词；在关系运算中由也是一谓词；在关系运算中由 Q 与与 F 共同组成谓词，即称含有谓共同组成谓词，即称含有谓词合取性质。比如词合取性质。比如 QR F、QR QS F 等。等。这种合取性本身可能引发一些矛盾：这种合取性本身可能引发一些矛盾：如如例例3.1中中，Supplier划划分分为为两两个个逻逻辑辑关关系系就就有有两两个个限限定定关关系系，其其中中Q1：CITY=London，Q2：CITY=Paris，就可能有表示式：，就可能有表示式：CITY=Paris S1：CITY=London=即，当限定关系谓词合取是含有矛盾限定条件，实际上将是一个即，当限定关系谓词合取是含有矛盾限定条件，实际上将是一个空操作。空操作。这种这种谓词合取可能为空性质谓词合取可能为空性质对查询转换（执行）时很有用，我们对查询转换（执行）时很有用，我们能够依据逻辑片段所含有内涵性质，对其操作可能遗留下一些有能够依据逻辑片段所含有内涵性质，对其操作可能遗留下一些有矛盾表示式为空情况以矛盾表示式为空情况以简化查询简化查询执行。执行。第25页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.6 扩充关系代数规则对RQ操作是关系代数操作一种扩充，其中使用限定关系作为操作数。将关系代数操作作用到限定关系上有如下八条扩充规则 可以根据八个对限定关系操作规则，讨论扩充关系代数表达式转换等价性 两个限定关系是等价，即当它们两个基础关系是等价，且其限定条件都表示了相同真值函数（即当对同一元组用两个限定条件时，能得到相同真值）用于限定关系命题：命题4.l：全部关系代数具有等价转换同样适用于限定关系。第26页分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024直直观观地地说说，对对一个全局关系一个全局关系进进行行选择选择操作（操作（谓词为谓词为QR）得到）得到逻辑逻辑关系再做关系再做选择选择操作（操作（谓词为谓词为F），相当于），相当于对对全局关系做了一次全局关系做了一次选择选择操作，但其操作，但其谓词谓词为为F AND QR，即，即谓词谓词合取性合取性;4.2.6 扩充关系代数规则RQRQR R RFQRFQR R 规则（规则（1）规则（规则（2）对对限定关系投影出一些属性（限定关系投影出一些属性（A），即使），即使计计算算谓词谓词条件属性不在条件属性不在A中，所得到限定关系中，所得到限定关系谓词谓词不会改不会改变变，仍是，仍是QR。A ARQRQR R AR QR第27页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.2.6 扩充关系代数规则RQRQR RSQSQS S（R R）（S S）QQR RQQS S 一样有谓词合取性。一样有谓词合取性。规则（规则（3）规则（规则（4）R QRS QS（R）（S）QR 两个限定关系差操作是不对称。两个限定关系差操作是不对称。规则（规则（5）R QRS QS（R）（S）QRQs 两个限定关系并操作，其谓词含有合取性。两个限定关系并操作，其谓词含有合取性。规则（规则（6）R QRS Qs(R)(S)QRQS 两个限定关系交操作是由差操作推导出。两个限定关系交操作是由差操作推导出。规则（规则（7）R:QRS:QS(R)(S):QRQSF 两个限定关系联接操作也是导出操作两个限定关系联接操作也是导出操作。R:QRS:QS(R)(S):QRQSF 规则（规则（8）FF第28页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3 全局查询到逻辑查询转换讨论讨论“查询转换查询转换”，是讨论分布式数据库查询处理优，是讨论分布式数据库查询处理优化。即在转换过程中，利用等价变换规则，综合并充化。即在转换过程中，利用等价变换规则，综合并充分地考虑分布查询代价原因，使分布查询处理逐步实分地考虑分布查询代价原因，使分布查询处理逐步实现优化。现优化。4.3.1 全局查询到逻辑查询转换步骤全局查询到逻辑查询转换步骤4.3.2 等价转换准则等价转换准则4.3.2.1 全局查询转换成查询树全局查询转换成查询树4.3.2.2 生成优化逻辑查询树生成优化逻辑查询树第29页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.1 全局查询到逻辑查询转换步骤标准上能够按两步实现分布式查询第一次转换（全局查询到逻辑查询），每一步标准上能够按两步实现分布式查询第一次转换（全局查询到逻辑查询），每一步可恪守一些转换规则，以实现部分优化：可恪守一些转换规则，以实现部分优化：第一步：第一步：n将全局查询表示式（将全局查询表示式（SQL语法和代数操作表示式）转换成语法和代数操作表示式）转换成全局全局查询内部结查询内部结构形式构形式（查询树）（查询树）n在其转换过程中需要在其转换过程中需要利用等价变换规则利用等价变换规则及其所归纳出来及其所归纳出来两个转换准则（两个转换准则（C1，C2）第二步：第二步：n将全局查询树与模式分解树合并转换成部分优化将全局查询树与模式分解树合并转换成部分优化逻辑关系查询树逻辑关系查询树，或称分，或称分解树化简操作。其中包含：将全局查询树叶节点按分片模式定义逻辑关系名，解树化简操作。其中包含：将全局查询树叶节点按分片模式定义逻辑关系名，取代全局关系名（查询树与分解树合并），并分别利用变换规则，化简成部取代全局关系名（查询树与分解树合并），并分别利用变换规则，化简成部分优化逻辑查询树。分优化逻辑查询树。n其实现过程中，除了应用转换准则其实现过程中，除了应用转换准则C1，C2以外，以外，还有还有C3C6准则准则。第30页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.1 全局查询转换成查询树例例4.4：对例：对例4.1查询树查询树(a)，利用代数操作等价变换规则可有如图，利用代数操作等价变换规则可有如图4.4所表示。所表示。图4.4 全局查询树转换范例第31页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.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页分布式数据库 厦门大学计算机科学系 林子雨 8/2/2024准则准则C1：缩减二元操作数关系，利用一元操作对二元操作分配律，将一：缩减二元操作数关系，利用一元操作对二元操作分配律，将一元操作向下移动。元操作向下移动。U(R)B(S)(U(R)B(U(S)准则准则C2：用一元操作幂等律对操作数关系产生适当一元操作或分解成多：用一元操作幂等律对操作数关系产生适当一元操作或分解成多个一元操作，以缩减操作数关系。个一元操作，以缩减操作数关系。U(R)U1U2(R)4.3.2.1 全局查询转换成查询树结论：结论：查询树相当于对一个集中式数据库查询，集中式数据库逻辑优化技术能够作用查询树相当于对一个集中式数据库查询，集中式数据库逻辑优化技术能够作用于其上。详细说是要：于其上。详细说是要：对全局查询树中一元操作尽可能下移到叶节点；对全局查询树中一元操作尽可能下移到叶节点；假如查询树中有二元操作，则应尽可能先缩减二元操作操作数。由此，可取假如查询树中有二元操作，则应尽可能先缩减二元操作操作数。由此，可取得等价转换准则得等价转换准则C1和和C2。第33页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.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页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.1 分解树化简处理过程分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合。要将全局查询转换成逻辑查询，需要对分解树进行处理。对于一个全局查询而要将全局查询转换成逻辑查询，需要对分解树进行处理。对于一个全局查询而言，并非组成全局关系全部逻辑关系都将包括到，往往只使用其中某一些，所言，并非组成全局关系全部逻辑关系都将包括到，往往只使用其中某一些，所以应依据查询树对分解树进行处理。我们称它为以应依据查询树对分解树进行处理。我们称它为分解树化简处理分解树化简处理。图图 分解树结构分解树结构第35页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.1 分解树化简处理过程当全局查询用查询树表示，经过当全局查询用查询树表示，经过C1、C2 准则处理后，查询要用到逻辑关系准则处理后，查询要用到逻辑关系条件在查询树中就表现出来了。接着，能够依据这些条件消去一些与查询无条件在查询树中就表现出来了。接着，能够依据这些条件消去一些与查询无关逻辑关系，即去掉一些操作为空子树。关逻辑关系，即去掉一些操作为空子树。假设在查询树中，存在一棵关于全局关系假设在查询树中，存在一棵关于全局关系R（U，True，T）一元操作）一元操作UnUn-1U1子查询树。令子查询树。令F为为Ul，Un中全部选择操作谓词逻辑合取，即有中全部选择操作谓词逻辑合取，即有 F=。假如没有选择操作，则。假如没有选择操作，则F=True，令，令A为为U1,，Un中全部投影操作中属性中全部投影操作中属性和谓词和谓词Pj中所包括属性并，即有：中所包括属性并，即有：令Qs=Un,U1(R)为关系R上子查询，下面给出分解树化简定义：定定义义4.4：一个关系一个关系Ri（Ui，Qi，Si）对对于子于子查询查询Qs是无用，是无用，当当FQi=False，UiA=；不然是有用。不然是有用。假如假如Ri是是诱导诱导分片所得关系，当其主关系是无用，它分片所得关系，当其主关系是无用，它也是无用也是无用。第36页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.1 分解树化简处理过程例例4.5 设相关系设相关系R0上上子查询子查询Qs=其查询子树如图其查询子树如图4.7（a）所表示，）所表示，R0分解树分解树见图见图3.6，有，有 F=P1P2，A=A1A2A（P1）A（P2）。）。(R0)，假设有假设有FQ1=Flase，AU221=,则则化简后分解树如图化简后分解树如图4.7（b）所表示。）所表示。图4.7 分解树化简第37页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.1 分解树化简处理过程图3.6 独立分片操作后分解树结构第38页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.1 分解树化简处理过程依据上述叙述，可从中归结两个化简分解树时有用准则依据上述叙述，可从中归结两个化简分解树时有用准则C3，C4：n准则准则 C3：在全局查询转换成逻辑查询过程中，能够：在全局查询转换成逻辑查询过程中，能够消去谓词合取含有矛消去谓词合取含有矛盾子树，即可消去选择操作结果为空子查询树盾子树，即可消去选择操作结果为空子查询树。n准则准则C4：在全局关系转换成逻辑关系查询过程中，也能够消去联接操作：在全局关系转换成逻辑关系查询过程中，也能够消去联接操作结果为空子树。结果为空子树。第39页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.2 分解树与查询树合并过程在分解树简化处理后应该与查询树合并。在分解树简化处理后应该与查询树合并。这是两种性质不一样树，但因为这是两种性质不一样树，但因为分解树是由全局关系经过分片操作形成，即一分解树是由全局关系经过分片操作形成，即一组代数操作组代数操作。查询树是对全局关系查询操作，也是一组代数操作查询树是对全局关系查询操作，也是一组代数操作。所以，我们。所以，我们能够用以下算法实现转化。能够用以下算法实现转化。算法算法4.2：简化分解树转化为逻辑查询树简化分解树转化为逻辑查询树。输入：已经化简后分解树。输入：已经化简后分解树。输出：从全局查询转换为逻辑查询树。输出：从全局查询转换为逻辑查询树。方法：从根节点开始：方法：从根节点开始：(1)假如节点上操作假如节点上操作Oj=H或或DH，则将其转换为，则将其转换为U（一元）操作节点；（一元）操作节点；(2)假如节点上操作假如节点上操作Oj=V，则将其转换为联接操作节点，联接属性是，则将其转换为联接操作节点，联接属性是k；(3)假如节点操作假如节点操作Oj=AO，则无须转换；，则无须转换；(4)直至将全部节点处理完成，最终输出（取得）对逻辑片段查询树。直至将全部节点处理完成，最终输出（取得）对逻辑片段查询树。(5)当然，当得到了逻辑片段当然，当得到了逻辑片段(关系关系)查询树后，还应按查询树后，还应按C1、C2准则重复变换，准则重复变换，使得一元操作下移，二元操作操作数尽可能缩减。使得一元操作下移，二元操作操作数尽可能缩减。第40页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.3 一元操作合并过程一元操作合并一元操作合并 在得到逻辑查询树后可能还有一些性质，如在逻辑关系与二元操作之间或在二元操作之上存在若干一元操作。这时，就应按集中式数据库逻辑优化中一些技术，使对同一逻辑关系多个选择、投影，应合并成一个选择操作后接一个投影操作，且尽可能使查询树上相连一元操作最多只有2个。第41页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.4 分布联接化简过程所谓分布联接是指含有两个以上（含两个）全局关系联接（尤其是它们不在同所谓分布联接是指含有两个以上（含两个）全局关系联接（尤其是它们不在同一场地上）。一场地上）。比如：在查询树中，假如有两个全局关系R，S联接时，对R，S全部元组都应进行比较；当这两个全局关系逻辑关系不在同一场地上，就须经通讯形成份布联接。图4.8中，节点表示全局关系逻辑关系（分片后），边表示两节点间联接不为空。图4.8（a）是R，S全联接图，即R全部逻辑关系（R1，Rn）与S全部逻辑关系（s1，Sn）进行完全分布联接。对于DDB来讲，这种联接代价是极大。所以，在设计DDB时，对于有两个联接操作关系（经常表达在实体间关联性质）应尽可能使其划分合理。图4.8 分布联接图第42页分布式数据库 厦门大学计算机科学系 林子雨 8/2/20244.3.2.2.4 分布联接化简过程对于完全联接化简法有两种：对于完全联接化简法有两种：n一个是部分分布联接图如图一个是部