【文档说明】数据库系统实用教程-课件.ppt，共(137)页，650.000 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-92491.html

以下为本文档部分文字说明：

第8章关系数据库的规范化理论版权所有(C)-南京大学计算机科学与技术系2在关系数据库系统的建立过程中，如何构造一个合适的关系数据模式？关系数据库的设计理论关系数据库的规范化理论版权所有(C)-南京大学计算机科学与技术系3本章的内容8.1概述

8.2规范化理论8.2.1函数依赖8.2.2与函数依赖有关的范式8.2.3多值依赖与第四范式8.3规范化所引起的一些问题函数依赖理论的研究模式分解的研究：无损联接性，依赖保持性版权所有(C)-南京大学计算机

科学与技术系48.1概述1模式设计同一个数据库系统可以有多种不同的模式设计方案。如：假设一个学生数据库中有8个属性：S#,Sn,Sd,Sa,C#,G,CN,P#,可以采用的模式设计方案有多个。如表8-1所示：方案1：一个关系SCG(S#,Sn,Sd,Sa,C#,G,CN,P#)方案2

：三个关系S(S#,Sn,Sd,Sa)C(C#,CN,P#)SC(S#,C#,G)版权所有(C)-南京大学计算机科学与技术系58.1概述2不同模式设计方案的比较不同的模式设计方案对数据库的影响是否相同？例：根据方案1所建立的数据库如表8-2所

示根据方案2所建立的数据库如表8-3所示我们从下面三个方面来比较这两个数据库：数据冗余度元组插入操作元组删除操作版权所有(C)-南京大学计算机科学与技术系68.1概述S#SnSdSaC＃CnP＃G0001王剑飞CS17101ABC10250001王剑飞CS17102ACD105500

01王剑飞CS17103BBC10540001王剑飞CS17105AEF10730001王剑飞CS17110BCF40002陈瑛MA19103BBC10530002陈瑛MA19105AEF10730003方世觉CS17107BHD1104表8-2根据方案1所建立的数据库(关系SCG)版权所

有(C)-南京大学计算机科学与技术系78.1概述S#SnSdSa0001王剑飞CS170002陈瑛MA190003方世觉CS17关系SC＃CnP＃101ABC102102ACD105103BBC105105AEF107107BHD110110BCF关系CS#C＃G000110150001102

5000110340001105300011104000210330002105300031074关系SC表8-3根据方案2所建立的数据库(关系S,C和SC)版权所有(C)-南京大学计算机科学与技术系88.1概述经过比较发现，表8-2

具有如下缺点：数据冗余度大插入异常如果需要新开设一门尚未有学生选修的课程(104,DB,103)，则无法构造出一个由S#,Sn,Sd,Sa等属性值所组成的新元组，在表8-2中就无法执行元组的插入操作。在表8-3中，我们可以直接将元组(104,DB,103)插入到课程关系C中。版权所有(C)

-南京大学计算机科学与技术系98.1概述删除异常在表8-2中，107号课程仅有0003号学生选修，如果该学生因故退学，就必须将与该学生有关的元组从表8-2中删除掉，这样就必然也将107号这门课程也从数据库中删除掉了。

在表8-3中，我们可以仅在学生关系S和选课关系SC中删除0003号学生的元组及其选课信息，但不会误删除掉107号课程，其所对应的元组仍然保留在课程关系C中。因此，不同的模式设计方案有好坏的区分。好的设计方案应该是：既具有合

理的数据冗余度，又没有插入和删除等异常现象的出现。版权所有(C)-南京大学计算机科学与技术系108.1概述3在不同的设计结果之间产生区别的原因数据库的各属性之间是互相关联的，它们互相依赖、互相制约，构成一个结构严密的整体。要设计出一个好的关系模式，必须从数据库中所有属性的语义上

进行分析，从语义上入手分清每个属性的语义含义及其相互之间的依存关系。进而将那些相互依赖密切的属性组合在一起构成一个关系模式，避免对属性的松散组合所引起的‘排它性’，从而可以降低数据冗余度，避免上述异常现象的产生。版权所有(C)-南京大学计算

机科学与技术系118.1概述4关系的规范化在一个关系中，属性与属性之间的内在语义联系有两种：函数依赖多值依赖关系的规范化在每个关系中，属性与属性之间一定要满足某种内在的语义联系，这被称为关系的规范化。根据对属性间所存在的内在语义联系要求的不同，又可以将关系的规范化分为若干

个级别，这被称为范式。上述相关的理论被称为关系规范化理论。版权所有(C)-南京大学计算机科学与技术系128.2规范化理论数据依赖理论函数依赖（FD–FunctionalDependency）1970年，

E.F.Codd1972–1974年，Codd,Casey,Bernstein,Armstrong–完全/部分FD，平凡/非平凡FD，直接/传递FD–键（key）1974年，Armstrong公理系统–FD的逻辑蕴涵–FD的形式化推理规则集多值依赖（MVD–Multi-

ValuedDependency）1976–1978年，Zaniolo,Fagin,Delobel版权所有(C)-南京大学计算机科学与技术系138.2规范化理论规范化理论规范化的途径竖向规范化–采用‘投影’和‘联接’运算–将

一个关系模式的属性集分解构成若干个关系模式–有关理论构成了关系数据库的规范化理论–模式分解理论：无损联接性，依赖保持性水平规范化–采用‘选择’和‘并’运算–将一个关系的元组集合分解成若干个子集，从而构成若干

个与原来的关系具有相同关系模式的子关系–尚未形成一个成熟的规范化理论版权所有(C)-南京大学计算机科学与技术系148.2规范化理论8.2.1函数依赖函数依赖–完全/部分FD，平凡/非平凡FD，直接/传递FDArmstrong公理系统键（key）两个算法–属性集的闭包的计算–关键字的计

算8.2.2与函数依赖有关的范式范式：1NF，2NF，3NF，BCNF8.2.3多值依赖与第四范式多值依赖–与MVD有关的推理规则4NF版权所有(C)-南京大学计算机科学与技术系158.2.1函数依赖例1：

在学生关系模式S(S#,Sn,Sd,Sa)中就存在下面的几组依赖关系：{Sn}的取值依赖于{S#}的取值{Sd}的取值依赖于{S#}的取值{Sa}的取值依赖于{S#}的取值在一个关系模式R(U)

中，如果一部分属性Y的取值依赖于另一部分属性X的取值，则在属性集X和属性集Y之间存在着一种数据依赖关系，我们称之为函数依赖。版权所有(C)-南京大学计算机科学与技术系168.2.1函数依赖定义8.1：函数依赖设有关系模式R(U)，U是关系模式R的属性集合，X

、Y是U的子集。若对于任一个符合关系模式R(U)的关系r中的任一元组t在X中的属性值确定后，则元组t在Y中的属性值也必确定，则称Y函数依赖于X，或者X函数决定Y，并记为X→Y。其中：X称为决定因素Y称为依赖因素版权所有(C)-南京大学计算机科学与技术系178.2.1函数依赖定义8.1：函

数依赖(cont.)假设在关系模式R(U)上存在函数依赖关系：X→Yr是依据关系模式R(U)建立起来的任意一个关系，那么关系r必满足：从关系r中任取两个元组t1和t2，如果t1在X这组属性上的取值t1[X]等于t2在X这组属性上的取

值t2[X]，即：t1[X]=t2[X]则它们在Y这组属性上的取值也必定相等，即：t1[Y]=t2[Y]版权所有(C)-南京大学计算机科学与技术系188.2.1函数依赖函数依赖是语义范畴上的概念，只有根据属性间固有的语义联系才能归纳出与客观事实相符合的函数依赖关系，而不是仅从现有的一个或若干

个关系实例中得出的结论。S#SnSdSa0001王剑飞CS170002陈瑛MA190003方世觉CS17关系S特定的关系实例虽然不能用于函数依赖的发现，但可以用于否定某些函数依赖。版权所有(C)-南京大学计算机科学与技术系198.2.1函

数依赖[例]根据下列具体的关系实例，判断其中可能存在哪些函数依赖关系？y2x6y2x5y1x4y1x3y2x2y1x1BAT1A→B?B→A?y3x4y4x2y2x3y1x1y4x2y1x1BAT2A→B?B→A?y3x2y4x2y2x3y1x1y

4x2y1x1BAT3A→B?B→A?☓☓版权所有(C)-南京大学计算机科学与技术系208.2.1函数依赖设有如下所示的关系RABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4其中可能成立的函数依赖关系有哪些？其

中又有哪些函数依赖关系是不可能成立的？版权所有(C)-南京大学计算机科学与技术系218.2.1函数依赖首先考虑决定因素和依赖因素都是单个属性的情况：ABCDa1b1c1d1a1b1c2d2a2b1c1d

3a2b1c3d4A→BA→CA→DB→AB→CB→DC→AC→BC→DD→AD→BD→C☓☓☓☓☓☓☓√√√√√版权所有(C)-南京大学计算机科学与技术系22其次，再考虑决定因素是多个属性的情况：ABCDa1b1c1d1a1b

1c2d2a2b1c1d3a2b1c3d4A→BC→BD→AD→BD→C1)在FD的左边不需要考虑含有属性D的情况，why?2)在FD的左边不需要考虑含有属性B的情况，why?AC→B?AC→D?因此只需要考虑下述的FD是否成立：版权所有(C)-南京

大学计算机科学与技术系23ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→BC→BD→AD→BD→C因此，最后只需要考虑下面的一个FD是否可能成立？AC→D?在上述的FD关系中，我

们不用考虑AC→B，why?AC→B?AC→D?√版权所有(C)-南京大学计算机科学与技术系248.2.1函数依赖该关系上可能存在的函数依赖：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→BC→BD→

AD→BD→CAC→D版权所有(C)-南京大学计算机科学与技术系258.2.1函数依赖函数依赖反映的是同一个关系中的两个属性子集之间在取值上的依存关系，这种依存关系实际上也是一种数据完整性约束。因此，我们也可以通过对数据完整性约束条件的分析来寻找属性之间的函数依赖关系。例

3：有一个学生关系R(S#,Sn,Sd,Ss,C#,G)，其中Ss表示学生所学专业。该关系模式中的语义约束如下：每个学生均只属一个系与一个专业每个学生修读之每门课有且仅有一个成绩各系无相同专业版权所有(C)-南京大学计算机科学与技术系268.2.1函数依赖例3：有一个学生关系R(S#,S

n,Sd,Ss,C#,G)，其中Ss表示学生所学专业。该关系模式中的语义约束如下：【基本常识】每个学生有唯一的一个学号，每个学生只有一个姓名S#→Sn每个学生均只属一个系与一个专业S#→SdS#→Ss每个学生修读之每门课有且仅有一个

成绩(S#，C#)→G各系无相同专业Ss→Sd版权所有(C)-南京大学计算机科学与技术系27定义8.2：平凡/非平凡函数依赖一个函数依赖关系X→Y如满足YX，则称此函数依赖是非平凡的函数依赖。否则，我们称其为平凡函数依赖。如无特殊声明，凡提到函数依赖时总认为指的是非平凡的函数依赖。8

.2.1函数依赖版权所有(C)-南京大学计算机科学与技术系28定义8.3：完全函数依赖在关系模式R(U)中，如有XU，YU，满足X→Y，且对任何X的真子集X'都有X'→Y，则称Y完全函数依赖于X，并记作：XY定义8.4：部分函数依赖在关系模式R(U)中，如有XU，Y

U，满足X→Y，但Y不完全函数依赖于X，则称Y部分依赖于X，并记作：XY8.2.1函数依赖pf版权所有(C)-南京大学计算机科学与技术系29同样也会有(S#，Sn)Sd(S#，Sa)Sdpp8.2.1函数依赖例如：在学生S(S#,Sn,Sd,Ss,C#,G)中我们有：S#→Sd我们有：S

#→SdSs→Sd同样也会有(S#，Ss)Sdp版权所有(C)-南京大学计算机科学与技术系308.2.1函数依赖定义8.5：传递函数依赖在关系模式R(U)中，如有XU，YU，ZU且满足：X→Y，YX，Y→X，Y→Z，则称Z传递函数依赖于X；否

则，称为非传递（直接）函数依赖。为了使得函数依赖在表示形式上的简单化，传递函数依赖与非传递函数依赖在表示形式上没有区别。版权所有(C)-南京大学计算机科学与技术系31例如：在学生关系中增加一个属性‘系的电话号码Dt’S(S#,Sn,S

d,Ss,C#,G,Dt)每个系只登记唯一的一个电话号码，则我们有：Sd→Dt8.2.1函数依赖由S#→Sd和Sd→Dt可得到传递FD：S#→Dt由S#→Ss和Ss→Sd可得到传递FD：S#→Sd版权所有(C)-南京大学计算机科学与技术系328.2.1函数依赖Arms

trong公理系统有关函数依赖的六条推理规则基本规则（3条）扩充规则（3条）FD的逻辑蕴涵概念函数依赖集F的闭包：F+版权所有(C)-南京大学计算机科学与技术系33Armstrong公理系统基本推理规则规则R1：自反规则如果Y是X的子集，则：X→Y证明：设t1,t2是关系R中

的两个元组(t1R,t2R),且它们在属性集X上的值相等(t1[X]=t2[X])由于Y是X的子集，即XY因此必有t1[Y]=t2[Y]证毕.版权所有(C)-南京大学计算机科学与技术系34Armstrong公理系统基本推理规则规则R2：增广规则如果X→Y，则：XZ→YZ

证明：设t1R,t2R,如果t1[XZ]=t2[XZ],则：t1[X]=t2[X]…………………………………(1)t1[Z]=t2[Z]…………………………………(2)由(1)及X→Y得：t1[Y]=t2[Y]……………

……(3)由(2)及(3)得：t1[YZ]=t2[YZ]证毕.版权所有(C)-南京大学计算机科学与技术系35Armstrong公理系统基本推理规则规则R3：传递规则如果X→Y，Y→Z，则：X→Z证明：设t1R,t2R,如果t1[X]=

t2[X]………………(1)由(1)及X→Y得：t1[Y]=t2[Y]………………...(2)由(2)及Y→Z得：t1[Z]=t2[Z]证毕.版权所有(C)-南京大学计算机科学与技术系36Armstrong公理系统扩充推理规则规则R4：分解规则如果X→YZ，则：X→Y证明：

由自反规则R1得：YZ→Y由X→YZ,YZ→Y,根据传递规则R3得:X→Y证毕.版权所有(C)-南京大学计算机科学与技术系37Armstrong公理系统扩充推理规则规则R5：合并规则如果X→Y且X→Z

，则：X→YZ证明：使用增广规则R2可作如下推导：•由X→Y可得：XX→XY即X→XY…………(1)•由X→Z可得：XY→YZ……………………(2)由(1),(2)根据传递规则R3可得:X→YZ证毕.版权所有(C)-南京大学计算

机科学与技术系38Armstrong公理系统扩充推理规则规则R6：伪传递规则如果X→Y且WY→Z，则：WX→Z证明：使用增广规则R2，由X→Y可得：WX→WY…………………………………(1)使用传递规则R3，由(1)及WY→Z可得:W

X→Z证毕.版权所有(C)-南京大学计算机科学与技术系39Armstrong公理系统课后练习：请利用Armstrong公理系统证明下面的推导过程是否成立？如果不成立，请给出具体的例子关系。1.{WY,XZ}{WXY}2.{XY}andZY{XZ}3.{XY,XW,W

YZ}{XZ}4.{XYZ,YW}{XWZ}5.{XZ,YZ}{XY}6.{XY,XYZ}{XZ}7.{XY,ZW}{XZYW}8.{XYZ,ZX}{ZY}9.{XY,YZ}{XYZ}10.{XYZ,ZW}{XW}版权所

有(C)-南京大学计算机科学与技术系408.2.1函数依赖FD的逻辑蕴涵概念设F是关系模式R(U)的一个函数依赖集，X,Y是关系模式R的属性子集，如果从F中的已有函数依赖关系利用Armstrong公理系统能够推出X→Y，则称F逻辑蕴涵X→Y，并

记为：FX→Y函数依赖集F的闭包F+由被F逻辑蕴涵的所有函数依赖关系构成的集合被称为函数依赖集F的闭包，并记为F+F+={X→Y│FX→Y}版权所有(C)-南京大学计算机科学与技术系418.2.1函数依赖计算函数依赖集F={A→B,B→C}的闭包F+

F中的所有函数依赖都是其闭包中的元素，即：A→B∈F+B→C∈F+根据自反规则，下述函数依赖也是其闭包中的元素A→AB→BC→CAB→AAB→BAB→ABAC→AAC→CAC→ACBC→BBC→CBC→BCABC→AABC→BABC→CABC→AB

ABC→ACABC→BCABC→ABC版权所有(C)-南京大学计算机科学与技术系428.2.1函数依赖由A→B,B→C及传递规则可得到闭包中的下列元素A→C由A→B,A→C及合并规则可得到闭包中的下列元素A→BC由A→B及增广规则可得到闭包中的下列元素A→ABAC→BCAC→ABC

由B→C及增广规则可得到闭包中的下列元素AB→ACB→BCAB→ABC由A→C及增广规则可得到闭包中的下列元素A→ACAB→BC由A→BC及增广规则可得到闭包中的下列元素A→ABC版权所有(C)-南京大学计算机科学与技术系438.2.

1函数依赖由AB→B,B→C及传递规则可得到闭包中的下列元素AB→C由AC→A,A→B及传递规则可得到闭包中的下列元素AC→B由AC→B及增广规则可得到闭包中的下列元素AC→AB版权所有(C)-南京大学计算机科学与技术系448.2.

1函数依赖定义8.6：关键字（也称为码或key）在关系模式R(U,F)中，如有KU且满足：KU则称K为R的关键字。f几种不同的关键字候选关键字主关键字全关键字版权所有(C)-南京大学计算机科学与技术系458.2.1函数依赖定义8.7：主属性(集)由关系模式R的所有关键

字中的属性所构成的集合被称为关系模式R的主属性集主属性集中的属性被称为关系模式R的主属性定义8.8：非主属性(集)由主属性集之外的其它属性所构成的集合被称为关系模式R的非主属性集非主属性集中的属性被称

为关系模式R的非主属性版权所有(C)-南京大学计算机科学与技术系468.2.1函数依赖如何寻找一个关系模式R(U,F)的关键字？fKU方法一：利用Armstrong公理系统中的推导规则，从已知的函数依赖集F中推导得到如下的函数依赖关系：

缺点：依赖于对推导规则的熟练使用版权所有(C)-南京大学计算机科学与技术系478.2.1函数依赖如何寻找一个关系模式R(U,F)的关键字？方法二：根据关键字的定义及属性集闭包的概念，计算能够满足条件（KF+=U）的最小属性集合K算法8-1,8-2方法三：先计算函数依赖集F的

最小覆盖（即与F相等价的最小函数依赖集），然后根据函数依赖的特性以及关键字的定义来寻找关系的关键字可缩短算法8-2的计算过程版权所有(C)-南京大学计算机科学与技术系488.2.1函数依赖习题：寻找下述关系模式的关键字(1)R(A,B,C,D)，F:{BD,ABC}解：由B→D及

增广规则R2可得：AB→AD……(1)由(1),AB→C及合并规则R5可得:AB→ACD…………………………………(2)由(2)及增广规则R2可得：AB→ABCD完.版权所有(C)-南京大学计算机科学与技术系498.2.1函数依赖习题：寻找下述关系模式

的关键字(2)R(A,B,C)，F:{AB,BA,AC}解1：由A→B,A→C及合并规则R5可得：A→BC由A→BC及增广规则R2可得：A→ABC完.解2：由B→A,A→C及传递规则R3可得：B→C由B→A,B→C及合并规则R5

可得：B→AC由B→AC及增广规则R2可得B→ABC完.版权所有(C)-南京大学计算机科学与技术系508.2.1函数依赖习题：寻找下述关系模式的关键字(3)R(A,B,C)，F:{AC,DB}解：由A→C及增广规则R2可得：AD→CD……(1)由D→B及增广规则R2可得：

AD→AB……(2)由(1),(2)及合并规则R5可得：AD→ABCD完.版权所有(C)-南京大学计算机科学与技术系518.2.1函数依赖习题：寻找下述关系模式的关键字(4)R(A,B,C,D)，F:{AC,CDB}解：由

A→C及增广规则R2可得：AD→CD……(1)由(1),CD→B及传递规则R3可得：AD→B由AD→B及增广规则R2可得：AD→AB…………………………………(2)由(1),(2)及合并规则R5可得：AD→ABCD完.版权所有(C)-南京大学计算

机科学与技术系528.2.1函数依赖属性集的闭包XF+（可以简写为X+）设F是关系模式R(U)上的函数依赖集，X是关系模式R(U)的属性子集，由所有函数依赖于X的属性所构成的集合被称为属性集X在函数

依赖集F上的闭包。X+={A│FX→A}版权所有(C)-南京大学计算机科学与技术系538.2.1函数依赖算法8-1：计算属性集X在函数依赖集F上的闭包XF+(简写为X+）X+:=X;repeatoldX+:=X+;foreachfunctionaldep

endencyYZinFdoifYX+thenX+:=X+Z;until(oldX+=X+)版权所有(C)-南京大学计算机科学与技术系548.2.1函数依赖例：设F={(f1)B→CD,(f2)AD

→E,(f3)B→A}，请计算{B}F+?{B}F+={B}第一遍循环1)X={B}F+={B}2)f1的决定因素是{B}F+的一个子集，所以{B}F+={B}F+∪{C,D}={B,C,D}2)f2的决定因素不是{B}F+的子集,因此f2不影响本次循环的计算结果3)f3

的决定因素是{B}F+的一个子集，所以{B}F+={B}F+∪{A}={A,B,C,D}4)X{B}F+,回到步骤1)开始执行第二遍循环版权所有(C)-南京大学计算机科学与技术系558.2.1函数依赖第二遍循环1)X={B

}F+={A,B,C,D}2)跳过在第一遍循环中已经处理过的函数依赖3)f2的决定因素是{B}F+的子集,所以{B}F+={B}F+∪{E}={A,B,C,D,E}4)X{B}F+,回到步骤1)开始执行第三遍循环第三遍循环1)X={B}F+={A,B,C,D,E}2)F中的所有函数依赖都已处

理过（其依赖因素都已经被并入到{B}F+中）3)因此在本次循环中{B}F+将不再发生变化，算法执行结束返回{B}F+版权所有(C)-南京大学计算机科学与技术系568.2.1函数依赖关键字K与属性集闭包XF+概念之间的关系设F是关系模式R(U)上的

函数依赖集，K是关系模式R(U)的一个关键字，则：1)KF+=U2)对于K的任意一个真子集K’，都有：K’F+U版权所有(C)-南京大学计算机科学与技术系578.2.1函数依赖习题：寻找下述关系模式的关键字(1)R(A,B,C,D)，F

:{BD,ABC};解：由B→D及增广规则R2可得：AB→AD………(1)由(1),AB→C及合并规则R5可得:AB→ACD……………………………………(2)由(2)及增广规则R2可得：AB→ABCD因为：(对方法一计算结果的验证){

A}F+={A}{A,B,C,D}{B}F+={B,D}{A,B,C,D}所以(A,B)是关系模式R的一个关键字。完.版权所有(C)-南京大学计算机科学与技术系588.2.1函数依赖算法8-2：寻找关系模式R(U,F)的关键字K1.set

K:=R;2.foreachattributeAinK{compute(K–A)F+;if(K–A)F+containsalltheattributesinR,then{setK:=K–{A};}}版权所有(C)-南京大学计算机科学与技术系598.2.1函数依赖习题

：寻找下述关系模式的关键字(2)R(A,B,C)，F:{AB,BA,AC};解1：K={A,B,C}∵{K–A}+={A,B,C}=U∴K=K–A={B,C}∵{K–B}+={C}U∴该关键字中必

定含有属性B∵{K–C}+={A,B,C}=U∴K=K–C={B}最后得到该关系的一个关键字{B}解2：K={A,B,C}∵{K–B}+={A,B,C}=U∴K=K–B={A,C}∵{K–A}+={C}

U∴该关键字中必定含有属性A∵{K–C}+={A,B,C}=U∴K=K–C={A}最后得到该关系的另一个关键字{A}版权所有(C)-南京大学计算机科学与技术系608.2.1函数依赖习题：寻找下述关系模式的关键字(4)R(A,B,C,D)，F:{AC,CDB}解1：K={

A,B,C,D}∵{K–A}+={A,B,C}U∴该关键字中必定含有属性A∵{K–B}+={A,B,C,D}=U∴K=K–B={A,C,D}∵{K–C}+={A,B,C,D}=U∴K=K–C={A,D}∵{K–D}+={A,C}U∴该关键字中必定含有属

性D最后得到该关系的一个关键字{A,D}版权所有(C)-南京大学计算机科学与技术系618.2.1函数依赖习题8.6：关系模式函数依赖集关键字主属性集非主属性集(1)R(A,B,C,D)BDABC{A,B}A,BC,D(

2)R(A,B,C)ABBAAC{A}{B}A,BC(3)R(A,B,C,D)ACDB{A,D}A,DB,C(4)R(A,B,C,D)ACCDB{A,D}A,DB,C版权所有(C)-南京大学计算机科学与技术系628.2规范化理论8.2.1函数依赖8.2.2与函数依赖有关

的范式范式及模式分解方法–1NF–2NF–3NF–BCNF8.2.3多值依赖与第四范式版权所有(C)-南京大学计算机科学与技术系638.2.2与函数依赖有关的范式定义：第一范式（1NF）如果关系模式R(U)中的每个属性值都是一个不可分割的数据量，则称该关系

模式满足第一范式，并记为：R1NF定义8.9：第二范式(2NF)设有关系模式R(U)∈1NF，且其每个非主属性都完全函数依赖于关键字，则称关系模式R(U)满足第二范式，并记作：R∈2NF版权所有(C)-南京大学计算机科学与技术系648.2.2与函数

依赖有关的范式例：有一个学生关系SCG(S#,Sn,Sd,Ss,C#,G)，根据用户给定的语义约束得到如下的函数依赖关系：基本常识：S#→Sn每个学生均只属一个系与一个专业；S#→SdS#→Ss每个学生修读之每门课有且仅有一个成绩；(S#，C#)→G各系

无相同专业。Ss→Sd版权所有(C)-南京大学计算机科学与技术系658.2.2与函数依赖有关的范式关系模式SCG(S#,Sn,Sd,Ss,C#,G)，函数依赖集为：S#→Sn,S#→Sd,S#→Ss,(S#,C#)→G,Ss→Sd该关系模式是否满足第二范式的要求？1

)找出该关系模式的所有(候选)关键字2)据此确定该关系的主属性集和非主属性集3)判断每一个非主属性和关键字之间的函数依赖关系是否满足2NF的要求。如果不存在非主属性对关键字的部分依赖，那么SCG2NF(S#,C#)主属性集：

{S#,C#}非主属性集：{Sn,Sd,Ss,G}版权所有(C)-南京大学计算机科学与技术系668.2.2与函数依赖有关的范式关系模式SCG(S#,Sn,Sd,Ss,C#,G)，函数依赖集为：S#→Sn,S#→Sd,S#→Ss,(S#，C#)→G,Ss→Sd关系模式SCG只能满足到1NF

采用SCG(S#,Sn,Sd,Ss,C#,G)的模式设计方案（仅满足1NF的关系模式）会带来什么样的问题？数据冗余因数据冗余而产生更新异常为什么出现数据冗余现象？非主属性对关键字的部分函数依赖如何避免上述的数据冗余现象？按照更高范式的要求设计关系模式：模式分解版权所有

(C)-南京大学计算机科学与技术系678.2.2与函数依赖有关的范式S#SnSdSsC＃G0001王剑飞CS软件10150001王剑飞CS软件10250001王剑飞CS软件10340002张军CS应用10130002张军CS应用10340003陈瑛CS应用

10330003陈瑛CS应用10430004方世觉CS软件1034图1：根据关系模式SCG所建立的数据库（仅满足1NF）版权所有(C)-南京大学计算机科学与技术系688.2.2与函数依赖有关的范式为了使最终的模式设计结果能够满

足到2NF，我们可以对关系SCG进行模式分解，将其属性集合分解构成若干个小的关系模式。随着对原有关系模式的分解，原来在关系模式SCG上存在的函数依赖集合也被分解到若干个小的关系模式上去。模式分解的目标–使

得分解得到的每个小的关系模式都能够满足2NF的要求。版权所有(C)-南京大学计算机科学与技术系698.2.2与函数依赖有关的范式模式分解设在关系模式R上成立的函数依赖集为F,Head(R)是由关系R中的所有属性所构成的属性

集合。如果存在一组子关系模式{R1,R2,…,Rk}满足下述的两个条件，则我们称{R1,R2,…,Rk}是关系模式R的一个分解(Decomposition)1)Head(R)=Head(R1)∪Head(R2)∪…∪Head(Rk)2)设子关系Ri

上的函数依赖集为Fi(i=1,2,…,k),则：Fi={XYXYF+且(X∪Y)Head(Ri)}版权所有(C)-南京大学计算机科学与技术系708.2.2与函数依赖有关的范式关系的规范化过

程就是一个不断进行模式分解的过程。通过模式分解可以消除原有关系模式中那些不好的函数依赖关系（即不满足更高范式要求的函数依赖关系），以尽可能地解决原有模式中所存在的数据冗余和各种插入、删除异常现象。版权所有(C)-南京大学计算机科学

与技术系718.2.2与函数依赖有关的范式模式分解的方法设存在一个关系模式R,其属性集合为Head(R),F是其函数依赖集。将其分解到满足范式M的步骤如下：1)找出所有不满足范式M要求的函数依赖关系2)选择一

个不符合要求的函数依赖关系作如下的分解：•假设XYF+且不满足范式M的要求，则我们将关系模式R分解为如下的两个子关系：»R1(XY,{XY})»R2(Head(R)–Y,F2)，其中：F2={ABA

BF+且(A∪B)Head(R2)}f版权所有(C)-南京大学计算机科学与技术系728.2.2与函数依赖有关的范式模式分解的方法3)对于分解得到的子关系模式R2重复上述的步骤1)和步骤2)，直到所有的子关系模式都能满

足范式M的要求4)合并那些具有相同关键字的子关系模式版权所有(C)-南京大学计算机科学与技术系738.2.2与函数依赖有关的范式利用前面介绍的分解方法对关系模式SCG进行规范化（分解到满足2NF）f不符合2NF要求的函数依赖关系具有以下特征：XY

，Y是关系SCG的非主属性，而X则是其某个候选关键字的真子集函数依赖集Ff1:S#→Snf2:S#→Sdf3:S#→Ssf4:(S#,C#)→Gf5:Ss→Sd非主属性集{Sn,Sd,Ss,G}主属性集{S#,C#}关键字K(S#,C#)版权所有(

C)-南京大学计算机科学与技术系748.2.2与函数依赖有关的范式分解过程(1)在关系SCG(U={S#,Sn,Sd,Ss,C#,G})中找出所有不满足2NF要求的函数依赖f1:S#→Snf2:S#→Sdf3:S#→Ss从中选择一个函

数依赖(f1)进行模式分解，分解结果如下：R1(U1={S#,Sn},F1={f1:S#→Sn})R0(U0=U–{Sn}={S#,Sd,Ss,C#,G},F0={f2:S#→Sd,f3:S#→Ss,f4:(S#,C#)→G,f5:S

s→Sd})版权所有(C)-南京大学计算机科学与技术系758.2.2与函数依赖有关的范式分解过程(2)在关系R0(U0={S#,Sd,Ss,C#,G},F0)中找出所有不满足2NF要求的函数依赖f2:S#→

Sdf3:S#→Ss从中选择一个函数依赖(f2)进行模式分解，分解结果如下：R2(U2={S#,Sd},F2={f2:S#→Sd})R0(U0=U–{Sd}={S#,Ss,C#,G},F0={f3:S#→Ss,f4:(

S#,C#)→G})版权所有(C)-南京大学计算机科学与技术系768.2.2与函数依赖有关的范式分解过程(3)在关系R0(U0={S#,Ss,C#,G},F0)中找出所有不满足2NF要求的函数依赖f3:S#→Ss从中选择一个

函数依赖(f3)进行模式分解，分解结果如下：R3(U3={S#,Ss},F3={f3:S#→Ss})R0(U0=U–{Ss}={S#,C#,G},F0={f4:(S#,C#)→G})版权所有(C)-南京大学计算机科学与技术系778.2.2与函数依赖有关的

范式综合前面的分解结果R1(U1={S#,Sn},F1={f1:S#→Sn})R2(U2={S#,Sd},F2={f2:S#→Sd})R3(U3={S#,Ss},F2={f3:S#→Ss})R0(U0=U–{Ss}={S#,C#,G},F0={f4:(S#,C#)→G})所有的子关系模式都已经

满足2NF版权所有(C)-南京大学计算机科学与技术系788.2.2与函数依赖有关的范式合并关键字相同的子关系模式后得到如下的分解结果SCG1(S#,C#,G),其函数依赖集是：{f4:(S#,C#)→G}SCG2(S

#,Sn,Sd,Ss),其函数依赖集是：{f1:S#→Sn,f2:S#→Sd,f3:S#→Ss,f5:Ss→Sd}版权所有(C)-南京大学计算机科学与技术系798.2.2与函数依赖有关的范式S#SnSdSs0001王剑

飞CS软件0002张军CS应用0003陈瑛CS应用0004方世觉CS软件关系SCG2图2：根据关系模式SCG1和SCG2所建立的数据库（可以满足到2NF）S#C＃G000110150001102500011034000210130002

1034000310330003104300041034关系SCG1版权所有(C)-南京大学计算机科学与技术系808.2.2与函数依赖有关的范式在关系SCG2中仍然存在数据冗余以及因此而产生的更新异常现象原

因：存在非主属性对关键字的传递依赖S#SnSdSs0001王剑飞CS软件0002张军CS应用0003陈瑛CS应用0004方世觉CS软件关系SCG2版权所有(C)-南京大学计算机科学与技术系818.2.2与函数依赖有关的范式

定义8.10：第三范式(3NF)设有关系模式R(U)∈2NF，且其每个非主属性都不传递函数依赖于关键字，则称关系模式R(U)满足第三范式，并记作：R∈3NF不符合3NF要求的函数依赖关系具有如下特征：XY，Y是关系SCG的非主属性，而X并不是关键字

，或者X只是关键字的一个真子集f版权所有(C)-南京大学计算机科学与技术系828.2.2与函数依赖有关的范式分解到满足3NFSCG1({S#,C#,G},{(S#,C#)→G})已满足3NFSCG2({

S#,Sn,Sd,Ss},{S#→Sn,S#→Ss,Ss→Sd})关键字：S#存在非主属性Sd对关键字的传递依赖：S#→Ss,Ss→S#,Ss→Sd⊨S#→Sd版权所有(C)-南京大学计算机科学与技术系83

8.2.2与函数依赖有关的范式分解到满足3NFSCG2(S#,Sn,Sd,Ss)的分解结果如下：SCG21(S#,Sn,Ss),其函数依赖集是：{S#→Sn,S#→Ss}SCG22(Sd,Ss

),其函数依赖集是：{Ss→Sd}版权所有(C)-南京大学计算机科学与技术系848.2.2与函数依赖有关的范式S#SnSs0001王剑飞软件0002张军应用0003陈瑛应用0004方世觉软件关系SCG21图3：符合3NF要求的模式设

计S#C＃G0001101500011025000110340002101300021034000310330003104300041034关系SCG1SdSsCS软件CS应用关系SCG22版权所有(C)-南

京大学计算机科学与技术系858.2.2与函数依赖有关的范式定义8.11：BCNF设关系模式R(U)满足1NF，且若XY时X必含有该关系模式的关键字，则称关系模式R(U)满足BCNF范式，并记作：R∈BCNF版权所有(C)-南京大学计算机科学与技术系868.2.2与函数依赖有关

的范式例8.1设有关系模式R(S,C,T)，其中S,C含义同前,T表示教师，R有下列语义信息：每个教师仅上一门课T→C学生与课程确定后，教师即惟一确定(S,C)→T思考题：1.关系模式R的关键字是什么？2.关系模式R的主属性集是什么？非主属性集

又是什么？3.该关系模式R最高能够满足到第几范式？版权所有(C)-南京大学计算机科学与技术系878.2.2与函数依赖有关的范式3.关系R最高能够满足到第几范式？R({S,C,T},{T→C,(S,C)→T})候选关键字：{S,C}和{S,T}思考题答案1.有两个候选关键字：{S,

C}和{S,T}2.主属性集是：{S，C，T}其主属性集为{S,C,T}，非主属性集为空（不存在非主属性），因此该关系模式中不存在不满足2NF和3NF范式要求的函数依赖，因此该关系模式一定可以满足到3NF。版权所有(C)-南京大学计算机科学与技术系888.2.2与函数依赖有

关的范式关系模式R是否能够满足BCNF？R({S,C,T},{T→C,(S,C)→T})候选关键字：{S,C}和{S,T}存在不满足BCNF要求的函数依赖:T→C因此不满足BCNF分解到满足BCNF

范式R1(C,T)函数依赖集：{T→C}R2(S,T)函数依赖集：{}版权所有(C)-南京大学计算机科学与技术系898.2.2与函数依赖有关的范式定理8-1如果关系模式R(U)BCNF，则R(U)3NF证明：假设R(U)3NF,则有三种可能性：(2)假设存在一个非主属性A

部分依赖于关键字K，即：KA（AK）由部分依赖的定义可知：必存在K的某个真子集K’，且满足：K’→A（AK’）由R(U)BCNF及BCNF定义可知：K’中必含有关键字，即关键字K中含有另一个关键字K’，且K’K，这与关键字的定义相矛盾。p(1

)假设R(U)1NF由R(U)BCNF可知：R(U)1NF。与假设相矛盾。版权所有(C)-南京大学计算机科学与技术系908.2.2与函数依赖有关的范式(3)假设存在一个非主属性A传递依赖于关键字K，即存在一个属性集合B，并满足：K→B，

BK，B→K，B→A由B→A及R(U)BCNF可知：B中必含有关键字K’由关键字的定义可知：K’→U因为BK’,KU，故B→K。这与B→K相矛盾。综上所述，假设不成立，即R(U)3NF证毕.版权所有(C)-南京大学计算机科学与技术系918.2规范化理论8

.2.1函数依赖8.2.2与函数依赖有关的范式8.2.3多值依赖与第四范式多值依赖–与MVD有关的推理规则4NF版权所有(C)-南京大学计算机科学与技术系928.2.3多值依赖与第四范式1.一个多值依赖的例子【例子8.2】设有一个课程关系R，其

示意图用表8.5表示。此表表示‘高等数学’这门课（C）的任课教师（T）有3个，它的参考书（L）可以有2本；‘普通物理’这门课（C）的任课教师（T）也有3个，它的参考书（L）可以有3本。如用关系的形式表示，如表8.6所示。课程名C教师名T选用参考书L高等数学

李华民王天华林静高等数学高等数学教程普通物理吴铁钢谢晓芳徐秋芳物理学普通物理普通物理基础表8.5关系R的示意图版权所有(C)-南京大学计算机科学与技术系938.2.3多值依赖与第四范式缺点数据大量冗余

存储CTLCTL高等数学李华民高等数学普通物理吴铁钢物理学高等数学李华民高等数学教程普通物理吴铁钢普通物理高等数学王天华高等数学普通物理吴铁钢普通物理基础高等数学王天华高等数学教程普通物理谢晓芳物理学高等数学林静高等数学普通

物理谢晓芳普通物理高等数学林静高等数学教程普通物理谢晓芳普通物理基础普通物理徐秋芳物理学普通物理徐秋芳普通物理普通物理徐秋芳普通物理基础表8.6关系R版权所有(C)-南京大学计算机科学与技术系948.2.3多值依赖与第四范式特点一个C

的值与一组T的值相对应这组T的值与其它属性（L）的值无关CTLCTL高等数学李华民高等数学普通物理吴铁钢物理学高等数学李华民高等数学教程普通物理吴铁钢普通物理高等数学王天华高等数学普通物理吴铁钢普通物理基础高等数学王天华高等数学教程普通物理谢晓芳物理学高等数学林静高等数学普通物理谢晓芳

普通物理高等数学林静高等数学教程普通物理谢晓芳普通物理基础普通物理徐秋芳物理学普通物理徐秋芳普通物理普通物理徐秋芳普通物理基础表8.6关系R版权所有(C)-南京大学计算机科学与技术系958.2.3多值依赖与

第四范式特点一个C的值与一组T的值相对应‘高等数学’对应‘李华民，王天华，林静’‘普通物理’对应‘吴铁钢，谢晓芳，徐秋芳’这组T的值与该关系中的其它属性（L）的值无关。即：设t1,t2是关系R中的两个元组(t1R,t2R)，且t1

[C]=t2[C]，则互换这两个元组在属性L上的取值所构成的两个新的元组：t3：(t1[C],t1[T],t2[L])t4：(t2[C],t2[T],t1[L])也必定是关系R中的元组(t3R,t4R)。在这里并没有区别t1,t2,t3,t4是不

是相同的元组。版权所有(C)-南京大学计算机科学与技术系968.2.3多值依赖与第四范式2.定义8-12：多值依赖(MVD)设有关系模式R(U)，X,Y是U的子集(X,YU)，若对R(U)的任何一个关系r，对X的一个确定值，存在Y的一组值与之对应，且Y的这组值又与Z=U-X-

Y中的属性值不相关，此时称Y多值依赖于X，并记为X→→Y。多值依赖产生的原因在一个关系模式中，若存在两个相互独立的属性之间的‘一对多’函数对应关系，如：–C与T的‘一对多’函数对应关系–C与L之间的

‘一对多’函数对应关系而T和L之间又没有任何依赖关系，此时若把它们合并起来构成一个关系，即R(C,T,L)，则就会产生多值依赖现象。版权所有(C)-南京大学计算机科学与技术系978.2.3多值依赖与第四范式由例8.2我们可以看到：若存在两个元组(表8.6的第1和第3个

元组),它们在C上的取值相同(高等数学)，但在T上的值不同(李华民,王天华)，那么对于T的每个值，都必须重复地与同这个C上的值相关的L上的每个值(高等数学,高等数学教程)相匹配，因此在关系T内出现了一个多值属性，产生了数据冗余。T李华民王天华林静C高等数学L高等数学高等数学教

程RDB因为1NF的要求而产生了多值依赖版权所有(C)-南京大学计算机科学与技术系988.2.3多值依赖与第四范式3非平凡的多值依赖【定义】设在关系模式R(U)中，X→→Y且U-X-Y，则称X→→Y是非平凡的多值依赖，否则称为平凡的多值依赖。【例】在关

系模式S(S#,Sn,Sd)中，三个属性分别是学号、姓名和学生所在的系。请问：1)在该关系模式中存在哪些MVD？2)如果存在MVD，请指出是平凡的MVD，还是非平凡的MVD？版权所有(C)-南京大学计算机科学与技术系998.2.3多值依赖与第四范式存在

的MVD有：S#→→SnS#→→SdS#→→(Sn,Sd)Sn→→(S#,Sd)Sd→→(S#,Sn)(S#,Sn)→→Sd(S#,Sd)→→Sn(Sn,Sd)→→S#1)S#→→Sn4)Sn→→S#7)Sd→→S#10)(S#,S

n)→→Sd2)S#→→Sd5)Sn→→Sd8)Sd→→Sn11)(S#,Sd)→→Sn3)S#→→(Sn,Sd)6)Sn→→(S#,Sd)9)Sd→→(S#,Sn)12)(Sn,Sd)→→S#红颜色是非平凡多值依赖，其

它的为平凡多值依赖版权所有(C)-南京大学计算机科学与技术系1008.2.3多值依赖与第四范式习题8.2在关系SC(S#,C#,G)中S#C#正确吗？请说明其理由。版权所有(C)-南京大学计算机科学与技术系1018.2.3多值依赖与第四范式4.多值依赖的性质在一个关系模式R

(U)中，如有X→→Y，则必有X→→(U-X-Y)如有X→Y，则必有X→→Y版权所有(C)-南京大学计算机科学与技术系1028.2.3多值依赖与第四范式【思考题】在学生关系模式S(S#,Sn,Ss,Sd)中，属性之间的语

义约束要求同前，请问在该关系中存在哪些不是函数依赖的非平凡的MVD？【答案】Ss→→(S#,Sn)S#→SnS#→SdS#→SsSs→Sd版权所有(C)-南京大学计算机科学与技术系1038.2.3多值依赖与

第四范式有关函数依赖(FD)和多值依赖(MVD)的推导规则关系模式R(U)，X，Y，Z，W是U的子集规则IR1：自反规则如果Y是X的子集，则：X→Y规则IR2：增广规则如果X→Y，则：XZ→YZ规则IR3：传递

规则如果X→Y，Y→Z，则：X→Z规则IR4：求补规则如果X→→Y，则X→→(U-X-Y)版权所有(C)-南京大学计算机科学与技术系1048.2.3多值依赖与第四范式规则IR5：多值依赖的增广规则如果X→→Y且WZ，则WX→→YZ证明：设t1R

,t2R,如果t1[WX]=t2[WX],则：………(1)t1[W]=t2[W]…..………………………………(2)t1[X]=t2[X]……………………………………(3)由(2)和WZ得：t1[Z]=t2

[Z]…………………(4)由(3)和X→→Y得：(t1[X],t1[Y],t2[U-X-Y])R(t2[X],t2[Y],t1[U-X-Y])R版权所有(C)-南京大学计算机科学与技术系1058.2.3多值依赖与第四范式将

W中的属性从(U-X-Y)中移至X之前，将Z中的属性从(U-X-Y)中移至Y之后得：(t2[W],t1[X],t1[Y],t2[Z],t2[U-X-Y-W-Z])R(t1[W],t2[X],t2[Y],t1[Z],t1[U-X-Y-W-Z])R(5)由(3),(4),(5)可得：

(t1[W],t1[X],t1[Y],t1[Z],t2[U-X-Y-W-Z])R(t2[W],t2[X],t2[Y],t2[Z],t1[U-X-Y-W-Z])R即：(t1[WX],t1[YZ],t2[U-WX-YZ])R(t2[WX],t2[YZ],

t1[U-WX-YZ])R(6)由(1)和(6)可知：WX→→YZ版权所有(C)-南京大学计算机科学与技术系1068.2.3多值依赖与第四范式规则IR6：多值依赖的传递规则如果X→→Y，Y→→Z，则X→→(Z–Y)规则IR7：转换规则如果X→Y

，则X→→Y规则IR8：结合规则如果X→→Y，且存在另一个属性集合W满足：WY=WZYZ则X→Z版权所有(C)-南京大学计算机科学与技术系1078.2.3多值依赖与第四范式规则IR6：多值依赖的传递规则如果X→→Y，Y→→Z，则X→→(Z–Y)证明：假设X,Y,Z

是关系模式R(U)的属性子集，且Y=AB,Z=BC,则D=U-X-Y-Z是该关系中除X,Y,Z三部分属性之外的其它属性所构成的集合。因此我们可以将该关系中的属性分为五个属性子集：X,A,B,C,D如果t1,t2是关系R中的任意两

个元组,且t1[X]=t2[X],即：(t1[X],t1[AB],t1[C],t1[D])R……………………(1)(t2[X],t2[AB],t2[C],t2[D])R……………………(2)t1[X]=t2[X]…………..………………………………(3)由X→

→Y(即X→→AB)和(1),(2)得：(t1[X],t1[AB],t2[C],t2[D])R……………………(4)(t2[X],t2[AB],t1[C],t1[D])R……………………(5)版权所有(C)-南京大学计算机科学与技术系1088.2.3多值依赖与第四范式由Y→→Z(即AB→→

BC)和(1),(4)：(t1[X],t1[AB],t1[C],t1[D])R……………………(1)(t1[X],t1[AB],t2[C],t2[D])R……………………(4)交换它们两者在属性集X和D上的取值得：(t1[

X],t1[AB],t1[C],t2[D])R……………………(6)(t1[X],t1[AB],t2[C],t1[D])R……………………(7)由Y→→Z(即AB→→BC)和(2),(5)：(t2[

X],t2[AB],t2[C],t2[D])R……………………(2)(t2[X],t2[AB],t1[C],t1[D])R……………………(5)交换它们两者在属性集X和D上的取值得：(t2[X],t2[AB],t2[C],t1

[D])R……………………(8)(t2[X],t2[AB],t1[C],t2[D])R……………………(9)版权所有(C)-南京大学计算机科学与技术系1098.2.3多值依赖与第四范式调整表达式(1)和(2)的属性排列次序得：(t1[X

],t1[C],t1[ABD])R………………………(10)(t2[X],t2[C],t2[ABD])R………………………(11)由t1[X]=t2[X]及(10),(11),(12),(13)得：X→→C由于t1[X]=

t2[X]，因此：–将表达式(9)：(t2[X],t2[AB],t1[C],t2[D])R变换为：(t1[X],t1[C],t2[ABD])R…………………(12)–将表达式(7)：(t1[X],t1[AB],t2[C],t1[D])R变换为：(t2[X],t2[C],t

1[ABD])R…………………(13)版权所有(C)-南京大学计算机科学与技术系1108.2.3多值依赖与第四范式规则IR8（结合规则）如果X→→Y,且存在另一个属性集合W满足：WY=,WZ,YZ,则：X→Z证明：将关系模式R(U)的属性集合U划分为五个属性子集：X,(Y-

Z),Z,W,P如果t1,t2是关系R中的任意两个元组,且t1[X]=t2[X],即：(t1[X],t1[Y-Z],t1[Z],t1[W],t1[P])R……………(1)(t2[X],t2[Y-Z],t2[Z],t2[W],t2[P])R……………(2)由X→→Y和(1),(2)得：(t

1[X],t1[Y-Z],t1[Z],t2[W],t2[P])R……………(4)由W→Z和(2),(4)得：t1[Z]=t2[Z]由于从t1[X]=t2[X]可以推出t1[Z]=t2[Z],所以有:X→Z

版权所有(C)-南京大学计算机科学与技术系1118.2.3多值依赖与第四范式定义8.13：第四范式(4NF)在关系模式R(U)中，如果X→→Y是非平凡多值依赖，则X必含有关键字，此时称关系模式R满足第四范

式，并记作R∈4NF。第四范式的特点只允许出现平凡多值依赖；函数依赖要满足BCNF。例：将R(C,T,L)分解为：R1(C,T)C→→TR2(C,L)C→→L从而消除了原关系模式中的数据冗余和异

常现象版权所有(C)-南京大学计算机科学与技术系1128.2.4小结规范化的目的解决插入、删除及修改异常，降低数据冗余度规范化的方法根据各属性间的依赖关系(函数依依赖及多值依赖)来构造关系模式。规范化的实现手段模式分解习题8.3：是不是规范化最佳的模式结构是最好的结

构？为什么？关系模式的逆规范化问题8.3规范化理论的研究版权所有(C)-南京大学计算机科学与技术系1148.3.1函数依赖理论5函数依赖集的等价如果两个函数依赖集F1和F2的闭包是相等的，即F1+=F2+，则称函数依赖集F1等价于函数依赖集F2。1Armstrong公理系

统2函数依赖的逻辑蕴涵3函数依赖集F的闭包F+4属性集X在函数依赖集F上的闭包XF+6最小函数依赖集与函数依赖集F相等价的所有函数依赖集中的最小者被称为函数依赖集F的最小函数依赖集。版权所有(C)-南京大学计算机科学与技术系1158

.3.1函数依赖理论最小函数依赖集的判定条件：凡是满足下述三个条件的函数依赖集F就是其最小函数依赖集对于F中的每一个FD关系X→A均作如下判断：1.依赖因素A为单个属性；2.令：F1=F–{X→A},则F1+F+；–不存在冗余的函数依赖关系3.对于

决定因素X的每一个真子集Y(YX)均作如下判断：令F2=F–{X→A}{Y→A},则F2+F+–不存在部分函数依赖关系版权所有(C)-南京大学计算机科学与技术系1168.3.1函数依赖理论如果F中的每一个FD关系X→A均符合上述三个条件的

要求，则F是一个最小函数依赖集。其中：条件1并不是必须的，只是为了方便对条件2和条件3的判断。版权所有(C)-南京大学计算机科学与技术系117算法8-3：寻找与函数依赖集F等价的最小函数依赖集G1.令G:=F2.将G中每一个形如X(A1,A2,…,An)的函数依赖

替换为如下一组依赖因素为单个属性的函数依赖：XA1,XA2,…,XAn3.对G中的每一个函数依赖XA作如下的处理：对决定因素X中的每一个属性B作如下处理：1)计算属性集的闭包(X–B)G+；2)如果A

(X–B)G+,则用新的函数依赖(X–B)A替换原来的函数依赖XA;版权所有(C)-南京大学计算机科学与技术系118算法8-3：寻找与函数依赖集F等价的最小函数依赖集G4.对G中的每一个函数依赖XA作如下处理：1)令N:=G

–{XA};2)计算属性集的闭包XN+;3)如果AXN+,那么从G中删去函数依赖XA；5.将G中每一组形如XA1,XA2,…,XAn(决定因素相同)的函数依赖合并为一个函数依赖:X(A1,A2,…,An)版权所有(C)-南京大学计算机科学与

技术系1198.3.1函数依赖理论例：设F={AC,ACD,EAD,EH}G={ACD,EAH}请问：F与G是否等价？分析：要判断两个函数依赖集是否等价，只要检查它们的FD是否相互逻辑蕴涵。首先判断F中的函数依赖是否为G所逻辑蕴涵：对于F中的每一个函数依赖XA均做如下判断

：o如果AXG+，则G逻辑蕴涵XA再判断G中的函数依赖是否为F所逻辑蕴涵：对于G中的每一个函数依赖YB均做如下判断：o如果BYF+，则F逻辑蕴涵YB如果F中的每一个FD都是G所逻辑蕴涵的，且G中的每一个FD也都是F所逻辑蕴涵的，则F和G必是逻辑等价

的。版权所有(C)-南京大学计算机科学与技术系1208.3.1函数依赖理论例：设F={AC,ACD,EAD,EH}，请给出F的最小函数依赖集。解：首先根据算法8-3的步骤(2)将F转换成：G={A

C,ACD,EA,ED,EH}根据步骤(3)消除部分FD。在这里我们只要检查ACD是否为部分函数依赖。考虑其决定因素AC的每个真子集：•{A}G+={A,C,D},D{A}G+•{C}G+={C},D{C}G+因此，可以用AD来替换G中的ACD得：G={AC

,AD,EA,ED,EH}版权所有(C)-南京大学计算机科学与技术系121步骤(3)的计算结果如下：G={AC,AD,EA,ED,EH}8.3.1函数依赖理论根据步骤(4)的要求消除G中多余的函数依赖关系。步骤(4)的计算结果如下：G={A

C,AD,EA,EH}根据步骤(5)的要求得到最终计算结果：G={ACD,EAH}版权所有(C)-南京大学计算机科学与技术系1228.3.1函数依赖理论例：F={B→CD,AD→E,B→A}G={B→C

DE,B→ABC,AD→E}请问：1.F与G是否等价？2.计算G的最小函数依赖集版权所有(C)-南京大学计算机科学与技术系1238.3.1函数依赖理论一个函数依赖集F的最小函数依赖集可能有若干个，并不具有唯一性。解：本题主要是判断ABC是否

为部分函数依赖？如果是部分FD，那么可以将其简化为哪一个完全函数依赖？例：计算函数依赖集F={AB,BA,ABC}的最小函数依赖集。版权所有(C)-南京大学计算机科学与技术系124F={AB,BA,ABC}判断ABC是否为部分函数依赖？如是则需要将其转

化为完全函数依赖。•从其决定因素中去掉属性B，计算{A}F+：{A}F+={A,B,C}有：C{A}F+•从其决定因素中去掉属性A，计算{B}F+：{B}F+={A,B,C}有：C{B}F+因此

，可以用AC和(或)BC来替换原来的ABCG={AB,BA,AC,BC}在算法8-3的步骤(4)中，需要消除G中冗余的函数依赖。根据对函数依赖处理顺序的不同可以得到两个不同（但也是相互等价）的最小函数依赖集：G1={AB,BA,AC}G2={AB,BA,BC}版权

所有(C)-南京大学计算机科学与技术系1258.3.2模式分解的研究关系数据库的规范化实际上就是一个不断进行模式分解的过程。在分解过程中需要研究下列问题：无损联接性（losslessjoin）分解后，原关

系中的信息不会被丢失依赖保持性原有的函数依赖关系在分解后的关系模式上依然存在在满足无损联接性与(或)依赖保持性的情况下，一个关系模式可以被分解到满足第几范式？相关的一些分解算法版权所有(C)-南京大学计算机科学与技术系1268

.3.2模式分解的研究无损联接性设R是一个关系模式，F是关系模式R上的一个函数依赖集，={R1,R2,…,Rk}是对R的一个分解。如果对R中满足F的每一个关系实例r都有：r=R1(r)R2(r)……Rk(r)其中：Ri(r)为关系实例r在关系模

式Ri上的投影，即根据Ri中的属性对r执行投影运算后的结果。则称该分解相对于F是“无损联接分解”，或称分解具有无损联接性。对于不具备‘无损联接性’的分解来说，关系r与分解后的子关系满足：rR1(r)R2(r)……Rk(r)版权所有(C)-南京大学计算机科学与技

术系1278.3.2模式分解的研究一个具有‘无损联接性’的模式分解c3300a3c2200a2c1100a1CBAABC300a3200a2100a1BAABc3300c2200c1100CBBCc3300a3c2200a2c1100a1C

BAABBC版权所有(C)-南京大学计算机科学与技术系1288.3.2模式分解的研究一个不具备‘无损联接性’的模式分解c4200a4c3300a3c2200a2c1100a1CBAABC200a4300a3200a2100a1BAABc4200

c3300c2200c1100CBBCc3300a3c4200a4c2200a4c4200a2c2200a2c1100a1CBAABBC版权所有(C)-南京大学计算机科学与技术系1298.3.2模式分解的研究从关系模式AB

C（如下左图）到关系模式AB和BC的分解为何具有‘无损联接性’？c3300a3c2200a2c1100a1CBAABC300a3200a2100a1BAABc3300c2200c1100CBBC在关系模式ABC中具有如

下的函数依赖关系：BC因此从模式ABC到模式AB和BC的分解具有无损联接性：ABCABBCWHY？版权所有(C)-南京大学计算机科学与技术系1308.3.2模式分解的研究在满足依赖关系BC的前提下向关系ABC插入一个新的元组(a4,200,c2)，新的关系ABC（

下图左）仍然具有无损联接性ABCa1100c1a2200c2a3300c3a4200c2ABCABa1100a2200a3300a4200ABBC100c1200c2300c3BC版权所有(C)-南京大学计算机科学与技术系1318.3.2模式

分解的研究如果违反依赖关系BC的要求强行向关系ABC插入一个新的元组(a4,200,c4)，则新的关系ABC（下图左）将不再具有依赖关系BC，因而该分解则不再具有无损联接性(WHY?)ABCa1100c1a220

0c2a3300c3a4200c4ABCABa1100a2200a3300a4200ABBC100c1200c2300c3200c4BC版权所有(C)-南京大学计算机科学与技术系1328.3.2模式分解的研究定理8.3.2.1：如果R的分解为={R1,R2}，F为R所满

足的函数依赖集合，分解具有无损联接性的充分必要条件是：R1R2(R1–R2)或R1R2(R2–R1)版权所有(C)-南京大学计算机科学与技术系1338.3.2模式分解的研究设有一个关系模式T(

A,B,C)，函数依赖集为F,请判断下述的分解={T1,T2}是否具有无损联接性？1)F={AB},T1(A,B),T2(A,C)2)F={AC,BC},T1(A,B),T2(A,C)3)F={AB},T1(A,B),T2(B,C)4)F={AB,BC},T1(A,C),

T2(B,C)版权所有(C)-南京大学计算机科学与技术系1348.3.2模式分解的研究依赖保持性设F是属性集U上的函数依赖集，Z是U上的一个子集，F在Z上的投影用Z(F)来表示设存在关系模式R的一个分解={R1,R2,…,Rk}

,F是R上的函数依赖集。如果：F+=(R1(F)R2(F)…Rk(F))+则称分解具有依赖保持性版权所有(C)-南京大学计算机科学与技术系1358.3.2模式分解的研究在必须同时满足无损联

接性和依赖保持性的要求下，一个关系模式最高可以被分解到满足第三范式。算法8-4：假设存在一个关系模式R，其函数依赖集为F，利用该算法可以将其分解到满足第三范式，同时该分解满足无损联接性和依赖保持性。假设S是分解所获

得的子关系模式的集合算法8-4：1)计算F的最小函数依赖集，并用来代替F进行下面的模式分解;2)S=;版权所有(C)-南京大学计算机科学与技术系1363)对F中的每一个函数依赖XY做如下处理：如果：对于集合S中的每一个子关系模式Z都有：XYZ则由X和Y构成一个新的子关系加入到集

合S中，即：S=SHeading(XY)8.3.2模式分解的研究4)如果关系R的每一个候选关键字K都没有出现在分解后的子关系模式中，即：对集合S中的每一个子关系模式Z都有：KZ则：从关系R中任选一个候选关键字K,并由K中的属性单独构成一个子关系模式并加入到集合S中去，即：S=SHea

ding(K)版权所有(C)-南京大学计算机科学与技术系137