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

南晓数信学院 第3讲 关系模式的分解 主要内容 模式分解 无损联接分解 保持函数依赖集 1、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} 一、模式分解 2、分解定义 P109 经过不适当的分解后再连接，将恢复不了原来信息 关系模式分解例： 关系模式：学生（学号，系别，系主任） 函数依赖集：F={学号→系别，系别-系主任} 分解1： ρ1={R1(学号)，R2(系别)，R3(系主任)} 不能连接为原关系实例 F1=F2=F3=φ ，函数依赖不保持 分解2 ρ2={P(学号，系别)，R(学号，系主任)}F1={学号→系别}，F2={学号→系主任}能连接为原关系实例，但依赖约束不能恢复（ 系别→系主任） 分解3 ρ3={P(学号，系属)，R(系属，主任)}F1={学号→系属}，F2={系属→主任} 既能连接为原关系，又能保持函数依赖约束 思考： 两个问题： 二、无损联接分解 二、无损联接分解 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,一个不少,一个不多) 输入：关系模式R(A1,…,An)， 函数依赖集F， R的一个分解ρ＝(R1,…,Rk)。 输出：ρ是否为无损联接的判断。 方法: （1）构造一个k行n列表S，其中： （2）依据函数依赖集F进行修正：X→Y （3）判断条件： *补充：关系分解无损连接性判别算法的正确性证明 引理1 算法5.2的初始矩阵有性质: 任取j,第j行对Rj的投影元素全是a.?（事实上，这是由算法的初始化步骤所决定的。） 引理2 执行算法5.2过程中,矩阵的每个符号a不可能变为其它符号.（因算法规则是‘若列含a则全列改为a,否则全列取为最小行标’ ） 引理3 算法5.2终止矩阵有性质: 任意j,第j行对Rj的投映元素全是a.(?事实上，这由引理1和引理2所决定 ) 引理4 算法5.2的终止矩阵作为关系实例必然满足函数依赖集F.（事实上,算法的实质是检查初始矩阵作为关系实例是否满足F?的每个函数依赖.若不满足某个函数依赖,则修改相关元素,?使矩阵满足这个函数依赖,故终止矩阵必满足F.） 定理1 关系R的分解ρ具无损连接性的充要条件是算法5.2的终止矩阵r有一行的符号全是a. 证明必要性:若终止矩阵无全a的行,断言ρ不具无损连接性.一方面, 由引理4,终止矩阵r必满足函数依赖集F,且无全a的行.另一方面,由引理3,终止矩阵r的第j行对Rj的投映元素全是a( 任取j),故Mρ(r)=∏R1(r)∞...∞∏Rk(r)必含全a行.故r≠Mρ(r).故断言真证明充分性:若终止矩阵有一行全a,往证ρ具无损连接性.（……) 设有关系模式R(U,F)，F是R的属性集U上的函数依赖集，ρ=（R1,R2）是R的一个分解，当且仅当 （R1∩R2）→（R1-R2） 或（R1∩R2）→（R2-R1）属于F+ 时，ρ具有无损联接性。 证：充分性 (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(B