流程
①
先拆右边
,假如依赖集F中的右边项包含不止一个属性,那么将这些项都拆为单个项。例如A->BC,拆分为A->B和A->C
②
去除冗余依赖项
,例如A->C和AB->C,那么就要去除AB->C这个冗余项
③
拆左边
,假如依赖集F中的左边项包含不止一个属性,那么将这些项中的第一个属性先遮住,看剩下的属性能否推出结果,不行的话就换第二属性遮住,看剩余的属性能否推出结果,以此类推
例题
已知G={A->BC,CD->E,B->D,BE->F,EF->A},求最小函数依赖集
答:
1.先拆右边
将G中依赖项右边包含两个属性的拆为单个属性
拆完G={A->B,A->C,CD->E,B->D,BE->F,EF->A}
2.去除冗余依赖项
诀窍
:一个个试
①先去掉A->B,发现剩余的{A->C,CD->E,B->D,BE->F,EF->A}没法推出B,所以A->B不是冗余项
②以此类推,最后发现G中不存在冗余项
3.再拆左边
①第一个左边包含两个属性的为CD->E,先遮住C,看能否由D->E。首先由A->C可获得C,那么C与剩下的D就能推出E,因此C为冗余属性;然后再遮住D,看能否由C->E,因为A->B,A->C中都得不到D,因此没法组成CD->E,所以D不是冗余项。
经过第一步得出的G暂为{A->B,A->C,D->E,B->D}
②以此类推,第二个左边包含两个属性的为BE->F,先遮住B,看能否由E->F。因为A->B可获得B,那么B与剩下的E就能推出F,因此B为冗余属性;然后在遮住E,看能否由B->F,因为D->E,那么BE->F,因此E也可以为冗余属性。
可知最小函数依赖集不止一个
暂定G为{A->B,A->C,D->E,B->D,E->F}
③同上,最后G为{A->B,A->C,D->E,B->D,E->F,F->A}
最小函数依赖集为{A->B,A->C,D->E,B->D,E->F,F->A}