第五章第3讲关系模式分解.ppt

第3讲 关系模式的分解 主要内容 模式分解 无损联接分解 保持函数依赖集 一、模式分解 1、分解定义 2、F在Ui上的投影 设有关系模式R(U,F)，F是R的函数依赖 集，Z是U的子集，则把F＋中所有满足XY?Z的函 数依赖X→Y组成的集合，称为依赖集F在属性集 Z上的投影，记为πZ(F)： πZ(F)＝{X→Y|X→Y∈F＋且XY?Z} 思考： 两个问题： 二、无损联接分解 二、无损联接分解 1、定义 设有关系模式R(U,F)，ρ=（R1,R2…,Rk）是R的一个分解。如果对于R的任一满足F的关系r，把r在ρ上的投影的联接表达式记为： m?(r)＝πR1(r)∞πR2(r)∞…∞πRk(r) 如果r＝m?(r)成立，则称这个分解ρ是满足依赖集F的无损联接分解。 输入：关系模式R(A1,…,An)， 函数依赖集F， R的一个分解ρ＝(R1,…,Rk)。 输出：ρ是否为无损联接的判断。 方法: （1）构造一个k行n列表S，其中： （2）依据函数依赖集F进行修正：X→Y （3）判断条件： 设有关系模式R(U,F)，F是R的属性集U上的函数依赖集，ρ=（R1,R2）是R的一个分解，当且仅当 （R1∩R2）→（R1-R2） 或（R1∩R2）→（R2-R1） 时，ρ具有无损联接性。 证：充分性 (R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立 证：充分性 (R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立 证：充分性 (R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立 证：充分性 (R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立 证：必要性 证：必要性 举例： 例5.8 设有关系模式R(A,B,C)，函数依赖集F={A→B，C→B}，分解ρ={R1,R2}，其中R1=AB，R2=BC。检验分解ρ是否具有无损联接性。 三、保持函数依赖集 1、定义 设有关系模式R(U,F)，F是R的函数依赖集，ρ＝{R1,R2,…,Rk}是R上的一个分解。如果所有函数依赖集πRi(F)（i=1，2，…,k）的并集逻辑蕴含F中的每一个函数依赖，则称分解ρ具有依赖保持性，也即分解ρ保持依赖集F。即 举例： 例：设有关系模式R(A,B,C,D,E,P)，R的函数依赖集F={C→P,EC→D,E→A,A→B}。当将R分解成{R1(CP),R2(AE),R3(CDE),R4(BCE)}时，判断该分解是否保持依赖性？ πR1(F)={C→P} πR2(F)={E→A} πR3(F)={EC→D} πR4(F)={E→B} 小 结 分解ρ不具有无损联接性 对F中每个X→Y,计算XG+ Y ? XG+? 保持依赖 Y 不保持依赖 N 令G= ，验证G?=F? 2、保持依赖的判断方法 无法导出A→B 该分解不保持依赖性 * * 第5章 关系数据库模式设计 ρ R(U,F) U=U1∪U2∪…∪Uk 对于任意的i,j(1≤i, j≤k)，不成立Ui?Uj Fi是F在Ui上的投影 = {R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)} R(U,F)的一个分解 也称数据库模式 R(U) R1(U1), R2(U2),…, Rk(Uk) F F1, F2,…, Fk 数据等价 依赖（语义）等价 无损联接 保持依赖 2、算法5.2 判断一个分解的无损联接性 … … Ri Aj Rk … R1 An … A1 s[i,j] Aj在Ri中, aj Aj不在Ri中, bij 2、算法5.2 判断一个分解的无损联接性（续1） … Y Ri … Rk … R1 … X … 若Y值中有 aj，其它也改为aj 若Y值中无 aj，其它改为bij（下标小） FD的选择顺序可随意 2、算法5.2 判断一个分解的无损联接性（续2） … Y Ri … Rk … R1 … X … a1 an a2 … … 分解ρ具有无损联接性 2、算法5.2 判断一个分解的无损联接性（续3） a5 b54 b53 b52 a1 R5 a5 a4 a3 b42 b41 R4 a5 b34 b33 a2 b31 R3 b25 b24 b23 a2 a1 R2 b15 a4 b13 b12 a1 R1 E D C B A 第一步：构造表S 例 5.7 设R(ABCDE)，F={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，检