数据库系统原理及应用丁忠俊第四章关系数据库理论.ppt

第四章 关系数据库设计理论,第一节 概述,一、关系DB设计理论的主要内容1、解决的主要问题从理论上来讲，如何设计一个比较好的关系模式的集合？,2、本章的主要内容,三方面的内容：,数据依赖（函数依赖、关键字、函数依赖的推理规则）关系模式的分解（两种特性：无损联接性和保持依赖性）范式理论（1NF-5NF）,其中：数据依赖是基础。即：范式理论和关系模式的分解都是建立在数据依赖的概念基础之上。,二、关系模式使用中的异常问题例:设有关系模式R（TNAME，ADDR，C#，CNAME）（分别为：教师名，地址，课程号，课程名）其关系如下：,R,现实世界的事实可知：一个教师只有一个地址一个教师可讲若干课程每门课程只有一个教师任教,R的侯选关键字为:(TNAME,C#),在使用过程中会存在以下问题：（1）数据冗余：当一个教师若讲多门课程，则其地址值会重复存储多次。数据冗余：同一个数据重复存储。数据冗余会引起：浪费存储空间；造成修改数据不一致性。,（2）更新操作异常修改异常：由数据冗余引起的。如上例：t1教师讲了三门课，其地址值a1重复存储了三次；若t1搬家，则它的地址值必须修改三处值，若只修改一处，则会产生修改不一致性。插入异常：指该插入的数据而不能插入到关系中。如：新增加一个教师，但尚未分配讲课任务，则不能将其姓名和地址值插入到R中。原因：R 的候选关键字（TNAME，C#）中，C#为空值。即：候选关键字中主属性为空或部分为空的元组违反了实体完整性原则。,删除异常：指不该从关系中删除的数据被删除了。如：若要把原来上过课，但目前未上课的教师的所有元组删去，则将该教师的姓名和地址信息也从R中删除了。注：DB的更新操作异常和数据冗余在网状，层次，面向对象的模型也存在。,什么原因使得关系产生操作异常和数据冗余呢？原因：关系模式中的属性之间依赖问题；这就是引入属性之间函数依赖的原因。现在采用函数依赖的概念，利用分解方法，将R 分解两个等价的关系：R1（TNAME，ADDR）R2（TNAME，C#，CNAME）,数据冗余大减，上述情况的异常消除。关系模式如何分解；分解到一个什么程度为好？将是本章讨论的问题。,R1,R2,第二节 函数依赖,一、函数依赖（Functional Dependency 简称FD）的定义定义1：设有关系模式R（U），U=A1，A2，An，若对R的所有具体关系r都存在：对于每一个X值，都有唯一的Y值与之对应，则称 X 函数决定 Y；或说 Y 函数依赖于X，记为：,定义2：设有关系模式R(A1,A2,An),和 均A1,A2,An的子集，r是R 的任一具体的关系(R-型,r值),t1和t2是r中任意两个元组,若由 导致,则称 函数决定,或说 函数依赖于,记为：,注：(1)FD是对R一切可能的当前值r定义的，不是针对某个特定关系。(2)FD是语义范畴的概念，只有通过属性之间的语义来确定是否存在函数依赖关系，不能用数学方法推导或证明。它是现实世界中属性之间客观存在或设计者人为强制相结合的产物。例:若设计者限定：无同名同姓；则：姓名年龄（反之：年龄 姓名），若有同名同姓：则，姓名 年龄。(3)中，称为决定的因素，只要 取一个值，则有 唯一的值与之对应。,二、函数依赖与属性间联系的关系设关系模式R，则：(1)如果，之间是1-1联系，则存在：和，即，相互函数依赖 记为。(2)如果,之间是 m-1联系，则存在,。(3)如果X,Y之间是n-m 联系，则X,Y 之间不存在函数依赖，即，.结论：根据关系r当前值，可从属性间的联系入手来决定函数依赖是否存在。,例：已知关系r如下,r,下列函数依赖中，关系r满足哪些依赖？,a、ABb、(A,B)Dc、C(B,D,E)d、EAe、AE,三、关键字（键、码）用FD概念精确定义关键字定义：设关系模式R（A1，A2，An），F是R上的函数依赖集，X是（A1，A2，An）的一个子集，如果：（1）XA1，A2，An且（2）在X中不存在真子集 Y，使得YA1，A2，An成立，则称X是R的候选关键字。注：条件（1）表示X能唯一决定一个元组。条件（2）表示X是满足（1）而无多余的属性集。,例：关系模式R（学号，姓名，性别，年龄）中，按语义：学号姓名 学号性别 学号年龄 学号（学号，姓名，性别，年龄）学号是R一个候选关键字。也可说明：（学号，姓名）也可决定R中的全部属性，但（学号，姓名）不是候选关键字。（学号，姓名）存在真子集：“学号”可以决定全部属性；“姓名”属性多余。说明：主属性：包含在候选关键字中的属性。非主属性：不包含在候选关键字中的属性。,四、函数依赖的分类,根据不同性质，函数依赖分类：,完全函数依赖部分函数依赖传递函数依赖,1、完全函数依赖与部分函数依赖定义：在关系模式R（U）中，如果，并且对 的任何一个真子集，都有 则称 完全函数依赖于，记作。如果对 某个真子集,有，则称 对 的函数依赖是部分的函数依赖，记作：。,例：关系模式SC(学号，课程号，成绩)中，显然：学号 成绩，课程号 成绩，而：(学号，课程号)成绩,可见：(学号、课程号)是候选关键字：学号，课程号是主属性；成绩为非主属性。又如：关系模式R(学号，课程名，系名)中：学号系名,课程名 系名,(学号，课程名)系名.,f,p,注：只有决定因素是组合属性，才存在部分函数依赖，当决定因素是单属性时，只能是完全函数依赖。,2、传递函数依赖定义：在关系模式R（U）中，如果，且，则称Z传递函数依赖于，记作:。注：当条件 不成立时，即，则，实际上是直接函数依赖而非传递函数依赖。,例：在关系模式R（学号，学生姓名，系名，系主任名）中。学号学生姓名 学生姓名系名（设无同名同姓）则：学号系名是直接函数决定再：学号系名，系名 学号，系名系主任名，则有：学号 系主任名。,t,五、函数依赖的逻辑蕴涵,有时需要从一些已知的FD去判断另一些FD是否成立。如：已知F=AB，BC在模式R中成立，那么AC在R中是否成立。这个问题称为逻辑蕴涵问题。定义：设F 在关系R上成立的函数依赖集,XY是一个其他的FD(XR,YR)。如果从F中的函数依赖能推出XY，则称F逻辑蕴涵XY，记为：F|XY。,定义：被F函数蕴涵的函数依赖的全体构成的集合称为F的闭包(closure),记为：F+=xY|FXY一般，F F+，若F=F+则称F是函数依赖的完备集。,值得注意：依据F计算F+是很麻烦的，即使F不大，F+也可能很大。如：有关系R(X,Y,Z)其函数依赖集F=XY,YZ则,共有43个依赖,这些函数依赖怎么出来？待学习了函数依赖的推理规则，再回答此,问题,第三节 F D 公理,目的：确定函数依赖的逻辑蕴涵。即从给定的F中的函数依赖，推出F+中的函数依赖。也就是说给定了F和，判断是 否在F+中。为此，要有一套推理规则。,一、Armstrong 公理 设有关系R(A1,A2,An)和属性全集U=A1 A2An X，Y，Z，W均是U的子集；F是U上的一个函数依赖集，推导规则是：A1 自反性(Reflexivity)：若，则F逻辑蕴涵（平凡的函数依赖）A2 增广性(Augmentation)：若F逻辑蕴涵，则F逻辑蕴涵A3 传递性(Transitivity)：若F逻辑蕴涵,F逻辑蕴涵：,例：设R(C,S,Z)，其中：C为城市名，S为街名，Z为邮编，给定F=CSZ,ZC 即函数依赖图如下：,由Armstrong公理，有(1)ZC(已知)说明：ZC逻辑蕴涵F+中。(2)SZCS(由(1)和 A2增广性)说明:SZCS 逻辑蕴涵在F+中。(3)CSZ(已知)(4)CSCSZ(由(3)和A2增广性)说明：CSCSZ 在F+，也说明 CS是R 的一个候选关键字。(5)SZCSZ(由(2)和A2增广性，或由(2),(4)和A3传递性)说明：SZCSZ 在F+中，也说明 SZ 是R 的另一个候选关键字。注：可以证明候关键字：CS 和 SZ 中没有多余的属性存在。,说明：通过公理可以推出F中的隐含的FD，尤其可推出关系R的候选关键字。能否保证由公理推出的函数依赖都是正确的，即所推出的函数依赖都是否 都属于F+？公理的正确性。正确性：只要F的FD为真，由公理推出的FD也为真，则推出的FD都由F+逻辑蕴涵。若公理正确，求F+，则可根据F通过公理推出所有的函数依赖。属于F+中函数依赖是否都能够由公理通过F中的FD推出？公理完备性。,定理：Armstrong公理是正确的，即若 是由F通过公理推出的，那么 在F+中。,证明：用FD定义证明(1)自反性：设r是R的任意一个关系，t1和t2是r任意的两个元组。若，则在t1和t2中的 的任何子集也必相等 由条件：必有 由FD定义可知：,(2)增广性：设t1,t2,r的含义同上采用反证法：假定结果不成立：，即：但 由 设：或 若 则与已知的 相矛盾(,)若 则与假设的 相矛盾 增广性是正确的,(3)传递性：设t1,t2,r的含义同上采用反证法：假设结果不成立：即 X Z 即 但 若 则与条件 相矛盾(则，但由上)，若 则与条件 相矛盾(，则)传递性正确,推论：由阿氐公理可以得出如下推论：(1)合并规则：若，成立，则 成立(2)分解规则：若 成立，则，成立(3)伪传递规则：若，成立，则 成立,证明：用公理证明,(1)(已知)(2)(3)(已知)(公理A2)(公理A1)(公理A2)又(已知)同理(公理A1)(已知)(公理A2)(已知)(公理A3)(公理A3)(公理A3)同理(公理A3),例：判断下列推论是否正确，若正确给出相关证明；若错误，试举出一反例说明(1)如果ABC，则BC(2)如果ABC，则AB,或AC(3)如果AB 并且BCD,则ABCD解：(1)错误(2)错误(3)正确,R,R,AB ABCBC又 BCD ABCD（公理A3）,R 满足ABC 但B C;R 满足ABC 但A C，A B,说明：通过规则A1，得出平凡的FD概念：对于函数依赖,若,则称 是平凡的函数依赖；若，则为非平凡的 FD。如：AA,A是平凡FD.平凡FD总是成立的，对A的语义无影响，对模式设计也没有影响。一般不考虑平凡FD,根据推论中合并和分解规则：得出 推论：若A i(i=1,2,n)是关系模式R 的属性集则 XA1 A2An成立的充分必要条件是XA i(i=1,2,n)均成立。,属性集的闭包概念定义：设有关系模式R(A1,A2,An)，U=A1,A2,An；F是U上的一个函数依赖集，则称所有用公理从F推出的函数依赖 中的Ai的属性集合为X 的属性闭包，记为。即：=Ai用阿氐公理从F推出 XA i。显然：,例：设关系模式R(A,B,C),R 的FD集 F=AB,BC 则：C+=C(CC)B+=BC(由BB,BC)A+=ABC(由AA，AB，BC；AABC)A 是R的侯选关键字 可见：计算属性闭包 比从F计算F+要简单得多。下列定理告诉我们判断：从 一眼看出某一函数依赖是否是用阿氐公理从F推出。定理：设F是关系模式R(A1,A2,An)的FD集，U=A1,A2,An。若，则 是用阿氐公理从F推出的充要条件是。,二、Armstrong公理是完备的。证明见书(证明：不能从F通过公理推出的FD不在F+中)Armstrong公理完备性告诉我们两个重要结论：(1)所有由F逻辑蕴涵的 的右端属性A的集合称为 的属性闭包。(与 定义等价)(2)用阿氐公理从F推导出来的所有FD的集合是F的闭包F+(与F+定义等价：F+是由F逻辑蕴涵的所有FD的集合)可见:函数依赖公理和函数依赖的逻辑蕴涵之间有某种等效关系。,三、属性集闭包的计算计算F+的目的：确定某一函数依赖 是否由F逻辑蕴涵，即它是不是成立。公理的完备性说明：通过计算，若 则 是由阿氐定理从F推出，则 是成立的。这就说明:则 成立。因此，把计算F+转化为 计算，可达到同样的目的。,算法：求属性集 在F上的属性闭包。输入：关系模式R的全部属性集U，F为U上的函数依赖集输出：在F上的属性闭包方法：按下列规则计算；,(1)置初值(2)其中A是这样的属性：在F中寻找尚未用过的左边是 的子集的函数依赖：其中：在Z中寻找 中未出现过的属性集合A；若无这样的A则转(4)，否则：(3)判断是否有，若是则转(4)，否则转(2)(4)输出，即为上述方法计算步骤是很有限的，因为U,X,F是有限集。,例：设函数依赖集F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG 试用算法，求(BD)+,解：设=BD(1)=BD(2)在F中找左边是BD子集的FD，只有：DEG，显然(i=0)接下来在F中找左边是BDEG子集的FD，(但用过的不再考虑)：BEC，显然(i=1)又在F中找左边是BCDEG的子集的FD：CA,BCD,CGBD,CEAG 于是：BCDEGABDG(不考虑用过的FD)，在 中未出现的属性是A 此时，虽然，但发现 已包含了全部属性，所以不再计算下去。若即使计算下去，很快发现 或再也找不到在 中未出现的属性。(BD)+=ABCDEG,说明：判断计算终止的4种方法：(1)；(2)当 包含了全部属性；(3)在F中FD的右边属性中再也找不到 中未出现过的属性；(4)在F中未用过的FD的左边属性已经没有 的子集。算法计算正确性见书。,说明：利用 求R的候选关键字：上例：由于(BD)+=ABCDEG(B,D)可能是R的候选关键字；(B,D)是否一定是R候选关键字，则还要看(B,D)是否存在决定全部属性的 真子集：即(B)+ABCDEG D+ABCDEG 求B+求D+=B D+=DEG=B D也不是真子集 B+=B B不是真子集(B,D)是R的一个候选关键字怎么找出R的全部候选关键字呢？(下面介绍求候选关键字的理论),四.FD集的等价和覆盖（求F 的最小集）定义：设F和G是两个函数依赖集，若F+G+则称F和G等价；如果F和G等价，则说F覆盖G，同时G覆盖F。引理1：设F和G是函数依赖集，则F+G+的充分必要条件是F G+且G F+。证明略。这说明，检查F和G是否等价并不困难，只要检查 F G+且G F+是否成立。检查F G+是否成立,即F中的每一个FD是否属于G+。例如：对于X Y F，则在G上计算X+，看是否满足Y X+，若满足，则X Y G+。继续检查其他所有依赖，若全部满足，则F G+。同理，对G中每个依赖作同样的处理来检查G F+才能确定F+=G+.引理2:每一个函数依赖集F都可以由一个右端只有单个属性的函数依赖集G所覆盖。证明：设G由行为X A（A为单属性）的函数依赖组成。AY且X Y在F中。此时，显然能从X Y按分解规则导出X A，从而有G F+。,.,反之，如果YA1A2An，而且X A1，X A2，X An在G中，可根据合并规则得：X A1An，因而有F G+。由此得：FG，即F被G覆盖。在研究FD时，它的最小集是很有用处的。定义：对于给定的一个函数依赖集F,当满足下列条件时，称为F的最小集，记为F（最小集也称为最小覆盖）。（1）F 的每个依赖的右部都是单个属性；（2）对于F 的任一函数依赖X A来说，F X A与F 都不等价；（3）对于F 的任一函数依赖X A来说，（F X A）U Z A与F 都不等价，其中Z为X的任一子集。这个定义中：条件(1)保证了每个依赖的右边都是单属性 条件(2)保证在F中不存在多余的依赖 条件(3)保证在F中的每一个依赖的左边没有多余的属性,定理：每一个函数依赖集F都与它的最小依赖集F 等价这个定理的证明按最小依赖集的定义考虑其三个条件，证明的过程也是计算最小集的过程。证明过程见书。,例：设FAB C，C A，BC D，ACD B，D EG，BE C，CG BD，CE AG求F 解：按最小覆盖依赖集的定义，分别考虑三个条件。（1）用分解规则，将F中所有的FD变为右边是单属性的依赖AB C，C A，BC D，ACD B，D E，D G，BE C，CG B，CG D，CE A，CE G（2）去掉F中函数依赖左边多余的属性方法：逐个检查F中左边非单属性的依赖，如：XY A，若判Y是否为多余属性，只要在F中求X+，若X+包含A，则Y为多余属性，否则Y不多于，依法判F中其它FD。考察：ACD B（CD）+CDAEGBA为多余属性，应去掉，即用CD B代替ACD B,再考察：CE A(C)=CA(C A)E为多余属性，用C A代替CE AAB C，C A，BC D，CD B，D E，D G，BE C，CG B，CG D，C A，CE G（3）去掉F中多余的依赖方法：从F中的第一个FD开始，将它从F中去掉（设为X Y），然后从剩下的依赖求X，看X是否包含Y，若包含，则X Y是多余的，应去掉，这样依次做下去。,(1),显然：上面F中有两个C A，应去掉一个.考察;CG B先去掉CG B则：CG D保留（CG）CGD（CG D）（CG）CGDB（CD B）CG B为多余FD。得：FAB C，C A，BC D，CD B，D E，D G，BE C，CG D，CE G 注：求出的F不是唯一的。,注：依F中的顺序不同，则F是不同的若先考察：CD B（CD）CDG（D G）（CD）CDGB（CG B）CD B多余.再考察：CG D（CG）CGB（CG B）（CG）CGBD（BC D）CG D 多余另一个FAB C，C A，BC D，DC E，D G，BE C，CG B，CE G,(1),(1),(2),(2),(2),(1),第四节 关系模式的分解,一、关系模式分解中的问题1模式分解的目的为了消除更新异常（插、删、改）和减少数据冗余，设计一个较好的关系模式。2模式分解的定义定义：设有关系模式R（A1，A2，A3，An）,Ri(i=1,2,k)是R的一些属性子集，R1R2Rk=U 则称用=R1,R2,Rk代替R的过程称为关系模式R 的分解。注：关系模式的分解，不仅仅是属性集合的分解，它是对模式上的函数依赖集以及关系模式当前值的分解的具体表现。,例，设关系模式（其中S#为学号，SD为系名，MN为系主任名），R中当前值的关系r如下：,关系r,若不分解R，存在的问题：删除异常：若S4学生毕业了，删除S4则D3系的系主任的王一的信息随之丢失。插入异常：若一个系D5尚无学生，则这个系的系主任赵某信息无法插入R中。数据冗余：系和系主任的名称会多次重复存储。,F=S SD,SD MN,#,3模式分解中的问题,（1）将R分解为 则对每一个ri 有：,将R按下列3种方式分解：,rr1 r2 r3 R1(r)R2(r)R3(r),r3=张五，李四，五一,分解的特性:既不保持函数依赖性，又不保持无损连接性。R1R2R3的属性之间不能保持F中的函数依赖：不能回答“S1在哪 个系学习”的问题。分解后r1r2r3难以恢复原来r值，即,一般表示：,（2）将R分解为 则得r4和r5的关系如下：,r4,r5,不保持SDMN，仍存在前面提到的数据冗余插入和删除异常。保持无损的连接性：分解后r4和r5中没有损失r中的数据,即用连接运算可以恢复：r=r4 r5=R4(r)R5(r)(与原来r中的元组一致),分解的特性：不保持FD性,但保持无损的连接性。,总之：模式分解特性的四种情况：,1）既不具有无损连接性，又不具有函数依赖的保持性。（不可取的分解）2）具有无损联接性。3）具有函数依赖的保持性。4）既具有无损联接性，又具有函数依赖的保持性。（最好的分解特性）,（3）将R按F中的两个依赖分解：,r6,分解特性:既保持FD性,又保持无损的连接性。即保持F中的FD，又不损失r中原来的数据即：r=r4 r6 异常操作不存在.,二、无损连接的分解1、定义：设F是关系模式R 的一个依赖集，=R1,R2,.,Rk 是R 的一个分解，如果对于R 的任意一个满足F 的关系r 都有：r=R1(r)R2(r)Rk(r),则称这个分解是满足F 的无损连接分解。注：若设m(r)=R1(r)R2(r)Rk(r)=Ri(r)分解具有无损连接性的条件是：r=m(r)。分解不具有无损连接性的条件：r m(r)，一般：r mp(r)引理：设关系模式R的一个分解=R1,R2,Rk，r 为R 任一关系，ri=Ri(r)(1ik)则(a)r m p(r)(b)Ri(m p(r)=Ri(r)(c)m p(m p(r)=mp(r),i=1,k,例：有模式R(A,B,C),分解为R1(A,B)和R2(B,C)各有具体关系r,r1,r2如下：r r1=A,B(r)r2=B,C(r)R=A,B(R),B,C(R)而mp(r)=A,B(r)B,C(r)如下表 显然比r 多出一个元组（a2,b1,c1）：寄生元组 这就是 r mp(r)的含义可见将R分解R1和R2不具有无损联接性,但保持函数依赖性（A B）,1，,A,B(r),A,C(r),A,C(r),B,C(r),2,3,mp(r)=A,B(r)A,C(r):r=m(r)，具有无损的连接性分解：既保持函数依赖（AB），又具有无损的连接性。,mp(r)=A,C(r)B,C(r):r=m(r)，具有无损的连接性分解：不保持函数依赖性（A B），但具有无损的连接性。,第2种分解最理想，其次第3种分解，第1种分解不好。,注：无损连接的分解应是关系模式分解时所必须满足的条件。因为分解前后的数据，作同样的查询，应产生同样的结果。保持函数依赖性就是保持属性间的语义在分解后不变（不割裂属性间的语义）。一个具有无损联接分解不一定保持依赖保持性；反之，一个具有依赖保持性的分解也不一定具有无损联接性。,2无损连接分解的判断算法：无损连接的判断(判定表法)输入：关系模式R（A1，A2，An），它的函数依赖集F，以及R 的一个分解=R1,R2,Rk 输出：判断 相对于F是否具有无损连接特性。,方法：（1）构造一个k 行n列的表：每列对应一个属性Aj（1jn），每行对应一个模式Ri（1iK），若Aj Ri，则在第i 行处填上符号 aj,否则填上符号 bij。（2）逐个地检查F中的每个函数依赖，并修改表中元素。方法如下：取F中的,在 X 的分量中寻找相同的行，然后将这些行中 Y 的分量改为相同的符号，如果其中有aj，则将bij改变aj，若其中无aj，则改为bij。（3）反复重复（2），如果发现某一行变成了a1,a2 ak，则分解的具有对F的无损连接性，否则具有连接接性。,例：设关系模式R=(A,B,C且F=AB,CB,分别判断下列分解是否具有无损连接性。(1)p1=AB,BC(2)p2=AC,BC(3)p3=AC,AB解（1）构造一个表对于AB,A列中无相同的行；对于CB,C列中无相同的行；无法修改且也无全部为aj 的行。p1不具有无损连接性。,（2）构造一个表查：CB；C列中有相同的行，于是将第一行的B改为a2,则此时，立即发现第一行为a1,a2,a3所以不再检查其他依赖，则可判定p2具有无损联接性。若按前例：r1=r2=S=r1r2=,(3)构造一个表查：AB；发现A列中有两行相等，把B列第一行b12也改为相应的a2,则在第一行出现a1,a2,a3，于是具有无损连接性。可使用简便列表法：其思想与原列表一样，只是bij不填入表中，使其留空位，只将ai填入表中，然后按算法改变表中的元素，如：上例（3）定理：算法1能正确的判定一个分解是否具有无损连接性。,例：设有关系模式R(U,V,W,X,Y,Z),其依赖集F=UV,WZ,YU,WYX 判断下列分解是否具有无损联接性,(1)1=WZ,VY,WXY,UV(2)2=UVY,WXYZ,解:(1)构造1无损联接判定表,由 UV 可知U中无相同的行,故V不能修改 WZ;将b36改为a6(W中有相同行a3)YU;Y列中有相同的行a5,将U列中的b31改为b21 W Y X;WY两列中无相同的行,故X不能修改。,由化简的判定表可知1不具有 无损联接性。,(2)判断2的无损联接性可用两种方法：构造判定表法和推导法a、构造判定表法,考察F：UV；V列不能修改(U列中无相同行)WZ；Z列不能修改(W列中无相同行)YU；Y列有相同行a5,则U列中 将b21改为a1 WYX；Y中有相同行，但W无相同行 X列不能修改。,判定表为：,b、推导法(它被分解成两个关系)(UVY)(WXYZ)=Y又(UVY)-(WXYZ)=UV(WXYZ)-(UVY)=WXZ(UVY)(WXYZ)(UVY)-(WXYZ)即YUV不在F 中,但在 中即用公理推出：Y U，U V传递性：Y V，由合并性：Y UV根据定理：2分解为无损联接。,对于只包含两个关系子模式的分解，有更简单的方法可检验的无损联接性。定理：设=R1,R2是R的一个分解，F是R上函数依赖集，则对于F+来说，具有无损联接性的充要条件是(R1R2)(R1R2)或(R1R2)(R2 R1)。,三、保持依赖的分解定义：设F是关系模式R(U)的函数依赖集,Z U,F在Z上的一个投影用Z(F)表示，定义为：Z(F)=|定义：设=R1,R2,Rk是关系模式R的一个分解，F是R的一个FD集。若，则称分解保持函数依赖集F，其中：（或称 具有依赖保持性）,即：分解前的F和分解后的F等价。,例：R(A,B,C),F=AB,CB 当有一分解：=AB,AC（具有无损连接性）但，A,B(F)A,B(F)=AB，并不等价于F，不保持函数依赖性。说明：直接按保持函数依赖性的定义去论证一个分解是否保持原FD集是不现实的，因为需要计算F+的时间是指数级的。比较可行的方法：逐个验证F中每个FD是否为 Ri(F)所逻辑蕴涵。这种方法计算的复杂性是多项式时间级。总之：保持函数依赖性的论证是困难的。实质上他是要求两个函数依赖集的等价问题。分解不保持FD性带来两个问题：1）破坏原来成立且被丢失的FD，导致语义出错。2）造成无约束地对数据插入或修改，使数据出错。,k,i=1,例：设关系模式GZ（N，T，S），属性表示职工号，职务，工资。若规定：一个职工只有一个职务，一种职务只有一个工资数目。那么,GZ上的FD集F=NT，TS。若将GZ分解成=GZ1（NT），GZ2（NS），可以判定是无损分解。GZ1上的FD集F1=NT，GZ2上的FD集F2=NS；由于F中的TS不被F1F2逻辑蕴涵，即TS被丢失了，所以，不保持FD性。即不保持FD：TS，会产生：,GZ,=,造成无约束地对数据的插入或修改，使数据出错。例如，由于GZ2在N与S之间无函数依赖，系统无法检查对GZ2插入或修改数据的语义完整性，这样，若向GZ2中插入无约束的数据与向受约束的GZ1中（满足FD：NT）插入的数据做连接操作后，就产生了错误的数据：“S1和S2同是处长却有不同的工资数”。破坏了原来成立且被丢失的函数依赖，导致语义混乱。原来TS成立，连接后不成立。,GZ1的r1,GZ2的r2,r1 r2关系,=,注:(1)保持函数依赖与无损联按分解这两个要求在性质上有些差异，前者决定分解的好坏,而后者决定能否分解.不保持函数依赖的分解则会产生异常操作,有损分解是无实用意义的。(2)关系模式的分解主要准则：满足无损联接分解要求。既满足无损联接分解要求,又满足保持依赖要求准则(2)比(1)理想,但分解要受到更多的限制。(3)只满足保持依赖而不满足无损联接分解的分解是存在的。如:R(A,B,C,D)设,则分解 保持依赖,不满足无损分解的要求,这种分解前后的关系模式不等价,因而无实用价值。因此:在DB设计中,只满足保持依赖不宜作为关系分解的一个独立准则。,本节小结:讨论关系模式的分解两个特性，实际上涉及到两个模式的等价问题，包括数据等价和依赖等价。数据等价是指两个模式中实例应表示同样的信息内容，这就用无损联接衡量。依赖等价是指两个模式应有相同的依赖集闭包。在依赖集闭包不变的情况下，数据的语义是不会出现差错的。,第五节 关系模式的规范化,用什么标准衡量分解后的模式的好坏呢？满足特定函数依赖要求的模式称为范式。,一第一范式（1NF）与第二范式（2NF）11NF定义：如果一个关系模式R的每个具体关系r的每个属性值都是不可再分 的最小数据单位，则称R为第一范式，简记1NF。,如：,r1(非1NF),r2(非1NF),1NF,1NF,改写：去掉组项,改写：去掉重复组,注：DB中关系一般要求至少是1NF,22NF定义：设 是关系模式R的一个FD，若存在的真子集，使的 成立，则称 部分函数依赖 X，简记：，否则称 完全函数依赖于，简记：。定义：满足1NF的关系模式R，如果它的所有非主属性完全函数依赖于任一 侯选关键字，则称R是第二范式，记为2NF。注：1，关系模式R中的每个侯选关键字都由单个属性构成，则R一定是2NF。关系模式R中的某个侯选关键字由多个属性构成，只要有一个非主属性部分函数依赖于该侯选关键字，则R一定不是2NF。2，关系模式R中的属性都是主属性，无非主属性，则R必定是2NF。3，二元关系模式必定是2NF。,例如：有关系student 如下：,存在插入异常：当新教师尚未任课，无法插该教师信息；存在删除异常：当学生毕业或退学教师信息被删除。,：非主属性部分依赖于侯选关键字,分解：消除部分函数依赖,显然,根据语义：该关系的关键字（SNO，CNO）,冗余得到有效控制:讲授同一门课的教师:NAME和LOCA只出现一次(当学生多时)；消除删除异常：学生降级或退学时,因删除仅在ST1上进行,不会丢失课程方面的信息；修改异常得到控制：某任课教师改变了,其修改只涉及ST2的一个元组。,二、第三范式 2NF关系并不能解决所有问题，尽管解决以上部分问题但：,例:上例：,ST2,存在新的插入异常：有新教师报到，要将数据插入到ST2中，但未教课程（即CNO为空），而不能插入。删除插入异常：删除课程方面操作，则会删除教师的信息。修改插入异常：由于一个教师可讲多门课程，要修改时，必须涉及多个元组。,原因是：在ST2中存在非主属性对关键字的传送函数依赖：CNONAME，NAME LOCA,但NAME CNO 即：CNO LOCA,t,定义：在关系模式中,如果，且 和 称 传递函数依赖，记为。,定义：如果关系模式R满足2NF，且它的任何一个非主属性都不传递依赖于 任何的侯选关键字，则称R是第三范式，记为：3NF。,例 将ST2分解：消除传递依赖成为3NF ST3(CNO,CTITLE,NAME)教课实体 ST4(NAME,LOCA)教师实体,3NF关系可以解决大多数的异常问题，分解成3NF一般就可以了。但3NF还有特殊异常的情况。,注：1，关系模式R中的属性都是主属性，无非主属性，R必定是3NF。2，二元关系模式必定是3NF。3，关系模式R是3NF，则R必定是2NF。反之不一定成立。,三BC范式（BCNF）3NF的关系存在稀少特殊的异常问题：如,S,每个学生可选多门课程，每门课有多个教师，但每个教师只教一门课。S的候选关键字为：（SNO，CTITLE）和（SNO,NAME）即S中无非主属性，也不存在非主属性对关键字传递依赖。S3NF,但仍存在插入异常：一个新课程和指导教师的数据要插入S中时必须至少有一个学生选修该课程且该指导教师被分配给他时才行，否则SNO为空而不能插入。删除异常：学生退学或改变所学课程时，会丢失课程或指导教师信息。另外，更换某课程的指导教师，且很多选修该课时，修改很麻烦。,特征：多个候选关键字存在重叠属性SNO。,分解：,S1(NAME,CTITLE)S2(SNO,NAME),定义：设F为模式R的依赖集，如果F中所有依赖 的左部(即 中)都包含了R一个候选关键字，则称R是BoyceCodd范式,简记：BCNF。简言之：若R中每一个依赖的决定因素都包含候选关键字，则R为BCNF。,例如：上例SBCNF，其中含NAMECTITLE，但NAME不是候选关键字。但：S1BCNF,NAMECTITLE是S1的唯一依赖,但NAME是候选关键字。S2BCNF,(SNO,NAME)是S2关键字。,定理：一个BCNF范式必定是3NF（但反之不一定）证明：用反证法 设R是一个BCNF，但不是3NF 则必存在非主属性A和候选关键字X,以及属性集y,使得：xy,yA,其中 不在 中(即Y X)，这就是说 y不可能包含R的候选关键字X，但 却成立，根据BCNF定义,R不是BCNF,与题设矛盾，从而定理得证。,4种范式的关系：1NF 2NF 3NF BCNF,规范化关系：,非规范关系 1NF 2NF 3NF BCNF4NF5NF,消去重复组,组项,消去非主属性,对侯选关键字得部分依赖,消除非主属性,对侯选关键字的传递依赖,消去所有的部分和传递,依赖(包括主属性对侯选关键字的部分和传递依赖),四、BCNF的分解 算法：结果为BCNF的无损联接分解。输入：关系模式R及R的函数依赖集F。输出：R关于F的无损联接分解,其中,分解后的每一个关系子模式Ri都是满足 的BCNF。,方法：1.置初值=R;2.如果中所有关系模式都是BCNF，则转4；3.如果中有一个关系模式S不是BCNF，则S中必须能找到一个函数依赖 XA X不是S 的关键字，且，设S1=XA,S2=SA，用分解后的S1，S2 代替S，转2；4.分解结束，输出。,例：R(C,S,Z),F=CSZ,ZC,其中关系模式R3NF，但R 不是BCNF利用算法分解成BCNF：确定R的关键字，显然为（C，S）Z不是R的关键字，且C不属于Z，令R1=CZ，R2=R-C=SZ 则=CZ，SZ 为R的一分解。又R1=C，Z，R2=S，Z为二元关系模式，它们都是BCNF，而是R关于F的无损联接分解。分解结束。注：不是保持依赖分解：CSZ不属于可见：算法只能将R分解成BCNF是无损的，但不一定使R的分解保持函数依赖。,五、3NF的分解对于任何一个关系模式都可以分解成3NF，同时满足无损联接性和保持依赖性。算法把一个关系模 式分解成保持函数依赖性的3NF模式集。,输入：关系模式R及R的最小依赖集。输出：R的一个分解=R1，R2，,Rk，满足每一个Ri相对于 是3NF，且保持函数依赖。方法；（1）如果 中有一个依赖XA，且 XA=R，则=R，转（4）（2）如果R中某些属性在 的所有依赖的左边和右边都不出现，则将它们构成 一个关系模式，并把这些属性从R中分出去单独构成一个模式。（3）对于 中的每一个 都构成一个关系子模式；若F中有：则可将 作为一个模式输出。（4）分解结束，输出。,例：R(C,H,T,R,S,G)的最小覆盖 为=CT,CSG,HTR,HRC,HSR 则：利用算法（3）:（一般情况只利用（3）=CT，CSG，HTR，HRC，HST它们均为3NF，且保持依赖。,定理：设=R1，R2，,Rk是由算法1得到的R的3NF分解，是R的一个侯选关键字，则=R1，R2，Rk,X 也是R的一个 分解，且它具有以下三个属性：,（1）每个Ri(i=1,2,k+1)都是3NF。（2）具有依赖保持性。（3）具有无损联接性。,例：设R(S,SN,P,C,T,Z)F=SSN,SP,SC,ST,SZ,(P,C,T)Z,ZP,ZC 试分解R为3NF,解：a、首先将R分解成3NF，且具有函数依赖保持性。,求F的最小覆盖 F中所有依赖的右边都是单属性 去掉F 中冗余FD：SP,SC,ST,故 S(P,C,T)。合并性又(P,C,T)Z S Z 传递性，S Z 由其它FD 导出，多余,去掉;得。,用算法1求:=(S,SN,P,C,T),(P,C,T,Z),(Z,P,C)b.求的无损分解R的关键字为S，根据定理设为：=(S,SN,P,C,T),(P,C,T,Z),(Z,P,C),(S)要考虑消除多余的关系模式:(S)和(Z,P,C)。(S S,SN,P,C,T)Z,P,C P,C,T,Z)最后的分解结果：=(S,SN,P,C,T),(P,C,T,Z),注：若在分解=R1,R2,Rm,中有冗余：即中的某一模式包含在另一 个模式之中，则应去掉冗余的关系模式。分解后 不是唯一的：因为删去关系模式不同，另求F 最小覆盖不同。,六、模式设计的原则,模式分解=R1,R2,Rk的特性:（1）Ri应有某种范式性质（1NFBCNF）（2）具有无损联接性：r=（3）具有保持依赖性:F=（4）具有最小性，模式最小，模式中属性总数应最小。,K,i=1