# 函数依赖的概念

函数依赖是关系模式中各个属性之间的一种依赖关系
例如可以通过一个学号值，得到唯一一个姓名值
== 属性（属性组）和属性（属性组）== 之间的推导关系便为函数依赖

# 平凡函数依赖

设一个关系为 $R(U)$，$X$ 和 $Y$ 为属性集 $U$ 的子集，当 $X \to Y$ 时，如果 $Y \subsetneq X$（$Y$ 是 $X$ 的子集），那么称 $X \to Y$ 是平凡函数依赖

• （学号，姓名） $\to$ 姓名

# 非平凡函数依赖

设一个关系为 $R(U)$，$X$ 和 $Y$ 为属性集 $U$ 的子集，若 $X \to Y$ 且 $X \nsubseteq B$，那么称 $X \to Y$ 是非平凡函数依赖

• （学号，课程号） $\to$ 个人成绩

# 完全函数依赖

一个关系模式 $R(U)$ 中，$X$ 和 $Y$ 为属性集 $U$ 上的子集，如果 $X \to Y$，且对与 $X$ 的任意一个真子集 Z 来说，$Z \to Y$ 都不成立

• $X$ 为单个属性，此时 $X \to Y$，那么此时必为完全函数依赖
• $X$ 为属性组，$X$ 的任何一个子集 $Z$ 都不满足 $Z \to Y$，那么此时为完全函数依赖

# 部分函数依赖

一个关系模式 $R(U)$ 中，$X$ 和 $Y$ 为属性集 $U$ 上的子集，如果 $X \to Y$，且存在 $X$ 的一个真子集 Z，满足 $Z \to Y$，则称 $Y$ 部分依赖于 $X$

# 传递函数依赖

一个关系模式 $R(U)$ 中，$X$, $Y$, $Z$ 为属性集 $U$ 上的子集，如果 $X \to Y$，$Y$ 不能反推出 $X$，且 $Y \to Z$，这时候通过 $X$ 可以推出 $Z$，即 $X \to Z$，我们把 $X \to Z$ 称为传递函数依赖

• 学号 $\to$ 所在系 $\to$ 系主任

# 与函数依赖相关的概念

• 候选键：对于关系 $R(U)$ 中的属性（组）$K$，如果 $U$ 完全函数依赖于 $K$，即 $K$ 中的所有属性一起才能决定 $U$，则称 $K$ 为 $R(U)$ 的候选键
• 主键：若有多个候选键，则可任选一个作为主键
• 主属性：包含在任一候选键中的属性称为主属性，其他属性称为非主属性
• 外来键：一个关系的外键是另一关系的候选键
• 逻辑蕴含：设 $F$ 是关系 $R(U)$ 中的一个函数依赖集合，$X$、$Y$ 是 $R$ 的属性子集。如果能从 $F$ 这个函数依赖集合中推导出 $X \to Y$，则称 $F$ 逻辑蕴含 $X \to Y$，或者说 $X \to Y$ 是 $F$ 的逻辑蕴含。记作： $F \models X \rightarrow Y$
  • 在已知的函数依赖集合中，能推导出一个新的函数依赖，则成这个新的函数依赖逻辑蕴含于函数依赖集合 $F$
• 闭包：被 $F$ 逻辑蕴含的所有函数依赖集合称为 $F$ 的闭包，记作 $F^+$
  • 如果 $F^+ = F$，则称 $F$ 是一个全函数依赖族（函数依赖完备集）

# Armstrong 公理及引理

设 $F$ 为 $R(U)$ 的一组函数依赖，记为 $R(U, F)$

# 公理

• 自反律：若 $Y \subseteq X \subseteq U$，则 $X \to Y$ 被 $F$ 逻辑蕴含
  • 人话：平凡函数依赖
• 增广率：若 $X \to Y \subseteq F, Z \subseteq U$，则 $XZ \to YZ$ 被 $F$ 逻辑蕴含
• 传递率：若 $X \to Y \in F, Y \to Z \in F$，则 $X \to Z$ 被 $F$ 逻辑蕴含

# 引理

# 引理 1

• 合并率：若 $X \to Y$ 且 $X \to Z$，则 $X \to YZ$
• 伪传递率：若 $X \to Y$ 且 $WY \to Z$，则 $XW \to Z$
• 分解率：若 $X \to Y$ 且 $Z \subseteq Y$，则 $X \to Z$

# 引理 2

如果 $A_1,A_2...,A_n$ 是属性，则 $X \to A_1A_2...A_n$，当且仅当 $X \to A_i ~ (1 \le i \le n)$

• 一组属性整体依赖于 $X$，等价于：其中每一个属性都分别依赖于 $X$

# 属性（集）闭包和引理 3

# 属性（集）闭包

对于 $R(U,F),X \subseteq U,U=A_1A_2...A_n$，令 $X^+_F = A_i$，即可从 $F$ 推导出 $X \to A_i$，称 $X^+_F$ 为 $X$ 关于 $F$ 的属性（集）闭包

• 属性集闭包的元素是属性
• 闭包的元素是函数依赖

# 引理 3

若从 $F$ 这个函数依赖中，可以通过公理导出 $X \to Y$，则当且仅当 $Y \subseteq X_F^+$

# 覆盖和引理 4、5

# 覆盖

对 $R(U)$ 上的两个函数依赖集合 $F,G$，如果 $F^+=G^+$，则称 $F$ 和 $G$ 也是等价的，也称 $F$ 覆盖 $G$ 或者 $G$ 覆盖 $F$

# 引理 4

F^{+} = G^{+} \iff F \subseteq G^{+} \land G \subseteq F^

# 引理 5

每个函数依赖集 $F$ 可被一个其右端至多有一个属性的函数依赖集 $G$ 覆盖
人话解释：​​任何复杂的函数依赖集 $F$，都可以用一个更简单的依赖集 $G$ 来代替​，而且这个 $G$ 有一个特点： 它的每一条规则，右边都只有一个属性​​（比如 $A \to B$，而不是 $A \to BC$）

# （正则）最小覆盖

• 每条规则右边只有一个属性
• 不能有废话规则
• 每条规则左边属性不能多余
  每个函数依赖集 $F$ 都有等价的最小覆盖 F^