《关系模式分解》PPT课件.ppt

《《关系模式分解》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系模式分解》PPT课件.ppt（42页珍藏版）》请在金锄头文库上搜索。

1、第第3讲讲关系模式的分解关系模式的分解授课人：授课人： 李朔李朔Email:Email:2024/8/61南晓数信学院主要内容主要内容主要内容主要内容n n模式分解模式分解模式分解模式分解n n无损联接分解无损联接分解无损联接分解无损联接分解n n保持函数依赖集保持函数依赖集保持函数依赖集保持函数依赖集2024/8/62南晓数信学院 设设设设有关系模式有关系模式有关系模式有关系模式R(U,F)R(U,F)R(U,F)R(U,F)，F F F F是是是是R R R R的函数依的函数依的函数依的函数依赖赖赖赖集，集，集，集，Z Z Z Z是是是是U U U U的子集的子集的子集的子集，则则则则把把

2、把把F F F F中所有中所有中所有中所有满满满满足足足足XYXYXYXY Z Z Z Z的函的函的函的函数依数依数依数依赖赖赖赖XYXYXYXY组组组组成的集合，称成的集合，称成的集合，称成的集合，称为为为为依依依依赖赖赖赖集集集集F F F F在属性集在属性集在属性集在属性集Z Z Z Z上的投影上的投影上的投影上的投影，记为记为记为记为Z Z Z Z(F(F(F(F) ) ) )： Z Z Z Z(F(F(F(F) ) ) ) XYXYXYXY| | | |XYFXYFXYFXYF且且且且XYXYXYXY Z Z Z Z 1 1、F F在在在在U Ui i上的投影上的投影上的投影上的投影

3、2024/8/63南晓数信学院U=UU=U1 1 U U2 2 U Uk k对于任意的对于任意的对于任意的对于任意的i,j(1i,i,j(1i,i,j(1i,i,j(1i,jkjkjkjk) ) ) )，不成立不成立不成立不成立U U U Ui i i i U U U Uj j j jF Fi i是是是是F F在在在在U Ui i上的投影上的投影上的投影上的投影= R1(U1,F1),R2(U2,F2),Rk(Uk,Fk)一、模式分解一、模式分解一、模式分解一、模式分解2 2、分解定义、分解定义、分解定义、分解定义 P109P1092024/8/64南晓数信学院经过不适当的分解后再连接，将恢复

4、不了原来经过不适当的分解后再连接，将恢复不了原来经过不适当的分解后再连接，将恢复不了原来经过不适当的分解后再连接，将恢复不了原来信息信息信息信息 2024/8/65南晓数信学院关系模式分解例：关系模式分解例：关系模式关系模式关系模式关系模式：学生（学号，系别，系主任）：学生（学号，系别，系主任）：学生（学号，系别，系主任）：学生（学号，系别，系主任）函数依赖集函数依赖集函数依赖集函数依赖集：F=F=学号学号学号学号系别，系别系别，系别系别，系别系别，系别-系主任系主任系主任系主任 分解分解分解分解1 1：11=R1(=R1(学号学号学号学号) )，R2(R2(系别系别系别系别) )，R3(R3

5、(系主任系主任系主任系主任)不能连接为原关系实例不能连接为原关系实例不能连接为原关系实例不能连接为原关系实例F1=F2=F3=F1=F2=F3=，函数依赖不保持，函数依赖不保持，函数依赖不保持，函数依赖不保持2024/8/66南晓数信学院分解分解分解分解2222=P(=P(学号，系别学号，系别学号，系别学号，系别) )，R(R(学号，系主任学号，系主任学号，系主任学号，系主任)F1F1=学号学号学号学号系别系别系别系别 ，F2F2=学号学号学号学号系主任系主任系主任系主任 能连接为原关系实例，但依赖约束不能恢复（能连接为原关系实例，但依赖约束不能恢复（能连接为原关系实例，但依赖约束不能恢复（能

6、连接为原关系实例，但依赖约束不能恢复（ 系别系别系别系别系主任）系主任）系主任）系主任）分解分解分解分解3333=P(=P(学号，系属学号，系属学号，系属学号，系属) )，R(R(系属，主任系属，主任系属，主任系属，主任)F1F1=学号学号学号学号系属系属系属系属 ，F2F2=系属系属系属系属主任主任主任主任既能连接为原关系，又能保持函数依赖约束既能连接为原关系，又能保持函数依赖约束既能连接为原关系，又能保持函数依赖约束既能连接为原关系，又能保持函数依赖约束 2024/8/67南晓数信学院两个问题两个问题两个问题两个问题：思考：思考：思考：思考：R(UR(U) )R R1 1(U(U1 1),

7、 ), R R2 2(U(U2 2), ), R Rk k(U(Uk k) )F FF F1 1, F, F2 2, , F Fk k无损联接无损联接无损联接无损联接保持依赖保持依赖保持依赖保持依赖2024/8/68南晓数信学院二、无损联接分解二、无损联接分解二、无损联接分解二、无损联接分解2024/8/69南晓数信学院二、无损联接分解二、无损联接分解二、无损联接分解二、无损联接分解1 1 1 1、定义、定义、定义、定义 设设设设有有有有关关关关系系系系模模模模式式式式R(U,F)R(U,F)R(U,F)R(U,F)，=（R R R R1 1 1 1,R,R,R,R2 2 2 2,R R R

8、Rk k k k）是是是是R R R R的的的的一一一一个个个个分分分分解解解解。如如如如果果果果对对对对于于于于R R R R的的的的任任任任一一一一满满满满足足足足F F F F的的的的关关关关系系系系r r r r，把把把把r r r r在在在在上的投影的上的投影的上的投影的上的投影的联联联联接表达式接表达式接表达式接表达式记为记为记为记为： mm (r(r) ) R1R1(r)(r)R2R2(r)(r) RkRk(r(r) ) 如如如如果果果果r r r rm m m m (r(r(r(r) ) ) )成成成成立立立立，则则则则称称称称这这这这个个个个分分分分解解解解是是是是满满满满足

9、足足足依依依依赖赖赖赖集集集集F F F F的的的的无无无无损损损损联联联联接接接接分分分分解解解解。( ( ( (通通通通过过过过自自自自然然然然连连连连接接接接可可可可还还还还原原原原关关关关系系系系r,r,r,r,一个不少一个不少一个不少一个不少, , , ,一个不多一个不多一个不多一个不多) ) ) )2024/8/610南晓数信学院 输输输输入：关系模式入：关系模式入：关系模式入：关系模式R(AR(AR(AR(A1 1 1 1,A,A,A,An n n n) ) ) )， 函数依函数依函数依函数依赖赖赖赖集集集集F F F F， R R R R的一个分解的一个分解的一个分解的一个分解

10、(R(R(R(R1 1 1 1,R R R Rk k k k) ) ) )。 输输输输出：出：出：出：是否是否是否是否为为为为无无无无损联损联损联损联接的判断。接的判断。接的判断。接的判断。 方法方法方法方法: : : :2 2 2、算法算法算法算法5.25.2 判断一个分解的无损联接性判断一个分解的无损联接性判断一个分解的无损联接性判断一个分解的无损联接性2024/8/611南晓数信学院A A1 1A Aj jA An nR R1 1R Ri iR Rk ksi,jsi,jsi,jsi,j A Aj j在在在在R Ri i中中中中, , a aj jA Aj j不在不在不在不在R Ri i中

11、中中中, , b bij ij（1 1 1 1）构造一个）构造一个）构造一个）构造一个k k k k行行行行n n n n列列列列表表表表S S S S，其中：，其中：，其中：，其中：2 2 2、算法算法算法算法5.2 5.2 判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续1 1）2024/8/612南晓数信学院（2 2 2 2）依据函数依）依据函数依）依据函数依）依据函数依赖赖赖赖集集集集F F F F进进进进行行行行修正修正修正修正：XYXYXYXYX XY YR R1 1R Ri iR Rk k若若若若Y Y值中有值中有值

12、中有值中有 a aj j，其它也改为，其它也改为，其它也改为，其它也改为a aj j若若若若Y Y值中无值中无值中无值中无 a aj j，其它改为，其它改为，其它改为，其它改为b bij ij（下标小（下标小（下标小（下标小）FDFD的选择顺序可随意的选择顺序可随意的选择顺序可随意的选择顺序可随意2 2 2、算法算法算法算法5.2 5.2 判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续2 2）2024/8/613南晓数信学院X XY YR R1 1R Ri iR Rk ka a a a1 1 1 1a a a an n n na

13、 a a a2 2 2 2分解分解分解分解 具有无损联接性具有无损联接性具有无损联接性具有无损联接性（3 3 3 3）判断条件判断条件判断条件判断条件：2 2 2、算法算法算法算法5.2 5.2 判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续判断一个分解的无损联接性（续3 3）2024/8/614南晓数信学院A AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b2323b b2424b b2525R R3 3b b3131a a2 2b b3333b b3434a

14、 a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b5353b b5454a a5 5第一步：构造表第一步：构造表第一步：构造表第一步：构造表S S S S例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1( ( ( (ADADADAD) ) ) )，R R R R2 2 2 2( ( ( (ABABA

15、BAB) ) ) )，R R R R3 3 3 3( ( ( (BEBEBEBE) ) ) )，R R R R4 4 4 4( ( ( (CDECDECDECDE) ) ) )，R R R R5 5 5 5( ( ( (AEAEAEAE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/615南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正A A A AC C C CA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a

16、 a2 2b b2323b b2424b b2525R R3 3b b3131a a2 2b b3333b b3434a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b5353b b5454a a5 5例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=F=F=F=ACACACAC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R

17、2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/616南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正ACACACAC( ( ( (注意注意注意注意: : : :此时表式此时表式此时表式此时表式,R1,R2,R5,R1,R2,R5,R1,R2,R5,R1,R2

18、,R5自然联接自然联接自然联接自然联接, , , ,刚刚刚刚A A A A属性值相同属性值相同属性值相同属性值相同, , , ,若有若有若有若有C C C C属性，则值一属性，则值一属性，则值一属性，则值一定相同定相同定相同定相同A AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313b b2424b b2525R R3 3b b3131a a2 2b b3333b b3434a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5

19、252b b1313b b5454a a5 5例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=F=F=F=ACACACAC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE

20、)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/617南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正BCBCBCBCA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313b b2424b b2525R R3 3b b3131a a2 2b b3333b b3434a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b

21、b1313b b5454a a5 5例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分

22、解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/618南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正BCBCBCBCA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313b b2424b b2525R R3 3b b3131a a2 2b b1313b b3434a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b1313

23、b b5454a a5 5例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分

24、解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/619南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正CDCDCDCDA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313b b2424b b2525R R3 3b b3131a a2 2b b1313b b3434a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b1313b b54

25、54a a5 5例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分

26、解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/620南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正CDCDCDCDA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3b b3131a a2 2b b1313a a4 4a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b1313a a4 4a a5 5

27、例例例例 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否

28、具有无损联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/621南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正DECDECDECDECA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3b b3131a a2 2b b1313a a4 4a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252b b1313a a4 4a a5 5例例例例

29、 5.7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损

30、联接性。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/622南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正DECDECDECDECA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3b b3131a a2 2a a3 3a a4 4a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252a a3 3a a4 4a a5 5例例例例 5.7 5

31、.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否

32、具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/623南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正CEACEACEACEAA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3b b3131a a2 2a a3 3a a4 4a a5 5R R4 4b b4141b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252a a3 3a a4 4a a5 5例例例例 5.7 5.7 5.7

33、 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA ，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联

34、接性。是否具有无损联接性。是否具有无损联接性。 2024/8/624南晓数信学院第二步：修正第二步：修正第二步：修正第二步：修正CEACEACEACEAA AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3a a1 1a a2 2a a3 3a a4 4a a5 5R R4 4a a1 1b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252a a3 3a a4 4a a5 5例例例例 5.7 5.7 5.7 5.7 设设

35、设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性。是否具有无损联接性。是否具有无

36、损联接性。是否具有无损联接性。 2024/8/625南晓数信学院第三步：判断第三步：判断第三步：判断第三步：判断A AB BC CDDE ER R1 1a a1 1b b1212b b1313a a4 4b b1515R R2 2a a1 1a a2 2b b1313a a4 4b b2525R R3 3a a1 1a a2 2a a3 3a a4 4a a5 5R R4 4a a1 1b b4242a a3 3a a4 4a a5 5R R5 5a a1 1b b5252a a3 3a a4 4a a5 5分解分解分解分解具有无损联接性具有无损联接性具有无损联接性具有无损联接性例例例例 5.

37、7 5.7 5.7 5.7 设设设设R(ABCDE)R(ABCDE)R(ABCDE)R(ABCDE)，F=ACF=ACF=ACF=AC，BCBCBCBC，CDCDCDCD，DECDECDECDEC，CEACEACEACEA，=R=R=R=R1 1 1 1(AD)(AD)(AD)(AD)，R R R R2 2 2 2(AB)(AB)(AB)(AB)，R R R R3 3 3 3(BE)(BE)(BE)(BE)，R R R R4 4 4 4(CDE)(CDE)(CDE)(CDE)，R R R R5 5 5 5(AE)(AE)(AE)(AE)，检验分解，检验分解，检验分解，检验分解是否具有无损联接性

38、。是否具有无损联接性。是否具有无损联接性。是否具有无损联接性。 2024/8/626南晓数信学院* *补充：关系分解无损连接性判别算法的正确性证明补充：关系分解无损连接性判别算法的正确性证明补充：关系分解无损连接性判别算法的正确性证明补充：关系分解无损连接性判别算法的正确性证明引理引理引理引理1 1 算法算法算法算法5.25.2的初始矩阵有性质的初始矩阵有性质的初始矩阵有性质的初始矩阵有性质: :任取任取任取任取j, j,第第第第j j行对行对行对行对RjRj的投影元素全是的投影元素全是的投影元素全是的投影元素全是a.a. （事实上，这是由算法的初始化步骤所决定的。事实上，这是由算法的初始化步

39、骤所决定的。事实上，这是由算法的初始化步骤所决定的。事实上，这是由算法的初始化步骤所决定的。）引理引理引理引理2 2 执行算法执行算法执行算法执行算法5.25.2过程中过程中过程中过程中, ,矩阵的每个符号矩阵的每个符号矩阵的每个符号矩阵的每个符号a a不可不可不可不可能变为其它符号能变为其它符号能变为其它符号能变为其它符号. .（因算法规则是因算法规则是因算法规则是因算法规则是 若列含若列含若列含若列含a a则全列改为则全列改为则全列改为则全列改为a,a,否则全否则全否则全否则全列取为最小行标列取为最小行标列取为最小行标列取为最小行标 ）2024/8/627南晓数信学院引理引理引理引理3 3

40、 算法算法算法算法5.25.2终止矩阵有性质终止矩阵有性质终止矩阵有性质终止矩阵有性质: :任意任意任意任意j, j,第第第第j j行对行对行对行对RjRj的投映元素全是的投映元素全是的投映元素全是的投映元素全是a.a.( (事实上，这由引理事实上，这由引理事实上，这由引理事实上，这由引理1 1和引理和引理和引理和引理2 2所决定所决定所决定所决定 ) )引理引理引理引理4 4 算法算法算法算法5.25.2的终止矩阵作为关系实例必然满足的终止矩阵作为关系实例必然满足的终止矩阵作为关系实例必然满足的终止矩阵作为关系实例必然满足函数依赖集函数依赖集函数依赖集函数依赖集F.F.（事实上事实上事实上事

41、实上, ,算法的实质是检查初始矩阵作为关系算法的实质是检查初始矩阵作为关系算法的实质是检查初始矩阵作为关系算法的实质是检查初始矩阵作为关系实例是否满足实例是否满足实例是否满足实例是否满足FF的每个函数依赖的每个函数依赖的每个函数依赖的每个函数依赖. .若不满足某个若不满足某个若不满足某个若不满足某个函数依赖函数依赖函数依赖函数依赖, ,则修改相关元素则修改相关元素则修改相关元素则修改相关元素, ,使矩阵满足这个函数使矩阵满足这个函数使矩阵满足这个函数使矩阵满足这个函数依赖依赖依赖依赖, ,故终止矩阵必满足故终止矩阵必满足故终止矩阵必满足故终止矩阵必满足F.F.）2024/8/628南晓数信学院

42、定理定理定理定理1 1 关系关系关系关系R R的分解的分解的分解的分解 具无损连接性的充要条件是算法具无损连接性的充要条件是算法具无损连接性的充要条件是算法具无损连接性的充要条件是算法5.25.2的终止矩阵的终止矩阵的终止矩阵的终止矩阵r r有一行的符号全是有一行的符号全是有一行的符号全是有一行的符号全是a.a.证明证明证明证明必要性必要性必要性必要性: :若终止矩阵无全若终止矩阵无全若终止矩阵无全若终止矩阵无全a a的行的行的行的行, ,断言断言断言断言 不具无损连接性不具无损连接性不具无损连接性不具无损连接性. .一方面一方面一方面一方面, ,由引理由引理由引理由引理4,4,终止矩阵终止矩

43、阵终止矩阵终止矩阵r r必满足函数依赖集必满足函数依赖集必满足函数依赖集必满足函数依赖集F,F,且无全且无全且无全且无全a a的行的行的行的行. .另一方面另一方面另一方面另一方面, ,由引理由引理由引理由引理3,3,终止矩阵终止矩阵终止矩阵终止矩阵r r的第的第的第的第j j行对行对行对行对RjRj的投映元素全的投映元素全的投映元素全的投映元素全是是是是a(a(任取任取任取任取j),j),故故故故M(rM(r)=R1(r).)=R1(r).Rk(rRk(r) )必含全必含全必含全必含全a a行行行行. .故故故故rM(rrM(r).).故断言真故断言真故断言真故断言真证明充分性证明充分性证明

44、充分性证明充分性: :若终止矩阵有一行全若终止矩阵有一行全若终止矩阵有一行全若终止矩阵有一行全a,a,往证往证往证往证 具无损连接性具无损连接性具无损连接性具无损连接性. .（)2024/8/629南晓数信学院 设设设设有有有有关关关关系系系系模模模模式式式式R(U,F)R(U,F)R(U,F)R(U,F)，F F F F是是是是R R R R的的的的属属属属性性性性集集集集U U U U上上上上的的的的函函函函数数数数依依依依赖赖赖赖集集集集，=（R R R R1 1 1 1,R,R,R,R2 2 2 2）是是是是R R R R的的的的一一一一个个个个分分分分解解解解，当当当当且且且且仅仅仅

45、仅当当当当 （R R R R1 1 1 1RRRR2 2 2 2）（R R R R1 1 1 1-R-R-R-R2 2 2 2） 或或或或（R R R R1 1 1 1RRRR2 2 2 2）（R R R R2 2 2 2-R-R-R-R1 1 1 1）属于）属于）属于）属于F+F+F+F+ 时时时时，具有无具有无具有无具有无损联损联损联损联接性。接性。接性。接性。3 3、判断定理判断定理判断定理判断定理2024/8/630南晓数信学院证证证证：充分性：充分性：充分性：充分性 (R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R1 1 1 1-R-R-R-R2 2 2

46、2) ) ) )或或或或(R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R2 2 2 2-R-R-R-R1 1 1 1) ) ) )成立成立成立成立R R1 1RR2 2R R1 1-R-R2 2R R2 2-R-R1 1R R1 1R R2 2aaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a abbbbbbbbb b b bbbbbbbbbb b b bFFFF3 3、判断定理（续判断定理（续判断定理（续判断定理（续1 1）2024/8/631南晓数信学院证证证证：充分性：充分性：充分性：充分性 (

47、R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R1 1 1 1-R-R-R-R2 2 2 2) ) ) )或或或或(R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R2 2 2 2-R-R-R-R1 1 1 1) ) ) )成立成立成立成立R R1 1RR2 2R R1 1-R-R2 2R R2 2-R-R1 1R R1 1R R2 2aaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a abbbbbbbbb b b bFFFFaaaaaaaaa a a a3 3、判断定理（续判断

48、定理（续判断定理（续判断定理（续2 2）2024/8/632南晓数信学院证证证证：充分性：充分性：充分性：充分性 (R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R1 1 1 1-R-R-R-R2 2 2 2) ) ) )或或或或(R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R2 2 2 2-R-R-R-R1 1 1 1) ) ) )成立成立成立成立R R1 1RR2 2R R1 1-R-R2 2R R2 2-R-R1 1R R1 1R R2 2aaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a aaaa

49、aaaaaa a a abbbbbbbbb b b bbbbbbbbbb b b bFFFF+ + + +3 3、判断定理（续判断定理（续判断定理（续判断定理（续3 3）2024/8/633南晓数信学院证证证证：充分性：充分性：充分性：充分性 (R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R1 1 1 1-R-R-R-R2 2 2 2) ) ) )或或或或(R(R(R(R1 1 1 1RRRR2 2 2 2)(R)(R)(R)(R2 2 2 2-R-R-R-R1 1 1 1) ) ) )成立成立成立成立R R1 1RR2 2R R1 1-R-R2 2R R2 2-R

50、-R1 1R R1 1R R2 2aaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a aaaaaaaaaa a a abbbbbbbbb b b bFFFF+ + + +aaaaaaaaa a a a具有无损联接性具有无损联接性3 3、判断定理（续判断定理（续判断定理（续判断定理（续4 4）2024/8/634南晓数信学院R R1 1RR2 2R R1 1-R-R2 2R R2 2-R-R1 1R R1 1aaaaaaaaaaaabbbbbbR R2 2aaaaaaaaaaaaaaaaaa（R1R2）（R1-R2）证：必要性证：必要性证：必要性证：必要性3

51、3、判断定理（续判断定理（续判断定理（续判断定理（续5 5）2024/8/635南晓数信学院R R1 1RR2 2R R1 1-R-R2 2R R2 2-R-R1 1R R1 1aaaaaaaaaaaaaaaaaaR R2 2aaaaaabbbbbbaaaaaa（R1R2）（R2-R1）证：必要性证：必要性证：必要性证：必要性3 3、判断定理（续判断定理（续判断定理（续判断定理（续6 6）2024/8/636南晓数信学院分解分解分解分解不具有无损联接性不具有无损联接性不具有无损联接性不具有无损联接性举例：举例：举例：举例： 例例例例5.8 5.8 5.8 5.8 设设设设有有有有关关关关系系系

52、系模模模模式式式式R(A,B,C)R(A,B,C)R(A,B,C)R(A,B,C)，函函函函数数数数依依依依赖赖赖赖集集集集F=ABF=ABF=ABF=AB，CBCBCBCB，分分分分解解解解=R=R=R=R1 1 1 1,R,R,R,R2 2 2 2 ，其其其其中中中中R R R R1 1 1 1=AB=AB=AB=AB，R R R R2 2 2 2=BC=BC=BC=BC。检验检验检验检验分解分解分解分解是否具有无是否具有无是否具有无是否具有无损联损联损联损联接性。接性。接性。接性。2024/8/637南晓数信学院三、保持函数依赖集三、保持函数依赖集三、保持函数依赖集三、保持函数依赖集20

53、24/8/638南晓数信学院1 1、定义、定义、定义、定义 设设设设有有有有关关关关系系系系模模模模式式式式R(U,F)R(U,F)R(U,F)R(U,F)，F F F F是是是是R R R R的的的的函函函函数数数数依依依依赖赖赖赖集集集集，RRRR1 1 1 1,R,R,R,R2 2 2 2,R R R Rk k k k 是是是是R R R R上上上上的的的的一一一一个个个个分分分分解解解解。如如如如果果果果所所所所有有有有函函函函数数数数依依依依赖赖赖赖集集集集RiRiRiRi(F(F(F(F) ) ) )（i=1i=1i=1i=1，2 2 2 2，,k,k,k,k）的的的的并并并并集集

54、集集逻逻逻逻辑辑辑辑蕴蕴蕴蕴含含含含F F F F中中中中的的的的每每每每一一一一个个个个函函函函数数数数依依依依赖赖赖赖，则则则则称称称称分分分分解解解解具具具具有有有有依依依依赖赖赖赖保持性，也即保持性，也即保持性，也即保持性，也即分解分解分解分解保持依保持依保持依保持依赖赖赖赖集集集集F F F F。即。即。即。即2024/8/639南晓数信学院对对对对F F F F中每个中每个中每个中每个XY,计算计算计算计算X X X XG G G G+ + + +Y XG+?保持依赖保持依赖保持依赖保持依赖Y Y不保持依赖不保持依赖不保持依赖不保持依赖N N令令令令G= G= G= G= ，验证，

55、验证，验证，验证G G G G =F?=F?2 2 2 2、保持依赖的判断方法、保持依赖的判断方法、保持依赖的判断方法、保持依赖的判断方法实质是看：实质是看：Y在在G中是中是否仍被否仍被X约束着？约束着？2024/8/640南晓数信学院例例例例：设设设设有有有有关关关关系系系系模模模模式式式式R(A,B,C,D,E,P)R(A,B,C,D,E,P)R(A,B,C,D,E,P)R(A,B,C,D,E,P)，R R R R的的的的函函函函数数数数依依依依赖赖赖赖集集集集F=CP,ECD,EA,ABF=CP,ECD,EA,ABF=CP,ECD,EA,ABF=CP,ECD,EA,AB。当当当当将将将将

56、R R R R分分分分解解解解成成成成R1(CP),R2(AE),R3(CDE),R4(BCE)R1(CP),R2(AE),R3(CDE),R4(BCE)R1(CP),R2(AE),R3(CDE),R4(BCE)R1(CP),R2(AE),R3(CDE),R4(BCE)时时时时，判判判判断断断断该该该该分解是否保持依分解是否保持依分解是否保持依分解是否保持依赖赖赖赖性？性？性？性？ R1R1R1R1(F)=CP(F)=CP(F)=CP(F)=CP R2R2R2R2(F)=EA(F)=EA(F)=EA(F)=EA R3R3R3R3(F)=ECD(F)=ECD(F)=ECD(F)=ECD R4R4

57、R4R4(F)=EB(F)=EB(F)=EB(F)=EB无法导出无法导出无法导出无法导出ABAB该分解不保持依赖性该分解不保持依赖性该分解不保持依赖性该分解不保持依赖性举例：举例：举例：举例：2024/8/641南晓数信学院 小小小小 结结结结数据等价数据等价依赖等价依赖等价两个数据库模式的等价性问题两个数据库模式的等价性问题无损联接无损联接保持保持FDFD关系模式分解的两个特性的含义、关系模式分解的两个特性的含义、关系模式分解的两个特性的含义、关系模式分解的两个特性的含义、 判断方法判断方法判断方法判断方法 = R1(U1,F1),R2(U2,F2),Rk(Uk,Fk)注意注意2024/8/642南晓数信学院