厦门大学计算机科学系11月

《厦门大学计算机科学系11月》由会员分享，可在线阅读，更多相关《厦门大学计算机科学系11月（69页珍藏版）》请在金锄头文库上搜索。

1、分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024厦门大学计算机科学系2011年11月Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024专题三 分布式查询处理第第4章章 分布式查询处理分布式查询处理4.1 4.1 4.1 4.1 分布式查询特点分布式查询特点分布式查询特点分布式查询特点4.2 4.2 4.2 4.2 全局查询转换的基础知识全局查询转换的基础知识全局查询转换的基础知识全局查询转换的基础知识4.3

2、 4.3 4.3 4.3 全局查询到逻辑查询的转换全局查询到逻辑查询的转换全局查询到逻辑查询的转换全局查询到逻辑查询的转换4.4 4.4 4.4 4.4 逻辑查询到物理查询的转换逻辑查询到物理查询的转换逻辑查询到物理查询的转换逻辑查询到物理查询的转换4.5 4.5 4.5 4.5 联接操作联接操作联接操作联接操作分布式数据库 厦门大学计算机科学系 林子雨 7/26/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、特点分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义4.1.1.1 4.1.1.1 集中式数据库查询的基本原理集中式数据库查询的基本原理集中式数据库查询的基本原理集中式数据库查询的基本原理 在集中式数据库环境中的查询处理，是将用户查询（由查询语言在集中式数据库环境中的查询处理，是将用户查询（由查询语言表达）转换成物理查询处理，其中包括了物理优化和逻辑优化两个层表达）转换成物理查询处理，其中包括了物理优化和逻辑优化两个层次。次。 物理优化物理优化：对关系（数据库）的基本操作符的运算在实现中的优：对关系（数据库）的基本操作符的运算在实现中的优化（化（

4、如索引、排序、聚集（聚簇）等）如索引、排序、聚集（聚簇）等） 逻辑优化逻辑优化：在进行物理优化前先应有一个合理的（最优的）操作：在进行物理优化前先应有一个合理的（最优的）操作符次序或一些操作策略的选择符次序或一些操作策略的选择 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义4.1.1.2 4.1.1.2 分布式查询处理分布式查询处理 分布式数据库环境是由虚拟的全局数据库和实际存在的各局分布式数据库环境是由虚拟的全局数据库和实际存在的各局部数据库组成的。部数据库组成的。DDB的分布性，使虚拟的全局数据库在抽象时的分布性，使虚拟的全局数据库在抽象时

5、还有逻辑数据库（还有逻辑数据库（LgDB)和物理数据库（和物理数据库（PDB）的概念；）的概念； DDB的四层模式结构的四层模式结构中的局部概念层是由物理数据库映射到中的局部概念层是由物理数据库映射到局部场地上的，即形成局部数据库；局部场地上的，即形成局部数据库； 分布式查询处理包含了全局查询处理和局部查询处理两个部分布式查询处理包含了全局查询处理和局部查询处理两个部分。但是，对使用分。但是，对使用 DDB 来说，用户（应用）只看到来说，用户（应用）只看到 GDB，且也，且也只在全局关系上执行查询。而用户的这种查询是通过查询语言表只在全局关系上执行查询。而用户的这种查询是通过查询语言表示，并由

6、系统将其转换。因而在查询执行过程中，实际上最终要示，并由系统将其转换。因而在查询执行过程中，实际上最终要涉及到具体场地上的物理关系的查询。涉及到具体场地上的物理关系的查询。 因此，分布式查询对应全局层三种数据库有三种查询：因此，分布式查询对应全局层三种数据库有三种查询：用户用户查询、逻辑查询和物理查询查询、逻辑查询和物理查询。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义集集中中式式三三层层摸摸式式结结构构图图分分布布式式四四层层摸摸式式结结构构图图分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义

7、4.1.1.2 4.1.1.2 分布式查询处理分布式查询处理 用户查询（用户查询（用户查询（用户查询（QQu u）：）：）：）： 是是是是DDBDDB中在全局数据库（中在全局数据库（中在全局数据库（中在全局数据库（GDBGDB）上的查询；）上的查询；）上的查询；）上的查询； 逻辑查询（逻辑查询（逻辑查询（逻辑查询（QQL L）：）：）：）： 是是是是DDBDDB中在逻辑数据库（中在逻辑数据库（中在逻辑数据库（中在逻辑数据库（LgDBLgDB）上的查询；）上的查询；）上的查询；）上的查询； 物理查询（物理查询（物理查询（物理查询（QQp p）：）：）：）： 是是是是DDBDDB中在物理数据库（中

8、在物理数据库（中在物理数据库（中在物理数据库（PDBPDB）上的查询。）上的查询。）上的查询。）上的查询。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义4.1.1.3 4.1.1.3 三种查询之间的联系三种查询之间的联系 上述三种查询之间有一定的联系，这种联系依赖于上述三种查询之间有一定的联系，这种联系依赖于上述三种查询之间有一定的联系，这种联系依赖于上述三种查询之间有一定的联系，这种联系依赖于DDBDDB的分片模式定的分片模式定的分片模式定的分片模式定义和分配模式定义，我们可用以下定理来描述：义和分配模式定义，我们可用以下定理来描述：义和分

9、配模式定义，我们可用以下定理来描述：义和分配模式定义，我们可用以下定理来描述： 定理定理定理定理 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

10、-1 (LgDB)=FS-1AS-1 (PDB)， 因而，有因而，有Qu(GDB)= Qu(FS-1AS-1 (PDB)= Qu.FS-1AS-1 (PDB) 。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义4.1.1.4 4.1.1.4 4.1.1.4 4.1.1.4 分布式查询定义分布式查询定义分布式查询定义分布式查询定义 定理定理定理定理4.14.1讨论的是全局层的查询处理，其中对用户查询，讨论的是全局层的查询处理，其中对用户查询，讨论的是全局层的查询处理，其中对用户查询，讨论的是全局层的查询处理，其中对用户查询，在系统中实际存在了两次转

11、换：在系统中实际存在了两次转换：在系统中实际存在了两次转换：在系统中实际存在了两次转换：全局查询到逻辑查询的转换全局查询到逻辑查询的转换全局查询到逻辑查询的转换全局查询到逻辑查询的转换和和和和逻辑查询到物理查询的转换逻辑查询到物理查询的转换逻辑查询到物理查询的转换逻辑查询到物理查询的转换。如下图所示：。如下图所示：。如下图所示：。如下图所示： FS AS GDB LgDB PDB 转换转换1 转换转换2 Qu QL Qp分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.1 分布式查询处理的定义 定义定义4.1 ：分布式数据库系统的查询处理分布式数据库系统的查询处理Q是一算

12、法：算法的输入是用户是一算法：算法的输入是用户查询查询Qu，算法的输出是相应的物理查询，算法的输出是相应的物理查询Qp; 算法的功能是将用户查询按算法的功能是将用户查询按照每个全局关系的分布结构转换成一个最优的物理查询。照每个全局关系的分布结构转换成一个最优的物理查询。 DDBDDB查询优化主要讨论以下问题：查询优化主要讨论以下问题：全局查询处理的转换、优化全局查询处理的转换、优化由于分布性引起的数据在场地间移动时的数据副本选择和查询操由于分布性引起的数据在场地间移动时的数据副本选择和查询操作序的确定等策略作序的确定等策略 对于物理查询的具体执行，就相当于在一个集中式数据库上对于物理查询的具体

13、执行，就相当于在一个集中式数据库上的操作（即对局部数据库的操作），其上的查询处理属于局部查的操作（即对局部数据库的操作），其上的查询处理属于局部查询处理。集中式数据库所讨论的查询处理及优化策略是本专题的询处理。集中式数据库所讨论的查询处理及优化策略是本专题的技术基础。技术基础。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.1.2 分布式查询的代价因素综述 分布式查询的代价因素如下：分布式查询的代价因素如下： IO代价（即估算输入代价（即估算输入/输出操作次数）输出操作次数）CPU的使用情况的使用情况传输代价（包括数据量的传输费用、传输的延迟时间，以及涉及传输代价（包括数

14、据量的传输费用、传输的延迟时间，以及涉及传输数据的控制信息及控制次数）传输数据的控制信息及控制次数）分布事务处理的管理策略（事务可串行化、分布式并发控制、分分布事务处理的管理策略（事务可串行化、分布式并发控制、分布式恢复）布式恢复）分布查询操作方法（如联接操作、分布查询操作方法（如联接操作、并操作、二元操作以及全局查并操作、二元操作以及全局查询和局部查询的不同操作）对效率的影响询和局部查询的不同操作）对效率的影响分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2 全局查询转换的基础知识4.2.1 4.2.1 4.2.1 4.2.1 查询表达式的等价性查询表达式的等价性查询表

15、达式的等价性查询表达式的等价性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 扩充的关系代数规则扩充的关系代数规则扩充的关系代数规则扩充的关系代数规则分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.1

16、 查询表达式的等价性关系数据模型有三种查询语言：关系数据模型有三种查询语言：代数语言、元组演算语言、域演代数语言、元组演算语言、域演算语言算语言，这三种语言是等价的，这三种语言是等价的用代数语言表达查询处理最为方便用代数语言表达查询处理最为方便SQL 语言是关系数据库的标准语言，它是完备的，对用户而言，语言是关系数据库的标准语言，它是完备的，对用户而言，提供非过程的查询语言最为方便提供非过程的查询语言最为方便这里假设这里假设 DDBMS 提供完全透明提供完全透明, , 全局用户可以用全局用户可以用SQL语言操语言操纵语句来纵语句来表达全局查询，表达全局查询，SQL语句是对语句是对DDB进行查询

17、的外部表达进行查询的外部表达式式分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.1 查询表达式的等价性查询要得到结果，必须对关系进行具体操作：查询要得到结果，必须对关系进行具体操作：pp 五种基本操作五种基本操作五种基本操作五种基本操作 并（并（）、差（）、差（）、迪卡尔积（）、迪卡尔积（）、选择（）、选择（ ）、投影（）、投影（ ）pp 五种导出操作五种导出操作五种导出操作五种导出操作 交（交（）、商（）、商（）、联接（）、联接（ ）、自然联接（）、自然联接（）、半联接（）、半联接（） ijij为了便于查询处理的转换，将上面的十种关系操作数分为两类：为了便于查询处理的

18、转换，将上面的十种关系操作数分为两类：p一元操作，用一元操作，用U表示表示p二元操作，用二元操作，用B表示表示 属于一元操作的只有属于一元操作的只有和和，而其余的操作都是二元操作，而其余的操作都是二元操作 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.1 查询表达式的等价性 例例 ：对全局关系对全局关系 Emp,有如下有如下SQL查询表达式查询表达式 Select ENAME,DNO From Emp Where DNO=15; （4-14-1） 其相应的代数操作表达式为：其相应的代数操作表达式为： ENAMEENAME，DNODNO（DNO=DNO=1515 Emp

19、Emp） （4-24-2） 或或 DNODNO= =1515（ENAMEENAME，DNO DNO EmpEmp） （4-34-3）本例本例表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。 定义定义定义定义4.24.24.24.2：两个查询表达式两个查询表达式 E1 和和 E2 是等价的，如果其是等价的，如果其 查询的结果是相同的，记为查询的结果是相同的，记为 E1 E2。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.2 查询树 定义定义4.34.3： 查询树是一棵树查询树是一棵树 T=(V,E)，其

20、中：，其中： 1）V是节点集，每个非叶结点是关系操作符，叶节点是关系名是节点集，每个非叶结点是关系操作符，叶节点是关系名（即查询涉及的关系）；（即查询涉及的关系）； 2）E是边集，二节点有边（是边集，二节点有边（V1,V2），当且仅当），当且仅当 V2 是是 V1 的操作的操作分量。分量。通常，人们用查询树表示查询表达式的内部结构。通常，人们用查询树表示查询表达式的内部结构。分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024例例4.1：有有查查询询Q1：查查询询北北部部地地区区（AREA=North）所所属属部部门门发发出出订订单单的的供供应应商商号号。这这里里涉涉及及两两个个全

21、全局局关关系系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是非叶节点是

22、非叶节点 的分量。的分量。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.2 查询树例子：多表连接操作例子：多表连接操作StudentIDStudentNameStudentAge1张三252李四263王五274赵六285无名氏27表表Student，存放学生基本信息，存放学生基本信息 BorrowBookIDBorrowBookNameStudentIDBorrowBookPublish1马克思主义政治经济学1电子工业出版社2毛泽东思想概论2高等教育出版社3邓小平理论3人民邮电出版社4大学生思想道德修养4中国铁道出版社5C语言程序设计5高等教育出版社表表BorrowB

23、ook，存放学生所借的书，存放学生所借的书 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.2 查询树例子：多表连接操作例子：多表连接操作Select Student.StudentName,Student.StudentAge,BorrowBook.BorrowBookName,BorrowBook.BorrowBookPublishFROM Student,BorrowBookWHERE Student.StudentID = BorrowBook.StudentID 运行的结果如下： StudentNameStudentAgeBorrowBookNameBorro

24、wBookPublish张三25马克思主义政治经济学电子工业出版社李四26毛泽东思想概论高等教育出版社王五27邓小平理论人民邮电出版社赵六28大学生思想道德修养中国铁道出版社分布式数据库 厦门大学计算机科学系 林子雨 7/26/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 查询树查询树可以理解为全局查查询树可以理解为全局查询树，其叶节点是全局关询树，其叶节点是全局关系。系。根据等价定义，可用三种根据等价定义，可用三种方式描述查询：方

25、式描述查询：SQL表达式（查询语句）表达式（查询语句） 代数表达式代数表达式 查询树查询树注意注意:查询树不同于查询树不同于分解树分解树分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.2 查询树图 分解树分布式数据库 厦门大学计算机科学系 林子雨 7/26/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（） 其中，关系其中，关

26、系R R与空关系进行操作（联接）表示了一种空操作，在查与空关系进行操作（联接）表示了一种空操作，在查 询转换过程中是可以消去的操作（某种程度的优化）询转换过程中是可以消去的操作（某种程度的优化）例例4.2：（）：（）（） 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.3 等价变换规则（2）多个关系模式的操作的变换规则）多个关系模式的操作的变换规则 设有多个关系，其关系模式分别为设有多个关系，其关系模式分别为R， S S，T T，在一定条，在一定条件下有如下规则：件下有如下规则： 一元操作交换律：一元操作交换律： U U1 1（ U U2 2（R) UR) U2 2（

27、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

28、) U(R)B(S) 利用等价变换规则可以改变操作序实现查询优化利用等价变换规则可以改变操作序实现查询优化分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.4 限定关系的简化表示逻辑关系（逻辑片段）是对全局关系进行逻辑关系（逻辑片段）是对全局关系进行、的的操作得操作得到的到的从对关系的操作而言，逻辑关系是带有从对关系的操作而言，逻辑关系是带有一定限定条件一定限定条件的关系，的关系，我们可称它为我们可称它为限定关系限定关系限定关系限定关系，它的限定条件是谓词或属性集，它的限定条件是谓词或属性集定理定理 4.1 指出用户查询必有相应的对逻辑关系和物理关系的查指出用户查询必有相

29、应的对逻辑关系和物理关系的查询，询，其中对逻辑关系的查询就是对这种限定关系的操作，也就其中对逻辑关系的查询就是对这种限定关系的操作，也就是说，对关系的操作可以进一步地再作用到限定关系上是说，对关系的操作可以进一步地再作用到限定关系上给出给出限定关系的简化表示为限定关系的简化表示为R:QR:Q，其中：，其中：R是全局关系；是全局关系；Q是是限定关系即逻辑关系应满足的谓词。限定关系即逻辑关系应满足的谓词。R:QR:Q读作读作“全局关系全局关系R对对应于限定条件应于限定条件Q的逻辑关系（即限定关系）的逻辑关系（即限定关系）”限定关系限定关系 R:QR:Q被作为一个操作数，因此，它可以被关系代数被作为

30、一个操作数，因此，它可以被关系代数所操作，这是一种扩充的操作所操作，这是一种扩充的操作分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.5 谓词合取性什么叫谓词合取性什么叫谓词合取性 假设有假设有全局关系模式全局关系模式 R，F 是一谓词，是一谓词，Q 是关系所满足的限定条是关系所满足的限定条件，也是一谓词；在关系运算中由件，也是一谓词；在关系运算中由 Q 与与 F 共同组成谓词，即称具共同组成谓词，即称具有谓词合取性质。例如有谓词合取性质。例如 QR F 、QR QS F 等。等。这种合取性本身可能引起一些矛盾：这种合取性本身可能引起一些矛盾： 如如例例3.1中中，Su

31、pplier划划分分为为两两个个逻逻辑辑关关系系就就有有两两个个限限定定关关系系，其其中中Q1：CITY=London，Q2：CITY=Paris，就可能有表达式：，就可能有表达式： CITY=Paris S1：CITY=London= 即，当限定关系的谓词合取是具有矛盾的限定条件，实际上将是即，当限定关系的谓词合取是具有矛盾的限定条件，实际上将是一种空操作。一种空操作。 这种这种谓词合取可能为空的性质谓词合取可能为空的性质对查询转换（执行）时很有用，我对查询转换（执行）时很有用，我们可以根据逻辑片段所具有的内涵性质，对其操作可能遗留下一们可以根据逻辑片段所具有的内涵性质，对其操作可能遗留下一

32、些有矛盾的表达式为空的情况以些有矛盾的表达式为空的情况以简化查询简化查询的执行。的执行。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.6 扩充的关系代数规则对对R Q 的操作是关系代数操作的一种扩充，其中使用限定的操作是关系代数操作的一种扩充，其中使用限定关系作为操作数。关系作为操作数。将关系代数操作作用到限定关系上有将关系代数操作作用到限定关系上有如下八如下八条扩充规则条扩充规则 可可以以根根据据八八个个对对限限定定关关系系的的操操作作规规则则，讨讨论论扩扩充充的的关关系系代代数数表表达式转换的等价性达式转换的等价性 两两个个限限定定关关系系是是等等价价的的，即即当

33、当它它们们的的两两个个基基础础关关系系是是等等价价的的，且且其其限限定定条条件件都都表表示示了了相相同同的的真真值值函函数数（即即当当对对同同一一元元组组用用两两个限定条件时，能得到相同的真值）个限定条件时，能得到相同的真值）用于限定关系的命题：用于限定关系的命题： 命命题题4.l4.l： 所所有有关关系系代代数数具具有有的的等等价价转转换换同同样样适适用用于于限限定定关关系。系。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024直直观地地说，对一个全局关系一个全局关系进行行选择操作（操作（谓词为QR）得到的）得到的逻辑关系再关系再做做选择操作（操作（谓词为F），相当于），相当

34、于对全局关系做了一次全局关系做了一次选择操作，但其操作，但其谓词为F AND QR，即，即谓词的合取性的合取性; 4.2.6 扩充的关系代数规则RQRQR R RFQRFQR R 规则（规则（1）规则（规则（2）对限定关系投影出某些属性（限定关系投影出某些属性（A），即使），即使计算算谓词条件的属性不在条件的属性不在A中，所得到的限定关系的中，所得到的限定关系的谓词不会改不会改变，仍是，仍是QR。A ARQRQR R AR QR分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.2.6 扩充的关系代数规则RQRQR RSQSQS S（R R）（S S）QQR RQQS S 同样

35、有谓词合取性。同样有谓词合取性。规则（规则（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)

36、(S):QRQSF 规则（规则（8）FF分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3 全局查询到逻辑查询的转换讨论讨论“查询转换查询转换”，是讨论分布式数据库查询处理的，是讨论分布式数据库查询处理的优化。即在转换过程中，利用等价变换规则，综合并优化。即在转换过程中，利用等价变换规则，综合并充分地考虑分布查询的代价因素，使分布查询处理逐充分地考虑分布查询的代价因素，使分布查询处理逐步实现优化。步实现优化。4.3.1 全局查询到逻辑查询的转换步骤全局查询到逻辑查询的转换步骤4.3.2 等价转换准则等价转换准则4.3.2.1 全局查询转换成查询树全局查询转换成查询树4.3.

37、2.2 生成优化的逻辑查询树生成优化的逻辑查询树分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.1 全局查询到逻辑查询的转换步骤原则上可以按两步实现分布式查询的第一次转换（全局查询到逻辑查询），每一原则上可以按两步实现分布式查询的第一次转换（全局查询到逻辑查询），每一步可遵守一些转换规则，以实现部分优化：步可遵守一些转换规则，以实现部分优化：第一步：第一步：n将全局查询表达式（将全局查询表达式（SQL语法和代数操作表达式）转换成语法和代数操作表达式）转换成全局全局查询内部结查询内部结构形式构形式（查询树）（查询树）n在其转换过程中需要在其转换过程中需要利用等价变换规则利

38、用等价变换规则及其所归纳出来的及其所归纳出来的两个转换准则两个转换准则（C1，C2）第二步：第二步：n将全局查询树与模式分解树合并转换成部分优化的将全局查询树与模式分解树合并转换成部分优化的逻辑关系查询树逻辑关系查询树，或称，或称分解树的化简操作。其中包括：将全局查询树叶节点按分片模式定义的逻辑分解树的化简操作。其中包括：将全局查询树叶节点按分片模式定义的逻辑关系名，取代全局关系名（查询树与分解树合并），并分别运用变换规则，关系名，取代全局关系名（查询树与分解树合并），并分别运用变换规则，化简成部分优化的逻辑查询树。化简成部分优化的逻辑查询树。n其实现过程中，除了应用转换准则其实现过程中，除了

39、应用转换准则C1，C2以外，以外，还有还有C3C6准则准则。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.1 全局查询转换成查询树例例4.4：对例：对例4.1的查询树的查询树(a)，利用代数操作等价变换规则可有如图，利用代数操作等价变换规则可有如图4.4所示。所示。 图4.4 全局查询树转换范例分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.1 全局查询转换成查询树分析分析：图图4.4（a）是下列代数表达式的查询树：）是下列代数表达式的查询树： S#AREA=North（Sp Dept） D=D 图4.4（b）是利用）是利用一元操作一

40、元操作对二元操作的分配律二元操作的分配律规则：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分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024准则准则C1

41、：缩减二元操作数关系，利用一元操作对二元操作的分配律，将：缩减二元操作数关系，利用一元操作对二元操作的分配律，将一元操作向下移动。一元操作向下移动。U(R)B(S) (U(R)B(U(S)准则准则C2：用一元操作幂等律对操作数关系产生适当的一元操作或分解成：用一元操作幂等律对操作数关系产生适当的一元操作或分解成多个一元操作，以缩减操作数关系。多个一元操作，以缩减操作数关系。U(R)U1U2 (R)4.3.2.1 全局查询转换成查询树结论：结论：查询树相当于对一个集中式数据库的查询，集中式数据库的逻辑优化技术可以查询树相当于对一个集中式数据库的查询，集中式数据库的逻辑优化技术可以作用于其上。具体

42、说是要：作用于其上。具体说是要：对全局查询树中的一元操作尽量下移到叶节点；对全局查询树中的一元操作尽量下移到叶节点；如果查询树中有二元操作，则应尽量先缩减二元操作的操作数。由此，可获如果查询树中有二元操作，则应尽量先缩减二元操作的操作数。由此，可获得等价转换准则得等价转换准则C1和和C2。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2 生成优化的逻辑查询树生成优化的逻辑查询树，就是把查询树与全局模式的分解树生成优化的逻辑查询树，就是把查询树与全局模式的分解树一起来考虑，需要用到限定关系等价变换性质。这一步的操一起来考虑，需要用到限定关系等价变换性质。这一步的操

43、作比较复杂，基本上分为以下几个子过程：作比较复杂，基本上分为以下几个子过程：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 一个实例一个实例分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.1 分解树的化简处理过程分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合 。要将全局查询转换成逻辑查询，需

44、要对分解树进行处理。对于一个全局查询而要将全局查询转换成逻辑查询，需要对分解树进行处理。对于一个全局查询而言，并非构成全局关系的所有逻辑关系都将涉及到，往往只使用其中某一些，言，并非构成全局关系的所有逻辑关系都将涉及到，往往只使用其中某一些，所以应根据查询树对分解树进行处理。我们称它为所以应根据查询树对分解树进行处理。我们称它为分解树的化简处理分解树的化简处理。 图图 分解树结构分解树结构分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.1 分解树的化简处理过程当全局查询用查询树表示，经过当全局查询用查询树表示，经过C1、C2 准则处理后，查询要用到的逻辑关准则处

45、理后，查询要用到的逻辑关系的条件在查询树中就表现出来了。接着，可以根据这些条件消去一些与查系的条件在查询树中就表现出来了。接着，可以根据这些条件消去一些与查询无关的逻辑关系，即去掉一些操作为空的子树。询无关的逻辑关系，即去掉一些操作为空的子树。 假设在查询树中，存在一棵关于全局关系假设在查询树中，存在一棵关于全局关系R（U，True，T）的一元操作）的一元操作UnUn-1U1的子查询树。令的子查询树。令F为为Ul，Un中所有选择操作谓词的逻辑合取，中所有选择操作谓词的逻辑合取，即有即有 F= 。如果没有选择操作，则。如果没有选择操作，则F=True，令，令A为为U1,，Un中所有投影操作中的属

46、性和谓词中所有投影操作中的属性和谓词Pj中所涉及的属性的并，即有：中所涉及的属性的并，即有： 令Qs=Un,U1(R)为关系R上的子查询，下面给出分解树化简的定义：定定义4.4：一个关系一个关系Ri（Ui，Qi，Si）对于子于子查询Qs是无用的，是无用的，当当FQi=False，UiA=；否否则是有用的。是有用的。如果如果Ri是是诱导分片所得的关系，当其主关系是无用分片所得的关系，当其主关系是无用的，它也是无用的的，它也是无用的。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.1 分解树的化简处理过程例例4.5 设有关系设有关系R0上的上的子查询子查询Qs=

47、其查询子树如图其查询子树如图4.7（a）所示，）所示，R0的分解树的分解树见图见图3.6，有，有 F=P1P2，A=A1A2A（P1）A（P2）。）。 (R0)，假设有假设有FQ1=Flase，AU221=,则则化简后的分解树如图化简后的分解树如图4.7（b）所示。）所示。 图4.7 分解树化简分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.1 分解树的化简处理过程图3.6 独立分片操作后的分解树结构分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.1 分解树的化简处理过程根据上述论述，可从中归结两个化简分解树时有用的准则根据上述论

48、述，可从中归结两个化简分解树时有用的准则C3，C4：n准则准则 C3：在全局查询转换成逻辑查询的过程中，可以：在全局查询转换成逻辑查询的过程中，可以消去谓词合取具有消去谓词合取具有矛盾的子树，即可消去选择操作结果为空的子查询树矛盾的子树，即可消去选择操作结果为空的子查询树。n准则准则C4：在全局关系转换成逻辑关系查询过程中，也可以消去联接操作：在全局关系转换成逻辑关系查询过程中，也可以消去联接操作结果为空的子树。结果为空的子树。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.2 分解树与查询树的合并过程在分解树简化处理后应该与查询树合并。在分解树简化处理后应该

49、与查询树合并。这是两种性质不同的树，但由于这是两种性质不同的树，但由于分解树是由全局关系经过分片操作形成的，即分解树是由全局关系经过分片操作形成的，即一组代数操作一组代数操作。查询树是对全局关系的查询操作，也是一组代数操作查询树是对全局关系的查询操作，也是一组代数操作。所以，。所以，我们可以用以下算法实现转化。我们可以用以下算法实现转化。算法算法4.2：简化的分解树转化为逻辑查询树简化的分解树转化为逻辑查询树。 输入：已经化简后的分解树。输入：已经化简后的分解树。 输出：从全局查询转换为逻辑查询树。输出：从全局查询转换为逻辑查询树。方法：从根节点开始：方法：从根节点开始：(1) 如果节点上操作

50、如果节点上操作Oj=H或或DH，则将其转换为，则将其转换为U（一元）操作节点；（一元）操作节点； (2) 如果节点上的操作如果节点上的操作Oj=V，则将其转换为联接操作节点，联接属性是，则将其转换为联接操作节点，联接属性是k；(3) 如果节点操作如果节点操作Oj=AO，则不必转换；，则不必转换；(4) 直至将所有节点处理完毕，最后输出（获得）对逻辑片段的查询树。直至将所有节点处理完毕，最后输出（获得）对逻辑片段的查询树。(5) 当然，当得到了逻辑片段当然，当得到了逻辑片段(关系关系)的查询树后，还应按的查询树后，还应按C1、C2准则反复变准则反复变换，使得一元操作下移，二元操作的操作数尽量缩减

51、。换，使得一元操作下移，二元操作的操作数尽量缩减。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.3 一元操作的合并过程一元操作的合并一元操作的合并 在得到逻辑查询树后可能还有一些性质，如在逻辑关系与二元操作之间或在二元操作之上存在若干一元操作。这时，就应按集中式数据库逻辑优化中的某些技术，使对同一逻辑关系的多个选择、投影，应合并成一个选择操作后接一个投影操作，且尽量使查询树上相连的一元操作最多只有2个。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.4 分布联接的化简过程所谓分布联接是指具有两个以上（含两个）全局关系的联接（特

52、别是它们不在所谓分布联接是指具有两个以上（含两个）全局关系的联接（特别是它们不在同一场地上）。同一场地上）。例如：在查询树中，如果有两个全局关系R，S联接时，对R，S的所有元组都应进行比较；当这两个全局关系的逻辑关系不在同一场地上，就须经通讯形成分布联接。图4.8中，节点表示全局关系的逻辑关系（分片后），边表示两节点间联接不为空。 图4.8（a）是R，S的全联接图，即R的所有逻辑关系（R1，Rn）与S的所有逻辑关系（s1，Sn）进行完全分布联接。对于DDB来讲，这种联接的代价是极大的。所以，在设计DDB时，对于有两个联接操作的关系（常常体现在实体间的关联性质）应尽量使其划分合理。 图4.8 分

53、布联接图分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.4 分布联接的化简过程对于完全联接的化简法有两种：对于完全联接的化简法有两种：n一种是部分分布联接图如图一种是部分分布联接图如图4.8（b），），其中部分节点间没有联通，使其中部分节点间没有联通，使完全联接图形成两个或两个以上子图。完全联接图形成两个或两个以上子图。n另一种是简化为简单分布联接图如图另一种是简化为简单分布联接图如图4.8（C），每对节点间只有一条），每对节点间只有一条边。边。 图4.8 分布联接图分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.4 分布联接的化

54、简过程 DDB中分片操作支持的诱导操作实际上是这种简单分布联接，R与S的逻辑关系只存在一对一的联接，这就可以先做局部联接，再完成分布联接，其通讯开销一定会降低。所谓先做局部联接，就是先在逻辑关系之间完成联接，然后再合并。 例4.6 设有图4.9（a）所示的查询树，S1，S2是按R1，R2诱导分片操作所得到的逻辑关系，该查询树可以依等价变换规则转换成图4.9（b）所示。图4.9（c）表示简单分布联接的查询树。 图4.9 简单分布联接分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024内容回顾（3.2.2.4 诱导分片）分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244

55、.3.2.2.4 分布联接的化简过程从例从例4.6我们可以看到：对于图我们可以看到：对于图4.9（c）的查询树表示了先做联接操作再做）的查询树表示了先做联接操作再做并操作，有利于进一步优化查询树，其中使用了一些等价变化规则。所以可归并操作，有利于进一步优化查询树，其中使用了一些等价变化规则。所以可归纳出分布联接的转换准则纳出分布联接的转换准则C5。准则准则C5：在全局查询中具有分布联接时，可将联接下属的并操作上推。：在全局查询中具有分布联接时，可将联接下属的并操作上推。 附：附： 二元操作结合律：二元操作结合律： (R)B(S)B(T) (R)B(S)B(T) 二元操作交换律：二元操作交换律：

56、 (R)B(S) (S)B(R)分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.5 一个实例例子例子：至此，我们可以将：至此，我们可以将例例4.4的全局查询转换再根据上述准则进行优化。的全局查询转换再根据上述准则进行优化。假设全局关系假设全局关系Dept按部门号水平分片，其谓词为：按部门号水平分片，其谓词为： Q1：D110 Q2：D1120 Q3：D2130且且D=110在在“North”地区。同时有约定；地区。同时有约定；North地区的零件由地区的零件由London供应者供应。图供应者供应。图4.10是利用上列准则对图是利用上列准则对图 4.4的进一步转换

57、。的进一步转换。 图4.4 全局查询树转换范例分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.3.2.2.5 一个实例图4.10是例4.l的全局查询到逻辑查询的最后查询树，其中经过了从C1C5准则。 准则准则C1：缩减二元操作数关系，：缩减二元操作数关系，利用一元操作对二元操作的分配利用一元操作对二元操作的分配律，将一元操作向下移动。律，将一元操作向下移动。准则准则C2：用一元操作幂等律对操：用一元操作幂等律对操作数关系产生适当的一元操作或作数关系产生适当的一元操作或分解成多个一元操作，以缩减操分解成多个一元操作，以缩减操作数关系。作数关系。准则准则 C3：在全局查询转换成

58、逻辑：在全局查询转换成逻辑查询的过程中，可以查询的过程中，可以消去谓词合消去谓词合取具有矛盾的子树，即可消去选取具有矛盾的子树，即可消去选择操作结果为空的子查询树择操作结果为空的子查询树。准则准则C4：在全局关系转换成逻辑：在全局关系转换成逻辑关系查询过程中，也可以消去联关系查询过程中，也可以消去联接操作结果为空的子树。接操作结果为空的子树。准则准则C5：在全局查询中具有分布：在全局查询中具有分布联接时，可将联接下属的并操作联接时，可将联接下属的并操作上推。上推。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4 逻辑查询到物理查询的转换 逻辑转换是把注意力集中于如何将一元

59、操作尽量合并，先选择后投影提逻辑转换是把注意力集中于如何将一元操作尽量合并，先选择后投影提取公共因子、消去无用子表达式（子树）、减少二元操作数等方面，最后获得取公共因子、消去无用子表达式（子树）、减少二元操作数等方面，最后获得简化了的查询树和操作表达式。简化了的查询树和操作表达式。 那么，物理查询转换的内容是什么呢？转换的策略是什么呢？转换的方那么，物理查询转换的内容是什么呢？转换的策略是什么呢？转换的方法是什么呢？法是什么呢？本节讨论以下内容：本节讨论以下内容：4.4.1 物理转换中的基本内容和方法物理转换中的基本内容和方法4.4.2 物理转换的策略与方法分析物理转换的策略与方法分析分布式数

60、据库 厦门大学计算机科学系 林子雨 7/26/20244.4.1 物理转换中的基本内容和方法一、什么是物理查询转换？一、什么是物理查询转换？ 所谓从逻辑查询到物理查询转换，是指将逻辑查询转换得到的简化了的查询所谓从逻辑查询到物理查询转换，是指将逻辑查询转换得到的简化了的查询树，转换成具体的每个场地上的局部操作命令和数据传输命令的过程。树，转换成具体的每个场地上的局部操作命令和数据传输命令的过程。n也就是说，全局查询须两次转换后才形成一个具体的分布执行计划也就是说，全局查询须两次转换后才形成一个具体的分布执行计划（DEP），然后才是交付给各个局部场地去执行。），然后才是交付给各个局部场地去执行

61、。n在实际执行过程中也同样存在查询处理的优化，这就是前面提到过的分布在实际执行过程中也同样存在查询处理的优化，这就是前面提到过的分布式查询处理中的局部层优化。式查询处理中的局部层优化。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.1 物理转换中的基本内容和方法二、物理转换的基本内容和策略综述二、物理转换的基本内容和策略综述 物理查询转换的过程，将涉及到物理副本和查询的处理场地，即执行物理查询转换的过程，将涉及到物理副本和查询的处理场地，即执行环境。特别对于二元操作数不在同一场地时或者有多个副本可选择的环境。特别对于二元操作数不在同一场地时或者有多个副本可选择的情况时

62、，其情况时，其“执行环境执行环境”的概念更为重要。所以，物理转换时一般注的概念更为重要。所以，物理转换时一般注意以下因素：意以下因素：n操作副本选择操作副本选择n操作执行次序的选择操作执行次序的选择n操作方法的选择操作方法的选择n通讯代价通讯代价n评估数据量评估数据量分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2 物理转换的策略与方法分析4.4.2.1 选择操作副本的原则和策略选择操作副本的原则和策略4.4.2.2 操作执行次序的选择操作执行次序的选择4.4.2.3 操作方法的选择操作方法的选择4.4.2.4 通讯代价的计算通讯代价的计算4.4.2.5 操作场地选择

63、操作场地选择 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2.1 选择操作副本的原则和策略n操作副本的选择操作副本的选择是选定逻辑关系相对应的物理关系有多个副本时的具体化。是选定逻辑关系相对应的物理关系有多个副本时的具体化。原则上，对不同查询有不同的具体选择。各个物理关系的副本其使用情况、路原则上，对不同查询有不同的具体选择。各个物理关系的副本其使用情况、路径代价和使用要求不完全一样，若按随机选定显然不合理，应该遵守一定的协径代价和使用要求不完全一样，若按随机选定显然不合理，应该遵守一定的协定，选择一个理想的（合理的）副本。定，选择一个理想的（合理的）副本。n副本的

64、使用状态副本的使用状态可分为可用和不可用。不可用指的是可能副本所在场地出现可分为可用和不可用。不可用指的是可能副本所在场地出现故障或到该场地的通讯有了故障；可用则又可能处于繁忙或轻松状态，这主要故障或到该场地的通讯有了故障；可用则又可能处于繁忙或轻松状态，这主要是指对副本可用时等候查询的多少。是指对副本可用时等候查询的多少。 为此，可以给出副本选择的一般原则：为此，可以给出副本选择的一般原则：n 本场地物理关系优先。如果查询始发场地上有逻辑关系的一个相应的物本场地物理关系优先。如果查询始发场地上有逻辑关系的一个相应的物理关系，就应尽量的选择该物理关系理关系，就应尽量的选择该物理关系n同场地上有

65、二元操作，则应尽量选择同一场地上的相应物理关系完成二元同场地上有二元操作，则应尽量选择同一场地上的相应物理关系完成二元操作，以减少数据传送操作，以减少数据传送n在查询等候中数据最小的物理关系应被优先选中在查询等候中数据最小的物理关系应被优先选中n代价最小的应优先选中代价最小的应优先选中分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2.2 操作执行次序的选择n在全局查询到逻辑查询转换时产生的在全局查询到逻辑查询转换时产生的查询树已经部分地蕴含了部分操作次序，查询树已经部分地蕴含了部分操作次序，如执行时从叶到根向上执行。然而，这并没有全部地给出最好的执行次序。如执行时从叶

66、到根向上执行。然而，这并没有全部地给出最好的执行次序。n一方面，从叶子到根向上执行未必会产生最好效果；一方面，从叶子到根向上执行未必会产生最好效果；n另一方面，对查询树上有二元操作如并操作的联接操作时，其执行次序另一方面，对查询树上有二元操作如并操作的联接操作时，其执行次序还有许多方面可以还有许多方面可以“优化优化”。 n另外，为了对数据库存取进行定量分析，需要定义数据库的统计信息，以确定另外，为了对数据库存取进行定量分析，需要定义数据库的统计信息，以确定数据量的大小。数据量的大小。n即利用一种统计方法使查询执行前后对物理关系尺寸的变化能有所估计，即利用一种统计方法使查询执行前后对物理关系尺寸

67、的变化能有所估计，给出一个满意的执行次序。给出一个满意的执行次序。n一种行之有效的方法是计算物理关系的静态特征，估算出对物理关系操作一种行之有效的方法是计算物理关系的静态特征，估算出对物理关系操作后的变化，从而决定中间关系的特性后的变化，从而决定中间关系的特性。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2.3 操作方法的选择n关于操作方法的选择，更多地取决于对局部数据库的存取方式关于操作方法的选择，更多地取决于对局部数据库的存取方式n在物理转换时应尽量注意到对同一次数据库存取中的一些代数操在物理转换时应尽量注意到对同一次数据库存取中的一些代数操作是否能组合在一起

68、完成作是否能组合在一起完成n尽量避免多次内尽量避免多次内/外存调用，这与局部层优化有很大关系外存调用，这与局部层优化有很大关系n一般来说，在物理转换时，对同一场地上的数据库存取时要注意一般来说，在物理转换时，对同一场地上的数据库存取时要注意对同一物理关系的全部操作序列统一考虑，对于如何完成相应的数对同一物理关系的全部操作序列统一考虑，对于如何完成相应的数据库的存取，可以由局部层去考虑据库的存取，可以由局部层去考虑 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2.4 通讯代价的计算 这里介绍分布式数据库最特殊的代价因素：场地间信息的传输费用的估这里介绍分布式数据库最特

69、殊的代价因素：场地间信息的传输费用的估算。算。 在传输过程中一般有两种影响：费用（在传输过程中一般有两种影响：费用（cost）和延迟（）和延迟（delay）。 一次传输的传输费用（一次传输的传输费用（TC）和传输延迟（）和传输延迟（TD）可以用函数法表示，它们）可以用函数法表示，它们与数据量的大小成线性关系：与数据量的大小成线性关系： TC（X）C0+XC1 （4-9a）TD（X）D0+XD1 （4-9b） 其中，其中，C0，C1，D0，D1对均是与系统有关的常数。对均是与系统有关的常数。C0相当于场地间传输数相当于场地间传输数据的初始（启动一次）所需的固定费；据的初始（启动一次）所需的固定费

70、；C1是网络传输数据的统一费用；是网络传输数据的统一费用；D0是是两场地建立一次连接所需的固定时间；两场地建立一次连接所需的固定时间；D1是网络传输数据统一的单位传输速率。是网络传输数据统一的单位传输速率。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.4.2.5 操作场地选择 场地选择包含在逻辑关系转换为物理关系的过程中，选择了物理场地选择包含在逻辑关系转换为物理关系的过程中，选择了物理关系，逻辑关系就有了确定的场地。关系，逻辑关系就有了确定的场地。 但是还需考虑一系列问题，比如，查询结果场地是否就是查询始但是还需考虑一系列问题，比如，查询结果场地是否就是查询始发场地呢

71、？中间的每个操作在何处完成？完成后送何处？发场地呢？中间的每个操作在何处完成？完成后送何处？ 场地确定也包含有优化的策略。根据系统设计的总目标和相应的场地确定也包含有优化的策略。根据系统设计的总目标和相应的优化策略，有具体的场地选定的算法。优化策略，有具体的场地选定的算法。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5 联接操作4.5.1 联接操作重要性4.5.2 联接操作4.5.3 半联接操作原理和不对称性4.5.4 半联接操作的缩减作用4.5.5 半联接程序的作用4.5.6 半联接程序的具体过程分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5.

72、1 联接操作重要性n关系数据库由许多关系组成，关系与关系之间的联系主要通过联接操作表现出来，因而在二元操作中，联接操作远比其它操作用得多。n讨论联接，其实包括了“选择投影联接”的综合问题，即二元操作和一元操作的综合优化问题。n分布式查询处理的联接操作，更是影响分布式查询效率的最关键因素。n在DDB中，联接操作的大量数据会引起场地间的传输，它直接影响整个系统性能。n当前对联接操作的优化有两种趋向：一种是采用半联接技术来减少联接操作的操作数，以降低通讯费用；另一种是直接进行联接操作的代价计算分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5.2 联接操作联接操作联接操作是从两个

73、关系的笛卡尔积中选取属性间满足一定条件的元是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记作：组。记作： 其中其中A和和B分分别为R和和S上可比的属性上可比的属性组。 自然联接自然联接（Natural join）是一种特殊的等值联接，它要求两个关系中）是一种特殊的等值联接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。即若去掉。即若R和和S具有相同的属性组具有相同的属性组B，则自然连接可记作：（，则自然连接可记作：（实例实例）等值连接等值连接（equi-join），），为为“”的连接运算称为

74、等值连接。它是从的连接运算称为等值连接。它是从关系关系R与与S的笛卡尔积中选取的笛卡尔积中选取A、B属性值相等的那些元组。即等值连接属性值相等的那些元组。即等值连接为：（为：（实例实例） 分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024（回顾）自然联接图 自然联接实例自然联接自然联接的结果是在的结果是在 R R 和和 S S 中的在它们的公共属性名字上相等的所中的在它们的公共属性名字上相等的所有元组的组合。例如下面是表格有元组的组合。例如下面是表格“雇员雇员”和和“部门部门”和它们的自然联和它们的自然联接接: :分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024（

75、回顾）等值联接图 -联接实例-联接和等值联接联接和等值联接如果我们要组合来自两个关系的元组，而组合条件不是简单的共享属性如果我们要组合来自两个关系的元组，而组合条件不是简单的共享属性上的相等，则有一种更一般形式的连接算子才方便，这就是上的相等，则有一种更一般形式的连接算子才方便，这就是 - -联接联接( (或或 theta-theta-联接联接) )。 是在集合是在集合 , , 中的中的二元关系二元关系。的结的结果由在果由在 R R 和和 S S 中满足关系中满足关系 的元素的所有组合构成。只有的元素的所有组合构成。只有 S S 和和 R R 的的表头是不相交的，即不包含公共属性的情况下，表头

76、是不相交的，即不包含公共属性的情况下，-连接的结果才是有定连接的结果才是有定义的。义的。实例：实例：考虑分别列出车模和船模的价格的表“车”和“船”。假设一个顾客要购买一个车模和一个船模，但不想为船花费比车更多的钱。在关系上的-联接 CarPrice BoatPrice 生成所有可能选项的一个表。分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5.3 半联接操作原理和不对称性半联接操作半联接操作是关系代数操作中联接（是关系代数操作中联接（JOIN）操作的一种缩减，关系）操作的一种缩减，关系R和和S的的半联接记为半联接记为RS。其结果关系是其结果关系是R和和S的自然联接（的自然

77、联接（Natural JOIN）后，在）后，在R的属性上的投影的属性上的投影，可用下述表达式表示：，可用下述表达式表示： RS=R（RS） 等价方法：将等价方法：将S中与中与R有相同属性名的属性集投影出来，然后与有相同属性名的属性集投影出来，然后与R完成自然完成自然联接，其等价公式为：联接，其等价公式为：RS=R （BS） 具不对称操作性：具不对称操作性：RSSR。 半联接操作是一种导出操作：半联接操作是一种导出操作： 一个关系的分片是根据另一个与其有关联性质的关系的属性来划分，即诱导分片。而诱导分片就是用“半联接”概念实现的，即诱导分片是两个相关关系的半联接产生的。或者具体地说，是两个相关关

78、系实现自然联接后，在主关系的属性上的投影。 一个半联接操作的实例一个半联接操作的实例分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024（回顾）半联接图 半联接实例半联接半联接的结果只是在 S 中有在公共属性名字上相等的元组所有的 R 中的元组。实例：实例：“雇员”和“部门”和它们的半联接的表: 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5.4 半联接操作的缩减作用例例4.17 有R（A,B）和 S（B,C），根据半联接计算公式有： 和 。如果有图 4.21（a）的实例，则 R S的结果如 4.21（b）所示，S R的结果如图4.21（C）所示。图图4.1

79、2 半联接操作的不对称性与缩减作用半联接操作的不对称性与缩减作用 从图从图4.21（b）、（）、（c）可得出结论：半联接操可得出结论：半联接操作作对操作数对操作数R或或S有缩减有缩减作用作用，且由于，且由于其不对称其不对称性则各自缩减的程度不性则各自缩减的程度不一样一样。半联接操作的缩。半联接操作的缩减性与在联接操作前先减性与在联接操作前先对操作数关系做选择和对操作数关系做选择和投影有相似的效果。特投影有相似的效果。特别在分布式环境中，可别在分布式环境中，可用半联接操作减少网上用半联接操作减少网上数据的传送量。数据的传送量。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.

80、5.5 半联接程序的作用半联接程序半联接程序是用半联接技术实现联接操作的程序，即用一组具有半联接与是用半联接技术实现联接操作的程序，即用一组具有半联接与联接的操作，映射出具有与等值联接相同结果的过程。联接的操作，映射出具有与等值联接相同结果的过程。 (4-11a)(4-11b)（411a）、（）、（411b）式说明半联接程序与两个关系的直接等值联接等价。）式说明半联接程序与两个关系的直接等值联接等价。 同样，在分布式数据库中，当同样，在分布式数据库中，当R，S两个关系不在相同场地上时，用（两个关系不在相同场地上时，用（411a）公式或（）公式或（411b）公式处理，可公式处理，可以减少联接操作

81、的数据传送量，并且以减少联接操作的数据传送量，并且半联接程序的技术可以缩减它的操作数。半联接程序的技术可以缩减它的操作数。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/20244.5.6 半联接程序的具体过程以式（以式（4-11a）为例，且假定）为例，且假定 R和和S不在同一场地：不在同一场地： 在在s场地对场地对S关系做投影操作，使关系做投影操作，使S关系缩减为关系缩减为S： 将将S送往送往r场地；场地； 在在r场场地地上上完完成成R与与S的的半半联联接接操操作作，使使R关系缩减为关系缩减为R： 将将R关系送回关系送回S场地；场地； 在在S场地完成场地完成R与与S的联接操作。的联

82、接操作。 图图4.22 半联接程序操作半联接程序操作 图图4.22的核心技术思想是只将联接操作有关的操作分量在网上进行传输。的核心技术思想是只将联接操作有关的操作分量在网上进行传输。R与与S关系在关系在A=B条件下联接，条件下联接，R、S关系只有公共属性值相等的那些元组才有意义。关系只有公共属性值相等的那些元组才有意义。 分布式数据库 厦门大学计算机科学系 林子雨 7/26/2024附件：主讲教师和助教信息单位：厦门大学计算机科学系E-mail:个人网页：http:/ 厦门大学计算机科学系 林子雨 7/26/2024Department of Computer Science, Xiamen University, Nov, 2011