求最小函数依赖

  • Post author:
  • Post category:其他




已知关系模式R(A, B, C, D, E, G, H),函数依赖集F为{BC→AE, DC→EH, DG→E, B→CD, D→G},请严格按步骤来对F进行最小化处理,得到F的最小函数依赖集


第一步


对F中的函数依赖运用分解原则来创建一个等价函数依赖集H,该集合中每一个函数依赖的右部是单个属性:



第一步之后的结果H={①BC→A,②BC→E,③DC→E,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}


第二步


考察每一个函数依赖是否是必须的,去除非必要的函数依赖:

(1):


考察BC→A


,去掉函数依赖集会得到新的函数依赖集J={②BC→E,③DC→E,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}。则(BC)J+=BCDEGH,不包含A,因此BC→A不能去掉。

(2):


考察BC→E


,J={①BC→A,③DC→E,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}。则(BC)J+=ABCDEGH,包含E,能去掉。


此时H={①BC→A,③DC→E,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(3):


考察DC→E


,J={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}。则(DC)J+=CDEGH,包含E,能去掉。


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(4):


考察DC→H


,J={①BC→A,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}。则(DC)J+=CDGE,不包含H,不能去掉


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(5):


考察DG→E


,J={①BC→A,④DC→H,⑥B→C,⑦B→D,⑧D→G}。则(DG)J+=DG,不包含E,不能去掉。


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(6):


考察B→C


,J={①BC→A,④DC→H,⑤DG→E,⑦B→D,⑧D→G}。则(B)J+=BDGE,不包含C,不能去掉。


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(7):


考察B→D


,J={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑧D→G}。则(B)J+=ABC,不包含D,不能去掉。


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}

(8):


考察D→G


,J={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D}。则(D)J+=D,不包含G,不能去掉。


此时H={①BC→A,④DC→H,⑤DG→E,⑥B→C,⑦B→D,⑧D→G}



所以第二步之后H={①BC→A,②DC→H,③DG→E,④B→C,⑤B→D,⑥D→G}


第三步

考察每一个左部为多个属性的函数依赖,看左部的每个属性是否是必须的,能否用更小的属性集替代原有的属性集。

首先从函数依赖①BC→A开始。


(1): 去除B



如果B可以去除,那么可得到新的函数依赖集J={①C→A,②DC→H,③DG→E,④B→C,⑤B→D,⑥D→G}。去掉B后C在J上的闭包将比在H下函数决定更多的属性,如果(C )J+=(C )H+或者A∈(C )H+,则说明去掉B得到的函数依赖集和原有的函数依赖集是等价的,可以用C→A替换BC→A。

( C)H+=C,不包含A,不能去除。


去除C



(B)H+=ABCDEGH,包含A,可以去除。


此时H={①B→A,②DC→H,③DG→E,④B→C,⑤B→D,⑥D→G}


(2):去除②中的D



(D)H+=DGE,不包含H,不能去掉。


去除②中的C?


(C )H+=C,不包含H,不能去掉。


此时H={①B→A,②DC→H,③DG→E,④B→C,⑤B→D,⑥D→G}


(3):去掉③中的D



(G)H+=G,不含E,不能去掉。


去掉③中的G?


(D)H+=DGE,包含E,可以去掉。


此时H=此时H={①B→A,②DC→H,③D→E,④B→C,⑤B→D,⑥D→G}



所以最后的结果H={B→A,DC→H,D→E,B→C,B→D,D→G}



数学表达式格式:

在这里插入图片描述



版权声明:本文为m0_46493091原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。