《关系数据模式的规范化理论.ppt》由会员分享，可在线阅读，更多相关《关系数据模式的规范化理论.ppt（61页珍藏版）》请在三一办公上搜索。
1、第4章 关系数据模式的规范化理论,4.1 问题的提出4.2 函数依赖4.3 范式和规范化,什么是数据库设计?怎么设计？,现实世界数据/关系,机器世界,4.1 问题的提出,是不是从信息世界的模型中简单地转化为机器世界的数据就可以了呢?,实体,关系表,属性,数据项,4.1 问题的提出,4.1 问题的提出,如果要设计一个教学管理数据库，希望从数据库中得到学生学号(sno)、学生姓名(name)、性别(sex)、学生学习的课程号(cno)、课程名(cname)和该门课程的成绩(grade)。如何设计该关系模式？主码是什么?,(学号,姓名,性别,课程号,课程名,成绩)(SNO,NAME,SEX,CNO,
2、CNAME,GRADE),4.1 问题的提出,问题1：数据冗余,4.1 问题的提出,问题2：不一致性,4.1 问题的提出,问题3：插入异常,（S0010，李四，男，null，null，null）,4.1 问题的提出,问题4：删除异常（当某学号只有一条记录，并做删除操作时）,4.1 问题的提出,解决方案,S1（SNO，NAME，SEX）S2（CNO，CNAME）S3（SNO，CNO，GRADE）,4.2 函数依赖,定义1设R(U)是属性集U上的关系模式，X，Y是U的子集。若对于R(U)任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依
3、赖于X，记作X-Y,4.2 函数依赖,例子职工号-姓名S1:SNO-NAME;SNO-SEXS2:(SNO,CNO)-GRADES3:CNO-CNAME,4.2 函数依赖,定义2 设X-Y是一个函数依赖，若 则称X-Y是一个平凡函数依赖。,4.2 函数依赖,例子 在S2中有(SNO,CNO)-SNO(SNO,CNO)-CNO 所以这些都是平凡函数依赖关系(SNO,CNO)-GRADE 这个是非平凡函数依赖关系,4.2 函数依赖,定义3设X-Y是一个函数依赖，并且对于任何则称XY是一个完全函数依赖。即Y函数依赖于整个X，记,4.2 函数依赖,举例：在关系S(SNO,NAME,SEX,CNO,CN
4、AME,GRADE)中：(SNO,CNO)-GRADE但SNO-GRADE；(CNO)-GRADE都不成立所以(SNO,CNO)-GRADE是完全函数依赖关系。,4.2 函数依赖,定义4设X-Y是一个函数依赖,但不是完全函数依赖,则称X-Y是一个部分函数依赖,或称Y函数依赖于X的某个真子集,记,4.2 函数依赖,在关系S(SNO,NAME,SEX,CNO,CNAME,GRADE)中：(SNO,CNO)-NAME,而对于每个学生都有唯一的SNO值,所以SNO-NAME,而CNO-NAME,因此，(SNO,CNO)-NAME是部分函数依赖,4.2 函数依赖,设R(U)是一个关系模式,则称Z传递函数
5、依赖于X,记,4.2 函数依赖,例子：班级(班号,专业名,系名,人数,入学年份),班号-专业名,专业名-系名,班号-人数,班号-入学年份,班号-专业名,专业名-系名,4.2 函数依赖,函数依赖与属性关系 属性之间有3种关系,但并不是每一种关系中都存在函数依赖。,函数依赖与属性关系,设R(U)是属性集U上的关系模式,X,Y是U的子集:若X和Y之间是1:1关系,则存在函数依赖 X-Y,Y-X;若X和Y之间是1:n关系,则存在函数依赖 X-Y;若X和Y之间是m:n关系,则X,Y间不存在函数依赖.,函数依赖与属性关系,分析下列关系中各种函数的依赖关系:学生(学号,姓名,出生年月,系名,班号,宿舍区),
6、Armstrong公理,背景为了从一组函数依赖中求得逻辑蕴涵的函数依赖,例如已知函数依赖集F,要问是否逻辑蕴涵X-Y,就需要一套推理规则.,Armstrong公理,设A,B,C,D是给定关系模式R的属性集的任意子集,并把A和B的并集称为AB,则其推理规则可归结为3条:,自反律:如果,这是一个平凡函数依赖,增广律:如果,传递律:如果,Armstrong公理推论,自合规则:A-A,分解规则:A-BC,则A-B且 A-C,合并规则:A-B且 A-C,则A-BC,复合规则:A-B且 C-D成立,则AC-BD,4.2 函数依赖,4.2.6 闭包及其计算定义6：设F是关系模式R的一个函数依赖集，X，Y是R
7、的属性子集，如果从F中的函数依赖能够推出XY，则称F逻辑蕴涵XY。定义7：被F逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包，记为F+。,练习1：设有关系模式R(A,B,C,D,E)，F=AC,BC E,D C,E A，试求F的闭包F+。,4.2 函数依赖,定义8：设F是属性集U上的一组函数依赖，X U，则属性集X关于F的闭包X+定义为X+=A|AU且XA在F+中，即X=A|XAF+。,算法4.1 result=X do if F中有某个函数依赖YZ满足Y result then result=result Z while(result有所改变);,XF+算法:设i=0 令 X(0)=X 计
8、算 A=B|一切W X(i)且 W B F+令 X(i+1)=X(i)A 判断 X(i+1)=X(i)是否成立，成立，转，不成立，i=i+1，转 算法结束，XF+=X(i),4.2 函数依赖,随堂练习,练习1：设有关系模式R(A,B,C,D,E)，F=AB,C E,D AC，试求D关于F的闭包。,练习2：设有关系模式R(A,B,C,D,E)，F=ABC,BD,CE,EC,AC，试求BC关于F的闭包(BC)F+。,4.2 函数依赖,关键码的定义 如果XU在R上成立（即XU在F+中），那么称X是R的一个超键。如果XU在R上成立，但对X的任一真子集X都有XU不成立（即XU不在F+中，或者X U），那
9、么称X是R上的一个候选键。快速求解候选键的一个充分条件 对于给定的关系模式R(A1，An)和函数依赖集F，可将其属性分为以下四类：,f,L类,R类,N类,LR类,定理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的惟一候选键。,随堂练习,练习1：设有关系模式R(A,
10、B,C,D,E)，F=AB,CG,EA，CE D，求R的所有候选键。,练习2：设有关系模式R(A,B,C,D,E,P)，F=AD,ED,DB,BCD,DCA，求R的所有候选键。,练习3：设有关系模式R(A,B,C,D,E)，F=ABC,CDE,BD,EA，求R的所有候选键。,多属性函数依赖集候选键的求解算法（1）属性分类（L、R、N和LR）（2）若X+包含了R的全部属性，转（5）；否则，转（3）。（3）在Y中取一个属性A，求(XA)+，若它包含了R的全部属性，则转（4）；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。（4）如果已找出所有候选键，则转（5）；否则在Y中依次取两个、三个
11、、，求它们的属性集的闭包，直到其闭包包含R的全部属性。（5）停止，输出结果。,令X代表L和N类，Y代表LR类,随堂练习,设有关系模式R(A,B,C,D,E,G)，F=BGC,BDE,DGC,ADGBC,AGB,BD，试求R的所有候选键。,4.4 范式和规范化,要想设计一个好的关系,必须使关系满足一定的约束条件,此约束条件已经形成了规范,分成几个等级,一级比一级要求得严格。,4.4 范式和规范化,满足最低要求的关系称为第一范式,在此基础上又满足某条件,达到第二范式,如此类推,直到第五范式.,4.4 范式和规范化,一个较低范式关系,可以通过关系的无损分解转换为若干较高范式关系的集合,这一过程叫做关
12、系规范化.,4.4 范式和规范化,一般情况下,第一范式和第二范式的关系存在许多缺点,实际的关系数据库一般使用第三范式以上的关系.,4.4.1 范式,范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF),范式（续）,各种范式之间存在联系：某一关系模式R为第n范式，可简记为RnNF。,4.4 范式和规范化,候选码定义 设K为关系模式R(U，F)中的属性或属性组合，若K U，则k称为R的一个候选码。若关系模式R中有多个候选码，
13、则选定其中一个作为主码。组成候选码的属性称为主属性，不参加任何候选码的属性成为非主属性。,f,第一范式,4.4.2 范式的判定条件与规范化1.第一范式（1NF）定义：设R是一个关系模式，R属于第一范式当且仅当R中每一个属性A的值域只包含原子项，即不可分割的数据项。,第一范式（续）,例:关系模式 SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：(Sno,Cno)f Grade Sno Sdept(Sno,Cno)P Sdept Sno Sloc(Sno,Cno)P Sloc Sdept Sloc,第一范式（续）,SLC的
14、码为(Sno,Cno),第一范式（续）,结论:1.SLC满足第一范式。2.非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)。,第一范式（续）,第一范式存在的问题插入异常：若插入一个学生，但未选课，这样的元祖不能插入。删除异常：如果某个学生只选修了一门课，如果他不选该课程了，则在删除课程号的同时会把该学生也一起删除。数据冗余大：如果一个学生选修了10门课程，则他的DEPT和SLOC值就要重复存储10次。修改复杂：如果要修改DEPT和SLOC的值，则必须修改10次。,第一范式（续）,原因 Sdept、Sloc部分函数依赖于码。解决方法 采用投影分解法，把SLC分解为两个关系模式，以消
15、除这些部分函数依赖。SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）,第一范式（续）,第一范式（续）,函数依赖图：,第二范式,2.第二范式（2NF）定义：设R是一个关系模式，R属于第二范式当且仅当R是1NF，且每个非主属性都完全函数依赖于主码。,第二范式（续）,例：2NF关系模式SL(Sno,Sdept,Sloc)中函数依赖：SnoSdept SdeptSloc SnoSloc,Sloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。,第二范式（续）,第二范式存在的问题删除异常：如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系的信息也丢掉了。数
16、据冗余大：每一个系的学生都住在同一个地方，系的住处重复了多次。修改复杂：当学校调整学生住处，如信息系的学生全部迁到另一地方，修改时必须同时修改该系的所有学生的SLOC属性值。原因是还存在sloc对sno的传递函数依赖,第二范式（续）,原因Sloc传递函数依赖于Sno解决方法 采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为Sno，DL的码为Sdept。,第二范式（续）,SD的码为Sno，DL的码为Sdept。,第三范式,3.第三范式（3NF）定义：设R是一个关系模式，R属于第三范式当且仅当R是2NF，且每个非主属性都
17、非传递函数依赖于主码。,第三范式（续）,例如：模型SC(SNO,SNAME,CNO,GRADE)模型的候选码是：(SNO,CNO)、(SNAME,CNO)非主属性只有GRADE，对这两个候选码都是完全函数依赖，因此SC3NF。,存在的问题删除异常：当学生退选了课程，元组被删除也失去学生学号和姓名的对应关系。数据冗余：学生选课多时，姓名会被重复存储。,BC范式,4.BC范式（BCNF）定义：对于关系模式R，对任何非平凡的函数依赖X Y，X均包含码，则R属于BCNF。,BC范式（续）,例：STJ（S，T，J）S表示学生，T表示教师，J表示课程。假若每一教师只教一门课，每门课有若干教师教，某一学生选
18、定的某门课就确定了一个固定的教师。STJ中F=SJ T，ST J，T J 存在两个候选码SJ和ST 没有非主属性，所以STJ 3NF 但是非平凡的函数依赖T J中T不包含码，故STJ不属于BCNF。对STJ分解，变为：ST（S，T），TJ（T，J）,规范化步骤,消除非主属性对码的部分函数依赖,BCNF,2NF,3NF,1NF,消除非主属性对码的传递函数依赖,消除每一属性对码的部分和传递函数依赖,随堂练习,（1）在关系模式R(U,F)中，如果X Y，存在X的真子集X1，使X1 Y，称函数依赖X Y为（）A.平凡函数依赖 B.部分函数依赖C.完全函数依赖D.传递函数依赖,（2）在关系模式R(U,F)中，对任何非平凡的函数依赖X Y，X均包含键，则R最高可以达到（）A.2NF B.3NFC.BCNFD.4NF,随堂练习,（3）已知：关系模式R(U,F),U=ABCDEG,F=A B,C G,E A,CE D 求：（1）R的候选码（2）R最高属于哪级范式,（4）已知：关系模式R(U,F),U=ABCDE,F=A BC,CD E,E A,B D 求：（1）R的候选码（2）R最高属于哪级范式,
