数据库原理-分解算法

依赖集、独立性、无损连接、函数依赖、分离程度

Posted by Kingtous on May 4, 2019

问题条件

fd={abd->e,ab->g,b->f,c->j,cj->i,g->h}

求最小函数依赖集

1.将F中的所有依赖右边化为单一元素 此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足

2.去掉F中的所有依赖左边的冗余属性. 作法是属性中去掉其中的一个,看看是否依然可以推导 此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性 ab->g,也没有 cj->i,因为c+={c,j,i}其中包含i所以j是冗余的.cj->i将成为c->i F={abd->e,ab->g,b->f,c->j,c->i,g->h};

3.去掉F中所有冗余依赖关系. 做法为从F中去掉某关系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->是多余的.需要去掉. 此题如果F去掉abd->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},其中不包含e.所有不是多余的. 同理(ab)+={a,b,f}也不包含g,故不是多余的. b+={b}不多余,c+={c,i}不多余 c->i,g->h多不能去掉. 所以所求最小函数依赖集为 F={abd->e,ab->g,b->f,c->j,c->i,g->h};

验证函数依赖集是否具有无损连接性

图1

转换为3NF保持函数依赖的分解算法

  • 将函数依赖集做极小化处理
  • 把所有没出现在函数依赖集的变量给删除,剩余的属性记作$U$
  • 如果有$X\rightarrow{A} ∈ F$,且$XA=U$,(也就是U只含有X和A),则$ρ=\{R\}$(整个R属性),算法终止
  • 将每一个属性的左右边合并,看一看有没有一个属性包含于另一个属性的,如果有的话,删去少了那部分

参考链接&例题

转换为3NF既具有无损连接性又保持函数依赖的分解算法

第一步:首先用算法1求出R的保持函数依赖的3NF分解,设为q={R1,R2,„,Rk}(这步完成后分解已经是保持函数依赖,但不一定具有保持无损连接)

第二步: 设X是R的码,求出p=q {R(X)}

第三步:若X是q中某个Ri的子集,则在p中去掉R(X)

第四步:得到的p就是最终结果

例题

例题:R(S#,SN,P,C,S,Z) F={S#→SN,S#→P,S#→C,S#→S,S#→Z,{P,C,S}→Z,Z→P,Z→C}

  • 第一步:求出最小FD集

F={S# →SN, S# →P,S# →C, S#→S, {P,C,S→Z, Z →P,Z →C} // S# →Z冗余,FD:最小函数依赖 按具有相同左部分组:q={R1(S#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)} R3是R2的子集,所以去掉R3 q={R1(S#,SN,P,C,S), R2(P,C,S,Z)}

  • 第二步:R的主码为S#,于是p=q {R(X)}={R1(S#,SN,P,C,S), R2(P,C,S,Z), R(S#)}

  • 第三步:因为{S#}是R1的子集,所以从p中去掉R(S#)
  • 第四步:p ={R1(S#,SN,P,C,S), R2(P,C,S,Z)}即最终结果

什么是数据独立性,如何实现?

数据独立性是指应用程序和数据之间相互独立、不受影响,即数据结构的修改不会引起应用程序的修改.

数据独立性包括:物理数据独立性和逻辑数据独立性.物理数据独立性是指数据库物理结构改变时不必修改现有的应用程序.逻辑数据独立性是指数据库逻辑结构改变时不用改变应用程序.数据独立性是由DBMS 的二级睁像功能来实现的.当整个系统要求改变模式时(增加记录类型、增加数据项,由DBMS对各个外模式/模式的映像做相应改变,从而保证了数据的逻辑独立性.当数据的存储结构改变时,由DBMS对模式/内模式的映像做相应改变,从而保证了数据的物理独立性.

候选码求解算法

候选码求解算法

§分析:

对于给定的关系模式R<U, F>,依照函数依赖集F将U中的属性分为以下四类:

​ L类属性: 在F中只出现在函数依赖的左部的属性;

​ R类属性: 在F中只出现在函数依赖的右部的属性;

​ LR类属性: 分别出现在F中的函数依赖左部和右部的属性;

​ N类属性: 不在F中的函数依赖中出现的属性。

§结论:

① L类属性和N类属性必包含于任一候选码中;

​ ② R类属性必不包含于任何候选码中;

​ ③ LR类属性不能确定是否在码中。

候选码求解算法涉及到的两个推论

§推论1:关系模式R(U,F),若X是L类属性,且x+包含了R的全部属性,则x是R的惟一候选码。

§推论2:关系模式R(U,F),若X是L类、N类组成的属性集,且x+包含了R的全部属性,则x是R的惟一候选码。

设R(A,B,C,D,E,P),G={A→D, E→D, D→B, BC→D, DC→A},求R的所有候选码。

解:L类属性:C,E N类属性:p R类属性:无 LR类属性:A,B,D

​ (CEP)+=ABCDEP

​ ∴ CEP是R的惟一候选码

算法

(1) 依照函数依赖集F将R中的所有属性分为L类、R类、LR类和N类 属性,令X为L、N类属性的集合,Y为LR类属性集合;

(2) 若XF+=U,则X为R的唯一候选码,结束;否则转(3);(P191,算法6.1)

(3) 逐一取Y中的单一属性A,若(XA)F+=U,则XA为候选码 ,

令Y=Y-{A} ,转(4);

(4)若已找出所有候选码,则转(5)否则再依次取Y中的任意两个、三个……属性,与X组成属性组XZ ,若(XZ)F+ =U, 且XZ不包含已求得的候选码,则XZ为候选码。

(5)算法结束,输出结果。

候选码例题

求解分离程度

参考

3NF既具有无损连接性又保持函数依赖的分解算法