北航数据库原理与技术第六章new.ppt

* * * 关系模式的分解算法 模式分解 函数依赖集合Fi = {X?Y | X?Y?F+ ? XY ? Ui}称为F在Ui上的投影 关系模式RU , F的一个分解是指 ? = {R1U1 , F1 , R2U2 , F2, … , RnUn , Fn} 其中U = Ui ，并且没有Ui ? Uj ，1≤i，j ≤n， Fi是F在Ui上的投影。 设? = {R1U1 , F1 , R2U2 , F2, … , RnUn, Fn}是R(U，F)的一个分解，r是R(U，F)的一个关系，定义m? (r) = ?Ri（r），即m? （r）是r在?中各关系模式投影上的连接。这里?Ri（r）={t.Ui|t?r} 关系模式的分解算法 一般定义 关系模式RU , F ，U = Ui ， ? = {R1U1 , F1 , R2U2 , F2, … , RnUn , Fn}是RU , F的一个分解，r是RU , F的一个关系。定义m?(r) = ∏Ri(r) ,若对于RU , F的任一个关系r，都有r = m?(r)，则称?是RU , F的一个无损连接分解。 关系模式的分解算法 算法：（判别一个分解的无损连接性） U={A1, A2, … , An}，F＝{FD1，FD2，，FD ?}不妨设F是一个最小依赖集，记FDi为Xi ? Aj ? = {R1U1 , F1 , R2U2 , F2, … , RkUk , Fk} ⒈建立一个n列k行的矩阵。每一列对应一个属性，每一行对应于分解中的一个关系模式。若属性Aj 属于Ui ，则在j列i行交叉处填上aj ，否则填上bij 。 {Cij | 若Aj ? Ui , Cij = aj , 否则Cij = bij} 关系模式的分解算法 ⒉对每一个FDi做下列操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中j列的元素，若其中有aj，则全部改为aj；否则全部改为bmj；m是这些行的行号最小值。 如果在某次更改之后，有一行成为a1, a2 , … , an 。则算法终止， ?为无损分解，否则为有损分解。 关系模式的分解算法 3. 比较扫描前后，表有无变化。如有变化，则返回第二步，否则算法终止。 关系模式的分解算法 示例：U={A,B,C,D,E}, F={AB?C, C?D,D?E} ? ={(A, B, C), (C, D), (D, E)} A B C D E ABC a1 a2 a3 b14 b15 CD b21 b22 a3 a4 b25 DE b31 b32 b33 a4 a5 A B C D E ABC a1 a2 a3 b14 b15 CD b21 b22 a3 a4 b25 DE b31 b32 b33 a4 a5 AB?C A B C D E ABC a1 a2 a3 a4 b15 CD b21 b22 a3 a4 b25 DE b31 b32 b33 a4 a5 C?D A B C D E ABC a1 a2 a3 a4 a5 CD b21 b22 a3 a4 a5 DE b31 b32 b33 a4 a5 D?E 关系模式的分解算法 U={A,B,C,D,E}, F={A?C, B?C, C?D, DE?C, CE?A} ? ={R1(A, D), R2(A, B), R3(B, E), R4 (C, D, E), R5(A, E)} 关系模式的分解算法 A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b23 b24 b25 R3(B, E) b31 a2 b33 b34 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b53 b54 a5 关系模式的分解算法 A?C A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b13 b24 b25 R3(B, E) b31 a2 b33 b34 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b13 b54 a5 关系模式的分解算法 B?C A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b13 b24 b25 R3(B, E) b31 a2 b13 b34 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b13 b54 a5 关系模式的分解算法 C?D A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1