关系数据模式的规范化理论

Copyright@2006CollegeofITSoft(HZIEE)VersionNo:1.0第4章关系数据模式的规范化理论4.1问题的提出4.2函数依赖4.3范式和规范化Copyright@2006CollegeofITSoft(HZIEE)2VersionNo:1.0什么是数据库设计?怎么设计？现实世界数据/关系机器世界4.1问题的提出Copyright@2006CollegeofITSoft(HZIEE)3VersionNo:1.0是不是从信息世界的模型中简单地转化为机器世界的数据就可以了呢?实体关系表属性数据项4.1问题的提出Copyright@2006CollegeofITSoft(HZIEE)4VersionNo:1.04.1问题的提出如果要设计一个教学管理数据库，希望从数据库中得到学生学号(sno)、学生姓名(name)、性别(sex)、学生学习的课程号(cno)、课程名(cname)和该门课程的成绩(grade)。如何设计该关系模式？主码是什么?(学号,姓名,性别,课程号,课程名,成绩)(SNO,NAME,SEX,CNO,CNAME,GRADE)Copyright@2006CollegeofITSoft(HZIEE)5VersionNo:1.04.1问题的提出问题1：数据冗余SNONAMESEXCNOCNAMEGRADES0102王华男C108C语言84S0102王华男C206数据库92S0108李丽女C206数据库86S0108李丽女C207数学86Copyright@2006CollegeofITSoft(HZIEE)6VersionNo:1.04.1问题的提出问题2：不一致性SNONAMESEXCNOCNAMEGRADES0102王华男C108C语言84S0102张三男C206数据库92S0108李丽女C206数据库86S0108李丽女C207数学86Copyright@2006CollegeofITSoft(HZIEE)7VersionNo:1.04.1问题的提出问题3：插入异常SNONAMESEXCNOCNAMEGRADES0102王华男C108C语言84S0102王华男C206数据库92S0108李丽女C206数据库86S0108李丽女C207数学86（S0010，李四，男，null，null，null）Copyright@2006CollegeofITSoft(HZIEE)8VersionNo:1.04.1问题的提出问题4：删除异常（当某学号只有一条记录，并做删除操作时）SNONAMESEXCNOCNAMEGRADES0102王华男C108C语言84S0103张三男C206数据库92S0108李丽女C206数据库86S0108李丽女C207数学86Copyright@2006CollegeofITSoft(HZIEE)9VersionNo:1.04.1问题的提出解决方案S1（SNO，NAME，SEX）S2（CNO，CNAME）S3（SNO，CNO，GRADE）Copyright@2006CollegeofITSoft(HZIEE)10VersionNo:1.04.2函数依赖定义1设R(U)是属性集U上的关系模式，X，Y是U的子集。若对于R(U)任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X-YCopyright@2006CollegeofITSoft(HZIEE)11VersionNo:1.04.2函数依赖例子职工号-姓名S1:SNO-NAME;SNO-SEXS2:(SNO,CNO)-GRADES3:CNO-CNAMECopyright@2006CollegeofITSoft(HZIEE)12VersionNo:1.04.2函数依赖定义2设X-Y是一个函数依赖，若则称X-Y是一个平凡函数依赖。YXYX设X-Y是一个函数依赖，若则称X-Y是一个非平凡函数依赖。Copyright@2006CollegeofITSoft(HZIEE)13VersionNo:1.04.2函数依赖例子在S2中有(SNO,CNO)-SNO(SNO,CNO)-CNO所以这些都是平凡函数依赖关系(SNO,CNO)-GRADE这个是非平凡函数依赖关系Copyright@2006CollegeofITSoft(HZIEE)14VersionNo:1.04.2函数依赖定义3设X-Y是一个函数依赖，并且对于任何则称X→Y是一个完全函数依赖。即Y函数依赖于整个X，记'',XXXY都不成立（记为XY）fXYCopyright@2006CollegeofITSoft(HZIEE)15VersionNo:1.04.2函数依赖举例：在关系S(SNO,NAME,SEX,CNO,CNAME,GRADE)中：(SNO,CNO)-GRADE但SNO-GRADE；(CNO)-GRADE都不成立所以(SNO,CNO)-GRADE是完全函数依赖关系。Copyright@2006CollegeofITSoft(HZIEE)16VersionNo:1.04.2函数依赖定义4设X-Y是一个函数依赖,但不是完全函数依赖,则称X-Y是一个部分函数依赖,或称Y函数依赖于X的某个真子集,记pXYCopyright@2006CollegeofITSoft(HZIEE)17VersionNo:1.04.2函数依赖在关系S(SNO,NAME,SEX,CNO,CNAME,GRADE)中：(SNO,CNO)-NAME,而对于每个学生都有唯一的SNO值,所以SNO-NAME,而CNO-NAME,因此，(SNO,CNO)-NAME是部分函数依赖(SNO,CNO)—NAMEpCopyright@2006CollegeofITSoft(HZIEE)18VersionNo:1.04.2函数依赖设R(U)是一个关系模式,则称Z传递函数依赖于X,记\,,,,XYZUXYXY如果（YX）,YZ成立tXZCopyright@2006CollegeofITSoft(HZIEE)19VersionNo:1.04.2函数依赖例子：班级(班号,专业名,系名,人数,入学年份)班号-专业名,专业名-系名,班号-人数,班号-入学年份班号-专业名,专业名-系名t班级号系名Copyright@2006CollegeofITSoft(HZIEE)20VersionNo:1.04.2函数依赖函数依赖与属性关系属性之间有3种关系,但并不是每一种关系中都存在函数依赖。Copyright@2006CollegeofITSoft(HZIEE)21VersionNo:1.0函数依赖与属性关系设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间不存在函数依赖.Copyright@2006CollegeofITSoft(HZIEE)22VersionNo:1.0函数依赖与属性关系分析下列关系中各种函数的依赖关系:学生(学号,姓名,出生年月,系名,班号,宿舍区)Copyright@2006CollegeofITSoft(HZIEE)23VersionNo:1.0Armstrong公理背景为了从一组函数依赖中求得逻辑蕴涵的函数依赖,例如已知函数依赖集F,要问是否逻辑蕴涵X-Y,就需要一套推理规则.Copyright@2006CollegeofITSoft(HZIEE)24VersionNo:1.0Armstrong公理设A,B,C,D是给定关系模式R的属性集的任意子集,并把A和B的并集称为AB,则其推理规则可归结为3条:自反律:如果,BAAB则这是一个平凡函数依赖增广律:如果ABACBC，则传递律:如果ABAC，且BC则Copyright@2006CollegeofITSoft(HZIEE)25VersionNo:1.0Armstrong公理—推论自合规则:A-A分解规则:A-BC,则A-B且A-C合并规则:A-B且A-C,则A-BC复合规则:A-B且C-D成立,则AC-BDCopyright@2006CollegeofITSoft(HZIEE)26VersionNo:1.04.2函数依赖4.2.6闭包及其计算定义6：设F是关系模式R的一个函数依赖集，X，Y是R的属性子集，如果从F中的函数依赖能够推出X→Y，则称F逻辑蕴涵X→Y。定义7：被F逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包，记为F+。练习1：设有关系模式R(A,B,C,D,E)，F={A→C,BC→E,D→C,E→A}，试求F的闭包F+。Copyright@2006CollegeofITSoft(HZIEE)27VersionNo:1.04.2函数依赖定义8：设F是属性集U上的一组函数依赖，XU，则属性集X关于F的闭包X+定义为X+={A|A∈U且X→A在F+中}，即X={A|X→A∈F+}。算法4.1result=Xdo{ifF中有某个函数依赖Y→Z满足Yresultthenresult=result∪Z}while(result有所改变);Copyright@2006CollegeofITSoft(HZIEE)28VersionNo:1.0XF+算法:设i=0①令X(0)=X②计算A={B|一切WX(i)且W→BF+}令X(i+1)=X(i)A③判断X(i+1)=X(i)是否成立，成立，转④，不成立，i=i+1，转②④算法结束，XF+=X(i)4.2函数依赖Copyright@2006CollegeofITSoft(HZIEE)29VersionNo:1.0随堂练习练习1：设有关系模式R(A,B,C,D,E)，F={A→B,C→E,D→AC}，试求D关于F的闭包。练习2：设有关系模式R(A,B,C,D,E)，F={AB→C,B→D,C→E,E→C,A→C}，试求BC关于F的闭包(BC)F+。Copyright@2006CollegeofITSoft(HZIEE)30VersionNo:1.04.2函数依赖关键码的定义如果X→U在R上成立（即X→U在F+中），那么称X是R的一个超键。如果X→U在R上成立，但对X的任一真子集X′都有X′→U不成立（即X′→U不在F+中，或者X→U），那么称X是R上的一个候选键。快速求解候选键的一个充分条件对于给定的关系模式R(A1…，An)和函数依赖集F，可将其属性分为以下四类：fL类R类N类LR类Copyright@2006CollegeofITSoft(HZIEE)31VersionNo:1.0定理4.4对于给定的关系模式R及其函数依赖集F（1）若X（X∈R）是L类属性，则X必为R的任一候选键的成员。（2）若X（X∈R）是L类属性，且X+包含了R的全部属性，则X必为R的惟一候选键。（3）若X（X∈R）是R类属性，则X不在任何候选键中。（4）若X（X∈R）是N类属性，则X包含在R的任一候选键中。（5）若X（X∈R）是R的N类和L类属性组成的属性集，且X+包含了R的全部属性，则X是R的惟一候选键。Copyright@2006CollegeofITSoft(HZIEE)32VersionNo:1.0随堂练习练习1：设有关系模式R(A,B,C,D,E)，F={A→B,C→G,E→A，CE→D}，求R的所有候选键。练习2：设有关系模式R(A,B,C,D,E,P)，F={A→D,E→D,D→B,BC→D,DC→A}，求R的所有候选键。练习3：设有关系模式R(A,B,C,D,E)，F={A→BC,CD→E,B→D,E→A}，求R的所有候选键。Copyright@2006CollegeofITSoft(HZIEE)33VersionNo:1.0多属性函数依赖集候选键的