《数据库原理与技术第六章.ppt》由会员分享，可在线阅读，更多相关《数据库原理与技术第六章.ppt（91页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 关系数据理论关系数据理论问题v如何才能构造一个良好的关系模式？要回答这个如何才能构造一个良好的关系模式？要回答这个问题就必须要解决以下问题：问题就必须要解决以下问题：什么是不好的关系模式，一个不好的关系模式存在哪些弊病？区分一个关系模式设计的优劣程度的标准是什么？如何将一个不好的关系模式转换为一个好的关系模式？v关系数据理论借助于数学工具规定了一套关系数关系数据理论借助于数学工具规定了一套关系数据库设计的理论和方法。是数据库逻辑设计的有据库设计的理论和方法。是数据库逻辑设计的有力工具。力工具。关系数据库设计中存在的问题(I)v有关学生的关系模式有关学生的关系模式S(SNO , S
2、NAME , DEPT , HEAD , CNO , G)v主键？主键？SNOSNAMEDEPTHEADCNOGS01杨明杨明D01李一李一C0190S02李婉李婉D01李一李一C0187S01杨明杨明D01李一李一C0292S03李婉李婉D02王二王二C0195S04安然安然D02王二王二C0278S02李婉李婉D01李一李一C0381S05乐天乐天D03赵三赵三C0182关系数据库设计中存在的问题()v问题问题插入异常：如果一个系刚成立没有学生，或者有了学生但尚未安排课程，那么就无法将这个系及其负责人的信息插入数据库。删除异常：如果某个系的全部学生都毕业了，则删除该系学生及其选修课程的同时
3、，把这个系及其负责人的信息也丢掉了。数据冗余和更新异常：学生及其所选课程很多，而系主任只有一个，但其却要和学生及其所选课程出现的次数一样多。此外，如果某个系要更换系主任，就必须修改这个系学生所选课程的每个元组，修改其中的系主任信息。若有疏忽，就会造成数据的不一致，从而造成更新异常。关系数据库设计中存在的问题()v原因：把多个实体型用一个关系模式表示原因：把多个实体型用一个关系模式表示v解决之道：分解解决之道：分解SNOSNAMEDEPTS01杨明杨明D01S02李婉李婉D01S03李婉李婉D02S04安然安然D02S05乐天乐天D03DEPTHEADD01李一李一D02王二王二D03赵三赵三S
4、NOCNOGS01C0190S02C0187S01C0292S03C0195S04C0278S02C0381S05C0182函数依赖v一个实体型的诸属性之间具有内在的联系，通过一个实体型的诸属性之间具有内在的联系，通过对这些联系的分析，我们可以做到一个关系模式对这些联系的分析，我们可以做到一个关系模式只表示一个实体型的信息，从而消除上述问题。只表示一个实体型的信息，从而消除上述问题。在关系模型中，我们利用数据依赖来描述这些属在关系模型中，我们利用数据依赖来描述这些属性间的联系。性间的联系。v数据依赖是通过关系中属性间值的相等与否体现数据依赖是通过关系中属性间值的相等与否体现出来的数据间的相互关
5、系，它是现实世界属性间出来的数据间的相互关系，它是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的相互联系的抽象，是数据内在的性质，是语义的体现。其中最重要的是函数依赖。体现。其中最重要的是函数依赖。函数依赖v设有以下关系模式设有以下关系模式U=Sno, Sname, Dept, Head, Cno, Gv现实世界中的语义现实世界中的语义一个系有若干学生，但一个学生只属于一个系一个系只有一个（正职）负责人一个学生可以选修多门课程，每门课程有若干学生选修每个学生选修每门课程有一个成绩。北京航空航天大学软件开发环境重点实验室函数依赖SELECT SNAME FROM S WHERE SNO
6、=S01SELECT SNAME FROM S WHERE SNO=S02SNOSNAMEDEPTHEADCNOGS01杨明杨明D01李一李一C0190S02李婉李婉D01李一李一C0187S01杨明杨明D01李一李一C0292S03李婉李婉D02王二王二C0195S04安然安然D02王二王二C0278S02李婉李婉D01李一李一C0381S05乐天乐天D03赵三赵三C0182SELECT SNO FROM SWHERE SNAME = 李婉函数依赖v函数依赖极为普遍地存在于现实生活中。考察关函数依赖极为普遍地存在于现实生活中。考察关系模式系模式S(SNO , SNAME , DEPT , H
7、EAD , CNO , G)，由于一个，由于一个SNO只对应一个学生，而只对应一个学生，而一个学生只能在一个系中学习。因而当一个学生只能在一个系中学习。因而当SNO的值的值确定后，确定后，SNAME和和DEPT也被唯一地确定了。也被唯一地确定了。就像自变量就像自变量x确定后，相应的确定后，相应的f(x)也被确定了一也被确定了一样。我们说样。我们说SNO函数决定（函数决定（SNAME，DEPT），），而（而（SNAME，DEPT）函数依赖于）函数依赖于SNO。函数依赖v定义定义函数依赖：设R(U)是属性集U上的关系模式，X , Y 是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在
8、两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数决定Y，或Y函数依赖于X，记作XY。如SNO SNAME， （SNO，CNO） GSELECT SNO, COUNT(DISTINCT SNAME)FROM SGROUP BY SNO函数依赖v函数依赖是不随时间而变的。若关系模式函数依赖是不随时间而变的。若关系模式R具具有函数依赖有函数依赖XY，那么，那么虽然关系模式虽然关系模式R的关系的关系实例实例r在在X，Y上的取值各不相同，并且随时间上的取值各不相同，并且随时间而变化，而变化， 但但X，Y在任一特定时刻都保持函数在任一特定时刻都保持函数依赖依赖XY 。v函数依赖不是指关系模式函
9、数依赖不是指关系模式R的某个或某些关系的某个或某些关系满足的约束条件，而是指满足的约束条件，而是指R的一切关系均要满的一切关系均要满足的约束条件。足的约束条件。v函数依赖是语义范畴的概念，它反映了一种语函数依赖是语义范畴的概念，它反映了一种语义完整性约束，我们只能根据语义来确定一个义完整性约束，我们只能根据语义来确定一个函数依赖。函数依赖。关系数据库设计中存在的问题(I)vGSNO? GSNAME?vSNOSNAME?SNOSNAMEDEPTHEADCNOGS01杨明杨明D01李一李一C0190S02李婉李婉D01李一李一C0187S01杨明杨明D01李一李一C0292S03李婉李婉D02王二
10、王二C0195S04安然安然D02王二王二C0278S02李婉李婉D01李一李一C0381S05乐天乐天D03赵三赵三C0182函数依赖v函数依赖于属性间的联系类型有关。函数依赖于属性间的联系类型有关。当X、Y之间是“1对1”联系时，则存在函数依赖XY和Y X。如：学号和身份证号当X、Y之间是“多对1”联系时，则存在函数依赖XY。如：SNO和DEPT当X、Y之间是“多对多”联系时，则不存在函数依赖。如：SNO和CNO函数依赖平凡函数依赖：如果X Y，但YX，则称其为非平凡的函数依赖，否则称为平凡的函数依赖。如（SNO，SNAME） SNAME是平凡的函数依赖完全函数依赖：在R(U)中，如果XY
11、，且对于X的任何真子集X ，都有XY ，则称Y对X完全函数依赖，记作X Y ，否则称为Y对X部分函数依赖，记作X Y。 （SNO，CNO） G， （SNO，CNO） SNAME函数依赖传递函数依赖：在R(U)中，如果XY，（ YX ）Y Z，且Y X， ZY则称Z对X传递函数依赖。SNO DEPT，DEPT HEAD函数依赖v检验：检验：AC？CA？ABD？ABCDa1b1c1d1a1b2c1d2a2b2c2d2a2b3c2d3a3b3c2d4码v定义定义候选码：设K为R的属性或属性组合， 若K U ，则称K为R的一个候选码。若候选码多于一个，则选定其中一个作为主码。超码：设K为R的属性或属性
12、组，若K U，则称K为R的超码。码主属性：包含在任何一个候选码中的属性，称作主属性。非主属性：不包含在任何一个候选码中的属性，称作非主属性。全码：关系模式的码由整个属性组构成。如（P，W，A）例子关系模式S(SNO , SNAME , DEPT , HEAD , CNO , G)主码：（SNO，CNO）函数依赖：（SNO，CNO） GSNOSNAME，（SNO，CNO） SNAMESNO DEPT，（SNO，CNO） DEPTSNOHEAD，（SNO，CNO） HEAD范式v定义定义范式是对关系的不同数据依赖程度的要求。如果一个关系满足某个范式所指定的约束集，则称它属于某个特定的范式。1NF2
13、NF3NF4NFBCNF5NF规范化v一个低一级范式的关系模式，通过模式分解可以一个低一级范式的关系模式，通过模式分解可以转换为若干个高级范式的关系模式的集合，这一转换为若干个高级范式的关系模式的集合，这一过程称作规范化。过程称作规范化。1NFv定义定义关系中每一分量必须是原子的，不可再分。即不能以集合、序列等作为属性值。SNOCNOS1C1，C2，C3SNOCNOS1C1S1C2S1C3不满足不满足1NF的关系模式的关系模式满足满足1NF的关系模式的关系模式2NF()v定义定义若R1NF，且每个非主属性完全依赖于码，则称R2NF将1NF的关系模式规范化为2NF的关系模式，其方法是消除1NF的
14、关系模式中非主属性对码的部分依赖。思考：如果关系R的全体属性都是R的主属性，或者R的所有候选码都只含一个属性，那么，R是否属于第二范式？2NF(II)关系模式S(SNO, SNAME , DEPT , HEAD , CNO , G)v不良特性不良特性插入异常：如果学生没有选课，关于他的个人信息及所在系的信息就无法插入。删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了。数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复更新异常：如果学生转系，若他选修了k门课，则需要修改k次。2NF(III)v原因：原因：S 2NF，因为，因为（SNO，CNO） GSNO
15、SNAME，（SNO，CNO） SNAMESNO DEPT，（SNO，CNO） DEPTSNOHEAD， （SNO，CNO） HEADv规范化规范化将S分解为：S_SD(SNO, SNAME, DEPT, HEAD) 2NFSC( , CNO , G)2NF SNO3NF（I）S_SD(SNO, SNAME, DEPT, HEAD)v不良特性不良特性插入异常：如果系中没有学生，则有关系的信息就无法插入。删除异常：如果学生全部毕业了，则在删除学生信息的同时有关系的信息也随之删除了。更新异常：如果学生转系，不但要修改DEPT，还要修改HEAD，如果换系主任，则该系每个学生元组都要做相应修改。数据冗
16、余：每个学生都存储了所在系的系主任的信息。3NF(II)v定义定义关系模式R中，若不存在这样的码X，属性组Y及非主属性Z(Z Y)，使得下式成立，XY , YZ , YX则称R3NF。将2NF的关系模式规范化为3NF的关系模式，其方法是消除2NF的关系模式中非主属性对码的传递依赖。3NF(III)v原因：原因： S_SD 3NF，因为，因为SNOSNAME, SNODEPTSNO HEAD原因：SNODEPT，DEPTHEADv规范化规范化将S分解为：DEPT(DEPT , HEAD)STUDENT( , SNAME , SNO)DEPTBCNF(I)v示例示例STJ(S, T, J)，S表示
17、学生，T表示教师，J表示课程。每位老师只教授一门课,每门课由若干教师教，某一学生选定某门课就确定了一个固定的教师，因此具有以下函数依赖： TJ，（S，J）T（S，T），（S，J）为候选码。BCNF()v不良特性不良特性插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入。删除异常：删除学生选课信息，会删除掉老师的任课信息。更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动。数据冗余：每位学生都存储了有关老师所教授的课程的信息。BCNF(III)v定义定义若关系模式R1NF，若XY，且YX时，X必含有码，则R BCNF。由BCNF的定义可以看到
18、，每个BCNF的关系模式都具有如下三个性质：所有非主属性都完全函数依赖于每个候选码。所有主属性都完全函数依赖于每个不包含它的候选码。没有任何属性完全函数依赖于非码的任何一组属性。BCNF(IV)v原因：原因：存在主属性对码的不良依赖，STJ BCNF，因为T J，而T不含有码。v改造改造将S分解为（S，T），（T，J）。v思考思考(S , J , P)，表示学生选修课程的名次，有函数依赖(S，J) P， (J，P) S，它属于BCNF吗？多值依赖()v关系模式TEACH（C#，P#，B#），一门课程由多个教师任教，一门课程使用相同的一套参考书。它的码是（C#，P#，B#），所以属于BCNF。C
19、#P#B#物理物理张明张明普通物理学普通物理学物理物理张明张明光学原理光学原理物理物理张平张平普通物理学普通物理学物理物理张平张平光学原理光学原理化学化学张明张明无机化学无机化学化学化学张明张明有机化学有机化学化学化学王微王微无机化学无机化学化学化学王微王微有机化学有机化学C#P#B#物理物理张明张明,张平张平普通物理学普通物理学,光学原理光学原理化学化学张明张明,王微王微无机化学无机化学,有机化学有机化学多值依赖()v不良特性不良特性插入异常：当某门课程增加一名教师时，该门课程有多少本参考书就必须插入多少个元组；同样当某门课程需要增加一本参考书时，它有多少个教师就必须插入多少个元组。删除异常
20、：当删除一门课程的某个教师或者某本参考书时，需要删除多个元组。数据冗余：同一门课的教师与参考书的信息被反复存储多次。更新异常：当一门课程的教师或参考书作出改变时，需要修改多个元组。多值依赖(III)v定义定义设R(U)是属性集U上的一个关系模式，X、Y、Z是U的子集，并且Z = U X Y，关系模式R(U)中多值依赖X Y成立，当且仅当对R(U)的任一关系r，给定的一对（x，z）值有一组Y的值，这组值仅仅决定于x值而与z值无关。如在关系模式TEACH中，对(物理 , 普通物理学)有一组P#值(张明, 张平)，对(物理, 光学原理)也有一组P#值(张明, 张平)，这组值仅取决于C#的取值，而与B
21、#的取值无关。因此，P#多值依赖于C#，记作C# P#，同样有C# B#。多值依赖()形式化：在R(U)的任一关系r中，如果存在元组t，s使得tx=sx，那么就必然存在元组w，vr，（w，v可以与s，t相同），使得：wX = sX = vX = tXwY = tY， vY = sYwZ = sZ， vZ = tZ则称Y多值依赖与X，记作X Y。 若X Y，而Z，则称X Y为平凡的多值依赖。多值依赖()v性质性质多值依赖具有对称性，即若XY，则XZ，其中Z=UXY。函数依赖是多值依赖的特例，即若XY，则XY。若XY， XZ，则XYZ若XY， XZ，则XYZ若XY， XZ，则XYZ， X ZY若X
22、Y， YZ，则X Z Y多值依赖 Vs 函数依赖()v函数依赖有效性范围函数依赖有效性范围XY的有效性仅决定于X、Y属性集上的值，它在任何属性集W（XY W U）上都成立。若XY在R(U)上成立，则对于任何Y Y，均有XY 成立。多值依赖 Vs 函数依赖()v多值依赖有效性范围多值依赖有效性范围XY的有效性与属性集范围有关。 XY在U上成立 XY在属性集W（XY W U）上成立。反之则不然。若在R(U)上，XY在属性集W(XY W U)上成立，则称XY为R(U) 的嵌入式多值依赖。若XY在R(U)上成立，则不能断言对于Y Y，是否有XY 成立。4NFv定义定义关系模式R 1NF，如果对于R到每
23、个非平凡的多值依赖XY（YX）是，X都含有码，则称R4NF。v4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为根据定义，对于每一个非平凡的多值依赖XY，X都含有候选码，于是就有XY，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。4NF如关系模式CPB，C#P#，C#B#，码为(C#, P#, B#)，所以CPB4NF。如果一门课Ci有m个教师，n本参考书，则关系中分量为Ci的元组共有mn个，数据冗余非常大。v改造改造将CPB分解为CP（C#，P#），CB（C#，B#）。数据依赖的公理系统v定义定义对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖X
24、Y都成立，则称F逻辑蕴涵XY。vArmstrong公理公理X，Y，Z是属性集，自反律。若YXU， 则XY为F所蕴含。增广律。若XY为F所蕴含，且ZU，则XZ YZ为F所蕴含。传递律。若XY及YZ为F所蕴含，则XZ为F所蕴含。数据依赖的公理系统v在关系模式在关系模式R中，为中，为F所逻辑蕴涵的所逻辑蕴涵的函数依赖的全体称作函数依赖的全体称作F的闭包，记作的闭包，记作F+。例：F=XY，YZ，则XZ F+。vArmstrong公理的有效性及完备性公理的有效性及完备性有效性：由F出发根据Armstrong公理推导出来的函数依赖一定在F+中。完备性： F+中的每一个函数依赖都可以由F出发根据Armst
25、rong公理从F中导出。数据依赖的公理系统v关于关于Armstrong公理有效性的证明公理有效性的证明设YXU，R上的任一关系r的两个元组t，s 若tX=sX，由YX，有tY=sY，所以XY成立，自反律得证。设XY为F所蕴含，且ZU。设R上的任一关系r的两个元组t，s 若tXZ=sXZ，则有tX=sX 和tZ=sZ， 由XY，有tY=sY，所以tYZ=sYZ，因此XZ YZ为F所蕴含，增广律得证。数据依赖的公理系统设XY及YZ为F所蕴含。设R上的任一关系r的两个元组t，s 。 若tX=sX，且由XY，有tY=sY 再由YZ，有tZ=sZ，所以XZ为F所蕴含，传递律得证。v由由Armstrong
26、公理导出的推理规则公理导出的推理规则合并律。若X Y，X Z，则X YZ。分解律。若X YZ ，则X Y，X Z 。伪传递律。若X Y，WY Z，则XW Z数据依赖的公理系统v示例示例R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？CG HI？AG I？数据依赖的公理系统问题：有没有一般性的算法判定问题：有没有一般性的算法判定XY是否能由是否能由F根据根据Armstrong公理导出？公理导出？v属性集的闭包属性集的闭包设F为属性集U上的一组函数依赖，X U， = A | XA能由F根据Armstrong公理导出称 为属性集X关于
27、函数依赖集F的闭包。 数据依赖的公理系统引理一： XA1 A2 Ak成立 XAi成立(i=1, 2, ,k)引理二： 设F为属性集U上的一组函数依赖，X，Y U， XY能由F根据Armstrong公理导出的充分必要条件是Y 数据依赖的公理系统v算法（求属性集的闭包）算法（求属性集的闭包）Input：X，FOutput：步骤：(1)令X(0)X，i=0(2)求B，B=A|(V)(W)(VWV X(i) AW)(3) X(i+1)BX (i)(4)判断X(i+1)X (i) ？(5)若相等，或X(i+1)U，则X(i+1)就是 ，算法终止。(6)若否，则i=i+1，返回第二步。数据依赖的公理系统v
28、示例示例R, U = (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,计算 。所用依赖 ABCABC BDABCD CEABCDE= ABCDE数据依赖的公理系统vArmstrong公理完备性的证明公理完备性的证明证明：用反证法，假定存在函数依赖XY被F逻辑蕴涵，但XY不能用Armstrong公理从F中导出。(1) 若VWF，且V ，则W 证：因为V ，所以有XV；于是X W成立，所以W 。数据依赖的公理系统（2）构造一张二维表r，它由下列两个元组构成，可以证明r必是R(U, F)的一个关系，即F中的全部函数依赖在r上成立。r（ U ）t 111 00 0
29、s 111 111若r不是R(U, F)的关系，则必由于F中有函数依赖VW在r上不成立所致。由r的构成可知，V必定是 的子集，而W不是 的子集，可是由第（1）步可知，W 矛盾，所以r必是R(U, F)的一个关系。数据依赖的公理系统（3）若XY不能由F从Armstrong公理导出，则Y不是 的子集，因此必有Y的子集Y满足YU ，则XY在r中不成立，即XY必不为R(U, F)所蕴含。数据依赖的公理系统v定义定义函数依赖集的等价性函数依赖集F，G，若F+= G+，则称F与G等价。F+ = G+ F G+，G F+最小依赖集（最小覆盖）满足下列条件的函数依赖集F称为最小覆盖，记作Fm：F中任一函数依赖
30、的右部仅含有一个属性。F中不存在这样的函数依赖X A，使得F与F X A等价。F中不存在这样的函数依赖X A，在X中有真子集Z，使得F与F X A Z A等价。数据依赖的公理系统v算法算法求解函数依赖集求解函数依赖集F的最小覆盖的最小覆盖Fm逐个检查F中各函数依赖FDi ：XY，若Y=A1 A2 Ak ，k2，则用诸XAi 代替Y。逐个检查F中各函数依赖XA，令G = FXA，若A ，则从F中去掉该函数依赖。逐个检查F中各函数依赖XA，设X = B1Bm，逐个考查Bi，若A ，则以（X Bi）取代X。数据依赖的公理系统v示例示例F = AB，BA，AC，BC，C A，求Fm。Fm = AB，C
31、A，BC或者Fm = AB，BA，AC，C A模式分解中的问题v实例实例设R是一个关系模式，R的属性集合U=SNO，DEPT，HEAD），R的函数依赖集合F=SNODEPT，DEPTHEAD，R的候选码为SNO，由于R中存在非主属性HEAD对码的传递函数依赖，因此存在异常，需要进行模式分解，其方式可以有：分解一：（SNO），（DEPT） ，（HEAD）分解二：（SNO，DEPT），（SNO，HEAD）分解三：（SNO，DEPT），（DEPT，HEAD） 模式分解中的问题v分解一所形成的三个关系无法通过自然连接恢复分解一所形成的三个关系无法通过自然连接恢复成原来的关系，实际上是它们三个的笛卡尔积
32、，成原来的关系，实际上是它们三个的笛卡尔积，元组增加了，信息却丢失了。元组增加了，信息却丢失了。SNODEPTHEADS1D1张红张红S2D1张红张红S3D2李微李微S4D3王力王力SNOS1S2S3S4DEPTD1D2D3HEAD张红张红李微李微王力王力模式分解中的问题v分解二能够分解二能够 通过自然连接恢复到原来的关系，但通过自然连接恢复到原来的关系，但仍然具有插入和删除等异常。原因在于丢失了函仍然具有插入和删除等异常。原因在于丢失了函数依赖数依赖DEPTHEAD。SNODEPTHEADS1D1张红张红S2D1张红张红S3D2李微李微S4D3王力王力SNODEPTS1D1S2D1S3D2S
33、4D3SNOHEADS1张红张红S2张红张红S3李微李微S4王力王力模式分解中的问题v分解三既可以通过自然连接恢复到原来的关系，分解三既可以通过自然连接恢复到原来的关系，同时也保持了原关系的函数依赖，消除了原关系同时也保持了原关系的函数依赖，消除了原关系的异常。的异常。SNODEPTHEADS1D1张红张红S2D1张红张红S3D2李微李微S4D3王力王力SNODEPTS1D1S2D1S3D2S4D3DEPTHEADD1张红张红D2李微李微D3王力王力关系模式的分解算法v分解的目标分解的目标无损连接分解保持函数依赖达到更高级范式关系模式的分解算法v模式分解模式分解函数依赖集合Fi = XY |
34、XYF+ XY Ui称为F在Ui上的投影关系模式R的一个分解是指 = R1 , R2, , Rn其中U = Ui ，并且没有Ui Uj ，1i，j n， Fi是F在Ui上的投影。设 = R1 , R2, , Rn是R(U，F)的一个分解，r是R(U，F)的一个关系，定义m (r) = Ri（r），即m （r）是r在中各关系模式投影上的连接。这里Ri（r）=t.Ui|tr关系模式的分解算法一般定义关系模式R ，U = Ui ， = R1 , R2, , Rn是R的一个分解，r是R的一个关系。定义m(r) = Ri(r) ,若对于R的任一个关系r，都有r = m(r)，则称是R的一个无损连接分解。
35、关系模式的分解算法算法：（判别一个分解的无损连接性）U=A1, A2, , An，FFD1，FD2，FD 不妨设F是一个最小依赖集，记FDi为Xi Aj = R1 , R2, , Rk建立一个n列k行的矩阵。每一列对应一个属性，每一行对应于分解中的一个关系模式。若属性Aj 属于Ui ，则在j列i行交叉处填上aj ，否则填上bij 。Cij | 若Aj Ui , Cij = aj , 否则Cij = bij关系模式的分解算法对每一个FDi做下列操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中j列的元素，若其中有aj，则全部改为aj；否则全部改为bmj；m是这些行的行号最小值。注意：如
36、果某个bij被修改，则该列中所有的bij都必须做同样的修改 如果在某次更改之后，有一行成为a1, a2 , , an 。则算法终止， 为无损分解，否则为有损分解。 关系模式的分解算法3. 比较扫描前后，表有无变化。如有变化，则返回第二步，否则算法终止。 关系模式的分解算法示例：U=A,B,C,D,E, F=ABC, CD,DE =(A, B, C), (C, D), (D, E)ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEA
37、BCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DE关系模式的分解算法vU=A,B,C,D,E, vF=AC, BC, CD, DEC, CEAv =R1(A, D), R2(A, B), R3(B, E), R4 (C, D, E), R5(A, E)关系模式的分解算法ABCDER1(A, D)a1b12b13a4b15R2(A, B)a1a2b23b24b25R3(B, E)b31a2b33b34a5R4(C, D, E) b41b42a3a4a5R5(A
38、, E)a1b52b53b54a5关系模式的分解算法vACABCDER1(A, D)a1b12b13a4b15R2(A, B)a1a2b13b24b25R3(B, E)b31a2b33b34a5R4(C, D, E)b41b42a3a4a5R5(A, E)a1b52b13b54a5关系模式的分解算法v BCABCDER1(A, D)a1b12b13a4b15R2(A, B)a1a2b13b24b25R3(B, E)b31a2b13b34a5R4(C, D, E)b41b42a3a4a5R5(A, E)a1b52b13b54a5关系模式的分解算法vCDABCDER1(A, D)a1b12b13a
39、4b15R2(A, B)a1a2b13a4b25R3(B, E)b31a2b13a4a5R4(C, D, E) b41b42a3a4a5R5(A, E)a1b52b13a4a5关系模式的分解算法vDECABCDER1(A, D)a1b12a3a4b15R2(A, B)a1a2a3a4b25R3(B, E)b31a2a3a4a5R4(C, D, E) b41b42a3a4a5R5(A, E)a1b52a3a4a5关系模式的分解算法vCEAABCDER1(A, D)a1b12a3a4b15R2(A, B)a1a2a3a4b25R3(B, E)a1a2a3a4a5R4(C, D, E) a1b42a
40、3a4a5R5(A, E)a1b52a3a4a5关系模式的分解算法定理若U1U2 U1(或U2)，则r =U1(r) U2(r) 。 关系模式的分解算法v保持函数依赖的分解保持函数依赖的分解定义若F+ = ( Fi)+， 则称R的分解 = R1 , , Rn保持函数依赖。如表（职工，级别，工资）的分解，分解一：（职工，工资），（工资，级别）丢失函数依赖，职工级别分解二：（职工，级别），（工资，级别）保持函数依赖。关系模式的分解算法v算法：（达到算法：（达到3NF且保持函数依赖的分解）且保持函数依赖的分解）对R 中的函数依赖集F进行“极小化处理”（处理后得到的依赖集仍记为F）。找出不在F中出现的
41、属性，将它们构成一个关系模式，并从U中去掉它们(剩余属性仍记为U)。若有XA F ，且XA=U，则 =R，算法终止。关系模式的分解算法否则，对F按具有相同左部的原则进行分组（设为k组），每一组函数依赖Fi所涉及的全部属性为Ui。若Ui Uj （ij） ，就去掉Ui 。由于经过了步骤2，故U = Ui ，于是 = R1 , , Rk是R的一个保持函数依赖的分解，并且每个Ri 3NF。关系模式的分解算法示例U=SNO，DEPT，HEAD，CNO，GF=SNODEPT，SNOHEAD，DEPTHEAD，(SNO,CNO)GFC=SNODEPT，DEPTHEAD ，(SNO,CNO)G分组(SNO，D
42、EPT)，SNODEPT(DEPT，HEAD)，DEPTHEAD(SNO，CNO，G)， (SNO,CNO)G关系模式的分解算法示例：R（ABC；AC，BC）按保持无损连接分解码为AB，分解为AC；AC，AB。丢失了函数依赖BC。按保持函数依赖分解进行分组，AC；AC，BC；BC。分解是有损的。ABC111211221AC1121BC1121ABC111121211221关系模式的分解算法算法：（达到3NF且同时保持无损连接与函数依赖的分解）设X为R的码，设 = R1 , , Rk是R的一个保持函数依赖的3NF分解。令 = R 若有某个Ui，X Ui，则将R 从去掉。 = R 即为所求的解。关
43、系模式的分解算法示例：求R（ABC；AC，BC）的保持无损连接和函数依赖的3NF分解。按保持函数依赖分解进行分组， =AC；AC，BC；BC。键为AB = AB最后的分解为：AC；AC，BC；BC，AB关系模式的分解算法v算法：（达到算法：（达到BCNF无损连接分解算法）无损连接分解算法）给定关系模式R ，令 = R检查中各关系模式是否属于BCNF，若是，则算法终止。 设 中Ri不属于BCNF，则存在函数依赖XA ，且X不是Ri的码，则XA是Ri的真子集，将Ri分解为=S1，S2，其中US1 = XA， US2 = Ui A以代替Ri ，返回到关系模式的分解算法示例：U=SNO，DEPT，HE
44、AD，CNO，GFc=SNODEPT，DEPTHEAD，(SNO,CNO)GU1=DEPT，HEAD , F1=DEPTHEAD U2=SNO, DEPT, CNO, G, F2=SNODEPT, (SNO,CNO)GU1 = DEPT，HEAD, F1=DEPTHEAD U2 = SNO, DEPT, F2=SNODEPT U3 = SNO, CNO, G, F3 = (SNO,CNO)G例子v设有关系设有关系R（U, F）U=A, B, C, D, E, F, GF=ED, CB, CEAF, BA, CABv求：求：R的候选码判断R所属的范式如果R不属于第三范式，将R规范化到第三范式，并
45、保持函数依赖和无损连接的分解例子求R的候选码vL: E, CvR: A, D, FvLR: BvN: Gv首先查看首先查看 v因此，因此，CEG是是R唯一的候选码唯一的候选码例子判断R属于第几范式vR的主属性：的主属性：C, E, GvR的非主属性：的非主属性：A, B, D, Fv非主属性与候选码的关系：非主属性与候选码的关系：ED, 故CEGD为部分函数依赖v故故R属于第一范式属于第一范式例子分解为第三范式v求最小函数依赖集求最小函数依赖集v第一步：将函数依赖的右部分解为单属性第一步：将函数依赖的右部分解为单属性vFmED, CB, CEA, CEF, BA, CA, CBv第二步：去掉多
46、余的函数依赖第二步：去掉多余的函数依赖vFmED, CB, CEF, BAv第三步：检查是否存在部分函数依赖第三步：检查是否存在部分函数依赖例子分解为第三范式v按相同左部分组，得到以下按相同左部分组，得到以下4个属性组：个属性组：R1(E, D)，F=EDR2(C, B) ，F=CBR3(C, E, F) ，F=CEFR4(B, A) ，F=BAv这些属性组之间没有相互包含的情况，因此，我这些属性组之间没有相互包含的情况，因此，我们得到了保持函数依赖且达到第三范式的分解结们得到了保持函数依赖且达到第三范式的分解结果果例子分解为第三范式v判断上述结果是否是无损连接分解判断上述结果是否是无损连接分解v因为上述分解后的关系模式中没有哪一个包含了因为上述分解后的关系模式中没有哪一个包含了原关系模式原关系模式R的候选码的候选码CEG，所以上述分解结果，所以上述分解结果是有损的。是有损的。v为此，在上述分解结果中加入一个全由候选码中为此，在上述分解结果中加入一个全由候选码中属性构成的关系模式属性构成的关系模式R5(C, E, G) ，F=例子分解为第三范式v最后的分解结果为：最后的分解结果为：R1(E, D)，F=EDR2(C, B) ，F=CBR3(C, E, F) ，F=CEFR4(B, A) ，F=BAR5(C, E, G) ，F=
