关系数据库规范化理论.ppt

1、1,第五章 关系数据库规范化理论,2,5.1 关系规范化的必要性 5.2 函数依赖 5.3 范式 5.4 关系模式的规范化,第五章 关系数据库规范化理论,3,5.1 关系规范化的必要性,每个关系由哪些属性组成？,1.关系数据库逻辑设计问题,构造几个关系？,关系数据库,关系,属性,4,5.1 关系规范化的必要性,例：教学管理系统，需要存储下列信息 学号,姓名,系名,系主任名,课程名,成绩 Sno, Sname, Sdept, Mname, Cname, Score,设计一个关系模式：SLC=Sno,Sname,Sdept,Mname,Cname,Score,5,5.1 关系规范化的必要性,SLC

2、中的样本数据,6,5.1 关系规范化的必要性,该关系模式存在四个主要问题：,（1）数据冗余度大,浪费空间，产生数据的不一致性,（2）插入异常,（3）删除异常,（4）更新异常,7,5.1 关系规范化的必要性,解决方法：,关系分解，实现信息的某种程度上的分离,S = Sno,Sname,Sdept D = Sdept,Mname SC= Sno,Cname,Score,解决问题，说明是一个好的关系数据库模式。,P113,8,5.1 关系规范化的必要性,思考：为什么会产生上述问题？,与数据间的依赖有关,关于分离度,高,低,：查询效率低,：会产生四个问题,9,5.1 关系规范化的必要性,2.规范化理论

3、研究的内容,（1）函数依赖,核心,模式分解和设计的基础,（2）范式,模式分解的标准,（3）模式设计,10,数据依赖 函数依赖 键的形式化定义 候选键的求解理论和算法,5.2 函数依赖,11,5.2.1 数据依赖,关系模式回顾,R（U, D, DOM, F）,F：属性U上数据的依赖关系集合,记作：R(U，F),12,5.2.1 数据依赖,定义5.1 数据依赖 是通过一个关系中属性间值的相等与否 体现出来的数据间的相互关系，是现实世界属性间 相互联系的抽象，是数据内在的性质，是语义的体现。,数据依赖共有三种：,（1）函数依赖（Functional Dependency，FD）,（2）多值依赖（Mu

4、ltivalued Dependency，MVD）,（3）连接依赖（Join Dependency，JD）,13,5.2.2 函数依赖,定义5.2 函数依赖 设R(U)是一个关系模式，U是R的属性集合。 X,Y为U的子集。 如果R(U)的所有关系r都存在着： 对于X的每一个值，Y都有唯一值与之对应， 则称X函数决定Y,或Y函数依赖于X。,记作XY。其中X叫作决定属性集，Y叫作被决定属性集。,若Y不函数依赖于X，记作：XY。,若XY， YX，记作：X Y,注：函数依赖是属性间的一种联系,14,5.2.2 函数依赖,设有关系模式SLC1(SNo,SName,SDept,MName,SLoc,CNa

5、me,Score),U = SNo,SName,SDept,MName,SLoc,CName,Score, 根据学号可以确定学生的姓名；, 一个系有若干学生，但一个学生只属于一个系；, 一个系只有一名主任；, 根据学生所在的系可以确定学生的住处；, 一个学生可以选修多门课程，每门课程有若干学生选修；, 每个学生所学的每门课程都有一个成绩。,根据如下描述写出依赖关系：,SNoSName,SNoSDept,SDeptMName,SDeptSLoc,(SNo,CName)Score,F=SNoSName, SNoSDept, SDeptMName, SDeptSLoc,(SNo,CName)Scor

6、e,15,5.2.2 函数依赖,注意：P115,（1）属性间的函数依赖 指R的一切关系子集都要满足定义中的限定；,（2）函数依赖 是语义范畴的概念；,（3）数据库设计者可以对现实世界做强制的规定。,16,5.2.2 函数依赖,定义5.3 平凡函数依赖与非平凡函数依赖 在关系模式R(U,F)中，对于U的子集X、Y，,如果XY,但Y X，则称XY是非平凡函数依赖；,如果Y X，则称XY是平凡函数依赖。,若不特别声明，本书中讨论的是非平凡函数依赖。,例：（SNo,CName）Score,Score (SNo,CName),非平凡函数依赖,（SNo,CName）CName,SName (SNo,CNa

7、me),平凡函数依赖,17,5.2.2 函数依赖,定义5.4 完全/部分函数依赖 在R(U,F)中,如果XY，对于X的任一真子集X，都有X Y,则称Y对X完全函数依赖,记为,否则,称Y对X是部分函数依赖,记作,例：（SNo,CName）SName,SNoSName,（SNo,CName）Score,18,5.2.2 函数依赖,定义5.5 传递函数依赖 在R(U,F)中,如果XY，YZ,且Y X,Z Y,YX,则称Z对X是传递函数依赖,记为,若有YX,则X Y,那么,例： SNoSDept SDeptMName,19,5.2.3 键的形式化定义,定义5.6 设K是关系模式R(U,F)中的属性或属

8、性组。若,则K为R的候选键（Candidate Key），简称为键。,定义5.7 主键,定义5.8 主属性,定义5.9 非主属性,定义5.10 单键,定义5.11 全键,例： （演奏者，作品，听众）,定义5.12 外键,R（A，B，C，F）,S（ Ks ，D，E）,R的外键,参照关系,被参照关系,20,5.2.4 候选键的求解理论和算法,思考：设有关系模式R(A,B,C,D)其函数依赖集 F=DB,BD,ADB,ACD,求R的所有候选键。,21,5.2.4 候选键的求解理论和算法,定义5.13 闭包(Closure) 对于给定的关系模式R(U,F)， F的闭包是由F所逻辑蕴含的所有的函数依赖的

9、集合， 记作 。,例：F=DB,BD,ADB,ACD,= ,A,C,D,B,=,D,B,注意：若K为候选键，则,22,5.2.4 候选键的求解理论和算法,思考：设有关系模式R(A,B,C,D)其函数依赖集 F=DB,BD,ADB,ACD,求R的所有候选键。,=,D,B,= B, D ,= A ,= C ,= A, B, D ,= A, C, D, B ,= A, D, B , CK：AC,23,5.2.4 候选键的求解理论和算法,对于给定的关系模式R(U)和函数依赖集F，可将其属性分为4类：, L类 仅出现在的函数依赖左部的属性；, R类 仅出现在的函数依赖右部的属性；, N类 在的函数依赖左

10、右两边均未出现的属性；, LR类 在的函数依赖左右两边均出现的属性。,24,5.2.4 候选键的求解理论和算法,定理5.1 对于给定的关系模式R(U)及其函数依赖集F， 若X(XR)是L类属性，则X必为R的任一侯选键的成员。,推论5.1 对于给定的关系模式R(U)及其函数依赖集F， 若X(XR)是L类属性，且X+包含了R的全部属性， 则X必为R的的唯一侯选键 。,25,5.2.4 候选键的求解理论和算法,【例5.1】：设有关系模式R(A,B,C,D)其函数依赖集 F=DB,BD,ADB,ACD,求R的所有候选键。,L：,解：,A, C,R：,none,N：,none,LR：,B, D,= A,

11、 C, D, B , CK：AC,26,5.2.4 候选键的求解理论和算法,定理5.2 对于给定的关系模式R(U)及其函数依赖集F， 若X(XR)是R类属性，则X不在任何侯选键中。,定理5.3 对于给定的关系模式R(U)及其函数依赖集F， 若X(XR)是N类属性，则X必为R的任一侯选键的成员。,推论5.2 对于给定的关系模式R(U)及其函数依赖集F， 若X是N类和L类组成的属性集，且X+包含了R的全部属性， 则X必为R的的唯一侯选键 。,27,5.2.4 候选键的求解理论和算法,【例5.2】：设有关系模式R(A,B,C,D,E,P)其函数依赖集 F=AD,ED,DB,BCD,DCA, 求R的所

12、有候选键。,L：,解：,C, E,R：,none,N：,P,LR：,A, B, D, CK：CEP,= ,C,E,P,D,B,= U,A,28,5.2.4 候选键的求解理论和算法,【练习1】：设有关系模式R(A,B,C,D,E,P)其函数依赖集 F=AB,CP,EA,CED,求R的所有候选键。,L：,解：,C, E,R：,P, D, B,N：,none,LR：,A, CK：CE,= ,C,E,P,A,B,= U,D,29,5.2.4 候选键的求解理论和算法,【练习2】：设有关系模式R(A,B,C)其函数依赖集 F=ABC,CA,求R的所有候选键。,L：,解：,B,R：,none,N：,none

13、,LR：,A, C, CK：AB, BC,=,B, U,= ,A,B,C,= U,= ,B,C,A,= U,30,5.2.4 候选键的求解理论和算法,【练习3】：设有关系模式R(A,B,C,D,E)其函数依赖集 F=ABC,CDE,BD,EA,求R的所有候选键。,L：,解：,none,N：,none,LR：,A, B, C, D, E,= ,B,R：,none,= ,A,B,C,= U,D,E,D,= C ,= D ,= ,E,A,B,= U,C,D,= ,B,C,D,= U,E,A,= ,B,D,= ,C,D,E,A,B,= U, CK：A, E, BC, CD,31,回顾,规范化理论研究的

14、内容,（1）函数依赖,核心,模式分解和设计的基础,（2）范式,模式分解的标准,（3）模式设计,32,5.3 范式,范式定义 第一范式（1NF） 第二范式（2NF） 第三范式（3NF） 改进的3NF（BCNF） 多值依赖与第四范式（4NF）,33,5.3.1 范式的定义,范式（NF）是符合某一种级别的关系模式的集合。,满足不同程度要求的为不同范式。,范式的概念最早由E.F.Codd提出：,1971年 1NF，2NF，3NF,1974年 BCNF,1976年 4NF，5NF,5NF,3NF,BCNF,2NF,4NF,1NF,若R(U,F)符合x范式的要求，则称R为x范式，记作：RxNF,34,5.

15、3.2 第一范式（1NF）,定义5.14 第一范式（1NF） 如果一个关系模式R(U,F)的所有属性都是不可分的 基本数据项，则R1NF.,例：SLC2(SNo,SDept,SLoc,CName,Score)1NF,满足1NF的数据库模模式不一定是一个好的关系模式；,不满足1NF的数据库模式不能称为关系数据库模式。,35,5.3.3 第二范式（2NF）,定义5.15 第二范式（2NF） 满足第一范式的关系模式R(U,F)，如果所有的 非主属性都完全依赖于键，则称R属于第二范式, 记为R(U,F)2NF.,例：SLC2(SNo,SDept,SLoc,CName,Score)1NF,SC2(SNo

16、,CName,Score),2NF,SL2(SNo,SDept,SLoc),2NF,(SNo,CName)Score,SnoScore,CnameScore,36,5.3.4 第三范式（3NF）,定义5.16 第三范式（3NF）若R(U,F)2NF， 且它的任何一个非主属性都不传递依赖于键， 则称关系R属于第三范式,记为R(U,F)3NF。,例：SL2(SNo,SDept,SLoc)2NF,SD2(SNo,SDept),3NF,DL2(SDept,SLoc),3NF,在关系数据库模型设计中目前一般采用第三范式。,37,5.3.5 BCNF,定义5.17 改进的3NF-BCNF 设关系模式R(U

17、,F)1NF， 若XY且Y X时X必包含键，则称R(U,F)BCNF。,一个满足BCNF的关系模式必然有：,R中所有非主属性对每一个键都是完全函数依赖；,R中所有主属性对每一个不包含它的键，都是完全函数依赖；,R中没有任何属性完全函数依赖于非键的任何一组属性。,38,5.4 关系模式的规范化,SLC2(SNo,SDept,SLoc,CName,Score)1NF,SC2(SNo,CName,Score)2NF,SL2(SNo,SDept,SLoc)2NF,SD2(SNo,SDept)3NF,DL2(SDept,SLoc)3NF,一个低一级的范式的关系模式， 通过模式分解转换为若干个高一级范式的

18、关系模式集合， 这种分解过程叫做关系模式的规范化,39,5.4.1 关系模式规范化的目的和基本思想,规范化的目的：,基本思想：,解决关系模式中存在的数据冗余、插入和删除异常、更新异常的问题,逐步消除数据依赖中不合适的部分，使模式中的各个关系模式达到某种程度的“分离”，即采用“一事一地”的模式设计原则。,40,5.4.2 关系模式规范化的步骤,1NF,2NF,3NF,BCNF,消除非主属性对键的部分函数依赖,消除非主属性对键的传递函数依赖,消除主属性对键的部分和传递函数依赖,基本原则：,由低到高，逐步规范,权衡利弊，适可而止,通常以满足第三范式为基本要求。,41,范式的判定,【练习1】：设有关系

19、模式R(A,B,C,D,E,P)其函数依赖集 F=AB,CP,EA,CED,判断R属于第几范式。,L：,解：,C, E,R：,P, D,N：,none,LR：,A, CK：CE,= ,C,E,P,A,B,= U,D,R1NF,主属性：,C, E,非主属性：,A, B, D, P,又 (C,E)P,CP, R2NF, R1NF,42,范式的判定,【练习2】：设有关系模式R(A,B,C,D)其函数依赖集 F=AC,CA,BA,DC,判断R属于第几范式。,L：,解：,B, D,R：,none,N：,none,LR：,A, C, CK: BD,= ,B,D,A,C,= U,R1NF,主属性：,B, D

20、,非主属性：,A, C,又 (B,D)A,BA, R2NF, R1NF,43,范式的判定,【练习3】：设有关系模式R(A,B,C,D)其函数依赖集 F=BC,CD,DA,判断R属于第几范式。,L：,解：,B,R：,A,N：,none,LR：,C, D, CK: B,= ,B,C,D,A,= U,R1NF,主属性：,B,非主属性：,A, C, D, R2NF,又因为候选键只有一个属性， 所以所有非主属性都完全依赖于键 R2NF,又 BC CD, R3NF,44,范式的判定,【练习4】：设有关系模式R(A,B,C)其函数依赖集 F=ABC,CA,判断R属于第几范式。,解：,CK: AB, BC,R

21、1NF,主属性：,A, B, C,非主属性：,none, R3NF,又因为所有属性都是主属性,又,RBCNF, R3NF,45,范式的判定,【练习5】：设有关系模式R(A,B,C,D,E)其函数依赖集 F=ABC,BD, CE, ECB, ACB 判断R属于第几范式。,L：,解：,A,R：,D,N：,none,LR：,B, C, E,= ,A,= U,= ,A,B,C,D,E,= U,= ,A,C,E,B,D,= U,= ,A,E,= U, CK: AB, AC,R1NF,主属性：,A, B, C,非主属性：D, E,又 (A,B)D,BD, R2NF, R1NF,46,复习,1NF,2NF,

22、3NF,BCNF,消除非主属性对键的部分函数依赖,消除非主属性对键的传递函数依赖,消除主属性对键的部分和传递函数依赖,基本原则：,由低到高，逐步规范,权衡利弊，适可而止,通常以满足第三范式为基本要求。,47,5.4.3 关系模式规范化的要求,定义5.20 关系模式R的一个分解是指,其中,并且没有,1i, jn,是F在 上的投影。,等价的常用标准有三个：,（1）分解要具有无损连接性；,（2）分解要保持函数依赖；,（3）分解既要保持函数依赖又要具有无损连接性。,48,5.4.3 关系模式规范化的要求,1.无损连接分解,定义5.21 无损连接性（Lossless Join） 设关系模式R被分解为若干

23、个关系模式,其中,，且不存在,是F在 上的投影，如果R与,自然连接的结果相等，则称关系模式R的分解 具有无损连接性。,49,5.4.3 关系模式规范化的要求,例如，对于关系模式SL2(SNo,SDept,SLoc),SNo,SDept,SLoc,02001 电子系 10-201 02002 电子系 10-201 02003 计科系 11-305 02004 数学系 12-823,50,5.4.3 关系模式规范化的要求,例如，对于关系模式SL2(SNo,SDept,SLoc),SNo,SDept,02001 电子系 02002 电子系 02003 计科系 02004 数学系,SDept,电子系 10-201 计科系 11-305 数学系 12-823,SLoc,ND2,DL2,SNo,SDept,SLoc,02001 电子系 10-201 02002 电子系 10-201 02003 计科系 11-305 02004 数学系 12-823,ND2 DL2,51,5.4.3 关系模式规范化的要求,关系模式R被分解为,中有如下函数依赖中的一个，则此分解为无损连接分解：,，若,（1）,（2）,即R分解成 和 后，如果它们的公共属性集是 或者