数据库系统概论-第六章.ppt

数据库系统概论 An Introduction to Database System 第六章 关系数据理论,第六章 关系数据理论,6.1 关系模式设计的问题 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结,6.1关系模式设计的问题,关系数据库逻辑设计 针对具体问题，如何构造一个适合于它的数据模式 数据库逻辑设计的工具关系数据库的规范化理论,概念回顾 关系：描述实体、属性、实体间的联系。 从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。 关系模式：用来定义关系。 关系数据库：基于关系模型的数据库，利用关系来描述现实世界。 从形式上看，它由一组关系组成。 关系数据库的模式：定义这组关系的关系模式的全体。,6.1 关系模式设计的问题,关系模式由五部分组成，即它是一个五元组： R(U, D, DOM, F) R： 关系名 U： 组成该关系的属性名集合 D： 属性组U中属性所来自的域 DOM：属性向域的映象集合 F： 属性间数据的依赖关系集合 关系模式R（U, D, DOM, F）简化为一个三元组：R（U, F） 当且仅当U上的一个关系r 满足F时，r称为关系模式 R（U, F）的一个关系 有时候，更简写成R(U)，即R(A1,A2,An)的形式,6.1 关系模式设计的问题,如何设计一个适合的关系数据库系统，关键是关系数据库模式的设计，一个好的关系数据库模式应该包括多少关系模式，而每一个关系模式又应该包括哪些属性，又如何将这些相互关联的关系模式组建一个适合的关系模型，这些工作决定了到整个系统运行的效率，也是系统成败的关键所在，这属于数据库设计的问题，确切地讲是数据库逻辑设计的问题(有关数据库设计的全过程将在第7章详细讨论)。 本章讲述关系数据库规范化理论，这是数据库逻辑设计的理论依据。,6.1 关系模式设计的问题,规范化理论主要包括三个方面的内容： 函数依赖 范式（Normal Form） 模式设计 其中，函数依赖起着核心的作用，是模式分解和模式设计的基础，范式是模式分解的标准。,6.1 关系模式设计的问题,关系模式的存储异常问题 数据库的逻辑设计为什么要遵循一定的规范化理论？ 什么是好的关系模式？ 某些不好的关系模式可能导致哪些问题？ 下面通过例子进行分析:,6.1 关系模式设计的问题,描述教学管理数据库: 学号(sno),姓名(sname),年龄(age),所在系别(dept),所在系的系主任姓名(Mn),选修的课程号(cno),该课程的成绩(score) 用一个单一的关系模式来表达： SCD(Sno,Sname,Age,Dept,Mn,Cno,Score) 语义定义如下: 一个系有若干个学生，但一个学生只属于一个系； 一个系只有一名系主任； 一个学生可以选修多门功课，每门课程可有若干学生选修； 每个学生学习课程有一个成绩。,6.1 关系模式设计的问题,教学管理数据库的一个实例:,6.1 关系模式设计的问题,关系模式SCD存在的问题: 1. 数据冗余 浪费大量的存储空间 例：每一个系主任的姓名重复出现 2. 更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任，或学生改名后,6.1 关系模式设计的问题,关系模式SCD存在的问题(续): 3. 插入异常（Insertion Anomalies） 该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。又如，学生未选课，则学生信息无法输入. (为什么？) 4. 删除异常（Deletion Anomalies） 不该删除的数据不得不删 例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,6.1 关系模式设计的问题,结论: 关系模式SCD不是一个好的模式。 “好”的模式应该满足： 不会发生插入异常、删除异常、更新异常， 数据冗余应尽可能少。 产生的原因：模式中的某些数据依赖引起的 解决方法：分解! 学生关系S(SNO,SN,AGE,DEPT) 选课关系SC(SNO,CNO,SCORE) 系关系D(DEPT,MN),6.1 关系模式设计的问题,分解后: (左上：S； 左下：Dept; 右： SC),6.1 关系模式设计的问题,分解后的关系模式是“好” 的。 不过，一个好的关系模式并不是在任何情况下都是最优的。 如何按照一定的规范设计关系模式，将结构复杂的关系分解成结构简单的关系，从而把“不好”的关系数据库模式转变为“好”的关系数据库模式，这就是关系的规范化。 规范化又可以根据不同的要求而分成若干级别。 数据库模式的好坏和关系中各属性间的依赖关系有关，因此，我们先讨论属性间的依赖关系，然后再讨论关系规范化理论。,6.1 关系模式设计的问题,6.1 关系模式设计的问题 6.2 规范化 6.3 数据依赖的公理系统 6.4 关系模式的分解 6.5 小结,第6章 关系数据库设计理论,函数依赖 平凡函数依赖与非平凡函数依赖 完全函数依赖与部分函数依赖 传递函数依赖,6.2.1 函数依赖,1. 函数依赖 定义6.1 设R(U)是一个属性集U上的关系模式，X , Y U， r是R(U) 上的任意一个关系，如果成立 对t , s r，若tX = sX，则tY = sY 则称 “X函数确定Y” 或 “Y函数依赖于X”，记作XY。(或不存在t,s, tX=sX而tYsY) X称为这个函数依赖的决定属性集(Determinant)。 Y = f(x),6.2.1 函数依赖,R(A,B,C,D,E):,tY,tX,sX,sY,S,t,只要sX = tX 就有 sY = tY: XY,函数依赖,能找出哪些函数依赖关系?,学号姓名 学号年龄 学号系别 学号系主任 学号 (姓名,年龄,系别,系主任) 系别系主任 (学号,课程号)成绩 请思考： (学号,姓名)年龄 ? (年龄,系别)系别 ? (平凡的函数依赖) (学号,课程号) ?,函数依赖,两个记号： 若XY，并且YX, 则记为XY。 若Y不函数依赖于X, 则记为XY。 有关函数依赖的几点说明: 1) 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 2) 函数依赖是语义范畴的概念。 只能根据语义来确定一个函数依赖。例如，对于前述关系模式，当学生不存在重名的情况下，可以得到： 姓名年龄 姓名系别 3) 函数依赖关系的存在与时间无关。,函数依赖,4) 函数依赖与属性之间的联系类型有关。 在一个关系模式中，如果属性X与Y有1:1联系时，则存在函数依赖XY，YX，即XY。 如果属性X与Y有m:1的联系时，则只存在函数依赖XY。 例如，SNO与DEPT之间为m:1联系，所以有SNODEPT。 如果属性X与Y有m: n的联系时，则X与Y之间不存在任何函数依赖关系。 例如，一个学生可以选修多门课程，一门课程又可以为多个学生选修，所以SNO与CNO之间不存在函数依赖关系。,函数依赖,2.平凡函数依赖与非平凡函数依赖 定义6.2 在关系模式R(U)中，对于U的子集X和Y，如果XY，但Y X，则称XY是非平凡的函数依赖。若XY，但Y X, 则称XY是平凡的函数依赖。 非平凡的函数依赖: (学号,课程号)成绩 平凡的函数依赖: (学号,课程号)学号 (年龄,系别)系别 对于任何关系模式，平凡的函数依赖总是成立的，除非特别说明，我们总是讨论非平凡的函数依赖。,函数依赖,3. 完全函数依赖与部分函数依赖 定义6.3 设关系模式R(U)，U是属性全集，X和Y是U的子集: 如果XY，并且对于X的任何一个真子集X,都有XY，则称Y完全函数依赖于X，记作X f Y。 如果对X的某个真子集X，有XY，则称Y部分函数依赖于X，记作X p Y。 在SCD中，因为学号 成绩，且课程号 成绩，所以有：（学号，课程号） f 成绩 。 而学号年龄，所以（学号，课程号） p 年龄。,函数依赖,4. 传递函数依赖 定义6.4 在关系模式R(U)中，如果XY，YZ，且Y X，YX，则称Z传递函数依赖于X。 注: 如果YX， 即XY，则Z直接依赖于X。 在前述关系模式SCD中，有： 学号 系别，系别 系主任 系主任传递函数依赖于学号,函数依赖,码 定义6.5 设K为关系模式R中的属性或属性组合。若K U，则K称为R的一个侯选码Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primary key）。 主属性与非主属性 全码(ALL KEY),码的定义,外码 定义6.6 关系模式 R 中属性或属性组X 并非R的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码（Foreign key）也称外码 主码和外部码一起提供了表示关系间联系的手段。,码的定义,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,6.2 关系模式的规范化,范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。 通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化。 范式的级别：,范式,策略 概念单一化：一个关系模式表示一个概念，一个实体，一个实体间联系；多余部分分解出去。 目标 较少冗余 避免修改麻烦 避免操作异常 某一关系模式R为第n范式，可简记为RnNF。,范式,1.定义 任给关系模式R(U,F)，若U中每个属性及其值均为不可再分的基本数据元素（原子项），则R1NF。 2.说明 关系DBS中,所有关系模式至少都必须是1NF。否则不能称为关系数据库系统。 例,1NF,3.转换: 非1NF 1NF 去掉嵌套属性的上层(保留最底层);重写行交叉处的值,1NF,4. 1NF 存在的问题 SCD(Sno,Sname,Age,Dept,Mn,Cno,Score),1NF,1NF存在的问题(续) 数据冗余;更新复杂;插入异常;删除异常 5. 症由: 非主属性部分函数依赖于候选码 候选码: (Sno,Cno) U 注意到: Sno (sno,sname, age,dept,mn) 所以, 姓名、年龄、系别和系主任部分依赖于候选码。 6. 解决方法：规范化(投影分解) 消除非主属性对码的部分依赖。 所有完全函数依赖于码的属性组成一个关系模式 所有部分FD于码的属性组成一个关系模式,1NF,分解后,1NF,SD,SC,分解后消除了哪些弊端？还保留了哪些弊端?,1.定义 定义6.12 若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。 例6.10 SD(sno,sname,age,dept,mn), F=snosname, snoage, snodept, deptmn. 码为sno, SD 2NF。 SC(sno,cno,score),F=(sno,cno)score. 码为(sno,cno), SC 2NF。,2NF,推论: 若R1NF,且其候选码为单个属性,则R2NF (为什么?),2NF,2. 2NF存在的问题 SD(sno,sname,age,dept,mn) 2NF 冗余仍存在:系主任信息冗余； 更新复杂:某系换系主任，需同时更改很多信息； 插入异常:某系无学生,则系及系统主任信息不能插入； 删除异常:删除某系全部学生,则将删除系及主任信息。 3. 症由 非主属性对码的传递依赖:snodept, deptmn 4. 解决方法 投影分解,消去非主属性对码的传递依赖。,2NF,分解后,2NF,S,D,1.定义 定义6.13 关系模式R 中若不存在这样的码X、属性组Y及非主属性Z（Z Y）, 使得XY，Y X，YZ，成立，则称R 3NF。 若R 3NF,则每一非主属性既不部分依赖于码也不传递依赖于码。 若R 3NF ,则必有R 2NF 。 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。,3NF,推论1: 若R2NF，且至多存在一个非主属性，则R3NF 推论2: 任何二元关系模式R(A,B)必为3NF。 2. 说明 部分FD和传递FD是冗余及操作异常的重要根源。 3NF不存在非主属性对候选码的部分FD和传递FD。 3NF消去了大部分冗余及操作异常。 但并非所有的3NF都能完全消除冗余及操作异常。,3NF,例6.11 关系模式STJ(S,T,J)中,S表示学生,T表示教师,J表示课程。每一教师只教一门课,每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。即有: (S,J) T; (S,T) J; T J 显然(S,J),(S,T)都是候选码 STJ是3NF,3NF,3. 3NF仍可能存在冗余与更新异常 以STJ 3NF 为例 冗余:多个学生选同一老师的课时,T,J重复。 修改麻烦:课程改名，需改多处。 插入异常: 学生未选课或教师开课无人选时 删除异常: 删除学生信息时,3NF,4. 症由? 存在主属性对候选码的部分FD。 (S,T) J; T J 存在主属性对候选码的传递FD。 (S,J) T; T J 5. 解决方法 投影分解,消去主属性对候选码的部分FD ST(S,T), TJ(T,J),3NF,6. 分解后 冗余得到控制 插入异常得以避免 删除异常得以避免 修改麻烦避免了,3NF,1.定义 定义6.14 设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么RBCNF。 2. BC范式的性质 每一个函数依赖中的左部决定属性集都包含有候选码。 不存在非主属性对候选码的部分FD。 不存在非主属性对候选码的传递FD。 所有主属性都完全FD于不包含它的候选码。 没有任何属性完全函数依赖于非码的任何一组属性。,BCNF,3. 定理 如果RBCNF，则R3NF 证 反证法.设R是BC范式,但不是3NF.则必存在非主属性对码的传递FD.即存在非主属性Z,通过属性组Y，传递依赖于码 X，亦即XY，YZ成立，这里Z Y , Y X. 根据BCNF的定义，Y必含有某个候选码K。由候选码的定义，有: Y X. 这与Y X矛盾，定理得证。,BCNF,例6.12 前述STJ(S,T,J)是3NF但不是BCNF，但分解后的ST(S,T)以及TJ(T,J)都是BCNF. 例6.13 前述S(sno,sname,age,dept)和D(dept,mn)以及SC(sno,cno,score)均为BCNF。 例6.14 关系模式SJP(S,J,P)中，S指学生,J表示课程,P表示名次。每个学生选修一门课获得一定的名次，没有并列名次。即: (S,J) P; (J,P) S (S,J)和(J,P)都可以作候选码, SJP BCNF,BCNF,1.问题的提出 设学校中某一门课程由多个教师讲授，他们使用相同的一套参考书，每个教员可以讲授多门课程,每种参考书可以供多门课程使用。考察关系模式： 关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B,多值依赖,用非规范化的关系示意如下,多值依赖,多值依赖,规范化的二维表格,分析Teaching(C,T,B): 找出Teaching的非平凡函数依赖 Teach具有唯一候选码(C，T，B)， 即全码 TeachingBCNF Teaching模式是否存在不良特性？ 数据冗余 插入异常 删除异常 更新异常,多值依赖,症由: 多值依赖: 给定的一对（X，Z）值有一组Y的值，这组值仅仅决定于X值而与Z值无关(Z = U-X-Y)。Y多值依赖于X。 考察(课程C,教员T)与(参考书B) 考察(课程C,参考书B)与(教员T),多值依赖,2. 定义: 定义6.15(描述型) 设R(U)是一个属性集U上的一个关系模式， X、 Y和Z是U的子集，并且ZUXY，多值依赖 XY成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。 例 Teaching（C, T, B）有 C T 和 C T,多值依赖,定义6.15(形式化) 在R（U）的任一关系r中，如果存在元组s，t 使得sX=tX，那么就必然存在元组 v，w r，（v，w可以与s，t相同），使得: vX = wX = sX = tX vY = tY, wY = sY vZ = sZ，wZ = tZ （即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。 这里，X，Y是U的子集，Z=U-X-Y。 或：r中若存在(x,y1,z1)和(x,y2,z2)，则必存在(x,y2,z1)和(x,y1,z2),多值依赖,例6.15 找出关系上所满足的多值依赖:,多值依赖,B C? 若使BC，需加入哪些元组？,AC AB CB CA 事实上AB, C B,加入后有没有破坏前述依赖关系？,3. 平凡多值依赖与非平凡多值依赖: 若XY，而Z，则称 XY为平凡的多值依赖 否则称XY为非平凡的多值依赖,多值依赖,4. MVD性质: 多值依赖具有对称性 若XY，则XZ，其中ZUXY,多值依赖,性质(续): 函数依赖是多值依赖的特例，即 若XY，则XY 多值依赖具有传递性 若XY，YZ， 则X(Z Y) 并规则:若XY，XZ，则X(Y Z) 交规则:若XY，XZ，则X(YZ) 差规则: 若XY，XZ，则X(Y-Z)，X(Z Y) 伪传递规则: XY，WYZ， 则WX(Z W-Y),多值依赖,5. 多值依赖与函数依赖的区别: 函数依赖规定某些元组不能出现在关系中 多值依赖要求某种形式的其它元组必须在关系中 有效性范围不同 X Y的有效性仅决定于X、Y属性集上的值 X Y不仅涉及属性组 X和 Y，而且涉及U中其余属性Z 若XY在R(U)上成立，则对于任何Y Y，均有XY 成立; 多值依赖XY若在R(U)上成立，不能断言对于任何Y Y有XY 成立 若XY在U上成立，则在W（X Y W U）上一定成立；反之则不然，即XY在W（W U）上成立，在U上并不一定成立(嵌入型MVD),多值依赖,多值依赖,AB在ABC上成立，而在ABCD上不成立,ABC 成立AB不成立,6. 不当MVD的关系式引起的弊端及对策: Teaching(C,T,B) T(C,T) B(C,B),多值依赖,1. 定义 定义6.16 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选码，则R4NF。 不允许有非平凡且非函数依赖的多值依赖 允许的是函数依赖（是非平凡多值依赖）,4NF,例6.16 关系模式: Teaching(C,T,B) 4NF 码为(C, T, B) 存在MVD：CT,且C不是候选码 分解成两个关系模式： T(C, T) 4NF (码:CT) B(C, B) 4NF (码:CB) CT， CB是平凡多值依赖,4NF,如果R 4NF， 则R BCNF 证 反证法。设R 4NF, 但R BCNF，但R中必存在某个非平凡FD : XY(当然更有X Y)，且X不含R的码。如果X Y=U，则X将成为码，与假设矛盾; 而如果X Y U，则Z=U-X-Y , 从而X Y是一个非平凡的多值依赖，加之X不含R的码，于是R 4NF, 这也与题设矛盾。,4NF,规范化小结,2NF,4NF,1NF,3NF,消除非主属性对码的部分函数依赖,消除非主属性对码的传递函数依赖,消除主属性对码的部分和传递函数依赖,消除非平凡的且非函数依赖的多值依赖,BCNF,6. 关系模式的规范化,思考,任何一个二目关系模式R（A，B）一定属于BCNF吗？一定属于4NF吗？ 关系模式R（A，B，C），ABC一定成立吗？ 一个全是主属性的关系模式一定可以达到第几范式？ 一个全码的关系模式一定可以达到第几范式？,第六章 关系数据理论,6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结,6.3 数据依赖的公理系统,逻辑蕴含 定义6.11 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立, （即r中任意两元组t，s，若t X=s X，则t Y=s Y），则称F逻辑蕴含X Y,1. Armstrong公理系统,关系模式R 来说有以下的推理规则： A1.自反律（Reflexivity）：若Y X U，则X Y为F所蕴含。 A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。,定理 6.1 Armstrong推理规则是正确的,（l）自反律: 若Y X U，则X Y为F所蕴含 证: 设Y X U 对R 的任一关系r中的任意两个元组t，s： 若tX=sX，由于Y X，有ty=sy， 所以XY成立，自反律得证,定理 6.l Armstrong推理规则是正确的（续）,(2)增广律: 若XY为F所蕴含，且Z U，则XZYZ 为F所蕴含。 证：设XY为F所蕴含，且Z U。 设R 的任一关系r中任意的两个元组t，s： 若tXZ=sXZ，则有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以 XZYZ为F所蕴含，增广律得证。,定理 6.l Armstrong推理规则是正确的（续）,(3) 传递律：若XY及YZ为F所蕴含，则 XZ为 F所蕴含。 证：设XY及YZ为F所蕴含。 对R 的任一关系 r中的任意两个元组 t，s： 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ为F所蕴含，传递 律得证。,2. 导出规则,1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由XY，XZ，有XYZ。 （A2， A3） 伪传递规则：由XY，WYZ，有XWZ。 （A2， A3） 分解规则：由XY及 ZY，有XZ。 （A1， A3）,导出规则,2.根据合并规则和分解规则，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要条件是XAi成立（i=l，2，k）,Armstrong公理系统,Armstrong公理系统是有效的、完备的 有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中； 完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来,3. 函数依赖闭包,定义6.l2 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。 定义6.13 设F为属性集U上的一组函数依赖，X U， XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包,F的闭包,F=XY, YZ F+= X, Y, Z, XY, XZ, YZ, XYZ, XX, YY, ZZ, XYX, XZX, YZY, XYZX, XY, Y Z, XYY, XZY, YZZ, XYZY, XZ, YYZ, XYZ, XZZ, YZYZ,XYZZ, XXY, XYXY,XZXY, XYZXY, XXZ, XYYZ,XZXZ, XYZYZ, XYZ, XYXZ,XZXY, XYZXZ, XZYZ, XYXYZ,XZXYZ, XYZXYZ F=XA1, , XAn的闭包F+计算是一个NP完全问题,关于闭包的引理,引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能 由F 根据Armstrong公理导出的充分必要条件是Y XF+ 用途 将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题,求闭包的算法,算法6.1 求属性集X（X U）关于U上的函数依赖集F 的闭包XF+ 输入：X，F 输出：XF+ 步骤： （1）令X（0）=X，i=0 （2）求B，这里B = A |( V)( W)(VWFV X（i）A W)； （3）X（i+1）=BX（i） （4）判断X（i+1）= X （i）吗? （5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。 （6）若否，则 i=i+l，返回第（2）步。,算法6.1,对于算法6.1， 令ai =|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就 会终止。,函数依赖闭包,例1 已知关系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 设X（0）=AB； (1) X（1）=ABCD=ABCD。 (2) X（0） X（1） X（2）=X（1）BE=ABCDE。 (3) X（2）=U，算法终止 （AB）F+ =ABCDE。,4. Armstrong公理系统的有效性与完备性,定理6.2 Armstrong公理系统是有效的、完备的 证明： 1. 有效性 可由定理6.1得证 2. 完备性 只需证明逆否命题: 若函数依赖XY不能由F从Armstrong公理导出，那么它必然不为F所蕴含,Armstrong公理系统完备性证明,(1) 引理: 若VW成立，且V XF+，则W XF+ (2) 构造一张二维表r，它由下列两个元组构成，可以证明r必是R（U，F）的一个关系，即F+中的全部函数依赖在 r上成立。 XF+ U-XF+ 111 000 111 111 (3) 若XY 不能由F从Armstrong公理导出，则Y 不是XF+ 的子集。,5. 函数依赖集等价,定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。 引理6.3 F+ = G+ 的充分必要条件是F G+ ，和G F+ 证: 必要性显然，只证充分性。 （1）若FG+ ，则XF+ XG+ 。 （2）任取XYF+ 则有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。 （3）同理可证G+ F+ ，所以F+ = G+。,6. 最小依赖集,定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与F-XA等价。 (3) F中不存在这样的函数依赖XA， X有真子集Z使得F-XAZA与F等价。,最小依赖集,例2 关系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno，Cno)Grade 设F=SnoSdept，SnoMname，SdeptMname， (Sno，Cno)Grade，(Sno，Sdept)Sdept F是最小覆盖，而F不是。 因为：F - SnoMname与F 等价 F - (Sno，Sdept)Sdept也与F 等价,7. 极小化过程,定理6.3 每一个函数依赖集F均等价于一个极小函数依赖 集Fm。此Fm称为F的最小依赖集。 证明: 构造性证明，找出F的一个最小依赖集。,极小化过程（续）,(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2， 则用 XAj |j=1，2， k 来取代XY。 (2)逐一检查F中各函数依赖FDi：XA，令G=F-XA， 若AXG+， 则从F中去掉此函数依赖。 (3)逐一取出F中各函数依赖FDi：XA，设X=B1B2Bm， 逐一考查Bi （i=l，2，m），若A （X-Bi ）F+ ， 则以X-Bi 取代X。,极小化过程（续）,例3 F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依赖集Fm不唯一 极小化过程( 定理6.3的证明 )也是检验F是否为极小依赖集的一个算法,第六章 关系数据理论,6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结,6.4.1 模式分解的定义 6.4.2 模式分解中的问题 6.4.3 无损连接分解 6.4.4 保持函数依赖的分解 6.4.5 关系模式的分解算法 6.4.6 关系模式的设计原则,6.4 模式的分解,定义6.16 设有关系模式R, 称用= R1，R2，Rn 代替R的过程为R模式的分解， 称为R的一个分解，这里Ui和Fi必须同时满足： U=U1U2Un Ui与Uj可以相交,但不允许Ui Uj或Uj Ui , ij, i,j=1,2,n Fi是F在Ui上的投影(也可记作Ri(F),6.4 模式的分解,定义6.17 函数依赖集合 XY | XY F+ XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影 设有R,U=A,B,C,D, F=AB,CD (R最高为几范式?) 1: R1(A,B,C), R2(C,D),F在R1,R2上的投影是什么? F1 = AB, F2=CD (R1最高为几范式?R2呢?),6.4 模式的分解,设有R,U=A,B,C, F=AB,BC (R最高为几范式?) 1: R1(A,B), R2(A,C),F在R1,R2上的投影是什么? F1 = AB, F2=AC (R1最高为几范式?R2呢?),6.4 模式的分解,SCD(Sno,Sname,Age,Dept,Mn,Cno,Score) F=sno*, DeptMn,(sno,cno)score 分解1=SD,SC: SD(Sno,Sname,Age,Dept,Mn), F1=sno*,deptMn SC(Sno,Cno,Score), F2=(sno,cno) score 分解2=S,D,SC: S (Sno,Sname,Age,Dept),F1=sno(sname,age,dept) D(Dept,Mn),F2=deptMn SC(Sno, Cno,Score),F3=(sno,cno) score,6.4 模式的分解,6.4.1 模式分解的定义 6.4.2 模式分解中的问题 6.4.3 无损连接分解 6.4.4 保持函数依赖的分解 6.4.5 关系模式的分解算法 6.4.6 关系模式的设计原则,6.4 模式的分解,把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义 无损连接性 保持函数依赖 既保持函数依赖，又无损连接,6.4 模式的分解,6.4 模式的分解,A B, B C,(A,B): (学生,学院) (A,C): (学生,院长),(A,C): (学生,院长) (B,C): (学院,院长),(A,B): (学生,学院) (B,C): (学院,院长),6.4 模式的分解,A C,B C,=,多出违背事实的元组 有损连接的分解,A B, B C,6.4 模式的分解,A B,A C,=,插入,违反 B C: 不保持FD的分解,A B, B C,6.4 模式的分解,A B,B C,=,无损连接，且保持FD,A B, B C,6.4.1 模式分解的定义 6.4.2 模式分解中的问题 6.4.3 无损连接分解 6.4.4 保持函数依赖的分解 6.4.5 关系模式的分解算法 6.4.6 关系模式的设计原则,6.4 模式的分解,定义6.18 关系模式R的一个分解 = R1，R2， ，Rn 若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Lossless join）。 具有无损连接性的分解保证不丢失信息 无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题,6.4 模式的分解,算法6.2 判别一个分解是否具有无损连接性 U= A1, A2, , An = R1 , R2, , Rk 1.建立一个n列k行的矩阵 TB = Cij | 若Aj Ui , Cij = aj , 否则Cij = bij,6.4 模式的分解,算法6.2(续) 2. 对F中每一个函数依赖XY，若TB中存在元组 t1，t2，使得t1X=t2X，t1Yt2Y，则对每一个Ai Y： 若t1Ai,t2Ai中有一个等于aj,则另一个也改为aj ； 若不成立,则取t1Ai = t2Ai (t2的行号小于t1)。 (即Ai列上，只要其中有一个aj则全改为aj,否则全改为行号最小的即一列的值),6.4 模式的分解,算法6.2(续) 3. 反复执行2, 直至： TB中出现一行为a1, a2 , , an 的一行。 TB不再发生变化, 且没有一行为a1, , an。 在情况下， 为无损分解，否则为有损分解。 定理5.4 为无损连接的分解当且仅当是算法5.2终止时,表中有一行为a1, , an。,6.4 模式的分解,例5 U=A,B,C,D,E, F=ABC, CD, DE, =(A, B, C), (C, D), (D, E)，判断分解是否具有无损连接性。,6.4 模式的分解,ABC,CD,DE,别解 U=A,B,C,D,E, F=ABC, CD, DE, =(A, B, C), (C, D), (D, E)，判断分解是否具有无损连接性。,ABC,CD,DE,6.4 模式的分解,例6 U=A,B,C,D,E, F=AC, BC, CD, DEC , CEA, =AD, AB, BE, CDE, AE, 判断分解是否无损连接。,AC,BC,CD,DEC,CEA,b13,b13,a1,a1,a3,a4,a4,a4,b13,b13,a3,无损连接,6.4 模式的分解,定理6.5 R的一个分解无损连接 = R1, R2 具有无损连接性的充要条件是： U1 U2 U1-U2 F+ 或 U1 U2 U2-U1 F+,6.4 模式的分解,证明 借助算法6.2,将R的属性分成三部分 ,(1) 充分性 如有U1 U2 U1-U2,则U2行(U1-U2)列全改为a,于是U2行全为a. 分解具有无损连接性; 同理, (2) 必要性 如是无损连接，则必有一行全a，,6.4 模式的分解,例7 R,U=A,B,C,F=A B的两个分解： (1) 1 = R1(A,B),R2(A,C) (2) 2 = R1(A,B),R2(B,C) 问两分解具有无损连接性吗? 解: (1) ABAC = A, AB-AC=B, A B F+ ,故分解 1具有无损连接性。 (2) ABBC = B, AB-BC=A, BC-AB=C. 无论B A，还是B C都不在F+ 中，所以分解 2不具有无损连接性。,6.4 模式的分解,例8 R,U=A,B,C,F=A B, C B 的分解： (1) 1 = AC,BC (2) 2 = AB,BC 问两分解具有无损连接性吗? 解: (1) ACBC =C, AC-BC=A, BC-AC=B,C B F+ ,故分解 1具有无损连接性。 (2) ABBC = B, AB-BC=A, BC-AB=C. 无论B A，还是B C都不在F+ 中，所以分解 2不具有无损连接性。,6.4 模式的分解,例9 R,U=A,B,C,D,E,F,F=A B, C F, E A, CED 的分解： = ABE,CDEF 问分解具有无损连接性吗? 解: ABECDEF =E, ABE-CDEF=AB, E AB F+ (为什么?). 故分解具有无损连接性。 思考：R的候选码是什么？它最高是几范式？分解后的两个关系模式又是几范式?,6.4 模式的分解,6.4.1 模式分解的定义 6.4.2 模式分解中的问题 6.4.3 无损连接分解 6.4.4 保持函数依赖的分解 6.4.5 关系模式的分解算法 6.4.6 关系模式的设计原则,6.4 模式的分解,定义6.19 关系模式R的一个= R1，R2， ，Rn 若 F 与 F1 F2 Fn等价 则称分解保持函数依赖。(Fi是F在Ui上的投影) 引理5.4 F+ = G+ F G+，G F+ 给出了判断分解是否保持函数依赖的算法。,6.4 模式的分解,例10 R,U=A,B,C,F=A B, C B 的分解： (1) 1 = AC,BC (2) 2 = AB,BC 问两个分解是否为保持函数依赖的分解? 解: (1) F1=, F2=C B ; F1 F2=C B , 显然与F=A B, C B 不等价。 分解不具保持函数依赖性。 (2) F1=A B, F2=C B ; F1 F2=A B ,C B = F. 分解是保持函数依赖的分解。,6.4 模式的分解,例11 R,U=A,B,C,D,E,F,F=A B, C F, E A, CED 的分解： = ABE,CDEF 问分解具有保持函数依赖性吗? 解: ABE(F)=E A, A B CDEF(F)=C F, CE D ABE(F) CDEF(F) = F 故分解具有保持函数依赖性。 前面已经发现分解是无损连接的。问:该分解是否理想?,6.4 模式的分解,6.4 模式的分解,A B,A C,=,插入,违反 B C: 不保持FD的分解,A B, B C,例12 R,U=A,B,C,F=A B, B C 的分解： = AB,AC 保持函数依赖吗? 解: F1=A B, F2=A C ; F1 F2=A B, A C , 与 F = A B, B C 并不等价。因为 (B C) (F1 F2) + ,但(B C) F + 。 所以，分解不具保持函数依赖性。,6.4 模式的分解,6.4.1 模式分解的定义 6.4.2 模式分解中的问题 6.4.3 无损连接分解 6.4.4 保持函数依赖的分解 6.4.5 关系模式的分解算法 6.4.6 关系模式的设计原则,6.4 模式的分解,分解算法,算法6.2 判别一个分解的无损连接性 算法6.3（合成法）转换为3NF的保持函数依赖的分解。 算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解 算法6.5 （分解法）转换为BCNF的无损连接分解 算法6.6 达到4NF的具有无损连接性的分解,模式分解的几个重要事实： 若仅要求分解具有无损连接性，则分解一定能达到4NF。 若仅要求分解保持FD，则分解一定能达到3NF，但不一定能达到BCNF。 若既要求分解具有无损连接性，又保持了FD，则分解一定能达到3NF，但不一定能达到BCNF。,6.4 模式的分解,算法6.3 达到3NF且保持函数依赖的分解算法。 输入: 给定关系模式R 输出: = R1, Rk, Ri 3NF, i = 1,2,k 步骤: 1. 求R的最小函数依赖集F; 2.若F中有XA ,且XA=U,则 = R,算法终止; 3.找出不在F中出现的属性，将它们构成一个关系模式，并从U中去掉它们(剩余属性仍记为U); 4.对于F中的每个XA ,构成一个关系模式XA.如果F中有XA1, XA2, ,XAn,则可以用XA1 A2 An代替n个模式XA1, XA2, XAn; 5.如发现某个Ui Uj,则应将Ui去掉。,6.4 模式的分解,例13 R,U=S#,D,M,C#,G,F=S# D,S# M,D M,(S#,C#) G. 试将R分解3NF,并保持函数依赖。(比较例5.25的无损连接分解) 解: (1)最小依赖集F =S# D,D M,(S#,C#) G (2)分解 R1(S#，D)， S#D R2(D，M)， DM R3(S#，C#，G)， (S#,C#)G 这个分解是无损连接的分解吗？,6.4 模式的分解,例14 R(C,T,H,R,S,G), 其中:C课程,T教师,H时间,R教室,S学生,G成绩. F： 1. CT(每门课仅一名教师上) 2. HRC(任一时间，一个教室只能上一门课) 3. HTR(一个时间，一个教师只能在一个教室上课) 4. CSG(一个学生，一门课只有一个成绩) 5. HSR(一个时间，一个学生只能在一个教室上课)