分布式数据库技术 专题三 分布式查询处理 厦门大学计算机科学系研究生课程 林子雨 厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn 厦门大学计算机科学系 2011年11月

专题三 分布式查询处理 第4章 分布式查询处理 4.1 分布式查询特点 4.2 全局查询转换的基础知识 4.3 全局查询到逻辑查询的转换 第4章 分布式查询处理 4.1 分布式查询特点 4.2 全局查询转换的基础知识 4.3 全局查询到逻辑查询的转换 4.4 逻辑查询到物理查询的转换 4.5 联接操作

4.1 分布式查询特点 4.1.1 分布式查询处理的定义 4.1.2 分布式查询的代价因素综述 4.1.1.2 分布式查询处理 4.1.1 分布式查询处理的定义 4.1.1.1 集中式数据库查询的基本原理 4.1.1.2 分布式查询处理 4.1.1.3 三种查询之间的联系 4.1.1.4 分布式查询定义 4.1.2 分布式查询的代价因素综述

4.1.1 分布式查询处理的定义 4.1.1.1 集中式数据库查询的基本原理 4.1.1.1 集中式数据库查询的基本原理 在集中式数据库环境中的查询处理，是将用户查询（由查询语言表达）转换成物理查询处理，其中包括了物理优化和逻辑优化两个层次。 物理优化：对关系（数据库）的基本操作符的运算在实现中的优化（如索引、排序、聚集（聚簇）等） 逻辑优化：在进行物理优化前先应有一个合理的（最优的）操作符次序或一些操作策略的选择

4.1.1 分布式查询处理的定义 4.1.1.2 分布式查询处理 分布式数据库环境是由虚拟的全局数据库和实际存在的各局部数据库组成的。DDB的分布性，使虚拟的全局数据库在抽象时还有逻辑数据库（LgDB)和物理数据库（PDB）的概念； DDB的四层模式结构中的局部概念层是由物理数据库映射到局部场地上的，即形成局部数据库； 分布式查询处理包含了全局查询处理和局部查询处理两个部分。但是，对使用 DDB 来说，用户（应用）只看到 GDB，且也只在全局关系上执行查询。而用户的这种查询是通过查询语言表示，并由系统将其转换。因而在查询执行过程中，实际上最终要涉及到具体场地上的物理关系的查询。 因此，分布式查询对应全局层三种数据库有三种查询：用户查询、逻辑查询和物理查询。

4.1.1 分布式查询处理的定义 集 中 式 三 层 摸 结 构 图 分 布 式 四 层 摸 结 构 图

4.1.1 分布式查询处理的定义 4.1.1.2 分布式查询处理 用户查询（Qu）： 是DDB中在全局数据库（GDB）上的查询； 4.1.1.2 分布式查询处理 用户查询（Qu）： 是DDB中在全局数据库（GDB）上的查询； 逻辑查询（QL）： 是DDB中在逻辑数据库（LgDB）上的查询； 物理查询（Qp）： 是DDB中在物理数据库（PDB）上的查询。

4.1.1 分布式查询处理的定义 4.1.1.3 三种查询之间的联系 上述三种查询之间有一定的联系，这种联系依赖于DDB的分片模式定义和分配模式定义，我们可用以下定理来描述： [ 定理 4.1 ]：对于任一用户查询Qu， 　　　　　　相应的逻辑查询为QL = Qu ·FS-1， 相应的物理查询为QP = Qu ·FS-1 ·AS–1。 证明：由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-1·AS-1 (PDB)， 因而，有Qu(GDB)= Qu(FS-1·AS-1 (PDB))= Qu.FS-1·AS-1 (PDB) 。

4.1.1 分布式查询处理的定义 4.1.1.4 分布式查询定义 定理4.1讨论的是全局层的查询处理，其中对用户查询，在系统中实际存在了两次转换：全局查询到逻辑查询的转换和逻辑查询到物理查询的转换。如下图所示： FS AS GDB LgDB PDB 转换1 转换2 Qu QL Qp

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

4.1.2 分布式查询的代价因素综述 分布式查询的代价因素如下： I／O代价（即估算输入/输出操作次数） CPU的使用情况 　传输代价（包括数据量的传输费用、传输的延迟时间，以及涉及 　　传输数据的控制信息及控制次数） 　分布事务处理的管理策略（事务可串行化、分布式并发控制、分 　　布式恢复） 　分布查询操作方法（如联接操作、并操作、二元操作以及全局查 　　询和局部查询的不同操作）对效率的影响

4.2 全局查询转换的基础知识 4.2.1 查询表达式的等价性 4.2.2 查询树 4.2.3 等价变换规则 4.2.4 限定关系的简化表示 4.2.1 查询表达式的等价性 4.2.2 查询树 4.2.3 等价变换规则 4.2.4 限定关系的简化表示 4.2.5 谓词合取性 4.2.6 扩充的关系代数规则

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

4.2.1 查询表达式的等价性 查询要得到结果，必须对关系进行具体操作： 并（∪）、差（﹣）、迪卡尔积（×）、选择（σ ）、投影（π ） 五种基本操作 并（∪）、差（﹣）、迪卡尔积（×）、选择（σ ）、投影（π ） 五种导出操作 交（∩）、商（÷）、联接（ ∞ ）、自然联接（∞）、半联接（∝） iθj 为了便于查询处理的转换，将上面的十种关系操作数分为两类： 一元操作，用U表示 二元操作，用B表示 属于一元操作的只有σ和π，而其余的操作都是二元操作

4.2.1 查询表达式的等价性 [定义4.2]：两个查询表达式 E1 和 E2 是等价的，如果其 查询的结果是相同的，记为 E1 ≡ E2。 [例]：对全局关系 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。

4.2.2 查询树 [定义4.3]： 查询树是一棵树 T=(V,E)，其中： 2）E是边集，二节点有边（V1,V2），当且仅当 V2 是 V1 的操作分量。 通常，人们用查询树表示查询表达式的内部结构。

4.2.2 查询树 例4.1：有查询Q1：查询北部地区（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’ ∞ Sp Dept 显然，边为 E1（∞ ，Sp ） D＃=D＃ 时，则Sp是非叶节点 ∞ 的分量。

4.2.2 查询树 例子：多表连接操作 表Student，存放学生基本信息 表BorrowBook，存放学生所借的书 StudentID StudentName StudentAge 1 张三 25 2 李四 26 3 王五 27 4 赵六 28 5 无名氏 表BorrowBook，存放学生所借的书 BorrowBookID BorrowBookName StudentID BorrowBookPublish 1 马克思主义政治经济学 电子工业出版社 2 毛泽东思想概论 高等教育出版社 3 邓小平理论 人民邮电出版社 4 大学生思想道德修养 中国铁道出版社 5 C语言程序设计

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 大学生思想道德修养 中国铁道出版社

4.2.2 查询树 用查询树表示更加复杂的查询表达式： E=πA(S∞σρ（R）)－πA（T∞R∞S） πA πA ∞ ∞ S σρ T ∞ R R S 查询树可以理解为全局查询树，其叶节点是全局关系。 根据等价定义，可用三种方式描述查询： SQL表达式（查询语句） 代数表达式 查询树 注意:查询树不同于分解树

4.2.2 查询树 图 分解树

4.2.3 等价变换规则 （1）单个关系的代数操作的变换规则 利用等价性定义，等价规则可以归纳为两类 R∪R≡R R∪Ø≡R Ø－R≡Ø R∝Ø≡Ø 　　 R∩R≡R R∩Ø≡Ø R×Ø≡Ø Ø∝R≡Ø R∞R≡R R∞Ø≡Ø σP（Ø）≡Ø R－R≡Ø R－Ø≡Ｒ πA（Ø）≡Ø 其中，关系R与空关系进行操作（联接）表示了一种空操作，在查 询转换过程中是可以消去的操作（某种程度的优化） 例4.2：（Ｒ－Ｒ）∞（Ｒ∪Ｒ） Ø ∞Ｒ Ø

4.2.3 等价变换规则 （2）多个关系模式的操作的变换规则 设有多个关系，其关系模式分别为R， S，T，在一定条件下有如下规则： ① 一元操作交换律： U1（ U2（R)) ≡ U2（ U1（R)) ② 二元操作结合律： (R)B((S)B(T)) ≡ ((R)B(S))B(T) ③ 二元操作交换律： (R)B(S) ≡(S)B(R) ④ 一元操作幂等律： U(R) ≡ U1U2 (R) ⑤ 一元操作对二元操作的分配律： U((R)B(S)) (U(R))B(U(S)) ⑥ 一元操作的因式分解律： (U(R))B(U(S)) U((R)B(S)) 利用等价变换规则可以改变操作序实现查询优化

4.2.4 限定关系的简化表示 逻辑关系（逻辑片段）是对全局关系进行σ、π、∞的操作得到的 从对关系的操作而言，逻辑关系是带有一定限定条件的关系，我们可称它为限定关系，它的限定条件是谓词或属性集 定理 4.1 指出用户查询必有相应的对逻辑关系和物理关系的查询，其中对逻辑关系的查询就是对这种限定关系的操作，也就是说，对关系的操作可以进一步地再作用到限定关系上 给出限定关系的简化表示为[R:Q]，其中：R是全局关系；Q是限定关系即逻辑关系应满足的谓词。[R:Q]读作“全局关系R对应于限定条件Q的逻辑关系（即限定关系）” 限定关系 [R:Q]被作为一个操作数，因此，它可以被关系代数所操作，这是一种扩充的操作

4.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’]= Ø 即，当限定关系的谓词合取是具有矛盾的限定条件，实际上将是一种空操作。 这种谓词合取可能为空的性质对查询转换（执行）时很有用，我们可以根据逻辑片段所具有的内涵性质，对其操作可能遗留下一些有矛盾的表达式为空的情况以简化查询的执行。

4.2.6 扩充的关系代数规则 对［R∶Q]的操作是关系代数操作的一种扩充，其中使用限定关系作为操作数。将关系代数操作作用到限定关系上有如下八条扩充规则 可以根据八个对限定关系的操作规则，讨论扩充的关系代数表达式转换的等价性 两个限定关系是等价的，即当它们的两个基础关系是等价的，且其限定条件都表示了相同的真值函数（即当对同一元组用两个限定条件时，能得到相同的真值） 用于限定关系的命题： [命题4.l]： 所有关系代数具有的等价转换同样适用于限定关系。

4.2.6 扩充的关系代数规则 规则（1） [R∶QR] [ R∶F∧QR] 直观地说，对一个全局关系进行选择操作（谓词为QR）得到的逻辑关系再做选择操作（谓词为F），相当于对全局关系做了一次选择操作，但其谓词为F AND QR，即谓词的合取性; 规则（2） πA[R∶QR] [ πAR∶QR] 对限定关系投影出某些属性（A），即使计算谓词条件的属性不在A中，所得到的限定关系的谓词不会改变，仍是QR。

4.2.6 扩充的关系代数规则 [R∶QR]×［S∶QS］ ［（R）×（S）∶QR∧QS] ［R∶QR］―[S∶QS] 规则（3） [R∶QR]×［S∶QS］ ［（R）×（S）∶QR∧QS] 同样有谓词合取性。 规则（4） ［R∶QR］―[S∶QS] ［（R）―（S）∶QR］ 两个限定关系的差操作是不对称的。 规则（5） [R∶QR]∪[S∶QS ] [（R）∪（S）∶QR∧Qs] 两个限定关系的并操作，其谓词具有合取性。 规则（6） [R∶QR]∩[S∶Qs] [(R)∩(S) ∶QR∧QS] 两个限定关系的交操作是由差操作推导出的。 [R:QR] [S:QS] [(R) (S):QR∧QS∧F] 规则（7） 两个限定关系的联接操作也是导出操作 。 规则（8） [R:QR] ∝ [S:QS] [ (R) ∝ (S):QR∧QS∧F] F F

4.3 全局查询到逻辑查询的转换 讨论“查询转换”，是讨论分布式数据库查询处理的优化。即在转换过程中，利用等价变换规则，综合并充分地考虑分布查询的代价因素，使分布查询处理逐步实现优化。 4.3.1 全局查询到逻辑查询的转换步骤 4.3.2 等价转换准则 4.3.2.1 全局查询转换成查询树 4.3.2.2 生成优化的逻辑查询树

4.3.1 全局查询到逻辑查询的转换步骤 原则上可以按两步实现分布式查询的第一次转换（全局查询到逻辑查询），每一步可遵守一些转换规则，以实现部分优化： 第一步： 将全局查询表达式（SQL语法和代数操作表达式）转换成全局查询内部结构形式（查询树） 在其转换过程中需要利用等价变换规则及其所归纳出来的两个转换准则（C1，C2） 第二步： 将全局查询树与模式分解树合并转换成部分优化的逻辑关系查询树，或称分解树的化简操作。其中包括：将全局查询树叶节点按分片模式定义的逻辑关系名，取代全局关系名（查询树与分解树合并），并分别运用变换规则，化简成部分优化的逻辑查询树。 其实现过程中，除了应用转换准则C1，C2以外，还有C3～C6准则。

4.3.2.1 全局查询转换成查询树 [例4.4]：对例4.1的查询树(a)，利用代数操作等价变换规则可有如图4.4所示。 图4.4 全局查询树转换范例

πS#σAREA=‘North’（Sp ∞ Dept） πS#（πS#，D# （Sp） ∞ πS#σAREA=‘North’（Dept） 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＃

4.3.2.1 全局查询转换成查询树 结论： 查询树相当于对一个集中式数据库的查询，集中式数据库的逻辑优化技术可以作用于其上。具体说是要： ①对全局查询树中的一元操作尽量下移到叶节点； ②如果查询树中有二元操作，则应尽量先缩减二元操作的操作数。由此，可获得等价转换准则C1和C2。 准则C1：缩减二元操作数关系，利用一元操作对二元操作的分配律，将一元操作向下移动。 U((R)B(S)) (U(R))B(U(S)) 准则C2：用一元操作幂等律对操作数关系产生适当的一元操作或分解成多个一元操作，以缩减操作数关系。 U(R)≡U1U2 (R)

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 一个实例

4.3.2.2.1 分解树的化简处理过程 图 分解树结构 分解树表明了全局关系由哪些逻辑关系组成，按什么方式组合 。 要将全局查询转换成逻辑查询，需要对分解树进行处理。对于一个全局查询而言，并非构成全局关系的所有逻辑关系都将涉及到，往往只使用其中某一些，所以应根据查询树对分解树进行处理。我们称它为分解树的化简处理。 图 分解树结构

4.3.2.2.1 分解树的化简处理过程 当全局查询用查询树表示，经过C1、C2 准则处理后，查询要用到的逻辑关系的条件在查询树中就表现出来了。接着，可以根据这些条件消去一些与查询无关的逻辑关系，即去掉一些操作为空的子树。 假设在查询树中，存在一棵关于全局关系R（U，True，T）的一元操作UnUn-1…U1的子查询树。令F为Ul，…Un中所有选择操作谓词的逻辑合取，即有 F= 。如果没有选择操作，则F=True，令A为U1,…，Un中所有投影操作中的属性和谓词Pj中所涉及的属性的并，即有： 令Qs=Un,…,U1(R)为关系R上的子查询，下面给出分解树化简的定义： 定义4.4：一个关系Ri（Ui，Qi，Si）对于子查询Qs是无用的，当FΛQi=False，Ui∩A=Ø； 否则是有用的。如果Ri是诱导分片所得的关系，当其主关系是无用的，它也是无用的。

4.3.2.2.1 分解树的化简处理过程 例4.5 ①设有关系R0上的子查询Qs= (R0)， 其查询子树如图4.7（a）所示，②R0的分解树见图3.6，有 F=P1∧P2，A=A1∪A2∪A（P1）∪A（P2）。 假设有F∧Q1=Flase，A∩U221=Ø,则③化简后的分解树如图4.7（b）所示。 图4.7 分解树化简

4.3.2.2.1 分解树的化简处理过程 图3.6 独立分片操作后的分解树结构

4.3.2.2.1 分解树的化简处理过程 根据上述论述，可从中归结两个化简分解树时有用的准则C3，C4：

4.3.2.2.2 分解树与查询树的合并过程 在分解树简化处理后应该与查询树合并。 这是两种性质不同的树，但由于分解树是由全局关系经过分片操作形成的，即一组代数操作。查询树是对全局关系的查询操作，也是一组代数操作。所以，我们可以用以下算法实现转化。 算法4.2：简化的分解树转化为逻辑查询树。 输入：已经化简后的分解树。 输出：从全局查询转换为逻辑查询树。 方法：从根节点开始： (1) 如果节点上操作Oj=H或DH，则将其转换为U（一元）操作节点； (2) 如果节点上的操作Oj=V，则将其转换为联接操作节点，联接属性是k； (3) 如果节点操作Oj=AO，则不必转换； (4) 直至将所有节点处理完毕，最后输出（获得）对逻辑片段的查询树。 (5) 当然，当得到了逻辑片段(关系)的查询树后，还应按C1、C2准则反复变换，使得一元操作下移，二元操作的操作数尽量缩减。

4.3.2.2.3 一元操作的合并过程 一元操作的合并 在得到逻辑查询树后可能还有一些性质，如在逻辑关系与二元操作之间或在二元操作之上存在若干一元操作。这时，就应按集中式数据库逻辑优化中的某些技术，使对同一逻辑关系的多个选择、投影，应合并成一个选择操作后接一个投影操作，且尽量使查询树上相连的一元操作最多只有2个。

4.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 分布联接图

4.3.2.2.4 分布联接的化简过程 对于完全联接的化简法有两种： 一种是部分分布联接图［如图4.8（b）］，其中部分节点间没有联通，使完全联接图形成两个或两个以上子图。 另一种是简化为简单分布联接图［如图4.8（C）］，每对节点间只有一条边。 图4.8 分布联接图

4.3.2.2.4 分布联接的化简过程 DDB中分片操作支持的诱导操作实际上是这种简单分布联接，R与S的逻辑关系只存在一对一的联接，这就可以先做局部联接，再完成分布联接，其通讯开销一定会降低。所谓先做局部联接，就是先在逻辑关系之间完成联接，然后再合并。 例4.6 设有图4.9（a）所示的查询树，S1，S2是按R1，R2诱导分片操作所得到的逻辑关系，该查询树可以依等价变换规则转换成图4.9（b）所示。图4.9（c）表示简单分布联接的查询树。 图4.9 简单分布联接

内容回顾（3.2.2.4 诱导分片）

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)

4.3.2.2.5 一个实例 例子：至此，我们可以将例4.4的全局查询转换再根据上述准则进行优化。假设全局关系Dept按部门号水平分片，其谓词为： Q1：D＃＝1～10 Q2：D＃＝11～20 Q3：D＃＝21～30 且D＃=1～10在“North”地区。同时有约定；North地区的零件由London供应者供应。图4.10是利用上列准则对图 4.4的进一步转换。 图4.4 全局查询树转换范例

4.3.2.2.5 一个实例 图4.10是例4.l的全局查询到逻辑查询的最后查询树，其中经过了从C1～C5准则。

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

4.4.1 物理转换中的基本内容和方法 一、什么是物理查询转换？ 所谓从逻辑查询到物理查询转换，是指将逻辑查询转换得到的简化了的查询树，转换成具体的每个场地上的局部操作命令和数据传输命令的过程。 也就是说，全局查询须两次转换后才形成一个具体的分布执行计划（DEP），然后才是交付给各个局部场地去执行。 在实际执行过程中也同样存在查询处理的优化，这就是前面提到过的分布式查询处理中的局部层优化。

4.4.1 物理转换中的基本内容和方法 二、物理转换的基本内容和策略综述 物理查询转换的过程，将涉及到物理副本和查询的处理场地，即执行环境。特别对于二元操作数不在同一场地时或者有多个副本可选择的情况时，其“执行环境”的概念更为重要。所以，物理转换时一般注意以下因素： 操作副本选择 操作执行次序的选择 操作方法的选择 通讯代价 评估数据量

4.4.2 物理转换的策略与方法分析 4.4.2.1 选择操作副本的原则和策略 4.4.2.2 操作执行次序的选择 4.4.2.1 选择操作副本的原则和策略 4.4.2.2 操作执行次序的选择 4.4.2.3 操作方法的选择 4.4.2.4 通讯代价的计算 4.4.2.5 操作场地选择

4.4.2.1 选择操作副本的原则和策略 操作副本的选择是选定逻辑关系相对应的物理关系有多个副本时的具体化。原则上，对不同查询有不同的具体选择。各个物理关系的副本其使用情况、路径代价和使用要求不完全一样，若按随机选定显然不合理，应该遵守一定的协定，选择一个理想的（合理的）副本。 副本的使用状态可分为可用和不可用。不可用指的是可能副本所在场地出现故障或到该场地的通讯有了故障；可用则又可能处于繁忙或轻松状态，这主要是指对副本可用时等候查询的多少。 为此，可以给出副本选择的一般原则： 本场地物理关系优先。如果查询始发场地上有逻辑关系的一个相应的物理关系，就应尽量的选择该物理关系 同场地上有二元操作，则应尽量选择同一场地上的相应物理关系完成二元操作，以减少数据传送 在查询等候中数据最小的物理关系应被优先选中 代价最小的应优先选中

4.4.2.2 操作执行次序的选择 在全局查询到逻辑查询转换时产生的查询树已经部分地蕴含了部分操作次序，如执行时从叶到根向上执行。然而，这并没有全部地给出最好的执行次序。 一方面，从叶子到根向上执行未必会产生最好效果； 另一方面，对查询树上有二元操作如并操作的联接操作时，其执行次序还有许多方面可以“优化”。 另外，为了对数据库存取进行定量分析，需要定义数据库的统计信息，以确定数据量的大小。 即利用一种统计方法使查询执行前后对物理关系尺寸的变化能有所估计，给出一个满意的执行次序。 一种行之有效的方法是计算物理关系的静态特征，估算出对物理关系操作后的变化，从而决定中间关系的特性。

4.4.2.3 操作方法的选择 关于操作方法的选择，更多地取决于对局部数据库的存取方式 在物理转换时应尽量注意到对同一次数据库存取中的一些代数操作是否能组合在一起完成 尽量避免多次内/外存调用，这与局部层优化有很大关系 一般来说，在物理转换时，对同一场地上的数据库存取时要注意对同一物理关系的全部操作序列统一考虑，对于如何完成相应的数据库的存取，可以由局部层去考虑

4.4.2.4 通讯代价的计算 这里介绍分布式数据库最特殊的代价因素：场地间信息的传输费用的估算。 在传输过程中一般有两种影响：费用（cost）和延迟（delay）。 一次传输的传输费用（TC）和传输延迟（TD）可以用函数法表示，它们与数据量的大小成线性关系： TC（X）＝C0+X×C1 （4-9a） TD（X）＝D0+X×D1 （4-9b） 其中，C0，C1，D0，D1对均是与系统有关的常数。C0相当于场地间传输数据的初始（启动一次）所需的固定费；C1是网络传输数据的统一费用；D0是两场地建立一次连接所需的固定时间；D1是网络传输数据统一的单位传输速率。

4.4.2.5 操作场地选择 场地选择包含在逻辑关系转换为物理关系的过程中，选择了物理关系，逻辑关系就有了确定的场地。 但是还需考虑一系列问题，比如，查询结果场地是否就是查询始发场地呢？中间的每个操作在何处完成？完成后送何处？ 场地确定也包含有优化的策略。根据系统设计的总目标和相应的优化策略，有具体的场地选定的算法。

4.5 联接操作 4.5.1 联接操作重要性 4.5.2 联接操作 4.5.3 半联接操作原理和不对称性 4.5.4 半联接操作的缩减作用 4.5.5 半联接程序的作用 4.5.6 半联接程序的具体过程

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

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

（回顾）自然联接 自然联接的结果是在 R 和 S 中的在它们的公共属性名字上相等的所有元组的组合。例如下面是表格“雇员”和“部门”和它们的自然联接: 图 自然联接实例

（回顾）等值联接 θ-联接和等值联接 如果我们要组合来自两个关系的元组，而组合条件不是简单的共享属性上的相等，则有一种更一般形式的连接算子才方便，这就是 θ-联接(或 theta-联接)。θ 是在集合 {<, ≤, =, >, ≥} 中的二元关系。θ的结果由在 R 和 S 中满足关系θ 的元素的所有组合构成。只有 S 和 R 的表头是不相交的，即不包含公共属性的情况下，θ-连接的结果才是有定义的。 实例：考虑分别列出车模和船模的价格的表“车”和“船”。假设一个顾客要购买一个车模和一个船模，但不想为船花费比车更多的钱。在关系上的θ-联接 CarPrice ≥ BoatPrice 生成所有可能选项的一个表。 图 θ-联接实例

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

（回顾）半联接 半联接的结果只是在 S 中有在公共属性名字上相等的元组所有的 R 中的元组。 实例：“雇员”和“部门”和它们的半联接的表: 图 半联接实例

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.21（b）、（c）可得出结论：半联接操作对操作数R或S有缩减作用，且由于其不对称性则各自缩减的程度不一样。半联接操作的缩减性与在联接操作前先对操作数关系做选择和投影有相似的效果。特别在分布式环境中，可用半联接操作减少网上数据的传送量。 图4.12 半联接操作的不对称性与缩减作用

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

以式（4-11a）为例，且假定 R和S不在同一场地： 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关系只有公共属性值相等的那些元组才有意义。

附件：主讲教师和助教信息 主讲教师：林子雨 单位：厦门大学计算机科学系 E-mail:ziyulin@xmu.edu.cn 个人网页：http://www.cs.xmu.edu.cn/linziyu 助教：苏志锋 单位：厦门大学计算机科学系2010级硕士研究生 E-mail:rocsky2010@foxmail.com

Department of Computer Science, Xiamen University, Nov, 2011