数据库原理-5关系数据理论.ppt

数据库系统原理(第5章)第五章 关系数据理论意义：提供分析和判断数据库模式好坏的准则；指导设计好的数据库模式。地位：本章是本书最难的部分之一，但对于应用设计十分有用。5.1 问题的提出什么是不好的数据库设计我们目前为止掌握的知识尚无法解决大量的具体设计问题，即关系模式该如何选择。应用数据库应该由多少个表组成，每个表有哪些字段。本章即从理论上解决关系数据库的逻辑设计问题。一个关系模式应当是一个五元组。R（U,D,DOM,F）由于D和DOM对模式设计关系不大,因此我们在本章中把关系模式看作是一个三元组：RU,F 当且仅当U上的一个关系r满足F时,r称为关系模式RU,F的一个关系。关系,作为一张二维表,我们对它有一个最起码的要求：每一个分量必须是不可分的数据项。满足了这个条件的关系模式就属于第一范式（1NF）。我们的任务是研究模式设计，研究设计一个“好”的（没有“毛病”的）关系模式的办法。数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是现实世界属性间相互联系的抽象,是数据内在的性质,是语义的体现。现在人们已经提出了许多种类型的数据依赖,其中最重要的是函数依赖(Functional Dependency简记为FD)和多值依赖(Multivalued Dependency简记为MVD)。函数依赖极为普遍地存在n例如，描述学生的关系,可以有学号(SNO),姓名(SNAME),系名(SDEPT)等几个属性。n由于一个学号只对应一个学生,一个学生只在一个系学习。因而当“学号”值确定之后,姓名和该生所在系的值也就被唯一地确定了。n上述值的确定就象数学函数：自变量x确定之后,相应的函数值f(x)也就唯一地确定。n我们说SNO函数决定SNAME和SDEPT,或者说SNAME，SDEPT函数依赖于SNO,记为SNOSNAME,SNOSDEPT。例如，前面介绍的学生选课模型，可以用一个关系模式表示：SC(Sno,Sname,Sage,Sgendar,Sdept,Cno,Cname,Grade)一个可能的关系为：95001 赵一 18 男 CS 1 C语言 8095001 赵一 18 男 CS 2 数据库原理 8292002 钱二 19 男 CS 1 C语言 80可以看出，该模式存在的主要问题是冗余。冗余是不可避免的。在一定程度内也是合理的。但是，过度的冗余则会给数据库带来三类大的问题：插入异常（学生不选课，其基本信息就无法插入）删除异常（删除学生选课信息，其基本信息也被删除）修改复杂（修改某学生的基本信息，要随选课多次被修改）解决的方法n一个大关系分解为若干个小关系。n如前面的SC大关系分解为第三章的 Student，SC和Course三个小关系，即可消除三类异常。为什么小关系比大关系好呢？现在我们要讨论的就是这个问题。从上面的分解观察到：如果在一个关系模式内，函数依赖形式上如果只有：码 非主属性 的形式，冗余就较小，三类异常就没有了。5.2 规范化目的n将具有不合适性质的关系转换为更合适的形式。要求n掌握函数依赖的定义及判定；n掌握1NF到BCNF的定义及判定；n了解多值依赖，理解4NF的定义。5.2.1 函数依赖(注意：现在还不能用到码的概念。)定义5.1 设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R的任何一个可能的关系r，r中不可能存在两个元组在X属性值上相等而在Y属性值上不等，则称X函数确定Y或Y函数依赖于X，记作 XY.XY，且YX，则称XY是非平凡的函数依赖。若不特别声明,我们总是讨论非平凡的函数依赖。XY，但YX 则称XY是平凡的函数依赖。n全部一致，部分一致，没有太大意义。若XY,则X叫做决定因素(Determinant)。若XY，YX，则记作XY。n在这种情况下，X和Y在R(U)中地位相同。若Y不函数依赖于X,则记作X Y。定义5.3(完全函数依赖和部分函数依赖的定义)在R(U)中，如果XY，并且对X的任何一个真子集X，都有XY，则称Y对X完全函数依赖，记作:X Y定义5.4（传递函数依赖）在R(U)中，如果XY，(YX)，YX，YZ，则称Z对X传递函数依赖。5.2.2 码定义5.4 设K为R中的属性或属性组，若KU，则K为R的候选码。若候选码多于一个，则选定其中一个作为主码。主属性：包含在任何候选码中的属性。非主属性：不包含在任何候选码中的属性。定义5.5 (外码的定义)关系模式R中的属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，简称外码。5.2.3 范式满足最低要求的关系，叫第一范式，简称1NF。n关系表的每一分量是不可分的数据项n1NF 不允许表中出现嵌套或复合的属性 5NF 4NF BCNF 3NF 2NF 1NF 定义5.6 若R1NF，对R的每一个非平凡的函数依赖XY，要么X是主属性，要么X不是任何码的真子集，则R 2NF。2NF 在 1NF基础上消除了非主属性对码的部分函数依赖。5.2.4 2NF例：前面的大表SC不是2NF的关系模式。如果一个关系模式不是2NF的，一定存在过度冗余，带来3类异常。解决方法：分解为多个小表。5.2.5 3NF定义5.7 若R 1NF，对R中的每一个非平凡的函数依赖XY，要么Y是主属性，要么X中含有码，则R 3NF。3NF与2NF相比，条件更强。n因为X中含有码，则X不会是任何码的真子集；n而2NF定义中，X不是任何码的真子集，还可能是非主属性组。即3NF在2NF的基础上消除了非主属性对码的传递函数依赖。5.2.6 BCNF由Boyce和Codd共同提出，属于修正的3NF。定义5.8 若R1NF，对R中的每一个非平凡的函数依赖XY，X中均含有码，则R BCNF。BCNF与3NF相比，条件更强。n不允许主属性对码的部分和传递函数依赖。从3NF到BCNF也是通过分解得到的。到BCNF为止，完全消除了由于函数依赖带来的过度冗余及相应的三类异常。但事实上，关系模式还可能存在由于非函数依赖带来的冗余及三类异常。这些数据依赖有多值依赖和连接依赖。我们只简单要求多值依赖。n在多个实体间联系为1对多联系时可能出现多值依赖带来的问题。5.2.7 多值依赖多值依赖定义多值依赖定义：设有关系模式R(U)，X,Y,Z是U的子集，且Z=U-X-Y。对于R的任一关系r,给定一对(x,z)值，就有一组Y的值与之对应，这组值仅仅决定于x值而与z值无关，则称“Y多值依赖于X”或“X多值决定Y”。记作XY。或记忆为：对R(U)的任一关系r，任意两元组s和t，如果sX=tX，则交换s和t的Y值所得两个新元组必在r中。翻译情况 A B C （姓名，东方语言，西方语言）王 红 日语 法语 王 红 汉语 英语 王 红 日语 英语 王 红 汉语 法语是BCNF,其中 只有ABC 才是关键字，没有违反 法则但有冗余,又有删除异常，例如删除（王 红 汉语 法语）衣着（姓名，衣服，裤子）类似，可称为 完全搭配依赖（课程,教师,参考书）类似，看书上不是多值依赖的例子：n学生选课表SC（Sno，Cno，G）中一个Sno（一个学生）有一组Cno（选了一组课程）和一组G（有一组成绩），但Cno与G有关（成绩与课程有关），所以没有SnoCno，以及SnoG。平凡的多值依赖：平凡的多值依赖：若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，X Y-Z，X YZ。多值依赖与函数依赖的区别1、多值依赖的有效性与属性集的范围有关。若XY在U上成立，则在W（XY W U）上一定成立；反之则不然，即X Y在W（W包含于U）上成立，在U上并不一定成立。这是因为多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。但是在关系模式R（U）中，函数依赖X Y的有效性仅决定于X，Y这两个属性集的值。只要在R的任何一个关系r中，元组在X和Y上的值满足函数依赖的定义，则该函数依赖在任何属性集W（U的子集）上成立。2、子集有效性不同：若函数依赖X Y在R（U）上成立，则对于任何Y属于Y，都有X Y成立。而多值依赖X Y在R（U）上成立，却不能断言对于任何Y属于Y，有X Y成立。5.2.8 4NF定义5.10 若关系模式R（U，F）1NF，如果对于R的每个非平凡多值依赖X Y（Y不包含于X），X都含有码，则称R（U，F）4NF。实质上4NF消除了多值依赖。为什么？一个关系模式到了BCNF可能还有不合适的性质nWSC（仓库、管理员、物品）中，仓库的管理员与物品无关，存放的物品也与管理员无关；n每一管理员随物品增加而重复被存储，类似地，每一物品也随管理员增加而重复被存储，存在过度冗余；n三类异常同样存在。可以通过分解方法将其分解为一组4NF 的关系模式nWSC分解为WS和WC两个关系模式即可使之达到4NF，解决上述问题5.2.9 规范化小结1NF：每个分量是不可分的数据项。2NF：非主属性完全函数依赖于码。3NF：非主属性即不部分依赖于码也不传递依赖于码。BCNF：所有属性都不部分依赖于码也不传递依赖于码。所有决定因素(属性集)都包含码。4NF：所有非平凡的多值依赖都是函数依赖。5.3 数据依赖的公理系统逻辑蕴含逻辑蕴含：定义定义5.11对于关系模式R，其任何一个关系r，若函数依赖X Y都成立（即r中任意两元组s，t，若tX=sX，则tY=sY），则称函数依赖集函数依赖集F逻辑蕴含逻辑蕴含XY。为了求得给定关系模式的码，为了从一组函数依赖求得蕴为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖含的函数依赖，例如已知函数依赖集F，要问XY是否为F所蕴含，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。它是关系模式分解算法的理论基础。要求得给定关系模式的所有候选码对于关系模式的范式级别判定具有决定作用：n范式级别的判定需要知道关系模式的所有候选码；n有的范式级别还需确定主属性和非主属性，也需要知道所有候选码。Armstrong 公理系统A1 自反律 若Y X U，则X Y为F所蕴含(给出平凡的函数依赖)。A2 增广律 若X Y为F所蕴含，且Z U，则XZ YZ为F所蕴含。A3 传递律 如X Y及Y Z为F 所蕴含，则X Z为F所蕴含。Armstrong公理的推论：n合并规则：若X Y，X Z，有X YZ。n分解规则：由X Y及Z包含于Y，有X Z。n伪传递规则：若X Y，WY Z，有XW Z。根据合并规则和分解规则，得到一个重要事实：X A1A2AK成立的充分必要条件是X Ai成立（i=1,2,k)。F的闭包：在关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。Armstrong公理是有效的，完备的：有效性：由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中。有效性的证明书上定理5.1“Armstrong推理规则是正确的”可直接得证。完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。经典证明定义5.13 XF+的定义 设F是属性集U上的一组函数依赖集，X U，XF+A|XA能由F根据Armstrong公理导出。引理5.2 设F为属性集U上的一组函数依赖，X，Y U，XY能否由F根据Armstrong公理导出的充分必要条件是Y XF+算法5.1 求XF+的方法。非常重要。例1.P185增加要求 求(AC)F+令X(0)AC计算X(1)=ACEB=ABCE计算X(2)ABCDE即得结果。定义5.13,引理5.2和算法5.1非常重要，可用于求码。如KF+=U,而KF+！=U，即求得K为一候选码。求码方法要点(自己的总结)1.找出不出现在非平凡函数依赖右部的属性组X，它们一定包含于所有候选码。2.求XF+，判断U？成立结束，否则转3。3.(自底向上)扩展X的X，求XF+，判断U？直到所有情况找完为止。应用举例，对书上P185例1，求所有候选码要点：n不出现在任何函数依赖右部的只有A；n求AF+A；n扩展wAB，ABF+U；wAC，ACF+U；wAD，ADF+！U；（需再扩展）wAE，AEF+！U；（需再扩展）w再扩展nADE，ADEF+！U要证明它首先解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。如果能求出这个集合就很容易判断，但是求这样的集合是一个NP完全问题。所以该判定转换为：任一个函数依赖X Y是F+中成员的充分必要条件是：Y XF+。证明完备性转换为证明它的逆否命题为真。即若函数依赖不能有F从Armstrong公理导出，那么它必然不为F所蕴含。证明分3步（略）证明用到了构造(特殊的二维表)、反证，十分巧妙。完备性证明。n要证原命题，只需证明其逆否命题：若函数依赖XY不能由F出发从Armstrong公理导出，则它本身不为F所蕴含。n（1）若VW成立，且V XF+，则W XF+。wV XF+，则由引理5.2，有XV。w由XV，VW，有X W。w再由引理5.2，有W XF+。n（2）构造如下二维表r，r必是R的一个关系。用反证法。XF+U XF+11.1 00 0 11.1 11 1w若r不是R的关系，必是由F中的函数依赖VW在r上不成立所致。w观察r，V XF+，而W XF+。w与（1）矛盾。n（3）若XY不能由Armstrong公理导出w则Y不是XF+的子集，必有Y Y，且Y UXF+。（推）w XY本身不为F所蕴含。（观察r）w得证。定义5.14 函数依赖集等价：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖或G是F的覆盖），或F与G等价。有相应的判定算法。引理5.3的充分性证明的过程实际上给出了判断两函数依赖集等价的方法。引理5.3 F+=G+的充分必要条件是 F G+，和G F+。定义定义5.15 最小依赖集最小依赖集n右部唯一右部唯一n无多余函数依赖无多余函数依赖n无部分函数依赖无部分函数依赖定理定理5.3 每一个函数依赖集都等价于一个极小函数依赖集Fm(Fm一定存在，可能不唯一。)定理5.3的证明过程给出了检验(或构造)Fm的方法。例子：设FABC，AB,求Fm。FmBC，AB?对不对？为什么？上面的F与Fm根本不等价。FmAC，AB5.4 模式的分解要求了解前面我们为了解决设计得不好(范式级别不够高)的数据库模式带来的问题，我们采用了大关系分解为小关系的方法来提高范式级别。本节给出分解的理论指导。5.4.1 模式分解的三个定义1.具有无损连接性。分解后的(几个)小模式可自然连接恢复位原来的模式。2.保持函数依赖 分解前后函数依赖集等价3.既保持无损连接，又保持连接依赖。(理想情况)5.4.2 分解的无损连接性和保持函数依赖性m(r)R1(r)R2(r)Rk(r)定义5.18 R1，R2 Rk是R上的一个分解，若对于R的任一关系r，均有r m(r)成立，则具有无损连接性。此定义无法用于判断，无损连接性只能通过算法5.2来判断。算法5.2 要求会做。(通过例子来学习)例1 R(S，A，I，P)分解为R1(S，A)，R2(S，I，P)。FSA,SIPS A I P-a1 a2 b13 b14a1 b22 a3 a4由于有SA，使第二行第二列变成a2。S A I P-a1 a2 b13 b14a1 a2 a3 a4补充例 R(A，B，C，D，E)，分解R1=AD,R2=AB,R3=BE,R4=CDE,R5=AE F=AC,BC,CD,DEC,CE AA 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)CE A(A列变a1)第三行出现了a1到a5.定理定理5.5 R的一个分解R1，R2具有无损连接性的充分必要条件是U1U2U1U2F+或U1U2U2U1 F+。可用于简单情况(分解为两个小关系模式)的快速判断。例如：RABC,F=AB,B CR1=AB,F1=AB,R2=AC,F2=ACU1U2U1U2 即AB为F所蕴含。定义定义5.19(保持函数依赖的定义)若F(F1F2 Fk)+,则R的分解R1，R2 Rk保持函数依赖。注：实际上只需判断分解后是否有函数依赖的损失，只需判断F(F1F2 Fk)+5.4.3 模式分解算法要记住的三个事实1.要求分解保持函数依赖，模式分离总可以达到3NF，不一定能达到BCNF。2.要求分解既保持函数依赖有具有无损连接性，可以达到3NF，不一定能达到BCNF。3.要求分解具有无损连接性，可以达到4NF。分解算法，要求掌握算法5.3(合成法)和5.4。合成法要点1.函数依赖集极小化处理2.处理不出现在F中的属性3.对F按相同左部原则分组，每组的全部属性为一个分解后的关系模式。算法5.4 在 合成法基础上进行调整。1.增加R*(X，Fx)(构成码的属性)2.如果分解后的模式有属性包含的情况，只保留大的。作业一.设 R，U=B,O,I,S,Q,D,F=S-D,I-B,IS-Q,B-O.1.求R的所有候选码。2.判断R满足的最高范式级别（到BCNF为止）。3.若R满足的最高范式级别不到3NF，试将其分解为一组既具有无损连接性，又保持函数依赖的3NF关系模式。二.P196,2三.分析。设由以下关系R:工厂名产品号产品名车间名车间地点单价W1P1M1J1D1100W2 P1 M1J1D2110W2P2M2 J1D280W2P3M3J2D375W3 P1M1J1D490 试分析上述数据，并充分利用常识，完成以下要求：1 分析R的函数依赖，求R的候选码。2 求R的最高范式级别（到BCNF为止），说明理由。3 分析R存在的主要问题。4 将R分解为一组合适的3NF关系模式。