数据库课件 第六章 关系数据库设计理论

数据库课件第六章关系数据库设计理论第1页，共89页，2023年，2月20日，星期六第六章关系数据库设计理论12问题的提出基本概念34规范化函数依赖的公理系统5模式分解第2页，共89页，2023年，2月20日，星期六6.1问题的提出

针对一个具体问题，设计一个好的关系数据库系统，关键是要构造一个适合于它的数据模式（数据库逻辑设计问题）数据库逻辑设计主要解决的问题：应该构造几个关系模式每个关系模式包括哪些属性

数据库逻辑设计工具─关系数据库的规范化理论第3页，共89页，2023年，2月20日，星期六6.1问题的提出例：描述电力设备存放管理的数据库数据库：WAE(仓库号，所在区域，区域主管，设备号，数量)语义：⒈一个区域有多个仓库，一个仓库只能属于一个区域；⒉一个区域只有一个区域主管；⒊一个仓库可以存放多种设备，每种设备可以存放在多个仓库中；⒋每个仓库的每种设备都有一个库存数量。第4页，共89页，2023年，2月20日，星期六6.1问题的提出⒈数据冗余太大浪费大量的存储空间⒉更新异常更新代价大，可能导致数据不一致⒊插入异常该插的数据插不进去⒋删除异常不该删除的数据不得不删，造成某些数据丢失

存在的问题：第5页，共89页，2023年，2月20日，星期六6.1问题的提出结论：WAE关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。第6页，共89页，2023年，2月20日，星期六6.1问题的提出分解成三个关系模式即可：

W(仓库号，所在区域)；A(区域，区域主管)；WE(仓库号，设备号，数量)第7页，共89页，2023年，2月20日，星期六6.2基本概念

规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余等问题。第8页，共89页，2023年，2月20日，星期六6.2.1函数依赖定义6.1

设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，对t1,t2r，若t1[X]=t2[X]，则t1[Y]=t2[Y]则称X函数决定Y或Y函数依赖X，记作X→Y。如：仓库号所在区域

所在区域区域主管

（仓库号，设备号）数量若Y不函数依赖于X,则记为X→Y若X→Y，并且Y→X,则记为X←→Y若X→Y，则称X为这个函数依赖的决定因素。第9页，共89页，2023年，2月20日，星期六6.2.1函数依赖1.函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。

例：“区域主管→所在区域”只有在不允许有同名人的条件下成立2.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。3.函数依赖存在的时间无关性。说明:第10页，共89页，2023年，2月20日，星期六6.2.1函数依赖函数依赖与属性间的联系类型有关(1)若属性X和Y之间有“一对一”的联系则：X→Y,Y→X,X←→Y(2)若属性X和Y之间有“多对一”的联系则：X→Y,但Y→X(3)若属性X和Y之间有“多对多”的联系则：X与Y之间不存在任何函数依赖注：当确定函数依赖关系时,可从属性间的联系入手第11页，共89页，2023年，2月20日，星期六6.2.1函数依赖平凡函数依赖与非平凡函数依赖定义6.2在关系模式R(U)中，对于U的子集X和Y：若X→Y，但YX，则称X→Y是非平凡函数依赖.若X→Y，但YX，则称X→Y是平凡函数依赖.例：在关系WAE中，非平凡函数依赖：（仓库号，设备号）数量

平凡函数依赖：（仓库号，设备号）仓库号（仓库号，设备号）设备号注：对任一关系模式，平凡函数依赖必然存在，则一般讨论非平凡函数依赖。第12页，共89页，2023年，2月20日，星期六6.2.1函数依赖完全函数依赖与部分函数依赖定义6.3

在R(U)中，如果X→Y，并且对于X的任何一个真子集X’

，都有X’→Y,则称Y对X完全函数依赖，记作Xｆ

Y。

若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作XPY。例：在关系WAE中，由于：（仓库号，设备号）数量,但仓库号→数量,设备号→数量

因此：（仓库号，设备号）ｆ数量第13页，共89页，2023年，2月20日，星期六6.2.1函数依赖传递函数依赖与直接函数依赖

如果Y→X，即X←→Y，则Z对X直接函数依赖。例：在关系wae中有：定义6.4

在R(U)中，如果X→Y，Y→Z，且YX，Y→X，则称Z对X传递函数依赖,记作XtZ。仓库号→所在区域，所在区域→区域主管可得到传递函数依赖：仓库号t

区域主管第14页，共89页，2023年，2月20日，星期六6.2.2码定义6.5

设K为R<U,F>中的属性或属性组合。若KFU，则K称为R的一个侯选码。若关系模式R有多个候选码，则选定其中的一个做为主码。

主属性：包含在任何一个候选码中的属性非主属性：不包含在任何一个码中的属性

全码：整个属性组全是码第15页，共89页，2023年，2月20日，星期六6.2.2码定义6.5

关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。注：主码和外码一起提供了表示关系间联系的手段。例：在关系SC(Sno,Cno,Grade)中，由于：Sno不是SC的码，但是另一个关系S的码因此：Sno是SC的外码第16页，共89页，2023年，2月20日，星期六6.3规范化范式是对关系数据库的规范化过程中为不同程度的规范化要求设立的不同标准。范式是符合某一种级别的关系模式的集合。

范式的种类： 第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)第17页，共89页，2023年，2月20日，星期六6.3规范化各种范式之间存在联系：5NF

4NF

BCNF

3NF

2NF

1NF

某一关系模式R为第n范式，可简记为R∈nNF。通过模式分解将一个低级范式的关系模式转换为若干个高级范式的关系模式的过程称作规范化。第18页，共89页，2023年，2月20日，星期六6.3.1第一范式（1NF）定义6.7满足最低要求的范式。如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF。

第一范式是对关系模式的最起码要求。不满足第一范式的数据库模式不能称为关系数据库。但满足第一范式的关系模式并不一定是一个好的关系模式。第19页，共89页，2023年，2月20日，星期六6.3.2第二范式（2NF）定义6.8若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。即：消除非主属性对码的部分依赖

如果一个数据库模式中的每个关系模式都是第二范式的，则称此数据库模式属于第二范式的数据库模式。从1NF中消除非主属性对候选码的部分函数依赖,则获得2NF。第20页，共89页，2023年，2月20日，星期六6.3.2第二范式（2NF）例:关系模式WAE中:WAE(仓库号，所在区域，区域主管，设备号，数量)

码：(仓库号,设备号)

主属性:仓库号,设备号

非主属性:所在区域、区域主管和数量

函数依赖：第21页，共89页，2023年，2月20日，星期六6.3.2第二范式（2NF）仓库号

设备号数量

所在区域

区域主管关系WAE码为(仓库号,设备号)非主属性所在区域和区域主管部分函数依赖于码WAE满足第一范式，但不满足第二范式。第22页，共89页，2023年，2月20日，星期六6.3.2第二范式（2NF）解决方法：将WAE分解为两个关系模式，消除这些部分函数依赖：即：

WE（仓库号，设备号，数量）

WA（仓库号，所在区域，区域主管）仓库号设备号数量关系WE关系WA仓库号所在区域区域主管WE∈2NF,WA∈2NF第23页，共89页，2023年，2月20日，星期六6.3.2第二范式（2NF）注：采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。如：(1)若某个区域刚刚设立还没有仓库，则所在区域和区域主管的值无法插入，造成插入异常。(2)有一定的数据冗余，当多个仓库处于同一个区域时，区域主管的值被多次存储。(3)若某区域要更换区域主管，则要逐一地修改该区域的所有区域主管记录，稍有不慎，就有可能漏改某些记录，造成更新异常。第24页，共89页，2023年，2月20日，星期六6.3.3第三范式（3NF）如果一个数据库模式中的每个关系模式都是第三范式的，则称此数据库模式属于第三范式的数据库模式。从2NF中消除非主属性对候选码的传递依赖,则获得3NF。定义6.9如果关系模式R∈2NF，且每个非主属性都不传递函数依赖于R的候选码，则称R属于第三范式，简称3NF，记作R∈3NF。

即：消除非主属性对码的部分依赖和传递依赖第25页，共89页，2023年，2月20日，星期六6.3.3第三范式（3NF）例:WE（仓库号，设备号，数量）

WA（仓库号，所在区域，区域主管）

函数依赖：

WE中：(仓库号，设备号)f数量

WA中：仓库号→所在区域，所在区域→区域主管可得到传递函数依赖：仓库号ｆ

区域主管

因此：

WE∈3NF，而WA∈3NF第26页，共89页，2023年，2月20日，星期六6.3.3第三范式（3NF）原因:区域主管传递依赖于码。解决方法：将WA分解为两个关系模式，消除这些传递依赖：即：W（仓库号，所在区域）

A（所在区域，区域主管）仓库号所在区域关系W关系A所在区域区域主管W∈3NF,A∈3NF第27页，共89页，2023年，2月20日，星期六6.3.3第三范式（3NF）注：采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上减轻原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。表现在可能存在主属性对码的部分和传递依赖。第28页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）

BCNF范式是第三范式的改进形式，建立在第一范式的基础上，消除了主属性对码的部分和传递依赖。定义6.10

设关系模式R∈1NF，若对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么R∈BCNF。即：每一个决定因素（决定属性集）都包含码第29页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）证明：BCNF3NF反证：若RBCNF，但R3NF，则按3NF定义，一定有非主属性对码的传递依赖。于是存在：R的码X，属性组Y，以及非主属性Z（ZY），使得XY，YZ，YX成立。由YZ，按BCNF定义，Y含有码，则是YX成立，这与YX矛盾。所以：R3NF。第30页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）注意：若R∈BCNF，则R∈3NF若R∈3NF，则R不一定属于BCNF若R∈BCNF

所有非主属性对每一个候选码都是完全函数依赖；所有主属性对每一个不包含它的候选码都是完全函数依赖；没有任何属性完全函数依赖于非码的任何一组属性。第31页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）例1:Course（Cno,Creidt,Pcno）

函数依赖：

Cno→Credit,Cno→Pcno

即：无部分依赖和传递依赖，且Cno是唯一决定因素

因此：

Course∈3NF，且Course∈BCNF

码：Cno即为主属性，决定因素第32页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）例2：在关系模式SCP（S,C,P）中，S表示学生，C表示课程，P表示名次。说明：每一个学生选修每一门课程都有一个固定的名次：每一门课程中每一名次只对应一个学生（假设没有相同名次的学生）：(S，C)→P(C，P)→S第33页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）SCPCPS关系SCP

候选码：(S，C)和(C，P)即：S，C和P都是主属性

决定因素：(S，C)和(C，P)

结论：SCP∈BCNF只有(S，C)和(C，P)决定因素且包含候选码，无其他决定因素SCP∈3NF

S、C、P都是主属性无部分依赖和传递依赖第34页，共89页，2023年，2月20日，星期六6.3.4BC范式（BCNF）例3：在关系模式WES(仓库号,设备号,职工号)中。说明：一个仓库可以有多个职工;一个职工仅在一个仓库工作;每个仓库一种设备仅由一名职工保管,但每名职工可以保管多种设备.问:该关系的码?属于第几范式?答:码:(仓库号,设备号)属于3NF,但不属于BCNF非BCNF的不良特性:某位职工刚分配到一个仓库工作，但尚未负责具体设备，这样的信息就无法插入。职工号仓库号

(仓库号,设备号)职工号第35页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式课程C教员T参考书B物理

数学

计算数学李勇王军

李勇张平

张平周峰

普通物理学光学原理物理习题集

数学分析微分方程高等代数

数学分析

例:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 即：关系模式Teaching(C,T,B)

课程C、教师T和参考书B第36页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数…李勇李勇李勇王军王军王军李勇李勇李勇张平张平张平

…物理物理物理物理物理物理数学数学数学数学数学数学

…参考书B教员T课程C用二维表表示Teaching第37页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式Teach具有唯一候选码(C,T,B)，即全码Teaching∈BCNF

存在的问题

(1)数据冗余：有多少名任课教师，参考书就要存储多少次；

(2)插入异常：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组；

(3)删除异常：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组；

(4)修改异常：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。

产生原因：存在多值依赖第38页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式定义6.11

设R(U)是属性集U上的一个关系模式。X、Y、Z是U的子集，并且Z＝U－X－Y，多值依赖X→→Y成立当且仅当对R的任一关系r，给定一对（x，z）值，则对应一组Y值，且这组值仅仅决定于X值而与Z值无关。例：Teaching（C,T,B）对于C的每一个值，T总有一组值与之对应，而与B的取值无关，则T多值依赖于C即：C→→T，且B也多值依赖于C即：C→→B。第39页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式平凡多值依赖和非平凡的多值依赖若X→→Y，而Z＝φ，则称X→→Y为平凡的多值依赖；否则称X→→Y为非平凡的多值依赖。如非平凡的多值依赖：CT，CB第40页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式

多值依赖的性质：（1）对称性：即：若X→→Y，则X→→Z，其中Z＝U－X－Y

多值依赖的对称性可以用完全二分图直观地表示出来。（2）传递性：即：若X→→Y，Y→→Z，则X→→Z－Y第41页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式

物理普通物理学光学原理物理习题集李勇王军完全二分图描述多值依赖对称性第42页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式（5）函数依赖是多值依赖的特殊情况： 即：若X→Y，则X→→Y。（3）合并性:若X→→Y，X→→Z，则X→→YZ。（4）分解性:若X→→Y，X→→Z，则X→→Y∩Z,X→→Y－Z，X→→Z－Y。第43页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式定义6.12

关系模式R∈1NF，如果对于R的每个非平凡多值依赖X→→Y（YX），X都含有候选码，则R∈4NF。即：消除各属性间非平凡且非函数依赖的多值依赖。

允许出现函数依赖（非平凡多值依赖）允许出现平凡多值依赖

如果R∈4NF，则R∈BCNF第44页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式证明：4NFBCNF反证：若R4NF，但RBCNF，则按BCNF定义，一定有一个决定因素不包含码。于是存在：XY，YX，且X中不含有码。由于函数依赖是多值依赖的特殊情况，即：XY，可得X→→Y（YX），按4NF定义，X一定含有码，则与X中不含有码矛盾。所以：RBCNF。第45页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式

存在非平凡的多值依赖C→→T，且C不是候选码，该关系模式的码是(C,T,B)，即全码。存在问题：数据冗余大，插入、删除、更新异常解决方法：用投影分解法把Teach分解为如下两个关系模式：CT(C,T)∈4NFCB(C,B)∈4NF

其中：C→→T，C→→B是平凡多值依赖

例：Teach(C,T,B)∈4NF第46页，共89页，2023年，2月20日，星期六6.3.5多值依赖与第四范式函数依赖和多值依赖是两种非常重要的数据依赖若只考虑函数依赖，则BCNF为最高范式（但不是数据库模式设计的最高范式）；若考虑多值依赖，则4NF为最高范式；若消除了4NF中的连接依赖，可以得到更为规范化的5NF。第47页，共89页，2023年，2月20日，星期六6.3.6关系模式规范化一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化1NF。规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。第48页，共89页，2023年，2月20日，星期六6.3.6关系模式规范化消除不合适的数据依赖;采用“一事一地”的模式设计原则，使各关系模式达到某种程度的“分离”；让一个关系描述一个概念、一个实体或者实体间的一种联系;若多于一个概念就把它“分离”出去；所谓规范化实质上是概念的单一化。

规范化的基本思想第49页，共89页，2023年，2月20日，星期六6.3.6关系模式规范化关系模式规范化的基本步骤

1NF ↓消除决定因素2NF非码的非平凡↓函数依赖3NF ↓ BCNF ↓ 4NF消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除非平凡且非函数依赖的多值依赖不能说规范化程度越高的关系模式就越好；在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式；上面的规范化步骤可以在其中任何一步终止。注意：第50页，共89页，2023年，2月20日，星期六练习

给定关系模式和函数依赖集合，要求判断达到的最高范式。步骤如下：1.求出给定关系的候选码（可能不止一个）2.根据码，写出主属性和非主属性。3.判断是否满足第一范式(属性的值域是否可以分解）4.判断是否满足第二范式(非主属性对码的部分函数依赖)5.判断是否满足第三范式(非主属性对码的传递函数依赖)6.判断是否满足BCNF范式(主属性对码的传递和部分函数依赖)第51页，共89页，2023年，2月20日，星期六解：1.关系r的候选码为：AB和AC

练习1.已知关系模式R<U,F>U={A,B,C,D}F={ABD,ACBD,BC}在函数依赖范围内该关系属于的最高范式是什么？2.主属性为：A、B、C

非主属性为：D3.判断是否满足各个范式的要求：

1)R的所有的属性值域都不可再分，则r∈1NF。

2)非主属性D不存在对任何码的部分函数依赖，则r∈2NF。

3)非主属性D不存在对任何码的传递函数依赖，则r∈3NF。

4)因为有函数依赖BC，而B不是关系R的码，则r不属于BCNF。则：r∈3NF

第52页，共89页，2023年，2月20日，星期六解：1.关系r的候选码为：AC练习2.已知关系模式R<U,F>U={A,B,C,D,E,F}F={AB,CDF,ACE,DF}在函数依赖范围内该关系属于的最高范式是什么？2.主属性为：A、C

非主属性为：B、D、E、F3.判断是否满足各个范式的要求：

1)R的所有的属性值域都不可再分，则r∈1NF。

2)由于存在函数依赖AB,CDF，而A和C均不是关系的码，存在非主属性B、D、F对码的部分函数依赖，则r不属于2NF。则：r∈1NF

第53页，共89页，2023年，2月20日，星期六练习练习3.假设：某商业集团数据库中有一关系模式R如下：

R(商店编号，商品编号，数量，部门编号，负责人)

如果规定：

(1)每个商店的每种商品只在一个部门销售；

(2)每个商店的每个部门只有一个负责人；

(3)每个商店的每种商品只有一个库存数量。

试回答下列问题：

(1)根据上述规定，写出关系模式R的基本函数依赖；

(2)找出关系模式R的候选码；

(3)试问关系模式R最高已经达到第几范式？为什么？

(4)如果R不属于3NF，请将R分解成3NF模式集第54页，共89页，2023年，2月20日，星期六练习(1)有三个函数依赖：

(商店编号，商品编号)→部门编号

(商店编号，部门编号)→负责人

(商店编号，商品编号)→数量(2)R的候选键:(商店编号，商品编号)(3)因为R中存在着非主属性“负责人”对候选码(商店编号、商品编号)的传递函数依赖，但无部分函数依赖，所以R属于2NF，R不属于3NF。(4)将R分解成：

R1(商店编号，商品编号，数量，部门编号)R2(商店编号，部门编号，负责人)

第55页，共89页，2023年，2月20日，星期六6.4函数依赖的公理系统逻辑蕴含

定义6.13

对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立，则称F逻辑蕴含X→Y

，或称X→Y为F所蕴含。即：对于r中任意两个元组t和s，有：若t[X]=s[X]

则t[Y]=s[Y]必成立。第56页，共89页，2023年，2月20日，星期六6.4.1Armstong公理系统Armstrong公理系统－函数依赖的推理规则关系模式R<U，F>有以下推理规则：Al自反律：若YXU，则X→Y为F所蕴含。A2增广律：若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。A3传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。注：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。第57页，共89页，2023年，2月20日，星期六6.4.1Armstong公理系统伪传递规则：若XY，WYZ，则XWZ。分解规则：若XY及ZY，则XZ。XY增广律XXYXZ增广律XYYZ传递律}XYZ证明合并规则：由Armstrong公理导出的推理规则:合并规则：若XY，XZ，则XYZ。第58页，共89页，2023年，2月20日，星期六6.4.2闭包

引理6.l若A1A2…An是关系模式R的属性集,则：X→A1A2…AkX→Ai成立(i=l,2,…,k)。证明：充分性：由合并律 必要性：由分解律根据合并规则和分解规则，可得：第59页，共89页，2023年，2月20日，星期六6.4.2闭包定义6.14在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。定义6.15设F为属性集U上的一组函数依赖，XU，XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。引理6.2设F为属性集U上的一组函数依赖，X，YU，X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+用途：将判定X→Y是否能由F根据Armstrong公理导出的问题，转化为求出XF+

，判定Y是否为XF+的子集的问题。第60页，共89页，2023年，2月20日，星期六6.4.2闭包算法6.l

求属性集X（XU）关于U上的函数依赖集F的闭包XF+

输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B：B={A|(V)(W)(V→WF∧VX（i）∧AW)}；（3）X（i+1）=B∪X（i）

（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若不相等,则i=i+l，返回第（2）步。第61页，共89页，2023年，2月20日，星期六例：已知关系模式R<U，F>，其中U={A，B，C，D，E}F={AB→C，B→D，C→E，EC→B，AC→B}求（AB）F+

。解：(1)设X（0）=AB；

(2)计算X（1）:

逐一扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：AB→C，B→D。

(3)X（1）=AB∪CD=ABCD。(4)X（0）≠X（1）

则需再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D，C→E，AC→B

于是：X（2）=X（1）∪BCDE=ABCDE。(5)X（2）=U，算法终止所以（AB）F+=ABCDE第62页，共89页，2023年，2月20日，星期六6.4.2闭包练习：已知关系模式R<U，F>，其中U={A，B，C，D，E，G}F={AE,BEAG,CEA,GD}求（AB）F+

。解：所用依赖（AB）F+

ABAE（AAB) ABE

BEAG(BE

ABE)

ABEGGD(G

ABEG)

ABEGD所以：（AB）F+

=ABDEG第63页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化函数依赖等价定义6.16如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理6.3F+=G+的充分必要条件是：

FG+

和GF+第64页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化最小依赖集定义6.17

如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖:(1)F中任一函数依赖的右部仅含有一个属性。

(2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。

(3)F中不存在这样的函数依赖X→A，X有真子集Z使得（F-{X→A}）∪{Z→A}与F等价。

第65页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化例:对于关系模式S<U，F>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT,SDEPT→MN,(SNO，CNAME)→G}设:F’={SNO→SDEPT,SNO→MN,SDEPT→MN,(SNO,CNAME)→G,(SNO,SDEPT)→SDEPT}

F是最小覆盖，而F’不是因为：F’-{SNO→MN}与F’等价

F’-{(SNO，SDEPT)→SDEPT}也与F’等价第66页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化定理6.1每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。求解过程:依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集：

(1)逐一检查F中各函数依赖FDi：X→Y

若Y=A1A2

…Ak，k>2，则用{X→Aj|j=1，2，…，k}来取代X→Y。

理由：引理6.1保证了F变换前后的等价性。第67页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化(2)逐一检查F中各函数依赖FDi：X→A

令G=F-{X→A}，若AXG+，则从F中去掉此函数依赖。理由：由于F与G=F-{X→A}等价的充要条件是AXG+，因此F变换前后是等价的。第68页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化(3)逐一取出F中各函数依赖FDi：X→A

设X=B1B2…Bm，逐一考查Bi（i=l，2，…，m），若A（X-Bi）F+，则以X-Bi取代X。理由：由于F与（F-{X→A}）∪{Z→A}等价的充要条件是AZF+，其中Z=X-Bi，因此F变换前后是等价的。即：若AZF+，则说明Z→AF+，又由ZX，则

X→AF+，用Z取代X即可。第69页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化例：已知关系模式R<U，F>，U＝｛A，B，C，D，E，G｝；F＝｛AB→C，C→A，CG→BD，ACD→B｝，求F的最小函数依赖集。

(1)分解右边:F＝｛AB→C，C→A，CG→B，CG→D，ACD→B｝

(2)去掉F中多余的函数依赖:检查AB→C：

G=F-{ABC}={C→A，CG→B，CG→D，ACD→B}

则：ABG+={AB}，C{AB}

保留ABC：

F={AB→C，C→A，CG→B，CG→D，ACD→B}第70页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化检查C→A：

G=F-{CA}={AB→C,CG→B,CG→D,ACD→B}

则：CG+={C}，A{C}保留CA：F={AB→C，C→A，CG→B，CG→D，ACD→B}检查CG→B：

G=F-{CGB}={AB→C,C→A,CG→D,ACD→B}

则：CGG+={ABCDG}，B{ABCDG}删除CGB：F={AB→C,C→A,CG→D,ACD→B}第71页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化检查CG→D：

G=F-{CGD}={AB→C,C→A,ACD→B}

则：CGG+={ACG}，D{ACG}保留CGD：F={AB→C,C→A,CG→D,ACD→B}检查ACD→B：

G=F-{ACDB}={AB→C,C→A,CG→D}

则：ACDG+={ACD}，B{ACD}保留ACDB：F={AB→C,C→A,CG→D,ACD→B}则：F={AB→C,C→A,CG→D,ACD→B}第72页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化

(3)去掉F中各依赖左部多余的属性:

检查AB→C：

G=F-{ABC}={C→A,CG→D,ACD→B}

由于：AG+={A}，BG+={B}

保留ABC：F={AB→C,C→A,CG→D,ACD→B}

F={AB→C,C→A,CG→D,ACD→B}检查CG→D：

G=F-{CGD}={AB→C,C→A,ACD→B}

由于：CG+={C，A}，GG+={G}保留CGD：F={AB→C,C→A,CG→D,ACD→B}第73页，共89页，2023年，2月20日，星期六6.4.3函数依赖集的等价和最小化检查ACD→B：

G=F-{ACDB}={AB→C,C→A,CG→D}

由于：CDG+={C，D，A}，

包含A则A多余，可用CDB替代ACDB得到：F={AB→C,C→A,CG→D,CD→B}最后：Fmin={AB→C,C→A,CG→D,ACD→B}

F={AB→C,C→A,CG→D,ACD→B}注意:1)F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi

及X→A中X各属性的处置顺序有关。

2)若改造后的F与原来的F相同，说明F本身就是一个最小依赖集。第74页，共89页，2023年，2月20日，星期六6.5模式分解把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的；只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义；实际上，关系模式的分解，不仅仅是属性集合的分解，它是对关系模式上的函数依赖集，以及关系模式的当前值的分解的具体表现。第75页，共89页，2023年，2月20日，星期六6.5.1模式分解的准则定义6.18关系模式R<U,F>的一个分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}

其中：U=U1∪U2∪…∪Un，且不存在Ui

Uj，Fi为F在Ui上的投影。定义6.19函数依赖集合{X→Y|X→YF+∧XY

Ui}的一个覆盖Fi叫作F在属性Ui上的投影。第76页，共89页，2023年，2月20日，星期六6.5.1模式分解的准则三种模式分解的“等价”定义：⒈分解具有无损连接性⒉分解要保持函数依赖⒊分解既要保持函数依赖，又要具有无损连接性第77页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性例:已知关系模式：SDL<U,F>U={Sno,Sdept,Sloc}F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}

因为：SDL中存在传递函数依赖Sno→Sloc所以：SL∈2NF

存在插入异常、删除异常、冗余度大和更新异常等问题，则可进行分解，且分解方法可以有多种：第78页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性SDL─────────────

Sno Sdept Sloc

─────────────95001CSA95002ISB95003MAC95004ISB95005 PH B─────────────第79页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性第一种分解：SDL分解为下面三个关系模式：

SN(Sno)SD(Sdept)SO(Sloc)

SN──────SD──────SO────

SnoSdeptSloc

────────────────95001CSA95002ISB95003MAC95004PH───95005─────────注：分解后的数据库丢失了许多信息第80页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性第二种分解：SDL分解为下面两个关系模式：

NL(Sno,Sloc)DL(Sdept,Sloc)

NL───────────DL──────────

SnoSlocSdeptSloc─────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B───────────────────第81页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性NLDL─────────────

SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH注：元组增加了，信息丢失了不能确定95002、95004、95005是哪个系的学生？第82页，共89页，2023年，2月20日，星期六6.5.2分解的函数依赖保持性和无损连接性第三种分解：SDL分解为下面两个关系模式：

ND(Sno,Sdept)NL(Sno,Sloc)

ND────────────NL──────────

SnoSdeptSnoSloc