数据库系统原理DatabaseSystemPrinciples.ppt

数据库系统原理Database System Principles,四川大学计算机学院段 磊2011.9,第六章 关系数据库理论,意义 提供分析和判断数据库模式好坏的准则 指导设计好的数据库模式 难易度 本章是本书最难的部分之一 对于应用设计十分有用,2023/6/29,数据库系统概论-第6章,3/83,本章目录,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,2023/6/29,数据库系统概论-第6章,4/83,6.1 问题的提出什么是不好的数据库设计,我们目前为止掌握的知识尚无法解决大量的具体设计问题，即关系模式该如何选择。应用数据库应该由多少个表组成？每个表有哪些字段？本章从理论上解决关系数据库的逻辑设计问题。,2023/6/29,数据库系统概论-第6章,5/83,关系模式,一个关系模式应当是一个五元组。R（U,D,DOM,F）F是本章开始引入的数据依赖集。由于D和DOM对模式设计关系不大,因此我们在本章中把关系模式看作是一个三元组：R 当且仅当U上的一个关系r满足F时，r称为关系模式R的一个关系。关系，作为一张二维表，我们对它有一个最起码的要求：每一个分量必须是不可分的数据项。满足了这个条件的关系模式就属于第一范式（1NF）。,2023/6/29,数据库系统概论-第6章,6/83,数据依赖,我们的任务是研究模式设计，研究设计一个“好”的（没有“毛病”的）关系模式的办法。数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是现实世界属性间相互联系的抽象，是数据内在的性质,是语义的体现。现在人们已经提出了许多种类型的数据依赖，其中最重要的是函数依赖(Functional Dependency,FD)和多值依赖(Multivalued Dependency,MVD)。,2023/6/29,数据库系统概论-第6章,7/83,函数依赖,函数依赖极为普遍地存在例如，描述学生的关系，可以有学号(SNO)，姓名(SNAME)，系名(SDEPT)等几个属性。由于一个学号只对应一个学生，一个学生只在一个系学习。因而当“学号”值确定之后，姓名和该生所在系的值也就被唯一地确定了。上述值的确定就象数学函数：自变量x确定之后，相应的函数值f(x)也就唯一地确定。我们说SNO函数决定SNAME和SDEPT，或者说SNAME，SDEPT函数依赖于SNO，记为：SNOSNAME，SNOSDEPT。,2023/6/29,数据库系统概论-第6章,8/83,例：学生选课模型的关系模式,例如，前面介绍的学生选课模型，可以用一个关系模式表示：SC(Sno,Sname,Sage,Sgendar,Sdept,Cno,Cname,Grade)一个可能的关系为：S1 赵一 18 男 CS 1 C语言 80S1 赵一 18 男 CS 2 数据库原理 82S2 钱二 19 男 CS 1 C语言 80可以看出，该模式存在的主要问题是冗余。,2023/6/29,数据库系统概论-第6章,9/83,冗余带来的问题,冗余是不可避免的。在一定程度内也是合理的。但是，过度的冗余则会给数据库带来三类大的问题：插入异常（学生不选课，其基本信息就无法插入）删除异常（删除学生选课信息，其基本信息也被删除）修改复杂（修改某学生的基本信息，要随选课多次被修改）,2023/6/29,数据库系统概论-第6章,10/83,解决冗余的方法,解决的方法一个大关系分解为若干个小关系。感性经验：多用小关系，少用字段。如前面的SC大关系分解为第三章的 Student，SC和Course三个小关系，即可消除三类异常。,2023/6/29,数据库系统概论-第6章,11/83,问题的引出,为什么小关系比大关系好呢？现在我们要讨论的就是这个问题。从上面的分解观察到：如果在一个关系模式内，函数依赖形式上如果只有：码 非主属性 的形式，冗余就较小，三类异常就没有了。,2023/6/29,数据库系统概论-第6章,12/83,本章目录,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,2023/6/29,数据库系统概论-第6章,13/83,6.2 规范化,目的将具有不合适性质的关系转换为更合适的形式。要求掌握函数依赖的定义及判定；掌握1NF到BCNF的定义及判定；了解多值依赖，理解4NF的定义。,2023/6/29,数据库系统概论-第6章,14/83,6.2.1 函数依赖,(注意：现在还不能用到码的概念。)定义6.1 设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R的任何一个可能的关系r，r中不可能存在两个元组在X属性值上相等而在Y属性值上不等，则称X函数确定Y或Y函数依赖于X，记作：XY。,2023/6/29,数据库系统概论-第6章,15/83,6.2.1 函数依赖,XY，且YX，则称XY是非平凡的函数依赖。若不特别声明，我们总是讨论非平凡的函数依赖。XY，但YX 则称XY是平凡的函数依赖。理解为：整体一致，部分一致，没有特殊意义（过于“平凡”）。,2023/6/29,数据库系统概论-第6章,16/83,6.2.1 函数依赖,若XY，则X叫做决定因素(Determinant)。若XY，YX，则记作XY。在这种情况下，X和Y在R(U)中地位相同。若Y不函数依赖于X，则记作X Y。,2023/6/29,数据库系统概论-第6章,17/83,6.2.1 函数依赖,定义6.2(完全函数依赖和部分函数依赖的定义)在R(U)中如果XY，并且对X的任何一个真子集X，都有XY，则称Y对X完全函数依赖，记作:X Y若X Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：X Y,F,P,2023/6/29,数据库系统概论-第6章,18/83,6.2.1 函数依赖,定义6.3（传递函数依赖）在R(U)中，如果XY，(YX)，YX，YZ，则称Z对X传递函数依赖。记作：X Z,传递,2023/6/29,数据库系统概论-第6章,19/83,6.2.2 码,定义6.4 设K为R中的属性或属性组，若KU，则K为R的候选码(Candidate Key)。若候选码多于一个，则选定其中一个作为主码(Primary Key)。主属性(Prime attribute)：包含在任何候选码中的属性。非主属性(Nonprime attribute)：不包含在任何候选码中的属性。也称非码属性(Non-key attribute).,F,2023/6/29,数据库系统概论-第6章,20/83,6.2.2 码,定义6.5(外码的定义)关系模式R中的属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，简称外码。,2023/6/29,数据库系统概论-第6章,21/83,6.2.3 范式,满足最低要求的关系，叫第一范式，简称1NF。关系表的每一分量是不可分的数据项1NF 不允许表中出现嵌套或复合的属性 5NF 4NF BCNF 3NF 2NF 1NF,2023/6/29,数据库系统概论-第6章,22/83,6.2.4 2NF,定义6.6 若R1NF，对R的每一个非平凡的函数依赖XY，要么Y是主属性，要么X不是任何码的真子集，则R2NF。2NF 在 1NF基础上消除了非主属性对码的部分函数依赖。,2023/6/29,数据库系统概论-第6章,23/83,6.2.4 2NF,例：前面的大表SC不是2NF的关系模式。例4：关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)存在函数依赖Sno SdeptSdept Sloc(Sno,Cno)Grade唯一候选码(Sno,Cno)。则SnoSdept是非主属性对码的部分函数依赖。,2023/6/29,数据库系统概论-第6章,24/83,6.2.4 2NF,如果一个关系模式不是2NF的，一定存在过度冗余，带来3类异常。解决方法：分解为多个小表。如S-L-C分解为S-L(Sno,Sdept,Sloc),SC(Sno,Cno,Grade)2NF仅仅具有历史意义。,2023/6/29,数据库系统概论-第6章,25/83,6.2.5 3NF,定义6.7 若R 1NF，对R中的每一个非平凡的函数依赖XY，要么Y是主属性，要么X中含有码，则R 3NF。,2023/6/29,数据库系统概论-第6章,26/83,6.2.5 3NF,3NF与2NF相比，条件更强。因为X中含有码，则X不会是任何码的真子集；而2NF定义中，X不是任何码的真子集，还可能是非主属性组。即3NF在2NF的基础上消除了非主属性对码的传递函数依赖。,2023/6/29,数据库系统概论-第6章,27/83,6.2.5 3NF,判断3NF例子S-L(Sno,Sdept,Sloc)唯一候选码Sno函数依赖Sno Sdept,Sdept Sloc没有非主属性对码的部分函数依赖，满足2NF。存在非主属性对非主属性的函数依赖，不满足3NF。,非主属性,非主属性,2023/6/29,数据库系统概论-第6章,28/83,6.2.5 3NF,满足2NF，不满足3NF，仍有过度冗余及其带来的3类异常。,2023/6/29,数据库系统概论-第6章,29/83,6.2.5 3NF,解决方法，分解成小关系S-D(Sno,Sdept)D-L(Sdept,Sloc),2023/6/29,数据库系统概论-第6章,30/83,6.2.6 BCNF,由Boyce和Codd共同提出，属于修正的3NF。定义6.8 若R1NF，对R中的每一个非平凡的函数依赖XY，X中均含有码，则RBCNF。,2023/6/29,数据库系统概论-第6章,31/83,6.2.6 BCNF,BCNF与3NF相比，条件更强。不允许主属性对码的部分和传递函数依赖。到BCNF为止，完全消除了由于函数依赖带来的过度冗余及相应的三类异常。,2023/6/29,数据库系统概论-第6章,32/83,6.2.6 BCNF,例7(BCNF的例子)关系模式SPJ（学生，课程，名次）每个学生选每门课程有一定名次每门课程中每一名次只有一个学生,2023/6/29,数据库系统概论-第6章,33/83,6.2.6 BCNF,例7(BCNF的例子)关系模式SPJ（学生，课程，名次）每个学生选每门课程有一定名次每门课程中每一名次只有一个学生,(学生,课程)-名次,(课程,名次)-学生,2023/6/29,数据库系统概论-第6章,34/83,6.2.6 BCNF,例7(BCNF的例子)关系模式SPJ（学生，课程，名次）每个学生选每门课程有一定名次每门课程中每一名次只有一个学生,(学生,课程)-名次,(课程,名次)-学生,候选码,2023/6/29,数据库系统概论-第6章,35/83,6.2.6 BCNF,例8(是3NF，但不是BCNF的例子)关系模式STJ（学生，教师，课程）每一教师只教一门课一个学生选定某门课程，就对应一个固定的教师,2023/6/29,数据库系统概论-第6章,36/83,6.2.6 BCNF,例8(是3NF，但不是BCNF的例子)关系模式STJ（学生，教师，名次）每一教师只教一门课一个学生选定某门课程，就对应一个固定的教师,教师-课程,(学生,课程)-教师,2023/6/29,数据库系统概论-第6章,37/83,6.2.6 BCNF,例8(是3NF，但不是BCNF的例子)关系模式STJ（学生，教师，课程）每一教师只教一门课一个学生选定某门课程，就对应一个固定的教师,教师-课程,(学生,课程)-教师,候选码,教师,学生,2023/6/29,数据库系统概论-第6章,38/83,6.2.6 BCNF,例8存在的过度冗余,“每个教师上一门课”随选课学生的增加而被重复存储,2023/6/29,数据库系统概论-第6章,39/83,6.2.6 BCNF,解决方法还是分解分解为两个小关系模式(都是BCNF的)ST(学生,教师)TJ(教师,课程)或SJ(学生,课程)TJ(教师,课程),2023/6/29,数据库系统概论-第6章,40/83,6.2.6 BCNF,解决方法还是分解分解为两个小关系模式(都是BCNF的)ST(学生,教师)TJ(教师,课程)或SJ(学生,课程)TJ(教师,课程),两种分解都损失了：“一个学生选定某门课程，就对应一个固定的教师”语义,2023/6/29,数据库系统概论-第6章,41/83,6.2.6 BCNF,解决方法还是分解分解为两个小关系模式(都是BCNF的)ST(学生,教师)TJ(教师,课程)或SJ(学生,课程)TJ(教师,课程),两种分解都损失了：“一个学生选定某门课程，就对应一个固定的教师”语义,函数依赖“(学生,课程)-教师”在分解后没有保持！,2023/6/29,数据库系统概论-第6章,42/83,6.2.6 BCNF,事实上，关系模式即使到了BCNF，还可能存在由于非函数依赖带来的冗余及三类异常。这些数据依赖有多值依赖和连接依赖。我们只简单要求多值依赖。在多个实体间联系为1对多联系时可能出现多值依赖带来的问题。,2023/6/29,数据库系统概论-第6章,43/83,6.2.7 多值依赖,多值依赖定义：设有关系模式R(U)，X,Y,Z是U的非空子集。对于R的任一关系r，给定一对(x,z)值，就有一组Y的值与之对应，这组值仅仅决定于x值而与z值无关，则称“Y多值依赖于X”或“X多值决定Y”。记作XY。或记忆为：设有关系模式R(U)，X,Y,Z是U的非空子集。对R(U)的任一关系r，任意两元组s和t，如果sX=tX，则交换s和t的Y值所得两个新元组必在r中。,2023/6/29,数据库系统概论-第6章,44/83,6.2.7 多值依赖,翻译情况 A B C（姓名，东方语言，西方语言）王 红 日语 法语 王 红 汉语 英语 王 红 日语 英语 王 红 汉语 法语是BCNF,其中 只有ABC 才是关键字但有冗余,又有删除异常例如删除（王 红 汉语 法语）,2023/6/29,数据库系统概论-第6章,45/83,6.2.7 多值依赖,衣着（姓名，衣服，裤子）类似，可称为 完全搭配依赖（课程,教师,参考书）类似，看书上,2023/6/29,数据库系统概论-第6章,46/83,6.2.7 多值依赖,不是多值依赖的例子：学生选课表SC（Sno，Cno，G）中一个Sno（一个学生）有一组Cno（选了一组课程）和一组G（有一组成绩），但Cno与G有关（成绩与课程有关），所以没有SnoCno，以及SnoG。也就是说一个学生选的一组课程和一组成绩没有形成完全搭配。,2023/6/29,数据库系统概论-第6章,47/83,6.2.7 多值依赖,平凡的多值依赖：若XY，而Z=；则称X Y是平凡的多值依赖。多值依赖的性质：1、对称(互补)性：若X Y；则X Z，其中Z=U-X-Y。2、传递性：若X Y，Y Z；则X Z-Y。3、函数依赖是多值依赖的特殊情况：若X Y，则X Y。4、若X Y，X Z；则X YZ，X Z-Y，XY-Z，X YZ。,2023/6/29,数据库系统概论-第6章,48/83,6.2.8 4NF,定义6.10 若关系模式R（U，F）1NF，如果对于R的每个非平凡多值依赖X Y（Y不包含于X），X都含有码，则称R（U，F）4NF。实质上4NF消除了多值依赖。为什么？,2023/6/29,数据库系统概论-第6章,49/83,6.2.9 规范化小结,1NF：每个分量是不可分的数据项。2NF：非主属性完全函数依赖于码。3NF：非主属性既不部分依赖于码也不传递依赖于码。BCNF：所有属性都不部分依赖于码也不传递依赖于码。所有决定因素(属性集)都包含码。4NF：所有非平凡的多值依赖都是函数依赖。,2023/6/29,数据库系统概论-第6章,50/83,本章目录,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,2023/6/29,数据库系统概论-第6章,51/83,函数依赖公理系统的背景,为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，例如已知函数依赖集F，要问XY是否为F所蕴含，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。它是关系模式分解算法的理论基础。要求得给定关系模式的所有候选码对于关系模式的范式级别判定具有决定作用：范式级别的判定需要知道关系模式的所有候选码；有的范式级别还需确定主属性和非主属性，也需要知道所有候选码。,2023/6/29,数据库系统概论-第6章,52/83,数据依赖的公理系统,逻辑蕴含：定义6.11对于关系模式R，其任何一个关系r，若函数依赖XY都成立（即r中任意两元组s，t，若tX=sX，则tY=sY），则称函数依赖集F逻辑蕴含XY。,2023/6/29,数据库系统概论-第6章,53/83,Armstrong 公理系统,A1 自反律 若Y X U，则XY为F所蕴含(给出平凡的函数依赖)。A2 增广律 若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。A3 传递律 如XY及YZ为F 所蕴含，则XZ为F所蕴含。证明见定理6.1,2023/6/29,数据库系统概论-第6章,54/83,Armstrong 公理系统,Armstrong公理的推论：合并规则：若X Y，X Z，有X YZ。分解规则：由X Y及Z包含于Y，有X Z。伪传递规则：若X Y，WY Z，有XW Z。根据合并规则和分解规则，得到一个重要事实：X A1A2AK成立的充分必要条件是XAi(i=1,2,k)成立。,2023/6/29,数据库系统概论-第6章,55/83,Armstrong 公理系统,定义6.12 F的闭包：函数集闭包(找亲戚的亲戚)在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。Armstrong公理是有效的，完备的：有效性：由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中。有效性的证明书上定理6.1“Armstrong推理规则是正确的”可直接得证。完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。经典证明,2023/6/29,数据库系统概论-第6章,56/83,Armstrong 公理系统,定义6.13(属性集闭包)XF+的定义 设F是属性集U上的一组函数依赖集，X U，XF+A|XA能由F根据Armstrong公理导出。引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F根据Armstrong公理导出的充分必要条件是Y XF+,2023/6/29,数据库系统概论-第6章,57/83,算法6.1 求XF+的方法-非常重要,计算 XF+，滚雪球算法result:=X;/从X 开始while(changes to result)dofor each V W in F dobeginif V result then result:=result W endreturn result,2023/6/29,数据库系统概论-第6章,58/83,例,例1 关系模式R,U=A,B,C,D,E,F=ABC,BD,CE,ECB,ACB,求(AC)F+0.初始化 令resultAC1.第一次循环 计算result=ACEB=ABCE2.第二次循环 计算result=ABCDE即得结果。定义6.13，引理6.2和算法6.1非常重要，可用于求码。如KF+=U,而KF+!=U，即求得K为一候选码。,2023/6/29,数据库系统概论-第6章,59/83,求码方法要点(自己的总结),找出不出现在非平凡函数依赖右部的属性组X，它们一定包含于所有候选码。求XF+，判断U？成立结束，否则转3。(自底向上)扩展X的X，求XF+，判断U？直到所有情况找完为止。,2023/6/29,数据库系统概论-第6章,60/83,例,应用举例，对书上P184例1，求所有候选码要点：不出现在任何函数依赖右部的只有A；求AF+A；扩展AB，ABF+U；AC，ACF+U；AD，ADF+！U；（需再扩展）AE，AEF+！U；（需再扩展）再扩展ADE，ADEF+！U,2023/6/29,数据库系统概论-第6章,61/83,6.3 数据依赖的公理系统,要证明完备性首先解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。如果能求出这个集合就很容易判断，但是求这样的集合是一个NP完全问题。所以该判定转换为：任一个函数依赖X Y是F+中成员的充分必要条件是：Y XF+。证明完备性转换为证明它的逆否命题为真。即若函数依赖不能由F从Armstrong公理导出，那么它必然不为F所蕴含。证明分3步（略）证明用到了构造(特殊的二维表)、反证，十分巧妙。,2023/6/29,数据库系统概论-第6章,62/83,6.3 数据依赖的公理系统,完备性证明要证原命题，只需证明其逆否命题：若函数依赖XY不能由F出发从Armstrong公理导出，则它本身不为F所蕴含。（1）若VW成立，且V XF+，则W XF+。V XF+，则由引理6.2，有XV。由XV，VW，有XW。再由引理6.2，有W XF+。,2023/6/29,数据库系统概论-第6章,63/83,6.3 数据依赖的公理系统,（2）构造如下二维表r，r必是R的一个关系。用反证法。XF+U XF+11.1 00 0 11.1 11 1若r不是R的关系，必是由F中的函数依赖V W在r上不成立所致。观察r，V XF+，而W XF+。与（1）矛盾。,2023/6/29,数据库系统概论-第6章,64/83,6.3 数据依赖的公理系统,（3）若XY不能由Armstrong公理导出则Y不是XF+的子集，必有Y Y，且Y UXF+。（推）XY本身不为F所蕴含。（观察r）得证。,2023/6/29,数据库系统概论-第6章,65/83,6.3 数据依赖的公理系统,定义6.14 函数依赖集等价：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖或G是F的覆盖），或F与G等价。有相应的判定算法。引理6.3的充分性证明的过程实际上给出了判断两函数依赖集等价的方法。引理6.3 F+=G+的充分必要条件是 F G+，和G F+。,2023/6/29,数据库系统概论-第6章,66/83,6.3 数据依赖的公理系统,定义6.15 最小依赖集右部唯一无多余函数依赖无部分函数依赖定理6.3 每一个函数依赖集都等价于一个极小函数依赖集Fm(Fm一定存在，可能不唯一)。定理6.3的证明过程给出了检验(或构造)Fm的方法。,2023/6/29,数据库系统概论-第6章,67/83,求解极小函数依赖集的过程,用分解规则将F中每一函数依赖分解为若干个右部唯一的函数依赖，新函数依赖集仍命名为F。判断当前F中有没有多余的函数依赖。注意，检查XA，要在G集(其中G=F-XA)下考察XA是否被蕴含(G集下计算XG+，看A是否包含在其中)。处理后的函数依赖集不妨仍命名为F。判断当前F中每一函数依赖左部有没有多余的属性。注意，检查ABY中B是否多余时，令G=F-ABYAY,需要考察AY是否为F所蕴含(F集下计算XF+，看Y是否包含在其中)。最后得到F的函数依赖集Fm。,2023/6/29,数据库系统概论-第6章,68/83,6.3 数据依赖的公理系统,例子：设FABC，AB，求Fm。FmBC，AB?对不对？为什么？,2023/6/29,数据库系统概论-第6章,69/83,6.3 数据依赖的公理系统,上面的F与Fm根本不等价。FmAC，AB,2023/6/29,数据库系统概论-第6章,70/83,本章目录,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,2023/6/29,数据库系统概论-第6章,71/83,6.4 模式的分解,要求了解前面我们为了解决设计得不好(范式级别不够高)的数据库模式带来的问题，我们采用了大关系分解为小关系的方法来提高范式级别。本节给出分解的理论指导。,2023/6/29,数据库系统概论-第6章,72/83,6.4.1 模式分解的三个定义,具有无损连接性。分解后的(几个)小模式可自然连接恢复为原来的模式。保持函数依赖 分解前后函数依赖集等价既保持无损连接，又保持函数依赖。(理想情况),2023/6/29,数据库系统概论-第6章,73/83,6.4.2 分解的无损连接性和保持函数依赖性,m(r)R1(r)R2(r)Rk(r)定义5.18 R1，R2 Rk是R上的一个分解，若对于R的任一关系r，均有r m(r)成立，则具有无损连接性。此定义无法用于判断，无损连接性只能通过算法6.2或定理6.5来判断。,2023/6/29,数据库系统概论-第6章,74/83,6.4.2 分解的无损连接性和保持函数依赖性,算法6.2 要求会做。(通过例子来学习)例1 R(S，A，I，P)分解为R1(S，A)，R2(S，I，P)。F SA,SIPS A I P-a1 a2 b13 b14a1 b22 a3 a4由于有SA，使第二行第二列变成a2。S A I P-a1 a2 b13 b14a1 a2 a3 a4,2023/6/29,数据库系统概论-第6章,75/83,6.4.2 分解的无损连接性和保持函数依赖性,补充例 R(A，B，C，D，E)，分解R1=AD,R2=AB,R3=BE,R4=CDE,R5=AE F=AC,BC,CD,DEC,CEAA B C D E-a1 b12 b13 a4 b15a1 a2 b23 b24 b25b31 a2 b33 b34 a5b41 b42 a3 a4 a5a1 b52 b53 b54 a5AC(b23变b13，b53变b13),BC(b33变b13),CD(b24,b34,b54变a4),DEC(C列变a3)CEA(A列变a1)第三行出现了a1到a5.,2023/6/29,数据库系统概论-第6章,76/83,6.4.2 分解的无损连接性和保持函数依赖性,定理6.5 R的一个分解R1，R2具有无损连接性的充分必要条件是U1U2 U1U2F+或U1U2 U2U1 F+。可用于简单情况(分解为两个小关系模式)的快速判断。例如：RABC,F=AB,BCR1=AB,F1=AB,R2=AC,F2=ACU1U2 U1U2 即A B为F所蕴含。,2023/6/29,数据库系统概论-第6章,77/83,分解的无损连接性和保持函数依赖性,定义6.19(保持函数依赖的定义)若F(F1F2 Fk)+,则R的分解R1，R2 Rk保持函数依赖。注：实际上只需判断分解后是否有函数依赖的损失，只需判断F(F1F2 Fk)+,2023/6/29,数据库系统概论-第6章,78/83,6.4.3 模式分解算法,要记住的三个事实要求分解保持函数依赖，模式分解总可以达到3NF，不一定能达到BCNF。要求分解既保持函数依赖有具有无损连接性，可以达到3NF，不一定能达到BCNF。要求分解具有无损连接性，可以达到4NF。分解算法，要求掌握算法6.3(合成法)和6.4,2023/6/29,数据库系统概论-第6章,79/83,6.4.3 模式分解算法,算法6.3合成法要点函数依赖集极小化处理处理不出现在F中的属性对F按相同左部原则分组，每组的全部属性为一个分解后的关系模式。算法6.4 在 合成法基础上进行调整。1.增加R*(X，Fx)(构成码的属性)2.如果分解后的模式有属性包含的情况，只保留大的。,2023/6/29,数据库系统概论-第6章,80/83,作 业,一.设R，U=B,O,I,S,Q,D,F=SD,IB,ISQ,BO.1.求R的所有候选码。2.判断R满足的最高范式级别（到BCNF为止）。3.若R满足的最高范式级别不到3NF，试将其分解为一组既具有无损连接性，又保持函数依赖的3NF关系模式。二.P195,2,2023/6/29,数据库系统概论-第6章,81/83,作 业,三.分析设有以下关系R:,2023/6/29,数据库系统概论-第6章,82/83,作 业,试分析上述数据，并充分利用常识，完成以下要求：分析R的函数依赖，求R的候选码。求R的最高范式级别(到BCNF为止)，说明理由。分析R存在的主要问题。将R分解为一组合适的3NF关系模式。截止日期12月10日,2023/6/29,数据库系统概论-第6章,83/83,Any Question?,Thank you!,