最小函数依赖集的推导（数据库系统）

本文介绍: 已知关系模式R，其中：U = {A，B，C，D，E}，求ABFX0=AB；X1X2所以ABF函数依赖F由以下依赖组成：{AC→PE、PG→A、B→CE、A→P、A→B、GC→A、PAB→G、AG→BG、ABCP→H}，求BGFX0=BG；X1X2X3所以BGF={ABCEGP}

求闭包

已知关系模式R<U,F&g t;，其中：U = {A，B，C，D，E}，
F = {AB→C，B→D，C→E，EC→B，AC→B}
求

(

A

B

)

F

+

{(AB)_F^+}

$(A B)_{F}^{+}$

(

)

{X^{(0)}}

$X^{(0)}$ =AB；

(

)

{X^{(1)}}

$X^{(1)}$ =AB∪CD=ABCD；

(

)

{X^{(2)}}

$X^{(2)}$ =ABCD∪E=ABCDE=U

所以

(

)

{(AB)_F^+}

$(A B)_{F}^{+}$ ={A、B、C、D、E}

函数依赖F由以下依赖组成：{AC→PE、PG→A、B→CE、A→P、A→B、GC→A、PAB→G、AG→BG、ABCP→H}，求

(

B

G

)

F

+

{(BG)_F^+}

$(BG)_{F}^{+}$

(

)

{X^{(0)}}

$X^{(0)}$ =BG；

(

)

{X^{(1)}}

$X^{(1)}$ =BG∪CE=BGCE；

(

)

{X^{(2)}}

$X^{(2)}$ =BGCE∪A=BGCEA；

(

)

{X^{(3)}}

$X^{(3)}$ =BGCEA∪PE=ABCEGP=U

所以

(

)

{(BG)_F^+}

$(BG)_{F}^{+}$ ={ABCEGP}

求最小 函数 依赖集

步骤

将F中的所有函数依赖的右边化为单一属性；
去掉F中所有冗余的函数依赖；
去掉F中的所有函数依赖左边的冗余属性；

例子

关系模式R(U，F)中，U={A，B，C，D，E，G}，F={B→D,DG→C,BD→E,AG→B,ADG→BC}；求F的最小函数依赖集。

STEP1将右边化为单一属性：
B→D，DG→C，BD→E，AG→B，ADG→B，ADG→C

STEP2去除冗余的函数依赖：
1.如果去除B→D，

(

)

{(B)_F^+}

$(B)_{F}^{+}$ ={B}不包含D，所以不能去除；
2.去除DG→C，

(

)

{(DG)_F^+}

$(D G)_{F}^{+}$ ={D，G}不包含C，所以不能去除；
3.去除BD→E，

(

)

{(BD)_F^+}

$(B D)_{F}^{+}$ ={B，D}不包含E，所以不能去除；
4.去除AG→B，

(

)

{(AG)_F^+}

$(A G)_{F}^{+}$ ={A，G}不包含B，所以不能去除；
5.去除ADG→B，

(

)

{(ADG)_F^+}

$(A D G)_{F}^{+}$ ={A,D,G,C,B,E}包含B，也就是说去除ADG→B之后得到的依赖集与之前的F等价，所以可以去除；
6.去除ADG→C，

(

)

{(ADG)_F^+}

$(A D G)_{F}^{+}$ ={A,D,G,C,B,E}包含C，和ADG→B类似，所以可以去除；

所以最后F={B→D，DG→C，BD→E，AG→B}

STEP3去除左边的冗余属性
1.DG→C
我们需要判断D或G是否是冗余的

先看D，如果D冗余，那么去掉D之后的依赖集应该与去掉之前的依赖集是等价的，则需要看F={B→D，DG→C，BD→E，AG→B}和F1={B→D，G→C，BD→E，AG→B}是否等价；
对于F1，

(

G

)

F

+

{(G)_F^+}

$(G)_{F}^{+}$ ={G,C}；对于F，

(

G

)

F

+

{(G)_F^+}

$(G)_{F}^{+}$ ={G}，不等价，因此D不是冗余属性；
再看G，判断F={B→D，DG→C，BD→E，AG→B}和F1={B→D，D→C，BD→E，AG→B}是否等价；
对于F1，

(

D

)

F

+

{(D)_F^+}

$(D)_{F}^{+}$ ={D,C}；对应F，

(

D

)

F

+

{(D)_F^+}

$(D)_{F}^{+}$ ={D}，不等价，因此D不是冗余属性；