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

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中的样本数据,6,5.1 关系规范化的必要性,该关系模式存在四个主要问题：,（1）数据冗余度大,浪费空间，产生数据的不一致性,（2）插入异常,（3）删除异常,（4）更新异常,7,5.1 关系规范化的必要性,解决方法：,关系分解，实现信息的某种程度上的分离,S=Sno,Sname,SdeptD=Sdept,MnameSC=Sno,Cname,Score,解决问题，说明是一个好的关系数据库模式。,P113,8,5.1 关系规范化的必要性,思考：为什么会产生上述问题？,与数据间的依赖有关,关于分离度,高,低,：查询效率低,：会产生四个问题,9,5.1 关系规范化的必要性,2.规范化理论研究的内容,（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）多值依赖（Multivalued 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,CName,Score),U=SNo,SName,SDept,MName,SLoc,CName,Score,根据学号可以确定学生的姓名；,一个系有若干学生，但一个学生只属于一个系；,一个系只有一名主任；,根据学生所在的系可以确定学生的住处；,一个学生可以选修多门课程，每门课程有若干学生选修；,每个学生所学的每门课程都有一个成绩。,根据如下描述写出依赖关系：,SNoSName,SNoSDept,SDeptMName,SDeptSLoc,(SNo,CName)Score,F=SNoSName,SNoSDept,SDeptMName,SDeptSLoc,(SNo,CName)Score,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,CName),平凡函数依赖,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)中的属性或属性组。若,则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所逻辑蕴含的所有的函数依赖的集合，记作。,例：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类 在的函数依赖左右两边均未出现的属性；,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,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的所有候选键。,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,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,回顾,规范化理论研究的内容,（1）函数依赖,核心,模式分解和设计的基础,（2）范式,模式分解的标准,（3）模式设计,32,5.3 范式,范式定义 第一范式（1NF）第二范式（2NF）第三范式（3NF）改进的3NF（BCNF）多值依赖与第四范式（4NF）,33,5.3.1 范式的定义,范式（NF）是符合某一种级别的关系模式的集合。,满足不同程度要求的为不同范式。,范式的概念最早由提出：,1971年 1NF，2NF，3NF,1974年 BCNF,1976年 4NF，5NF,5NF,3NF,BCNF,2NF,4NF,1NF,若R(U,F)符合x范式的要求，则称R为x范式，记作：RxNF,34,5.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,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,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,一个低一级的范式的关系模式，通过模式分解转换为若干个高一级范式的关系模式集合，这种分解过程叫做关系模式的规范化,39,5.4.1 关系模式规范化的目的和基本思想,规范化的目的：,基本思想：,解决关系模式中存在的数据冗余、插入和删除异常、更新异常的问题,逐步消除数据依赖中不合适的部分，使模式中的各个关系模式达到某种程度的“分离”，即采用“一事一地”的模式设计原则。,40,5.4.2 关系模式规范化的步骤,1NF,2NF,3NF,BCNF,消除非主属性对键的部分函数依赖,消除非主属性对键的传递函数依赖,消除主属性对键的部分和传递函数依赖,基本原则：,由低到高，逐步规范,权衡利弊，适可而止,通常以满足第三范式为基本要求。,41,范式的判定,【练习1】：设有关系模式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,非主属性：,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,R1NF,主属性：,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,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被分解为若干个关系模式,其中,，且不存在,是F在 上的投影，如果R与,自然连接的结果相等，则称关系模式R的分解具有无损连接性。,49,5.4.3 关系模式规范化的要求,例如，对于关系模式SL2(SNo,SDept,SLoc),SNo,SDept,SLoc,02001 电子系 10-20102002 电子系 10-20102003 计科系 11-30502004 数学系 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-20102002 电子系 10-20102003 计科系 11-30502004 数学系 12-823,ND2 DL2,51,5.4.3 关系模式规范化的要求,关系模式R被分解为,中有如下函数依赖中的一个，则此分解为无损连接分解：,，若,（1）,（2）,即R分解成 和 后，如果它们的公共属性集是 或者 的主键，那么分解是无损的。,52,5.4.3 关系模式规范化的要求,2.依赖保持的分解,定义5.22 函数依赖保持性（Preserve Dependency）设关系模式R的一个分解为,其中,，且不存在,是F在 上的投影，,若,则称关系模式R的分解具有函数依赖保持性。,53,5.4.3 关系模式规范化的要求,如果一个分解具有无损分解，则它能够保证不丢失信息；,如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。,具有无损连接性的分解不一定保持函数依赖，保持函 数依赖的分解不一定具有无损连接性。,54,习题,1.设工厂里有一个记录职工每天日产量的关系模式：R（ENo，Date，Output，PNo，PDirector）。其中，Eno表示职工号，Date表示日期，Output表示职工日产量，PNo表示车间号，Pdirector表示车间主任 如果规定：每个职工每天只有一个日产量；每个职工只能隶属于一个车间，一个车间有多个职工；每个车间只有一个车间主任。（1）根据上述规定，写出关系模式R的基本函数依赖；（2）试写出关系模式R的候选键，并写出求解过程；（3）试问关系模式R最高已经达到第几范式？为什么？（4）若不满足第三范式，请将其分解使其满足三范式。,55,习题,2.现有关系模式如下：R（Sno，Cno，Grade，Tname，Taddr）其属性分别表示学生的学号、选修课程的编号、成绩、任课教师名、教师地址等意义。现规定：每个学生每学一门课程只有一个成绩；每门课可以有多位教师任教，一位教师只能教一门课；每位教师只有一个地址，一个地址可以居住多位教师（此外不允许教师同名同姓）。1、根据上述规定，写出关系模式R的基本函数依赖；2、试写出关系模式R的候选键，并写出求解过程；3、试问关系模式R最高已经达到第几范式？为什么？,