保持函数依赖的分解

1、保持函数依赖的分解保持函数依赖的分解定义定义(FD集的投影集的投影)：设设F是属性集是属性集U上的上的FD集，集，Z是是U的子集，的子集，P PZ(F) =XY | XY可由可由F推出推出, 且且X, Y Z F= RUZF在在Z上的上的投影投影P PZ(F)定义为：定义为：P PZ(F)= , 投影投影如果如果XY可由可由F推出推出XYX, Y例例: FD集的投影集的投影设有关系模式设有关系模式R(ABCD), R上的上的FD集为：集为： F = AB, BC , DB 求求P PACD(F) 和和P PBD(F) P PACD(F)= , ACDCP PBD(F)= DB 设设=R1,Rk

2、是关是关系模式系模式R的一个分解，的一个分解，F是是R上的上的FD集，如果集，如果: P PR1(F) P PRk(F)与与F等价，等价，两个函数依赖集两个函数依赖集F和和G是是等价的等价的，当且仅当：，当且仅当： 1) 凡是能够由凡是能够由F推出的推出的FD都能够由都能够由G推出；推出； 2) 凡是不能由凡是不能由F推出的推出的FD也不能由也不能由G推出。推出。则称则称分解分解保持函数依赖集保持函数依赖集F。定义定义(保持函数依赖的分解保持函数依赖的分解)：例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解设有关系模式：设有关系模式：R( N, S, G ) 职工工号职工工号

3、 工资级别工资级别 工资数目工资数目R上的上的FD集为：集为：F= NS, /* 每个职工只有一个工资级别每个职工只有一个工资级别 */ S G /* 一个工资级别只有一个工资数目一个工资级别只有一个工资数目*/ 将将R分解为分解为: = NS, NG ， 保持依赖？无损分解？保持依赖？无损分解？解：解：P PNS(F)=NS， P PNG(F)=NG。 因为根据因为根据NS和和NG推不出推不出S G, 所以所以不保持不保持函数依赖；函数依赖；1N2S3G1NSa1a2b132NGa1b22a3但是是但是是无损分解无损分解：设有关系模式：设有关系模式：R( N, S, G ) 职工工号职工工号

4、 工资级别工资级别 工资数目工资数目R上的上的FD集为：集为：F= NS, /* 每个职工只有一个工资级别每个职工只有一个工资级别 */ S G /* 一个工资级别只有一个工资数目一个工资级别只有一个工资数目*/ 将将R分解为分解为: = NS, NG ， 保持依赖？无损分解？保持依赖？无损分解？解：解：P PNS(F)=NS， P PNG(F)=NG。 因为根据因为根据NS和和NG推不出推不出S G, 所以所以不保持不保持函数依赖；函数依赖；1N2S3G1NSa1a2b132NGa1a2a3但是是但是是无损分解无损分解：例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解思考：

5、不保持函数依赖的思考：不保持函数依赖的分解会导致什么问题？分解会导致什么问题？设有关系模式：设有关系模式：R( N, S, G ) 职工工号职工工号 工资级别工资级别 工资数目工资数目R上的上的FD集为：集为：F= NS, /* 每个职工只有一个工资级别每个职工只有一个工资级别 */ S G /* 一个工资级别只有一个工资数目一个工资级别只有一个工资数目*/ 1N2S3G1NSa1a2b132SGb21a2a3也是也是无损分解无损分解：将将R分解为分解为: = NS, SG ， 保持依赖？无损分解？保持依赖？无损分解？解：解：P PNS(F)=NS， P PSG(F)=SG。 因为因为P PN

6、S(F)P PSG(F)= F, 所以所以保持函数依赖；保持函数依赖；例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解设有关系模式：设有关系模式：R( N, S, G ) 职工工号职工工号 工资级别工资级别 工资数目工资数目R上的上的FD集为：集为：F= NS, /* 每个职工只有一个工资级别每个职工只有一个工资级别 */ S G /* 一个工资级别只有一个工资数目一个工资级别只有一个工资数目*/ 1N2S3G1NSa1a2a32SGb21a2a3也是也是无损分解无损分解：将将R分解为分解为: = NS, SG ， 保持依赖？无损分解？保持依赖？无损分解？解：解：P PNS(

7、F)=NS， P PSG(F)=SG。 因为因为P PNS(F)P PSG(F)= F, 所以所以保持函数依赖；保持函数依赖；例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解解：解：P PAB(F)=AB， P PAC(F)= 。 保持依赖保持依赖；1A2B3C1ABa1a2b132ACa1b22a3也是也是无损分解无损分解：1A2B3C1ABa1a2b132ACa1a2a3设有关系模式：设有关系模式：R(ABC), R上的上的FD集为：集为：F= AB 将将R分解为分解为: = AB, AC ， 保持依赖？无

8、损分解？保持依赖？无损分解？例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解解：解：P PAB(F)=AB， P PAC(F)=AC。 不不保持依赖保持依赖(丢失丢失BC)；1A2B3C1ABa1a2b132ACa1b22a3但是是但是是无损分解无损分解：1A2B3C1ABa1a2b132ACa1a2a3设有关系模式：设有关系模式：R(ABC), R上的上的FD集为：集为：将将R分解为分解为: = AB, AC ， 保持依赖？无损分解？保持依赖？无损分解？F= AB, BC 例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解解：解：P PAB(F)=BA， P

9、 PAC(F)= 。 保持依赖保持依赖；1A2B3C1ABa1a2b132ACa1b22a3但是是但是是损失分解损失分解：设有关系模式：设有关系模式：R(ABC), R上的上的FD集为：集为：将将R分解为分解为: = AB, AC ， 保持依赖？无损分解？保持依赖？无损分解？F= BA 例例: 分解是否保持分解是否保持FD集集,是否无损分解是否无损分解解：解：P PAB(F)=BA， P PAC(F)=CA。 不不保持依赖保持依赖(丢失丢失CB) ；1A2B3C1ABa1a2b132ACa1b22a3也是也是损失分解损失分解：设有关系模式：设有关系模式：R(ABC), R上的上的FD集为：集为：将将R分解为分解为: = AB, AC ， 保持依赖？无损分解？保持依赖？无损分解？F= CB, BA 总结总结无损分解无损分解 保持依赖保持依赖说明说明YESYES最好最好 (不丢失数据和依赖不丢失数据和依赖)YESNO可接受可接受 (丢失依赖丢失依赖, 会导致会导致异常异常)NOYES不能接受不能接受(丢失数据丢失数据)NONO不能接受不能接受(丢失数据丢失数据)根据是否根据是否保持依赖保持依赖、是否、是否无损分解无损分解将将分解分解分成四类：分成四类：问题：问题：如何在如何在保证保证无损和保持依赖的前提下，使分解所无损和保持依赖的前提下，使分解所得的得的关系