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

怼烎@ 2022-02-23 05:44 229阅读 0赞

### 文章目录 ###

*  前言
 *  为什么需要最小函数依赖集
 *  闭包
 *  最小函数依赖集
 *   *  定义
     *  解释
     *  算法
     *  举例
 *  写在最后

# 前言 #

在本文中，会介绍为什么要引入最小函数依赖集，最小函数依赖集是什么，以及如何求最小函数依赖集。

# 为什么需要最小函数依赖集 #

在关系数据模型中，一个关系通常由R(*U*,*F*)构成，U为属性的全集，F为函数依赖集。在实际生活中，我们可以根据语义来定义关系中属性的依赖关系，例如学号可以唯一确定一位学生的姓名、性别等等。但是，有时候给出的函数依赖集并不是**最简**的，这有时会拖累我们对关系的后续处理，例如关系的分解、判断是否为无损分解等。所以，我们在必要时，需要对函数依赖集进行化简，这就是需要最小函数依赖集的原因。  
在正式介绍最小函数依赖集之前，还需要了解一个概念，那就是闭包。准确的说是**属性集X关于函数依赖集F的闭包**。

# 闭包 #

闭包分为两种，一种是函数依赖集F的闭包，另外一种是属性集X关于函数依赖集F的闭包。前者不做讨论，重点说说后者。先来看定义

> 设*F*为属性集*U*上的一组函数依赖集，*X*、*Y*  ∈ \\in ∈*U*， X F + X\_F^+ XF\+= \{ *A*|*X* → \\rightarrow →*A*能由*F*根据Armstrong公理导出\}， X F + X\_F^+ XF\+称为**属性集*X*关于函数依赖集*F*的闭包。**

说白了，就是给定属性集X，根据现有的函数依赖集，看其能推出什么属性。  
这里的[Armstrong公理系统][Armstrong]不用深究，想具体了解的可以点击查看百度百科。  
举例：

> 已知关系模式R<*U*,*F*>，其中：  
> *U* = \{ *A，B，C，D，E*\}，  
> *F* = \{ *AB  → \\rightarrow → C，B → \\rightarrow →D，C → \\rightarrow →E，EC → \\rightarrow →B，AC → \\rightarrow →B*\}  
> 求 ( A B ) F + (AB)\_F^+ (AB)F\+。

解：

> 从AB出发，此时我们的集合里已经包含了\{A，B\}。  
> 我们从现有的函数依赖集中可知，  
> AB可以推出C，于是C加入集合，  
> B可以推出D，于是D加入集合，  
> C可以推出E，于是E加入集合，  
> EC可以推出B，因为C、E、B都在集合中，于是不加入，  
> AC可以推出B，因为A、B、C都在集合中，于是不加入  
> 至此，可求得 ( A B ) F + (AB)\_F^+ (AB)F\+ =\{A、B、C、D、E\}。

# 最小函数依赖集 #

## 定义 ##

> 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为**最小依赖集**或**最小覆盖**。  
> (1)、*F*中任一函数依赖右部仅含有一个属性。  
> (2)、*F*中不存在这样的函数依赖 *X → \\rightarrow →A*，使得*F*与*F-\{X → \\rightarrow →A\}* 等价。  
> (3)、*F*中不存在这样的函数依赖*X → \\rightarrow →A*，*X*有真子集*Z*使得*F-\{X → \\rightarrow →A\} ⋃ \\bigcup ⋃\{ Z → \\rightarrow →A\}* 与*F*等价。

## 解释 ##

以上定义翻译成大白话就是，一个函数依赖集F要想称为最小函数依赖集，要满足以下三点：  
1、F中任一函数依赖的右边只有一个属性。  
2、F中不存在这样的函数依赖：从现有的函数依赖集中删除一个函数依赖X → \\rightarrow →A，删除后所得的函数依赖集与原来的函数依赖集等价，这样的函数依赖是不允许存在的。  
3、F中不存在这样的函数依赖：假设函数依赖集中存在AB → \\rightarrow →Y，现对该依赖的左部进行化简，即删除A，得B → \\rightarrow →Y；或删除B，得A → \\rightarrow →Y，若经过化简后的函数依赖集与没有化简前的函数依赖集等价，那么这样的函数依赖是不允许存在的。

## 算法 ##

1、首先，先利用函数依赖的分解性，将函数依赖集中右部不为单个属性的分解为单属性。

2、对于经过第1步筛选后的函数依赖集F中的每一个函数依赖X → \\rightarrow →A，进行以下操作：

*  2.1、将X → \\rightarrow →A从函数依赖中剔除
 *  2.2、基于剔除后的函数依赖，计算属性X的闭包，看其是否包含了A，若是，则该函数依赖是多余的(*这里体现出前面说的等价，因为如果基于化简后的函数依赖依赖，计算X的闭包依然包含A，则说明A可以由其他依赖推出，X → \\rightarrow →A不是必须的*)，可以删除，否则不能删除

3、对于经过第2步筛选后的函数依赖集F中每个**左部不为单个属性**的函数依赖AB → \\rightarrow →Y，进行以下操作：  
我们约定，经过第二步筛选后的函数依赖集记为F1，经过第三步处理后的函数依赖集为F2。

*  3.1、去除A，得B → \\rightarrow →Y，得F2，基于F1和F2计算属性B的闭包，如果二者相等，则说明它们是等价的，A可以去除；如果不相等，则A不能去除。
 *  3.2、去除B，得A → \\rightarrow →Y，得F2，基于F1和F2计算属性A的闭包，如果二者相等则说明它们是等价的，B可以去除；如果不相等，则B不能去除。

> 知识链接：函数依赖的分解性  
> 若X → \\rightarrow →YZ，则X → \\rightarrow →Y 且 X → \\rightarrow →Z。

## 举例 ##

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

解：  
1、首先根据函数依赖的分解性，对F进行第一次筛选，需要变动的有：  
ADG → \\rightarrow →BC拆解成ADG → \\rightarrow →B、ADG → \\rightarrow →C  
得新函数依赖集：  
F = \{B → \\rightarrow →D,DG → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B,ADG → \\rightarrow →B,ADG → \\rightarrow →C\}

2、筛选多余的函数依赖

*  2.1：去除B → \\rightarrow →D，得F = \{DG → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B,ADG → \\rightarrow →B,ADG → \\rightarrow →C\}， B F + B\_F^+ BF\+ = \{B\}，不包含D，故B → \\rightarrow →D不删除。
 *  2.2：去除DG → \\rightarrow →C，得F = \{B → \\rightarrow →D、BD → \\rightarrow →E,AG → \\rightarrow →B,ADG → \\rightarrow →B,ADG → \\rightarrow →C\}， ( D G ) F + (DG)\_F^+ (DG)F\+=\{D,G\}，不包含C，故DG → \\rightarrow →C不删除。
 *  2.3：去除BD → \\rightarrow →E，得F = \{B → \\rightarrow →D,DG → \\rightarrow →C,AG → \\rightarrow →B,ADG → \\rightarrow →B,ADG → \\rightarrow →C\}， ( B D ) F + (BD)\_F^+ (BD)F\+ = \{B,D\}，不包含E，故BD → \\rightarrow →E不删除。
 *  2.4：去除AG → \\rightarrow →B，得F = \{B → \\rightarrow →D,DG → \\rightarrow →C,BD → \\rightarrow →E,ADG → \\rightarrow →B,ADG → \\rightarrow →C\}， ( A G ) F + (AG)\_F^+ (AG)F\+ = \{A,G\}，不包含B，故AG → \\rightarrow →B不删除。
 *  2.5：去除ADG → \\rightarrow →B，得F = \{B → \\rightarrow →D,DG → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B,ADG → \\rightarrow →C\}， ( A D G ) F + (ADG)\_F^+ (ADG)F\+ = \{A,D,G,C,B,E\}，包含B，**故ADG → \\rightarrow →B去除**。
 *  2.6：去除ADG → \\rightarrow →C，得F = \{B → \\rightarrow →D,DG → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B,ADG → \\rightarrow →B\}， ( A D G ) F + (ADG)\_F^+ (ADG)F\+ = \{A,D,G,C,B,E\}，包含C，**故ADG → \\rightarrow →C去除**。  
    经过第二部筛选后，函数依赖集F变为\{B → \\rightarrow →D,DG → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B\}。

3、化简函数依赖左侧不为单个属性的函数依赖

*  3.1：先看DG → \\rightarrow →C
    
     *  3.1.1：去除D，得G → \\rightarrow →C，得函数依赖集F1 = \{B → \\rightarrow →D,G → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B\}。  
        基于F1，可求得 G F + G\_F^+ GF\+ = \{G,C\}。  
        基于F(第二步求出的，下同)，可求得 G F + G\_F^+ GF\+ = \{G\}  
        可见二者并不相同，所以D不去除。
     *  3.1.2：去除G，得D → \\rightarrow →C，得函数依赖集F1 = \{B → \\rightarrow →D,D → \\rightarrow →C,BD → \\rightarrow →E,AG → \\rightarrow →B\}  
        基于F1，可求得 D F + D\_F^+ DF\+ = \{D,C\}  
        基于F，可求得 D F + D\_F^+ DF\+ =\{D\}  
        可见二者并不相同，所以G不去除。

综上，DG → \\rightarrow →C，已是最简。

*  3.2：再看BD → \\rightarrow →E
    
     *  3.2.1：去除B，得D → \\rightarrow →E，得函数依赖集F1 = \{B → \\rightarrow →D,DG → \\rightarrow →C,D → \\rightarrow →E,AG → \\rightarrow →B\}  
        基于F1，可求得 D F + D\_F^+ DF\+ = \{D,E\}  
        基于F，可求得 D F + D\_F^+ DF\+ = \{D\}  
        可见二者并不相同，所以B不去除。
     *  3.2.2：去除D，得B → \\rightarrow →E，得函数依赖集F1 = \{B → \\rightarrow →D,DG → \\rightarrow →C,B → \\rightarrow →E,AG → \\rightarrow →B\}  
        基于F1，可求得 B F + B\_F^+ BF\+ = \{B,E,D\}  
        基于F，可求得 B F + B\_F^+ BF\+ = \{B,D,E\}  
        可见二者相同，所以D**可以去除**。

综上，BD → \\rightarrow →E，可化简为B → \\rightarrow →E。

*  3.3：最后看AG → \\rightarrow →B
    
     *  3.3.1：去除A，得G → \\rightarrow →B，得函数依赖集F1 = \{B → \\rightarrow →D,DG → \\rightarrow →C,B → \\rightarrow →E,G → \\rightarrow →B\}  
        基于F1，可求得 G F + G\_F^+ GF\+ = \{G,B\}  
        基于F，可求得  G F + G\_F^+ GF\+ = \{G\}  
        可见二者并不相同，所以A不可去除。
     *  3.3.2：去除G，得A → \\rightarrow →B，得函数依赖F1 = \{B → \\rightarrow →D,DG → \\rightarrow →C,B → \\rightarrow →E,A → \\rightarrow →B\}  
        基于F1，可求得 A F + A\_F^+ AF\+ = \{A,B\}  
        基于F，可求得 A F + A\_F^+ AF\+ = \{A\}  
        可见二者并不相同，所以G不可去除。

综上，AG → \\rightarrow →B，已是最简。  
综上，R的最小函数依赖集为F = \{B → \\rightarrow →D,DG → \\rightarrow →C,B → \\rightarrow →E,AG → \\rightarrow →B\}

# 写在最后 #

这个问题是我在考研复试的时候复习过程中遇到的，主要的纠结点在于第三步的判断上，查资料的时候发现网上很多都没有写清，最后还是在度娘的文库里找到了比较清楚的解释，在此做一下思路的整理。  
本文定义以及例子参考自：

*  *《数据库系统概论（第五版）》 王珊 萨师煊 编著 清华大学出版社*
 *  *CSDN 博文 [数据库建模和设计（2）：函数依赖、闭包、最小函数依赖集、范式、模式分解][2]*

[Armstrong]: https://baike.baidu.com/item/Armstrong%E5%85%AC%E7%90%86/1187858?fr=aladdin
[2]: https://blog.csdn.net/prdslf001001/article/details/80336835