第4章 关系数据库理论ppt课件

《第4章 关系数据库理论ppt课件》由会员分享，可在线阅读，更多相关《第4章 关系数据库理论ppt课件（47页珍藏版）》请在金锄头文库上搜索。

1、第4章 关系数据库理论,2,4.1 规范化问题的提出 4.2 函数依赖 4.3 关系模式的分解* 4.4 关系模式的范式 4.5 关系模式的规范化,3,4.1 规范化问题的提出,4.1.1 规范化理论的主要内容 关系数据库的规范化理论 函数依赖 范式（Normal Form） 模式设计,核心，是模式分解和设计的基础,模式分解的标准,4,4.1.2 不合理的关系模式存在的存储异常问题,教学管理数据库 SCD(SNo，SN，Age，Dept，MN，CNo，Score) 在此关系模式中填入一部分具体的数据,5,该表出现的问题,数据冗余 插入异常 删除异常 更新异常,根本原因：属性间存 在着数据依赖关

2、系,包罗万象,6,一个好的关系模式应该具备以下四个条件： （1）尽可能少的数据冗余； （2）没有插入异常； （3）没有删除异常； （4）没有更新异常。,SCD (SNo，SN，Age， Dept，MN，CNo，Score),S(SNo，SN，Age，Dept),SC(SNo，CNo，Score),D(Dept，MN),关系模式分解：,7,4.2 函数依赖,4.2.1 函数依赖的定义 定义4.1 SNo决定函数（SN，Age，Dept） （SN，Age，Dept）函数依赖于SNo,SCD (SNo，SN，Age，Dept，MN，CNo，Score),SNo,一个学生,SN，Age，Dept,惟一

3、确定,惟一确定,8,4.2.2 函数依赖的逻辑蕴涵定义,定义4.2 设F是在关系模式R(U)上成立的函数依赖集合，X，Y是属性集U的子集，XY是一个函数依赖。如果从F中能够推导出XY，即如果对于R的每个满足F的关系r也满足XY，则称XY为F的逻辑蕴涵（或F逻辑蕴涵XY），记为F|=XY 。 定义4.3 设F是函数依赖集，被F逻辑蕴涵的函数依赖的全体构成的集合，称为函数依赖集F的闭包（Closure），记为F +。即：F += XY | F|=XY,9,4.2.3函数依赖的推理规则,Armstrong公理 自反律： 如果YXU，则XY在R上成立如果YXU，则XY在R上成立 增广律 ： 若XY在R

4、上成立，且ZU，则XZYZ在R上也成立 传递律 ： 若XY和YZ在R上成立，则XZ在R上也成立,10,Armstrong公理推论 合并律（Union rule） 若XY和XZ在R上成立，则XYZ在R上也成立 伪传递律（Pseudotransitivity rule） 若XY和YWZ在R上成立，则XWZ在R上也成立 分解律（Decomposition rule） 若XY和ZY在R上成立，则XZ在R上也成立 复合律（Composition） 若XY和WZ在R上成立，则XWYZ在R上也成立,11,4.2.4 完全函数依赖与部分函数依赖,设有关系模式R(U)，U是属性全集，X和Y是U的子集： 如果XY

5、，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖，记作X Y。 如果XY，并且对于X的某个真子集X ，有XY，则称Y对X部分函数依赖，记作X Y。 在关系模式SCD中，因为SNo Score，且CNo Score，所以有：(SNo，CNo) Score。而SNoAge，所以(SNo，CNo) Age,f,p,f,f,p,12,4.2.5 传递函数依赖,设有关系模式R(U)，U是属性全集，X，Y，Z是U的子集 若XY，但Y X，而YZ（Y X，Z Y），则称Z对X传递函数依赖 ，记作：X Z 。 如果YX，则X Y，这时称Z对X直接函数依赖，而不是传递函数依赖。,t,函数依赖,

6、完全函数依赖,部分函数依赖,传递函数依赖,13,4.2.6 属性集的闭包及其算法,X +=属性A|XA在F +中 定理4.3 XY能用函数依赖推理规则推出的充分必要条件是Y X +中 算法4.1 result=X do if F中有某个函数依赖YZ满足Y result then result=result Z while (result有所改变);,14,4.2.7 候选键的求解理论和算法,关键码的定义 如果XU在R上成立（即XU在F +中），那么称X是R的一个超键。 如果XU在R上成立，但对X的任一真子集X都有XU不成立（即XU不在F+中，或者X U），那么称X是R上的一个候选键。 快速求解

7、候选键的一个充分条件 对于给定的关系模式R(A1，An)和函数依赖集F，可将其属性分为以下四类：,f,L类,R类,N类,LR类,15,定理4.4 对于给定的关系模式R及其函数依赖集F （1）若X（XR）是L类属性，则X必为R的任一候选键的成员。 （2）若X（XR）是L类属性，且X +包含了R的全部属性，则X必为R的惟一候选键。 （3）若X（XR）是R类属性，则X不在任何候选键中。 （4）若X（XR）是N类属性，则X包含在R的任一候选键中。 （5）若X（XR）是R的N类和L类属性组成的属性集，且X +包含了R的全部属性，则X是R的惟一候选键。,16,多属性函数依赖集候选键的求解算法 （1）属性分

8、类（L、R、N和LR） （2）若X +包含了R的全部属性，转（5）；否则，转（3）。 （3）在Y中取一个属性A，求(XA) +，若它包含了R的全部属性，则转（4）；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。 （4）如果已找出所有候选键，则转（5）；否则在Y中依次取两个、三个、，求它们的属性集的闭包，直到其闭包包含R的全部属性。 （5）停止，输出结果。,令X代表L和N类，Y代表LR类,17,4.2.8 函数依赖推理规则的完备性,定理4.5 函数依赖推理规则A1，A2，A3是完备的 （1）证明F中每个函数依赖VW在r上成立。 （2）证明XY在关系r上不成立。 综合（1）和（2）可知

9、，只要XY不能用推理规则推出，那么F就不逻辑蕴涵XY，也就是推理规则是完备的。,从函数依赖集F使用推理规则推出的函数依赖必定在F +中,F +中的函数依赖都能从F集使用推理规则集推出,正确性：,完备性：,18,4.2.9 函数依赖集的等价、覆盖和最小函数依赖集,等价定义4.8 关系模式R(U)的两个函数依赖集F和G，如果满足F += G + ，则称F和G是等价的函数依赖集。记作：FG。如果F和G等价，就说F覆盖G，或G覆盖F。 无关定义4.9 设F是属性集U上的函数依赖集，XY是F中的函数依赖。函数依赖中无关属性： （1）如果AX，且F逻辑蕴涵(F-XY) (X-A) Y，则称属性A是XY左部

10、的无关属性。 （2）如果AX，且(F-XY) X(Y-A)逻辑蕴涵F，则称属性A是XY右部的无关属性。 （3）如果XY的左右两边的属性都是无关属性，则函数依赖XY称为无关函数依赖。,19,定义4.10 设F是属性集U上的函数依赖集。如果Fmin是F的一个最小函数依赖集，那么Fmin应满足下列四个条件： （1）Fmin+=F +； （2）每个函数依赖的右边都是单属性； （3）Fmin中没有冗余的函数依赖（即在Fmin中不存在这样的函数依赖XY，使得Fmin与Fmin-XY等价），即减少任何一个函数依赖都将与原来的F不等价； （4）每个函数依赖的左边没有冗余的属性（即Fmin中不存在这样的函数依赖

11、XY，X有真子集W使得Fmin-XY WY与Fmin等价），减少任何一个函数依赖左部的属性后，都将与原来的F不等价。,20,算法4.3 计算函数依赖集F的最小函数依赖集G （1）对F中的任一函数依赖XY，如果Y=Y1,Y2,，Yk（k2）多于一个属性，就用分解律，分解为XY1，XY2，XYk，替换XY，得到一个与F等价的函数依赖集G，G中每个函数依赖的右边均为单属性。 （2）去掉G中各函数依赖左部多余的属性。 （3）在G中消除冗余的函数依赖。,21,4.3 关系模式的分解*,4.3.1 模式分解问题 定义4.11 设有关系模式R(U)，R=R1R2Rk，=R1，R2，Rk。这里称为R的一个分解

12、，也称为数据库模式。,泛关系模式,泛关系,数据库模式,数据库实例,R,r,=R1，R2，Rk,=,模式分解示意图,衡量关系模式的分解是否可取,分解是否具有无损连接 分解是否保持了函数依赖,22,4.3.2 无损连接分解,定义4.12 设有R，F是R上的函数依赖集，=R1，R2，Rk。如果对R中满足F的每一个关系r，有r =R1(r)R2(r)Rk(r),那么就称分解相对于F是“无损连接分解” ；否则称为“损失分解”。 定理4.6 设=R1，R2，Rk是关系模式R的一个分解，r是R的任一关系，ri=Ri(r)（1ik）,那么有下列性质： （1）r m(r)； （2）若s=m(r)，则Ri(s)=

13、ri； （3）m(m(r)=m(r)，这个性质称为幂等性。,23,4.3.3 无损分解的测试算法,（1）构造一个k行n列的表格R，表中每一列对应一个属性Aj（1jn），每一行对应一个模式Ri（1ik）。如果Aj在Ri中，则在表中的第i行第j列处填上符号aj，否则填上bij。 （2）把表格看成模式R的一个关系，根据F中的每个函数依赖，在表中寻找X分量上相等的行，分别对Y分量上的每一列做修改： 如果列中有一个是aj，那么这一列上（X相同的行）的元素都改成aj； 如果列中没有aj，那么这一列上（X相同的行）的元素都改成bij（下标ij取i最小的那个）。 对F中所有的函数依赖，反复地执行上述的修改操作

14、，一直到表格不能再修改为止（这个过程称为“追踪” 过程）。 （3）若修改到最后，表中有一行全为a，即a1a2an，那么称相对于F是无损连接分解。,24,例4-11 设有关系模式R(A，B，C，D)，R分解成=AB，BC，CD，如果R上成立的函数依赖集F=BA，CD，那么相对于F是否为无损连接分解？,BA,a1,CD,a4,修改后的表格中的第二行为a1a2a3a4， 因此，相对于F是无损连接分解 。,25,定理4.7 设=R1，R2是关系模式R的一个分解，F是R上成立的函数依赖集，那么分解相对于F是无损分解的充分必要条件是： (R1R2)(R1-R2)或(R1R2)(R2-R1) 当模式R分解成

15、两个模式R1和R2时，若两个模式的公共属性（除外）能够函数决定R1（或R2）中的其他属性，这样的分解具有无损连接性。,26,4.3.4 保持函数依赖的分解,定义4.13 设有关系模式R(U)，F是R(U)上的函数依赖集，Z是属性集U上的一个子集，=R1，R2，Rk是R的一个分解。 F在Z上的一个投影用Z(F)表示：Z(F)=XY | XYF +XYZ； F在Ri上的一个投影用Ri(F)表示：=R1(r)R2(r)Rk(r)； 如果有F +=( )+，则称是保持函数依赖集F的分解。,一个无损连接分解不一定是保持函数依赖的,一个保持函数依赖的分解也不一定是无损连接的,27,4.4 关系模式的范式,

16、各种范式之间的关系,28,4.4.1 第一范式,定义4.14 如果关系模式R所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，简称1NF，记作R1NF。 1NF是关系模式应具备的最起码的条件。 第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。 如关系模式SCD属于1NF，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖 。 克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行转换。,29,4.4.2 第二范式,第二范式的定义 如果关系模式R1NF，且每个非主属性都完全函数依赖于R的主关系键，则称R属于第二范式，简称2NF，记作R2NF 。 如：关系模式TCS（T，C，S） 关系键 （T，C，S） ；主属性 T、C、S 不存在非主属性对主关系键的部分函数依赖，因此属于2NF。,从1NF关系中消除非