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

3NF既具有无损连接性又保持数依赖的分解算法 ? 构造一个初始的二维，若“属性”属求最小函数依赖集分三步: ，否则填b。 于“模式”中的属性，则填ajij1.将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}; ? 根据A?C，对上表进行处理，由于属3.去掉F中所有冗余依赖关系. 性列A上第1、2、5行相同均为a，所以1做法为从F中去掉某关系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明将属性列C上的b、b、b改为同一个符132353 号b(取行号最小值)。 x->是多余的.需要去掉. 13此题如果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多不能去掉. ? 根据B?C，对上表进行处理，由于属所以所求最小函数依赖集为 F={abd->e,ab->g,b->f,c->j,c->i,g->h}; 性列B上第2、3行相同均为a，所以将属2 性列C上的b、b改为同一个符号b(取133313转换为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} ? 根据C?D，对上表进行处理，由于属 , 第一步:求出最小FD集:F={S# ?SN, S# ?P,S# ?C, S#?S, {P,C,S?Z, Z ?P,Z 性列C上第1、2、3、5行相同均为b，13 C} // S# ?Z冗余，FD:最小函数依赖 ?所以将属性列D上的值均改为同一个符号 按具有相同左部分组:q={R1(S#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)} a。 4 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)}即最终结果 ? 根据DE?C，对上表进行处理，由于属 性列DE上第3、4、5行相同均为aa，所45判别一个分解的无损连接性 以将属性列C上的值均改为同一个符号 a。 3举例2:已知R，U={A,B,C,D,E}，F={A?C,B?C,C?D,DE?C,CE?A}，R的一个分解为 R(AD)，R(AB)，R(BE)，R(CDE)，R(AE)，判断这个分解是否具有无损连接性。 12345 解:用判断无损连接的算法来解。 计算(AB)F1+:设X(0)=AB 计算X(1):扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不? 根据CE?A，对上表进行处理，由于到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。 属性列CE上第3、4、5行相同均为aa，35 所以将属性列A上的值均改为同一个符 (AB)F1+= AB不包含C，故AB?C不是冗余的函数依赖，不能从F1中去掉。 号a。 1 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} aaaaa，则算法终止。且分解具有无12345 计算(CG)F2+:设X(0)=CG 损连接性。 计算X(1):扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一 个C?A函数依赖。故有X(1)=X(0)?A=CGA=ACG。 求属性集合X关于函数依赖集F的闭包X+ 【算法5.1】 计算属性集,关于,的闭包,，。 计算X(2):扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到输入:属性集,为,的子集，函数依赖集,。 一个CG?D函数依赖。故有X(2)=X(1)?D=ACDG。 输出:,，。 步骤: 计算X(3):扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得(1) 置初始值 A=ф，A*=X; 到两个ACD?B和D?E函数依赖。故有X(3)=X(2)?BE=ABCDEG，因为X(3)=U，算法终止。 (2) 如果A?A*，置A=A*，否则转(4); (3) A*，置A*=A*?Z。全部搜索完,转(2);,依次检查F中的每一个函数依赖Y?Z，若Y (CG)F2+=ABCDEG包含B，故CG?B是冗余的函数依赖，从F2中去掉。 (4) 输出A*，即为X+。 【例】 已知关系模式R(A,B,C,D,E)，F={AB?C,B?D,C?E,EC?B,AC?B}是函数依赖集， C(设CG?D为冗余的函数依赖，则去掉CG?D，得:求(AB)+。 F3={AB?C,D?E,D?G,C?A,BE?C,BC?D,ACD?B,CE?A,CE?G} 依算法2.1解: (1) 置初始值 A=ф，A*=AB; 计算(CG)F3+:设X(0)=CG (2) 因A?A*，置A=AB; (3) 第一次扫描F，找到AB?C和B?D，其左部,AB，故置A*=ABCD。搜索完,转(2); 计算X(1):扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一(2) 因A?A*，置A=ABCD; 个C?A函数依赖。故有X(1)=X(0)?A=CGA=ACG。 (3) 第二次扫描F，找到C?E和AC?B，其左部, ABCD，故置A*=ABCDE。搜索完,转(2); (2) 因A?A*，置A=ABCDE; 计算X(2):扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为(3) 第三次扫描F，找到EC?B，其左部 , ABCDE，故置A*=ABCDE。搜索完,转(2); 找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3+=ACG。 (2) 因A=A*，转(4); (4) 输出A*，即(AB)+=ABCDE。 (CG)F3+=ACG不包含D，故CG?D不是冗余的函数依赖，不能从F3中去掉。 举例:已知关系模式R，U={A,B,C,D,E,G}， D(设CE?A为冗余的函数依赖，则去掉CE?A，得:F={AB?C,D?EG,C?A,BE?C,BC?D,CG?BD,ACD?B,CE?AG}，求F的最小函数依赖集。 F4={AB?C,D?E,D?G,C?A,BE?C,BC?D,CG?D,ACD?B,CE?G} 解1:利用算法求解，使得其满足三个条件 计算(CG)F4+:设X(0)=CE ? 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为: F={AB?C,D?E,D?G,C?A,BE?C,BC?D,CG?B,CG?D,ACD?B,CE?A,CE?G} 计算X(1):扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一 个C?A函数依赖。故有X(1)=X(0)?A=CEA=ACE。 ? 去掉F中多余的函数依赖 计算X(2):扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到 A(设AB?C为冗余的函数依赖，则去掉AB?C，得:一个CE?G函数依赖。故有X(2)=X(1)?G=ACEG。 F1={D?E,D?G,C?A,BE?C,BC?D,CG?B,CG?D,ACD?B,CE?A,CE?G} 计算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对模式,内模式的映像做相应改变，从而保证了数据的物理独立性(