关系数据库理论.ppt

《关系数据库理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库理论.ppt（38页珍藏版）》请在三一办公上搜索。

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,该表出现的问题,数据冗余 插入异常 删除异常 更新异常,根本原因：属性间存在着数据依赖关系,包罗万象,6,一

2、个好的关系模式应该具备以下四个条件：（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 设关系模式R(U,F),U为属性全集,F为函数依赖集,X和Y为U的子集,对于R(U)上 的任何关系r,X每一个具体值,Y都有唯一值与之对应,称X函数决定Y,或Y函数依赖于X,记作X Y.SNo函数决定（SN，Age，Dept）（SN，A

3、ge，Dept）函数依赖于SNo,SCD(SNo，SN，Age，Dept，MN，CNo，Score),SNo,一个学生,SN，Age，Dept,惟一确定,惟一确定,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、推理规则,Armstrong公理自反律：如果Y X U，则XY在R上成立 增广律：若XY在R上成立，且Z U，则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和Z Y在R上成立，则XZ在R上也成立复合律（Composition）若XY和WZ在R上成立，则XWYZ在R上也成立,Armstrong公理简表,

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

6、数依赖，记作：X Z。如果YX，则X Y，这时称Z对X直接函数依赖，而不是传递函数依赖。,t,函数依赖,完全函数依赖,部分函数依赖,传递函数依赖,14,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有所改变);,15,4.2.7 候选键的求解理论和算法,键码的定义 如果XU在R上成立（即XU在F+中），那么称X是R的一个超键。如果XU在R上成立，但对X的任一真子

7、集X都有XU不成立（即XU不在F+中，或者X U），那么称X是R上的一个候选键。快速求解候选键的一个充分条件 对于给定的关系模式R(A1，An)和函数依赖集F，可将其属性分为以下四类：,f,L类,R类,N类,LR类,16,定理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的全部属性，则

8、X是R的惟一候选键。,17,多属性函数依赖集候选键的求解算法（1）属性分类（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类,18,4.2.8 函数依赖推理规则的完备性,定理4.5 函数依赖推理规则A1，A2，A3(阿姆斯壮)是完备的 证明略.,从函数依赖集F使用

9、推理规则推出的函数依赖必定在F+中,F+中的函数依赖都能从F集使用推理规则集推出,正确性：,完备性：,19,4.2.9 函数依赖集的等价、覆盖和最小函数依赖集,等价定义4.8 关系模式R(U)的两个函数依赖集F和G，如果满足F+=G+，则称F和G是等价的函数依赖集。记作：FG。如果F和G等价，就说F覆盖G，或G覆盖F。,形式不同的两个函数依赖集可能在逻辑上等价.,20,定义4.10 设F是属性集U上的函数依赖集。如果Fmin是F的一个最小函数依赖集，那么Fmin应满足下列四个条件：（1）Fmin+=F+；（2）每个函数依赖的右边都是单属性；（3）Fmin中没有冗余的函数依赖（即在Fmin中不存

10、在这样的函数依赖XY，使得Fmin与Fmin-XY等价），即减少任何一个函数依赖都将与原来的F不等价；（4）每个函数依赖的左边没有冗余的属性（即Fmin中不存在这样的函数依赖XY，X有真子集W使得Fmin-XY WY与Fmin等价），减少任何一个函数依赖左部的属性后，都将与原来的F不等价。,21,算法4.3 计算函数依赖集F的最小函数依赖集G（1）对F中的任一函数依赖XY，如果Y=Y1,Y2,，Yk（k2）多于一个属性，就用分解律，分解为XY1，XY2，XYk，替换XY，得到一个与F等价的函数依赖集G，G中每个函数依赖的右边均为单属性。（2）去掉G中各函数依赖左部多余的属性。（3）在G中消除冗

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

12、依赖于R的主关系键，则称R属于第二范式，简称2NF，记作R2NF。如：关系模式TCS（T，C，S）关系键（T，C，S）；主属性 T、C、S 不存在非主属性对主关系键的部分函数依赖，因此属于2NF。,从1NF关系中消除非主属性对主关系键的部分函数依赖，则可得到2NF,如果R的关系键为单属性，或R的全体属性均为主属性，则R2NF,25,2NF规范化 2NF规范化是指把1NF关系模式通过投影分解，转换成2NF关系模式的集合。例4-15 将SCD(SNo，SN，Age，Dept，MN，CNo，Score)规范为2NF。,Score,SNo,CNo,Dept,MN,SN,Age,分解后:,SNo,Dep

13、t,MN,SN,Age,Score,SNo,CNo,SC(SNo，CNo，Score),SD(SNo，SN，Age，Dept，MN),27,2NF的缺点,数据冗余,插入异常,删除异常,更新异常,每个系名和系主任的名字存储的次数等于该系的学生人数,当一个新系没有招生时，有关该系的信息无法插入,某系学生全部毕业而没有招生时，删除全部学生的记录也随之删除了该系的有关信息,更换系主任时，仍需改动较多的学生记录,28,4.4.3 第三范式,第三范式的定义 如果关系模式R2NF，且每个非主属性都不传递函数依赖于R的主关系键，则称R属于第三范式，简称3NF，记作R3NF。如：SC(SNo，CNo，Score

14、)函数依赖为(SNo，CNo)Score，非主属性Score不传递函数依赖于主关系键（SNo，CNo），因此，SC3NF。又如：SD(SNo，SN，Age，Dept，MN)SNoDep和DeptMN SNo MN 非主属性MN与主关系键SNo间存在着传递函数依赖，所以SD 3NF。,主关系键,非主属性,t,非主属性,主关系键,29,例4-18 将SD(SNo，SN，Age，Dept，MN)规范到3NF。,SNo,Dept,MN,SN,Age,30,数据冗余降低了,不存在删除异常,不存在更新异常,不存在插入异常,分解后:,S(SNo，SN，Age，Dept),D(Dept，MN),SNo,Dep

15、t,SN,Age,Dept,MN,练习:设计关于供应商供应零件的数据库，要求达到3NF最初的设计：R(Sno,Sname,City,State,Pno,Pname,Color,Weight,QTY)函数依赖：Sno Sname,Sno State,Sno City,City State,Pno Pname,Pno Color,Pno Weight,(Sno,Pno)QTY主码：(Sno,Pno)可见，其中有部分依赖，还有传递依赖，该模式仅为1NF。,第1步分解，消除部分依赖，得到：R1(Sno,Pno,QTY)，(Sno,Pno)为码R2(Sno,Sname,City,State)，Sno为码

16、R3(Pno,Pname,Color,Weight)，Pno为码 其中，R1和R3都已达到3NF，但R2还存在传递依赖，仅仅是2NF第2步分解，消除R2中的传递依赖，得到：R2-1(Sno,Sname,City)，Sno为码R2-2(City,State)，City为码这样，R1,R2-1,R2-2和R3就是达到3NF的关系模式。,33,4.4.4 BC范式,BC范式的定义 如果关系模式R1NF，且所有的函数依赖XY（Y X），决定因素X都包含了R的一个候选键，则称R属于BC范式，记作RBCNF。BCNF具有如下性质：如果RBCNF，则R也是3NF。如果R3NF，则R不一定是BCNF。例4-1

17、9 设有关系模式SNC（SNo，SN，CNo，Score）SNo SN。存在着主属性对键的部分函数依赖：（SNo，CNo）SN，（SN，CNo）SNo，所以SNC不是BCNF。,无部分函数依赖和传递函数依赖，SNC3NF,34,BCNF规范化 例4-20 将SNC(SNo，SN，CNo，Score)规范到BCNF。候选键：（SNo，CNo）和（SN，CNo）函数依赖：,F=SNoSN，SNSNo，(SNo，CNo)Score，(SN，CNo)Score,分解后:S1(SNo，SN)，S2(SNo，CNo，Score),35,例4-21 设有关系模式TCS(T，C，S)候选键：（S，C）和（S，

18、T）函数依赖是：F=(S，C)T，(S，T)C，TC,消除了函数依赖(S，T)C，STBCNF，TCBCNF,分解:TC(T，C)，ST(S，T),C,S,C,T,S,T,36,4.5 关系模式的规范化,一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的规范化。关系模式规范化的目的和原则规范化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。规范化的基本原则就是遵循“一事一地”的原则。,37,4.5.2 关系模式规范化的步骤,规范化过程,第4章需要掌握的基本概念,函数依赖平凡的函数依赖与非平凡的函数依赖函数依赖集的闭包属性集的闭包超键/侯选键的定义主属性/非主属性定义部分函数依赖与完全函数依赖传递函数依赖第一范式第二范式第三范式BC范式,