|
|
【定义7.19】关系模式R(U,F)的一个分解ρ是指ρ={R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn)},其中:,并且没有,1≤i,j≤n,Fi是F在Ui上的投影,。
|
|
|
对一个给定的模式进行分解,使得分解后的模式是否与原来的模式等价有三种情况:
|
|
|
|
|
|
|
【定义7.20】ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)}是关系模式R(U,F)的一个分解,若对R(U,F)的任何一个关系r均有r=mρ(r)成立,则称分解ρ具有无损连接性,简称无损分解。其中,。
|
|
|
【定理7.1】关系模式R(U,F)的一个分解ρ={R1(U1,F1),R2(U2,F2)},具有无损连接的充分必要的条件是:U1∩U2→U1-U2∈F+或U1∩U2→U2-U1∈F+。证明略。
|
|
|
|
【定义7.21】设关系模式R(U,F)的一个分解ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)},如果,则称分解ρ保持函数依赖。
|
|
|
|
|
关系模式R(U,F)的一个分解ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)},U={A1,A2,…,An},F={FD1,FD2,…,FDp},并设F是一个最小依赖集,记FDi为Xi→Aij。判断ρ是否无损连接的步骤如下:
|
|
|
步骤1:建立一张n列k行的表,每一列对应一个属性,每一行对应分解中的一个关系模式。若属性Aj∈Ui,则在j列i行上填上aj,否则填上bij;
|
|
|
步骤2:对于每一个FDi做如下操作:找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素,若其中有aij,则全部改为aij,否则全部改为bmli,m是这些行的行号最小值。该步骤执行时注意如下几点:
|
|
|
.如果在某次更改后,有一行成为“a1,a2,…,an”则算法终止,且分解ρ具有无损连接性,否则不具有无损连接性。
|
|
|
.对F中p个FD逐一进行一次这样的处理,称为对F的一次扫描。
|
|
|
步骤3:比较扫描前后的表有无变化,若有变化,则返回步骤2;否则算法终止。
|
|
|
如果发生循环,那么前次扫描至少应使该表减少一个符号,表中符号有限,因此,循环必然终止。
|
|
|
|
【算法7.2】转换成3NF且保持函数依赖的分解算法。
|
|
|
步骤1:对R(U,F)的函数依赖集F进行极小化处理(处理后的结果仍记为F)。
|
|
|
步骤2:找出不在F中出现的属性,将这样的属性构成一个关系模式。把这些属性从U中去掉,剩余的属性仍记为U。
|
|
|
步骤3:若有X→A∈F,且XA=U,则ρ={R},算法终止。
|
|
|
步骤4:否则,对F按具有相同左部的原则分组(假定分为k组),每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若就去掉Ui。由于经过了步骤2,故合并属性集Ui:。于是ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)}构成R(U,F)的一个保持函数依赖的分解。并且,每个Ri(Ui,Fi)均属于3NF且保持函数依赖。
|
|
|
将关系模式转换成3NF且无损连接又保持函数依赖的算法
|
|
|
【算法7.3】将一个关系模式转换成3NF,使它既具有无损连接又保持函数依赖的分解。
|
|
|
|
输出:R(U,F)的一个分解ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)},Ri为3NF,且ρ具有无损连接又保持函数依赖的分解。
|
|
|
|
(1)根据算法7.2求出保持依赖的分解ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)};
|
|
|
(2)判断分解ρ是否具有无损连接性,若有,转(4);
|
|
|
|
|
|
【算法7.4】将关系模式转换成BCNF,使它具有无损连接的分解。
|
|
|
|
输出:R(U,F)的一个分解ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)},Ri为BCNF,且ρ具有无损连接的分解。
|
|
|
|
|
|
(3)若ρ中Ri不属于BCNF,则Ri中必能找到一个函数依赖,且X不是Ri的候选码,将Ri分解为τ={Ri1(XA),Ri2(Ri-A)},并用分解τ代替Ri,转(2)。
|
|
|
|
数据操纵语言(Data Manipulation Language,DML)用来表示用户对数据库的操作请求。一般地,数据操纵语言DML能表示如下的数据库操作:
|
|
|