函数依赖与关系模式设计

函数依赖基础

函数依赖的定义

函数依赖是关系数据库设计中描述属性之间约束的核心概念：

• 函数依赖：如果关系 R 中任意两个元组在属性集 X 上取值相同，则它们在属性集 Y 上的取值也必须相同，记为 $X\to Y$。

  • X 称为决定因素（或左部），Y 称为依赖因素（或右部）
  • X 函数决定 Y，或 Y 函数依赖于 X
  • 例如：name → addr favBeer 表示姓名决定了地址和喜欢的啤酒

• 逻辑蕴含：如果关系 $R(U,F)$ 的任意关系实例 r 都满足函数依赖 $X\to Y$，则称函数依赖集 F 逻辑蕴含函数依赖 $X\to Y$，记为 $F\models X\to Y$。

Armstrong公理系统

Armstrong公理系统是函数依赖的基本推理规则，可以用来推导函数依赖的所有逻辑结果：

1. 自反律（Reflexivity）

   • 如果 $Y\subseteq X\subseteq U$，则 $X\to Y$ 为 F 所蕴含
   • 直观理解：一个属性集总是能决定它的子集

2. 增广律（Augmentation）

   • 如果 $X\to Y$ 为 F 所蕴含，且 $Z\subseteq U$，则 $XZ\to YZ$ 为 F 所蕴含
   • 直观理解：如果X决定Y，那么在X和Y两边添加相同的属性Z后，关系仍然成立

3. 传递律（Transitivity）

   • 如果 $X\to Y$ 和 $Y\to Z$ 为 F 所蕴含，则 $X\to Z$ 为 F 所蕴含
   • 直观理解：依赖关系具有传递性

函数依赖的推理规则

基于Armstrong公理系统，可以推导出以下常用的函数依赖推理规则：

1. 合并规则

   • 如果 $X\to Y$ 和 $X\to Z$，则 $X\to YZ$
   • 例如：已知 $A\to B$ 和 $A\to C$，可推导 $A\to BC$

2. 分解规则

   • 如果 $X\to YZ$，则 $X\to Y$ 和 $X\to Z$
   • 例如：已知 $A\to BC$，可推导 $A\to B$ 和 $A\to C$

3. 伪传递规则

   • 如果 $X\to Y$ 和 $WY\to Z$，则 $XW\to Z$
   • 例如：已知 $A\to B$ 和 $CB\to D$，可推导 $AC\to D$

闭包计算

属性闭包

• 属性闭包：给定函数依赖集F和属性集X，X关于F的属性闭包（记为 $X_F^{+}$）是X在F下能决定的所有属性的集合。
• 用途：
  • 判断函数依赖 $X\to Y$ 是否被F逻辑蕴含（检查Y是否包含在$X_F^{+}$中）
  • 判断属性集X是否为关系模式的超键（检查$X_F^{+}$是否等于U）
  • 判断属性集X是否为关系模式的候选码（检查X是否为极小的使$X_F^{+}$ = U的属性集）

函数依赖闭包

• 函数依赖闭包：给定函数依赖集F，F的闭包（记为$F^{+}$）是F所逻辑蕴含的所有函数依赖的集合。
• 计算方法：通过Armstrong公理系统从F出发推导所有可能的函数依赖。
• 性质：
  • 如果$X\to Y\in F^{+}$，则$F\models X\to Y$
  • 两个函数依赖集F和G是等价的，当且仅当$F^{+}=G^{+}$

闭包计算算法

属性闭包的计算算法是函数依赖理论的核心：

属性闭包计算算法：

1. 初始化：令 $X^{(0)}=X$
2. 迭代扩展：对于每一步$i$，找到所有满足 $V\to W\in F$ 且 $V\subseteq X^{(i)}$ 的函数依赖，将W中不在$X^{(i)}$中的属性添加到$X^{(i)}$中，得到$X^{(i+1)}$
3. 终止条件：当$X^{(i+1)}=X^{(i)}$时停止，此时$X^{(i)}$即为$X_F^{+}$

示例： 计算 $(AB{)}_F^{+}$，其中 $F=\{AB\to C,B\to D,C\to E,EC\to B,AC\to B\}$

1. 初始：$X^{(0)}=AB$
2. 第一次迭代：
   • $AB\to C$：加入$C$，得到$ABC$
   • $B\to D$：加入$D$，得到$ABCD$
3. 第二次迭代：
   • $C\to E$：加入$E$，得到$ABCDE$
4. 第三次迭代：没有新属性加入，停止
5. 结果：$(AB{)}_F^{+}=ABCDE$

最小函数依赖集

最小依赖集的定义

最小函数依赖集（也称为极小覆盖或规范覆盖）是一个等价于原函数依赖集F的简化版本，满足以下条件：

1. 每个函数依赖的右部仅包含单个属性
2. 无法移除任何函数依赖而保持等价性
3. 无法将任何函数依赖的左部替换为其真子集而保持等价性

意义：最小函数依赖集消除了冗余，是设计关系模式和判断范式的基础。

最小依赖集的计算步骤

计算最小函数依赖集的步骤如下：

1. 右部单一化

   • 将每个函数依赖 $X\to Y_1{Y}_2...Y_n$ 拆分为一组函数依赖 $X\to Y_1,X\to Y_2,...,X\to Y_n$

2. 去除冗余依赖

   • 对于每个函数依赖 $X\to A$，检查是否可以从F中移除而不改变$F^{+}$
   • 具体方法：计算X在$F-\{X\to A\}$下的属性闭包，如果闭包包含A，则该依赖是冗余的

3. 左部简化

   • 对于每个函数依赖 $X\to A$，检查是否可以用X的真子集Z替代X
   • 具体方法：对于X中的每个属性B，计算$(X-\{B\})$在F中的属性闭包，如果闭包包含A，则B是冗余的

计算示例

计算$F=\{AB\to C,B\to D,C\to E,EC\to B,AC\to B\}$的最小函数依赖集：

1. 右部单一化：F已经满足右部单一化

2. 去除冗余依赖：

   • 检查 $AB\to C$：在$F-\{AB\to C\}$下，$(AB{)}_{F-\{AB\to C\}}^{+}=ABD$，不包含C，所以$AB\to C$不是冗余的
   • 检查 $B\to D$：$(B{)}_{F-\{B\to D\}}^{+}=B$，不包含D，所以$B\to D$不是冗余的
   • 检查 $C\to E$：$(C{)}_{F-\{C\to E\}}^{+}=C$，不包含E，所以$C\to E$不是冗余的
   • 检查 $EC\to B$：$(EC{)}_{F-\{EC\to B\}}^{+}=ECB$，包含B，所以$EC\to B$是冗余的，移除
   • 检查 $AC\to B$：$(AC{)}_{F-\{AC\to B\}}^{+}=ACEB$，包含B，所以$AC\to B$是冗余的，移除

3. 左部简化：

   • 对于 $AB\to C$：

     • 检查A：$(B{)}_F^{+}=BD$，不包含C，所以A不是冗余的
     • 检查B：$(A{)}_F^{+}=A$，不包含C，所以B不是冗余的

   • 对于 $B\to D$：B是单属性，无法简化

   • 对于 $C\to E$：C是单属性，无法简化

4. 最终结果：$F_m=\{AB\to C,B\to D,C\to E\}$

关系模式的分解与范式

候选码与超键

• 超键(Superkey)：关系模式R中的属性集K，若K函数决定R的所有属性，则K为R的超键。
• 候选码(Candidate Key)：R的极小超键，即不包含任何真子集是超键的超键。
• 主码(Primary Key)：从候选码中指定的一个，用作关系的唯一标识。
• 主属性(Prime Attribute)：包含在任一候选码中的属性。
• 非主属性(Non-prime Attribute)：不包含在任何候选码中的属性。

范式层次

关系模式的范式层次描述了关系模式对函数依赖的符合程度：

1. 第一范式(1NF)

   • 关系的每个属性都是原子的（不可再分）
   • 所有关系数据库都满足1NF

2. 第二范式(2NF)

   • 满足1NF
   • 每个非主属性完全函数依赖于每个候选码
   • 消除了部分依赖

3. 第三范式(3NF)

   • 满足2NF
   • 每个非主属性不传递依赖于任何候选码
   • 消除了传递依赖

4. BC范式(BCNF)

   • 对于每个非平凡函数依赖$X\to Y$，X都是超键
   • BCNF比3NF更严格，消除了所有基于函数依赖的冗余

模式分解

模式分解是将一个关系模式分解为若干个更小的关系模式，以消除冗余和异常：

分解为BCNF的步骤：

1. 找到违反BCNF的函数依赖$X\to Y$（X不是超键）
2. 计算$X_F^{+}$
3. 将R分解为$R_1=X_F^{+}$和$R_2=X\cup (R-X_F^{+})$
4. 递归应用于$R_1$和$R_2$，直到所有关系都满足BCNF

示例： 分解$R=ABCDE$，$F=\{A\to BC,CD\to E,B\to D,E\to A\}$：

1. 检查$A\to BC$：A不是超键（$A_F^{+}=ABCDE$但A不是极小的）
2. $A_F^{+}=ABCDE$
3. 分解为$R_1=ABCDE$和$R_2=A$，但$R_2$已包含在$R_1$中
4. 检查$CD\to E$：CD不是超键
5. $(CD{)}_F^{+}=CDEABC=ABCDE$
6. 分解为$R_1=CDE$和$R_2=CD\cup (ABCDE-CDE)=ABCD$
7. 继续递归检查...

3NF合成算法： 当BCNF分解可能导致函数依赖无法保持时，可使用3NF合成算法：

1. 找到F的最小覆盖$F_m$
2. 对$F_m$中每个函数依赖$X\to A$创建一个关系模式$R_i=XA$
3. 如果没有任何模式包含候选码，则添加一个只包含候选码的关系模式
4. 如果某个关系模式被其他关系模式完全包含，则可以去除