函数依赖及其公理/定理

短命女 2023-10-06 10:33 62阅读 0赞

#### 文章目录 ####

*  什么是函数依赖
 *  部分函数依赖与完全函数依赖
 *  传递函数依赖
 *  函数依赖相关的几个重要概念
 *  关于函数依赖的 Armstrong 公理
 *   *  Armstrong 公理
     *  Armstrong 公理对应的引理
 *  什么是属性（集）闭包
 *  属性闭包的计算算法与覆盖及其证明
 *  最小覆盖及其构造

## 什么是函数依赖 ##

**定义：**  
对于具有多个属性的关系模式 R，如果对于属性集合中的两个子集 A 和 B 和任意的关系 r，r 中不可能出现两个记录使得 A 中的值相等而 B 中的值不等，则称 A 函数决定 B，B 函数依赖于 A，记作 A→B。

另一种说法是，如果将 A 和 B 单独拿出来做一个关系，这个关系中 A 可以作为主键。

**性质：**  
有些函数依赖关系中 B⊆A，这种称为是 平凡 的函数依赖，反之为不平凡的函数依赖。

即使两个属性之间存在函数依赖关系，即 A→B，这不意味着 A 和 B 不能在关系的多条记录中出现。

两个属性子集可能相互函数依赖。

如果关系中，A 上没有相同的两个记录出现，那么任意属性子集都函数依赖于 A。

有基于 模式 的函数依赖，要求对所有可能的关系都成立；也有基于 关系 的函数依赖，只要求对这一个关系成立即可。

## 部分函数依赖与完全函数依赖 ##

如果 A→B，但是存在 A 的真子集 A’ 使得 A′→B，则称 B **部分函数依赖** 于 A。如果不存在这样的子集，此时为 **完全函数依赖**。

## 传递函数依赖 ##

函数依赖关系具有传递性：A→B,B→C⇒A→C。

如果加上一些更强的限制：A→B 和 B→C 都是非平凡的，且 C⊈A，B![在这里插入图片描述][20200606133357616.png]A，则称 C 传递函数依赖 于 A。

## 函数依赖相关的几个重要概念 ##

把数据库中的相关概念用函数依赖理论重新定义了一下：

**候选键**：能够 完全决定 关系模式中所有属性的属性组称为关系模式上的 候选键。

**主键**：对于一个关系模式，可以选取其任意一个候选键作为 主键。

**主属性**：包含于任意一个候选键中的属性称为 主属性，否则为 非主属性。

**超键**：超键和候选键类似，但是移除了完全决定的限制。超键是某个候选键对应属性集的超集。

**外键**：某个属性组不是当前关系模式的候选键，但是是另一个关系模式的候选键，称为当前关系模式的 外键。

其它的一些概念：

**逻辑蕴涵**：设 F 是关系模式 R 上函数依赖关系的集合（不一定是完整的）。对于 R 的两个属性组 A 和 B，如果从 F 中能够推理出 A→B，则称 F 逻辑蕴涵 A→B，记作 F⊨A→B。

**闭包**：设 F 是关系模式 R 上函数依赖关系的集合（不一定是完整的）。F 逻辑蕴涵的所有函数依赖关系构成的集合称为 F 的闭包。

可以看到，函数依赖是属性集子集上的一个关系，起码它是传递、自反的。

## 关于函数依赖的 Armstrong 公理 ##

### Armstrong 公理 ###

Armstrong 公理一共有三条，可以用来从函数依赖关系集合中发现新的函数依赖关系。

这一小节使用 X、Y、Z 作为属性组；U 作为属性全集；F 作为某个函数依赖关系的集合。

![在这里插入图片描述][2020060613373140.png]

### Armstrong 公理对应的引理 ###

从上述公理出发可以引出下面四条定理（为了方便就不写 ∈F 以及 F⊨ 了）：  
![在这里插入图片描述][20200606133807234.png]

## 什么是属性（集）闭包 ##

设 F 是函数依赖关系的集合，X 是一个属性组。能够从 F 推导出的所有依赖于 X 的属性构成的集合称为 X 关于 F 的属性闭包，记作 ![X+F][X_F]。

## 属性闭包的计算算法与覆盖及其证明 ##

函数依赖关系的集合称为 **函数依赖集**。

**函数依赖集的等价性：**  
如果两个函数依赖集的闭包相等，则这两个函数依赖集是 等价的。此时称其中一个函数依赖集 覆盖 另一个函数依赖集。

**如何计算属性闭包：**  
可以按照如下循环不断进行，直到序列稳定。假定要求的是 X 在 F 下的属性闭包：  
![在这里插入图片描述][20200606134055751.png]  
这样可以求出 ![在这里插入图片描述][20200606134106147.png]  
。

## 最小覆盖及其构造 ##

对于一个函数依赖集 F，如果和它等价的函数依赖集 F’ 满足下面三个条件，则称为是 F 的**最小覆盖**（也叫 最小依赖集）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

[20200606133357616.png]: https://img-blog.csdnimg.cn/20200606133357616.png
[2020060613373140.png]: https://img-blog.csdnimg.cn/2020060613373140.png
[20200606133807234.png]: https://img-blog.csdnimg.cn/20200606133807234.png
[X_F]: https://img-blog.csdnimg.cn/20200606133837757.png
[20200606134055751.png]: https://img-blog.csdnimg.cn/20200606134055751.png
[20200606134106147.png]: https://img-blog.csdnimg.cn/20200606134106147.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200606134156756.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70