函数依赖的公理系统剖析.pptVIP

6.4.1 模式分解的三个定义 对一个模式的分解是不唯一的，但是分解前后的两个模式应等价。 对“等价”的概念有三种不同的定义(也称分解的标准、分解的特性或分解的目标): (1)分解具有无损连接性(Lossless join)； (2)分解要保持函数依赖(Preserve dependency) (3)分解既要保持函数依赖，又要具有无损连接性。 模式分解的三个定义 按照不同的分解准则，模式所能达到的分离程度各不相同，各种范式就是对分离程度的测度。 进一步讨论: (1) “无损连接性”和“保持函数依赖”的含义? 如何判断? (2) 对不同的分解等价定义，分离后的关系模式的范式级别。 (3) 如何实现分离，分解的算法。 模式分解中的问题: 有损分解 R(A, B, C) A B C 1 1 2 2 2 1 A B 1 1 2 2 B C 1 2 2 1 A B C 1 1 2 2 2 1 ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) R(A, B, C) A B C 1 1 1 2 1 2 A B 1 1 2 1 B C 1 1 1 2 A B C 1 1 1 1 1 2 2 1 1 2 1 2 ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) 无损 分解 有损 分解 模式分解中的问题: 不保持函数依赖 A B C a1 b1 c1 a2 b1 c1 a3 b2 c2 a4 b3 c1 {A ? B, B ? C} A a1 a2 a3 a4 B b1 b2 b3 C c1 c2 各列值 A B a1 b1 a2 b1 a3 b2 a4 b3 A C a1 c1 a2 c1 a3 c2 a4 c1 = A B C a1 b1 c1 a2 b1 c1 a3 b2 c2 a4 b3 c1 分解 若插入 将违反 B ? C 该分解保持A ? B，而不保持 B ? C，但是是无损分解 { A ? B } a5 b3 a5 c3 a5 b3 c3 模式分解中存在的问题: 例 A B a1 b1 a2 b1 a3 b2 a4 b3 B C b1 c1 b2 c2 b3 c1 A C a1 c1 a2 c1 a3 c2 a4 c1 B C b1 c1 b2 c2 b3 c1 = = A B C a1 b1 c1 a1 b3 c1 a2 b1 c1 a2 b3 c1 a3 b2 c2 a4 b1 c1 a4 b3 c1 A B C a1 b1 c1 a2 b1 c1 a3 b2 c2 a4 b3 c1 该分解保持B ? C，而不保持A ?B, 且是有损分解 该分解保持函数依赖, 且是无损分解 { B ? C } { A ? B } { B ? C } 6.4.2 分解的无损连接性和保持函数依赖性 如果一个分解具有无损连接性，则它能够保证不丢失信息。 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。 分解的无损连接性定义 定义记号 m?( r) 关系模式 RU , F ，U = Ui ， ? ={R1U1,F1,R2U ,F2,… ,RnUn, Fn}是RU , F的一个分解，r 是RU , F的一个关系, 定义： m?(r) = ∏Ri(r) 是r在ρ中各关系模式上投影的连接。这里， ∏Ri(r) ={t[Ui]|t∈r} 定义6.18 R(U,F)的一个分解?是无损连接分解： r = m?(r) 1 i ∪ n = 判无损连接性的方法(chase过程) 算法6.2 判别一个分解的无损连接性。 定理6.7 无损连接分解的充分必要条件 (chase过程) 。 方法：构造一个表格，根据函数依赖变化表格，能够变出一行全为a，则是无损连接。 例5: 设 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 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 A B C D E ABC a1 a2 a3 b14 b1