数据库原理与应用(第二版)Chapter4课件

《数据库原理与应用(第二版)Chapter4课件》由会员分享，可在线阅读，更多相关《数据库原理与应用(第二版)Chapter4课件（52页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章关系数据理论关系数据理论4.1 4.1 关系数据库模式的设计问题关系数据库模式的设计问题1引言引言 数据库设计的一个最基本的问题是如何建立一数据库设计的一个最基本的问题是如何建立一个好的数据库模式，即给出一组数据，如何个好的数据库模式，即给出一组数据，如何构造一个适合于它们的数据模式，使数据库构造一个适合于它们的数据模式，使数据库系统有较好的性能。系统有较好的性能。 2 2关系模式的存储异常问题关系模式的存储异常问题 1)1)数据冗余量大数据冗余量大 2)2)数据修改量大数据修改量大 3)3)插入异常插入异常 4)4)删除异常删除异常 3 3 冗余和数据依赖冗余和数据依赖数据依数据

2、依赖是指数据之是指数据之间存在的各种存在的各种联系，系，譬如譬如键就是一种依就是一种依赖。数据冗余的。数据冗余的产生和数据依生和数据依赖有着密切的有着密切的联系。系。例如关系例如关系S S中，为什么学生中，为什么学生S2S2的班级会重的班级会重复出现？就是因为复出现？就是因为S S和和CLSCLS之间存在之间存在依赖关系，即每个学生只属于一个班依赖关系，即每个学生只属于一个班级，这种依赖称为函数依赖。这个依级，这种依赖称为函数依赖。这个依赖势必造成关系出现冗余现象。赖势必造成关系出现冗余现象。4.2 4.2 关系模式的函数依赖关系模式的函数依赖1.1.函数依函数依赖的定的定义定定义1 1：设有

3、有关关系系模模式式R R（），是是R R的的属属性性的的集集合合，X X、Y Y ，对于于R R的的任任意意关关系系实例例r r，r r中中的的任任意意两两个个元元组t t和和s s，如如果果tX=sXtX=sX，则tY=sYtY=sY，则称称Y Y函函数数依依赖于于X X，或或称称X X函函数数地地决决定定Y Y，记作作XYXY。 定定义2 2：设R R是是一一个个具具有有属属性性集集合合的的关关系系模模式式，如如果果XY XY ，并并且且对于于X X的的任任何何一一个个真真子子集集Z Z，ZYZY都都不不成成立立，则称称Y Y完完全全函函数数依依赖于于X X，记作作：X X Y Y 。若若

4、XYXY，但但Y Y不不完完全全函函数数依依赖于于X X，则称称Y Y部分函数依部分函数依赖于于X X，记作：作：X YX Y。定定义义3 3：设设R R是是一一个个具具有有属属性性集集合合的的关关系系模模式式，X X，Y Y，Z Z是是的的子子集集，YXYX不不成成立立，Z ZX X、Z ZY Y和和Y YX X不不空空。如如果果XYXY，YZYZ则则称称Z Z传传递递函函数数依依赖赖于于X X，记作：记作：X ZX Z。例例如如对对于于关关系系：学学生生（学学号号，班班级级，班班主主任任），有有：学学号号班班级级，班班级级班班主任，则学号主任，则学号班主任，所以班主任，所以 学号学号 班主

5、任。班主任。 2. 键键 定定义义4 4 设设R R是是一一个个具具有有属属性性集集合合的的关关系系模模式式，K K是是的的子子集集。若若K K满满足足下下列列两两个条件，则称个条件，则称K K是是R R的一个候选键。的一个候选键。1)1)KK2)2)不存在不存在K K的真子集的真子集Z Z，使得使得ZZ。候候选键可可以以唯唯一一地地识别关关系系的的元元组。一一个个关关系系模模式式中中可可能能具具有有多多个个候候选键。我我们可以指定一个候可以指定一个候选键作作为主主键。 定定义义5 5 设设X X是是关关系系模模式式R R的的属属性性的的子子集集。如如果果X X是是另另一一关关系系模模式式的的

6、候候选选键键，则则称称X X是是R R的的外外部键。部键。例例如如，在在学学生生关关系系S S（S S，SNSN，CLSCLS，MONMON，C C，GRGR）中存在以下函数依赖：中存在以下函数依赖：1)1)S SSNSN，每个学生有唯一的一个学号；每个学生有唯一的一个学号；2)2)CLSMONCLSMON，每个班最多只有一个班主任；每个班最多只有一个班主任；3)3)S SCLSCLS，每个学生只属于一个班级；每个学生只属于一个班级；4)4)（S S，C C）GRGR，一一个个学学生生选修修一一门课程有一个成程有一个成绩等等级；可以看出（可以看出（S S，C C）是主是主键。 4.3 关系的规

7、范化关系的规范化 在在关关系系数数据据模模式式设计中中，为了了避避免免由由依依赖引引起起的的数数据据冗冗余余和和更更新新异异常常等等问题，必必须进行行关关系系模模式式的的合合理理分分解解，即即关关系模式的系模式的规范化。范化。 1. 1. 关系模式的范式关系模式的范式关系模式的设计原则：关系模式的设计原则：1)1)数据的冗余量尽量小；数据的冗余量尽量小；2)2)对关系进行插入、删除等操作，不要出问题对关系进行插入、删除等操作，不要出问题3)3)尽尽量量能能如如实地地反反映映现实世世界界的的实际情情况况，而而且又易懂。且又易懂。 关系数据库中的关系满足一定的要求。而把满关系数据库中的关系满足一定

8、的要求。而把满足不同程度要求的关系称为不同的范式。足不同程度要求的关系称为不同的范式。满足最低要求的关系叫第一范式，简称满足最低要求的关系叫第一范式，简称1NF1NF。在在第一范式中进一步满足一定要求的为第二范第一范式中进一步满足一定要求的为第二范式，简称式，简称2NF2NF，其余以此类推。其余以此类推。 关系规范化关系规范化: :就是一个低一级范式的关系模式通就是一个低一级范式的关系模式通过投影运算，转化为若干高一级范式的关系过投影运算，转化为若干高一级范式的关系模式的集合，这种过程就叫关系的规范化。模式的集合，这种过程就叫关系的规范化。 各范式之间的关系各范式之间的关系1NF1NF2NF2

9、NF3NF3NF4NF4NF5NF5NF(1)(1)第一范式（第一范式（1NF1NF） 设设R R是一个关系模式。如果是一个关系模式。如果R R的每一属性的值都的每一属性的值都是不可分离的原子值，即每个属性的值域是是不可分离的原子值，即每个属性的值域是单值域，则单值域，则R R是第一范式，记作是第一范式，记作R1NFR1NF。符合符合1NF1NF的工资关系的工资关系编编 号号姓姓 名名基本工资基本工资奖奖 金金1 12 210101515张三张三李四李四王五王五赵六赵六200200000028028000002602600000230230000030300000505000004545000

10、040400000(2) (2) 第二范式第二范式如果关系模式如果关系模式R1NFR1NF，且，且R R中每一非主属性完全中每一非主属性完全函数依赖于函数依赖于R R的键，则的键，则R R称为第二范式，记作称为第二范式，记作R2NFR2NF。 例如，例如，4.14.1节给出的学生关系节给出的学生关系S S中非主属性中非主属性CLSCLS、MONMON都不是完全函数依赖于主键（都不是完全函数依赖于主键（S S，C C），），而部分函数依赖于（而部分函数依赖于（S S，C C）。）。对对1NF1NF进行进行投影运算，将其分解为两个关系：投影运算，将其分解为两个关系： SSSSS S，SNSN，CL

11、SCLS，MONMON（S S）SCSCS S，C C，GRGR（S S），其其中中S S为为SSSS的的主主键键，（S S，C C）为）为SCSC的主键。的主键。这这样样，在在这这两两个个关关系系中中，非非主主属属性性对对主主键键都都是是完全函数依赖，所以关系完全函数依赖，所以关系SSSS和和SCSC都为都为2NF2NF。 (3) (3) 第三范式第三范式如果关系模式如果关系模式R R是是2NF2NF，且它的任何一个非且它的任何一个非主属性都不传递函数依赖于任何候选键，主属性都不传递函数依赖于任何候选键，则称则称R R为第三范式，记作为第三范式，记作R3NFR3NF。例如，例如，订单关系关系

12、（订单号，号，顾客名称，商客名称，商店店货号，定号，定购数量，交数量，交货日期）中的主日期）中的主键是是订单号，存在的函数依号，存在的函数依赖是：是：订单号号顾客名称；客名称；订单号号商品商品货号；号；订单号号定定购数量；数量；订单号号交交货日期，日期，不再有不再有别的函数依的函数依赖，此关系是，此关系是2NF2NF的，的，且所有非主属性且所有非主属性对主主键没有没有传递函数依函数依赖，所以是，所以是3NF3NF的。的。 (4) BC(4) BC范式（范式（BCNFBCNF） 如如果果关关系系模模式式R1NFR1NF，且且每每个个函函数数依依赖赖XYXY中中X X必为候选键，则必为候选键，则R

13、 R是是BCNFBCNF范式。范式。从从BCNFBCNF的的定定义义可可以以明明显显地地得得出出一一个个满满足足BCNFBCNF的的关系模式如下结论：关系模式如下结论：1)1)所有非主属性对键是完全函数依赖。所有非主属性对键是完全函数依赖。2)2)所有主属性对不包含它的键是完全函数依赖。所有主属性对不包含它的键是完全函数依赖。3)3)没有属性完全函数依赖于非键的任何属性组没有属性完全函数依赖于非键的任何属性组例例4-3 4-3 在在关关系系模模式式SJPSJP（S S，J J，P P）中中，S S是是学学号号，J J是是课课号号，P P为为名名次次。每每一一个个学学生生每每门门课课程程有有一一

14、定定的的名名次次，每每门门课课程程中中每每一一名名次次只只有有一一个个学学生生。由由这这些语义可得到下面的函数依赖：些语义可得到下面的函数依赖：（S S，J J） P P（J J，P P） S S 显然，（显然，（S S，J J）与（与（J J，P P）都是候都是候选键。这两个候选键各由两个属性组成，选键。这两个候选键各由两个属性组成，而且相交。这个关系模式中显然没有属而且相交。这个关系模式中显然没有属性对键传递或部分依赖，所以性对键传递或部分依赖，所以SJP SJP 3NF3NF。 例例4 44 4 关系模式关系模式SCTSCT（S S，C C，T T）中，中，S S表示学号，表示学号，C

15、C表示课程号，表示课程号，T T表示教师。每一教师只教一门课。表示教师。每一教师只教一门课。每门课由若干教师教授，某一学生选每门课由若干教师教授，某一学生选定某门课，就确定了一个固定的教师。定某门课，就确定了一个固定的教师。于是有如下的函数依于是有如下的函数依赖： 1)1)（S S，C C）TT2)2)（S S，T T）CC3)3) TCTC 显然，（然，（S S，C C）和（和（S S，T T）都是都是候候选键。SCTSCT是是3NF3NF，因因为没有任何非没有任何非主属性主属性对键的的传递或部分函数依或部分函数依赖。但但SCTSCT不是不是BCNFBCNF，因因为T T是决定因素，是决定因

16、素，而而T T不是候不是候选键。 S#C#TS#TC#2关系规范化方法与实例关系规范化方法与实例 关系模式规范化遵循以下原则：关系模式规范化遵循以下原则：1)关关系系模模式式进进行行无无损损连连接接分分解解。关关系系模模式式分分解解过过程程中中数数据据不不能能丢丢失失或或增增加加，必必须须把把全全部部关关系系模模式式中中的的所所有有数数据据无无损损地地分分解解到到各各个个子子关关系模式中，以保证数据的完整性。系模式中，以保证数据的完整性。2)合合理理选选择择规规范范化化程程度度。低低级级范范式式造造成成的的冗冗余余度度很很大大，既既浪浪费费了了存存储储空空间间，又又影影响响了了数数据据的的一一

17、致致性性，因因此此希希望望一一个个子子模模式式的的属属性性越越少少越越好好，即即取取高高级级范范式式；若若考考虑虑查查询询效效率率、低低级级范范式式比比高高级级范范式式好好，此此时时连连接接运运算算的的代代价价较较小小，这这是是一一对对矛矛盾盾，所所以以应应根根据据实实际际情情况况，合理选择规范化程度。合理选择规范化程度。3)正确性与可实现性原则。正确性与可实现性原则。4.4函数依赖的公理系统函数依赖的公理系统 定定义义6 6 设设R R是是一一个个具具有有属属性性集集合合的的关关系系模模式式，F F是是R R上上的的函函数数依依赖赖集集合合。如如果果对对于于R R的的任任意意一一个个使使F

18、F成成立立的的关关系系实实例例r r，函函数数依依赖赖XYXY都都成成立立，则则称称F F逻辑地蕴含逻辑地蕴含XYXY。ArmstrongArmstrong公公理理系系统统 设设R R是是一一个个关关系系模模式式，为为R R的的属属性性集集合合，F F为为上上的的一一组组函函数数依依赖赖的的集集合合。ArmstrongArmstrong公理系统包含如下三条推理规则：公理系统包含如下三条推理规则：（1 1）自反律自反律 若若Y Y X X ，则，则F F蕴含蕴含XYXY（2 2）增增广广律律 若若XYXY为为F F所所蕴蕴含含，且且Z Z ，则则XZYZXZYZ为为F F所蕴含。所蕴含。（3 3

19、）传递律传递律 若若XYXY和和YZYZ为为F F所蕴含，则所蕴含，则XZXZ为为F F所蕴含。所蕴含。 定理定理1 Armstrong1 Armstrong推理规则是正确的。推理规则是正确的。证明：证明：（1 1）设设Y Y X X U U。对对于于R R的的任任一一关关系系实实例例r r的的任任意意两两个个元元组组t t和和s s，若若tX=SX,tX=SX,由由于于Y Y X X，有有tY=sYtY=sY， 所以所以XYXY成立。自反律得证。成立。自反律得证。（2 2）设设XYXY为为F F所所逻逻辑辑蕴蕴含含，Z Z U U。对对于于R R的的任任一一 关关 系系 实实 例例 r r的

20、的 任任 意意 两两 个个 元元 组组 t t和和 s s， 若若tXZ=sXZ,tXZ=sXZ,则则有有tX=sXtX=sX，tZ=sZ tZ=sZ 。由由XYXY，tY=sYtY=sY。于于是是tYZ=sYZtYZ=sYZ从从而而XZYZXZYZ成立。增广律得证。成立。增广律得证。（3 3）设设XYXY及及YZYZ为为F F所逻辑蕴含，所逻辑蕴含，Z Z U U。对对于于R R的任一关系实例的任一关系实例r r的任意两个元组的任意两个元组t t和和s s，若若tX=sX,tX=sX,由于由于XYXY，有，有tY=sYtY=sY。又由又由YZYZ，有，有tZ=sZtZ=sZ。于是，于是，XZ

21、XZ成立。成立。 三条推理规则：三条推理规则：（1 1）合合并并规规则则 如如果果XYXY，XZXZ成成立立，则则XYZXYZ成立。成立。（2 2）伪伪传传递递规规则则 如如果果XYXY和和WYZWYZ成成立立，则则XWZXWZ成立。成立。（3 3）分分解解规规则则 如如果果XYXY和和Z Z Y Y成成立立，则则XZXZ成立。成立。 定定理理2 2 合合并并规规则则、伪伪传传递递规规则则和和分分解解规规则则是是正正确的。确的。证明：证明：（1 1）由由XYXY和和增增广广律律，XXYXXY。又又由由XZXZ和和增增广广律律，XYYZXYYZ。由由传传递递律律，XYZXYZ成成立立。合合并并规

22、则得证。规则得证。（2 2）由由XYXY和和增增广广律律，XWYWXWYW。又又由由YWZYWZ和和传递律，传递律，XWZXWZ。伪传递规则得证。伪传递规则得证。（3 3）由由Z Z Y Y和和自自反反律律，YZYZ。又又由由XYXY和和传递律，律，XZXZ。分解分解规则得得证。 引引理理1 1 XAXA1 1 A A2 2 A AK K成成立立的的充充分分必必要要条条件是对于件是对于1ik1ik，XAXA1 1成立。成立。引引理理1 1 设设F F是是属属性性集集U U上上的的一一组组函函数数依依赖赖的的集集合合。X X、Y Y U U，XYXY能能由由F F根根据据ArmstrongArm

23、strong公公理导出的充分必要条件是理导出的充分必要条件是Y Y X X+ +。定定义义7 7 设设R R是是一一个个具具有有属属性性集集合合U U的的关关系系模模式式，F F是是给给定定的的函函数数依依赖赖集集合合。由由F F逻逻辑辑蕴蕴含含的的所所有有函函数数依依赖赖称称为为F F的的闭闭包包，记记作作F F+ + 。定定义8 8 设R R是是一一个个具具有有属属性性集集合合U U的的关关系系模模式式，F F是是给定定的的函函数数依依赖集集合合。X X U U。X X+ +=A|XA=A|XA能能由由F F根根据据ArmstrongArmstrong公公理理导出出 称称为属性集属性集X

24、X关于函数依关于函数依赖集集F F的的闭包。包。 引引理理2 2 把把判判定定XYXY是是否否能能由由F F根根据据ArmstrongArmstrong公公理理导导出出的的问问题题转转化化为为求求出出X X+ +，判判定定Y Y是是否否为为X X+ +的子集合的问题。的子集合的问题。证明：证明：（1 1）充充分分性性 设设Y Y X X+ + ，并并设设Y=BY=B1 1 B B2 2 B BK K。根根据据属属性性闭闭包包的的定定义义可可知知，XBXB1 1，XBXBK K是是根根据据ArmstrongArmstrong公公理理从从F F导导出出的的。由由合合并并规规则则，有有XYXY。所所

25、以以当当Y Y X X+ +时，时，XYXY能根据能根据ArmstrongArmstrong公理从公理从F F导出。导出。（2 2）必必要要性性 设设XYXY能能根根据据ArmstrongArmstrong公公理理从从F F导导出出的的， Y=BY=B1 1 B B2 2 B BK K。根根据据分分解解规规则则有有XBXB1 1，XBXBK K，由由X X+ + 的的定定义义可可知知B BK KXX+ +（I=1,2, I=1,2, kk），所所以以Y Y X X+ +，证毕。证毕。算法算法1 1 计算计算X X+ +。输入：输入：X X，F F输出：输出：X X+ +方法：方法：1)1) X

26、 X（1 1）：）：= =空集合；空集合；X X（0 0）：）：=X=X；2)2) B= B= A|VWA|VW能能由由F F根根据据ArmstrongArmstrong公公理理导导出出，V V X(0)AWX(0)AW；3)3) X X（1 1）：）：=BX=BX（0 0）；）；4)4) IF IF X X（1 1）XX（0 0） THEN THEN X X（0 0）：=X=X（1 1）；）；GOTO 2GOTO 2；5)5) ELSE XELSE X+ +=X=X（1 1）；）；6)6) ENDIFENDIF。 例例4 466已已知知R R是是一一个个具具有有属属性性集集合合U U的的关关

27、系系模模式式，F F是是给给定定的的函函数数依依赖赖集集合合。其其中中U=AU=A，B B，C C，D D，EE，F=ABCF=ABC，ACBACB，BDBD，CECE，ECBECB，求（求（ABAB）+ + 。解：由算法可知解：由算法可知X X（0 0）=A=A，BB。ABCABC，BDBD，XX（0 0）=X=X（1 1）=A=A，BCBC，D=AD=A，B B，C C，DD。又又ABCABC，BDBD，CECE，ACBACB，XX（0 0）=X=X（1 1）=A=A，B B，C C，DCDC，D D，E E，B=B=AA，B B，C C，D D，EE。这这时时，X X（0 0）已已经经包

28、包含含U U的的全全部部属属性性，所所以以（ABAB）+ + =A=A，B B，C C，D D，EE。引引理理3 3 设设G G和和F F是是两两个个函函数数依依赖赖的的集集合合。F F和和G G等等价的充分必要条件是价的充分必要条件是F F G G+ +且且G G F F+ +。证明：证明：（1 1）必必要要性性 设设G G+ + F F+ + ，由由于于F F F F+ + 和和G G+ +=F=F+ +，我我们有们有F F G G+ +。同理我们有同理我们有G G F F+ +。 （2 2）充分性充分性 设设F F G G+ +且且G G F F+ +。对于每个对于每个XYFXYF+ +

29、，能从能从F F出发根据出发根据ArmstrongArmstrong公理导出。公理导出。由于由于F F G G+ + ，所以所以XYXY，能从能从G G+ +出发根据出发根据ArmstrongArmstrong公理导出，即公理导出，即XYXY（G G+ +）+ += G= G+ +。于是于是F F+ + G G+ + 。同理可证同理可证G G+ + F F+ +。最后，我们有最后，我们有G G+ +=F=F+ + 即即F F与与G G等价。证毕。等价。证毕。 定定义义9 9 如如果果函函数数依依赖赖集集F F满满足足下下列列条条件件，则称则称F F是一个极小函数依赖集。是一个极小函数依赖集。

30、（1 1）F F中中任任一一函函数数依依赖赖的的右右部部仅仅含含有有一一个属性；个属性； （2 2）F F中中不不存存在在这这样样的的函函数数依依赖赖XAXA，使得使得F F与与F XAF XA等价；等价； （3 3）F F中中不不存存在在这这样样的的函函数数依依赖赖XAXA，X X包包 括括 真真 子子 集集 Z Z， 使使 得得 （ F F XAXA）ZAZA与与F F等价。等价。 例例4 47 7 已知已知R R是一个具有属性集合是一个具有属性集合U U的的关系模式，关系模式，F F是给定的函数依赖集合。是给定的函数依赖集合。其中其中U=S#U=S#，SDSD，MNMN，CNCN，GRG

31、R，F=S#SDF=S#SD，SDMNSDMN，（，（S#S#，CNCN）GRGR。F=S#SDF=S#SD，S#MNS#MN，（，（S#S#，CNCN）GR GR ，SDMNSDMN，（，（S#S#，SDSD）SDSD。根据定义可以验证根据定义可以验证F F是极小函数依赖集，是极小函数依赖集，而而FF不是，因为不是，因为FS#MNFS#MN与与FF等价，等价，FF（S#S#，SDSD）SDSD与与FF等等价。价。 4.5 模式分解模式分解 定定义义1010 关关系系模模式式 R RU U，F F的的一一个个分分解解是指是指=R=R1 1U U1 1，F F1 1，R R2 2U U2 2，F

32、 F2 2， ，R Rn nU Un n，F Fn n 其其中中U= U= U Ui i ，并并且且没没有有U Ui i U Uj j，1 1i i，jnjn，F Fi i是是F F在在U Ui i上的投影。上的投影。nUi=1所谓所谓“F Fi i是是F F在在U Ui i上的投影上的投影”的确切定义是：的确切定义是：定义定义1111 函数依赖集合函数依赖集合XY|XYXY|XY F F+ +XY XY U Ui i 的的一一个个覆覆盖盖F Fi i叫叫做做F F在属性在属性U Ui i上的投影。上的投影。1 模式分解的三个定义模式分解的三个定义1)1)具有具有“无损连接性无损连接性”（Lo

33、ssless Lossless joinjoin）。）。2)2)要要“保持函数依赖保持函数依赖”（Preserve Preserve dependencydependency）。）。3)3)既要既要“保持函数依赖保持函数依赖”，又要具有，又要具有“无损连接性无损连接性” 例例4-8 4-8 已知关系模式已知关系模式R RU U，F F，其中其中U=SNOU=SNO，SDEPTSDEPT，MNMN，F=SNOSDEPTMNF=SNOSDEPTMN。R RU U，F F的元的元组语义是学生组语义是学生SNOSNO正在正在SDEPTSDEPT系学习，系学习，其系主任是其系主任是MNMN。并且一个学生

34、（并且一个学生（SNOSNO）只在一个系学生，一个系只有一名系只在一个系学生，一个系只有一名系主任。主任。 由于由于R R中存在传递函数依赖中存在传递函数依赖SNOMNSNOMN，它会它会发生更新异常。例如，如果发生更新异常。例如，如果S4S4毕业，毕业，则则D3D3系的系主任是王一的信息也就丢系的系主任是王一的信息也就丢掉了。反过来，如果一个系掉了。反过来，如果一个系D5D5尚无在尚无在校学生，那么这个系的系主任是赵某校学生，那么这个系的系主任是赵某的信息也无法存入。的信息也无法存入。 对关系模式对关系模式R R作如下分解：作如下分解：1 1= R= R1 1SNO,SNO,R,R2 2SD

35、EPT,SDEPT, , ,R ,R3 3MN,MN, 如如果果分分解解后后的的数数据据库能能够恢恢复复到到原原来来的的情情况况，不不丢失失信信息息的的要要求求也也就就达达到到了了。R Ri i向向R R的的恢恢复复是是通通过自自然然连接接来来实现的的，这就就产生了无生了无损连接性的概念。接性的概念。显然然，本本例例的的分分解解1 1所所产生生的的诸关关系系自自然然连接接的的结果果实际上上是是它它们的的笛笛卡卡尔尔积，元，元组增加了，信息增加了，信息丢失了。失了。 对对R R又进行另一种分解：又进行另一种分解：2 2= R= R1 1SNO,SDEPT,SNOSDEPTSNO,SDEPT,SN

36、OSDEPT, , R R2 2SNO,MN,SNOMNSNO,MN,SNOMN 可可以以证明明2 2对R R的的分分解解是是可可恢恢复复的的，但但是是前前面面提提到到的的插插入入和和删除除异异常常仍仍然然没没有有解解决决，原原因因 就就 在在 于于 原原 来来 在在 R R中中 存存 在在 的的 函函 数数 依依 赖SDEPTMNSDEPTMN在在R R1 1和和R R2 2中中都都不不存存在在了了。因因此此人人们又要求分解具有又要求分解具有“保持函数依保持函数依赖”的特性。的特性。最后对最后对R R进行了以下分解：进行了以下分解：3 3= R= R1 1SNOSNO，SDEPT,SNOSD

37、EPTSDEPT,SNOSDEPT , , R R2 2 SDEPT,MN,SDEPTMN SDEPT,MN,SDEPTMN 可可以以证证明明分分解解3 3既既具具有有无无损损连连接接性性，又又保保持持函函数数依依赖赖。它它解解决决了了更更新新异异常常，又又没没有有丢丢失原数据库的信息，这是所希望的分解。失原数据库的信息，这是所希望的分解。引引理理4 4 设设R RU U，F F是是一一个个关关系系模模式式，=R=R1 1U U1 1，F F1 1，R Rk kU Uk k，F Fk k 是是R RU U，F F的的一一个个分分解解，r r是是R RU U，F F的的一一个个关关系系，r ri

38、 i= = RiRi(r(r) )，则则（1 1）r r m m(r)(r)（2 2）若若s=ms=m(r)(r)，则，则 RiRi(s(s)=)=r ri i（3 3）m m(m(m(r)=m(r)=m(r)(r)证证明明：（1 1）证证明明r r中中的的任任何何一一个个元元组组属属于于m m(r)(r)。任任取取r r中中的的一一个个元元组组t t，trtr，设设t ti i= =t.Ut.Ui i（i=1i=1， 2 2， ， k k） 。 对对 k k进进 行行 归归 纳纳 可可 以以 证证 明明t t1 1t t2 2t tk k RiRi(r(r) )，所以所以tmtm(r)(r)

39、。（2 2）由由（1 1）得得到到r r m m(r)(r)，已已设设s=ms=m(r)(r)，所所以以，r r s s， RiRi(r(r) ) RiRi(s(s) )。现现只只需需证证 明明 RiRi(s(s) ) RiRi(r(r) )， 就就 有有 RiRi(s(s)= )= RiRi(r(r)=)=r ri i。ki=1任任取取S Si i RiRi(s(s) ) ，必必有有S S中中的的一一个个元元组v v，使使得得v.Uv.Ui i= =S Si i。根根据据自自然然连接接的的定定义v=tv=t1 1t t2 2t tk k ，对于于其其中中每每一一个个t ti i必必存存在在r

40、 r中中的的一一个个元元组t t，使使得得t.Ut.Ui i= =t ti i 。由由前前面面 RiRi(r(r) )的的定定义即即得得t ti i RiRi(r(r) )。又又因因v=tv=t1 1t t2 2t tk k ，故故v.Uv.UI I = =t ti i。又又由由上上面面证得得：v.Uv.Ui i = =S Si i ，t ti i RiRi(r(r) )，故故S Si i RiRi(r(r) )。即。即 RiRi(s(s) ) RiRi(r(r) )。故。故 RiRi(s(s)= )= RiRi (r) (r)。 （3 3）m m(m(m(r)= (r)= RiRi(m(m

41、(r)= (r)= RiRi(s(s)=)= RiRi(r(r)= m)= m(r)(r)ki=1ki=1ki=1定定义义1212 =R=R1 1U U1 1，F F1 1，R Rk kU Uk k，F Fk k 是是R RU U，F F的的一一个个分分解解，若若对对R R U U， F F 的的 任任 何何 一一 个个 关关 系系 r r均均 有有 r= r= m m(r)(r)成成立立，则则称称分分解解具具有有无无损损连连接接性。简称性。简称为无损分解。为无损分解。直直接接根根据据定定义义1212去去鉴鉴别别一一个个分分解解的的无无损损连连接接性性是是不不可可能能的的，算算法法2 2给给出

42、出了了一一个个判判断方法。断方法。算算法法2 2 判判断断一一个个分分解解的的无无损损连连接接性性。=RR1 1U U1 1，F F1 1，R Rk kU Uk k，F Fk k 是是R RU U，F F的的一一个个分分解解，U=AU=A1 1 ，A A2 2 ，A An n ，F=FDF=FD1 1 ，FDFD2 2 ，FDFDp p ，不不妨妨设设F F是一极小依赖集，记是一极小依赖集，记FDFDi i为为X Xi iAA1i 1i 。（1 1）建建立立一一张张n n列列k k行行的的表表。每每一一列列对对应应一一个个属属性性，每每一一行行对对应应分分解解中中的的一一个个关关系系模模式式。

43、若若属属性性A Aj j属属于于U Ui i，则则在在j j列列i i行行交叉处填上交叉处填上a aj j ，否则填上否则填上b bijij ；（2 2）对对每每一一个个FDFDi i做做下下列列操操作作：找找到到X Xi i所所对对应应的的列列中中具具有有相相同同符符号号的的那那些些行行。考考察察这这些些行行中中L Li i列列的的元元素素，若若其其中中有有a alili；否否则则全全部部改改为为b bmlimli；m m是这些行的行号最小值。是这些行的行号最小值。应应当当注注意意的的是是，若若某某个个b btlitli被被更更动动，那那么么该该表表的的lili列列中中凡凡是是b btlit

44、li的的符符号号（不不管管它它是是开开始始找找到到的的那些行）均作相应更改。那些行）均作相应更改。如如在在某某次次更更改改之之后后，又又一一行行成成为为a a1 1，a a2 2，a an n。则则算算法法终终止止。具具有有无无损损连连接接性性，否否则则不不具有无损连接。具有无损连接。对对f f中中p p个个FDFD逐逐一一进进行行一一次次这这样样的的处处理理，成成为为对对F F的一次扫描。的一次扫描。（3 3）比比较较扫扫描描前前后后，表表有有无无变变化化。如如有有变化，则返回（变化，则返回（2 2）步，否则算法终止。）步，否则算法终止。如如果果发生生循循环，那那么么前前次次扫描描至至少少应

45、使使该表表减减少少一一个个符符号号，表表中中符符号号有有限限，因因此此循循环必然必然终止。止。定定理理3 为为无无损损连连接接分分解解的的充充分分必必要要条条件件是是算算法法2终终止止时时，表表中中有有一一行行为为a1，a2，an。 例例4-9 已知已知RU，F，U=A，B，C，D，E，F=ABC，CD，DE，R的一个分解为的一个分解为R1(A，B，C)，R2(C，D)，R3(D，E)。(1) 构构造初始表：造初始表：ABCDEa1b21b31 a2b22b32 a3a3b33 b14a4a4 b15b25a5 (2)对对ABC，因各元组的第，因各元组的第1、2列没有相列没有相同的分量，所以表

46、不改变。由同的分量，所以表不改变。由CD可以可以把把b14改成改成a4，再由，再由DE可使可使b15、b25全改全改为为a5。表中第。表中第1行成为行成为a1、a2、a3、a4、a5，所以此分解具有无损连接性。所以此分解具有无损连接性。 ABCDEa1b21b31 a2b22b32 a3a3b33 a4a4a4 a5a5a5 当关系模式当关系模式R分解为两个关系模式分解为两个关系模式R1 ，R2时有下面的判断准则。时有下面的判断准则。定理定理4 RU，F的一个分解的一个分解=R1U1，F1，R2U2，F2具有无损连接性具有无损连接性的充分必要条件是：的充分必要条件是：U1U2U1-U2F+。

47、定义定义13 若若F+=( Fi )+，则，则RU，F的的分解分解=R1U1，F1，RkUk，Fk保持函数依赖。保持函数依赖。 kUi=13 模式分解的算法模式分解的算法 模式分解的几个重要事实是：模式分解的几个重要事实是：（1 1）若若要要求求分分解解保保持持函函数数依依赖赖，那那么么模模式式分分离离总总可可以以达达到到3NF3NF，但但不不一一定定能能达达到到BCNFBCNF；（2 2）若若要要求求分分解解既既保保持持函函数数依依赖赖，又又具具有有无无损损连连接接性性，可可以以达达到到3NF3NF，但但不不一一定能达到定能达到BCNFBCNF；（3 3）若若要要求求分分解解具具有有无无损损

48、连连接接性性，那那一一定可达到定可达到4NF4NF。它们分别由算法它们分别由算法3算法算法5来实现。来实现。算法算法3 （合成法）转换为（合成法）转换为3NF的保持函数依的保持函数依赖的分解。赖的分解。（1）对）对R中的函数依赖集中的函数依赖集F进行进行“极小化处理极小化处理”（处理后得到的依赖集仍（处理后得到的依赖集仍记为记为F）。）。（2）找出不在）找出不在F中出现的属性，把这样的中出现的属性，把这样的属性构成一个关系模式。把这些属性从属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为中去掉，剩余的属性仍记为U。（3）若有）若有XA F，且，且XA=U，则，则=R，算法终止；否则

49、转，算法终止；否则转(4)步。步。(4) 对对F按具有相同左部的原则分组（假定分为按具有相同左部的原则分组（假定分为k组），组），每一组函数依赖每一组函数依赖Fi 所涉及的全部属性形成一个属性集所涉及的全部属性形成一个属性集Ui。若。若Ui Uj（ij）就去掉）就去掉Ui 。由于经过了步骤。由于经过了步骤(2)，故，故U= Ui，于是，于是=R1U1,F1, ,RkUk，Fk构成构成RU，F的一个保持函数依赖的分解，并且的一个保持函数依赖的分解，并且每个每个RiUi，Fi均属均属3NF。这里。这里Fi是是F在在Ui上的投影，上的投影，并且并且Fi不一定与不一定与Fi相等，但相等，但Fi一定被一

50、定被Fi所包含，因此所包含，因此分解分解保持函数依赖是显然的。保持函数依赖是显然的。 kUi=1算法算法4 转换为转换为3NF既有无损连接性又保持既有无损连接性又保持函数依赖的分解。函数依赖的分解。（1）设）设X是是R的码。的码。R已由算已由算法法3分解为分解为=R1U1,F1,R2U2,F2, , RkUk,Fk，令，令 =R*X，Fx； （2）若有某个）若有某个Ui，X Ui，将，将X，Fx从从 中去掉；中去掉；（3） 就是所求的分解。就是所求的分解。 算法算法5 转换为转换为BCNF的无损连接分解（分解法）的无损连接分解（分解法）（1）令）令=R（2）检查）检查中各关系模式是否均属于中各关系模式是否均属于BCNF。若。若是，则算法终止。是，则算法终止。（3）设）设中中Ri不属于不属于BCNF，那么必有，那么必有XAFi+(A X)，且，且X非非Ri的码。因此，的码。因此，XA是是Ui的真子集。对的真子集。对Ri进行分解：进行分解：S1，S2，US1=XA，US2= Ui-A，以，以代替代替Ri返返回第（回第（2）步。）步。 由于由于U中属性有限，因而有限次循环后算法中属性有限，因而有限次循环后算法5一定一定会终止。会终止。