[精华]闭包和函数最小依靠集的求法(含例题)下载_Word模板_4

is_321635

暂无简介

[精华]闭包和函数最小依靠集的求法(含例题)[精华]闭包和函数最小依靠集的求法(含例题) 一、等价和覆盖 ++ 定义:关系模式R上的两个依赖集F和G，如果F=G，则称F和G是等价的，记做F?G。若F?G，则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。二、最小函数依赖集定义:如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 ? F中的任何一个函数依赖的右部仅含有一个属性; ? F中不存在这样一个函数依赖X?A，使得F与F-{X?A}等价; ? F中不存在这样一个函数依赖X?A，X有真子集Z使得F-{X?A}?...

[精华]闭包和函数最小依靠集的求法(含例

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

) 一、等价和覆盖 ++ 定义:关系模式R上的两个依赖集F和G，如果F=G，则称F和G是等价的，记做F?G。若F?G，则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

达能力上是完全相同的。二、最小函数依赖集定义:如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 ? F中的任何一个函数依赖的右部仅含有一个属性; ? F中不存在这样一个函数依赖X?A，使得F与F-{X?A}等价; ? F中不存在这样一个函数依赖X?A，X有真子集Z使得F-{X?A}?{Z?A}与F等价。算法:计算最小函数依赖集。输入一个函数依赖集输出 F的一个等价的最小函数依赖集G 步骤:? 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性; ? 去掉多余的函数依赖:从第一个函数依赖X?Y开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y，若是，则去掉X?Y;否则不能去掉，依次做下去。直到找不到冗余的函数依赖; ? 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY?A，若要判Y为多余的，则以X?A代替XY?A是否等价,若A (X)+，则Y是多余属性，可以去掉。举例:已知关系模式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} 解2:利用Armstrong公理系统的推理规则求解 ? 假设CG?B为冗余的函数依赖，那么，从F中去掉它后能根据Armstrong公理系统的推理规则导出。因为CG?D (已知) 所以CGA?AD，CGA?ACD (增广律) 因为ACD?B (已知) 所以CGA?B (传递律) 因为C?A (已知) 所以CG?B (伪传递律) 故CG?B是冗余的。 ? 同理可证:CE?A是多余的。 ? 又因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}

本文档为【[精华]闭包和函数最小依靠集的求法(含例题)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

[精华]闭包和函数最小依靠集的求法(含例题)

热门搜索

历史搜索

[精华]闭包和函数最小依靠集的求法&#40;含例题&#41;

热门搜索

历史搜索

[精华]闭包和函数最小依靠集的求法(含例题)