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

求最小函数依赖集分三步: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-iF={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};转换为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的子集，所以去掉R3q={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)}即最终结果判别一个分解的无损连接性举例2：已知RU,F，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。解：用判断无损连接的算法来解。①构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。②根据A→C，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13（取行号最小值）。③根据B→C，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13（取行号最小值）。④根据C→D，对上表进行处理，由于属性列C上第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。⑤根据DE→C，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。⑥根据CE→A，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。⑦通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。求属性集合X关于函数依赖集F的闭包X+【算法5.1】计算属性集Ｘ关于Ｆ的闭包Ｘ＋。输入：属性集Ｘ为Ｕ的子集，函数依赖集Ｆ。输出：Ｘ＋。步骤：(1)置初始值A=ф，A*=X；(2)如果A≠A*，置A=A*，否则转(4)；(3)A*，置A*=A*∪Z。全部搜索完,转(2)；依次检查F中的每一个函数依赖Y→Z，若Y(4)输出A*，即为X+。【例】已知关系模式R(A,B,C,D,E)，F={AB→C,B→D,C→E,EC→B,AC→B}是函数依赖集，求(AB)+。依算法2.1解：(1)置初始值A=ф，A*=AB；(2)因A≠A*，置A=AB；(3)第一次扫描F，找到AB→C和B→D，其左部AB，故置A*=ABCD。搜索完,转(2)；(2)因A≠A*，置A=ABCD；(3)第二次扫描F，找到C→E和AC→B，其左部ABCD，故置A*=ABCDE。搜索完,转(2)；(2)因A≠A*，置A=ABCDE；(3)第三次扫描F，找到EC→B，其左部ABCDE，故置A*=ABCDE。搜索完,转(2)；(2)因A=A*，转(4)；(4)输出A*，即(AB)+=ABCDE。举例：已知关系模式R，U={A,B,C,D,E,G}，F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}，求F的最小函数依赖集。解1：利用算法求解，使得其满足三个条件①利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}②去掉F中多余的函数依赖A．设AB→C为冗余的函数依赖，则去掉AB→C，得：F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}计算(AB)F1+：设X(0)=AB计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。(AB)F1+=AB不包含C，故AB→C不是冗余的函数依赖，不能从F1中去掉。B．设CG→B为冗余的函数依赖，则去掉CG→B，得：F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G}计算(CG)F2+：设X(0)=CG计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CG→D函数依赖。故有X(2)=X(1)∪D=ACDG。计算X(3)：扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得到两个ACD→B和D→E函数依赖。故有X(3)=X(2)∪BE=ABCDEG，因为X(3)=U，算法终止。(CG)F2+=ABCDEG包含B，故CG→B是冗余的函数依赖，从F2中去掉。C．设CG→D为冗余的函数依赖，则去掉CG→D，得：F3={AB→C,D→E,D→G,C→A,BE→C,BC→D,ACD→B,CE→A,CE→G}计算(CG)F3+：设X(0)=CG计算X(1)：扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。计算X(2)：扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3+=ACG。(CG)F3+=ACG不包含D，故CG→D不是冗余的函数依赖，不能从F3中去掉。D．设CE→A为冗余的函数依赖，则去掉CE→A，得：F4={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}计算(CG)F4+：设X(0)=CE计算X(1)：扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CEA=ACE。计算X(2)：扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到一个CE→G函数依赖。故有X(2)=X(1)∪G=ACEG。计算X(3)：扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个CG→D函数依赖。故有X(3)=X(2)∪D=ACDEG。计算X(4)：扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个ACD→B函数依赖。故有X(4)=X(3)∪B=ABCDEG。因为X(4)=U，算法终止。(CE)F4+=ABCDEG包含A，故CE→A是冗余的函数依赖，从F4中去掉。③去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于C→A，函数依赖ACD→B中的属性A是多余的，去掉A得CD→B。故最小函数依赖集为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}什么是数据独立性？数据库系统如何实现数据独立性？数据独立性是指应用程序和数据之间相互独立、不受影响，即数据结构的修改不会引起应用程序的修改．数据独立性包括：物理数据独立性和逻辑数据独立性．物理数据独立性是指数据库物理结构改变时不必修改现有的应用程序．逻辑数据独立性是指数据库逻辑结构改变时不用改变应用程序．数据独立性是由DBMS的二级睁像功能来实现的．当整个系统要求改变模式时（增加记录类型、增加数据项，由DBMS对各个外模式／模式的映像做相应改变，从而保证了数据的逻辑独立性．当数据的存储结构改变时，由DBMS对模式／内模式的映像做相应改变，从而保证了数据的物理独立性．