第9章 关系数据库理论精选文档.ppt

《第9章 关系数据库理论精选文档.ppt》由会员分享，可在线阅读，更多相关《第9章 关系数据库理论精选文档.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章 关系数据库理论关系数据库理论本讲稿第一页，共一百一十六页关系模式的规范化理论概述关系模式的规范化理论概述v关系数据库设计的核心是关系模式的设计。在设计关系模式时，必须考虑以下几个问题：应该构造几个关系？每个关系由哪些属性组成？关系模式中的所有关系应该满足哪些约束条件？如何体现这些约束条件？评价关系模型好坏的依据是什么？如何将不好的关系模型改进为好的关系模型？v上述这些问题都可以从关系数据库设计理论中找到答案。本讲稿第二页，共一百一十六页关系模式规范化的必要性关系模式规范化的必要性例例9-1 9-1 学生-课程-教师关系如表9-1所示，其中包含学生、课程和教师实体的属性有：学号、课程

2、号、成绩、教师姓名、职称等。本讲稿第三页，共一百一十六页关系模式规范化的必要性关系模式规范化的必要性v分析表9-1,可以发现上述关系中存在许多问题。数据冗余 同一信息重复出现。例如，教师的姓名、职称和所在系等信息重复出现，如果有100个学生选修张三丰老师的课，那么张三丰老师的相关信息要出现100次。更新异常 对学生-课程-教师关系中的记录进行修改可能出现数据不一致的情况。例如，把第二个记录中属性职称的值改为教授，就会出现李丽萍老师的职称不一致的问题，除非把李丽萍老师的所有职称都改为同一值。插入异常 某些信息无法正常插入。例如，课程C5由王路耀老师担任，但在还不知道哪些学生选修前，无法将王路耀老

3、师的记录插入关系中。因为，在学生-课程-教师关系中（学号,课程号）是主码，当学号不确定时，根据关系模型的实体完整性规则，不允许主码为空值，因此不能插入该记录。删除异常 某些信息被意外删除。例如，如果要删除某门课程的所有成绩，则会将教这门课的教师信息也删掉。例如，若要删除C4的记录，结果会丢失赵新朋老师的有关信息。显然，这是不希望发生的事情。本讲稿第四页，共一百一十六页关系模式规范化的必要性关系模式规范化的必要性本讲稿第五页，共一百一十六页如果将学生-课程-教师关系分解为表9-2a所示的学生-课程、表9-2b所示的课程-教师和表9-2c所示的教师三个关系，则上述的4个异常问题就基本解决了。本讲稿

4、第六页，共一百一十六页关系模式规范化的概念关系模式规范化的概念 v例9-1将学生-课程-教师关系分解为学生-课程、课程-教师和教师3个关系的过程就是关系模式规范化的过程。本讲稿第七页，共一百一十六页属性间的联系属性间的联系 v一对一联系一对一联系设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值，Y中至多有一个值与之对应，且反之亦然，则称X、Y两属性间是一对一联系，记为1:1。在表9-1所示的学生-课程-教师关系中，课程号和课程名称之间就是一对一的联系，一个课程号唯一地决定一门课程名称，而一门课程名称只有唯一的一个课程号与之对应。本讲稿第八页，共一百一十六页属性间的联系属性间的联系 v

5、一对多联系一对多联系如果对于X中的任一具体值，Y中至多有一个值与之对应，而Y中的一个值却可以和X中的n个值（n0）相对应，则称Y对X是一对多联系，记为1:n。在表9-1所示的学生-课程-教师关系中，教师和职称之间就是一对多的联系，一个教师只能有一个职称，而同一个职称可能对应多个教师。同理，(学号,课程号)与成绩之间，教师与所在系之间，都是一对多的联系。本讲稿第九页，共一百一十六页v多对多联系多对多联系如果对于X中的任一具体值，Y中有m（m0）个值与之对应，而Y中的一个值也可以和X中的n个值（n0）相对应，则称Y对X是多对多关系，记为m:n。在表9-1所示的学生-课程-教师关系中，学号和课程号之

6、间就是多对多联系，一个学生可以选修多门课程，而一个课程也可以同时被多个学生选修。属性间的联系属性间的联系 本讲稿第十页，共一百一十六页函数依赖函数依赖 v用U表示属性集的全集A1，A2，.，An，设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的所有具体关系r都满足如下约束：对于X的每一个具体值，Y有唯一的具体值与之对应，则称Y函数依赖于X，或X函数决定Y，记作XY，X称作决定因素。本讲稿第十一页，共一百一十六页v例例9-29-2 设有读者-图书-借书关系如表9-3所示，其中（读者号,书号）是候选码。函数依赖函数依赖 本讲稿第十二页，共一百一十六页表9-3中各属性之间的联系如

7、下：本讲稿第十三页，共一百一十六页平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖 v如果XY，并且Y不是X的子集，则称XY是非平凡函数依赖。如果XY，且Y是X的子集，则称XY是平凡函数依赖。v例9-2中的所有函数依赖都是非平凡函数依赖。本讲稿第十四页，共一百一十六页完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖 v设XY是关系模式R(U)的一个函数依赖，如果存在X的真子集X，使得XY成立，则称Y部分依赖于X，记作X Y。否则，称Y完全依赖于X，记作X Y。v在例9-2中，只有非主属性“借出日期”完全函数依赖于候选码（读者号，书号），即（读者号，书号）借出日期，而其他非主属性都是

8、部分函数依赖于主码。本讲稿第十五页，共一百一十六页传递函数依赖传递函数依赖 v在同一关系模式R(U)中，如果存在非平凡函数依赖XY，YZ而Y X，则称Z传递依赖于X。v在例9-2中，存在函数依赖：读者号单位，单位地址。根据传递函数依赖的定义，可知读者号地址是传递函数依赖。本讲稿第十六页，共一百一十六页第一范式（第一范式（1NF）v定定义义9-19-1 在关系模式R(U)中的每一个具体关系r中，如果每个属性值都是不可再分的最小数据单位，则称R(U)是第一范式的关系，记为R(U)lNF。v例9-2中的读者-图书-借书关系是满足1NF的.本讲稿第十七页，共一百一十六页第二范式（第二范式（2NF）v定

9、定义义9-29-2 如果关系模式R(U)中的所有非主属性都完全函数依赖于主码，则称R(U)是第二范式的关系，记为R(U)2NF。本讲稿第十八页，共一百一十六页 从图9-1可以发现，例9-2中的读者-图书-借书关系不满足2NF，因为其非主属性“姓名”、“单位”、“地址”、“书名”都没有完全函数依赖于候选码（读者号,书号）。作如图9-2所示的投影运算，就可将其分解为2NF的关系。本讲稿第十九页，共一百一十六页第三范式（第三范式（3NF）v定定义义9-39-3 如果关系模式R(U)中的所有非主属性对主码不存在传递函数依赖，则称R(U)是第三范式的关系，记为R(U)3NF。v3NF是一个可用的关系模式

10、应该满足的最低范式。本讲稿第二十页，共一百一十六页v3NF是一个可用的关系模式应该满足的最低范式。例9-2中的读者-图书-借书关系经过1NF，2NF和3NF的规范化后，就得到一个可用的关系模式，并包含4个关系：读者（读者号，姓名，单位名称），单位（单位名称，地址），图书（书号，书名），借书（读者号，书号，借出日期）。本讲稿第二十一页，共一百一十六页 v例9-3 有教务关系(学号，教工号，课程号)，其中（学号，教工号）和（学号，课程号）为候选码，且具有下列的函数依赖关系：每位老师只教授一门课，即教工号课程号。某学生选定一位老师，就对应一门课，即（学号，教工号）课程号。某学生选定一门课，就对应一位

11、老师，即（学号，课程号）教工号。(学号，教工号)和(学号，课程号)两个候选码相交，有公共的属性学号。教务关系中不存在非主属性，也就不可能存在非主属性对码的部分依赖或传递依赖，所以教务关系3NF。但是，这个教务关系仍然存在许多问题：插入异常：如果没有学生选修某位教师的任课，则该教师担任课程的信息就无法插入；删除异常：删除学生选课信息，会删除相关教师的任课信息；修改复杂：如果教师所教授的课程有所改动，则所有选修该教师课程的学生信息都要做改动；数据冗余：每位学生都存储了有关教师所教授的课程的信息。所以，仍需要进一步做规范化处理。这就需要用到BCNF范式。本讲稿第二十二页，共一百一十六页 v在例9-3

12、中，教务关系之所以出现问题就是因为决定因素被主码包含：教工号课程号中教工号是决定因素，但又被包含在候选主码（学号，教工号）中。所以不满足BCNF。如果将教务关系分解为教学（学号，教工号）和教课（教工号，课程号）两个关系，那么这两个新关系就都满足BCNF。本讲稿第二十三页，共一百一十六页多值依赖的定义多值依赖的定义v在关系模式R(U)中，X,Y,ZU且X+Y+Z=U。如果对R(U)中的任一关系r，给定一对(x,z)值，有一组Y的值，并且这组值仅由x值决定而与z值无关，那么关系模式R(U)中存在多值依赖XY。如果此时Z为空集（即 ），则XY被称为平凡多值依赖。本讲稿第二十四页，共一百一十六页v例例

13、9-4 9-4 设有满足BCNF的关系模式超市-助理-电话(超市名称，助理姓名，超市电话)，其中一家超市可能有多个助理，并且有多个电话号码，此时，就有如表9-4所示的关系。本讲稿第二十五页，共一百一十六页v在表9-4中，U=超市名称，助理姓名，超市电话，X=超市名称，Y=助理姓名，Z=超市电话，且X+Y+Z=U，存在多值依赖：超市名称助理姓名和超市名称超市电话。根据平凡多值依赖的定义，本例中的两个多值依赖都是非平凡多值依赖。本讲稿第二十六页，共一百一十六页多值依赖的性质多值依赖的性质 v多值依赖具有对称性：若XY，则XZ，其中ZUXY。多值依赖的对称性可以从例9-4中的两个多值依赖反映出来。v

14、多值依赖具有传递性：若XY，YZ，则XZY。v函数依赖可以看作是多值依赖的特殊情况：若XY，则XY。这是因为当XY时，对X的每一个值x，Y有一个确定的值y与之对应，所以XY。v若XY，XZ，则XY Zv若XY，XZ，则XYZ v若XY，XZ，则XYZ，XZY 本讲稿第二十七页，共一百一十六页第四范式（第四范式（4NF）v定义定义9-5 9-5 关系模式R(U)lNF,如果对于R的每个非平凡多值依赖XY(YX)，X都含有码,则称R(U)4NF。v4NF限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为根据定义，对于每一个非平凡的多值依赖XY，X都含有候选码，于是就有XY，所以4NF

15、所允许的非平凡的多值依赖实际上是函数依赖。本讲稿第二十八页，共一百一十六页 v在例9-4中，关系模式超市-助理-电话的候选码为（超市名称，助理姓名，超市电话），而X=超市名称，即X不包含码，所以不满足4NF。将超市-助理-电话解为超市-助理(超市名称，助理姓名)和超市-电话(超市名称，超市电话)两个关系。在超市-助理关系中，超市名称助理姓名，助理姓名不是超市名称的子集，而且超市名称是超市-助理关系的候选码，所以超市-助理关系满足4NF。同理，超市-电话关系也满足4NF。本讲稿第二十九页，共一百一十六页连接依赖的定义连接依赖的定义 v设R、R1、Rn是关系模式，U、U1、Un分别是R、R1、Rn

16、的属性集合，而且U=U1Un。如果R的任意关系实例r满足：则称R满足连接依赖，记作:其中 是自然连接符号。此时，如果某个Ui=U，则称该连接依赖是平凡连接依赖。本讲稿第三十页，共一百一十六页 v例例9-59-5 设有满足4NF的销售关系如表9-5所示，其中销售员代表汽车生产商（即单位），负责销售该生产商生产的汽车产品。本讲稿第三十一页，共一百一十六页 表9-5可以由表9-6所示的三个关系完全重建，即因此销售关系中存在连接依赖。本讲稿第三十二页，共一百一十六页第五范式（第五范式（5NF）v定定义义9-69-6 如果关系模式R(U)中的每一个连接依 赖 都 是 由 R的 候 选 码 所 蕴 含,则

17、 称R(U)5NF。本讲稿第三十三页，共一百一十六页 v在例9-5中，销售关系的候选码是（销售员，单位，产品名称），销售关系的连接依赖:都不由销售的候选码所蕴含，所以销售关系不满足5NF。但是，销售关系分解后的R1，R2和R3这三个关系都满足5NF。本讲稿第三十四页，共一百一十六页关系模式规范化的小结关系模式规范化的小结 v关系模式规范化的基本思想如图9-3所示 本讲稿第三十五页，共一百一十六页v关系模式的规范化会带来以下好处：由于关系中的各个数据项都是一个简单的数或符号串，故可以方便地进行存取。由于模式的分解，可以简化检索操作，故加快了检索速率。可消除对数据进行插入、修改和删除时的相互牵扯，

18、便于保持数据的一致性。可通过对于分解模式的连接来产生出新的模式，便于引入新型数据。避免重复存储，减少数据的冗余度，存储空间的利用率。关系模式规范化的小结关系模式规范化的小结 本讲稿第三十六页，共一百一十六页模式分解的定义模式分解的定义 v所谓模式分解是指根据规范化理论将一个结构复杂的关系分解为几个结构简单的关系的过程。v模式分解的目的是消除关系模式中存在的存入、删除、修改异常和数据冗余等弊病。模式分解的准则是既要保持函数依赖（即不破坏属性间存在的依赖关系），又要具有无损连接性（即不增减信息）本讲稿第三十七页，共一百一十六页模式分解的理论基础模式分解的理论基础 v函数依赖的逻辑蕴含 关系模式R(

19、U)，F是其函数依赖，X,Y是其属性U的子集，如果从F的函数依赖能够推出XY，则称F逻辑蕴涵XY。本讲稿第三十八页，共一百一十六页模式分解的理论基础模式分解的理论基础 vArmstrong公理体系Armstrong公理体系是用来推导函数依赖F是否蕴含XY。它包括:Armstrong公理系统基于Amstrong公理的推理规则Armstrong公理系统的有效性和完备性 本讲稿第三十九页，共一百一十六页Armstrong公理系统公理系统 v关系模式R(U)，F为R的一组函数依赖，X，Y，Z是属性集U的子集，则有下列公式成立：自反律（Reflexivity）：若YXU，则XY为F所蕴含。增广律：若XY

20、为F所蕴含，且ZY，则XZYZ为F所蕴含。传递性：若XY和YZ为F所蕴含，则XZ为F所蕴含。本讲稿第四十页，共一百一十六页基于基于Amstrong公理的推理规则公理的推理规则 合并规则：若XY，XZ，则 XYZ伪传递规则：若XY，WYZ，则 XWZ分解规则：若XY，ZY，则 XZ本讲稿第四十一页，共一百一十六页引理1：XA1A2Ak成立的充分必要条件是:XAi（i=1,2,k）成立。基于基于Amstrong公理的推理规则公理的推理规则 本讲稿第四十二页，共一百一十六页Armstrong公理系统的有效性和完备性公理系统的有效性和完备性 Armstrong公理系统是有效的和完备的Armstrong

21、公理系统的有效性是指由F出发根据Armstrong公理推导出的每一个函数依赖必在F+中（F+是F所逻辑蕴含的函数依赖的全体,即F的闭包）。完备性是指F+中每一个函数依赖必定可以由F出发根据Armstrong公理推导出来。本讲稿第四十三页，共一百一十六页属性集的闭包属性集的闭包 闭包的定义 设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。本讲稿第四十四页，共一百一十六页属性集的闭包属性集的闭包 闭包的计算 计算属性集闭包的算法如图9-4所示本讲稿第四十五页，共一百一十六页 v例例9-69-6 有关系模式R(U)

22、，其中属性集U=(A,B,C,G,H,I),属性集U上的函数依赖F=AB,ACCGH,CGI,BH，计算(AG)F+。解：根据图9-4所示的算法，具体计算步骤如下：令X(0)=AGX(1)=X(0)B=AGB，用依赖ABX(2)=X(1)C=AGBC，用依赖ACX(3)=X(2)H=AGBCH，用依赖BHX(4)=X(3)I=AGBCHI，用依赖CGI输出(AG)F+=AGBCHI本讲稿第四十六页，共一百一十六页 v有关系模式R(U)，其中属性集U=(A,B,C,D,E,G),属性集U上的函数依赖F=AE,BEAG,CEA,GD,计算(AB)F+。解：根据图9-4所示的算法，具体计算步骤如下：

23、令X(0)=ABX(1)=X(0)E=ABE，用依赖AEX(2)=X(1)G=ABEG，用依赖BEAGX(3)=X(2)D=ABEGD，用依赖GD输出(AB)F+=ABEGD本讲稿第四十七页，共一百一十六页 引理2：关系模式R(U)，X和Y是U的子集，F为属性U上的一组函数依赖，则XY能由Armstrong公 理 导 出 的 充 分 必 要 条 件 是YXF+。这样，判定XY能否由Armstrong公理导出的问题，就转化为求XF+，判定Y是否为XF+的子集的问题。而XF+可以由图9-4所示的算法求得。本讲稿第四十八页，共一百一十六页 v例例9-89-8 有关系模式R(U)，其中属性集U=(A,

24、B,C,D,E),属性集U上的函数依赖F=ABC,BD,CE,ECB,ACB,判定ABDE能否由Armstrong公理导出。解：判定ABDE能否由Armstrong公理导出，可以 转化为先求出(AB)F+，然后判定DE是否为 (AB)F+的子集。令X(0)=ABX(1)=X(0)CD=ABCD，用依赖ABC，BDX(2)=X(1)E=ABCDE，用依赖CE输出(AB)F+=ABCDEDE(AB)F+，所以ABDE能由Armstrong公理导出本讲稿第四十九页，共一百一十六页函数依赖的等价和覆盖函数依赖的等价和覆盖 若G+=F+，则称函数依赖集F覆盖G，或者G覆盖F，即F和G等价。本讲稿第五十页

25、，共一百一十六页 引理3：G+=F+的充分必要条件是：G+F+和F+G+这条引理给出了判断两个函数依赖等价的可行算法：先判断F+G+，具体步骤是逐一对F中的函数依赖XY，考察Y是否属于XG+。再判断G+F+，具体步骤是逐一对G中的函数依赖XY，考察Y是否属于XF+。本讲稿第五十一页，共一百一十六页最小函数依赖集（最小覆盖）最小函数依赖集（最小覆盖）v满足下列条件的函数依赖集F称为最小覆盖，记作Fmin：单属性化：F中任一函数依赖XA，A必是单属性。无冗余化：F中不存在这样的函数依赖XA，使得F与FXA等价。既约化：F中不存在这样的函数依赖XA，在X中有真子集Z，使得F与FXAZA等价。本讲稿第

26、五十二页，共一百一十六页 v求函数依赖集F的最小覆盖Fmin的算法如图9-5所示 本讲稿第五十三页，共一百一十六页 v例例9-99-9 设有函数依赖集F=AB,BA,AC,BC，求Fmin。解：根据图9-5所示的算法，具体求解步骤如下：单属性化:所有函数依赖中的Y已经是单属性的。无冗余化:检查 AB,G=FAB=BA,AC,BC,AG+=A,C,BA,C 检查 AC,G=FAC=AB,BA,BC,AG+=A,B,C,CA,B,C 从F中删除AC 既约化 所有函数依赖中的X是单属性的，该步骤可 略 Fmin=AB，BA，BC或者 Fmin=AB，BA，AC本讲稿第五十四页，共一百一十六页模式分解

27、的算法模式分解的算法 v模式分解的基本要求是分解前后的关系模式必须等价，即分解必须具有无损连接和函数依赖保持特性。因此，必须注意以下几个结论：（1）若要求分解具有无损连接性，那么分解一定可以达到BCNF。（2）若要求分解保持函数依赖，那么分解可以达到3NF，但不一定能达到BCNF。（3）若要求分解即保持函数依赖，又具有无损连接性，那么分解可以达到3NF，但不一定能达到BCNF。本讲稿第五十五页，共一百一十六页v模式分解的算法主要有三种：将关系模式转化为3NF的保持函数依赖的算法，将关系模式转化为3NF且具有无损连接性又能保持函数依赖的算法，将关系模式转化为BCNF的无损连接的算法。模式分解的算

28、法模式分解的算法 本讲稿第五十六页，共一百一十六页模式分解的算法模式分解的算法 v将将关关系系模模式式转转化化为为3NF的的保保持持函函数数依依赖赖的的算算法法 分解的函数依赖保持性 设 F是 关 系 模 式 R(U)的 函 数 依 赖 集，=R1(U1),R2(U2),Rk(Uk)为R(U)的一个分解，且F1,F2,Fk分别是R1(U1),R2(U2),Rk(Uk)的函数依赖集。如果Fi=Ri(F)(i=1,2,k)的并集(F1F2Fk)+F+,则称分解具有函数依赖保持性。本讲稿第五十七页，共一百一十六页 v3NF保持函数依赖分解算法如图9-6所示 本讲稿第五十八页，共一百一十六页 例例9-

29、109-10 将关系模式R(课程C,教师T,时间H,教室R，学生S，成绩G)分解为一组保持函数依赖达到3NF的关系模式。函数依赖集F为：CT：每门课程仅有一位教师担任 HTR：在任一时间，一个教师只能在一个教室上课 HRC：在任一时间，每个教师只能上一门课 HSR：在任一时间，每个学生只能在一个教室听课 CSG：每个学生学习一门课程只有一个成绩解：根据图9-6所示的3NF保持函数依赖分解算法，输入 R(U)1NF，U=(C,T,H,R,S,G),最小函数依赖集 F=CT,CSG,HRC,HSR,HTR。具体分解步骤如下：不存在不出现在任何一个函数依赖中的属性。不存在F中有一个函数依赖XA，且X

30、A=U。对F中的每一个函数依赖XA，构造一个关系模式R(X,A)，这样F中共有5个函数依赖，所以该模式可以保持函数依赖地分解为如下一组3NF的关系模式：=CT,CGS,CHR,HRS,HRT。本讲稿第五十九页，共一百一十六页模式分解的算法模式分解的算法 v将将关关系系模模式式转转化化为为3NF且且具具有有无无损损连连接接性性又又能能保保持持函函数数依赖的算法依赖的算法分解的无损连接性无损连接的定义 设F是关系模式R(U)的函数依赖集，=R1(U1),R2(U2),Rk(Uk)为R(U)的一个分解，且F1,F2,Fk分别是R1(U1),R2(U2),Rk(Uk)的函数依赖集。设r是R(U)的一个

31、关系实例，且有如下定义：如果对R的满足F的任一个关系r，均有r=m(r)，则称分解具有无损连接。本讲稿第六十页，共一百一十六页 v判定无损连接的算法 设=R1(U1,F1),.,Rk(Uk,Fk)是R(U,F)的一个分解,U=A1,A2,.,An,F=FD1,FD2,.,FDp，其中F为一最小依赖集，记FDi为XiAli。判定无损连接的算法如下：建立n列k行的一张表，每列对应于一个属性，每行对应于分解中的一个关系模式，若AjUi，则在j列i行上填aj，否则填bij；对每一个FDi做下列操作，找到Xi所对应的列中具有相同符号的那些行进行考查，考查这些行中lj列的元素，若其中有ali,则全部改为a

32、li，否则全部改为bm,li，l是这些行中最小的行号值；如果在某次更改后，有一行成为a1,a2,.an，则算法终止，具有无损连接，否则不具有无损连接；对F中个FD逐一进行一次这样的处理，称为对F的一次扫描。比较扫描前后，表有无变化，如有变化则转，否则算法终止。本讲稿第六十一页，共一百一十六页 v定定理理9-19-1 为无损连接分解的充分必要条件是 上 述 算 法 终 止 时，表 中 有 一 行 为a1,a2,.an本讲稿第六十二页，共一百一十六页 v具有无损连接性和保持函数依赖性的分解算法如图9-7所示。本讲稿第六十三页，共一百一十六页 v例例9-119-11 将例9-10的关系模式R分解为一

33、组3NF的关系模式，要求分解同时具有无损连接性和保持函数依赖性。解：根据图9-7所示的算法，具体解题步骤如下：跟据图9-6所示的3NF保持函数依赖分解算法，得到 =CT,CGS,CHR,HRS,HRT；HS是原模式的候选码，所以 =CT,CGS,CHR,HRS,HRT,HS；由于HS是模式HRS的一个子集，所以应该消去HS，那么最后的分解CT,CGS,CHR,HRS,HRT 就是具有无损连接性和保持函数依赖性的分解，且其中所有模式都是3NF。本讲稿第六十四页，共一百一十六页将关系模式转化为将关系模式转化为BCNF的无损连接的算法的无损连接的算法 v具有无损连接性的BCNF分解算法如图9-8所示

34、 本讲稿第六十五页，共一百一十六页 例例9-129-12 设关系模式R(ABCDE),R的函数依赖关系F=AD,ED,DB,BCD,DCA，请求出该关系的候选码。解：判断关系R中的属性是否为候选码的步骤如下：如果某个属性不在被决定因子中，该属性一定是侯选码的一部分。如果某个属性不在决定因子中，该属性一定不是侯选码的一部分。使用Armtrong公理去掉多余的函数依赖和左部多余的属性。在本例中，寻找候选码的具体步骤如下：因为ED,所以 ECDC 因为DCA,所以ECA 因为DB，所以DCBCB，ECB 所以得ECABD 所以：EC为候选码，这里候选码仅有一个 主属性：EC,非主属性：A,B,D本讲

35、稿第六十六页，共一百一十六页 例例9-139-13 将例9-10的关系模式R分解为具有无损连接的BCNF。解：根据图9-8所示的具有无损连接性的BCNF分解算法，具体解 题步骤如下：关系模式R的最小函数依赖集 F=CT,CSG,HRC,HSR,HTR 关系模式R的候选码为HS。由于CS不包含候选码且CSG，根据算法的第三步将R分解 为R1(U1)和R2(U2)，其中U1=C,S,G,U2=C,T,H,R,S，并 求得R1(U1)和R2(U2)上的最小函数依赖集：R1(CSG,CSG)(属于BCNF)R2(CTHRS,HSR,HTR,CT,HRC)=R1,R2 关系模式R2的候选码为HS。本讲稿

36、第六十七页，共一百一十六页 由于C不包含候选码CT，将R2分解为R3(U3)和R4(U4)，其中U3=C,T,U4=C,H,R,S，并求得R3和R4上的最小函数依 赖集：R3(CT,CT)(属于BCNF)，R4(CHRS,HSR,HRC),=R1,R3,R4 关系模式R4的候选码为HS。由于HR不包含候选码且HRC，将R4分解为R5(U5)和 R6(U6),其中U5=H,C,R,U6=H,R,S，并求得R5和 R6上的最 小函数依赖集：R5(HRC,HRC)(属于BCNF)，R6(HRS,HSR)(属于BCNF)，=R1,R3,R5,R6。由此可得，=R1,R3,R5,R6，即=CSG,CT,

37、HRC,HSR，中的所有关系模式都是BCNF。本讲稿第六十八页，共一百一十六页 查询优化查询优化 v关系查询优化属于关系数据库的操作理论。v关系查询优化是影响DBMS性能的关键因素。本讲稿第六十九页，共一百一十六页查询优化的必要性查询优化的必要性 例例9-149-14 设有教学管理关系模式如下，求“李刚”选修的课程号和成绩。学生（学号，姓名，性别，所在系，班号，出生日期）课程（课程号，课程名，学时，学分，先修课程号）选修（学号，课程号，成绩）用SQL实现查询，其语句为：SELECT 课程号，成绩 FROM 学生，选课 WHERE 学生.学号=选课.学号AND 姓名=李刚 该查询语句可以用多种等

38、价的关系代数表达式来完成：Q1=课程号,成绩(学生.学号=选课.学号 姓名=李刚(学生选修)Q2=课程号,成绩(姓名=李刚(学生 选修)Q3=课程号,成绩(姓名=李刚(学生)选修)本讲稿第七十页，共一百一十六页 Q1、Q2和Q3操作的结果是一样的。但分析这三种关系代数表达式可以发现，由于查询执行的策略不同,所需的查询时间相差很大。本讲稿第七十一页，共一百一十六页 v对于Q1而言，当计算(学生选修)时，需要把这两个关系的全部元组连接起来。假设每个存储块能保存10个元组，学生关系的物理文件在存贮器中需B1个存贮存块，选修关系的物理文件需B2块。内存中提供的运算缓冲区最多能装n块，而B1,B2均大于

39、n。计算广义笛卡尔积的办法是：将学生文件分成若干个n-1块,首先将第一个n-l块装入内存，并逐次装入选修文件的一个块，使之与学生文件已装入的n-l块进行乘积运算。当选课文件的每块都装入一遍后，再往内存装入学生文件的下一个n-l块，并同样从第一块开始逐次地装入选修文件的每一块，重复执行上述连接运算，这样直到计算完乘积的全部元组为止，其读块数目为：B1+B1/(n-1)B2。设B1=B2=1000，n=50，则所需读块的总数目为1000+1000/491000=21000。假设1s钟能读20块时，大约需要18min时间。同样假设每个存储块能保存连接后的10个元组和一秒钟能写入20块，则连接后一共有

40、10001000=2000000块，将连接后的中间结果写入存储器需要1667min，然后再将中间结果读出来进行选择和投影，也需1667min。与读块和写块相比，连接、选择、投影等运算时间均可忽略不计。完成Q1表达式的运算时间大约需要3352min，即近56h。本讲稿第七十二页，共一百一十六页 v对Q2而言，为了执行自然连接，读取学生文件和选修文件的策略不变,总的读取块数仍为21000块，花费1080s。但自然连接的结果比Q1的情况大大减少，为100000个元组,占10000块，因此写出这些元组时间均约为500s,将中间结果读出来进行选择和投影也需500s。所以完成Q2表达式的运算时间大约需要2

41、080s，即35min，仅为Q1的百分之一。v对Q3而言，先对学生文件做姓名=李刚的选择操作，读块数目为B1。然后把结果与选课文件作连接、投影运算，读块数目为B2，所以总的读块数目为B1+B2=2000。由于满足条件的元组很少(大约50个元组)，不用保存中间结果文件，因而完成Q3表达式共需约1.7min(1s仍读20块)，仅等于Q1的二千分之一。本讲稿第七十三页，共一百一十六页查询优化的一般准则查询优化的一般准则 1.1.选择运算应尽可能先做选择运算应尽可能先做 在优化策略中这是最重要、最基本的一条。它常常可使执行时间节约几个数量级，因为选择运算一般使计算的中间结果减小很多。本讲稿第七十四页，

42、共一百一十六页2.2.在执行连接操作前对关系适当地预在执行连接操作前对关系适当地预处理处理 预处理方法一般有两种：其一是连接属性上建立索引，其二是对关系排序。前者称为索引连接方法，后者称为排序合并(SORT-MERGE)连接方法 查询优化的一般准则查询优化的一般准则 本讲稿第七十五页，共一百一十六页 对于(学生 选修)这样的自然连接，用索引连接方法的步骤是：（1）在选修表上建立学号的索引。（2）对学生表中每一个元组,由学号通过选修表的索引 查找相应的选修表中的元组。（3）把这些选修表的元组和学生表的元组连接起来。这样学生表和选修表均只要扫描一遍，处理时间只是两个关系大小的线性函数。查询优化的一

43、般准则查询优化的一般准则 本讲稿第七十六页，共一百一十六页 对于(学生 选修)这样的自然连接，用排序合并连接方法的步骤是：（1）首先对学生表和选修表按连接属性学号排序。（2）取学生表中第一个学号,依次扫描选修表中具有相 同学号的元组，把它们连接起来。（3）当扫描到学号不相同的第一个选修表中的元组 时，返回学生表，并扫描它的下一个元组，再扫 描选修表中具有相同学号的元组，把它们连接起 来。重复上述步骤直到学生表扫描完.这样学生表和选课表也只要扫描一遍。当然，执行时间要加上对两个表的排序时间。即使这样，使用预处理方法执行连接的时间一般仍大大减少。查询优化的一般准则查询优化的一般准则 本讲稿第七十七

44、页，共一百一十六页 3.3.投影运算和选择运算同时做投影运算和选择运算同时做 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。查询优化的一般准则查询优化的一般准则 本讲稿第七十八页，共一百一十六页4.4.投影同双目运算结合投影同双目运算结合 把投影同其前或其后的双目运算结合起来，以减少扫描关系的次数。查询优化的一般准则查询优化的一般准则 本讲稿第七十九页，共一百一十六页5.5.选择操作同某些笛卡尔积结合起来构成一选择操作同某些笛卡尔积结合起来构成一个连接运算个连接运算 把某个选择操作同在它前面要执行的笛卡尔积结合起来成为一个连接

45、运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。查询优化的一般准则查询优化的一般准则 本讲稿第八十页，共一百一十六页6.6.找出公共子表达式找出公共子表达式 如果重复出现的子表达式的查询结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询的是视图时，定义视图的表达式就是公共子表达式的情况。查询优化的一般准则查询优化的一般准则 本讲稿第八十一页，共一百一十六页关系代数等价变换规则关系代数等价变换规则 v关系代数等价的定义关系代数等价的定义 如果两个查询表达式E1和E2查询的结果是相同的，那么它们是等

46、价的，记为：E1E2。本讲稿第八十二页，共一百一十六页（1）连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有：关系代数等价变换规则关系代数等价变换规则 本讲稿第八十三页，共一百一十六页 (2)连接、笛卡尔积的结合律 E1，E2，E3是关系代数表达式，Fl和F2是连接运算的条件，则有：关系代数等价变换规则关系代数等价变换规则 本讲稿第八十四页，共一百一十六页（3）投影的串接定律 这里E是关系代数表达式Ai(i=1,2,.,n),Bj(j=l,2,.,m)是属性名且A1,A2,.,An构成Bl，B2，.，Bm的子集。关系代数等价变换规则关系代数等价变换规则 本讲稿第八十

47、五页，共一百一十六页 （4）选择的串接定律 这里，E是关系代数表达式，Fl，F2是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。关系代数等价变换规则关系代数等价变换规则 本讲稿第八十六页，共一百一十六页 （5）选择与投影的交换律 这里，选择条件F只涉及属性A1,.,An。若F中有不属于A1,.,An的属性B1，,Bm，则有更一般的规则：关系代数等价变换规则关系代数等价变换规则 本讲稿第八十七页，共一百一十六页（6）选择与笛卡尔积的交换律如果F中涉及的属性都是El中的属性,则 如果F=F1F2，并且F1只涉及El中的属性，F2只涉及E2中的属性，则由上面的等价变换规则可推

48、出：如果F1只涉及El中的属性，F2涉及El和E2两者的属性，则仍有关系代数等价变换规则关系代数等价变换规则 本讲稿第八十八页，共一百一十六页 （7）选择与差运算的交换若E1与E2有相同的属性名，则关系代数等价变换规则关系代数等价变换规则 本讲稿第八十九页，共一百一十六页 （8）选择与差运算的交换若E1与E2有相同的属性名，则关系代数等价变换规则关系代数等价变换规则 本讲稿第九十页，共一百一十六页 （9）投影与笛卡尔积的交换设E1和E2是两个关系表达式，A1，.，An是E1的属性，B1，.，Bm是E2的属性，则关系代数等价变换规则关系代数等价变换规则 本讲稿第九十一页，共一百一十六页 （10）

49、投影与并的交换设E1和E2有相同的属性名，则关系代数等价变换规则关系代数等价变换规则 本讲稿第九十二页，共一百一十六页查询树的概念查询树的概念 定义定义9-79-7 查询树是一棵树T=(V,E)，其中：1）V是节点集，每个非叶节点是关系操作符，叶节点是关系名（即查询涉及的关系）。2）E是边集，二节点有边(V1,V2)，当且仅当V2是V1的操作分量。查询树包括叶节点和非叶节点。叶节点是关系名（即查询涉及的关系），非叶节点是关系操作符。本讲稿第九十三页，共一百一十六页 例例9-15 9-15 有查询Q1：“查询北部地区所属部门发出订单的供应商号。”这个查询Q1的SQL表达式为：SELECT 供应商

50、号 FROM 部门,供应商 WHERE供应商.供应商号=部门.供应商号 AND 地区=北部 其相应的关系代数表达式为：其相应的查询树如图9-9所示。本讲稿第九十四页，共一百一十六页本讲稿第九十五页，共一百一十六页本讲稿第九十六页，共一百一十六页查询优化算法查询优化算法 本讲稿第九十七页，共一百一十六页优化的一般步骤优化的一般步骤 1.1.把查询转换成某种内部表示把查询转换成某种内部表示首先对关系代数表达式进行分析，给出语法树，即查询树。例例9-169-16 将例9-14中的实例变换成用内部表示的语法树，如图9-12所示。经过关系代数表达式的转换，则可变成图9-13所示的语法树，即例9-14中Q