《关系规范化理论》PPT课件.ppt

第四章 关系规范化理论,本章内容,教学目的,掌握函数依赖的概念 掌握1NF、2NF、3NF和BCNF范式 掌握模式分解的方法,教学要求 牢记有关概念，掌握关系模式规范化的方法 教学重点 规范化问题的存在的原因 函数依赖、完全函数依赖、传递依赖 规范化过程,4.1.1 规范化理论的主要内容 关系数据库的规范化理论 函数依赖 范式（Normal Form） 模式设计,核心，是模式分解和设计的基础,模式分解的标准,【例4-1】 学生选课数据库 在此关系模式中填入一部分具体的数据,4.1.2 不合理的关系模式存在的数据冗余和异常现象,SCS(Sno, Sname, Ssex, Sdept, Cno, Cname, Sorce),数据冗余 插入异常 删除异常 修改异常,该表出现的问题,关系模式SCS存在以下问题： （1）数据冗余 当一个学生选修多门课程时，就会导致姓名、性别院名等多次重复存储；每一门课程名均对选修该门课程的学生重复存储，因而造成数据冗余。 （2）操作异常 插入异常 如果某个学生还没有选课，学生的有关信息就不能插入。 同样，没有被学生选修的课程信息也无法存入数据库。,关系模式SCS存在以下问题： 删除异常 当学生毕业离校时，要把他们的信息从数据库中删除，如果此时他们所选修的某些课程尚无其他年级的学生选修，那么这些课程的基本信息就会丢失，一旦查询所开课程信息时，就不会出现被删除课程的信息，就会认为该课程没有开过，可实际上不是这种情况。 修改异常 若某个学生从信电学院转到管理学院，那么与该学生相关的所有记录都需要逐一修改属性Sdept的值，如有遗漏，就会造成SCS中数据的不一致。,结论 SCS关系模式不是一个好的模式。 “好”的模式： 不会发生插入异常、删除异常、更新异常， 数据冗余应尽可能少 根本原因：属性间存在着数据依赖引起的 解决方法：通过分解关系模式来消除其中不合适的数据依赖,S(Sno, Sname, Ssex, Sdept) C(Cno, Cname) SC(Sno, Cno, Score),SCS(Sno, Sname, Ssex, Sdept, Cno, Cname, Sorce),就不会出现上述异常，数据冗余也得到较好控制。,关系模式分解,函数依赖（Functional Dependency）是数据依赖的一种。数据依赖是指一个关系中属性值之间的相互联系，它是现实世界属性间相互联系的体现，是数据之间的内在性质，是语义的体现。现在已经提出了多种类型的数据依赖，其中最重要的是函数依赖和多值依赖。函数依赖是关系规范化的理论基础。,函数依赖,4.2,4.2.1 函数依赖的定义,定义4.1设R(U)是一个关系模式，U是R的属性集合，X和Y是U的子集，如果对于R(U)的任意一个可能的关系r，对于X的每一个具体值，Y都有唯一的具体值与之对应，则称X决定函数Y，或Y函数依赖于X，记作XY。 例如：姓名年龄”这个函数依赖只有在没有重名的学生情况下成立。如果有重名的学生，则“年龄”就不再依赖于“姓名”了。,（1）如果XY，且YX，则称XY是平凡的函数依赖。 （2）如果XY，但，则称XY是非平凡的函数依赖。 （3）如果XY，则称X为决定因素（Determinant），称Y 为依赖因素（Dependent）。 （4）如果XY且YX，则记作XY。 （5）如果Y不函数依赖于X，则记作XY 。,一般都是,4.2.2 完全函数依赖和部分函数依赖,定义4.2在关系模式R(U)中，U是R的属性集合，X和Y是U的子集。 如果XY，并且对于X的任何一个真子集X，都有X Y，则称Y完全函数依赖（Full Functional Dependency）于X，记作X Y； 如果对的某个真子集X，有XY，则称Y部分函数依赖（Partial Functional Dependency）于X，记作X Y。 【例4-2】 在关系SC(Sno, Cno, Cname, Score)中，因为Sno Score且Cno Score，所以(Sno, Cno) Score。而CnoCname，所以(Sno, Cno) Cname。,4.2.3 传递函数依赖,定义4.3：在关系模式R(U)中，U是R的属性集合，X和Y是U的子集。如果XY，YZ，且Y X，Y X，则称Z传递函数依赖（Transitive Functional Dependency）于X，记作X Z；否则称Z非传递函数依赖于X。 【例4-3】 在关系S(Sno，Sname, Ssex, Sdept, Dean)中，有函数依赖关系Sno Sname，由于Sno Sdept，Sdept Dean，有Sno Dean。,范式（Normal Forms，NF）的概念是E.F.Codd在1971年提出的。19711972年，E.F.Codd提出了1NF、2NF与3NF。1974年，Codd与Boyce又共同提出了BCNF。1976年，Fagin提出了4NF，后来又有人提出了5NF。在这些范式中，最重要的是3NF和BCNF，它们是进行规范化的主要目标，基本保证了防止冗余问题和异常情况的发生。,关系数据库中的关系必须满足一定的规范化要求，对于不同的规范化程度可用范式来衡量。 范式是满足一定要求的关系模式的集合，是衡量关系模式规范化程度的标准，满足不同程度要求的为不同范式。 目前主要有6种范式： 第一范式（1NF） 第二范式（2NF） 第三范式（3NF） BC范式（BCNF） 第四范式（4NF） 第五范式（5NF）,范式的级别越高，条件越严格。满足基本规范化要求的关系模式称为第一范式，简称为1NF；在第一范式基础上进一步满足一定要求的范式为第二范式，简称为2NF；其余以此类推。 各种范式之间存在联系： 1NF2NF3NFBCNF4NF5NF 通常把某一关系模式R为第n范式简记为RnNF。 通过模式分解可以将低级范式的关系模式转换为若干个高级范式的关系模式的集合，这个过程称为关系模式的规范化。,4.3.1 第一范式（1NF）,定义4.4：如果关系模式R的每个属性都是不可分解的基本数据项，则称R属于第一范式，记为R1NF。 第一范式是对关系模式的最起码的要求。不满足第一范式 的数据库模式不能称为关系数据库。 但是满足第一范式的关系模式并不一定是一个好的关系模式,4.3.2 第二范式（2NF）,定义4.5：如果关系模式R1NF，且每个非主属性都完全函数依赖于主键，则称R属于第二范式，记为R2NF。 由定义可知，如果某个1NF的关系的主键只由一个属性组成或关系的全体属性均为主属性，那么这个关系就是2NF。如果主键是由多个属性列共同构成的复合主键，并且存在非主属性对主属性的部分函数依赖，则这个关系就不是2NF。,【例4-4】 对于关系S(Sno, Sname, Ssex, Sdept, Dean, Cno, Cname, Sorce)，主键为(Sno, Cno)。由于存在非主属性姓名（Sname）、性别（Ssex）、课程名（Cname）部分函数依赖于(Sno, Cno)，因此不属于2NF。 可以通过模式分解将非2NF的关系模式分解为多个满足2NF的关系模式。分解步骤如下： （1）首先用组成主键的属性集合的每个子集作为主键构成若干关系，对于关系S分解为如下3个子关系： S1(Sno, )，Sno为主键 S2(Cno, )，Cno为主键 S3(Sno, Cno, )，(Sno, Cno)为主键,（2）对于每个子关系，将依赖于此主键的属性放置到此关系中，则有： S1(Sno, Sname, Ssex, Sdept, Dean)，Sno为主键 S2(Cno, Cname)，Cno为主键 S3(Sno, Cno, Sorce)，(Sno, Cno)为主键 模式分解后，消除了原关系S中的部分函数依赖，即S1、S2、S3 3个关系模式都不存在部分函数依赖，S1、S2、S3都属于2NF。,分析一下S1存在的问题：,（1）数据冗余。 （2）插入异常。 （3）删除异常。 （4）修改复杂。 由此可见，满足第二范式的关系模式仍然可能出现数据冗余和操作异常。这是因为第二范式没有排除传递函数依赖。因此，还需要对满足第二范式的关系模式进行进一步分解。,4.3.3 第三范式（3NF）,定义4.6：如果关系模式R2NF，且所有非主属性都不传递函数依赖于任何候选键，则R3NF。,【例4-5】 分解例4-4中的关系S1，使其满足3NF的要求。 解：在关系S1中，院长（Dean）传递函数依赖于学号（Sno），即Sno Dean，所以S1不属于3NF。 将关系S1(Sno, Sname, Ssex, Sdept, Dean)进一步分解，消除传递依赖。分解步骤如下： （1）对于不是候选键的每个决定因素，从关系中删除依赖它的所有属性。 在关系S1中，学院（Sdept）不是候选键，但却是决定因素，从关系S1中删除依赖它的属性院长（Dean），得到新的关系S11(Sno, Sname, Ssex, Sdept)。 （2）新建一个关系，该关系中包含原关系中不是候选键的决定因素以及所有依赖该决定因素的属性，并将决定因素作为该关系的主键。对于关系S1，新建的关系为S12(Sdept, Dean)，主键为Sdept。 关系S1分解后消除了传递函数依赖，因此S11和S12都满足3NF。,4.3.4 BCNF,定义4.7：设关系模式R1NF，如果对于R的任意一个函数依赖XY，X必为候选键，则RBCNF。 等价于：每个决定属性集（因素）都包含（候选）码。 BCNF的关系模式都具有如下3个性质。 （1）所有非主属性都完全函数依赖于每个候选键。 （2）所有主属性都完全函数依赖于每个不包含它的候选键。 （3）没有任何属性完全函数依赖于非候选键的任何一组属性。,4.3.4 BCNF,若RBCNF 所有非主属性对每一个码都是完全函数依赖 所有的主属性对每一个不包含它的码，也是完全函数依赖 没有任何属性完全函数依赖于非码的任何一组属性 R BCNF R 3NF,4.3.4 BCNF,【例4-7】 分析关系模式T(Tno, Tname, Tsex)中，各属性分别代表教师号、教师姓名、性别。 解：T只有一个主键Tno，没有任何属性对Tno部分依赖或传递依赖，所以T3NF。同时Tno是T中唯一的决定因素，所以TBCNF。,4.3.4 BCNF,【例4-8】 分析关系模式STC(S, T, C)中，S表示学生，T表示教师，C表示课程。每一教师只教一门课。 解：每门课程有若干教师，某一学生选定某门课程，就对应一个固定的教师。由语义可得到函数依赖，如图4-1所示： (S,C)T, (S,T)C, TC,4.3.4 BCNF,该关系模式中，(S,C)和(S,T)都是候选键。 因为没有任何非主属性部分依赖和传递依赖于候选键所以STC3NF。但STC不是BCNF关系，因为T是决定因素，但它不是候选键(不满足第三条)。 STC可以分解为ST(S,T)与TC(T,C)，它们都是BCNF。 3NF和BCNF是对以函数依赖为基础的关系模式规范化程度的衡量标准。,3NF与BCNF的关系,R BCNF R 3NF 如果R3NF，且R只有一个候选码 R BCNF R 3NF,4.3.5 多值依赖与第四范式,1多值依赖 定义4.8：设有关系模式R(U)，X、Y、Z是U的子集，且Z=UXY。当且仅当R的任一关系r在（X、Z）上的每一个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关时，称Y多值依赖于X，记作XY。 如果XY，但Z=UXY=，则称XY为平凡的多值依赖，否则为非平凡的多值依赖。,4.3.5 多值依赖与第四范式,【例4-9】学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。,表4-4 关系模式Teach的一个关系实例,4.3.5 多值依赖与第四范式,TeachBCNF Teach具有唯一候选键(C，T，B)， 即全键 Teach模式中存在的问题 (1)数据冗余度大 (2)插入操作复杂 (3) 删除操作复杂 (4) 修改操作复杂,存在 多值依赖,4.3.5 多值依赖与第四范式,多值依赖具有以下性质： （1）替代性。若XY，则XY，即XY是XY的特例。 （2）对称性。若XY，则XUXY。 （3）传递性。若XY，YZ，则XZY。 （4）合并性。若XY，XZ，则XY Z。 （5）若XY，XZ，则XYZ。 （6）若XY，XZ，则XY-Z，XZ Y。,4.3.5 多值依赖与第四范式,2第四范式（4NF） 定义4.9：关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选键，则称R属于第四范式，记为R4NF。,4.3.5 多值依赖与第四范式,例4-9的关系模式Teach中，主键是(C,T,B)，即全键。CT，CB，它们都是非平凡的多值依赖，但C不是候选键，所以Teach不属于4NF。将Teach分解为T(C,T)和B(C,B)，虽然存在CT，CB，但它们是平凡的多值依赖，所以T4NF，B4NF，这样关系模式Teach存在的问题得到了较好地解决，如表4-5和表4-6所示。,表4-5 关系T 表4-6 关系B,4.3.5 多值依赖与第四范式,函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度是最高的；如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的。实际上，数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖，如连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖可由语义直接导出，而是在关系的连接运算时反映出来。存在连接依赖的关系模式仍然可能存在数据冗余、操作异常等问题。如果消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到满足5NF的关系模式。,4.3.6 关系模式的规范化,关系数据库的规范化理论是数据库逻辑设计的工具 目的：尽量消除插入、删除异常，修改复杂，数据冗余 基本思想：逐步消除数据依赖中不合适的部分 实质：概念的单一化,4.3.6 关系模式的规范化,一个关系模式的规范化过程如图4-2所示,图4-2 各种范式及规范化过程,4.3.6 关系模式的规范化,不能说规范化程度越高的关系模式就越好 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式 上面的规范化步骤可以在其中任何一步终止,1函数依赖集F的逻辑蕴含 定义4.10：对于满足一组函数依赖F的关系模式R(U,F)，其任何一个关系r，若函数依赖XY都成立（即r中任意两元组t、s，若tX=sX，则tY=sY），则称F逻辑蕴含XY。 如果考虑到F所蕴含（推导）的所有函数依赖，就有函数依赖集闭包的概念。 2函数依赖集闭包 定义4.11：所有被一个已知函数依赖集F逻辑蕴含的那些函数依赖的集合称为F的闭包（Closure），记为F+。 为了用一套系统的方法求F+，还必须遵循一组函数依赖的推理规则。,4.4.1 函数依赖集的闭包,1独立推理规则 独立规则是指下面给出的Armstrong公理的3条推理规则是彼此独立的。 （1）A1：自反律。 如果YX，则XY。 注意：由自反律得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。 （2）A2：增广律。 如果ZW且XY，则XZYZ。 （3）A3：传递律。 如果XY且YZ，则XZ。,4.4.2 函数依赖的推理规则,2其他推理规则 由3条独立推理规则，可得到3条推论 推论1：合并规则 若XY，XZ，有XYZ。 证明：由XY，可知XXY（增广律）；由XZ，知XYYZ（增广律），所以XYZ（传递律）。 推论2：分解规则。 若XY，Z Y，有XZ。 证明：由Z Y，可知YZ（自反律），又因为XY，所以XZ（传递律）。 推论3：伪传递规则。 若XY，WYZ，有XWZ。 证明：由XY，得到WXWY（增广律），又因为WYZ，所以有XWZ（传递律）。,真包含于,【例4-10】 设有关系模式R(A,B,C,D,E)及其上的函数依赖集F=ABCD,AB,DE，求证F必蕴含AE。 证明：AB （已知） AAB （增广律） ABCD （已知） ACD （传递律） AC，AD （分解规则） DE （已知） AE （传递律） 证毕,4.4.3 属性集的闭包及其算法,被决定属性的集合,4.4.3 属性集的闭包及其算法,4.4.3 属性集的闭包及其算法,定理4.2：Armstrong公理系统是正确的、完备的。 证明见教材,4.4.4 函数依赖推理规则的完备性,4.4.5 函数依赖集的等价、覆盖和最小函数依赖集,2最小函数依赖集的定义 定义4.14：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖： （1）F中任一函数依赖的右部仅含有一个属性。 （2）F中不存在函数依赖XA，使得F与FXA等价。 （3）F中不存在函数依赖XA，X有真子集Z使得FXAZA与F等价。 上述3个条件的作用分别如下： 条件（1）保证每个函数依赖的右部都不会有重复的属性。 条件（2）保证F中没有冗余的函数依赖。 条件（3）保证每个函数依赖的左部没有冗余的属性。 定义4.15：每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。,3最小函数依赖集的求解算法,把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义,三种模式分解等价的定义： 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性,4.5.1 模式分解的定义,定义4.16：关系模式R(U,F)的一个分解是指 = R1(U1 ,F1),R2(U2 ,F2),Rn(Un,Fn)，其中U=U1U2Un，并且没有Ui Uj（1i，jn），Fi是F在Ui上的投影，Fi = XY | XYF+XY Ui 。,4.5.2 分解的无损连接性,定义4.17：设F是关系模式R(U,F)的函数依赖集。,4.5.2 分解的无损连接性,算法4.2：判别一个分解的无损连接性。 = R1(U1,F1),R2(U2,F2),Rk(Uk,Fk)是R(U,F)的一个分解，U = A1,An，F = FD1, FD2,FD，设F是一个极小函数依赖集，记函数依赖FDi为XiAli。判别方法如下： （1）构造一张n列k行的表格。每列对应一个属性，每行对应分解中的一个关系模式。若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上b i j。 （2）对每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的行，考察这些行中li列的元素，若其中有ali，则全部改为ali，否则全部改为bmli（m是这些行的行号最小值）。 应当注意的是，若某个btli被更改，那么该表的li列中凡是btli的符号（不管它是否为开始找到的那些行）均应作相应的更改。 如在某次更改后，有一行成为a1,a2,an，则算法终止。具有无损连接性，否则不具有无损连接性。,按书本说明，有错,4.5.2 分解的无损连接性,定理4.3：为无损连接分解的充分必要条件是算法4.2终止时，表中有一行为a1,a2,an。 证明从略。,4.5.2 分解的无损连接性,【例4-13】 设有R(U,F)，其中，U = A, B, C, D, E，F = ABC, CD, DE，R的一个分解为R1(A, B, C)，R2(C, D)，R3(D, E), 该分解是否具有无损连接性?,4.5.2 分解的保持函数依赖性,4.5.4 关系模式分解的算法,4.5.4 关系模式分解的算法,4.5.4 关系模式分解的算法,4.5.4 关系模式分解的算法,本章主要介绍了关系规范化理论的内容，包括函数依赖及相关概念的定义、范式和规范化方法、数据依赖的公理系统、关系模式的分解等。 关系规范化理论是设计没有操作异常的关系数据库模式的基本原则，主要研究关系模式中各属性之间的依赖关系。范式是衡量模式优劣的标准，表达了模式中数据依赖之间应当满足的联系。对于函数依赖，考虑2NF、3NF或BCNF；对于多值依赖，考虑4NF。,一个数据库模式均包含若干个关系模式，而每个关系模式中都存在若干个函数依赖，每个关系模式的好坏标准是看其是否属于3NF和BCNF。如果一个数据库模式中的任一个关系模式都设计得理想，就是一个好的数据库模式。对于一个不理想的数据库模式，应将其关系模式分解，将低级范式的关系模式转换为若干个高级范式的关系模式的集合，使分解后的子关系模式都属于3NF或BCNF，且分解时应注意保持分解后的关系模式能够具有无损连接性并能保持原有的函数依赖关系。 规范化理论为数据库设计提供了理论指南和工具，目的是指导我们设计没有数据冗余和操作异常的关系模式。对于一般的数据库应用，设计到3NF就足够了，并不是规范化程度越高，模式就越好，应结合实际应用环境和现实世界的具体情况，合理地选择数据库模式。,