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

2023-07-20 22:37| 来源: 网络整理| 查看: 265

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

前言

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

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

在关系数据模型中，一个关系通常由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公理系统不用深究，想具体了解的可以点击查看百度百科。举例：

已知关系模式R，其中： 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）：函数依赖、闭包、最小函数依赖集、范式、模式分解

【本文地址】

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

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

今日新闻

推荐新闻