关系数据库部分理论.ppt

《关系数据库部分理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库部分理论.ppt（67页珍藏版）》请在三一办公上搜索。

1、主要内容：在数据库设计中，如何把现实世界表示成数据库模式(构成关系数据库的所有关系模式的集合构成了关系数据库模式），是数据库设计中一个极其重要而又基本的问题。它涉及到一系列的理论，关系模型有较为严格的数学基础，以关系模型作为讨论对象，形成了一整套的关系数据库理论。关系数据库设计理论是指导产生一个具有确定的、好的数据库模式的理论体系。,第六章 关系数据理论,6.1 问题的提出,2插入异常BORROWER的主KEY：NO，TNO关键字值非空。（新调入未借书的人）,NO NAME ADDR TNO TLTLE AU DATE001 张 平 A1 T1 DB AU1 D1 001 张 平 A1 T2

2、OS AU2 D2 001 张 平 A1 T3 MA AU3 D3 001 张 平 A1 T4 DB1 AU4 D3 008 李少林 A2 T3 MA AU3 D4 008 李少林 A2 T7 MA2 AU7 D7,数据库模式一BORROWER（NO,NAME，ADDR，TNO,TITLE，AU,DATE),1、有冗余：对于借书人，每借一次书他本人信息和书的信息都要存放一次。存在数据冗余，这样当修改某些数据项（如地址时，则每一个元组中的地址都要改变。增加更新代价，更严重的是潜在的不一致性。),存在的问题：,3删除异常如把借的书全部还掉，则就把这个人连同他的地址都删掉了,丢失了借书人的基本信息。

3、,数据库模式二 BORROWER（NO,NAME，ADDR)BOOKS(TNO,TITLE,AU)LOAN(NO，TNO，DATE）,由于将借书人、书、及借书分离成不同的关系，使数据冗余大大减少，且不存在插入异常和删除异常。存在另一问题：如使用上述模式时，为找到借MA的借书人名，则需进行三个关系的连接操作，代价高。如何找到一个好的数据库模式，这正是数据库设计理论所研究的问题。主要包括三个方面的内容：数据依赖、范式、数据库模式设计方法，其中数据依赖起核心作用。,原因：,不仅客观事物彼此互相联系、互相制约。客观事物本身的各个属性之间也互相联系、互相依赖。如一个人的住址依赖于他的姓名。属性之间的这种

4、依赖关系表达了一定的语义信息。在设计数据库时，对于事物之间的联系和事物属性之间的联系，都要考虑。例上例中，借书人的属性都依赖于NO，但与书,借书的属性没有联系。把本来无关的借书人信息和书信息，借书信息拼在一起，就出现了刚才的数据冗余和异常现象。所以我们在设计关系数据库模式时，必须从语义上摸清这些数据依赖，合理构成数据库模式。,数据依赖是通一个关系中属性间值的相等与否体现出来的数据间的相互联系。它是现实世界属性间相互联系的抽象，是数据内在性质，是语义的体现。一般有三种依赖：函数依赖（FD）、多值依赖（MVD）、连接依赖。,设R（U）是属性集U上的关系模式。X和Y是U的子集。若对于R（U）的任意一

5、个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，则称X函数决定Y或Y函数依赖于X，记为,一、定义,6.2 函数依赖,理解：如果R的两个元组在属性X：上一致，（即两个元组在这些属性相对应的各个分量具有相同的值），则它们在另一个属性B上也应该一致，则记为。如一组属性函数决定多个属性。如 则可以把这一组依赖关系简记为,注：函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。只要有一个具体关系R不满足定义中的条件，就破坏了函数依赖。,设R（U）是属性集U上的关系模式。X和Y是U的子集。R是R的任一具体关系，U,V是r中的任意两个元

6、组。如果由UX=VX能导致UY=VY,则称X函数决定Y或Y函数依赖于X，记为，其中UX表示元组U在X上的属性值。VX，UY，VY有类似的意义。设R（U）是属性集U上的关系模式。X和Y是U的子集。如果R的所有关系r都存在着：对于X的每一个具体值，都有Y唯一的具体值与之对应，则称X函数决定Y，或Y函数依赖于X。这两个定义等价。,可断言如下三个函数依赖：,即如两个元组在title，year分量上具有相同的值，则它们在length，filmType 和studioName上必然也相同。,title，year starName,设有属性集X、Y，及关系模式R。如果X、Y之间是“1-1”关系，则存在函数依

7、赖：且 如学号，姓名（唯一）。如果X、Y之间是“m-1”关系，则存在函数依赖：如学号（唯 一），宿舍。(一个宿舍信多个学生）如果X、Y之间是“m-m”关系，则X、Y之间不存在函数依赖。如借阅关系：学号，书号。也即设计者确定函数依赖时，可以从分析属性间的关系着手。,二、函数依赖与属性关系,2、完全函数依赖在R（U）中，如果，并且对于X的任何一个真子集，都有 Y，则称Y对X完全函数依赖：记作。,3、部分函数依赖若，但Y不完全函数依赖于X，则称Y对X部分函数依赖，,存在：书号 出版社，出版社 地址，出版社 书号故有地址对书号的传递函数依赖。,4、传递函数依赖在R（U）中，如果，Y X，则称Z对X传递

8、函数依赖。,如Books（书号，出版社名，出版社地址）一种书对应唯一书号，并只能为某一个出版社出版，一个 出版社一般只有一个名称和唯一地址。一个出版社可出版多种书。,Title,year lengthTitle length,定义：对于任给的关系R，U为其所含全部的属性集合 X 为U的子集。若有完全函数依赖 则,四、关键字（码）,作为候选关键字的属性集X唯一标识R中的元组，但该属性 集的任何真子集不能唯一标识R中的元组。,一个关系中可能存在多个候选关键字。选其一作为主关键字。,候选关键字中所含的属性称为主属性，不包含在任何候选关键字中的属性称为非主属性。,如 为 的关键字。它们函数决定所有其它

9、属性 均不是键码。如STUDENT(学号，姓名，性别，班级)，如姓名不重名，则学号，姓名均为键码,最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码。如关系模式S（SNO，SDEPT，SAGE）SNO是码 关系模式SC（SNO，CNO，G）（SNO，CNO）是码 关系模式R（P，W，A），P：演奏者，W：作品，A：听众。码为（P，W，A）,X为R的一个候选关键字。,闭包：在关系模式R中F所逻辑蕴涵的函数依赖的全体叫做F的闭包。记为。一般情况下，如 则称F是函数依赖的完备集。,对于给定的一组函数依赖，我们如何判断另外一些函数依赖是否成立？如对于关系模式R有 是否成立？定义：设F是

10、关系模式R的一个函数依赖集,X、Y是R的属性子集，如果从F中的函数依赖能够推出X Y，则称F逻辑蕴涵 或称 是F的逻辑蕴涵。,五、函数依赖的逻辑蕴涵,例：若有关系模式R（X,Y,Z),它的函数依赖集F=则F的闭包为,假设我们已知某关系所满足的函数依赖集，在不知道关系的具体元组的情况下，通常可推断出该关系必然满足的其他某些函数依赖。为此，要求有一套推理规则。Armstrong公理（推理规则中最主要、最基本的作为公理）Armstrong公理系统：设U为属性集总体，F是U上的一组函数依赖集，于是有关系模式R。对R来说有以下的推理规则：A1 自反律：若 为F所蕴涵。A2 增广律：若 为F所蕴涵，且，则

11、 为F所蕴涵。A3 传递律：若 为F所蕴涵，则 为F所蕴涵。,6.3 函数依赖公理一、Armstrong公理,注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。,定理6.1 Armstrong推理规则是正确的。证明：设u、v是r的任意两个元组，r是R的任一关系。若uX=vX,则在u和v中的X的任何子集也必相符。由条件Y是X的子集.必有uY=vY.根据函数依赖定义可知：:设u、v、r含义同上。若uXZ=vXZ，则uXuZ=vXvZ，也即uX=vX，uZ=vZ由条件，得如uX=vX则uY=vY uY=vY，uZ=vZ，即 uYuZ=vYvZ，也即uYZ=vYZ根据函数定义

12、可知：。：设u、v、r含义同上，设uX=vX uY=vY又 uZ=vZ,合并规则：若 则。分解规则：若，则，。伪传递规则：若，则。证明：则（增广性）（增广性）（传递性）（反射性）（传递性）同理（增广性）又（传递性）从合并和分解规则可得出一个重要结论：引理6.1 如果 是关系模式R的属性，则 成立的充要条件是 均成立。,二、公理的推论,从Armstrong公理推理规则可得如下推论：,Armstrong公理是有效的、完备的。有效性指：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在 中。正确性指：只要使F中的函数依赖为真，则用公理推出的函数依赖也为真。完备性指：中的每一个函数依赖，

13、必定可以由F出发根据Armstrong公理推导出来。即 中的所有函数依赖都能用Armstrong公理推导出来。幻灯片 18,公理的正确性保证推出的所有函数依赖都为真，公理的完备性保证可以推出所有的函数依赖。,定义：设F为属性集U上的一组函数依赖，F是U上一个函数依赖集，则称所有用公理从F推出的函数依赖 中Ai的属性集合为X的属性闭包 称为属性集X关于函数依赖集F的闭包。计算 的一个目的就是要确定某一函数依赖 是否由F逻辑蕴涵。即它是否成立，而通过计算 我们就能判断这一结论的真假。等价所有由F逻辑蕴涵的 属性A的集合。,三、属性闭包,引理6.2 设F为属性集U上的一组函数依赖，能由F根据Arms

14、trong公理导出的充分必要条件是。,算法6.1：求属性集X关于U上的函数依赖集F的属性闭包。输入：关系模式R的全部属性集U及上的函数依赖F，U的子集X输出：。方法：计算。1、2、求B，B=A|(V)(W)(V W F);3、4、判断 吗？5、若相等或，则 就是，算法终止。6、若否，则i=i+1,返回第2步。,于是，判定X Y是否能由F根据Armstrong公理推出的问题，就转化为求出,停止计算的几种判别方法：当发现 包含了所有属性时。在F中的函数依赖的右边属性中再也找不到 中未出现过的属性。在F中未用过的函数依赖的左边属性已没有 的子集。,=ABCDE（DE）,例：一具有属性A、B、C、D、

15、E、F的关系，假设该关系有如下函数依赖：AB C，BC AD，D E和CFB。左边不包含在中。求解：设X=AB，则有=AB,C=ABC（AB C）,=ABCAD=ABCD（BCAD）,在F中未用过的函数依赖的左边属性已没有Xi的子集。(或计算X(4)-ABCDE,=（ABCDE）,例：检验ABD是否蕴涵于F中。DA呢？解：计算 及。=ABCDE ABD蕴涵于F中。也即ABD成立。=DE DA不蕴涵于F中。也即DA不成立。,证明完备性的逆否命题，即如函数依赖X Y不能由F从Armstrong公理导出，那么它必然不为F所蕴涵，证明分三步。,定理6.2 Armstrong公理系统是有效的、完备的。,

16、若V W成立，且，则,证 因为，所以有X V成立；于是X W成立所以。,2.构造一张二维表r,它由下列两个元组组成,可以证明r必是R的一个关系，即F中的全部函数依赖在r上成立。,1111 1111,1111 0000,如r不是R的关系,则必由于F中有函数依赖V W在r上不成立所致。由r的构成可知，V必定是 的子集，而W不是 的子集，可是由第（1）步，矛盾。所以r必是R的一个关系。(即证明r满足F),若X Y不能由F从Armstrong公理导出,则Y不是 的子集,而因此在关系r的两个元组中X的属性值一致，而Y的属性值不一致,则X Y在r中不成立,即X Y必不为R所蕴含。,Armstrong公理的

17、有效性和完备性说明了“导出”和“蕴含”是两个完全等价的概念.于是 也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。,引理6.3 的充要条件是 和。证 必要性显然，只证充分性。若，则。任取，则有。所以，即。3.同理可证,所以,从蕴含（或导出）的概念出发，又引出了两个函数依赖集等价和最小依赖集的概念,定义6.14 设F和G是两个依赖集，如果,就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖),或F与G等价。,检查F中的每个函数依赖是否属于。,F和G是否等价：,如对于，看是否。是则 检查所有其它依赖，若全都满足，则。对G中每一个依赖也作同样处理。如 且。则F和G等价。幻灯片

18、50,例：,1.检查F中的每个函数依赖是否属于,取,求=ABCD,则同理可得出 2.检查G中的每个函数依赖是否属于F+取,同理可得出,所以F与G等价,引理：每一个函数依赖集F都可以由一个右部只有单个属性的函数依赖集G新覆盖。(G左部与F相同)证明：设F中的函数依赖由两部分组成：右边是1个以上的属性的函数依赖。设XY为其中任一个，Y=A1Ak,Ai为单属性。右边是单属性的函数依赖。设VW为其中任一个。令G由所有的VW及X Ai(i=1k)组成。对G中任一X Ai,，由于F中有XY。根据分解规则有X Ai(i=1.k),而 VW，在F和G中都有。所以而对于F中任一XY，在G中有XAi,根据合成规则

19、有XY。,函数依赖的最小集。定义6.15 如果函数依赖集F满足下列条件,则称为F为一个极小 函数依赖集。亦称为最小依赖集或最小覆盖。F中的每个依赖的右部都是单个属性。依赖右部为单属性。对于F的任一函数依赖XA来说，F与 都不等价，保证F中不存在多余的依赖。对于F的任一函数依赖XA来说，F与 都不 等价，其中Z为X的任一真子集，保证每个依赖的左边没有多余的属性。,例2 关系模式S,其中U=SNO,SDEPT,MN,CNAME,G F=SNO SDEPT,SDEPT MN,(SNO,CNAME)GF=SNO SDEPT,SDEPT MN,(SNO,CNAME)G,SNO MN,(SNO,SDEPT

20、)SDEPT根据定义可以验证F是最小覆盖,而F不是。,定理5.3：每个函数依赖集F均等价于一个最小函数依赖集。此 称为F的最 小依赖集。,定理6.3：每个函数依赖集F均等价于一个最小函数依赖集。此 称为F的最小依赖集。,证 这是一个构造性的证明，分三步对F进行“极小化处理”，找出F的一个最小依赖集。,逐一查找F中各函数依赖FDi：X Y，若Y=,则用 来取代X Y。(Y A1A2A3 Y A1)逐一查找F中各函数依赖FDi：X A，令，若 则 从F中去掉此函数依赖。逐一取出F中各函数依赖FDi：X A，设X=，逐一考查Bi(I=1,2,m)，若，则以X-Bi取代X。,最后剩下的F就一定是极小依

21、赖集，并且与原来的F等价。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价。,应当指出，F的最小依赖集 不一定是唯一的，它与对各函数依赖Fdi及X A中X各属性的处置顺序有关。例3 F=A B，B A，B C，A C，C A Fm1=A B,B C,C A Fm2=A B，B A，A C，C A Fm1与Fm2均为最小依赖集。,例：求。解：按最小依赖集的定义分别考虑三个条件：用分解规则将所有依赖变为右边是单属性的依赖。去掉F中的多余依赖，具体做法：从第一个依赖开始，从F中去掉它（假设为 XY）然后在剩下的依赖中求，看是否包含Y，若是则去掉XY：否则 不能去掉，依次做下去。A B=A

22、C 不能去掉 BA=CAB 去掉 BC=B 不能去掉 AC=ABC 去掉 C A=C 不能去掉 BE D=BEAC 不能去掉 判断XYA中X是否成为多余属性，只要在F中求 若包含A，则Y是多余属性。否则Y不是多余属性。依次判断其它属性即可消除各依赖左边的多余属性。去掉各依赖左边多余的属性,应当指出，F的最小依赖集 不一定是唯一的，它与对各函数依赖Fdi及X A中X各属性的处置顺序有关。,B+=BCA 不含D，E不多余E+=E，不含D，B不多余,注 F的最小依赖集不一定唯一。它和我们对各函数依赖的处置顺序有关。,两个关系模式R1，R2，如果F 与G等价，那么R1的关系一定是R2的关系。反过来，R

23、2的关系也一定是R1的关系。所以在R1 中用与F等价的依赖集G来取代F是允许的。,B+=BCA 不含D，E不多余E+=E，不含D，B不多余,6.4 关系模式的规范化,一、范式,规范化：一个低一级范式的关系模式，通过模式分解可转换为若干个高一级范式的关系模式的集合。这种过程就叫规范化。是以结构更单纯，更规则的关系逐步取代原有关系的过程。,关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式，满足最低要求的叫第一范式，简称1NF，在1NF中满足进一步一些要求的2NF，。,所谓“第几范式”，是表示关系的某一种级别。即符合某一种级别的关系模式的集合，R为第几范式就可以写成。,5NF 4N

24、F BCNF 3NF 2NF 1NF1NF：每一个分量必须是不可分的数据项。这是最基本的规范化。,5NF,4NF,BCNF,3NF,2NF,1NF,各种范式之间的关系,二、第一范式（1NF）定义：如果一个关系模式R的每个具体关系r的每个属性值都是不可再分的最小数据单位，则R为第一范式。简称1NF，r为1NF关系。,注：第一范式不含重复组，不存在嵌套结构。不满足1NF的关系为非规范关系。,正经理 副经理,借书人 所借书名 日期,T1 D1张平 T2 D2 T3 D3 T2 D2 T4 D4,李问,三、第二范式（2NF）,定义6.6 任给关系R，若R为INF，且每一个非主属性都完全函数依赖于码，则

25、R为2NF。,关系模式 SLC(SNO,SDEPT,SLOC,CNO,G)码:(SNO,CNO),(SNO,CNO)F G SNO SDEPT,(SNO,CNO)P SDEPT SNO SLOC,(SNO,CNO)P SLOC SDEPT SLOC(每个系的学生只住一个地方),函数依赖:,SNO SDEPT,CNO SLOC,G,非主属性:SDEPT,SLOC 部分函数依赖于码。所以 SLC为1NF,在SLC中，仍存在插入、删除异常，修改复杂等问题。解决办法是用投影分解把关系SLC分解为两个关系模式：SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）非主属性对码都是完全函数依赖了,

26、一个关系模式R不属于2NF,会产生以下几个问题,1.插入异常 若新来一个学生,该学生还未选课,即无CNO,这样的元组就不能插入SLC中。则该学生的SNO，SDEPT，SLOC信息无法插入。,2 删除异常 假定某个学生只选一门课，如S4就选了一门课C3。现在这门课他也不选了，那么C3这个数据项就要删除。而C3是主属性，删除了C3，整个元组就必须跟着删除，使得S4的其他信息也被删除了，造成删除异常，不应删的信息也被删除了。,3 修改复杂。如某个学生从数学系转到计算机系，不仅要修改SDEPT分量，还必须修改SLOC分量。另外，如果这个学生选修了多门课，SDEPT，SLOC重复存储多次，不仅存储冗余度

27、大，而且必须修个多个元组中全部SDEPT，SLOC信息，选成修改的复杂化。,原因：存在非主属性对码的不完全函数依赖。SDEPT，SLOC对码不是完全函数依赖。,四、第三范式,定义：如果关系模式R满足为2NF，且其每一个非主属性都不 传递函数依赖于任何码（候选关键字）。则R为第三范式。,一个关系模式R若不是3NF，就会产生与非2NF相类似的问题。,SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）,SNO,CNO,G,SNO,SDEPT,SLOC,SC中的函数依赖,SL中的函数依赖,SC没有传递函数依赖 SL中存在传递函数依赖,SNO SDEPT，（SDEPT SNO），SDEPT

28、SLOC可得SNO SLOC为传递函数依赖。所以，SL为2NF,一般来说，3NF的关系大多数都能解决插入和删除操作异常的问题，数据冗余也能得到有效的控制。,解决办法是将SL分解为：SD（SNO，SDEPT）分解后不再存在传递依赖 DL（SDEPT，SLOC）,SL（SNO，SDEPT，SLOC）存在问题：1.数据冗余如果一个系有500个学生，则地址就要重复500次。,2。插入异常如果成立了一个新系，分配了在5号楼，而该系还未开始招生，则不能插入SDEPT，SLOC。,五、BCNF,定义：任给关系R，X、Y为其属性集。F为其函数依赖集，且F中所有函赖XY（Y不属于X）中的X必包含码（候选关键字）

29、，则R为BCNF。即R中每一函数依赖的决定因素都包含一候选KEY。,由BCNF的定义可以得到结论，一个满足BCNF的关系模式有：所有非主属性对每一个码都是完全函数依赖。所有的主属性对每一个不包含它的码，也是完全函数依赖。没有任何属性完全函数依赖于非码的任何一组属性。,由于，按定义排除了任何属性对码的传递依赖与部分依赖，所以。但是若，则R未必属于BCNF。,如对于关系模式S（SNO，SNAME，SDEPT，SAGE）码：SNO，SNAME两个。SDEPT，SAGE不存在对码的部分依赖与传递依赖，所以。同时S中除SNO，SNAME外没有其他决定因素，所以S也属于BCNF。,假定没有重名情况非主属性

30、：SDEPT，SAGE主属性：SNO，SNAME,关系模式SPJ（S，J，P）S：学生，J：课程，P：名次。每个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生。由语义可得到如下的函数依赖：（S，J）P；（J，P）S 候选码：（S，J）（J，P）所有属性均为主属性，不存在非主属性对主属性的部分依赖和传递依赖，所以。而且除（S，J）和（J，P）以外没有其他决定因素，所以。,关系模式STJ（S，T，J）S：学生，T：教师，J：课程。每一教师只教一门课，每门课有若干教师，某一学生选定某门课，就对应一固定的教师。由语义可得：（S，J）T；（S，T）J；T J（S，J），（S，T）均为

31、码STJ是3NF，但STJ不是BCNF。因为T是决定因素，却不包含码。,非BCNF的关系模式也可以通过分解成为BCNF。例如STJ可分解为 ST（S，T）；TJ（T，J）它们均为BCNF。3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除异常。3NF的不彻底性表现在可能存在主属性对码的部分依赖和传递依赖。,六、多值依赖,例1 某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可讲授多门课程，每种参考书可供多门课程使用。用一个非规范化的关系来表示教员T，课程C和参

32、考书B之间的关系。,课程C,教员T,参考书B,物理 李勇 普通物理学,王军 光学原理,物理习题集,数学 李勇 数学分析,张平 微分方程,高等代数,计算数学 张平 数学分析,周峰,物理习题集,关系模型TEACHING（C，T，B）码：（C，T，B）问题：当某一课程增加一名讲课教员，必须插入多个元组。某一门课要去掉一本参考书，则必须删除多个元组。,对数据的增、删、改很不方便，数据的冗余也十分明显。,物理 李勇 物理习题集,定义6.9 设R(U)是属性集U上的一个关系模式。X、Y、Z是U的子集，并且Z=U-X-Y。关系模式R(U)中多值依赖X Y成立，当且仅当对R(U)的任一关系r，给定的一对（x,

33、z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。在R(U)的任一关系r中，如果存在元组t,s使得tX=sX，那么就必然存在元组w,v r(w,v可以与s,t相同），使得wX=vX=tX,而wY=tY,wZ=sZ,vY=sY,vZ=tZ（即交换s,t元组Y值所得的两个新元组仍在r中），则Y多值依赖于X，记为X Y。这里，X，Y是U的子集，Z=U-X-Y。,课程C,教员T,参考书B,物理 李勇 普通物理学,物理 李勇 光学原理,数学 李勇 数学分析,数学 李勇 微分方程,数学 李勇 高等代数,物理 王军 普通物理学,物理 王军 光学原理,物理 王军 物理习题集,即如果r有两个元组在X属性上

34、的值相等，则交换这两个元组在Y上的属性值，得到的两个新元组也必是r中的元组。,v,t,s,w,例 关系模式WSC（W，S，C）中，W表示仓库，S表示保管员，C表示商品。假设每个仓库有若干个保管员，有若干种商品。每个保管员保管所在的仓库的所有商品，每种商品被所有保管员保管。,对于W 的某一个值Wi,S有一个完整的集合与之对应而不论C取何值。W S对于W 的某一个值Wi,C有一个完整的集合与之对应而不论S取何值。W c,多值依赖具有以下性质：1.多值依赖具有对称性。即若X Y，则X Z，其中Z=U-X-Y。因为每个保管员保管所有商品，同时每种商品被所有保管员保管，显然若W S，则必然有W C。2.

35、多值依赖的传递性。即若X Y，Y Z，则X Z-Y。3.函数依赖可以看作是多值依赖的特殊情况。即若X Y，则X Y。,6.若X Y，X Z，则X Y-Z，X Z-Y。,多值依赖与函数依赖相比，具有下面两个基本的区别:,1、X Y在U上成立则在W（XY W U）上一定成立；反之则不然，即X Y在W（W U）上成立，在U上并不一定成立。因为多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。一般地，在R(U)上若有X Y在W(W U)上成立。则称X Y为R（U）的嵌入型多值依赖。,但是在关系模式R（U）中函数依赖X Y的有效性仅决定于X，Y这两个属性集的值。只要在R（U）的任何一个关系r

36、中，元组在X和Y上的值满足定义5.1，则函数依赖X Y在任何属性集W（XY W U）上成立。,2、若函数依赖X Y在R（U）上成立，则对于任何Y Y 均有X Y成立。而多值依赖X Y若在R（U）上成立，却不能断言对于任何Y Y有X Y成立。,七、4NF定义6.10 关系模式R 1NF,如果对于R的每个非平凡多值依赖X Y(Y X)，X都含有码，则称R 4NF。4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。根据定义，对于每一个非平凡的多值依赖X Y，X都含有候选码，于是就有X Y，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。,显然，如果一个关系模式是4NF，则必为

37、BCNF。但一个BCNF不一定是4NF。关系模式WSC（W，S，C），W S，W C，都为非平凡的多值依赖。码：（W，S，C）所以WSC 4NF。一个关系模式如果已达到了BCNF但不是4NF，这样的关系模式仍然具有不好的性质。如WSC，是BCNF但不是4NF，对于WSC的某个关系，若某一仓库Wi有n个保管员，存放m件物品，则关系中分量为Wi的元组数目一定有m*n个。每个保管员重复存储m次，每种物品重复存储n次，数据的冗于度太大，应继续规范化为4NF。可以用投影分解的方法消去非平凡且非函数依赖的多值依赖。WSC（W，S，C）分解为：WS（W，S），WC（W，C）均为平凡的多值依赖。所以 WS 4

38、NF，WC 4NF。,_,一个满足4NF的关系模式的特点是：1.该关系模式满足BCNF2 该关系模式只允许出现平凡多值依赖。定义：如果Y X或者XY=U，多值依赖X Y是平凡的幻灯片 37,U|,函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已经是最高的了。如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的。事实上，数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖。如有一种连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。存在连接依赖的关系模式仍可能遇到数据冗于及插入、修改、删除异常等问题。如果

39、消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到5NF的关系模式。,6.5 规范化小节规范化的基本思想是逐步消除数据依赖中不合适的部分,使模式中的各个关系模式达到某种程度的分离.让一个关系描述一个概念、一个实体或者实体间的一种联系。若多余一个概念就把它分离出去。,关系模式的规范化过程是通过对关系模式的分解来实现的。把低一级的关系模式分解为若干个高一级的关系模式。这种分解不是唯一的。下面将进一步讨论分解后的关系模式与原关系模式“等价”的问题以及分解的算法。,1NF,2NF,3NF,BCNF,4NF,消除非主属性对码的部分函数依赖。,消除非主属性对码的传递函数依赖。,消除主属性对码的部

40、分和传递函数依赖。,消除非平凡且非函数依赖的多值依赖。,各种范式及规范化过程,定义6.16 关系模式R的一个分解是指 其中U=，并且没有，1=i,j=n，是F在 上的投影。,6.5 关系模式的分解关系模式设计得不好会带来很多问题。为避免这些问题的发生，有时需要把一个关系模式分为几个关系模式。,一、模式分解的三个定义对于一个模式分解是多种多样的，但是分解后产生的模式应与原模式等价。人们从不同的角度去观察问题，对“等价”的概念形成了三种不同的定义：分解具有“无损连接性”。分解要“保持函数依赖”。分解既要“保持函数依赖”，又要具有“无损连接性”。,所谓“是F在 上的投影”的确切定义是：定义6.17

41、函数依赖集合 的一个覆盖 叫做F在 上的投影。,例 ui=ABC Uj=ABCD,例 关系模式R，其中U=SNO，SDEPT，MN，F=SNO SDEPT，SDEPT MN。语义是学生SNO正在SDEPT系学习，其系主任是MN。一个学生只在一个系学习，一个系只有一个系主任。由于R中存在传递函数依赖SNO MN，会发生更新异常。进行如下几种分解：,S1 D1 张平,无损联结性：分解后的关系做自然联接和分解前的关系完全一样吗？会不会多出某些信息或丢失某些信息。,依赖保持性：分解以后的关系模式能否保持原有的函数依赖。,无损联接性和依赖保持性是关系模式分解和联接中的重要问题。,SNO SDEPT MN

42、,S2 D1 张平,S3 D2 李四,S4 D3 王一,分解三既具有无损连接性又保持函数依赖。它解决了更新异常，又没有丢失原数据库的信息，所希望的分解。,SNO=S1,S2,S3,S4 SDEPTD1,D2,D3 MN=张平，李四，王一SNO SDEPT MN,失真,具有无损联接性丢失了函数依赖SDEPT MN,F,记号：设 是RU，F的一个分解，r是RU，F的一个关系。定义即 是r在中各关系模式上投影的连接。,定义 设F是关系模式R的一个依赖集。是R的一个分解。如果对于R的任一满足F的关系r都有 则称这个分解是满足依赖集F的无损联接性分解。,二、无损联接性和保持函数依赖性,无损联接分解可以通

43、过自然联接恢复原来的关系。,引理6.4 设有关系模式R，是RU，F的一个分解，r是R的一个关系。则 证：任取r中的一个元组t，设（i=1,2,k)。对k进行归纳可以证明，所以。,由 已设s=，所以，只需证明，就有任取，必有S中的一个元组v，使得。根据自然连接的定义，对于其中每一个 必存在r中的一个元组t，使得。由前面 的定义即得。又因，故。又由上面证得，故即。故。,的结论告诉我们，把分解后的关系做自然联接必包含分解前的关系，即分解是不会丢失元组的。因为分解是用投影法把原关系的某些信息“照”下来。对于每一列属性值都不会丢失，因而把分解后的关系再做自然联接，其结果关系必包含原来的关系，而且有可能多

44、出来。只有当 时，分解才是连接不失真分解。的结论说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此后的多次分解均能使分解不失真。,是RU，F的一个分解，,无损联接性检验算法：，设F是一极小依赖集，记方法：构成一个k行n列的表。每一列对应一个属性，每一行对应分解中的一个关系模式。若属性，则在第i行第j列上填上，否则填上。对每一个 做下列操作：找到 所对应的列中具有相同符号的行，考察这些行中 列的元素，如果其中有 则全部改为；否则全部改为；m是这些行的行号最小值。如果在某次更改之后，有一行成为 则算法终止。具有无损连接性，否则 不具有无损连接性。对F中p个FD逐一进行一次这相的处置，称为

45、对F的一次扫描。比较扫描前后，表有无变化，如有变化，则返回第2步。否则算法终止。如发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此循环必然终止。定理5.4 为无损连接分解的充分必要条件是算法5.2终止时，表中有一行为。,例 已知关系模式R，U=A，B，C，D，E，F=AB C，C D，D E，R的一个分解：首选构造初始表。,2.逐个检查每一个FDi,修改表中元素。表中第一行成为a1,a2,a3,a4,a5，所以此分解具有无损连接性。,A B C D E,ABC a1 a2 a3 b14 b15,CD b21 b22 a3 a4 b25,DE b31 b32 b33 a4 a5

46、,A B C D E,ABC a1 a2 a3 a4 a5,CD b21 b22 a3 a4 a5,DE b31 b32 b33 a4 a5,如 在 F中，则第2行全a。可知具有无损联接性。如果 不在F中，但在 中，即它可以用公理从F中推出来，从而也能推出。其中，用算法可将Ax列的第二行改为a，同样可将 中的其它属性的第2行也改为a，这样第2行就变成了全a。分解 具有无损联接。必要性：设按算法构造的表中有一行全a，如第一行全a，则由函数依赖定义可知。,定理6.5 R的一个分解 具有无损联接性的充要条件是 或 说明：充分性：设按算法构造下表：,例 R=（A，B，C），F=A B，C B，=AB，

47、BC=AC，BC解：=B，=A，=C 不具有无损连接性。=C，=A，=B 因为 C B属于F。所以 具有无损连接性。,定义6.19 若,则R的分解 保持函数依赖。,引理5.3 的充要条件是 和。此引理给出了判断两个函数依赖集等价的可行算法，也给出了判别R的分解 是否保持函数依赖的方法。幻灯片 19,例 设R，U=A，B，C，D，F=A B，B C，D B R的一个分解=AB，AC，BD，保持函数依赖吗？求F在 的每个模式上的投影。求=A B，A C,D B 与F等价。所以 保持函数依赖。,三、模式分解的算法,对于任一关系模式都可分解为3NF，同时满足无损联接性和依赖保持性。算法6.3 转换为3

48、NF的保持函数依赖的分解对R中的函数依赖集F进行极小化处理。处理后得到的依赖集仍记为F。找出不在F中出现的属性，将它们构成一个关系模式，从U中将它们去掉，剩余的属性仍记为U。（虽然其中没有函数依赖，但我们可把它的所有属性当作关键字。）如F中有一依赖XA，且XA=U，则，算法终止。否则，对F按具有相同左部的原则分组（假定分为k组）,每一组函数依赖 所涉及的全部属性形成一个属性集。若 就去掉。由于经过了步骤（2），故,于是 构成R的一个保持函数依赖的分解，并且每个 均属3NF。例 R（CTHRSG），,显然属于3NF，而 保持函数依赖也很显然。只要判定 的无损连接性。证明略。,算法6.4 转换为3

49、NF既有无损连接性又保持函数依赖的分解设X是R的码。R已由算法5.3分解为，令若有某个,，将 从 中去掉。就是所求的分解。,定理6.11 若 是R的一个具有无损联系性的分解，是 中的一个无损连接分解,那么(是R包含 的关系模式集合的分解)均是R的无损联接分解。证：是 的无损联接分解，故对于 满足 的所有关系 有而 所以有=是R关于F的无损联接分解，故对于R满足F的所有关系r有 由无损联接分解的定义可知，是R关于F的无损分解。,先证下列等式，设r是关系模式R的一个关系，是R的子集，即有归纳法：i=1,即证由于，本质上是一个选择运算，即选择公共属性 上具有相同值的那些r的元组。从而 是r的一个子集

50、，即 根据引理，可知 归纳：设i=K时结论为真即则当i=K+1时有：原结论为真。,是R的无损联接分解。,因为 是R的一个分解,故 由定义可知，是R关于F的无损联接性分解。,算法6.5 转换为BCNF的无损连接分解方法：反复运用定理5.11，逐步分解关系模式R，使得每次分解都具有无损 联接性，并且分解出来的关系模式都是BCNF。令 检查 中各关系模式是否均属于BCNF，若是,则算法终止。设 中 不属于BCNF，那么必有，且X非 的码。对 进行分解：，以 代替 返回（2）。由于U中属性有限，因而有限次循环后算法一定终止。,例：R（B，D，I，S，O，Q），F=SD，IB，ISQ，BO把R分解为BC