关系模式分解

第3讲关系模式的分解第5章关系数据库模式设计1主要内容模式分解无损联接分解保持函数依赖集2ρR(U,F)U=U1∪U2∪…∪Uk对于任意的i,j(1≤i,j≤k)，不成立Ui

UjFi是F在Ui上的投影={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)}R(U,F)的一个分解也称数据库模式一、模式分解1、分解定义3

设有关系模式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}2、F在Ui上的投影4两个问题：思考：？R(U)R1(U1),R2(U2),…,Rk(Uk)FF1,F2,…,Fk？数据等价依赖（语义）等价无损联接保持依赖5二、无损联接分解6二、无损联接分解1、定义设有关系模式R(U,F)，ρ=（R1,R2…,Rk）是R的一个分解。如果对于R的任一满足F的关系r，把r在ρ上的投影的联接表达式记为：

m

(r)＝πR1(r)∞πR2(r)∞…∞πRk(r)如果r＝m

(r)成立，则称这个分解ρ是满足依赖集F的无损联接分解。7输入：关系模式R(A1,…,An)，函数依赖集F，R的一个分解ρ＝(R1,…,Rk)。输出：ρ是否为无损联接的判断。方法:2、算法5.2判断一个分解的无损联接性8s[i,j]Aj在Ri中,ajAj不在Ri中,bij（1）构造一个k行n列表S，其中：2、算法5.2判断一个分解的无损联接性（续1）9（2）依据函数依赖集F进行修正：X→Y若Y值中有

aj，其它也改为aj若Y值中无aj，其它改为bij（下标小）FD的选择顺序可随意2、算法5.2判断一个分解的无损联接性（续2）10a1ana2……分解ρ具有无损联接性（3）判断条件：2、算法5.2判断一个分解的无损联接性（续3）11第一步：构造表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)}，检验分解ρ是否具有无损联接性。12第二步：修正①A→C例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)}，检验分解ρ是否具有无损联接性。13第二步：修正①A→C例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)}，检验分解ρ是否具有无损联接性。14第二步：修正②B→C例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)}，检验分解ρ是否具有无损联接性。15第二步：修正②B→C例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)}，检验分解ρ是否具有无损联接性。16第二步：修正③C→D例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)}，检验分解ρ是否具有无损联接性。17第二步：修正③C→D例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)}，检验分解ρ是否具有无损联接性。18第二步：修正④DE→C例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)}，检验分解ρ是否具有无损联接性。19第二步：修正④DE→C例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)}，检验分解ρ是否具有无损联接性。20第二步：修正⑤CE→A例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)}，检验分解ρ是否具有无损联接性。21第二步：修正⑤CE→A例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)}，检验分解ρ是否具有无损联接性。22第三步：判断分解ρ具有无损联接性例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)}，检验分解ρ是否具有无损联接性。23设有关系模式R(U,F)，F是R的属性集U上的函数依赖集，ρ=（R1,R2）是R的一个分解，当且仅当

（R1∩R2）→（R1-R2）或（R1∩R2）→（R2-R1）时，ρ具有无损联接性。3、判断定理24证：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…bbb…b∈F3、判断定理（续1）25证：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…b∈Faa…a3、判断定理（续2）26证：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…bbb…b∈F+3、判断定理（续3）27证：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…b∈F+aa…aρ具有无损联接性3、判断定理（续4）28（R1∩R2）→（R1-R2）证：必要性3、判断定理（续5）29（R1∩R2）→（R2-R1）证：必要性3、判断定理（续6）30分解ρ不具有无损联接性举例：

例5.8设有关系模式R(A,B,C)，函数依赖集F={A→B，C→B}，分解ρ={R1,R2}，其中R1=AB，R2=BC。检验分解ρ是否具有无损联接性。31三、保持函数依赖集321、定义设有关系模式R(U,F)，F是R的函数依赖集，ρ＝{R1,R2,…,Rk}是R上的一个分解。如果所有函数依赖集πRi(F)（i=1，2，…,k）的并集逻辑蕴含F中的每一个函数依赖，则称分解ρ具有依赖保持性，也即分解ρ保持依赖集F。即33对F中每个X→Y,计算XG+YXG+?保持依赖Y不保持依赖N令G=，验证G

=F?2、保持依赖的判断方法34例：设有关系模式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