数据库系统概论—最小函数依赖集算法

算法：

1.     用分解的法则，使F中的任何一个函数依赖的右边仅含一个属性

2.     去除多余的函数依赖：从第一个函数依赖X→Y开始，将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，判断X+是否包含Y，如果包含，则去掉X→Y，否则保留，依次做下去，直到扫描所有函数依赖为止。

3.     去掉依赖左侧多余的冗余属性：如XY→A，若要判断Y是冗余属性，则计算X+，判断A是否属于X+，如果属于，则Y是冗余属性，将其删除，同理判断X。

   注意：若在第三步中修改了函数依赖集F，则需要重新做一次步骤二。

例： R={A,B,C,D,E,G}，F={B→D,DG→C,BD→E,AG→B,ADG→BC}，求F的最小函数依赖

解：

1. 运用分解律，进行拆除

   F={B→D,DG→C,BD→E,AG→B,ADG→B,ADG→C}

2. 判断冗余的函数依赖

   1.假设删除B→D，则B+={B}，故保留

   2.假设删除DG→C，则(DG)+={D,G}，故保留

   3.假设删除BD→E，则（BD)+={B,D}，故保留

   4.假设删除AG→B，则（AG)+={A,G}，故保留

   5.假设删除ADG→B，则(ADG)+={A,D,G,C,B,E}，有B，删除

   6.假设删除ADG→C，则（ADG)+={A,D,G,B,E,C}，有C，删除

   综上，F更新为

   F={B→D,DG→C,BD→E,AG→B}

3. 判断左侧的冗余属性，DG→C,BD→E,AG→B，左侧的属性个数大于1，故进行判断是否冗余

   1.看DG→C，假设删除D，则G+={G}，假设删除G，则D+={D}，无C，保留

   2.看BD→E，假设删除B，则D+={D}，假设删除D，则B+={B，D，E}，有E，则删除D，得到B→E

   3.看AG→B，假设删除A，则G+={G}，假设删除G，则A+={A}，无B，保留。

   综上，F更新为

   F={B→D,DG→C,B→E,AG→B}

4. 由于步骤3更新了F，故在进行一次步骤2.

   1.假设删除B→D,显然B的闭包不包含D

   2.假设删除DG→C，显然DG的闭包不包含C

   3.假设删除B→E，显然B的闭包不包含E。

   4.假设删除AG→B，显然AG的闭包不包含B。

综上所述最小依赖集为F={B→D,DG→C,B→E,AG→B}。

注：最小依赖集不唯一。