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

第6章关系数据库规范化理论,教学目标：通过本章学习，了解不规范的关系模式存在的问题；理解函数依赖及关系规范化的相关概念，熟悉关系模式的形式化定义；掌握第一范式(1NF)、第二范式(2NF)、第三范式(3NF)及BCNF的定义及相关术语的含义；了解多值依赖及第四范式(4NF)的定义；理解函数依赖公理的内容，掌握属性闭包的定义及求解算法，能够正确判断关系模式的候选码及规范化程度；了解最小函数依赖集的定义及算法，了解对模式分解后无损连接性和函数依赖保持性的判断。,文章来自个人网站，转载注明,6.1问题的提出6.2关系模式的规范化6.3多值依赖及关系的第四范式6.4关系规范化小结6.5函数依赖公理和模式分解6.6关系模式设计实例6.7本章小结,第6章关系数据库规范化理论,1存在的问题2解决方法,6.1问题的提出,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.存在的问题,下面以一个实例说明如果一个关系没有经过规范化可能会出现的问题。例如，要设计一个教学管理数据库，希望从该数据库中得到学生学号、姓名、年龄、性别、系别、系主任姓名、学生学习的课程名和该课程的成绩信息。若将此信息要求设计为一个关系，则关系模式为：S(sno，sname，sage，ssex，sdept，mname，cname，score),1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.存在的问题,该关系模式中各属性之间的关系为：一个系有若干个学生，但一个学生只属于一个系；一个系只能有一名系主任，但一个系主任可以同时兼几个系的系主任；一个学生可以选修多门课程，每门课程可被若干个学生选修；每个学生学习的每门课程都有一个成绩。可以看出，此关系模式的码为(sno，cname)。,1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.存在的问题,1数据冗余太大浪费大量的存储空间。例：每个系名和系主任的名字存储的次数等于该系学生人数乘以每个学生选修的课程门数，系名和系主任数据重复量太大。,1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,关系模式S中存在的问题：,2插入异常该插的数据插不进去。例：一个新系没有招生时，或系里有学生但没有选修课程，系名和系主任名无法插入到数据库中。因为在这个关系模式中码是(sno，cname)，这时没有学生而使得学号无值，或学生没有选课而使得课程名无值。但在一个关系中，码属性不能为空值，因此关系数据库无法操作，导致插入异常。,1.存在的问题,3删除异常不该删除的数据不得不删。例：当某系的学生全部毕业而又没有招新生时，删除学生信息的同时，系及系主任名的信息随之删除，但这个系依然存在，而在数据库中却无法找到该系的信息，即出现了删除异常。,1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,4更新异常数据冗余，更新数据时，维护数据完整性代价大。例：若某系换系主任，数据库中该系的学生记录应全部修改。如果稍有不慎，某些记录漏改了，则造成数据的不一致，即出现了更新异常。,1.存在的问题,为什么会发生插入异常和删除异常？原因是该关系模式中属性与属性之间存在不好的数据依赖。一个“好”的关系模式应当不会发生插入和删除异常，冗余度要尽可能得少。,1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,结论：,2.解决方法,对于存在问题的关系模式，可以通过模式分解的方法使之规范化。例如将上述关系模式分解成3个关系模式：S(sno，sname，sage，ssex，sdept)SC(sno，cnname，score)DEPT(sdept，mname)这样分解后，3个关系模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控制，数据的更新也变得简单。“分解”是解决冗余的主要方法，也是规范化的一条原则，“关系模式有冗余问题，就分解它”。,1问题的提出存在的问题解决方法2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,6.2关系模式的规范化,1基本概念2函数依赖3关系模式的形式化定义4码5范式,6第一范式7第二范式8第三范式9BCNF,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.基本概念,规范化：指用形式更为简洁、结构更加规范的关系模式取代原有关系模式的过程。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,关系模式对数据的要求：关系模式必须满足一定的完整性约束条件以达到现实世界对数据的要求。完整性约束条件主要包括以下两个方面。(1)对属性取值范围的限定。(2)属性值间的相互联系(主要体现在值的相等与否)，这种联系称为数据依赖,属性间的联系可分为3类。1)一对一联系(11)设X、Y是关系R的两个属性(集)。如果对于X中的任一具体值，Y中至多有一值与之对应；反之亦然，则称X、Y两属性间是一对一联系。例如，在关系模式S中，如果学生无重名，则属性sno和sname之间是一对一联系，一个学号唯一地决定一个姓名，一个姓名也唯一地决定一个学号。,属性间的联系：,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.基本概念,2)一对多联系(1n)设X、Y是关系R的两个属性(集)。如果对于X中的任一具体值，Y中至多有一个值与之对应，而Y中的一个值却可以和X中的n个值(n0)相对应，则称Y对X是一对多联系。在学生关系模式S中，属性sdept和sno之间是一对多联系，即一个系对应多个学号(如计算机系可对应20060101、20060102等)，但一个学号却只对应一个系(如20060101只能对应计算机系)。同样，mname和sno、sno和score之间都是一对多联系。,3)多对多联系(mn)设X、Y是关系R的两个属性(集)。如果对于X中的任一具体值，Y中有m(m0)个值与之对应，而Y中的一个值也可以和X中的n个值(n0)相对应，则称Y对X是多对多联系。在关系模式S中，cname和score两属性间是多对多联系。一门课程对应多个成绩，而一个成绩也可以在多门课程中出现。Sno和cname、sno和score之间也是多对多联系。,属性间的联系：,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.基本概念,上述属性间的3种联系实际上是属性值之间相互依赖又相互制约的反映，称为属性间的数据依赖。,数据依赖是指通过一个关系中属性间值的相等与否体现出来的数据间的相互关系，是现实世界属性间相互联系的抽象，是数据内在的性质。,数据依赖：,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.基本概念,数据依赖共有3种：A、函数依赖(FunctionalDependency，FD)B、多值依赖(MultiValuedDependency，MVD)C、连接依赖(JoinDependency，JD)其中最重要的是函数依赖和多值依赖。,在数据依赖中，函数依赖是最基本、最重要的一种依赖，它是属性之间的一种联系，假设给定一个属性的值，就可以唯一确定(查找到)另一个属性的值。例如，知道某一学生的学号，可以唯一地查询到其对应的系别，如果这种情况成立，就可以说系别函数依赖于学号。这种唯一性并非指只有一个记录，而是指任何记录。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,函数依赖的定义：设有关系模式R(U)，X和Y均为U=A1，A2，An的子集，r是R的任一具体关系，r中不可能存在两个元组在X的属性值相等，而在Y上的属性值不等(也就是说，如果对于r中的任意两个元组t和s，只要有tX=sX，就有tY=sY)，则称X函数决定Y，或称Y函数依赖于X，记作XY，其中X叫做决定因素(Determinant)，Y叫做依赖因素(Dependent)。,(1)XY，但YX，则称XY是非平凡的函数依赖。(2)XY，但YX，则称XY是平凡的函数依赖。因为平凡的函数依赖总是成立的，所以若不特别声明，本书后面提到的函数依赖，都不包含平凡的函数依赖。(3)若XY，YX，则称XY。(4)若Y不函数依赖于X，则记作XY。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,术语与记号：,在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有XY，则称Y对X完全函数依赖，记作XY。若XY，如果存在X的某一真子集X(XX)，使XY，则称Y对X部分函数依赖，记作XY。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,在关系模式R(U)中，X、Y、Z是R的3个不同的属性或属性组，如果XY(YX，Y不是X的子集)，且YX，YZ，则称Z对X传递函数依赖，记作XY。加上条件YX，是因为如果YX，则XY，实际上是XZ，是直接函数依赖而不是传递函数依赖。,完全函数依赖与部分函数依赖：,传递函数依赖：,前面讨论的属性间的3种联系，并不是每种联系中都存在函数依赖。(1)11联系：如果两属性集X、Y之间是1：1联系，则存在函数依赖：XY。如学生关系模式S中，如果不允许学生重名，则有：snosname。(2)1n联系：如果两属性集X、Y之间是n1联系，则存在函数依赖：XY，即多方决定一方。如snosdept，snosage、snomname等。(3)mn联系：如果两属性集X、Y之间是mn联系，则不存在函数依赖。如sno和cname之间、cname和score之间就是如此。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,属性间联系决定函数依赖：,【例6-1】设有关系模式S(sno，sname，sage，ssex，sdept，mname，cname，score)，判断以下函数依赖的对错。(1)snosname，snossex，(sno，cname)score。(2)cnamesno，sdeptcname，snocname。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,例题：,在(1)中，sno和sname之间存在一对一或一对多的联系，sno和ssex、(sno，cname)和score之间存在一对多联系，所以这些函数依赖是存在的。在(2)中，因为sno和cname、sdept和cname之间都是多对多联系，因此它们之间是不存在函数依赖的。,【例6-2】设有关系模式：学生课程(学号，姓名，课程号，课程名称，成绩，教师，教师年龄)，在该关系模式中，成绩要由学号和课程号共同确定，教师决定教师年龄。该关系模式中包含的函数依赖有哪些？,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,2.函数依赖,例题：,此关系模式中包含了以下函数依赖关系：学号姓名(每个学号只能有一个学生姓名与之对应)，课程号课程名称(每个课程号只能对应一个课程名称)，(学号，课程号)成绩(每个学生学习一门课只能有一个成绩)，教师教师年龄(每一个教师只能有一个年龄)。,关系模式的完整表示是一个五元组：R(U，D，Dom，F)其中：R：关系名，代表一个关系模式；U：关系模式R的属性集合(属性组)；D：属性集合U的数据域；Dom：属性到域的映射关系；F：属性集合U上的一组数据依赖的集合。由于D和Dom对设计关系模式的作用不大，在讨论关系规范化理论时可以把它们简化为三元组：R(U，F)从上式可以看出，数据依赖是关系模式的重要因素。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,3.关系模式的形式化定义,设K是关系模式R(U，F)中的属性或属性集合，K是K的任一真子集。若KU，而不存在KU(KU)，则K为R的候选码(CandidateKey)，简称码。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,4.码,(1)若候选码多于一个，则选取其中的一个为主码(PrimaryKey)。(2)包含在任一候选码中的属性，称为主属性(PrimeAttribute)或码属性。(3)不包含在任何候选码中的属性称为非主属性(NonprimeAttribute)或非码属性(Non-keyAttribute)。(4)在关系模式中，最简单的情况，单个属性是码，称为单码(SingleKey)；最极端的情况，整个属性集合是码，称为全码(All-Key)。,例如：在关系模式S(sno，sdept，sage)中，sno是单码。在关系模式SC(sno，cno，score)中，属性组合(sno，cno)是码。在关系模式“签约(演员名，制片公司名，电影名)”中，由于一个制片公司可以为一部电影和多个演员签约，一个演员可以和多个制片公司签约饰演多部电影中的角色，一部电影可由不同的制片公司制作，所以此关系模式的码为(演员名，制片公司名，电影名)，即为全码。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,4.码,关系模式R(U，F)中属性或属性集合X并非R的码，但X是另一个关系模式的码，则称X是R的外码(Foreignkey)，也称外在码。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,4.码,如在SC(sno，cno，score)中，sno不是码，但sno是关系模式S(sno，sdept，sage)的码，则sno是关系模式SC的外码。,当一个关系中存在还可以再分的数据项时，这个关系就是非规范化的关系。非规范化的关系存在两种情况：第一种是关系中具有组合数据项；第二种是关系中具有多值数据项。实例见表1和表2。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,5.范式,非规范化的关系：,表2具有多值数据项的非规范化关系,表1具有组合数据项的非规范化关系,当一个关系中的所有分量都是不可再分的数据项时，该关系是规范化的，即当关系中不存在组合数据项和多值数据项，只存在不可分的数据项时，这个关系是规范化的。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,5.范式,规范化的关系：,利用规范化理论，使关系模式的函数依赖集满足特定的要求，满足特定要求的关系模式称为范式。关系按其规范化程度从低到高可分为5级范式(NormalForm)，分别称为1NF、2NF、3NF(BCNF)、4NF、5NF。,范式：,一个低一级范式的关系模式，通过模式分解可以转换成若干个高一级范式的关系模式的集合，这个过程称作规范化。,规范化：,如果关系模式R中不包含多值属性(每个属性必须是不可分的数据项)，则R满足第一范式(FirstNormalForm)，记作R1NF。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,6.第一范式,定义：,1NF是规范化的最低要求，是关系模式要遵循的最基本的范式，不满足1NF的关系是非规范化的关系。,关系模式如果仅仅满足1NF是不够的。尽管学生关系模式S满足1NF，但它仍然会出现插入异常、删除异常、更新异常及数据冗余等问题，只有对关系模式继续规范化，使之满足更高的范式，才能得到高性能的关系模式。,注意：,如果关系模式R(U，F)1NF，且R中的每个非主属性完全函数依赖于R的某个候选码，则R满足第二范式(SecondNormalForm)，记作R2NF。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,7.第二范式,定义：,【例6-3】关系模式S-L-C(U，F)U=SNO，SDEPT，SLOC，CNO，SCORE，其中，SNO是学号，SDEPT是学生所在系，SLOC是学生的宿舍(住处)，CNO是课程号，SCORE是成绩。该关系模式的码=(SNO，CNO)函数依赖集F=(SNO，CNO)SCORE，SNOSDEPT，SNOSLOC，SDEPTSLOC非主属性=SDEPT，SLOC，SCORE非主属性对码的部分函数依赖=(SNO，CNO)SDEPT，(SNO，CNO)SLOC显然，该关系模式不满足2NF。,例题：,(1)插入异常。插入一个新学生，若该生没有选课，则CNO为空，但码不能为空，所以不能插入。(2)删除异常。某学生只选择了一门课，现在该门课要删除，则该学生的基本信息也将删除。(3)更新异常。某个学生要从一个系转到另一个系，若该生选修了K门课，必须修改的该学生相关的字段值为2K个(系别、住处)，一旦有遗漏，将破坏数据的一致性。造成以上问题的原因是SDEPT、SLOC部分函数依赖于码。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,7.第二范式,不满足2NF的关系模式，会产生以下几个问题：,用投影分解把关系模式分解为多个关系模式。投影分解是把非主属性及决定因素分解出来构成新的关系，决定因素在原关系中保持，函数依赖关系相应分开转化(将关系模式中部分依赖的属性去掉，将部分依赖的属性单独组成一个新的模式)。,解决办法：,S-C(SNO，CNO，SCORE)码=(SNO，CNO)F=(SNO，CNO)SCORES-L(SNO，SDEPT，SLOC)码=SNOF=SNOSDEPT，SNOSLOG，SDEPTSLOG,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,7.第二范式,例6-3中关系模式的分解结果：,经过模式分解，两个关系模式中的非主属性对码都是完全函数依赖，所以它们都满足2NF。,如果关系模式R(U，F)2NF，且每个非主属性都不传递函数依赖于任何候选码，则R满足第三范式(ThirdNormalForm)，记作R3NF。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,8.第三范式,定义：,在例6-3中，关系S-L(SNO，SDEPT，SLOC)，SNOSDEPT，SDEPTSLOC，SLOC传递函数依赖于码SNO，所以S-L不满足3NF。解决的方法同样是将S-L进行投影分解：S-D(SNO，SDEPT)码=SNOF=SNOSDEPTD-L(SDEPT，SLOC)码=SDEPTF=SDEPTSLOC分解后的关系模式中不再存在传递函数依赖，即关系模式S-D和D-L都满足3NF。,例题：,3NF是一个可用的关系模式应满足的最低范式，也就是说，一个关系模式如果不满足3NF，实际上它是不能使用的。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,8.第三范式,总结：,关系模式R(U，F)1NF，若XY且YX时，X必含有码，则R(U，F)BCNF。也就是说，关系模式R(U，F)中，若每个决定因素都包含码，则R(U，F)BCNF。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,9.BCNF,定义：,由BCNF的定义可以得出结论，一个满足BCNF的关系模式有：(1)所有非主属性对每一个码都是完全函数依赖。(2)所有的主属性对每一个不包含它的码，也是完全函数依赖。(3)没有任何属性完全函数依赖于非码的任何一组属性。,【例6-4】设关系模式SC(U，F)，其中，U=SNO，CNO，SCOREF=(SNO，CNO)SCORE，(CNO，SCORE)SNOSC的候选码为(SNO，CNO)和(CNO，SCORE)，决定因素中都包含码，没有属性对码传递依赖或部分依赖，所以SCBCNF。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,9.BCNF,例题：,【例6-5】设关系模式STJ(S，T，J)，其中，S：学生，T：教师，J：课程。每位教师只教一门课，每门课有若干教师，某一学生选定某门课，就对应一位固定的教师。由语义可得到如下的函数依赖：(S，J)T，(S，T)J，TJ该关系模式的候选码为(S，J)，(S，T)。因为该关系模式中的所有属性都是主属性，所以STJ3NF，但STJBCNF，因为T是决定因素，但T不包含码。,(1)BCNF不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，则R一定满足3NF。如果一个实体集中的全部关系模式都满足BCNF，则实体集在函数依赖范畴内已实现了彻底的分离，消除了插入和删除异常问题。(2)3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传递依赖。,1问题的提出2关系模式的规范化基本概念函数依赖关系模式的形式化定义码范式第一范式第二范式第三范式BCNF3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,9.BCNF,BCNF和3NF的比较：,*6.3多值依赖及关系的第四范式,1多值依赖2第四范式,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.多值依赖,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,满足BCNF的关系实例：,1.多值依赖,(1)数据冗余十分明显。课程、教师和班级多次存储。(2)插入异常。若增加一个讲授“数据结构”的教师“张平”，由于有3个班级开设这门课，所以需要添加3个元组，即(数据结构，张平，06级01班)、(数据结构，张平，06级02班)和(数据结构，张平，06级03班)。(3)删除异常。若要删除某一个班级，则与该班级有关的元组将全部被删除。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,满足BCNF的关系模式存在的弊端：,1.多值依赖,(1)对于关系CTC中的Course值，有多个Teacher值与之对应，同样，Course和Class也存在着类似的联系。(2)对于关系CTC中的一个确定的Course值，只与其所对应的一组Teacher值和Class值相关。如对于“数据结构”课程，“王小平”给“06级01班”上课，“陈平”给“06级02班”上课，“张利英”给“06级03”班上课，关系CTC中其他与“数据结构”相关的元组中的Teacher与Class毫无关系。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,产生以上弊端的原因主要有以下两个方面：,从以上两个方面可以看出，Course与Teacher之间的联系显然不是函数依赖，在此称之为多值依赖(MultiValuedDependency，MVD)。,1.多值依赖,设有关系模式R(U)，U是属性全集，X、Y、Z是U的子集，且Z=U-X-Y。如果对R(U)的任一关系r，给定一对(X，Z)值，都有一组Y值与之对应，这组Y值仅仅决定于X值而于Z值无关，则称Y多值依赖于X，或X多值决定Y，记作XY。多值依赖的形式化定义为：设有关系模式R(U)，X，Y，Z是U的子集，其中Z=U-X-Y，r是R的任意一个关系，t，s是r的任意两个元组。如果tX=sX，必有r的两个元组u、v存在，使得：(1)uX=vX=tX=sX，(2)uY=tY且uZ=sZ，(3)vY=sY且vZ=tZ，则称X多值决定Y，或Y多值依赖于X。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,定义：,1.多值依赖,现有关系SDC(SDEPT，SNO，CNAME)，见表6-8。其中，SDEPT是系别，SNO是学号，CNAME是该系开设的课程。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,例题：,给出一对值(计算机工程系，微机原理)，有一组学号与之对应，学号仅仅决定于系别，而与课程无关，所以SDEPTSNO。同理，SDEPTCNAME。,1.多值依赖,对于属性集U上的多值依赖XY，如果YZ或者XY=U(即Z=)，则称XY为平凡的多值依赖，否则XY为非平凡的多值依赖。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,平凡的多值依赖与非平凡的多值依赖：,(1)对称性。若XY，则XZ，其中，Z=U-X-Y。(2)传递性。若XY，YZ，则XZ-Y。(3)合并性。若XY，XZ，则XYZ(Y与Z的并集)。(4)分解性。若XY，XZ，则XYZ(Y与Z的交集)，XY-Z，XZ-Y均成立。,多值依赖的性质：,函数依赖可以看成是多值依赖的特例，即函数依赖的关系一定是多值依赖；多值依赖是函数依赖的概括，即存在多值依赖的关系，不一定存在函数依赖。,2.第四范式,如果关系模式R1NF，对于R的每个非平凡的多值依赖XY(Y不包含在X中)，X含有码，则R满足第四范式(ForthNorwalForm)，记作R4NF。显然，如果R4NF，则必有RBCNF。反之则不然，因为所有非平凡的多值依赖实际上就是函数依赖。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式多值依赖第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,定义：,【例6-7】在SDC(SDEPT，SNO，CNAME)中，该关系的码为全码，SDEPTSNO，SDEPTCNAME，而SDEPT只是码的一部分，所以该关系模式不满足4NF，将其进行模式分解，得到两个关系模式：SD(SDEPT，SNO)DC(SDEPT，CNAME)在这两个关系模式中，多值依赖均不是平凡的多值依赖，即关系模式中存在非平凡的多值依赖，因此它们满足4NF。,例题：,6.4关系规范化小结,在关系数据库中，对关系模式的基本要求是满足1NF，在此基础上，为了消除关系模式中存在的插入异常、删除异常、更新异常和数据冗余等问题，人们寻求解决这些问题的方法，这就是规范化的目的。规范化的基本思想是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。让一个关系描述一个概念、一个实体或实体间的一种联系，若多于一个概念就把它“分离”出去，因此所谓规范化实质上是概念的单一化。关系模式的规范化过程是通过对关系模式的分解来实现的，把低一级的关系模式分解为若干个高一级的关系模式，对关系模式进一步规范化，使之逐步达到2NF、3NF、4NF和5NF。各种规范化之间的关系为：5NF4NFBCNF3NF2NF1NF。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,6.4关系规范化小结,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,关系规范化的递进过程,6.4关系规范化小结,一般来说，规范化程度越高，分解就越细，所得数据库的数据冗余就越小，且更新异常也可相对减少。但是，如果某一关系经过数据大量加载后主要用于检索，那么，即使它是一个低范式的关系，也不要去追求高范式而将其不断进行分解，因为在检索时，会通过多个关系的自然连接才能获得全部信息，从而降低了数据的检索效率。数据库设计满足的范式越高，其数据处理的开销也越大。因此，规范化的基本原则是：由低到高，逐步规范，权衡利弊，适可而止。通常，以满足第三范式为基本要求。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,6.4关系规范化小结,把一个非规范化的数据结构转换成第三范式，一般经过以下几步。(1)把该结构分解成若干个属于第一范式的关系。(2)对那些存在组合码、且有非主属性部分函数依赖的关系必须继续分解，使所得关系都属于第二范式。(3)若关系中有非主属性传递依赖于码，则继续分解之，使得关系都属于第三范式。事实上，规范化理论是在与SQL编程语言结合时产生的。关系理论的基本原则指出，数据库被规范化后，其中的任何数据子集都可以用基本的SQL操作获取，这就是规范化的重要性所在。数据库不进行规范化，就必须通过编写大量复杂代码来查询数据。规范化规则在关系建模和关系对象建模中同等重要。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,*6.5函数依赖公理和模式分解,1函数依赖公理2属性闭包及在计算3求解关系模式的候选码4函数依赖集的最小依赖集5模式分解,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解6关系模式设计实例7本章小结,1.函数依赖公理,当讨论函数依赖时，经常需要从一些已知的函数依赖中去判断另外一些函数依赖是否成立。例如，如果AB和BC在某个关系中成立，记作F=AB，BC，那么AC在该关系中是否成立的问题就称为逻辑蕴涵问题。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,函数依赖的逻辑蕴涵：,设F是关系模式R(U，F)的一个函数依赖集，X，Y是U的子集，如果从F中的函数依赖能够推导出XY，则称F逻辑蕴涵XY，或称XY是F的逻辑蕴涵，记作F|=XY。,所有被F逻辑蕴涵的函数依赖集称为F的闭包(Closure)，记作F+。一般情况下，FF+，如果F=F+，则称F是函数依赖的完备集。规定：若X为U的子集，则X属于F+。,1.函数依赖公理,计算函数依赖集F的闭包F+是一件很麻烦的事，即使F不大，F+也可能很大。例如，R(X，Y，Z)，它的函数依赖集F=XY，YZ，则F的闭包如下：,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,F+=X，XY，XZ，XYZ，Y，Z，XX，XYX，XZX，XYZX，YY，ZZ，XY，XYY，XZY，XYZY，YZ，XZ，XYZ，XZZ，XYZZ，YYZ，XXY，XYXY，XZXY，XYXXY，YZ，XXZ，XYXZ，XZXZ，XYZXZ，YZY，XYZ，XYYZ，XZYZ，XYZYZ，YZZ，XXYZ，XYXYZ，XZXYZ，XYZXYZ，YZYZ这些函数依赖就是利用函数依赖公理进行推导的。,1.函数依赖公理,Armstrong公理系统设有关系模式R(U，F)，X，Y，Z，WU(X，Y，Z，W是U的子集)，则对R(U，F)有：(1)A1(自反律)：若YX，则XY。(2)A2(增广律)：若XY，则XZYZ。(XZ表示XZ)(3)A3(传递律)：若XY，YZ，则XZ。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,函数依赖公理系统：,所有被F逻辑蕴涵的函数依赖集称为F的闭包(Closure)，记作F+。一般情况下，FF+，如果F=F+，则称F是函数依赖的完备集。规定：若X为U的子集，则X属于F+。,1.函数依赖公理,设t1、t2是关系R中的任意两个元组。A1：如果t1X=t2X，则因为YX，所以有t1Y=t2Y，故XY成立。A2：如果t1XZ=t2XZ，则有t1X=t2X、t1Z=t2Z。又已知XY，因此得t1Y=t2Y，可知t1YZ=t2YZ，故XZYZ成立。A3：如果t1X=t2X，则t1Y=t2Y；如果t1Y=t2Y，则t1Z=t2Z。因此可得：如果t1X=t2X，则t1Z=t2Z，即XZ成立。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,证明：【定理6.1】Armstrong公理是正确的。,1.函数依赖公理,(1)合成规则。若XY，XZ，则XYZ。(2)分解规则。若XYZ，则XY，XZ。(3)伪传递规则。若XY，WYZ，则XWZ。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,Armstrong公理系统的3个推论：,XA1A2Ak成立的充分必要条件是XAi成立(i=1，2，k)。,引理：,1.函数依赖公理,设关系模式R(A，B，C，G，H，I)，函数依赖集为F=AB，AC，CGH，CGI，BH，利用规则，可以得到关系中存在以下几个函数依赖。(1)AH。由于AB，BH，使用传递律可得到AH。(2)CGHI。由于CGH，CGI，由合成律可得CGHI。(3)AGI。由于AC，CGI，由伪传递律可推出AGI。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,例题：,2.属性闭包及其计算,判断XY是否包含在F+中，只要判断XY能否用推理规则从F中导出，即判断YX+是否成立。这样就把计算F+的问题简化为计算X+的问题。,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,属性闭包的定义：,设关系模式R(U，F)，U为R的属性集合，F为其函数依赖集，XU且YU，则从F推出XY的充分必要条件是YX+。,引理：,设关系模式R(U，F)，U=A1，A2，An，F为其函数依赖集，则称所有用Armstrong公理从F推出的函数依赖XAi中Ai的属性集合为X的属性闭包，记作X+，读作X关于函数依赖集F的闭包。,2.属性闭包及其计算,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,引理证明：,充分性：设Y=A1，A2，An，且YX+。根据闭包的定义，对于每个i(i=1，2，n)，XAi能由推理规则导出，再根据合成律，则有XY。必要性：设XY能由推理规则导出，利用分解律，可得XAi(i=1，2，n)，于是根据X+的定义，有AiX+，所以，A1，A2，AnX+，即YX+。,2.属性闭包及其计算,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,求属性闭包的算法：,输入：关系模式R的全部属性集U，U的子集X，U上的函数依赖集F。输出：X关于F的属性闭包X+。步骤：设i=0，1，2，(1)初始化：i=0，X(i)=X(0)=X。(2)求属性集A。A是这样的属性：在F中寻找尚未用过的左边是X(i)子集的函数依赖Y(i)X(i)，并且在F中有Y(i)Z(i)，则A=Z(1)Z(2)Z(i)。(3)X(i+1)=X(i)A。(4)判断以下条件之一是否成立，若有条件成立，则转向(5)；否则，i=i+1，转向(2)。X(i+1)=X(i)。X(i)中已包含了R的全部属性。在F中的每个函数依赖的右边属性中已没有X(i)中未出现过的属性。在F中未用过的函数依赖的左边属性已没有X(i)的子集。(5)输出X(i+1)，即为X+。,2.属性闭包及其计算,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,例题：,已知关系模式R(U，F)，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)+。,解：由【算法6.1】，设X(0)=AB。计算X(1)，逐一扫描集合F中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：ABC，BD，于是X(1)=ABCD=ABCD。因为X(0)X(1)，所以再找出左部为ABCD子集的那些函数依赖，又得到CE，ACB，于是X(2)=X(1)BE=ABCDE。因为X(2)已等于全部属性的集合，所以(AB)+=ABCDE=U。,2.属性闭包及其计算,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结5函数依赖公理和模式分解函数依赖公理属性闭包及在计算求解关系模式的候选码函数依赖集的最小依赖集模式分解6关系模式设计实例7本章小结,例题：,设有关系模式R(A，B，C，D，E，I)，其中，F=AD，ABC，BIC，EDI，CE，计算(AC)+。,解：(1)令X=AC，则X(0)=AC；(2)计算X(1)，在F中找出左部是AC子集的函数依赖：AD，CE；(3)X(1)=X(0)DE=ACDE；(4)由于X(0)X(1)，所以i=i+1=X(1)，并转向算法中的步骤(2)；(5)在F中找出左部是ACDE子集的函数依赖：EDI；(6)X(2)=X(1)I=ACEDI；(7)虽然X(2)X(1)，但是F中未用过的函数依赖的左边属性已没有X(2)的子集，所以，可停止计算，输出(AC)+=X(2)=ACDEI。,2.属性闭包及其计算,1问题的提出2关系模式的规范化3多值依赖及关系的第四范式4关系规范化小结