第13讲模式分解.ppt

小结 规范化理论为数据库设计提供了理论的指南和工具 对关系模式进行规范化的主要目的是消除数据冗余和更新异常； 规范化是通过模式分解来实现的，分解后的关系模式具有较少的列，能描述的信息也相应的减少了，或者说语义更纯了。 小结 并不是规范化程度越高，模式就越好，而必须结合应用环境和现实世界的具体情况合理地选择数据库模式。 有时出于对数据库性能的考虑而允许数据库中存在数据冗余，来获得比较好的性能。 比如 ： 1）复制某些数据列到一些表中以便更容易地访问而不必进行多表的连接。 2）存储派生数据以加快数据处理过程。 3）撤消某些已分解的关系模式以减少多个表连接的开销。 作业 教材：四（2，4，6） * 无损连接分解 【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。 A B C D E R1(AD) a1 b12 b13 a4 b15 R2(AB) a1 a2 b13 a4 b25 R3(BE) a1 a2 a3 a4 a5 R4(CDE) a1 b42 a3 a4 a5 R5(AE) a1 b52 a3 a4 a5 3）若表有变化，则返回步骤2)，否则算法终止。 若某次修改后，有一行全为a1,a2,…,an，则算法结束。 无损连接分解 【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。 A B C D E R1(AD) a1 b12 b13 a4 b15 R2(AB) a1 a2 b13 a4 b25 R3(BE) a1 a2 a3 a4 a5 R4(CDE) a1 b42 a3 a4 a5 R5(AE) a1 b52 a3 a4 a5 定理： ρ为无损连接分解的充分必要条件是算法终止时，表中有一行为a1,a2,…,an。 判断一个关系模式分解成两个关系模式是否为无损分解的方法 定理： 设ρ={R1(U1)，R2(U2)}是R(U)的一个分解，则ρ为无损分解的充分必要条件为 （U1∩U2）→（U1-U2）∈F+ 或 （U1∩U2）→（U2-U1）∈F+ 无损连接分解 无损连接分解 证明：用检验分解无损算法构造的如下初始表。表中a和b的下标都已省略 [充分性] 因为（U1∩U2）→（U1-U2），则算法8-2终止时，对应于(U1-U2)的bb···b全为a，因此，ρ={R1(U1)，R2(U2)}是R（U）的一个无损连接分解。 [必要性] 若ρ={R1(U1)，R2(U2)}是R（U）的一个无损连接分解，则算法终止时，表中必有一行全为a，假设R2行全为a，则（U1-U2）所对应的元素都应变为a。由于在表中，只有（U1∩U2）所对应的列的元素相同。设U1-U2中有一个属性Ai，则根据算法将Ai所对应的元素都改为a，则必有S→Ai?F+，且S?（U1∩U2）。根据自反律有（U1∩U2）→S；根据传递律有（U1∩U2）→Ai，即Ai?(U1∩U2)+。所以（U1-U2）? (U1∩U2)+ 即（U1∩U2）→ (U1∩U2)是(U1∩U2)所对应的元素都变为a的必要条件。 【例5-13】 设有关系模式R（U，F），U={A,B,C,D,E}，F={A →BC，CD→E，B →D，E →A }。 R的两个分解为ρ1={ R1(A,B,C)，R2(A,D,E)}，ρ2={R1(A,,B,C)，R2(C,D,E)}。试判断ρ1、ρ2是否为无损分解。 无损连接分解 解：对于分解ρ1={ R1（A,B,C），R2（A,D,E）} 因为U1∩U2=A，U1-U2=BC，且A →BC∈F 所以U1∩U2→U1-U2，ρ1为无损分解。 对于分解ρ2={ R1（A,B,C），R2（C,D,E）} 因为U1∩U2=C，U1-U2=AB，U2-U1=DE， 且C →AB? F+ ，C →DE ?F+ （如何来判断？） 即U1∩U2→U1-U2?F+ 或U1∩U2→U2-U1?F+， 所以ρ2为有损分解。 保持函数依赖分解 保持函数依赖 对于关系模式R（U,F），设ρ={ R1（U1,F1），R2（U2,F2）,…,Rn（Un,Fn） }是R的一个分解，若F+=(∪Fi)+，则称分解ρ保持函数依赖。 引理5.