求最小函数依赖集

客官°小女子只卖身不卖艺 2022-05-11 02:34 125阅读 0赞

# 步骤： #

![70][]

1.  用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性；
2.  去掉多余的函数依赖：从第一个函数依赖X→Y开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X(
    
     \[Y1\]闭包就是由一个属性直接或间接推导出的所有属性的集合，例如：
    
    f=\{a->b,b->c,a->d,e->f\}，
    
    由a可直接得到b和d，间接得到c，则a的闭包就是\{a,b,c,d\}
    
    ) ，看X+是否包含Y，若是，则去掉X→Y；否则不能去掉，依次做下去。直到找不到冗余的函数依赖；
3.  去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A，若要判Y为多余的，则以X→A代替XY→A是否等价？若A属于(X)+，则Y是多余属性，可以去掉。

# 例子 #

## 例子1： ##

![70 1][]

(1)判断右边是否最简，得F=\{B->D，DG->C,BD->E,AG->B,ADG->B,ADG->C\}

(2)第1步：

①假设B->D冗余，则去掉B->D得:G=\{DG->C,BD->E,AG->B,ADG->B,ADG->C\}

B+ =B 不包含D，所以不冗余，不能去掉。

②假设DG->C冗余，则去掉DG->C，得:G=\{B->D,BD->E,AG->B,ADG->B,ADG->C\}

(DG)+ =DG不包含C，所以不冗余，不能去掉。

③假设BD->E冗余，则去掉BD->E，

得:G=\{B->D，DG->C,AG->B,ADG->B,ADG->C\}

(BD)+ =BD不包含E，所以不冗余，不能去掉。

④假设AG->B冗余，则去掉AG->B，得:G=\{B->D，DG->C,BD->E,ADG->B,ADG->C\}，(AG)+ =AG不包含B，所以不冗余，不能去掉。

⑤假设ADG->B冗余，则去掉ADG->B，

得:G=\{B->D，DG->C,BD->E,AG->B,ADG->C\}

(ADG)+ =ABCDG包含B，所以冗余，去掉。

⑥假设ADG->C冗余，则去掉ADG->C，得:G=\{B->D，DG->C,BD->E,AG->B\}

(ADG)+ =ABCDG包含C，所以冗余，去掉。

综上:F=\{B->D，DG->C,BD->E,AG->B\}

第2步：

①假设D->C冗余，D+ =D不包含C,所以G不能去掉。

②假设G->C冗余，G+ =G不包含C,所以D不能去掉。

③假设B->E冗余，B+ =BD不包含E,所以D不能去掉。

④假设D->E冗余，D+ =D不包含E,所以B不能去掉。

⑤假设A->B冗余，A+ =A不包含B,所以G不能去掉。

⑥假设G->B冗余，G+ =G不包含B,所以A不能去掉。

所以，Fm=\{B->D，DG->C,BD->E,AG->B\}

## 例子2： ##

![70 2][]

[70]: /images/20220511/07150b9c47b942e88f0527537cc8301e.png
[70 1]: /images/20220511/6a93309a078e4300a79e9f938328649d.png
[70 2]: /images/20220511/2c0892c241e345b9a7025a676341f7a3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关函数依赖，闭包，覆盖，最小化基本集，部分函数依赖与完全函数依赖，传递函数依赖，候选键，外来建，逻辑蕴含

简介：本文讲解函数依赖，闭包，覆盖，最小化基本集，部分函数依赖与完全函数依赖，传递函数依赖，候选键，外来建，逻辑蕴含。函数依赖定义 ![在这里插入图片描述][

﹏ヽ暗。殇╰゛Y/ 2024年03月31日 08:51/ 0 赞/ 17 阅读

相关求数组的最大值和最小值函数

在 python 中，可以使用 numpy 库中的函数 numpy.max() 和 numpy.min() 来求数组的最大值和最小值。示例： import num

你的名字/ 2024年03月25日 17:20/ 0 赞/ 25 阅读

相关求最大公约数、最小公倍数、

一、求两个数的最大公约数 > 解法一： > ![在这里插入图片描述][78b2f18c4b2c4373a4b87ee39124958c.png] int m

迈不过友情╰/ 2023年10月08日 16:52/ 0 赞/ 20 阅读

相关求最小公倍数

/ 求最大公倍数 / include<stdio.h> include<stdlib.h> int getM

矫情吗；*/ 2022年07月16日 06:00/ 0 赞/ 173 阅读

相关创建函数模板实现求数组中的最小元素

创建函数模板实现求数组中的最小元素创建一个函数模板实现求数组中的最小元素，在主函数将分别使用该模板求整形数组和double型数组中的最小元素并输出。输入： 6

柔情只为你懂/ 2022年06月17日 01:06/ 0 赞/ 111 阅读

相关求最大公约数和最小公倍数

注：最大公约数和最小公倍数，我都是针对正整数的（一）最笨的方法：穷尽法 2个数的最大公约数的最大值：2数中的较小数。 2个数的最大公约数的最小值：1 因此，只

雨点打透心脏的1/2处/ 2022年06月12日 13:25/ 0 赞/ 215 阅读

相关求最小函数依赖集

步骤： ![70][] 1. 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性； 2. 去掉多余的函数依赖：从第一个函数依赖X→Y开始将其从F中去掉，然后

客官°小女子只卖身不卖艺/ 2022年05月11日 02:34/ 0 赞/ 126 阅读

相关求最小公倍数 java

求最小公倍数 java 题目描述正整数A和正整数B 的最小公倍数是指能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。输入描述: 输

野性酷女/ 2022年05月10日 10:26/ 0 赞/ 178 阅读

相关求最大公约数和最小公倍数

import java.util.Scanner; public class Main \{ public static void main(String\[\] arg

淡淡的烟草味﹌/ 2022年05月03日 07:26/ 0 赞/ 227 阅读

相关关系数据库理论之最小函数依赖集

文章目录前言为什么需要最小函数依赖集闭包最小函数依赖集定义解释算法举例

怼烎@/ 2022年02月23日 05:44/ 0 赞/ 200 阅读