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.函数依赖的定义函数依赖的定义
3、定义定义1 1：设有关系模式设有关系模式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完全
4、函数依赖于完全函数依赖于X X，记作：，记作：X Y X Y。若。若XYXY，但，但Y Y不完全函数依赖于不完全函数依赖于X X，则称，则称Y Y部分函数依赖于部分函数依赖于X X，记作：，记作：X YX Y。fp定义定义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、：主任），有：学号学号班级，班级班级，班级班班主任，则学号主任，则学号班主任，所以班主任，所以 学号学号 班主任。班主任。tt2.键键 定义定义4 4 设设R R是一个具有属性集合是一个具有属性集合的关系的关系模式，模式，K K是是的子集。若的子集。若K K满足下列两满足下列两个条件，则称个条件，则称K K是是R R的一个候选键。的一个候选键。1)1)KK2)2)不存在不存在K K的真子集的真子集Z Z，使得，使得ZZ。候选键可以唯一地识别关系的元组。一个候选键可以唯一地识别关系的元组。一个关系模式中可能具有多个候选键。我关系模式中可能具有多个候选键。我们可以指定一个候选键作为主键。们可以指定
6、一个候选键作为主键。定义定义5 5 设设X X是关系模式是关系模式R R的属性的子集。如果的属性的子集。如果X X是另一关系模式的候选键，则称是另一关系模式的候选键，则称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)
7、4)（S S，C C）GRGR，一个学生选修一门课，一个学生选修一门课程有一个成绩等级；程有一个成绩等级；可以看出（可以看出（S S，C C）是主键。）是主键。4.3 关系的规范化关系的规范化 在关系数据模式设计中，为了避免由依赖在关系数据模式设计中，为了避免由依赖引起的数据冗余和更新异常等问题，引起的数据冗余和更新异常等问题，必须进行关系模式的合理分解，即关必须进行关系模式的合理分解，即关系模式的规范化。系模式的规范化。1.1.关系模式的范式关系模式的范式关系模式的设计原则：关系模式的设计原则：1)1)数据的冗余量尽量小；数据的冗余量尽量小；2)2)对关系进行插入、删除等操作，不要出问题对关
8、系进行插入、删除等操作，不要出问题3)3)尽量能如实地反映现实世界的实际情况，而尽量能如实地反映现实世界的实际情况，而且又易懂。且又易懂。关系数据库中的关系满足一定的要求。而把满关系数据库中的关系满足一定的要求。而把满足不同程度要求的关系称为不同的范式。足不同程度要求的关系称为不同的范式。满足最低要求的关系叫第一范式，简称满足最低要求的关系叫第一范式，简称1NF1NF。在。在第一范式中进一步满足一定要求的为第二范第一范式中进一步满足一定要求的为第二范式，简称式，简称2NF2NF，其余以此类推。，其余以此类推。关系规范化关系规范化:就是一个低一级范式的关系模式通就是一个低一级范式的关系模式通过投
9、影运算，转化为若干高一级范式的关系过投影运算，转化为若干高一级范式的关系模式的集合，这种过程就叫关系的规范化。模式的集合，这种过程就叫关系的规范化。各范式之间的关系各范式之间的关系1NF1NF2NF2NF3NF3NF4NF4NF5NF5NF(1)(1)第一范式（第一范式（1NF1NF）设设R R是一个关系模式。如果是一个关系模式。如果R R的每一属性的值都的每一属性的值都是不可分离的原子值，即每个属性的值域是是不可分离的原子值，即每个属性的值域是单值域，则单值域，则R R是第一范式，记作是第一范式，记作R1NFR1NF。符合符合1NF1NF的工资关系的工资关系编编 号号姓姓 名名基本工资基本工
10、资奖奖 金金1 12 210101515张三张三李四李四王五王五赵六赵六200200000028028000002602600000230230000030300000505000004545000040400000(2)(2)第二范式第二范式如果关系模式如果关系模式R1NFR1NF，且，且R R中每一非主属性完全中每一非主属性完全函数依赖于函数依赖于R R的键，则的键，则R R称为第二范式，记作称为第二范式，记作R2NFR2NF。例如，例如，4.14.1节给出的学生关系节给出的学生关系S S中非主属性中非主属性CLSCLS、MONMON都不是完全函数依赖于主键（都不是完全函数依赖于主键（S
11、S，C C），），而部分函数依赖于（而部分函数依赖于（S S，C C）。对）。对1NF1NF进行进行投影运算，将其分解为两个关系：投影运算，将其分解为两个关系：SSSSS S，SNSN，CLSCLS，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
12、，且它的任何一个非，且它的任何一个非主属性都不传递函数依赖于任何候选键，主属性都不传递函数依赖于任何候选键，则称则称R R为第三范式，记作为第三范式，记作R3NFR3NF。例如，例如，订单订单关系关系（订单号，顾客名称，商（订单号，顾客名称，商店货号，定购数量，交货日期）中的主店货号，定购数量，交货日期）中的主键是订单号，存在的函数依赖是：订单键是订单号，存在的函数依赖是：订单号号顾客名称；订单号顾客名称；订单号商品货号；订商品货号；订单号单号定购数量；订单号定购数量；订单号交货日期，交货日期，不再有别的函数依赖，此关系是不再有别的函数依赖，此关系是2NF2NF的，的，且所有非主属性对主键没有
13、传递函数依且所有非主属性对主键没有传递函数依赖，所以是赖，所以是3NF3NF的。的。(4)BC(4)BC范式（范式（BCNFBCNF）如果关系模式如果关系模式R1NFR1NF，且每个函数依赖，且每个函数依赖XYXY中中X X必为候选键，则必为候选键，则R R是是BCNFBCNF范式。范式。从从BCNFBCNF的定义可以明显地得出一个满足的定义可以明显地得出一个满足BCNFBCNF的的关系模式如下结论：关系模式如下结论：1)1)所有非主属性对键是完全函数依赖。所有非主属性对键是完全函数依赖。2)2)所有主属性对不包含它的键是完全函数依赖。所有主属性对不包含它的键是完全函数依赖。3)3)没有属性完
14、全函数依赖于非键的任何属性组没有属性完全函数依赖于非键的任何属性组例例4-3 4-3 在关系模式在关系模式SJPSJP（S S，J J，P P）中，中，S S是学号，是学号，J J是课号，是课号，P P为名次。为名次。每一个学生每门课程有一定的名次，每每一个学生每门课程有一定的名次，每门课程中每一名次只有一个学生。由这门课程中每一名次只有一个学生。由这些语义可得到下面的函数依赖：些语义可得到下面的函数依赖：（S S，J J）P P（J J，P P）S S 显然，（显然，（S S，J J）与（）与（J J，P P）都是候）都是候选键。这两个候选键各由两个属性组成，选键。这两个候选键各由两个属性组
15、成，而且相交。这个关系模式中显然没有属而且相交。这个关系模式中显然没有属性对键传递或部分依赖，所以性对键传递或部分依赖，所以SJP SJP 3NF3NF。例例4 44 4 关系模式关系模式SCTSCT（S S，C C，T T）中，中，S S表示学号，表示学号，C C表示课程号，表示课程号，T T表示教师。每一教师只教一门课。表示教师。每一教师只教一门课。每门课由若干教师教授，某一学生每门课由若干教师教授，某一学生选定某门课，就确定了一个固定的选定某门课，就确定了一个固定的教师。教师。于是有如下的函数依赖：于是有如下的函数依赖：1)1)（S S，C C）TT2)2)（S S，T T）CC3)3)
16、TCTC 显然，（显然，（S S，C C）和（）和（S S，T T）都是）都是候选键。候选键。SCTSCT是是3NF3NF，因为没有任何非因为没有任何非主属性对键的传递或部分函数依赖。主属性对键的传递或部分函数依赖。但但SCTSCT不是不是BCNFBCNF，因为，因为T T是决定因素，是决定因素，而而T T不是候选键。不是候选键。S#C#TS#TC#2关系规范化方法与实例关系规范化方法与实例 关系模式规范化遵循以下原则：关系模式规范化遵循以下原则：1)关系模式进行无损连接分解。关系模式分解关系模式进行无损连接分解。关系模式分解过程中数据不能丢失或增加，必须把全部关过程中数据不能丢失或增加，必须
17、把全部关系模式中的所有数据无损地分解到各个子关系模式中的所有数据无损地分解到各个子关系模式中，以保证数据的完整性。系模式中，以保证数据的完整性。2)合理选择规范化程度。低级范式造成的冗余合理选择规范化程度。低级范式造成的冗余度很大，既浪费了存储空间，又影响了数据度很大，既浪费了存储空间，又影响了数据的一致性，因此希望一个子模式的属性越少的一致性，因此希望一个子模式的属性越少越好，即取高级范式；若考虑查询效率、低越好，即取高级范式；若考虑查询效率、低级范式比高级范式好，此时连接运算的代价级范式比高级范式好，此时连接运算的代价较小，这是一对矛盾，所以应根据实际情况，较小，这是一对矛盾，所以应根据实
18、际情况，合理选择规范化程度。合理选择规范化程度。3)正确性与可实现性原则。正确性与可实现性原则。4.4函数依赖的公理系统函数依赖的公理系统 定义定义6 6 设设R R是一个具有属性集合是一个具有属性集合的关系模式，的关系模式，F F是是R R上的函数依赖集合。如果对于上的函数依赖集合。如果对于R R的任意一个使的任意一个使F F成立的关系实例成立的关系实例r r，函数依赖，函数依赖XYXY都成立，则称都成立，则称F F逻辑地蕴含逻辑地蕴含XYXY。ArmstrongArmstrong公理系统公理系统 设设R R是一个关系模式，是一个关系模式，为为R R的属性集合，的属性集合，F F为为上的一组
19、函数依赖的集合。上的一组函数依赖的集合。ArmstrongArmstrong公理系统包含如下三条推理规则：公理系统包含如下三条推理规则：（1 1）自反律自反律 若若Y Y X X ，则，则F F蕴含蕴含XYXY（2 2）增广律增广律 若若XYXY为为F F所蕴含，且所蕴含，且Z Z ，则，则XZYZXZYZ为为F F所蕴含。所蕴含。（3 3）传递律传递律 若若XYXY和和YZYZ为为F F所蕴含，则所蕴含，则XZXZ为为F F所蕴含。所蕴含。定理定理1 Armstrong1 Armstrong推理规则是正确的。推理规则是正确的。证明：证明：（1 1）设设Y Y X X U U。对于。对于R R
20、的任一关系实例的任一关系实例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 的 任 意 两 个 元 组的 任 意 两 个 元 组 t t 和和 s s，若，若tXZ=sXZ,tXZ=sXZ,则有则有tX=sXtX=sX，tZ=sZ tZ=sZ。由由XYXY，tY=sYtY=sY。于是。于是tYZ=sYZtYZ=sYZ从
21、而从而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。于是，。于是，XZXZ成立。成立。三条推理规则：三条推理规则：（1 1）合并规则）合并规则 如果如果XYXY，XZXZ成立，成立，则则XYZXYZ成立。成立。（2 2）伪传递规则）伪传递规则 如果如果XYXY和和WYZWYZ成立，成立，则
22、则XWZXWZ成立。成立。（3 3）分解规则）分解规则 如果如果XYXY和和Z Z Y Y成立，成立，则则XZXZ成立。成立。定理定理2 2 合并规则、伪传递规则和分解规则是正合并规则、伪传递规则和分解规则是正确的。确的。证明：证明：（1 1）由由XYXY和增广律，和增广律，XXYXXY。又由。又由XZXZ和增和增广律，广律，XYYZXYYZ。由传递律，。由传递律，XYZXYZ成立。合并成立。合并规则得证。规则得证。（2 2）由由XYXY和增广律，和增广律，XWYWXWYW。又由。又由YWZYWZ和和传递律，传递律，XWZXWZ。伪传递规则得证。伪传递规则得证。（3 3）由由Z Z Y Y和自
23、反律，和自反律，YZYZ。又由。又由XYXY和传递和传递律，律，XZXZ。分解规则得证。分解规则得证。引理引理1 XA1 XA1 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根据根据ArmstrongArmstrong公理导出的充分必要条件是公理导出的充分必要条件是Y Y X X+。定义定义7 7 设设R R是一个具有属性集合是一个具有属性集合U U的关系模的关系模式，式，F F是
24、给定的函数依赖集合。由是给定的函数依赖集合。由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 X关于函数依赖集关于函数依赖集F F的闭的闭包。包。引理引理2 2 把判定把判定XYXY是否能由是否能由F F根据根据ArmstrongArmstrong公理导出的问题转
25、化为求出公理导出的问题转化为求出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。所以当。所以当Y Y X X+时，时，XYXY能根据能根据ArmstrongArmstrong公理从公理从F F导出。导出。（2 2）必要性）必要性 设设XYXY能根据能根据
26、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,k k），所以），所以Y Y X X+，证毕。，证毕。算法算法1 1 计算计算X X+。输入：输入：X X，F F输出：输出：X X+方法：方法：1)1)X X（1 1）：）：=空集合；空集合；X X（0 0）：）：=X=X；2)2)B=A|VWB=A|VW能由能由F F根据根据ArmstrongArmstrong公理导出，公理导出，V V
27、 X(0)AWX(0)AW；3)3)X X（1 1）：）：=BX=BX（0 0）；）；4)4)IF XIF X（1 1）XX（0 0）THEN XTHEN 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的关系模的关系模式，式，F F是给定的函数依赖集合。其中是给定的函数依赖集合。其中U=AU=A，B B，C C，D D，EE，F=ABCF=ABC，ACBACB，BDBD，CECE，ECBECB，求（，求（ABAB）+
28、。解：由算法可知解：由算法可知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=AB=A，B B，C C，D D，EE。这时，这时，X X（0 0）已经包含）已经包含U U的全部属性，所以（的全部属性，所以（ABAB）+=A=A，B B，C C，D D，EE。引理引理3 3 设设G G和和F F是两个函数依赖的集合。是两个函数依赖的集合。F F和和G G等等价的充
29、分必要条件是价的充分必要条件是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+，能从，能从F F出发根据出发根据ArmstrongArmstrong公理导公理导出。由于出。由于F F G G+，所以，所以XYXY，能从，能从G G+出发根据出发根据ArmstrongArmstrong公理导出，即公理导出，即XYXY（G G+）
30、+=G=G+。于是于是F F+G G+。同理可证。同理可证G G+F F+。最后，我们有。最后，我们有G G+=F=F+即即F F与与G G等价。证毕。等价。证毕。定义定义9 9 如果函数依赖集如果函数依赖集F F满足下列条件，满足下列条件，则称则称F F是一个极小函数依赖集。是一个极小函数依赖集。（1 1）F F中任一函数依赖的右部仅含有一中任一函数依赖的右部仅含有一个属性；个属性；（2 2）F F中不存在这样的函数依赖中不存在这样的函数依赖XAXA，使得使得F F与与F F XAXA等价；等价；（3 3）F F中不存在这样的函数依赖中不存在这样的函数依赖XAXA，X X包括真子集包括真子集
31、Z Z，使得（，使得（F F XAXA）ZAZA与与F F等价。等价。例例4 47 7 已知已知R R是一个具有属性集合是一个具有属性集合U U的的关系模式，关系模式，F F是给定的函数依赖集合。是给定的函数依赖集合。其中其中U=S#U=S#，SDSD，MNMN，CNCN，GRGR，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不是，因为不是，因
32、为FFS#MNS#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 F2 2，R Rn nU Un n，F Fn n 其中其中U=UU=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上的投影上的投影”的确切定义是：的确切定义是：定义定义1
33、111 函数依赖集合函数依赖集合XY|XYXY|XY F F+XY XY U Ui i 的一个覆盖的一个覆盖F Fi i叫叫做做F F在属性在属性U Ui i上的投影。上的投影。1 模式分解的三个定义模式分解的三个定义1)1)具有具有“无损连接性无损连接性”（Lossless Lossless joinjoin）。）。2)2)要要“保持函数依赖保持函数依赖”（Preserve Preserve dependencydependency）。）。3)3)既要既要“保持函数依赖保持函数依赖”，又要具有，又要具有“无损连接性无损连接性”例例4-8 4-8 已知关系模式已知关系模式R RU U，F F，
34、其中，其中U=SNOU=SNO，SDEPTSDEPT，MNMN，F=SNOSDEPTMNF=SNOSDEPTMN。R RU U，F F的元的元组语义是学生组语义是学生SNOSNO正在正在SDEPTSDEPT系学习，系学习，其系主任是其系主任是MNMN。并且一个学生（。并且一个学生（SNOSNO）只在一个系学生，一个系只有一名系只在一个系学生，一个系只有一名系主任。主任。由于由于R R中存在传递函数依赖中存在传递函数依赖SNOMNSNOMN，它会，它会发生更新异常。例如，如果发生更新异常。例如，如果S4S4毕业，毕业，则则D3D3系的系主任是王一的信息也就丢系的系主任是王一的信息也就丢掉了。反过
35、来，如果一个系掉了。反过来，如果一个系D5D5尚无在尚无在校学生，那么这个系的系主任是赵某校学生，那么这个系的系主任是赵某的信息也无法存入。的信息也无法存入。对关系模式对关系模式R R作如下分解：作如下分解：1 1=R=R1 1SNO,SNO,R,R2 2SDEPT,SDEPT,R,R3 3MN,MN,如果分解后的数据库能够恢复到原来的情如果分解后的数据库能够恢复到原来的情况，不丢失信息的要求也就达到了。况，不丢失信息的要求也就达到了。R Ri i向向R R的恢复是通过自然连接来实现的，的恢复是通过自然连接来实现的，这就产生了无损连接性的概念。这就产生了无损连接性的概念。显然，本例的分解显然，
36、本例的分解1 1所产生的诸关系自所产生的诸关系自然连接的结果实际上是它们的笛卡尔然连接的结果实际上是它们的笛卡尔积，元组增加了，信息丢失了。积，元组增加了，信息丢失了。对对R R又进行另一种分解：又进行另一种分解：2 2=R=R1 1SNO,SDEPT,SNOSDEPTSNO,SDEPT,SNOSDEPT,R R2 2SNO,MN,SNOMNSNO,MN,SNOMN 可以证明可以证明2 2对对R R的分解是可恢复的，但是前的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，面提到的插入和删除异常仍然没有解决，原因原因就在于原来在就在于原来在R R中存在的函数依赖中存在的函数依赖SDEP
37、TMNSDEPTMN在在R R1 1和和R R2 2中都不存在了。因此人中都不存在了。因此人们又要求分解具有们又要求分解具有“保持函数依赖保持函数依赖”的特的特性。性。最后对最后对R R进行了以下分解：进行了以下分解：3 3=R=R1 1SNOSNO，SDEPT,SNOSDEPTSDEPT,SNOSDEPT ,R R2 2 SDEPT,MN,SDEPTMN SDEPT,MN,SDEPTMN 可以证明分解可以证明分解3 3既具有无损连接性，又保持既具有无损连接性，又保持函数依赖。它解决了更新异常，又没有丢函数依赖。它解决了更新异常，又没有丢失原数据库的信息，这是所希望的分解。失原数据库的信息，这
38、是所希望的分解。引理引理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 i=RiRi(r(r)，则，则（1 1）r r m m(r)(r)（2 2）若若s=ms=m(r)(r)，则，则 RiRi(s)=r(s)=ri i（3 3）m m(m(m(r)=m(r)=m(r)(r)证明：（证明：（1 1）证明）证明r r中的任何一个元组属于中的任何一个元组属于m m(r)(r)。任取任取r r
39、中的一个元组中的一个元组t t，trtr，设，设t ti i=t.U=t.Ui i（i=1i=1，2 2，k k）。对）。对 k k 进 行 归 纳 可 以 证 明进 行 归 纳 可 以 证 明t t1 1t t2 2t tk k RiRi(r(r)，所以，所以tmtm(r)(r)。（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任取任
40、取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 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
41、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(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 RU U，F F的任何一个关系的任何一个关系r r均有均有r=mr=m(r)(r)成立，则称分解成立，则称分
42、解具有无损连接性。简具有无损连接性。简称称为无损分解。为无损分解。直接根据定义直接根据定义1212去鉴别一个分解的无损连去鉴别一个分解的无损连接性是不可能的，算法接性是不可能的，算法2 2给出了一个判给出了一个判断方法。断方法。算法算法2 2 判断一个分解的无损连接性。判断一个分解的无损连接性。=R=R1 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是一极小依赖集，记是一极小依赖集，记FDF
43、Di i为为X Xi iAA1i 1i。（1 1）建立一张）建立一张n n列列k k行的表。每一列对应行的表。每一列对应一个属性，每一行对应分解中的一个关一个属性，每一行对应分解中的一个关系模式。若属性系模式。若属性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；否则全
44、部改为；否则全部改为b bmlimli；m m是这些行的行号最小值。是这些行的行号最小值。应当注意的是，若某个应当注意的是，若某个b btlitli被更动，那么该表的被更动，那么该表的lili列中凡是列中凡是b btlitli的符号（不管它是开始找到的的符号（不管它是开始找到的那些行）均作相应更改。那些行）均作相应更改。如在某次更改之后，又一行成为如在某次更改之后，又一行成为a a1 1，a a2 2，a an n。则算法终止。则算法终止。具有无损连接性，否则具有无损连接性，否则不不具有无损连接。具有无损连接。对对f f中中p p个个FDFD逐一进行一次这样的处理，成为对逐一进行一次这样的处理
45、，成为对F F的一次扫描。的一次扫描。（3 3）比较扫描前后，表有无变化。如有）比较扫描前后，表有无变化。如有变化，则返回（变化，则返回（2 2）步，否则算法终止。）步，否则算法终止。如果发生循环，那么前次扫描至少应如果发生循环，那么前次扫描至少应使使该该表减少一个符号，表中符号有限，因此表减少一个符号，表中符号有限，因此循环必然终止。循环必然终止。定理定理3 为无损连接分解的充分必要条件为无损连接分解的充分必要条件是算法是算法2终止时，表中有一行为终止时，表中有一行为a1，a2，an。例例4-9 已知已知RU，F，U=A，B，C，D，E，F=ABC，CD，DE，R的一个分解为的一个分解为R1
46、(A，B，C)，R2(C，D)，R3(D，E)。(1)构造初始表：构造初始表：ABCDEa1b21b31 a2b22b32 a3a3b33 b14a4a4 b15b25a5(2)对对ABC，因各元组的第，因各元组的第1、2列没有相列没有相同的分量，所以表不改变。由同的分量，所以表不改变。由CD可以可以把把b14改成改成a4，再由，再由DE可使可使b15、b25全改全改为为a5。表中第。表中第1行成为行成为a1、a2、a3、a4、a5，所以此分解具有无损连接性。所以此分解具有无损连接性。ABCDEa1b21b31 a2b22b32 a3a3b33 a4a4a4 a5a5a5 当关系模式当关系模式
47、R分解为两个关系模式分解为两个关系模式R1，R2时有下面的判断准则。时有下面的判断准则。定理定理4 RU，F的一个分解的一个分解=R1U1，F1，R2U2，F2具有无损连接性的具有无损连接性的充分必要条件是：充分必要条件是：U1U2U1-U2F+。定义定义13 若若F+=(Fi)+，则，则RU，F的的分解分解=R1U1，F1，RkUk，Fk保持函数依赖。保持函数依赖。kUi=13 模式分解的算法模式分解的算法 模式分解的几个重要事实是：模式分解的几个重要事实是：（1 1）若要求分解保持函数依赖，那么模若要求分解保持函数依赖，那么模式分离总可以达到式分离总可以达到3NF3NF，但不一定能达，但不
48、一定能达到到BCNFBCNF；（2 2）若要求分解既保持函数依赖，又具若要求分解既保持函数依赖，又具有无损连接性，可以达到有无损连接性，可以达到3NF3NF，但不一，但不一定能达到定能达到BCNFBCNF；（3 3）若要求分解具有无损连接性，那一若要求分解具有无损连接性，那一定可达到定可达到4NF4NF。它们分别由算法它们分别由算法3算法算法5来实现。来实现。算法算法3（合成法）转换为（合成法）转换为3NF的保持函数依的保持函数依赖的分解。赖的分解。（1）对）对R中的函数依赖集中的函数依赖集F进行进行“极小化处理极小化处理”（处理后得到的依赖集（处理后得到的依赖集仍记为仍记为F）。）。（2）找
49、出不在）找出不在F中出现的属性，把这样的中出现的属性，把这样的属性构成一个关系模式。把这些属性从属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为中去掉，剩余的属性仍记为U。（3）若有）若有XA F，且，且XA=U，则，则=R，算法终止；否则转算法终止；否则转(4)步。步。(4)对对F按具有相同左部的原则分组（假定分为按具有相同左部的原则分组（假定分为k组），每组），每一组函数依赖一组函数依赖Fi 所涉及的全部属性形成一个属性集所涉及的全部属性形成一个属性集Ui。若若Ui Uj（ij）就去掉）就去掉Ui。由于经过了步骤。由于经过了步骤(2)，故，故U=Ui，于是，于是=R1U1,F1
50、,RkUk，Fk构构成成RU，F的一个保持函数依赖的分解，并且每个的一个保持函数依赖的分解，并且每个RiUi，Fi均属均属3NF。这里。这里Fi是是F在在Ui上的投影，并上的投影，并且且Fi不一定与不一定与Fi相等，但相等，但Fi一定被一定被Fi所包含，因此分解所包含，因此分解保持函数依赖是显然的。保持函数依赖是显然的。kUi=1算法算法4 转换为转换为3NF既有无损连接性又保持既有无损连接性又保持函数依赖的分解。函数依赖的分解。（1）设）设X是是R的码。的码。R已由算已由算法法3分解为分解为=R1U1,F1,R2U2,F2,RkUk,Fk，令，令 =R*X，Fx；（2）若有某个）若有某个Ui
