关系数据库理论

1、第6章 关系数据理论,意义： 提供分析和判断数据库模式好坏的准则； 指导设计好的数据库设计。 地位： 本章是本书最难的部分之一，但对于应用设计十分有用。,6.1 问题的提出 什么是不好的数据库设计 目前为止掌握的知识尚无法解决大量的具体设计问题，即关系模式该如何选择。应用数据库应该由多少个表组成，每个表有哪些字段。 本章即从理论上解决关系数据库的逻辑设计问题。,一个关系模式应当是一个五元组。 R(U, D, DOM, F) 关系模式简化为一个三元组：RU,F 当且仅当U上的一个关系r满足F时,r称为关系模式RU,F的一个关系。 关系,作为一张二维表, 它有一个最起码的要求：每一个分量必须是不可

2、分的数据项。满足了这个条件的关系模式就属于第一范式（1NF）。,关系的定义,数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是现实世界属性间相互联系的抽象,是数据内在的性质,是语义的体现。最重要的是函数依赖(Functional Dependency简记为FD)和多值依赖(Multivalued Dependency简记为MVD)。,函数依赖,函数依赖: 例如，描述学生的关系,可以有学号(SNO),姓名(SNAME),系名(SDEPT)等几个属性。 由于一个学号只对应一个学生,一个学生只在一个系学习。因而当“学号”值确定之后,姓名和该生所在系的值也就被唯一地确定了。 上

3、述值的确定就象数学函数：自变量x确定之后,相应的函数值f(x)也就唯一地确定。 所以说SNO函数决定SNAME和SDEPT,或者说SNAME，SDEPT函数依赖于SNO,记为SNOSNAME,SNOSDEPT。,例如:前面介绍的学生选课模型，可以用一个关系模式表示： SC(Sno,Sname,Sage,SSEX,Sdept,Cno,Cname,Grade) 一个可能的关系为： 95001 赵一 18 男 CS 1 C语言 80 95001 赵一 18 男 CS 2 数据库原理 82 92002 钱二 19 男 CS 1 C语言 80 可以看出，该模式存在的主要问题是冗余。,冗余是不可避免的。在

4、一定程度内也是合理的。但是，过度的冗余则会给数据库带来三类大的问题： 插入异常(学生不选课，其基本信息就无法插入） 删除异常(删除学生选课信息，其基本信息也被删除） 修改复杂(修改某学生的基本信息，要随选课多次被修改）,解决的方法 一个大关系分解为若干个小关系。 如前面的SC大关系分解为第三章的 Student，SC和Course三个小关系，即可消除三类异常。,为什么小关系比大关系好呢？现在我们要讨论的就是这个问题。 从上面的分解观察到：如果在一个关系模式内，函数依赖形式上如果只有： 码 非主属性 的形式，冗余就较小，三类异常就没有了。,6.1.1 规范化,目的 将具有不合适性质的关系转换为更

5、合适的形式。 要求 掌握函数依赖的定义及判定； 掌握1NF到BCNF的定义及判定； 了解多值依赖，理解4NF的定义。,6.1.2 函数依赖,定义6.1 设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R的任何一个可能的关系r，r中不可能存在两个元组在X属性值上相等而在Y属性值上不等，则称X函数确定Y或Y函数依赖于X，记作 XY。,XY，且YX，则称XY是非平凡的函数依赖。若不特别声明,我们总是讨论非平凡的函数依赖。 XY，但YX 则称XY是平凡的函数依赖。,若XY,则X叫做决定因素(Determinant)。 若XY，YX，则记作XY。 在这种情况下，X和Y在R(U)中地位相同。 若

6、Y不函数依赖于X,则记作X Y。,定义6.3 (完全函数依赖和部分函数依赖的定义) 在R(U)中，如果XY，并且对X的任何一个真子集X，都有XY，则称Y对X完全函数依赖，记作: X Y 定义4.4（传递函数依赖） 在R(U)中，如果XY，(YX)，YX，YZ，则称Z对X传递函数依赖。,F,6.1.3 码 定义6.4 设K为R中的属性或属性组，若KU，则K为R的候选码。若候选码多于一个，则选定其中一个作为主码。 主属性：包含在任何候选码中的属性。 非主属性：不包含在任何候选码中的属性。 全码:整个属性组都是码,6.2.1 范式(NORMAL FORM),满足最低要求的关系，叫第一范式，简称1NF

7、。 关系表的每一分量是不可分的数据项 1NF 不允许表中出现嵌套或复合的属性 5NF 4NF BCNF 3NF 2NF 1NF,定义6.6 若R1NF，对R的每一个非平凡的函数依赖XY，要么Y是主属性，要么X不是任何码的真子集，则R 2NF。 2NF 在 1NF基础上消除了非主属性对码的部分函数依赖(P175)(单主属性的关系一定是2NF,)。,6.2.2 2NF,如果一个关系模式不是2NF的，一定存在过度冗余，带来3类异常。 解决方法：分解为多个小表。,6.2.3 3NF,定义6.7 若R 1NF，对R中的每一个非平凡的函数依赖XY，要么Y是主属性，要么X中含有码，则R 3NF。,3NF与2

8、NF相比，条件更强。 因为X中含有码，则X不会是任何码的真子集； 反之，X不是任何码的真子集，还可能是非主属性组。 即3NF在2NF的基础上消除了非主属性对码的传递函数依赖。,1)关系 R(U,F) 2)数据依赖对关系模式的影响:数据冗余度大;更新异常;插入异常;删除异常. 3)函数依赖:XY,XY 4)平凡函数依赖与非平凡函数依赖. 5)完全函数依赖与部分函数依赖.X-Y,X-Y 6)传递函数依赖XY，(YX)，YX，YZ 7)码,候选码,主码,主属性,非主属性. 8) 5NF 4NF BCNF 3NF 2NF 1NF,F,P,1)1NF:每个属性都是不可分割属性. 2)2NF:不存在非主属

9、性对主属性的部分函数依赖. 3)3NF:不存在非主属性对主属性的传递函数依赖. 4)1NF2NF-3NF.,分解,分解,6.2.6 BCNF,由Boyce和Codd共同提出，属于修正的3NF。 定义6.8 若R1NF，对R中的每一个非平凡的函数依赖XY，X中均含有码，则R BCNF。即起决定因素都是含码.,BCNF与3NF相比，条件更强。 1)所有非主属性都完全函数依赖于每个候选码. 2)所有主属性都完全函数依赖于每个不包含它的候选码. 3)没有任何属性完全函数依赖于非码的任何一组属性. 从3NF到BCNF也是通过分解得到的。 到BCNF为止，完全消除由于函数依赖带来的过度冗余及相应的三类异常

10、。,1.关系C(CNO,CNAME,PCNO)属于第几范式?码是CNO 2.S(SNO,SNAME,SDEPT,SAGE),假如SNAME具有唯一性.码是SNO或SNAME 3.SPJ(S,J,P)S表示学生,J表示课程,P表示名次.侯选码(S,J)或(P,J).,总 结,候选码(其属性为主属性),不包含候选码中的属性为非主属性,若候选码多于一个,选其中一个为主码. 1NF:关系中的每个属性只包含原子项. 2NF:在1NF上,每个非主属性都完全依赖于候选码. 3NF:在2NF上,每个非主属性都非传递依赖于候选码. BCNF:F中的每一个依赖的决定因素必定包含R的某个候选码.不允许主属性对码的部

11、分和传递函数依赖.(任何2元关系必定是BCNF),1NF,2NF,3NF,BCNF,独立的数据项,消除了非主属性对码的部分函数依赖,消除了非主属性对码的传递函数依赖,(X-Y,X 含有主码),例1:假设关系模式R(A,B)属性3NF,下列说法中()是正确的? A.它一定消除了插入和删除异常 B.仍存在一定的插入和删除异常 C.一定属于BCNF .D.A和C都是 例2.关系模型中的关系模式至少是() .A.1NF B.2NF C.3NF 4.BCNF 例3:在关系DB中,任何二元关系模式的最高范式必定是( ) A.1NF, B.2NF C.3NF D.BCNF 例4:当B属性函数依赖于A属性时,

12、属性A与B的联系是( ) A.1对多 B.多对1 C.多对多 D.以上都不是 例5.在关系模式中,如果属性A和B存在1对1的联系,则说( ). A.A-B B.B-A C.CB D.以上都不是 例6:侯选码中的属性称为( ) A.非主属性 B.主属性 C.复合属性 D.关键属性.,例7:关系模式中各级范式之间的关系为 ( ). A)3NF 2NF 1NF B)3NF 1NF 2NF C)1NF 2NF 3NF D)2NF 1NF 3NF,例8:关系模式中,满足2NF的模式( ) A.可能是1NF B.必定是1NF C.必定是3NF D.必定是BCNF 例9:关系模式R中的属性全部是主属性, 则

13、R的最高范式必定是( ) A.2NF B.3NF C.4NF D.BCNF,例9:消除了部分函数依赖的1NF的关系模式必定是( ) A.1NF B.2NF C.3NF D .4NF 例10:关系模式的侯选吗可以是( ),主码有( ) A.0个 B.1个 C.1个或多个 D.多个 例11.侯选码中的属性可以有( ) A.0个 B.1个 C.1个或多个 D.多个 例13.根据关系数据库规范化理论,关系数据库中的关系要满足 1NF,下面”部门”关系中,因哪个属性而使它不满足1NF. 部门(部门号,部门名,部门成员,部门总经理) A.部门总经理 B.部门成员 C.部门名 D.部门号,例14.如下所显示

14、的关系R( ) A.不是3NF B.是3NF但不是BCNF .C.是3NF但不是2NF D.是BCNF,例15.在关系模式R(A,B,C,D)中,有函数依赖集 F=B-C,C-D,D-A,则R能达到( ) A.1NF B.2NF C.3NF D.以上三者都不行,6.2.7规范化小结 1NF：每个分量是不可分的数据项。 2NF：非主属性完全函数依赖于码。 3NF：非主属性即不部分依赖于码也不传递依赖于码。 BCNF：所有属性都不部分依赖于码也不传递依赖于码。所有决定因素(属性集)都包含码。,函数依赖与属性关系,1)如果X和Y之间是1:1关系,则存在函数依赖:X-Y,Y-X 2)如果X和Y之间是m

15、:1关系,则存在函数依赖:X-Y. 3)如果X和Y之间是m:n关系,则不存在函数依赖.,6.3 数据依赖的公理系统,逻辑蕴含： 定义4.11对于关系模式R，其任何一个关系r，若函数依赖X Y都成立（即r中任意两元组s，t，若tX=sX，则tY=sY），则称函数依赖集F逻辑蕴含XY。,为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，例如已知函数依赖集F，要问XY是否为F所蕴含，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。它是关系模式分解算法的理论基础。,Armstrong 公理系统 A1 自反律 :若Y X U，则X Y为F所蕴含(给出平凡的函数

16、依赖)。 A2 增广律: 若X Y为F所蕴含，且Z U，则XZ YZ为F所蕴含。 A3 传递律: 如X Y及Y Z为F 所蕴含，则X Z为F所蕴含。,Armstrong公理的推论： 合并规则：若X Y，X Z，有X YZ。 分解规则：由X Y及Z包含于Y，有X Z。 伪传递规则：若X Y，WY Z，有XW Z。 根据合并规则和分解规则，得到一个重要事实： X A1A2AK成立的充分必要条件是X Ai成立（i=1,2,k)。,F的闭包： 在关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F + 。 Armstrong公理是有效的，完备的： 有效性：由F出发根据Armstro

17、ng公理推导出来的每个函数依赖一定在F +中 。 完备性： F + 中的每一个函数依赖，必定可以由F出发根据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 + 算法4.1 求XF +的方法。 非常重要。 要求会求X F +,例:设关系模式R(U,F),其中U=A,B,C,D,E,I,F=A-D,AB-E,BI-E,CD-I,E-C.计算(AE)+ 解:令X

18、=AE,X(0)=AE. 在F中找出左边是AE子集的函数依赖:A-D,E-C. X(1)=X(0)DC=ACDE.此时X(1)!=X(0). 在F中找出ACDE子集的函数依赖:CD-I. X(2)=X(1)I=ACDEI,此时X(2)!=X(1).但F中未用过的函数依赖的左边已没有X(2)的子集了,所以结束. (AE)+=ACDEI 定义6.13,引理4.2和算法4.1非常重要，可用于求码。 如KF +=U, 而KF + ！=U，即求得K为一候选码。,求码方法要点(自己的总结) 找出不出现在非平凡函数依赖右部的属性组X，它们一定包含于所有候选码。 求XF +，判断U？成立结束，否则转3。 (自

19、底向上)扩展X的X，求XF +，判断U？直到所有情况找完为止。,例:设有关系R,其中U=A,B,C,D,E,P; F=A-B,C-P,E-A,CE-D 求R的所有侯选码. 解:根据侯选码的定义,如果X-U,不存在X-U,其中X X,则X是R的侯选码.C,E在所有函数依赖的右部都未出现,所以C,E必定是侯选码中的成员.又因为(CE)+=ABCDEP,所以CE-U,R只有唯一的侯选码CE. 例:设有关系模式R(C,T,S,N,G),其函数依赖为F=C-T,CS-G,S-N 求R的所有侯选码.,例:设有关系模式R(B,C,M,T,A,G),有函数依赖F=B-C,(M,T)-B,(M,C)-T,(M,

20、A)-T,(A,B)-G 求侯选码,属于第几范式? 侯选码为AM, 属于3NF,不属于BCNF.,例:设有关系模式R(A,B,C,D,E),其上的函数依赖:F=A-BC,CD-E,B-D,E-A 求1)B+ 2)R的所有侯选码. 1)B+=BD 2)分别为:A,BC,CD,E.,定义6.15 最小依赖集：若每一个函数依赖集都等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。(Fm一定存在，可能不唯一。),最小依赖集F,1)F的每个依赖的右部都是单个属性 2)对于F中的任何一个函数X-A,F-(X-A)与F都不等价(保证不存在多余的函数依赖) 3)对于F中的任何一个X-A和X的真子集Z,(

21、F-(X-A) UZ-A与F都不等价.(保证F的每个函数以来的左边没有多余的属性).,求最小依赖集的算法,1)应用分解规则,使F中每一个依赖的右部属性单一化; 2)去掉各依赖左边多余的属性.一个一个去掉F左边是非单属性的依赖,如XY-A,要看Y是否多余的,如果X+包含A,则Y是多余的. 3)去掉多余的依赖.从第一个依赖开始,从F中去掉它(如X-Y),然后在剩下的依赖中求X+看X+是否包含Y,如果包含,则可以去掉X-Y. 这样依次下去.,例:设有关系模式R,其中:U=A,B,C,D,E,G; F=AB-C,C-A,BC-D,ACD-B,D-EG,BE-C,CG-BD,CE-AG 求最小依赖集.

22、1)将依赖右边单一化 F=AB-C,C-A,BC-D,ACD-B,D-E,D-G,BE-C,CG-B,CG-D,CE-A,CE-G 2)去掉F中左部多余的属性.CE-A,由于有C-A,则E是多余的;对于ACD-B,由于CD+=ABCDEG,则A是多余的.结果为: F=AB-C,C-A,BC-D,ACD-B,D-E,D-G,BE-C,CG-B,CG-D,CE-A,CE-G,3)在F中去掉多余的依赖,对于CG-B,由于CG+=ABCDEG,则CG-B是多余的. 则F= =AB-C,C-A,BC-D,ACD-B,D-E,D-G,BE-C,CG-B,CG-D,CE-A,CE-G,6.4 模式的分解,要

23、求了解 前面我们为了解决设计得不好(范式级别不够高)的数据库模式带来的问题，我们采用了大关系分解为小关系的方法来提高范式级别。本节给出分解的理论指导。 4.4.1 模式分解的三个定义 1. 具有无损连接性。分解后的(几个)小模式可自然连接恢复位原来的模式。,2. 保持函数依赖 分解前后函数依赖集等价 3. 既保持无损连接，又保持连接依赖。(理想情况) 6.4.2 分解的无损连接性和保持函数依赖性 m(r)R1(r) R2(r) Rk(r) 定义5.18 R1，R2 Rk是R上的一个分解，若对于R的任一关系r，均有r m(r)成立，则具有无损连接性。 此定义无法用于判断，无损连接性只能通过算法来判断。,算法6.2 :(通过例子来学习) 例1 R(S，A，I，P) 分解为R1(S，A)， R2(S，I，P)。FSA,SIP S A I P - a1 a2 b13 b14 a1 b22 a3 a4 由于有SA，使第二行第二列变成a2。 S A I P - a1 a2 b13 b14 a1 a2 a3 a4,补