1、第第8 8章章 关系数据库的规范化理论关系数据库的规范化理论版权所有(C)-南京大学计算机科学与技术系q在关系数据库系统的建立过程中，如何构造一在关系数据库系统的建立过程中，如何构造一个合适的关系数据模式？个合适的关系数据模式？关系数据库的设计理论关系数据库的设计理论关系数据库的规范化理论关系数据库的规范化理论版权所有(C)-南京大学计算机科学与技术系q本章的内容本章的内容8.1 概述概述8.2 规范化理论规范化理论8.2.1 函数依赖函数依赖8.2.2 与函数依赖有关的范式与函数依赖有关的范式8.2.3 多值依赖与第四范式多值依赖与第四范式8.3 规范化所引起的一些问题规范化所引起的一些问题
2、函数依赖理论的研究函数依赖理论的研究模式分解的研究：无损联接性，依赖保持性模式分解的研究：无损联接性，依赖保持性版权所有(C)-南京大学计算机科学与技术系8.1 概述概述1 模式设计模式设计同一个数据库系统可以有多种不同的模式设计同一个数据库系统可以有多种不同的模式设计方案。方案。如：假设一个学生数据库中有如：假设一个学生数据库中有8个属性：个属性：S#,Sn,Sd,Sa,C#,G,CN,P#,可以采用的模式设计方案可以采用的模式设计方案有多个。如表有多个。如表8-1所示：所示：v方案方案1：一个关系：一个关系SCG(S#,Sn,Sd,Sa,C#,G,CN,P#)v方案方案2：三个关系：三个关
3、系S(S#,Sn,Sd,Sa)C(C#,CN,P#)SC(S#,C#,G)版权所有(C)-南京大学计算机科学与技术系8.1 概述概述2 不同模式设计方案的比较不同模式设计方案的比较不同的模式设计方案对数据库的影响是否相同？不同的模式设计方案对数据库的影响是否相同？例：例：根据方案根据方案1所建立的数据库如表所建立的数据库如表8-2所示所示根据方案根据方案2所建立的数据库如表所建立的数据库如表8-3所示所示我们从下面三个方面来比较这两个数据库：我们从下面三个方面来比较这两个数据库：数据冗余度数据冗余度元组插入操作元组插入操作元组删除操作元组删除操作版权所有(C)-南京大学计算机科学与技术系8.1
4、 概述概述S S#SnSn SdSd SaSa C C CnCn P P G G 0001 王剑飞王剑飞 CS 17 101 ABC 102 5 0001 王剑飞王剑飞 CS 17 102 ACD 105 5 0001 王剑飞王剑飞 CS 17 103 BBC 105 4 0001 王剑飞王剑飞 CS 17 105 AEF 107 3 0001 王剑飞王剑飞 CS 17 110 BCF 4 0002 陈陈 瑛瑛 MA 19 103 BBC 105 3 0002 陈陈 瑛瑛 MA 19 105 AEF 107 3 0003 方世觉方世觉 CS 17 107 BHD 110 4 表表8-2 根据方
5、案根据方案1所建立的数据库所建立的数据库(关系关系SCG)版权所有(C)-南京大学计算机科学与技术系8.1 概述概述S S#S Sn n S Sd d S Sa a 0001 王王剑剑飞飞 CS 17 0002 陈陈 瑛瑛 MA 19 0003 方方世世觉觉 CS 17 关关系系 S C C C C n n P P 1 0 1 A B C 1 0 2 1 0 2 A C D 1 0 5 1 0 3 B B C 1 0 5 1 0 5 A EF 1 0 7 1 0 7 B H D 11 0 11 0 B C F 关关 系系C S S#C C G G 0 0 0 1 1 0 1 5 0 0 0 1
6、 1 0 2 5 0 0 0 1 1 0 3 4 0 0 0 1 1 0 5 3 0 0 0 1 11 0 4 0 0 0 2 1 0 3 3 0 0 0 2 1 0 5 3 0 0 0 3 1 0 7 4 关关 系系S C 表表8-3 根据方案根据方案2所建立的数据库所建立的数据库(关系关系S,C和和SC)版权所有(C)-南京大学计算机科学与技术系8.1 概述概述q经过比较发现，表经过比较发现，表8-2具有如下缺点：具有如下缺点：数据冗余度大数据冗余度大 插入异常插入异常v如果需要新开设一门尚未有学生选修的课程如果需要新开设一门尚未有学生选修的课程(104,DB,103)，则无法构造出一个由
7、则无法构造出一个由S#,Sn,Sd,Sa等属性值所组成的新元组，在表等属性值所组成的新元组，在表8-2中中就无法执行元组的插入操作。就无法执行元组的插入操作。v在表在表8-3中，我们可以直接将元组中，我们可以直接将元组(104,DB,103)插入到课程关系插入到课程关系C中。中。版权所有(C)-南京大学计算机科学与技术系8.1 概述概述删除异常删除异常 在表在表8-2中，中，107号课程仅有号课程仅有0003号学生选修，如果该号学生选修，如果该学生因故退学，就必须将与该学生有关的元组从表学生因故退学，就必须将与该学生有关的元组从表8-2中删除掉，这样就必然也将中删除掉，这样就必然也将107号这
8、门课程也从数据号这门课程也从数据库中删除掉了。库中删除掉了。在表在表8-3中，我们可以仅在学生关系中，我们可以仅在学生关系S和选课关系和选课关系SC中删除中删除0003号学生的元组及其选课信息，但不会误删号学生的元组及其选课信息，但不会误删除掉除掉107号课程，其所对应的元组仍然保留在课程关号课程，其所对应的元组仍然保留在课程关系系C中。中。因此，不同的模式设计方案有好坏的区分。好的设计因此，不同的模式设计方案有好坏的区分。好的设计方案应该是：既具有合理的数据冗余度，又没有插入方案应该是：既具有合理的数据冗余度，又没有插入和删除等异常现象的出现。和删除等异常现象的出现。版权所有(C)-南京大学
9、计算机科学与技术系8.1 概述概述3 在不同的设计结果之间产生区别的原因在不同的设计结果之间产生区别的原因数据库的各属性之间是互相关联的，它们互相依赖、互数据库的各属性之间是互相关联的，它们互相依赖、互相制约，构成一个结构严密的整体。相制约，构成一个结构严密的整体。要设计出一个好的关系模式，必须从数据库中所有属性要设计出一个好的关系模式，必须从数据库中所有属性的语义上进行分析，从语义上入手分清每个属性的语义的语义上进行分析，从语义上入手分清每个属性的语义含义及其相互之间的依存关系。进而将那些相互依赖密含义及其相互之间的依存关系。进而将那些相互依赖密切的属性组合在一起构成一个关系模式，避免对属性
10、的切的属性组合在一起构成一个关系模式，避免对属性的松散组合所引起的松散组合所引起的排它性排它性，从而可以降低数据冗余，从而可以降低数据冗余度，避免上述异常现象的产生。度，避免上述异常现象的产生。版权所有(C)-南京大学计算机科学与技术系8.1 概述概述4 关系的规范化关系的规范化在一个关系中，属性与属性之间的内在语义联系有两种：在一个关系中，属性与属性之间的内在语义联系有两种：函数依赖函数依赖 多值依赖多值依赖关系的规范化关系的规范化 在每个关系中，属性与属性之间一定要满足某种内在在每个关系中，属性与属性之间一定要满足某种内在的语义联系，这被称为关系的的语义联系，这被称为关系的规范化规范化。根
11、据对属性间所存在的内在语义联系要求的不同，又根据对属性间所存在的内在语义联系要求的不同，又可以将关系的规范化分为若干个级别，这被称为可以将关系的规范化分为若干个级别，这被称为范式范式。上述相关的理论被称为关系规范化理论。上述相关的理论被称为关系规范化理论。版权所有(C)-南京大学计算机科学与技术系8.2 规范化理论规范化理论q 数据依赖理论数据依赖理论函数依赖（函数依赖（FD Functional Dependency）1970年，年，E.F.Codd 1972 1974年，年，Codd,Casey,Bernstein,Armstrong完全完全/部分部分FD，平凡平凡/非平凡非平凡FD，直接
12、直接/传递传递FD键（键（key）1974年，年，Armstrong公理系统公理系统FD的逻辑蕴涵的逻辑蕴涵FD的形式化推理规则集的形式化推理规则集多值依赖（多值依赖（MVD Multi-Valued Dependency）1976 1978年，年，Zaniolo,Fagin,Delobel版权所有(C)-南京大学计算机科学与技术系8.2 规范化理论规范化理论q 规范化理论规范化理论规范化的途径规范化的途径 竖向规范化竖向规范化采用采用投影投影和和联接联接运算运算将一个关系模式的属性集分解构成若干个关系模式将一个关系模式的属性集分解构成若干个关系模式有关理论构成了关系数据库的规范化理论有关理论
13、构成了关系数据库的规范化理论模式分解理论：模式分解理论：，水平规范化水平规范化采用采用选择选择和和并并运算运算将一个关系的元组集合分解成若干个子集，从而构将一个关系的元组集合分解成若干个子集，从而构成若干个与原来的关系具有相同关系模式的子关系成若干个与原来的关系具有相同关系模式的子关系尚未形成一个成熟的规范化理论尚未形成一个成熟的规范化理论版权所有(C)-南京大学计算机科学与技术系8.2 规范化理论规范化理论8.2.1 函数依赖函数依赖 函数依赖函数依赖完全完全/部分部分FD，平凡平凡/非平凡非平凡FD，直接直接/传递传递FD Armstrong公理系统公理系统 键（键（key）两个算法两个算
14、法属性集的闭包的计算属性集的闭包的计算关键字的计算关键字的计算8.2.2 与函数依赖有关的范式与函数依赖有关的范式 范式：范式：1NF，2NF，3NF，BCNF8.2.3 多值依赖与第四范式多值依赖与第四范式 多值依赖多值依赖与与MVD有关的推理规则有关的推理规则 4NF版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖例例1：在学生关系模式：在学生关系模式S(S#,Sn,Sd,Sa)中就存在下中就存在下面的几组依赖关系：面的几组依赖关系：Sn 的取值依赖于的取值依赖于 S#的取值的取值 Sd 的取值依赖于的取值依赖于 S#的取值的取值 Sa 的取值依赖于的取值依赖于 S#
15、的取值的取值q在一个关系模式在一个关系模式R(U)中，如果一部分属性中，如果一部分属性Y的取的取值依赖于另一部分属性值依赖于另一部分属性X的取值，则在属性集的取值，则在属性集X和和属性集属性集Y之间存在着一种数据依赖关系，我们称之间存在着一种数据依赖关系，我们称之为之为函数依赖函数依赖。版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖定义定义8.1：函数依赖函数依赖设有关系模式设有关系模式R(U)，U是关系模式是关系模式R的属性集合，的属性集合，X、Y是是U的子集。若对于任一个符合关系模式的子集。若对于任一个符合关系模式R(U)的关系的关系 r 中的任一元组中的任一元组
16、t 在在X中的属性值确定后，中的属性值确定后，则元组则元组 t 在在Y中的属性值也必确定，则称中的属性值也必确定，则称Y函数依函数依赖于赖于X，或者或者X函数决定函数决定Y，并记为并记为XY。其中：其中：X称为决定因素称为决定因素Y称为依赖因素称为依赖因素版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖定义定义8.1：函数依赖函数依赖(cont.)假设在关系模式假设在关系模式R(U)上存在函数依赖关系：上存在函数依赖关系：XY r 是依据关系模式是依据关系模式R(U)建立起来的任意一个关系，建立起来的任意一个关系，那么关系那么关系 r 必满足：必满足：从关系从关系 r 中
17、任取两个元组中任取两个元组t1和和t2，如果如果t1在在X这组这组属性上的取值属性上的取值t1X等于等于t2在在X这组属性上的取值这组属性上的取值t2X，即：即：t1X=t2X则它们在则它们在Y这组属性上的取值也必定相等，即：这组属性上的取值也必定相等，即：t1Y=t2Y版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖函数依赖是语义范畴上的概念，函数依赖是语义范畴上的概念，只有根据属性只有根据属性间固有的语义联系才能归纳出与客观事实相符间固有的语义联系才能归纳出与客观事实相符合的函数依赖关系，而不是仅从现有的一个或合的函数依赖关系，而不是仅从现有的一个或若干个关系实例中得
18、出的结论。若干个关系实例中得出的结论。S S#S Sn n S Sd d S Sa a 0001 王王 剑剑 飞飞 CS 17 0002 陈陈 瑛瑛 MA 19 0003 方方 世世 觉觉 CS 17 关关 系系 S 特定的关系实例虽然不能用于函数依赖的发现，特定的关系实例虽然不能用于函数依赖的发现，但可以用于否定某些函数依赖。但可以用于否定某些函数依赖。版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q例例 根据下列具体的关系实例，判断其中根据下列具体的关系实例，判断其中可能存在可能存在哪些函数依赖关系？哪些函数依赖关系？y2x6y2x5y1x4y1x3y2x2y1x1
19、BAT1AB?BA?y3x4y4x2y2x3y1x1y4x2y1x1BAT2AB?BA?y3x2y4x2y2x3y1x1y4x2y1x1BAT3AB?BA?版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q设有如下所示的关系设有如下所示的关系RABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4 其中可能成立的函数依赖关系有哪些？其中可能成立的函数依赖关系有哪些？其中又有哪些函数依赖关系是不可能成立的？其中又有哪些函数依赖关系是不可能成立的？版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q首先考虑决定因素和依赖因素都是单个属性的
20、情况：首先考虑决定因素和依赖因素都是单个属性的情况：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B A C A D B A B C B D C A C B C D D A D B D C 版权所有(C)-南京大学计算机科学与技术系其次，再考虑决定因素是多个属性的情况：其次，再考虑决定因素是多个属性的情况：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D C1)在在FD的左边不需要考虑含有属性的左边不需要考虑含有属性 D 的情况，的情况，why?2)在在FD的左边不需要考虑含有属性的左边不需要考虑含有属性 B
21、 的情况，的情况，why?AC B?AC D?因此只需要考虑下述的因此只需要考虑下述的FD是否成立：是否成立：版权所有(C)-南京大学计算机科学与技术系ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D Cq因此，最后只需要考虑下面的一个因此，最后只需要考虑下面的一个FD是否可能成立？是否可能成立？AC D?q在上述的在上述的FD关系中，我们不用考虑关系中，我们不用考虑 AC B，why?AC B?AC D?版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q该关系上可能存在的函数依赖：该关系上可能存在的函数依赖：ABC
22、Da1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D CAC D版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q函数依赖反映的是同一个关系中的两个属性子集函数依赖反映的是同一个关系中的两个属性子集之间在取值上的依存关系，这种依存关系实际上之间在取值上的依存关系，这种依存关系实际上也是一种数据完整性约束。因此，我们也可以通也是一种数据完整性约束。因此，我们也可以通过对数据完整性约束条件的分析来寻找属性之间过对数据完整性约束条件的分析来寻找属性之间的函数依赖关系。的函数依赖关系。例例3：有一个学生关系：有一个学生关系R(S#,S
23、n,Sd,Ss,C#,G)，其中其中Ss表示学生所学专业。该关系模式中的语表示学生所学专业。该关系模式中的语义约束如下：义约束如下：v每个学生每个学生均只属一个系与一个专业均只属一个系与一个专业v每个学生修读之每门课有且仅有一个成绩每个学生修读之每门课有且仅有一个成绩v各系无相同专业各系无相同专业版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q例例3：有一个学生关系：有一个学生关系R(S#,Sn,Sd,Ss,C#,G)，其中其中Ss表示学生所学专业。该关系模式中的语义表示学生所学专业。该关系模式中的语义约束如下：约束如下：【基本常识】每个学生有唯一的一个学号，每个【基本
24、常识】每个学生有唯一的一个学号，每个学生只有一个姓名学生只有一个姓名S#Sn每个学生均只属一个系与一个专业每个学生均只属一个系与一个专业S#SdS#Ss每个学生修读之每门课有且仅有一个成绩每个学生修读之每门课有且仅有一个成绩(S#，C#)G各系无相同专业各系无相同专业Ss Sd版权所有(C)-南京大学计算机科学与技术系定义定义8.2：平凡：平凡/非平凡函数依赖非平凡函数依赖 一个函数依赖关系一个函数依赖关系XY如满足如满足Y X，则称则称此函数依赖是此函数依赖是非平凡的函数依赖非平凡的函数依赖。否则，我。否则，我们称其为们称其为平凡函数依赖平凡函数依赖。如无特殊声明，凡提到函数依赖时总认为指如
25、无特殊声明，凡提到函数依赖时总认为指的是非平凡的函数依赖的是非平凡的函数依赖。8.2.1 函数依赖函数依赖版权所有(C)-南京大学计算机科学与技术系定义定义8.3：完全函数依赖：完全函数依赖 在关系模式在关系模式R(U)中，如有中，如有X U，Y U，满足满足XY，且对任何且对任何X的真子集的真子集X 都有都有XY，则则称称Y完全函数依赖于完全函数依赖于X，并记作：并记作：X YX Y定义定义8.4：部分函数依赖：部分函数依赖在关系模式在关系模式R(U)中，如有中，如有X U，Y U，满足满足XY，但但Y Y不完全函数依赖于不完全函数依赖于X X，则称则称Y Y部分依部分依赖于赖于X X，并记
26、作：并记作：X YX Y8.2.1 函数依赖函数依赖pf版权所有(C)-南京大学计算机科学与技术系v同样也会有同样也会有(S#，Sn)Sd(S#，Sa)Sdpp8.2.1 函数依赖函数依赖q例如：在学生例如：在学生S(S#,Sn,Sd,Ss,C#,G)中中我们有：我们有：S#Sd我们有：我们有：S#SdSs Sdv同样也会有同样也会有(S#，Ss)Sdp版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q定义定义8.5：传递函数依赖：传递函数依赖在关系模式在关系模式R(U)中，如有中，如有X U，Y U，Z U且满足：且满足：XYXY，Y Y X X，YXYX，YZYZ，则
27、称则称Z Z传递传递函数依赖函数依赖于于X X；否则，称为否则，称为非传递（直接）函数非传递（直接）函数依赖依赖。为了使得函数依赖在表示形式上的简单化，传为了使得函数依赖在表示形式上的简单化，传递函数依赖与非传递函数依赖在表示形式上没递函数依赖与非传递函数依赖在表示形式上没有区别。有区别。版权所有(C)-南京大学计算机科学与技术系例如：例如：在学生关系中增加一个属性在学生关系中增加一个属性系的电话号码系的电话号码DtS(S#,Sn,Sd,Ss,C#,G,Dt)每个系只登记唯一的一个电话号码，则我们有：每个系只登记唯一的一个电话号码，则我们有：SdDt8.2.1 函数依赖函数依赖 由由 S#Sd
28、 和和 SdDt 可得到传递可得到传递FD：S#Dt 由由 S#Ss 和和 SsSd 可得到传递可得到传递FD：S#Sd版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖qArmstrong公理系统公理系统有关函数依赖的六条推理规则有关函数依赖的六条推理规则基本规则（基本规则（3条）条）扩充规则（扩充规则（3条）条）FD的逻辑蕴涵概念的逻辑蕴涵概念函数依赖集函数依赖集F的闭包：的闭包：F+版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q基本推理规则基本推理规则规则规则R1：自反规则自反规则如果如果Y是是X的子集，则：的子集，则：X YX Y证明
29、：证明：设设t1,t2是关系是关系R中的两个元组中的两个元组(t1 R,t2 R),且它们在属性集且它们在属性集X上的值相等上的值相等(t1X=t2X)由于由于Y是是X的子集，即的子集，即X Y 因此必有因此必有t1Y=t2Y证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q基本推理规则基本推理规则规则规则R2：增广规则增广规则如果如果X Y，则：则：XZ YZ证明：证明：设设 t1 R,t2 R,如果如果 t1XZ=t2XZ,则：则：t1X=t2X(1)t1Z=t2Z(2)由由(1)及及XY得：得：t1Y=t2Y(3)由由(2)及及(3)得：得：t1YZ
30、=t2YZ证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q基本推理规则基本推理规则规则规则R3：传递规则传递规则如果如果X Y，Y Z，则：则：X Z证明：证明：设设 t1 R,t2 R,如果如果 t1X=t2X(1)由由(1)及及XY得：得：t1Y=t2Y.(2)由由(2)及及YZ得：得：t1Z=t2Z证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q扩充推理规则扩充推理规则规则规则R4：分解规则分解规则如果如果X YZ，则：则：X Y证明：证明：由自反规则由自反规则R1得：得：YZY 由由XYZ,YZY,根据传递
31、规则根据传递规则R3得得:XY证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q扩充推理规则扩充推理规则规则规则R5：合并规则合并规则如果如果X Y且且X Z，则：则：X YZ证明：证明：使用增广规则使用增广规则R2可作如下推导：可作如下推导：由由XY可得：可得：XXXY 即即 XXY(1)由由XZ可得：可得：XYYZ (2)由由(1),(2)根据传递规则根据传递规则R3可得可得:XYZ证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q扩充推理规则扩充推理规则规则规则R6：伪传递规则伪传递规则如果如果X Y且且WY Z
32、，则：则：WX Z证明：证明：使用增广规则使用增广规则R2，由由XY可得：可得：WXWY(1)(1)使用传递规则使用传递规则R3，由由(1)及及 WYZ 可得可得:WXZ证毕证毕.版权所有(C)-南京大学计算机科学与技术系Armstrong公理系统公理系统q 课后练习课后练习：请利用：请利用Armstrong公理系统证明下面的推导过公理系统证明下面的推导过程是否成立？如果不成立，请给出具体的例子关系。程是否成立？如果不成立，请给出具体的例子关系。1.WY,XZ WXY 2.XY and Z Y XZ 3.XY,XW,WYZ XZ 4.XYZ,YW XWZ 5.XZ,YZ XY 6.XY,XYZ
33、 XZ 7.XY,ZW XZYW 8.XYZ,ZX ZY 9.XY,YZ XYZ 10.XYZ,ZW XW 版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖qFD的逻辑蕴涵概念的逻辑蕴涵概念设设 F 是关系模式是关系模式 R(U)的一个函数依赖集，的一个函数依赖集，X,Y 是关系模式是关系模式 R 的属性子集，如果从的属性子集，如果从 F 中的已有中的已有函数依赖关系利用函数依赖关系利用 Armstrong 公理系统能够推公理系统能够推出出 XY，则称则称 F 逻辑蕴涵逻辑蕴涵 XY，并记为：并记为：F XYq函数依赖集函数依赖集 F 的闭包的闭包 F+由被由被 F 逻辑
34、蕴涵的所有函数依赖关系构成的集合逻辑蕴涵的所有函数依赖关系构成的集合被称为函数依赖集被称为函数依赖集 F 的闭包，并记为的闭包，并记为 F+F+=XY F XY 版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 计算函数依赖集计算函数依赖集 F=AB,BC 的闭包的闭包 F+F中的所有函数依赖都是其闭包中的元素，即：中的所有函数依赖都是其闭包中的元素，即：AB F+BC F+根据自反规则，下述函数依赖也是其闭包中的元素根据自反规则，下述函数依赖也是其闭包中的元素AA BB CCABA ABB ABABACA ACC ACACBCB BCC BCBCABCA ABCB A
35、BCCABCAB ABCAC ABCBCABCABC版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖由由AB,BC及传递规则可得到闭包中的下列元素及传递规则可得到闭包中的下列元素AC由由AB,AC及合并规则可得到闭包中的下列元素及合并规则可得到闭包中的下列元素ABC 由由AB及增广规则可得到闭包中的下列元素及增广规则可得到闭包中的下列元素AAB ACBC ACABC 由由BC及增广规则可得到闭包中的下列元素及增广规则可得到闭包中的下列元素ABAC BBC ABABC 由由AC及增广规则可得到闭包中的下列元素及增广规则可得到闭包中的下列元素AAC ABBC 由由ABC及增广
36、规则可得到闭包中的下列元素及增广规则可得到闭包中的下列元素AABC版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖由由ABB,BC及传递规则可得到闭包中的下及传递规则可得到闭包中的下列元素列元素ABC由由ACA,AB及传递规则可得到闭包中的下及传递规则可得到闭包中的下列元素列元素ACB由由ACB及增广规则可得到闭包中的下列元素及增广规则可得到闭包中的下列元素ACAB版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q定义定义8.6：关键字（也称为关键字（也称为 码码 或或 key）在关系模式在关系模式 R(U,F)中，如有中，如有 K U 且满足：且满
37、足：K U则称则称 K 为为 R 的关键字的关键字。f 几种不同的关键字几种不同的关键字v候选关键字候选关键字v主关键字主关键字v全关键字全关键字版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖定义定义8.7：主属性主属性(集集)由关系模式由关系模式 R 的所有关键字中的属性所构成的的所有关键字中的属性所构成的集合被称为关系模式集合被称为关系模式 R 的的 主属性集主属性集主属性集中的属性被称为关系模式主属性集中的属性被称为关系模式 R 的的 主属性主属性定义定义8.8：非主属性非主属性(集集)由主属性集之外的其它属性所构成的集合被称为由主属性集之外的其它属性所构成的集合
38、被称为关系模式关系模式 R 的的 非主属性集非主属性集非主属性集中的属性被称为关系模式非主属性集中的属性被称为关系模式 R 的的 非主非主属性属性版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q如何寻找如何寻找一个关系模式一个关系模式R(U,F)的关键字？的关键字？fK U方法一方法一：利用：利用Armstrong公理系统中的推导规公理系统中的推导规则，从已知的函数依赖集则，从已知的函数依赖集F中推导得到如下的函中推导得到如下的函数依赖关系：数依赖关系：缺点：缺点：依赖于对推导规则的熟练使用依赖于对推导规则的熟练使用版权所有(C)-南京大学计算机科学与技术系8.2.1
39、函数依赖函数依赖q如何寻找如何寻找一个关系模式一个关系模式R(U,F)的关键字？的关键字？方法二方法二：根据关键字的定义及属性集闭包的概念，：根据关键字的定义及属性集闭包的概念，计算能够满足条件（计算能够满足条件（KF+=U）的最小属性集合的最小属性集合K算法算法8-1,8-2方法三方法三：先计算函数依赖集：先计算函数依赖集F的最小覆盖（的最小覆盖（即与即与F相等价的最小函数依赖集相等价的最小函数依赖集），然后根据函数依），然后根据函数依赖的特性以及关键字的定义来寻找关系的关键字赖的特性以及关键字的定义来寻找关系的关键字可缩短算法可缩短算法8-2的计算过程的计算过程版权所有(C)-南京大学计算
40、机科学与技术系8.2.1 函数依赖函数依赖q习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(1)R(A,B,C,D)，F:BD,ABC 解：解：由由 BD 及增广规则及增广规则 R2 可得：可得：ABAD(1)(1)由由(1),ABC 及合并规则及合并规则 R5 可得可得:ABACD(2)由由(2)及增广规则及增广规则 R2 可得：可得：ABABCD完完.版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(2)R(A,B,C)，F:AB,BA,AC 解解1：由由 AB,AC 及合并规则及合并规则 R
41、5 可得：可得：ABC 由由 ABC 及增广规则及增广规则 R2 可得：可得：AABC完完.解解2：由由 BA,AC 及传递规则及传递规则 R3 可得：可得：BC 由由 BA,BC 及合并规则及合并规则 R5 可得：可得：BAC 由由 BAC 及增广规则及增广规则 R2 可得可得 BABC完完.版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(3)R(A,B,C)，F:AC,DB 解：解：由由 AC 及增广规则及增广规则 R2 可得：可得：ADCD(1)(1)由由 DB 及增广规则及增广规则 R2 可得：可得：
42、ADAB(2)(2)由由(1),(2)及合并规则及合并规则 R5 可得：可得：ADABCD完完.版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(4)R(A,B,C,D)，F:AC,CDB 解：解：由由 AC 及增广规则及增广规则 R2 可得：可得：ADCD(1)(1)由由(1),CDB 及传递规则及传递规则 R3 可得：可得：ADB 由由 ADB 及增广规则及增广规则 R2 可得：可得：ADAB(2)(2)由由(1),(2)及合并规则及合并规则 R5 可得：可得：ADABCD完完.版权所有(C)-南京大学计算
43、机科学与技术系8.2.1 函数依赖函数依赖q属性集的闭包属性集的闭包 XF+（可以简写为可以简写为 X+）设设 F 是关系模式是关系模式 R(U)上的函数依赖集，上的函数依赖集，X 是关是关系模式系模式 R(U)的属性子集，由所有函数依赖于的属性子集，由所有函数依赖于 X 的属性所构成的集合被称为属性集的属性所构成的集合被称为属性集 X 在函数依在函数依赖集赖集 F 上的闭包。上的闭包。X+=A F XA 版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖算法算法8-1：计算属性集：计算属性集X在函数依赖集在函数依赖集F上的闭包上的闭包XF+(简写为简写为X+）X+:=X;
44、repeatoldX+:=X+;for each functional dependency YZ in F doif Y X+then X+:=X+Z;until(oldX+=X+)版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q例：设例：设 F=(f1)BCD,(f2)ADE,(f3)BA，请计算请计算 BF+?BF+=B 第一遍循环第一遍循环1)X=BF+=B 2)f1 的决定因素是的决定因素是BF+的一个子集，所以的一个子集，所以BF+=BF+C,D=B,C,D2)f2 的决定因素不是的决定因素不是BF+的子集的子集,因此因此 f2 不影响本次不影响本次循环的计
45、算结果循环的计算结果3)f3 的决定因素是的决定因素是BF+的一个子集，所以的一个子集，所以BF+=BF+A=A,B,C,D4)X BF+,回到步骤回到步骤1)开始执行第二遍循环开始执行第二遍循环版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖 第二遍循环第二遍循环1)X=BF+=A,B,C,D 2)跳过在第一遍循环中已经处理过的函数依赖跳过在第一遍循环中已经处理过的函数依赖3)f2 的决定因素是的决定因素是BF+的子集的子集,所以所以BF+=BF+E=A,B,C,D,E4)X BF+,回到步骤回到步骤1)开始执行第三遍循环开始执行第三遍循环 第三遍循环第三遍循环1)X=
46、BF+=A,B,C,D,E2)F中的所有函数依赖都已处理过（其依赖因素都已经被并中的所有函数依赖都已处理过（其依赖因素都已经被并入到入到 BF+中）中）3)因此在本次循环中因此在本次循环中BF+将不再发生变化，算法执行结束将不再发生变化，算法执行结束 返回返回 BF+版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 关键字关键字 K 与属性集闭包与属性集闭包 XF+概念之间的关系概念之间的关系 设设 F 是关系模式是关系模式 R(U)上的函数依赖集，上的函数依赖集，K 是是关系模式关系模式 R(U)的一个关键字，则：的一个关键字，则：1)KF+=U2)对于对于 K 的任
47、意一个真子集的任意一个真子集 K，都有：都有：KF+U版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(1)R(A,B,C,D)，F:BD,ABC;解：解：由由 BD 及增广规则及增广规则 R2 可得：可得：ABAD(1)由由(1),ABC 及合并规则及合并规则 R5 可得可得:ABACD(2)由由(2)及增广规则及增广规则 R2 可得：可得：ABABCD 因为：因为：(对方法一计算结果的验证对方法一计算结果的验证)A F+=A A,B,C,D B F+=B,D A,B,C,D 所以所以(A,B)是关系模式是
48、关系模式 R 的一个关键字。的一个关键字。完完.版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖算法算法8-2：寻找关系模式：寻找关系模式 R(U,F)的关键字的关键字 K1.set K:=R;2.for each attribute A in Kcompute(K A)F+;if (K A)F+contains all the attributes in R,thenset K:=K A ;版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(2)R(A,B,C)，F:AB,BA,AC;解
49、解1：K=A,B,C KA+=A,B,C=U K=KA=B,C KB+=C U 该关键字中必定含有属性该关键字中必定含有属性 B KC+=A,B,C=U K=KC=B最后得到该关系的一个关键字最后得到该关系的一个关键字 B 解解2：K=A,B,C KB+=A,B,C=U K=KB=A,C KA+=C U 该关键字中必定含有属性该关键字中必定含有属性 A KC+=A,B,C=U K=KC=A最后得到该关系的另一个关键字最后得到该关系的另一个关键字 A 版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 习题：习题：寻找下述关系模式的关键字寻找下述关系模式的关键字(4)R(A
50、,B,C,D)，F:AC,CDB 解解1：K=A,B,C,D KA+=A,B,C U 该关键字中必定含有属性该关键字中必定含有属性 A KB+=A,B,C,D=U K=KB=A,C,D KC+=A,B,C,D=U K=KC=A,D KD+=A,C U 该关键字中必定含有属性该关键字中必定含有属性 D最后得到该关系的一个关键字最后得到该关系的一个关键字 A,D 版权所有(C)-南京大学计算机科学与技术系8.2.1 函数依赖函数依赖q 习题习题8.6：关系模式关系模式 函数依赖集函数依赖集 关键字关键字 主属性集主属性集 非主属性非主属性集集 (1)(1)R(A,B,C,D)BD ABC A,B
