数据库chp6_副本.ppt

An Introduction to Database System 6.4 模式的分解 把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义 An Introduction to Database System 模式的分解（续） 定义6.16 关系模式RU,F的一个分解： ρ={ R1U1,F1，R2U2,F2，…，RnUn,Fn} U= ∪Ui，且不存在 Ui ? Uj，Fi 为 F在 Ui 上的投影 定义6.17 函数依赖集合{X→Y | X→Y ? F+∧XY ?Ui} 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影 通过以下例子，给出模式分解的相关概念和算法 i=1 n 举例 例：已知R(U,F),U={A,B,C},F={A→B,B→C},并设R有下图所示的当前值r: 下面采用三种不同的方式对R进行分解： 方法1 设ρ1={R1(A,?),R2(B, ?),R3(C,?)},显然，分解后的Fi=?。将r也向各分解后的模式投影，可得： An Introduction to Database System A B C A1 B1 C1 A2 B2 C1 A3 B3 C2 举例（续） R1={A1,A2,A3},R2={B1,B2,B3},R3={C1,C1,C2} 分析此关系模式： （1）显然，已把R中的函数依赖全部丢失； （2）分解后的关系通过自然连接应当恢复原有R的所有信息。即： R1 R2 R3=R1×R2×R3(由于各Ri间无属性相同的列) 可得： A1 B1 C1 A2 B1 C1 A3 B1 C1 A1 B1 C2 A2 B1 C2 A3 B1 C2 A1 B2 C1 A2 B2 C1 A3 B2 C1 A1 B2 C2 A2 B2 C2 A3 B2 C2 A1 B3 C1 A2 B3 C1 A3 B3 C1 A1 B3 C2 A2 B3 C2 A3 B3 C2 结论：此分解不具有无损连接性 An Introduction to Database System 举例（续） 方法2： 设： ρ2={R1({A,B},{A→B} ),R2({A,C},{A→C})},通过将已知关系r在各Ui的投影，可以证明这种分解能够恢复原来的具体关系，即可以保持无损连接性。但分解不保持函数依赖。因为： F1+={A→?,AB→?,B→?,A→A,AB→A,B→B A →B,AB →B,A→AB,AB →AB} F2+={A→?,AC→?,C→?,A→A,AC→A,C→C A →C,AC →C,A→AC,AC →AC} 观察发现：原模式中的函数依赖B→C已不存在，故此分解 不能保持函数依赖性 An Introduction to Database System 举例（续） 方法3 设： ρ3={R1({A,B)},{A→B},R2({B,C},{B→C})}, 可以证明：此方法的分解既能保持无损连接，又能保持函数依赖性 这正是模式分解所希望的 通过此例，可有以下结论 An Introduction to Database System An Introduction to Database System 模式的分解（续） 如果一个分解具有无损连接性，则它能够保证不丢失信息 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。 下面给出各种判定及分解算法 An Introduction to Database System 1、无损连接分解 （1）无损连接的概念： 关系模式R(U,F)的一个分解 ρ={ R1(U1,F1)， R2(U2,F2)， …，Rn(Un,Fn)} 若R与R1、R2、…、Rn自然连接的结果相等，则称关系模式R 的这个分解ρ具有无损连接性（Lossless join） （2）关系R只分解为R1和R2两个子模式的无损连接判定算法： 设有R(U,F), ρ={R1,R2}是R的一个分解，当且仅当 (R1∩R2→(R1-R2) ? F+或(R1 ∩R2)→(R1-R2) ? F+的时， ρ具有无损连接性 1、无损连接分解（续） 例：已知R(A,B,C),F={A→ B,C → B},分解ρ={R1,R