数据库-函数依赖

函数依赖的定义和类型

关系模式的形式化定义

关系模式的形式化定义是指关系模式由五部分组成, 是一个五元组, 形如 $R (U,D,DOM,F)$

• $R$ 表示关系名
• $U$ 表示组成该关系的属性名集合
• $D$ 表示属性组 U 中属性所来自的域
• $DOM$ 表示属性到域的映射集合
• $F$ 表示属性间数据的依赖关系集合

函数依赖的定义

函数依赖是数据依赖的一种, 函数 $Y=f(X)$ 表示的是, 给定一个 $X$, 会有一个 $Y$ 与之对应
即 $X$ 决定 $Y$, $Y$ 依赖于 $X$, 记作:$X\to Y$

关系数据库中, 讨论函数依赖, 更注重语义上的关系.

例如:$Sname=f(Sno)$ 表示只要给出一个具体的 $学号$ 就会有一个 $姓名$ 与之对应, 即学号决定姓名, 或者姓名依赖于学号. $R(U)$ 是属性集 $U$ 上的关系模式, $X$ 和 $Y$ 是 $U$ 的子集.

可见函数依赖讨论的是属性之间的依赖关系.

• 函数依赖不是指关系模式 $R$ 的所有关系实例均要满足的约束条件.
• 人只能通过语义来确定函数依赖.
• 属性间的函数依赖与属性间的联系相关.
  如果属性 $X$ 和 $Y$ 是"1:1"的联系或者 “1:n” 的联系, 则存在函数依赖; 如果 $X$ 和 $Y$ 之间是 “m:n” 联系, 则不存在函数依赖.
• 若 $X\to Y$ 且 $Y\to X$, 则记为 $X\leftrightarrow Y$
• 若 $Y$ 不依赖于 $X$, 记作:$x\not\to Y$

函数依赖的类型

平凡依赖和非平凡依赖

在关系模式中, 对于 $U$ 的子集 $X$ 和 $Y$, 如果 $X\to Y$

• 若 $Y\not\subseteq X$, 则称 $X\to Y$ 是非平凡函数依赖
• 若 $Y\subseteq X$, 则称 $X\to Y$ 是平凡函数依赖.

例如:$X\to \varnothing$ 、$X\to X$ 是非平凡依赖.

举例:
平凡函数依赖:$学号\to 成绩$
非平凡函数依赖:$\{姓名,性别\}\to 姓名$

完全函数依赖和部分函数依赖

在关系模式 $R(U)$ 中, 如果 $X\to Y$ 并且对于 $X$ 的任何一个真子集 $X'$, 都有 $X'\not\to Y$, 则称 $Y$ 对 $X$ 完全函数依赖, 记作:$X\overset{F}\to Y$

若 $X\to Y$, 且存在 $X$ 的某一真子集 $X'$, 使得 $X'\to Y$, 则称 $Y$ 对 $X$ 部分函数依赖, 记作:$X\overset{P}\to Y$

举例:
部分函数依赖:$\{学号,姓名\}\to 成绩$
完全函数依赖:$\{班级,成绩\}\to 成绩$

传递函数依赖

在关系模式 $R(U)$ 中, $X$、$Y$、$Z$ 是 $R$ 的 3 个不同的属性或属性组, 如果 $X\to Y,(Y 不是 X 的子集)$ 且 $Y\not\to X$, $Y\to Z$, $Z\not\in Y$, 则称 $Z$ 对 $X$ 为传递函数依赖:

传递函数依赖要求 $Y$:

• $Y$ 不能决定 $X$ ($Y\not\to X$)
  如果 $Y\to X$ ,则 $Y\leftrightarrow X$ , $X$ $Y$ 等价, 所以 $X\to Z$ 就变成了直接依赖.
• $Y$ 不是 $X$ 的子集
  如果 $Y$ 是 $X$ 的子集, 就变成了 $X\{Y,...\}\to Z$ ,成了部分依赖.

举例:
$学号\to 专业 \to 专业人数$
传递依赖是一种间接传递 (如果不知道学生专业就不知道专业人数)

FD 的逻辑蕴涵和公理系统

FD 指的是 Functional Dependency 函数依赖

FD 的逻辑蕴涵

FD 的逻辑蕴涵指的是在一直的函数依赖集 F 中判断是否蕴涵着未知的函数依赖

函数依赖集 F 的闭包

被 F 逻辑蕴涵的所有函数依赖 FD 全体构成的集合叫做函数依赖集 F 的闭包, 记为: $F^+$

$$F^+ = \{X\to Y\mid F\Rightarrow X\to Y \}$$

FD 的公理系统

为了从 $F$ 中求出 $F^+$ , 尤其是根据已知的 FD 判断一个未知的 FD 是否成立, 或者求候选键, 就会用到 FD 的公理系统, 规则说明如下

• 自反律: 若在 $R$ 中有 $Y\subseteq X$ , 则 $X\to Y$ 在 $R$ 上成立, 并且蕴涵于 $F$ 之中.
• 传递率: 若 $F$ 中的 $X\to Y$ 和 $Y\to X$ 在 $R$ 上成立, 则 $X\to Z$ 在 $R$ 上成立, 并且蕴涵于 $F$ 之中.
• 增广率: 若 $F$ 中的 $X\to Y$ 在 $R$ 上成立, 则 $XZ\to YZ$ 在 $R$ 上也成立, 并且蕴涵于 $F$ 之中.

除上述三条推理规则外, 下面给出可由这 3 条规则推到哦出的 3 条推论

• 合并律: 若 $X\to Y$, $X\to Z$, 则有 $X\to YZ$.
• 分解律: 若 $X\to YZ$, 则有 $X\to Y$, $X\to Z$.
• 伪传递率: 若 $X\to Y$, $YW\to Z$, 则有 $XW\to Z$.

属性集闭包

推导出来的, 属性 $X$ 能决定的所有属性集合叫 $X$ 属性的闭包, 记作 $X^+$

求属性集闭包

前提: 有限的属性集合 $U$, $U$ 的子集 $X$, 以及在 $U$ 上成立的 $FD$ 集 $F$ , 求 $X$ 关于 $F$ 的闭包 $X^+$

具体步骤如下:

1. $X(0)=X$
2. $X(i+1)=X(i)A$, 其中 $A$ 满足以下条件:
   1. 在 $F$ 中寻找尚未使用过的
   2. $FD$ 左边是 $X(i)$ 的子集
3. 判断 $X(i+1)?=X(i)$, 若相等, 转到下一步, 否则返回上一步继续寻找
4. 输出 $X(i)$, 即 $X^+$

对于步骤 3 的判断, 以下 4 种方法是等价的:

1. $X(i+1)=X(i)$
2. $X(i)$ 中包含了全部属性
3. $F$ 中未使用的 $FD$ 左侧 找不到 $X(i)$ 的子集
4. $F$ 中未使用的 $FD$ 右侧 找到的都是 $X(i)$ 的子集

举例:
现在有关系模式 $R(U,F)$, 其中 $U=\{A,B,C,D,E,I\}$, $F=\{A\to D,AB\to I,BI\to E,CD\to I,E\to C\}$, 求 $(AE)^+$
解:
令 $X=\{AE\}$, $X(0)=X=\{AE\}$

在 $F$ 中找出左边是 $AE$ 子集的函数依赖, 其结果是: $A\to D$, $E\to C$.
所以, $X(1)=X(0)DC=AEDC$ (顺序无所谓)
判断 $X(1)\neq X(0)$, 继续寻找

在 $F$ 中未使用的 $FD$ 找出左边是 $AEDC$ 子集的函数依赖, 其结果是: $CD\to I$.
所以, $X(2)=X(1)I=AEDCI$, 显然 $X(2)\neq X(1)$ 继续寻找.

在 $F$ 中未使用的 $FD$ 找出左边是 $AEDCI$ 子集的函数依赖, 发现没有了, 停止寻找, 输出 $X(i)=AEDCI$

$F$ 的最小依赖集 $F_m$

如果函数依赖集 $F$ 满足一下条件, 则称为最小依赖集, 记为 $F_m$

• $F$ 的右侧都是单属性
• $F$ 中不存在多余依赖 (不存在任何依赖可以被其余依赖推出来)
• $F$ 的左侧不存在多余属性 (左侧删除任何属性都会导致依赖不成立)

每个函数依赖集 $F$ 都与它的最小依赖集 $F_m$ 等价

具体步骤:

1. 右边属性单一化
2. 去掉各依赖左边多余的属性
3. 去掉多余依赖

为什么要先去掉各依赖左边多余的属性?
因为如果先去掉多余依赖后, 去掉左边多余属性之后, 还有可能会出现新的冗余依赖.

举例:
设有关系模式 $R$, 其依赖集为:
$F=\{AB\to C,C\to A,BC\to D,ACD\to B,D\to EG,BE\to C,CG\to BD,CE\to AG \}$
求 $F$ 等价的最小依赖集 $F_m$
解:

1. 将右边的属性单一化
   $D\to EG \Rightarrow D\to E,D\to G$
   $CG\to BD \Rightarrow CG\to B,CG\to D$
   $CE\to AG \Rightarrow CE\to A, CE\to G$
   得到 $F=\{AB\to C,C\to A,BC\to D,ACD\to B,D\to E,D\to G,BE\to C,CG\to B,CG\to D,CE\to A,CE\to G \}$

2. 去掉左边多余属性

   1. 检查 $AB\to C$
      检查 $A$ 是否冗余: 去掉 $A$, 算 $B^+$, $B^+=B$, 不含 $C$, 所以 $A$ 不冗余
      检查 $B$ 是否冗余: 去掉 $B$, 算 $A^+$, $A^+=A$, 不含 $C$, 所以 $B$ 不冗余
      结论: $AB\to C$ 左部无冗余
   2. 同理检查 $BC\to D$
      $C^+=CA$, 不含 $D$, 所以 $B$ 不冗余
      $B^+=B$, 不含 $D$, 所以 $C$ 不冗余
      结论: $BC\to D$ 左部无冗余
   3. $ACD\to B$
      $(CD)^+=CDAEGB$, 含 $B$, 说明 $A$ 是冗余属性
      $(AD)^+=ADEG$, 不含 $B$, 所以 $C$ 不冗余
      $(AC)^+=AC$, 不含 $B$, 所以 $D$ 不冗余
      结论: $ACD\to B$ 应该移除冗余属性得到 $CD\to B$
   4. $BE\to C$
      $B^+=B$, 不含 $C$, 所以 $E$ 不冗余
      $E^+=E$, 不含 $C$, 所以 $B$ 不冗余
      结论: $BE\to C$ 左部无冗余
   5. $CG\to B$
      $C^+=CA$, 不含 $B$, 所以 $G$ 不冗余
      $G^+=G$, 不含 $B$, 所以 $C$ 不冗余
      结论: $CG\to B$ 左部无冗余
   6. $CG\to D$
      $C^+=CA$, 不含 $D$, 所以 $G$ 不冗余
      $G^+=G$, 不含 $D$, 所以 $C$ 不冗余
      结论: $CG\to D$ 左部无冗余
   7. $CE\to A$
      $C^+=CA$, 含 $A$, 说明 $E$ 是冗余属性
      $E^+=E$, 不含 $A$, 所以 $C$ 不冗余
      结论: $CE\to A$ 应该移除冗余属性得到 $C\to A$, 已经存在 $C\to A$, 所以需要移除, 或者在后面移除冗余依赖的时候移除也可以.
   8. $CE\to G$
      $C^+=CA$, 不含 $G$, 所以 $E$ 不冗余
      $E^+=E$, 不含 $G$, 所以 $C$ 不冗余
      结论: $CE\to G$ 左部无冗余

   最后得到: $F=\{AB\to C,C\to A,BC\to D,CD\to B,D\to E,D\to G,BE\to C,CG\to B,CG\to D,CE\to G \}$

3. 去掉冗余依赖
   一眼看过去, 可以直接判断本题的, 左侧仅有一个属性的 FD 无冗余依赖

   1. 检查 $AB\to C$ 是否冗余, 暂时移除 $AB\to C$
      计算 $(AB)^+=AB$
      结论: 不含 $C$, $AB\to C$ 不冗余
   2. 检查 $BC\to D$ 是否冗余, 暂时移除 $BC\to D$
      $(BC)^+=BCA$
      结论: 不含 $D$, $BC\to D$ 左部无冗余
   3. $CD\to B$, 暂时移除 $CD\to B$
      $(CD)^+=CDAEGB$
      结论: 含 $B$, 所以是冗余依赖, 直接移除
   4. $BE\to C$, 暂时移除 $BE\to C$
      $(BE)^+=BE$
      结论: 不含 $C$, $BE\to C$
   5. $CG\to B$, 暂时移除 $CG\to B$
      $(CG)^+=CGADE$ (这里因为前面移除了 $CD\to B$ 所以闭包里就没有 $B$ 了)
      结论: 不含 $B$, 所以 $CG\to B$ 不冗余
   6. $CG\to D$
      $(CG)^+=CGABDE$
      结论: 含 $D$, 所以是冗余依赖, 直接移除
   7. $CE\to G$
      $(CE)^+=CEA$
      结论: 不含 $G$, 所以 $CE\to G$ 不冗余

最终得到: $F=\{AB\to C,C\to A,BC\to D,D\to E,D\to G,BE\to C,CG\to B,CE\to G \}$

• 最小覆盖 (最小依赖集) 的化简过程通常是迭代式、逐步更新依赖集的:
  每做一次删除, 依赖集就更新一次; 后续所有闭包计算都基于当前最新的依赖集.

• $F_m$ 不是唯一的

求候选码(键)

能函数决定全部属性称为一个 超键
极小超键就是 候选键, 是不能再删减属性的超键
不能说 “最小超键” 因为 候选键 不止一个

这里只介绍 2 种计算方法: 图论判定法 和 多属性依赖集求解解法

在计算之前, 需要先给属性进行分类:

• L类: 仅出现在 $F$ 的函数依赖左边的属性
• R类: 仅出现在 $F$ 的函数依赖右边的属性
• N类: 在 $F$ 的函数依赖左右均未出现的属性
• LR类: 在 $F$ 的函数依赖左右均出现的属性

在分类的时候要从关系本身一个属性一个属性在函数依赖里面找, 不要直接在函数依赖里面找

图论判定法

如果依赖集等价的最小依赖集左边是单属性, 可以使用图论判定法求出所有候选键
我们需要画出函数依赖图, 函数依赖图是一个有序二元组 $(R,F)$, $R$ 中所有属性都是结点, 所有依赖都是有向边

1. 引入线/引出线:若结点 $A$ 到 $A$ 是连接, 则边 $A_i,A_j$ 是 $A_i$ 引出线, 是 $A_j$ 引入线
2. 原始点:只有引出线而无引入线旳结点
3. 终结点:只有引入线而无引出线的结点
4. 途中点:既有引入线又有引出线的结点
5. 孤立点:既无引入线又无引出线的结点
6. 关键点:原始点和孤立点都称为关键点
7. 关键尿性:关键点对应属性
8. 独立回路:不能被其他结点到达钓回路

求候选键具体步骤如下:

1. 求出F最小依赖集 $F_m$
2. 构造函数依赖图 $G$
3. 从该图中找出关键属性 $X$ (可为空).
4. 查看 $G$ 中有无独立回路, 若没有, 则输出 $X$ 即 $R$ 的唯一候选键, 转至步骤 6, 否则转至步骤 5
5. 从各个独立回路中各取一个结点对应属性, 并与 $X$ 组合成一个候选键, 然后重复这一过程, 直到取尽所有可能的组合为止, 此时结果即 $R$ 全部候选键.

举例:
设 $R(O,B,L,S,Q,D)$, 其函数依赖集 $F=\{S\to D,D\to S,I\to B,B\to I,B\to O,O\to B\}$, 求 $R$ 的所有候选键
解:

1. $F_m=\{S\to D,D\to S,I\to B,B\to I,B\to O,O\to B\}$
2. 构造函数依赖图
   
3. 关键属性集: ${Q}$
4. 共有 4 条回路, 但回路 $IBI$ 和 $BOB$ 不是独立回路, 而 $SDS$ 和 $IBOBI$ 是独立回路. 共有 $2\times 3=6$ 个候选键. 每个候选键都有 $1+2=3$ 个属性, 所以所有候选键为: $QSI$, $QSB$, $QSO$, $QDI$, $QDB$, $QDO$

多属性依赖集求解解法

具体步骤如下:

1. 将 $R$ 的所有属性分类: L类, R类, N类, LR类.
   令 $X$ 代表 L 类和 N 类, $Y$ 代表 LR 类
2. 求 $X^+$, 若 $X^+$ 包含 $R$ 的全部属性, 则 $X$ 为 $R$ 的唯一候选键, 转至步骤5, 否则转至步骤3
3. 在 $Y$ 中取一属性 $A$, 求 $(XA)^+$, 若 $A$ 包含 $R$ 的全部属性, 则 $A$ 为 $R$ 的候选键
   更换属性并反复进行这一过程, 直到试完 $Y$ 中所有属性为止
4. 如果已找出所有候选键, 则转至步骤5, 否则依次取两个, 三个, 等等, 求它们的属性闭包, 直到闭包包含R钓全部属性为止
5. 停止求解输出结果

举例:
有关系模式 $R(A,B,C,D,E)$, 其函数依赖集 $F=\{A\to BC,CD\to E,B\to D,E\to A\}$, 求 $R$ 的所有候选键
解:

1. X 类属性为 $\varnothing$, Y 类属性为 $A,B,C,D,E$
2. $A^+=ABCDE$, $B^+=BD$, $C^+=C$, $D^+=D$, $E^+=ABCDE$, 所以 $A$, $E$ 为 $R$ 的其中两个候选键
3. 由于 $B$, $C$, $D$ 属性还未出现在候选键中, 于是将其两两组合后与 X 类属性组合以求闭包:
   $(BC)^+=ABCDE, (BD)^+=BD, (CD)^+=ABCDE$
   因此 $BC$, $CD$ 为两个候选键
4. 所有 Y 类属性均已经出现在候选键中, 所以所有候选键为 $A$, $E$, $BC$, $CD$