第16讲_模式分解.pptVIP

6.4 模式的分解 模式分解的定义 无损连接分解 保持函数依赖的分解 模式分解的算法 一、关系模式分解的定义 关系模式RU,F的一个分解是指 ρ={R1U1,F1, R2U2,F2,…, RnUn,Fn} 其中U= U1∪U2∪…∪Un ，并且没有Ui ? Uj, i≠j ， Fi是F在Ui上的投影。 F在Ui上的投影（记作∏Ui F）是指 函数依赖集合{X→Y| X→Y∈F+∧XY?Ui}的一个覆盖Fi。 例2：已知关系模式RU,F,其中 U＝{Sno,Sdept,Sloc},F={Sno-Sdept,Sdept-Sloc}. 分析R属于？NF，并分析R的各种模式分解方法。 2.分解2： R1 R2 3.分解3： R1 R2 二、无损连接的分解 引入一个记号：设ρ={R1, R2,…, Rk} 是RU,F的一个分解，r是RU,F的一个关系。定义mρ(r)= 即mρ(r)是r在ρ中各关系模式上投影的自然连接。 定义：ρ={R1U1,F1,…,RkUk,Fk}是RU,F的一个分解.若对R的任一关系r都有r=mρ(r)，则称?具有无损连接性。简称?为无损分解。 判断一个分解是否具有无损连接性 方法一： 定理：已知RU,F的一个分解ρ={R1U1,F1,R2U2,F2}, ρ具有无损连接性的充要条件是 (U1∩U2)→(U1-U2)∈F+ 或(U1∩U2)→(U2-U1)∈F+ 证明从略。 ρ={R1U1,F1,…,RKUK,FK}是RU,F的一个分解，U={A1,…,An}, F={FD1,…,FDm}，并设F是一极小依赖集， 记FDi为 Xi－Ali 1）建立一个n列k行的表。每列对应一个属性Aj ，每行对应一个子关系模式的属性集Ui 。若Aj属于Ui，则在第i行j列交叉处填上aj，否则填上bij； 2）对每个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行，考察这些行中li列的元素，若其中有ali则全部改为ali，否则全部改为bmli；m是这些行的行号最小值（若某个btli被更动 ，那么该表的li列中凡是btli的符号均作相应更改）。 若有一行成为a1，…，an。则算法终止，分解具备无损连接性。 对F中个FD逐一进行上述处理，称为对F的一次扫描。 3）比较扫描前后，若表有变化，则返回2）；若表无变化，则算法终止，分解不具备无损连接性。 三、保持函数依赖的分解 定义:设ρ={R1U1, F1,…, RkUk,Fk}是RU,F的一 个分解，若 , 则?保持函数依赖。 其中Fi＝∏Ui F. 四、模式分解的算法 算法1（合成法)： 将RU,F分解为3NF并保持函数依赖的算法 ①对RU,F中的函数依赖集F进行极小化处理（处理后的结果仍记为F）； ②找出不在F中出现的属性，把它们构成一个关系模式。并把这些属性从U中去掉（剩余的属性仍记为U）； ③若X→A∈F且XA=U,则ρ={R}，算法终止； ④否则，对F按具有相同左部的原则分组，每组函数依赖Fi所涉及的全部属性形成一个属性集Ui；若 Ui包含于Uj就去掉Ui。 ⑤停止，是3NF且具有依赖保持性。 四、模式分解的算法 算法3（分解法）：分解为BCNF,且具有无损连接性。 步骤： ①令ρ={RU,F} ②检查：若ρ中所有关系模式均属于BCNF，则算法终止。 ③若ρ中RiUi,Fi不属于BCNF,则必有X→A∈Fi+,且X不是Ri的码，显然AX是Ui的真子集。对Ri进行分解:{Ri1,Ri2},其中Ui1=XA, Ui2=Ui-{A},用分解{Ri1Ui1,Fi1 , Ri2Ui2,Fi2 }代替RiUi,Fi,转② 小结 关系模式设计最低要求为1NF 范式级别并非越高越好： 大多分解到3NF即可满足要求； 依用户效率、空间、访问特征确定； 一、函数依赖 1.FD定义：若r中任意两个元组t，s，如果t[x]=s[x]导致t[y]=s[y] ,则x→y。 2.FD的逻辑蕴涵，F+ ={X→Y| X→Y是从F用推理系统推出} 3.Armstrong推理系统 自反，若Y X, 则X→Y 增广，若X→Y 则XZ→YZ 传递，若X→Y,Y→Z, 则X→Z 推论： 合并，若X→Y ,X→Z, 则X→YZ 分解，若X→YZ, 则X→Y,X→Z 伪传递，若X→Y,WY→Z，则XW→Z