1、数据库系统概论数据库系统概论 An Introduction to Database System 第六章第六章 关系数据理论关系数据理论 基于某个数据库管理系统设计数据库，如何基于数据库系统编程 第6章 关系数据理论 第7章 数据库设计 第8章 数据库编程 第二篇第二篇 设计与应用开发篇设计与应用开发篇 第六章 关系数据理论 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结 6.1 问题的提出 关系数据库逻辑设计 针对具体问题，如何构造一个适合于它的数据模式 数据库逻辑设计的工具关系数据库的规范化理论 An Introduction to D
2、atabase System * 问题的提出（续） 关系模式由五部分组成，是一个五元组： R(U, D, DOM, F) 关系名R是符号化的元组语义 U为一组属性 D为属性组U中的属性所来自的域 DOM为属性到域的映射 F为属性组U上的一组数据依赖 问题的提出（续） 由于D、DOM与模式设计关系不大，因此在本章中把关系模式看作一个三元组：R 当且仅当U上的一个关系r满足F时，r称为关系模式R的一个关系 作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分开的数据项。满足 了这个条件的关系模式就属于第一范式（1NF） * 问题的提出（续） 数据依赖 是一个关系内部属性与属性之间的一种约束
3、关系 通过属性间值的相等与否体现出来的数据间相互联系 是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现 * 问题的提出（续） 数据依赖的主要类型 函数依赖（Functional Dependency，简记为FD） 多值依赖（Multi-Valued Dependency，简记为MVD） * 问题的提出（续） 函数依赖普遍存在于现实生活中 描述一个学生关系，可以有学号、姓名、系名等属性。 一个学号只对应一个学生，一个学生只在一个系中学习 “学号”值确定后，学生的姓名及所在系的值就被唯一确定。 Sname=f(Sno)，Sdept=f(Sno) 即Sno函数决定Sname Sno函数
4、决定Sdept 记作SnoSname，SnoSdept * 问题的提出（续） 例6.1 建立一个描述学校教务的数据库。 涉及的对象包括： 学生的学号（Sno） 所在系（Sdept） 系主任姓名（Mname） 课程号（Cno） 成绩（Grade） * 问题的提出（续） 假设学校教务的数据库模式用一个单一的关系模式Student来表示，则该关系模式的属性集合 为： U Sno, Sdept, Mname, Cno, Grade 现实世界的已知事实（语义）： 一个系有若干学生， 但一个学生只属于一个系； 一个系只有一名（正职）负责人； 一个学生可以选修多门课程，每门课程有若干学生选修； 每个学生学习
5、每一门课程有一个成绩。 * 问题的提出（续） 由此可得到属性组U上的一组函数依赖F： F=SnoSdept, Sdept Mname, (Sno, Cno) Grade Sno Cno Sdept Mname Grade * 问题的提出（续） 关系模式Student中存在的问题： （1）数据冗余 浪费大量的存储空间 每一个系主任的姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同。 * 问题的提出（续） （2）更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 某系更换系主任后，必须修改与该系学生有关的每一个元组。 * 问题的提出（续） （
6、3）插入异常（Insertion Anomalies） 如果一个系刚成立，尚无学生，则无法把这个系及其系主任的信息存入数据库。 * 问题的提出（续） （4）删除异常（Deletion Anomalies） 如果某个系的学生全部毕业了， 则在删除该系学生信息的同时，把这个 系及其系主任的信息也丢掉了。 * 问题的提出（续） 结论 Student关系模式不是一个好的模式。 一个“好”的模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。 原因 由存在于模式中的某些数据依赖引起的。 解决方法 用规范化理论改造关系模式来消除其中不合适的数据依赖 * 问题的提出（续） 把这个单一的模式分成
7、三个关系模式： S(Sno,Sdept,Sno Sdept); SC(Sno,Cno,Grade,(Sno,Cno) Grade); DEPT(Sdept,Mname,Sdept Mname); 这三个模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控 制。 第六章 关系数据理论 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 6.2.
8、1 函数依赖 1.函数依赖 2.平凡函数依赖与非平凡函数依赖 3.完全函数依赖与部分函数依赖 4.传递函数依赖 * 1. 函数依赖 定义6.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的 任意一个可能的关系r，r 中不可能存在两个元组在X上的属性值相等， 而在Y 上的属性值不等， 则称“X函数确定Y”或“Y函数依赖于X”，记作XY。 函数依赖（续） 例 Student(Sno, Sname, Ssex, Sage, Sdept), 假设不允许重名，则有: Sno Ssex， Sno Sage Sno Sdept， Sno Sname Sname Ssex， Sna
9、me Sage Sname Sdept 但Ssex Sage, Ssex Sdept 若若XY，并且，并且YX, 则记为则记为XY。 若若Y不函数依赖于不函数依赖于X, 则记为则记为XY。 函数依赖（续） Sno Sname Ssex Sage Sdept S1 张三张三 男男 20 计算机系计算机系 S1 李四李四 女女 21 自动化系自动化系 S3 王五王五 男男 20 计算机系计算机系 S4 赵六赵六 男男 21 计算机系计算机系 S5 田七田七 男男 20 计算机系计算机系 . . . . . . . . . . . . . . . 违背了违背了Sno Sname 函数依赖（续） 由下
10、面的关系表, 能否得出Sno Sname Sno Sname Ssex Sage Sdept S1 张三张三 男男 20 计算机系计算机系 S2 李四李四 女女 21 自动化系自动化系 S3 王五王五 男男 20 计算机系计算机系 S4 赵六赵六 男男 21 计算机系计算机系 S5 田七田七 男男 20 计算机系计算机系 . . . . . . . . . . . . . . . 函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的的某个或某些关系实例满足的 约束条件，而是指约束条件，而是指R的所有关系实例均要满足的约束条件。的所有关系实例均要满足的约束条件。 * 函数依赖
11、（续） 函数依赖是语义范畴的概念，只能根据数据的语义来确定一个函数 依赖。 例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立 * 2. 平凡函数依赖与非平凡函数依赖 XY，但YX则称XY是非平凡的函数依赖。 XY，但YX 则称XY是平凡的函数依赖。 对于任一关系模式，平凡函数依赖都是必然成立的，它对于任一关系模式，平凡函数依赖都是必然成立的，它 不反映新的语义。不反映新的语义。 若不特别声明，若不特别声明， 我们总是讨论非平凡函数依赖。我们总是讨论非平凡函数依赖。 * 平凡函数依赖与非平凡函数依赖（续） 若XY，则X称为这个函数依赖的决定因素（Determinant）。 若XY，Y
12、X，则记作XY。 若Y不函数依赖于X，则记作XY。 * 3. 完全函数依赖与部分函数依赖 定义6.2 在R(U)中，如果XY，并且对于X的任何一个真子集X, 都有 X Y, 则 称Y对X完全函数依赖，记作X Y。 若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X Y F P * 完全函数依赖与部分函数依赖（续） 例 在关系SC(Sno, Cno, Grade)中，有： 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade (Sno, Cno)Sno (Sno, Cno) Cno F P P * 4. 传递函数依赖 定义6.3 在R(U)中，如果X
13、Y(YX)，YX，YZ，ZY, 则称Z对X传递函数依赖 (transitive functional dependency)。记为：X Z。 注: 如果YX, 即XY，则Z直接依赖于X，而不是传递函数依赖。 例 在关系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname， Mname传递函数依赖于Sno 传递传递 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 * 6.2.2 码 定义6.4 设K为R
14、中的属性或属性组合。若K U，则K称为R的一个候选 码(Candidate Key)。 如果U部分函数依赖于K，即K U,则K称为超码 （Surpkey）。候选码是最小的超码， 即K的任意一个真子集都不是候选码。 若关系模式R有多个候选码，则选定其中的一个做为主码(Primary key)。 F P * 码（续） 主属性与非主属性 包含在任何一个候选码中的属性 ，称为主属性 （Prime attribute） 不包含在任何码中的属性称为非主属性（Nonprime attribute）或非码属性（Non-key attribute） 全码：整个属性组是码，称为全码（All-key） * 码（续）
15、 例6.2S(Sno, Sdept, Sage)，单个属性Sno是码 SC(Sno, Cno, Grade)中，(Sno, Cno)是码 例6.3 R(P,W,A) P：演奏者 W：作品 A：听众 一个演奏者可以演奏多个作品 某一作品可被多个演奏者演奏 听众可以欣赏不同演奏者的不同作品 码为(P,W,A)，即All-Key * 码（续） 定义6.5 关系模式 R中属性或属性组X 并非 R的码，但 X 是另一个关系模式的 码，则称 X 是R 的外部码（Foreign key）也称外码。 SC(Sno,Cno,Grade)中，Sno不是码 Sno是 S(Sno,Sdept,Sage)的码，则Sno
16、是SC的外码 主码与外部码一起提供了表示关系间联系的手段 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 * 6.2.3 范式 范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足 不同程度要求的为不同范式。 范式的种类： 第一范式第一范式(1NF) 第二范式第二范式(2NF) 第三范式第三范式(3NF) BC范式范式(BCNF) 第四范式第四范式(4NF) 第五范式第五范式(5NF) * 范式（续） 各种范式之间
17、存在联系： 某一关系模式R为第n范式，可简记为RnNF。 NF5NF4BCNFNF3NF2NF1 一个低一级范式的关系模式，通一个低一级范式的关系模式，通 过模式分解（过模式分解（schema decomposition）可以转换为若）可以转换为若 干个高一级范式的关系模式的集干个高一级范式的关系模式的集 合，这种过程就叫合，这种过程就叫规范化规范化 （normalization）。）。 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 * 6.
18、2.4 2NF 定义6.6 若关系模式R1NF，并且每一个非主属性都完全函数依赖于任何一个候 选码，则R2NF 例6.4 S-L-C(Sno,Sdept,Sloc,Cno,Grade)， Sloc为学生的住处，并且每个系的学生住 在同一个地方。S-L-C的码为(Sno,Cno)。 函数依赖有 (Sno,Cno)Grade SnoSdept, (Sno,Cno)Sdept SnoSloc, (Sno,Cno)Sloc SdeptSloc F P P * 2NF（续） Sno Cno Grade Sdept Sloc 关系模式关系模式S-L-C不属于不属于2NF 非主属性非主属性Sdept、Slo
19、c并不完全依赖于码并不完全依赖于码 * 2NF（续） 一个关系模式不属于2NF，会产生以下问题： 插入异常 如果插入一个新学生，但该生未选课，即该生无Cno，由于插入元组时，必须给定码值，因 此插入失败。 删除异常 如果S4只选了一门课C3，现在他不再选这门课，则删除C3后，整个元组的其他信息也被删除 了。 修改复杂 如果一个学生选了多门课，则Sdept，Sloc被存储了多次。如果该生转系，则需要修改所有相 关的Sdept和Sloc，造成修改的复杂化。 * 2NF（续） 出现这种问题的原因 例子中有两类非主属性： 一类如Grade，它对码完全函数依赖 另一类如Sdept、Sloc，它们对码不是
20、完全函数依赖 解决方法： 用投影分解把关系模式S-L-C分解成两个关系模式 SC(Sno,Cno,Grade) S-L(Sno,Sdept,Sloc) 2NF（续） SC的码为(Sno,Cno),SL的码为Sno，这样使得非主属性对 码都是完全函数依赖了 Sno Cno Grade Sno Sdept Sloc 图图6.4 SC中的函数依赖中的函数依赖 图图6.5 S-L中的函数依赖中的函数依赖 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结
21、* 6.2.5 3NF 定义6.7 设关系模式R1NF,若R中不存在这样的码X、属性组Y及非主属 性Z（Z Y）, 使得XY，YZ成立，Y X不成立，则称R 3NF。 SC没有传递依赖，因此SC 3NF S-L中Sno Sdept( Sdept Sno), SdeptSloc，可得Sno Sloc。 解决的办法是将S-L分解成 S-D(Sno,Sdept) 3NF D-L(Sdept,Sloc) 3NF 传递传递 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2
22、.9 规范化小结 * 6.2.6 BCNF BCNF（Boyce Codd Normal Form）由Boyce和Codd提出，比3NF更进了一步。 通常认为BCNF是修正的第三范式，有时也称为扩充的第三范式。 定义6.8 设关系模式R1NF，若X Y且Y X时X必含有码，则 RBCNF。 换言之，在关系模式R中，如果每一个决定属性集都包含候选码，则 RBCNF。 * BCNF（续） BCNF的关系模式所具有的性质 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性 如果一个关系数据库中的所有关系模式都属于BCN
23、F，那么在函数依赖范畴内， 它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删 除异常。 BCNF（续） 例6.5考察关系模式C(Cno,Cname,Pcno) 它只有一个码Cno，没有任何属性对Cno部分依赖或传递依赖，所以C3NF。 同时C中Cno是唯一的决定因素，所以CBCNF。 对于关系模式SC(Sno,Cno,Grade)可作同样分析。 例6.6 关系模式S(Sno,Sname,Sdept,Sage)， 假定Sname也具有唯一性，那么S就有两个码，这两个码都由单个属性组成， 彼此不相交。 其他属性不存在对码的传递依赖与部分依赖，所以S3NF。 同时S中除Sno，S
24、name外没有其他决定因素，所以S也属于BCNF。 BCNF（续）（续） BCNF（续） 例6.7 关系模式SJP(S,J,P)中，S是学生，J表示 课程，P表示名次。每一个学生选修每门课程的 成绩有一定的名次，每门课程中每一名次只有一 个学生（即没有并列名次）。 由语义可得到函数依赖： (S,J)P；(J,P)S (S,J)与(J,P)都可以作为候选码。 关系模式中没有属性对码传递依赖或部分依赖，所以 SJP3NF。 除(S,J)与(J,P)以外没有其他决定因素，所以 SJPBCNF。 BCNF（续） 例6.8 关系模式STJ(S,T,J)中，S表示学生，T表 示教师，J表示课程。每一教师只
25、教一门课。每 门课有若干教师，某一学生选定某门课，就对应 一个固定的教师。 由语义可得到函数依赖：(S,J)T；(S,T)J；TJ 因为没有任何非主属性对码传递依赖或部分依赖， STJ 3NF。 因为T是决定因素，而T不包含码，所以STJ BCNF 关系。 图图6.6 STJ中的函数依赖中的函数依赖 BCNF（续） 对于不是BCNF的关系模式，仍然存在不合适的地方。 非BCNF的关系模式也可以通过分解成为BCNF。例如STJ可分解为ST(S,T)与TJ(T,J)， 它们都是BCNF。 BCNF（续） 3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度 的测度。 一个模式中的关系模
26、式如果都属于BCNF，那么在函数依赖范畴内，它已实 现了彻底的分离，已消除了插入和删除的异常。 3NF的“不彻底”性表现在可能存在主属性对码的部分依赖和传递依赖。 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 * 6.2.7 多值依赖 例6.9设学校中某一门课程由多个教师讲授，他们 使用相同的一套参考书。每个教员可以讲授多门课 程，每种参考书可以供多门课程使用 用关系模式Teaching(C,T,B)来表示课程C、教师T和参 考书B之间的关系
27、。 多值依赖（续） 表表6.3 非规范化关系示例非规范化关系示例 课程课程 C 教员教员 T 参考书参考书 B 物理物理 数学数学 计算数学计算数学 李李 勇勇 王王 军军 李李 勇勇 张张 平平 张张 平平 周周 峰峰 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 数学分析数学分析 微分方程微分方程 高等代数高等代数 数学分析数学分析 * 多值依赖（续） 表表6.4 规范化规范化的二维表的二维表 Teaching 课程课程 C 教员教员 T 参考书参考书 B 物物 理理 李李 勇勇 普通物理学普通物理学 物物 理理 李李 勇勇 光学原理光学原理 物物 理理 李李 勇勇 物理习
28、题集物理习题集 物物 理理 王王 军军 普通物理学普通物理学 物物 理理 王王 军军 光学原理光学原理 物物 理理 王王 军军 物理习题集物理习题集 数数 学学 李李 勇勇 普通物理学普通物理学 数数 学学 李李 勇勇 光学原理光学原理 数数 学学 李李 勇勇 物理习题集物理习题集 数数 学学 张张 平平 普通物理学普通物理学 数数 学学 张张 平平 光学原理光学原理 数数 学学 张张 平平 物理习题集物理习题集 * 多值依赖（续） Teaching具有唯一候选码(C,T,B)， 即全码。 TeachingBCNF * 多值依赖（续） 课程课程 C 教员教员 T 参考书参考书 B 物物 理理
29、李李 勇勇 普通物理学普通物理学 物物 理理 李李 勇勇 光学原理光学原理 物物 理理 李李 勇勇 物理习题集物理习题集 物物 理理 王王 军军 普通物理学普通物理学 物物 理理 王王 军军 光学原理光学原理 物物 理理 王王 军军 物理习题集物理习题集 数数 学学 李李 勇勇 普通物理学普通物理学 数数 学学 李李 勇勇 光学原理光学原理 数数 学学 李李 勇勇 物理习题集物理习题集 数数 学学 张张 平平 普通物理学普通物理学 数数 学学 张张 平平 光学原理光学原理 数数 学学 张张 平平 物理习题集物理习题集 (1)数据冗余度大：有多数据冗余度大：有多 少名任课教师，参考书少名任课教师
30、，参考书 就要存储多少次。就要存储多少次。 * 多值依赖（续） 课程课程 C 教员教员 T 参考书参考书 B 物物 理理 李李 勇勇 普通物理学普通物理学 物物 理理 李李 勇勇 光学原理光学原理 物物 理理 李李 勇勇 物理习题集物理习题集 物物 理理 王王 军军 普通物理学普通物理学 物物 理理 王王 军军 光学原理光学原理 物物 理理 王王 军军 物理习题集物理习题集 数数 学学 李李 勇勇 普通物理学普通物理学 数数 学学 李李 勇勇 光学原理光学原理 数数 学学 李李 勇勇 物理习题集物理习题集 数数 学学 张张 平平 普通物理学普通物理学 数数 学学 张张 平平 光学原理光学原理
31、数数 学学 张张 平平 物理习题集物理习题集 (2)增加操作复杂：当增加操作复杂：当 某一课程增加一名任某一课程增加一名任 课教师时，该课程有课教师时，该课程有 多少本参照书，就必多少本参照书，就必 须插入多少个元组。须插入多少个元组。 * 多值依赖（续） 课程课程 C 教员教员 T 参考书参考书 B 物物 理理 李李 勇勇 普通物理学普通物理学 物物 理理 李李 勇勇 光学原理光学原理 物物 理理 李李 勇勇 物理习题集物理习题集 物物 理理 王王 军军 普通物理学普通物理学 物物 理理 王王 军军 光学原理光学原理 物物 理理 王王 军军 物理习题集物理习题集 数数 学学 李李 勇勇 普通
32、物理学普通物理学 数数 学学 李李 勇勇 光学原理光学原理 数数 学学 李李 勇勇 物理习题集物理习题集 数数 学学 张张 平平 普通物理学普通物理学 数数 学学 张张 平平 光学原理光学原理 数数 学学 张张 平平 物理习题集物理习题集 (3)删除操作复杂：某一删除操作复杂：某一 门课要去掉一本参考书，门课要去掉一本参考书， 该课程有多少名教师，该课程有多少名教师， 就必须删除多少个元组。就必须删除多少个元组。 * 多值依赖（续） 课程课程 C 教员教员 T 参考书参考书 B 物物 理理 李李 勇勇 普通物理学普通物理学 物物 理理 李李 勇勇 光学原理光学原理 物物 理理 李李 勇勇 物理
33、习题集物理习题集 物物 理理 王王 军军 普通物理学普通物理学 物物 理理 王王 军军 光学原理光学原理 物物 理理 王王 军军 物理习题集物理习题集 数数 学学 李李 勇勇 普通物理学普通物理学 数数 学学 李李 勇勇 光学原理光学原理 数数 学学 李李 勇勇 物理习题集物理习题集 数数 学学 张张 平平 普通物理学普通物理学 数数 学学 张张 平平 光学原理光学原理 数数 学学 张张 平平 物理习题集物理习题集 (4)修改操作复杂：某一修改操作复杂：某一 门课要修改一本参考书，门课要修改一本参考书， 该课程有多少名教师，该课程有多少名教师， 就必须修改多少个元组。就必须修改多少个元组。 产
34、生原因产生原因: 存在多值依赖存在多值依赖 * 多值依赖（续） 定义6.9 设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集，并且Z=U-X-Y。 关系模式R(U)中多值依赖XY成立，当且仅当对R(U)的任一关系r，给定的 一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。 例 Teaching（C, T, B） 对于C的每一个值，T有一组值与之对应，而不论 B取何值。因此T多值依赖于C，即CT。 多值依赖（续） 多值依赖的另一个等价的定义 在R(U)的任一关系r中，如果存在元组t，s使得tX=sX ，那么就必然存在元组w，vr，（w，v可以与s，t相 同）, 使得w
35、X=vX=tX，而wY=tY，wZ=sZ， vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两 个新元组必在r中则Y多值依赖于X，记为XY。这里 X，Y是U的子集，Z=U-X-Y。 * 多值依赖（续） 平凡多值依赖和非平凡的多值依赖 若XY，而Z，即Z为空，则称XY为平凡的多值依赖。 否则称XY为非平凡的多值依赖。 多值依赖（续） 例6.10关系模式WSC(W,S,C)中，W表示仓库，S 表示保管 员，C 表示商品。假设每个仓库有若干个保管员，有若干种 商品。每个保管员保管所在仓库的所有商品，每种商品被所 有保管员保管。 W S C W1 S1 C1 W1 S1 C2 W1 S1 C3 W
36、1 S2 C1 W1 S2 C2 W1 S2 C3 W2 S3 C4 W2 S3 C5 W2 S4 C4 W2 S4 C5 多值依赖（续） 按照语义对于W的每一个值Wi，S有一个完整的集合与之对应而不问C取何值。 所以WS。 如图6.7所示 对应W的某一个值Wi的全部S值记作SWi（表示此仓库工作的全部保管员） 全部C值记作CWi（表示在此仓库中存放的所有商品） 应当有SWi中的每一个值和CWi中的每一个C值对应 于是SWi与CWi之间正好形成一个完全二分图，因而WS。 多值依赖（续） 由于C与S的完全对称性，必然有WC成立。 图图6.7 WS且且WC 多值依赖（续） 多值依赖的性质 （1）多
37、值依赖具有对称性。 即若XY，则XZ，其中ZUXY 多值依赖的对称性可以用完全二分图直观地表示出来。 从例6.10 容易看出，因为每个保管员保管所有商品，同时每种商品被所有保管员保管， 显然若WS，必然有WC。 * 多值依赖（续） （2）多值依赖具有传递性。即若XY，YZ， 则 XZ -Y。 （3）函数依赖是多值依赖的特殊情况。即若XY，则 XY。 （4）若XY，XZ，则XYZ。 （5）若XY，XZ，则XYZ。 （6）若XY，XZ，则XY-Z，XZ -Y。 * 多值依赖（续） 多值依赖与函数依赖的区别 （1）多值依赖的有效性与属性集的范围有关 若XY在U上成立，则在W（XY W U）上一定成立
38、；反之则不然，即XY在W（W U）上成立，在U上并不一定成立。 原因：多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。 * 多值依赖（续） 多值依赖的有效性与属性集的范围有关（续） 一般地，在R(U)上若有XY在W(W U)上成立，则称XY为R(U)的嵌入型多值依赖。 函数依赖XY的有效性仅决定于X、Y这两个属性集的值 只要在R(U)的任何一个关系r中，元组在X和Y上的值满足定义6.l，则函数依赖XY在任何属性 集W(XY W U)上成立。 * 多值依赖（续） （2）若函数依赖XY在R (U)上成立，则对于任何Y Y均有XY 成立。多值依赖XY若在 R(U)上成立，不能断言对于任
39、何Y Y有XY 成立。 * 多值依赖（续） 例如，关系R(A,B,C,D)，ABC成立，当然也有AD成立。有R的一个关系实例，在此实 例上AB是不成立的。 A B C D a1 b1 c1 d1 a1 b1 c1 d2 a1 b2 c2 d1 a1 b2 c2 d2 表表6.6 R的一个实例的一个实例 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结 * 6.2.8 4NF 定义6.10 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y
40、X），X都含有码，则R4NF。 4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。 4NF所允许的非平凡多值依赖实际上是函数依赖。 * 4NF（续） 如果一个关系模式是4NF， 则必为BCNF。 在例6.10的WSC中，W S, WC,他们都是非平凡多值依赖。而W不是码， 关系模式WSC的码是(W,S,C)，即All-key，因此WSC 4NF。 可以把WSC分解成WS(W,S),WC(W,C)， WS4NF，WC4NF。 6.2 规范化 6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依
41、赖 6.2.8 4NF 6.2.9 规范化小结 * 6.2.9 规范化小结 在关系数据库中，对关系模式的基本要求是满足第一范式。 规范化程度过低的关系不一定能够很好地描述现实世界 可能存在插入异常、删除异常、修改复杂、数据冗余等问题 解决方法就是对其进行规范化，转换成高级范式。 * 规范化小结（续） 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的 关系模式集合，这种过程就叫关系模式的规范化。 关系数据库的规范化理论是数据库逻辑设计的工具。 * 规范化小结（续） 规范化的基本思想 是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。 即采用“一事一地
42、”的模式设计原则 让一个关系描述一个概念、一个实体或者实体间的一种联系。 若多于一个概念就把它“分离”出去。 因此 规范化实质上是概念的单一化。 * 规范化小结（续） 关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖 消除决定因素 2NF 非码的非平凡 消除非主属性对码的传递函数依赖 函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF 图图6.8 规范化过程规范化过程 * 规范化小结（续） 不能说规范化程度越高的关系模式就越好。 必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映 现实世界的模式。
43、上面的规范化步骤可以在其中任何一步终止。 第六章 关系数据理论 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结 * 6.3 数据依赖的公理系统 定义6.11 对于满足一组函数依赖F的关系模式 R ，其任何一个关系r， 若函数依赖XY都成立（即r中任意两元组t、s，若tX=sX，则 tY=sY）， 则称F逻辑蕴涵X Y。 * 数据依赖的公理系统（续） Armstrong公理系统 一套推理规则，是模式分解算法的理论基础 用途 求给定关系模式的码 从一组函数依赖求得蕴涵的函数依赖 * 数据依赖的公理系统（续） Armstrong公理系统 设U为属性
44、集总体，F是U上的一组函数依赖， 于是有关 系模式R 。对R 来说有以下的推理规则： A1 自反律（reflexivity rule）：若Y X U，则X Y 为F所蕴涵。 A2 增广律（augmentation rule）：若XY为F所蕴涵，且Z U，则XZYZ 为F所蕴涵。 A3 传递律（transitivity rule）：若XY及YZ为F所蕴涵，则XZ 为F所蕴涵。 注意：由自反律所得到的函数依赖均是平凡的函数依赖, 自反律的使用并不依赖于F。 * 数据依赖的公理系统（续） 定理6.1 Armstrong推理规则是正确的。 证明 A1 自反律 设Y X U 。 对R 的任一关系r中的任
45、意两个元组t、s： 若tX=sX，由于Y X，有tY=sY， 所以XY成立， 自反律得证。 * 数据依赖的公理系统（续） A2 增广律 设XY为F所蕴涵，且Z U。 对R 的任一关系r中任意的两个元组t、s： 若tXZ=sXZ，则有tX=sX和tZ=sZ； 由XY，于是有tY=sY， 所以tYZ=sYZ，XZYZ为F所蕴涵， 增广律得证。 * 数据依赖的公理系统（续） A3 传递律 设XY及YZ为F所蕴涵。 对R 的任一关系r中的任意两个元组t、s： 若tX=sX，由于XY，有tY=sY； 再由YZ，有tZ=sZ， 所以XZ为F所蕴涵， 传递律得证。 * 数据依赖的公理系统（续） 根据A1，A
46、2，A3这三条推理规则可以得到下面三条推理规则： 合并规则（union rule）： 由XY，XZ，有XYZ。 伪传递规则（pseudo transitivity rule）： 由XY，WYZ，有XWZ。 分解规则（decomposition rule）： 由XY及ZY，有XZ。 * 数据依赖的公理系统（续） 根据合并规则和分解规则，可得引理6.1 引理6.1 XA1 A2Ak成立的充分必要条件是XAi成立（i=1，2， k）。 * 数据依赖的公理系统（续） 定义6.12 在关系模式R中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包，记为 F +。 定义6.13 设F为属性集U上的一组函数依赖，X
47、、Y U， XF+= A|XA能由F根据 Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。 * 数据依赖的公理系统（续） 引理6.2 设F为属性集U上的一组函数依赖，X、Y U，XY能由F根据Armstrong公 理导出的充分必要条件是Y XF+。 引理6.2的用途 判定XY是否能由F根据Armstrong公理导出的问题，就 转化为求出XF+，判定Y是否为XF+的子集的问题。 * 数据依赖的公理系统（续） 求闭包的算法 算法6.1 求属性集X（X U）关于U上的函数依赖集F的闭包XF+ 输入：X，F 输出：XF+ 步骤： 迭代迭代 * 数据依赖的公理系统（续） 令X(0)
48、=X，i=0 求B，这里B = A |( V)( W)(VWF V X(i)A W)。 X(i+1)=BX(i) 。 判断X(i+1)= X(i) 。 若X(i+1)与X(i)相等或X(i)=U ，则X(i)就是XF+， 算法终止。 若否，则i=i+1，返回第步。 对对X (i)中的每个元素，依次检查相应 中的每个元素，依次检查相应 的函数依赖的函数依赖,将依赖它的属性加入将依赖它的属性加入B * 数据依赖的公理系统（续） 例6.11 已知关系模式R，其中 U=A, B, C, D, E； F=ABC, BD, CE, ECB, ACB。 求(AB)F+ 。 * 数据依赖的公理系统（续） 解
49、：由算法6.1，设X(0)=AB。 计算X(1)：逐一的扫描F集合中各个函数依赖，找左部为 A、B或AB的函数依赖。得到两个：ABC，BD。于 是X(1)=ABCD=ABCD。 因为X(0) X(1)，所以再找出左部为ABCD子集的那些函数 依赖，又得到CE，ACB，于是 X(2)=X(1)BE=ABCDE。 因为X(2)已等于全部属性集合，所以(AB)F+ =ABCDE。 参见爱课程网数据库系统概论6.3节动画求闭包 * 数据依赖的公理系统（续） 有效性与完备性的含义 有效性：由F 出发根据Armstrong公理推导出来的每一个函数依赖一定在F +中 完备性：F +中的每一个函数依赖，必定可
50、以由F出发根据Armstrong公理推导出来 * 定理6.2 Armstrong公理系统是有效的、完备的。 证明： 1. 有效性 有效性实际上是“正确性” 可由定理6.1得证 数据依赖的公理系统（续）数据依赖的公理系统（续） * 2. 完备性 只需证明逆否命题：若函数依赖XY不能由F从Armstrong公理导出，那么它必然不为F 所蕴涵 分三步证明： （1） 若VW成立，且V XF+，则W XF+ 证：因为 V XF+，所以有XV成立； 因为X V，VW，于是XW 成立； 所以W XF+ 。 数据依赖的公理系统（续）数据依赖的公理系统（续） * （2）构造一张二维表r，它由下列两个元组构成，可
