第15章 关系数据库设计理论.ppt

《第15章 关系数据库设计理论.ppt》由会员分享，可在线阅读，更多相关《第15章 关系数据库设计理论.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第15章章 关系数据库设计理论关系数据库设计理论15.1 关系数据库设计理论概述关系数据库设计理论概述15.2 关系模式规范化关系模式规范化15.3 数据依赖的公理系统数据依赖的公理系统数据库原理与应用（基于MySQL）215.1 15.1 关系数据库设计理论概述关系数据库设计理论概述关系数据库设计理论有三个方面的内容：函数依赖、范式和模式设计。函数依赖起核心作用，它是模式分解和模式设计的基础，范式是模式分解的标准。【例15.1】设计一个学生课程数据库，其关系模式 SDSC(Sno,Sname,Age,Dept，DeptHead,Cno,Grade)，各属性含义为学号、姓名、年龄、系、系主

2、任姓名；课程号、成绩。根据实际情况，这些属性语义规定为：（1）一个系有若干学生，一个学生只属于一个系。（2）一个系只有一个系主任。（3）一个学生可以选修多门课程，一门课程可被多个学生选修。（4）每个学生学习每门课程有一个成绩。关系模式 SDSC 在某一时刻的一个实例，即数据表，如表15.1所示。数据库原理与应用（基于MySQL）315.1 15.1 关系数据库设计理论概述关系数据库设计理论概述 数据库原理与应用（基于MySQL）表15.1 SDSC表415.1 15.1 关系数据库设计理论概述关系数据库设计理论概述从上述语义规定和分析表中数据可以看出，(Sno,Cno)能唯一标识一个元组，所以

3、，(Sno,Cno)为该关系模式的主码，但在进行数据库操作时，会出现以下问题。（1）数据冗余当一个学生选修多门课程就会出现数据冗余，导致姓名、性别和课程名属性多次重复存储，系名和系主任姓名也多次重复。（2）插入异常如果某个新系没有招生，由于没有学生，则系名和系主任姓名无法插入，根据关系实体完整性约束，主码(Sno,Cno)不能取空值，此时 Sno,Cno 均无值，所以不能进行插入操作。另外，学生未选修课程，则 Cno 无值，其学号、姓名和年龄无法插入，因为实体完整性约束规定，主码(Sno,Cno)不能部分为空，也不能进行插入操作。数据库原理与应用（基于MySQL）515.1 15.1 关系数据

4、库设计理论概述关系数据库设计理论概述（3）删除异常当某系学生全部毕业还未招生时，要删除全部记录，系名和系主任姓名也被删除，而这个系仍然存在，这就是删除异常。（4）修改异常如果某系更换系主任，则属于该系的记录都要修改DeptHead的内容，若有不慎，造成漏改或误改，造成数据的不一致性，破坏数据完整性。由于存在上述问题，SDSC 不是一个好的关系模式。为了克服这些异常，将 S 关系分解为学生关系 S(Sno,Sname,Age,Dept)，系关系D(Dept，DeptHead)，选课关系 SC(Sno,Cno,Grade)，这三个关系模式的实例如表15.2、表15.3、表15.4所示。数据库原理与

5、应用（基于MySQL）表15.2 S表615.1 15.1 关系数据库设计理论概述关系数据库设计理论概述 数据库原理与应用（基于MySQL）表15.3 D表表15.4 SC表715.1 15.1 关系数据库设计理论概述关系数据库设计理论概述可以看出，首先是数据冗余明显降低。当新增一个系时，只需在关系 D 中增加一条记录即可，当某个学生未选修课程时，只需在关系 S 中增加一条记录，而与选课关系 SC 无关，这就避免了插入异常。当某系学生全部毕业时，只需在关系 S 中删除全部记录，不会影响到系名和系主任姓名等信息，这就避免了删除异常。当更换系主任时，只需在关系 D 中修改一条记录中的属性 Dept

6、Head 的内容，这就避免了修改异常。但是，一个好的关系模式不是在任何情况下都是最优的，例如，查询某个学生的系主任姓名和成绩，就需要通过三个表的连接操作来完成，需要的开销较大，在实际工作中，要以应用系统功能与性能需求为目标进行设计。规范化设计关系模式，将结构复杂的关系模式分解为结构简单的关系模式，使不好的关系模式转变为较好的关系模式，成为下一节讨论的内容。数据库原理与应用（基于MySQL）815.2 15.2 关系模式规范化关系模式规范化关系模式可以形式化地表示为一个五元组R(U,D,DOM,F)其中：R 是关系名，U 是组成该关系的属性名集合，D 是属性所来自的域，DOM 是属性向域的映象集

7、合，F 是属性间的数据依赖关系集合。由于 D 和 DOM 对设计好的关系模式作用不大，一般将关系模式简化为一个三元组R有时还可简化为 R(U)。数据依赖(Data Dependency)是一个关系内部属性与属性之间的一种约束关系，是数据内在的性质，是语义的体现。数据依赖有多种类型，主要介绍函数依赖(Functional Dependency，FD)，简单介绍多值依赖(Multivalued Dependency，MVD)和连接依赖(Join Dependency，JD)数据库原理与应用（基于MySQL）915.2 15.2 关系模式规范化关系模式规范化15.2.1 函数依赖、码和范式函数依赖、

8、码和范式1.函数依赖函数依赖函数依赖是关系数据库规范化理论的基础。定定义义15.1 设 R(U)是属性集 U 上的关系模式，X，Y 是 U 的子集。若对于 R(U)的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等，而在 Y 上的属性值不等，则称 X 函数确定 Y 或 Y 函数依赖于 X，记作 X Y，称 X 为决定因素，Y 为依赖因素。若 Y 不函数依赖于 X，则作为 X Y。若 XY，YX，则记作 XY。例如，关系模式SDSC(Sno,Sname,Age,Dept,DeptHead,Cno,Grade)，有U=Sno,Sname,Age,Dept，DeptHead,C

9、no,GradeF=Sno Sname,Sno Age,Sno Dept,Dept DeptHead,Sno DeptHead,(Sno,Cno)Grade 数据库原理与应用（基于MySQL）1015.2 15.2 关系模式规范化关系模式规范化一个 Sno 有多个 Grade 的值与之对应，Grade 不能函数依赖于 Sno，即 Sno Grade，同理，Cno Grade，但 Grade 可被(Sno,Cno)唯一确定，所以，(Sno,Cno)Grade。函数依赖和别的数据之间的依赖关系一样，是语义范畴的概念，人们只能根据数据的语义来确定函数依赖。函数依赖与属性之间联系的类型有关：（1）如果

10、 X 和 Y 之间是1：1关系（一对一关系），则存在函数依赖 XY，如学生没有重名时，SnoSname。（2）如果 X 和 Y 之间是1：n 关系（一对多关系），则存在函数依赖 X Y，如学号和姓名、部门名之间都有 1：n关系，所以 Sno Age,Sno Dept。（3）如果 X 和 Y 之间是 m：n 关系（多对多关系），则 X 和 Y 之间不存在函数依赖，如学生和课程之间就是 m：n 关系，所以，Sno 和Cno 之间不存在函数依赖关系。数据库原理与应用（基于MySQL）1115.2 15.2 关系模式规范化关系模式规范化数据库原理与应用（基于MySQL）由于函数依赖与属性之间联系的类型

11、有关，可以从分析属性之间的联系入手，确定属性之间的函数依赖。定义定义15.2 若XY是一个函数依赖，且 ，则则称XY是一个平凡函数依赖，否则称为非平凡函数依赖。例如，(Sno,Cno)Sno，(Sno,Cno)Cno都是平凡函数依赖。若不特别声明，本书讨论的都是非平凡函数依赖。定义定义15.3 设R(U)是属性集U上的关系模式，X，Y是U的子集。设XY是一个函数依赖，并且对于任何X的一个真子集 X，XY都不成立，则称XY是一个完全函数依赖(Full Functional Dependency)。即Y函数依赖于整个X，记作 。定义定义15.4 设R(U)是属性集U上的关系模式，X，Y是U的子集。

12、设XY是一个函数依赖，但不是完全函数依赖，则称XY是一个部分函数依赖(Partial Functional Dependency)，或称Y函数依赖于X的某个真子集，记作 。1215.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）1315.2 15.2 关系模式规范化关系模式规范化包含在任何一个候选码中的属性称为主属性(prime attribute)。不包含在任何候选码中的属性称为非主属性(nonprime attribute)或非码属性(non-key attribute)。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码(all-key)。

13、例如，在关系模式 S(Sno,Age,Dept)中，Sno 是码，而在关系模式SC(Sno,Cno,Grade)中属性组合(Sno,Cno)是码。在后面的章节中，主码和候选码都简称为码，读者可从上下文加以区分。定定义义15.7 关系 R 中的属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码(foreign)，也称外码。例如在关系模式 SC(Sno,Cno,Grade)中，单 Sno 不是主码，但 Sno是关系模式 S(Sno,Sname,Age,Dept)主码，所以，Sno 是 SC 的外码，同理，Cno也是 SC 的外码。数据库原理与应用（基于MyS

14、QL）1415.2 15.2 关系模式规范化关系模式规范化主码与外码提供了一个表示关系间的联系手段，例如关系模式 S 与SC 的联系就是通过 Sno 这个在 S 中是主码而在 SC 中是外码来实现的。3.范式范式规范化的基本思想是尽量减小数据冗余，消除数据依赖中不合适的部分，解决插入异常、删除异常和更新异常等问题，这就要求设计出的关系模式要满足一定条件。在关系数据库的规范化过程中，为不同程度的规范化要求设立的不同标准或准则称为范式。满足最低要求的称为第一范式，简称 1NF，在第一范式基础上满足进一步要求的成为第二范式 2NF，以此类推。1971年至1972年，E.F.Codd 系统地提出了 1

15、NF、2NF、3NF 的概念，讨论了关系模式的规范化问题。1974年，Codd 和 Boyce 又共同提出了一个新范式，即 BCNF。1976年有人提出了 4NF，后又有人提出了 5NF各个范式之间的集合关系可以表示为：5NF 4NF BCNF 3NF 2NF 1NF，如图15.1所示。数据库原理与应用（基于MySQL）1515.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）一个低一级范式的关系模式，通过模式分解可以转换成若干个高一级范式的关系模式的集合，该过程称为规范化1615.2 15.2 关系模式规范化关系模式规范化15.2.2 1NF定定义义15.8 在

16、一个关系模式 R 中，如果 R 的每一个属性都是不可再分的数据项，则称 R 属于第一范式 1NF，记作 R1NF。第一范式是最基本的范式，在关系中每个属性都是不可再分的简单数据项。【例15.2】第一范式规范化举例。表15.5所示的关系 R 不是 1NF，关系 R 转化为 1NF 的结果如表15.6所示。数据库原理与应用（基于MySQL）表15.5 关系R 表15.6 关系R转化为1NF1715.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）15.2.3 2NF1815.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）1915.2 1

17、5.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）可以看出，Sno,Cno为主属性，Sname,Age,Dept，DeptHead,Grade为非主属性，由于存在非主属性Sname对候选码(Sno,Cno)的部分依赖，所以，。在SDSC中，既存在完全函数依赖，又存在部分函数依赖和传递函数依赖，导致数据冗余、插入异常、删除异常、修改异常等问题，这在数据库中是不允许的。根据”一事一地”原则，将关系模式SDSC分解为两个关系模式：SD(Sno,Sname,Age,Dept，DeptHead)，SC(Sno,Cno,Grade)分解后的函数依赖图如图15.3和图15.4所示201

18、5.2 15.2 关系模式规范化关系模式规范化分解后的关系模式 SD 的候选码是 Sno，关系模式 SC 的候选码是(Sno,Cno)，非主属性对候选码都是完全函数依赖的，从而消除了非主属性对候选码的部分函数依赖，所以，SD2NF，SC2NF，它们之间通过SC 中的外键 Sno 相联系，需要时进行自然连接，恢复原来的关系，这种分解不会损失任何信息，具有无损连接性。数据库原理与应用（基于MySQL）2115.2 15.2 关系模式规范化关系模式规范化15.2.4 3NF定定义义15.10 如果关系模式 R2NF，R中所有非主属性对任何候选码都不存在传递函数依赖，则称R属于第三范式，记作 R3NF

19、。第三范式具有以下性质。（1）如果 R3NF，则 R 也是 2NF。（2）如果 R2NF，则 R 不一定是 3NF。2NF 的关系模式解决了 1NF 中存在的一些问题，但 2NF 的关系模式 SD 在进行数据操作时，仍然存在以下问题。（1）数据冗余每个系名和系主任名存储的次数等于该系的学生人数。（2）插入异常当一个新系没有招生时，有关该系的信息无法插入。数据库原理与应用（基于MySQL）2215.2 15.2 关系模式规范化关系模式规范化（3）删除异常当某系学生全部毕业没有招生时，删除全部学生记录的同时也删除了该系的信息。（4）修改异常更换系主任时需要更动较多的学生记录。存在以上问题，是因为在

20、 SD 中存在非主属性对候选码的传递函数依赖，消除传递函数依赖就可转换为 3NF。第三范式的规范化指将2NF关系模式通过投影分解，消除非主属性对候选码的传递函数依赖，转换成3NF关系模式的集合过程。分解时遵循”一事一地”原则。【例15.4】第三范式规范化举例。将属于 2NF 的关系模式 SD(Sno,Sname,Age,Dept，DeptHead)分解为：S(Sno,Sname,Age,Dept)D(Dept，DeptHead)数据库原理与应用（基于MySQL）2315.2 15.2 关系模式规范化关系模式规范化分解后的函数依赖图如图15.5和图15.6所示分解后的关系模式S的候选码是 Sno

21、，关系模式 D 的候选码是 Dept，不存在传递函数依赖，所以，S3NF，D3NF。关系模式 SD 由 2NF 分解为 3NF 后，函数依赖关系变得更简单，既无主属性对候选码的部分依赖，又无主属性对候选码的传递依赖，解决了 2NF 存在的4个问题，3NF 的关系模式 S 和 D 特点如下。数据库原理与应用（基于MySQL）2415.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）（1）降低了数据冗余度系主任名存储的次数与该系的学生人数无关，只在关系 D 中存储一次。（2）不存在插入异常当一个新系没有招生时，该系的信息可直接插入到关系 D 中，与学生关系 S 无关。

22、（3）不存在删除异常删除全部学生记录仍然保留该系的信息，可以只删除学生关系 S 中的记录，不影响关系 D 中的数据。（4）不存在修改异常更换系主任时，只需修改关系 D 中一个相应元组的 DeptHead 属性值，不影响关系 S 中的数据。由于 3NF 只限制了非主属性对码的依赖关系，未限制主属性对码的依赖关系，如果发生这种依赖，仍然可能存在）数据冗余、插入异常、删除异常、修改异常，需要对 3NF 进一步规范化，消除主属性对码的依赖关系转换为更高一级的范式，这就是下一节要介绍的 BCNF 范式。2515.2 15.2 关系模式规范化关系模式规范化15.2.5 BCNF定定义义15.11 对于关系

23、模式 R1NF，若XY且 Y X 时 X 必含有码，则 RBCNF。即若R中的每一决定因素都包含码，则 RBCNF。由 BCNF 的定义可以得到如下结论，一个满足 BCNF 的关系模式有：（1）所有非主属性对每一个码都是完全函数依赖。（2）所有主属性对每一个不包含它的码也是完全函数依赖。（3）没有任何属性完全函数依赖于非码的任何一组属性。若 RBCNF，按定义排除了任何属性对码的部分依赖和传递依赖，所以 R3NF。但若 R3NF，则 R 未必属于 BCNF。BCNF 的规范化指将 3NF 关系模式通过投影分解转换成 BCNF 关系模式的集合。数据库原理与应用（基于MySQL）2615.2 15

24、.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）【例15.5】BCNF范式规范化举例。设有关系模式SCN(Sno,Sname,Cno,Grade)，各属性含义为学号、姓名、课程名、成绩，并假定姓名不重名。可以看出，SCN有两个码(Sno,Cno)和(Sname,Cno)，其函数依赖如下：唯一的非主属性Grade对码不存在部分依赖和传递依赖，所以SCN 3NF。但是，由于 ，即决定因素Sno，或Sname不包含码，从另一个角度看，存在主属性对码的部分依赖：，所以 。根据分解的原则，将SCN分解为以下两个关系模式：S(Sno,Sname)SC(Sno,Cno,Grade)27

25、15.2 15.2 关系模式规范化关系模式规范化S 和 SC 的函数依赖图如图15.7和图15.8所示对于 S，两个候选码为 Sno,和Sname，对于 SC，主码为(Sno,Cno)。在上述两个关系模式中，主属性和非主属性都不存在对码的部分依赖和传递依赖，所以，S BCNF，SC BCNF。关系 SCN 转换为 BCNF 后，数据冗余度明显降低，学生姓名只在关系 S 中存储一次，学生改名时，只需改动一条学生记录中相应 Sname的值即可，不会发生修改异常。数据库原理与应用（基于MySQL）2815.2 15.2 关系模式规范化关系模式规范化 数据库原理与应用（基于MySQL）【例15.6】设

26、有关系模式STC(S,T,C)，其中，S表示学生，T表示教师，C表示课程，语义假设是每一位教师只教一门课，每门课有多名教师讲授，某一学生选定某一门课程，就对应一名确定的教师。由语义假设，STC的函数依赖是：，其中，(S,C)和(S,T)都是候选码。函数依赖图如图15.9所示2915.2 15.2 关系模式规范化关系模式规范化由于 STC 没有任何非主属性对码的部分依赖和传递依赖(因为 STC 没有非主属性)，所以 STC 3NF。但不是 BCNF，因为有 TC，T 是决定因素，而 T 不包含候选码。非 BCNF 关系模式分解为 ST(S,T)和 TC(T,C)，它们都是 BCNF15.2.6

27、多值依赖与多值依赖与4NF函数依赖表示的关系模式中属性间一对一或一对多的联系，不能表示属性间多对多的联系，本节讨论属性间多对多的联系即多值依赖问题，以及第四范式。1.多值依赖多值依赖为了说明多值依赖的概念，见下面的例题。【例15.7】设一门课程可由多名教师讲授，他们使用相同的一套参考书，可用如图15.10所示的非规范关系 CTR 表示课程C、教师T和参考书R间的关系。数据库原理与应用（基于MySQL）3015.2 15.2 关系模式规范化关系模式规范化转换成规范化的关系 CTR(C,T,R)，如图15.11所示 数据库原理与应用（基于MySQL）3115.2 15.2 关系模式规范化关系模式规

28、范化关系模式 CTR(C,T,R)的码是(C,T,R)，即全码(all-key)，所以，CTR BCNF。但存在以下问题：（1）数据冗余课程、教师和参考书都被多次存储。（2）插入异常当某一门课程”数据库原理与应用”增加一名讲课教师”周丽”时，必须插入多个元组：(数据库原理与应用,周丽,数据库系统概念),(数据库原理与应用,周丽,数据库系统概论),(数据库原理与应用,周丽,SQL Server 数据库教程)。（3）删除异常当某一门课程”数学”要去掉一本参考书”数学分析”时，必须删除多个元组：(数学,罗燕芬,数学分析),(数学,陈诗雨,数学分析)。分析上述关系模式，发现存在一种称之为多值依赖(Mu

29、lti-Valued Dependency,MVD)的数据依赖。数据库原理与应用（基于MySQL）3215.2 15.2 关系模式规范化关系模式规范化定定义义15.12 设 R(U)是是属性集 U 上的一个关系模式，X、Y、Z 是 U 的子集，且 Z=U-X-Y。如果 R 的任一关系 r，对于给定的(X,Z)上的每一对值，都存在一组 Y 值与之对应，且 Y 的这组值仅仅决定于 X 值而与 Z 的值不相关，则称 Y 多值依赖于 X，或 X 多值决定 Y，记为 XY。若 XY，而 Z，则称 XY 为平凡的多值依赖，否则称 XY 为非平凡的多值依赖。在上例的关系模式 CTR(C,T,R)中，对于给定

30、的(C,R)的一对值(数据库原理与应用,数据库系统概念)，对应的一组 T 值为刘俊松,李智强，这组值仅仅决定于 C 值。对于另一个(数据库原理与应用,SQL Server 数据库教程)，对应的一组 T 值仍为刘俊松,李智强，尽管此时参考书 R 的值已改变。所以，T 多值依赖于 C，记为 CT。2.4NF定定义义15.13 设关系模式 R 1NF，如果对于 R 的每个非平凡多值依赖 XY(Y X)，X 都含有码，则称 R 4NF。数据库原理与应用（基于MySQL）3315.2 15.2 关系模式规范化关系模式规范化由定义可知：（1）根据定义，4NF 要求每一个非平凡的多值依赖 XY，X 都含有码

31、，则必然是 XY，所以 4NF 允许的非平凡多值依赖实际上是函数依赖。（2）一个关系模式是 4NF，则必是 BCNF。而一个关系模式是 BCNF，不一定是 4NF。所以 4NF 是 BCNF 的推广。例15.7的关系模式 CTR(C,T,R)是 BCNF，分解后产生 CTR1(C,T)和CTR2(C,R)，因为 CT，CR 都是平凡的多值依赖，已不存在非平凡的非函数依赖的多值依赖，所以 CTR1 4NF，CTR2 4NF。函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于 BCNF 的关系模式规范化程度已达到最高；如果只考虑多值依赖，则属于 4NF 的关系模式规范化程度已达到

32、最高。在数据依赖中，除函数依赖和多值依赖外，还有其它数据依赖，例如连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖又是连接依赖的一种特殊情况。如果消除了属于 4NF 的关系模式中存在的连接依赖，则可进一步达到 5NF 的关系模式，这里就不再进行讨论了。数据库原理与应用（基于MySQL）3415.2 15.2 关系模式规范化关系模式规范化15.2.7 关系模式规范化的目的、方法和过程关系模式规范化的目的、方法和过程关系模式规范化目的是使结构更合理，消除插入异常、删除异常和更新异常，使数据冗余尽量小，便于插入、删除和更新。关系模式规范化的原则是遵从概念单一化“一事一地”原则，即一个关系模式描

33、述一个实体或实体间的一种联系。规范化的实质就是概念的单一化。方法是将关系模式投影分解为两个或两个以上的模式。一个关系模式只要其每一个属性都是不可再分的数据项，则称为 1NF。消除 1NF 中非主属性对码的部分函数依赖，得到 2NF。消除 2NF 中非主属性对码的传递函数依赖，得到 3NF。消除 3NF 中主属性对码的部分函数依赖和传递函数依赖，得到 BCNF。消除 BCNF 中非平凡且非函数依赖的多值依赖，得到 4NF。如图15.12所示 数据库原理与应用（基于MySQL）352.2 2.2 关系代数关系代数 数据库原理与应用（基于MySQL）3615.3 15.3 数据依赖的公理系统数据依赖

34、的公理系统15.3.1 Armstrong公理系统公理系统定定义义15.14 对于满足一组函数依赖 F 的关系模式 R，其任何一个关系 r，若函数依赖 XY 都成立(即 r 中任意两元组 t、s，若 tX=sX，则 tY=sY)，则称 F 逻辑蕴涵 XY，或称 XY 是 F 的逻辑蕴涵。怎样从一组函数依赖求得蕴涵的函数依赖？怎样求得给定关系模式的码？问题的关键在于已知一组函数依赖F，要问 XY 是否是 F 的逻辑蕴涵。这就需要一组推理规则，这组推理规则就是Armstrong公理系统。Armstrong公理系统(Armstrongs axiom)设 U 为属性集总体，F 是 U 上的一组函数依赖

35、，有关系模式 R，对于 R 来说有以下推理规则：（1）自反律（reflexivity rule）如果 Y X U，则 XY 为 F 所蕴涵。（2）增广律（augmentation rule）如果 XY 为 F 所蕴涵，且 Z U，则 XZYZ 为 F 所蕴涵。数据库原理与应用（基于MySQL）3715.3 15.3 数据依赖的公理系统数据依赖的公理系统（3）传递律（transitivity rule）如果 XY 及 YZ 为 F 所蕴涵，则 XZ 为 F 所蕴涵。注意：注意：XZ 表示 XZ，YZ 表示 YZ。定理定理15.1 Armstrong推理规则是正确的。证明：证明：（1）设 Y X

36、U，对于 R 的任一个关系中任意两元组 t、s：若 tX=sX，因为 Y X，有 tY=sY，所以 XY。（2）设 XY 为 F 所蕴涵，且 Z U，设 R 的任一个关系中任意两元组 t、s：若 tXZ=sXZ，有 tX=sX，tZ=sZ，由 XY，有 tY=sY，数据库原理与应用（基于MySQL）3815.3 15.3 数据依赖的公理系统数据依赖的公理系统所以 tYZ=sYZ，XZYZ 为 F 所蕴涵。（3）设 XY 及 YZ 为 F 所蕴涵，对于 R 的任一个关系中任意两元组 t、s：若 tX=sX，因为 XY，有 tY=sY，由YZ，有 tY=sY，所以 XZ 为 F 所蕴涵。注意：注意

37、：tX 表示元组 t 在属性组 X 上的分量，等价于t.X。根据（1）、（2）、（3）这三条推理规则，可得以下三条推理规则：（4)合并规则(Union Rule)如果 XY，YZ，则 XYZ。（5）分解规则(Decomposition Rule)如果 XY，Z Y，则 XZ。数据库原理与应用（基于MySQL）3915.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）（6）伪传递规则(Preudotransivity Rule)如果XY，Z Y，则XZ。由合并规则和分解规则可得：引理引理15.1 XA1A2.Ak成立的充要条件是XAi成立()。【例15.8】

38、设有关系模式R，A、B、C、D、E、F是它的属性集的子集，R满足的函数依赖为ABC，CDEF，证明函数依赖ADF成立。证明：证明：ABC题中给定AC 引理15.1ADCD增广律CDEF题中给定ADEF传递律ADF引理15.14015.3 15.3 数据依赖的公理系统数据依赖的公理系统15.3.2 闭包及其计算闭包及其计算定定义义15.15 在关系模式 R 中，为 F 所逻辑蕴涵的函数依赖的全体称为 F 的闭包(closure)，记为 F+。把自反律、增广律和传递律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。其有效性是指：由 F 出发根据Armstrong公理推导

39、出来的每一个函数依赖一定在 F+中；其完备性是指：F+中的每一个函数依赖，必定可以由 F 出发根据Armstrong公理推导出来。要证明完备性，首先要解决如何判定一个函数依赖是否属于由 F 根据Armstrong公理推导出来的函数依赖的集合。如果能求出这个集合，也就解决了这个问题。但这是一个 NP 完全问题，例如，从F=XA1,XAn出发，至少可以推导出 2n 个不同的函数依赖。为此，引入以下概念。定定义义15.16 设 F 是属性集 U 上的一组函数依赖，X、Y U，=A|XA 能由 F 根据Armstrong公理推导出，称为属性集 X 关于函数依赖集 F 的闭包。数据库原理与应用（基于My

40、SQL）4115.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）由引理15.1可得出由引理15.2。引理引理15.2 设F是属性集U上的一组函数依赖，X、Y U，XY 能由F根据Armstrong公理推导出的充分必要条件是Y 。这样，判定XY能否由F根据Armstrong公理推导出的问题转化为求出，判定Y是否为 的子集问题，该问题可由算法15.1解决。算法算法15.1 求属性集X(X U)关于U上的函数依赖集F的闭包 。输入：X、F输出：步骤：计算属性集序列 X(i)（i=0，1，）（1）令X(0)=X，i=0。（2）求B，B=A|(V)(W)(VWFV

41、 X(i)AW)。即在F中寻找尚未用过的左边是X(i)的子集的函数依赖：YjZj（j=0，1，k），其中Yj X(i)。再在Zj中寻找X(i)中未出现过的属性构成属性集B。4215.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）（3）X(i+1)=BX(i)。（4）判断X(i+1)=X(i)是否成立，若不成立则转（2）。（5）输出X(i)，即为 。对于（4）的计算停止条件，以下4种方法是等价的：X(i+l)=X(i)。当发现X(i)包含了全部属性时。在F中的函数依赖的右边属性中再也找不到X(i)中未出现过的属性。在F中未用过的函数依赖的左边属性集已没有X

42、(i)的子集。【例15.9】已知关系模式 R，其中，U=A,B,C,D,E，F=ABC,B D,CE,ECB,ACB，求 解：（1）设X(0)=AB。4315.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）（2）在F中找出左边是AB子集的函数依赖，其结果是ABC，BD，则X(1)=X(0)CD=ABCD=ABCD，显然X(1)X(0)。（3）在F中找出左边是ABCD子集的函数依赖，其结果是CE,ACB，则X(2)=X(1)BE=ABCDBE=ABCDE，显然X(2)X(1)。（4）由于X(2)以等于全部属性的集合，所以，=ABCDE【例15.10】设有关

43、系模式R，其中U=A，B，C，D，E，G，函数依赖集F=AD，ABE，BGE，CDG，EC，X=AE，计算 。解：（1）设X(0)=AE。（2）在F中找出左边是AE子集的函数依赖，其结果是AD，EC，则X(1)=X(0)DC=ACDE，显然X(1)X(0)。（3）在F中找出左边是ACDE子集的函数依赖，其结果是CDG，则X(2)=X(1)G=ACDEG。4415.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）（4）虽然X(2)X(1)，但F中未用过的函数依赖的左边属性集已没有X(2)的子集，所以不必再计算下去，即 =ACDEG。定理定理15.2 Arms

44、trong公理是有效的、完备的。Armstrong公理是有效性可由定理15.1得到证明，完备性证明略。Armstrong公理的完备性及有效性说明”导出”与”蕴含”是两个完全等价的概念，F+也可说成是由F出发根据Armstrong公理导出的函数依赖的集合。15.3.3 确定候选码确定候选码设关系模式为R，F为函数依赖集，将U中的属性分为以下4类：L类属性：只在F中各个函数依赖的左部出现。R类属性：只在F中各个函数依赖的右部出现。虽然X(2)X(1)，但F中未用过的函数依赖的左边属性集已没有X(2)的子集，所以不必再计算下去，即=ACDEG。4515.3 15.3 数据依赖的公理系统数据依赖的公理

45、系统 数据库原理与应用（基于MySQL）LR类属性：在F中各个函数依赖的左部和右部两边都出现。N类属性：不在F中各个函数依赖中出现。L类属性集中每一个属性都必定是候选码中的属性，R类和N类属性集中每一个属性都必定不是候选码中的属性，LR类属性集中每一个属性不能确定是否在候选码中。确定候选码的步骤如下：（1）划分属性类别令X为L类属性集的集合，Y为LR类属性集的集合。（2）基于F计算X+若X+包含了R的全部属性，则X是R的唯一候选码，算法结束。否则，转（3）。（3）逐一取Y中单一属性A，与X组成属性组XA，如果 =U，则XA为候选码，令Y=Y-A，转（4）。4615.3 15.3 数据依赖的公理系统数据依赖的公理系统 数据库原理与应用（基于MySQL）（4）如果已找出所有候选码，转（5）；否则，依次取Y中的任意两个、三个属性，与X组成属性组XZ，如果 ，且XZ不包含已求得的候选码，则XZ为候选码。（5）算法结束。【例15.11】设R(A，B，C，D，E，F)，G=ABE，ACF，ADB，BC，CD，求R的所有候选码。解：解：（1）R中L类属性：A，LR类属性：B、C、D。（2）=AU（3）因为 =ABCDEF，所以AB为候选码。因为 =ABCDEF，所以AC为候选码。因为 =ABCDEF，所以AD为候选码。故R的所有候选码为AB，AC，AD。