函数依赖

函数依赖（Functional Dependency，简称 FD）是对 关系模型（表结构）的一种断言或约束，它描述了关系中属性值之间的一种特定关系 [2]。

一个函数依赖 X → Y（读作“X 函数决定 Y”或“Y 函数依赖于 X”）是指，在关系 R 中，如果任意两个元组（行）在属性集 X 上拥有相同的值，那么它们在属性集 Y 上的值也必须相同 [2]。

• X：被称为决定因素（Determinant）或左侧（Left-hand side），它可以是一个或多个属性的集合。
• Y：被称为被决定因素（Dependent）或右侧（Right-hand side），它也可以是一个或多个属性的集合。

这意味着对于属性集 X 的每一个唯一值，属性集 Y 都有且只有一个唯一值与之对应。可以将其类比为数学中的函数关系：$f(X)=Y$。

示例： 考虑一个 Drinkers 关系，包含属性 (name, addr, beersLiked, manf, favBeer) [4]。

1. name → addr：表示一个饮酒者的姓名函数决定其地址。这意味着，如果关系中有两个元组的 name 值相同（例如，都是“Janeway”），那么它们的 addr 值也必须相同（例如，都住在“Voyager”）[5]。
2. beersLiked → manf：表示一种啤酒决定其制造商。这意味着，如果关系中有两个元组的 beersLiked 值相同（例如，都是“Bud”），那么它们的 manf 值也必须相同（例如，都是“A.B.”）[5]。

函数依赖的类型：

• 平凡函数依赖

  平凡函数依赖 (Trivial FD)：如果 Y 是 X 的子集（Y ⊆ X），则称 X → Y 是一个平凡函数依赖。这类依赖总是成立的，因为它仅仅说明一个属性集能够决定它自己的一部分或全部属性（例如，{Name, Address} → Name）。

  指向原始笔记的链接

• 非平凡函数依赖

  非平凡函数依赖 (Nontrivial FD)：如果 Y 不是 X 的子集（$Y⊈X$），则称 X → Y 是一个非平凡函数依赖 [12]。这类依赖在数据库设计中更具意义，因为它表示了数据值之间有价值的约束关系。

  指向原始笔记的链接

• 完全函数依赖

  完全函数依赖 (Full Functional Dependency)：如果 X → Y，并且 Y 不函数依赖于 X 的任何真子集，则称 Y 完全函数依赖于 X [64, 65]。

  指向原始笔记的链接

• 部分函数依赖

  部分函数依赖 (Partial Functional Dependency)：如果 X → Y，但 Y 也函数依赖于 X 的某个真子集，则称 Y 部分函数依赖于 X。

  指向原始笔记的链接

• 传递函数依赖

  传递函数依赖 (Transitive Functional Dependency)：A → B；B → C；B 不包含 A（即 B 不是候选码的一部分或不包含在主键中）；A 是候选码的一部分或主键。如果这些条件都满足，则称 C 对 A 存在传递函数依赖 。

  指向原始笔记的链接

函数依赖的重要性

函数依赖是关系数据库设计理论的基石，尤其在 范式理论（Normal Forms） 中扮演核心角色，用于指导数据库模式的分解和优化 [1, 37]。

• 识别冗余 (Redundancy)：FD 有助于发现数据中的冗余。例如，如果 beersLiked → manf 存在，但 manf 在 Drinkers 表中多次重复出现同一个啤酒的制造商信息，就存在冗余 [32]。
• 避免异常 (Anomalies)：数据冗余会导致更新异常（Update Anomaly）、删除异常（Deletion Anomaly）和插入异常（Insertion Anomaly） [31, 33]。函数依赖的违反会导致这些问题。
  • 更新异常：如果某个事实存在多处记录，只更新其中一处，可能导致数据不一致 [31, 33]。
  • 删除异常：删除某个元组时，可能意外地丢失不应丢失的重要事实 [31, 33]。
  • 插入异常：无法插入某些事实，除非插入其他不相关的事实 [31]。
• 确定键 (Keys)：一个关系模式的 超键 是能够函数决定该关系中所有属性的属性集 [6]。而键是最小的超键，即其任何真子集都不能作为超键 [6]。函数依赖是发现和验证关系键的基础。
• 规范化 (Normalization)：通过将关系分解为更小、更优化的关系，以消除冗余和各种异常。例如，第二范式（2NF）要求非主属性完全函数依赖于码 [66]，而第三范式（3NF）和 BCNF 则进一步处理传递依赖和非主属性对 超键 的依赖问题。
• Armstrong 公理系统：这是一套用于推理函数依赖的有效且完备的公理系统，包括自反律（Reflexivity）、增广律（Augmentation）和传递律（Transitivity）。这些规则允许我们从已知的 FD 集合推导出所有逻辑上蕴含的 FDs。

函数依赖定义证明

要直接使用定义证明 函数依赖（FD），而不是依赖 Armstrong 公理系统，您需要从函数依赖的基本含义出发，通过逻辑推导来展示一个 FD 是如何被另一组 FD 所蕴含的。

函数依赖 X → Y 的定义是：对于关系 R 的任何一个关系实例 r，如果 r 中任意两个元组 t 和 s 在属性集 X 上的值都相等（即 t[X] = s[X]），那么它们在属性集 Y 上的值也必须相等（即 t[Y] = s[Y]）。

以下是使用定义证明函数依赖的步骤和示例：

证明步骤：

1. 明确已知条件： 列出所有已知的函数依赖（F）。假设您有一个关系 R，并且它的任何实例都必须满足 F 中的所有函数依赖。
2. 明确目标： 确定您要证明的函数依赖 X → Y。
3. 选取任意两个元组： 考虑关系 R 的任意一个实例 r，并从 r 中选取任意两个元组 t1 和 t2。
4. 设定前提条件： 假设这两个元组 t1 和 t2 在 X 上的值是相等的，即 t1[X] = t2[X]。这是证明 X → Y 所需要的前置条件。
5. 运用已知 FD 推导： 使用已知条件中给定的函数依赖 F，结合 t1[X] = t2[X] 这个前提，一步一步地推导，直到能够得出 t1[Y] = t2[Y]。在每一步推导时，都必须明确指出是依据哪一个已知 FD 的定义来得出新的相等关系。
6. 得出结论： 如果能够成功推导出 t1[Y] = t2[Y]，那么根据函数依赖的定义，就证明了 X → Y 被 F 逻辑蕴含。

示例：证明传递律 (Transitivity) A → B 和 B → C 蕴含 A → C

• 已知条件：
  • A → B （根据定义：如果 t1[A] = t2[A]，则 t1[B] = t2[B]）
  • B → C （根据定义：如果 t1[B] = t2[B]，则 t1[C] = t2[C]）
• 目标： 证明 A → C

证明：

1. 考虑关系 R 的任意一个实例 r。
2. 从 r 中选取任意两个元组 t1 和 t2。
3. 设定前提条件： 假设 t1[A] = t2[A]。
4. 运用已知 A → B：
   • 由于 A → B 成立，并且我们有 t1[A] = t2[A]。
   • 根据 A → B 的定义，我们可以得出 t1[B] = t2[B]。
5. 运用已知 B → C：
   • 现在我们有 t1[B] = t2[B]。
   • 由于 B → C 成立，根据 B → C 的定义，我们可以得出 t1[C] = t2[C]。
6. 得出结论：
   • 我们从 t1[A] = t2[A] 出发，成功推导出了 t1[C] = t2[C]。
   • 因此，根据函数依赖 A → C 的定义，我们证明了 A → C 成立。

通过这种方式，您无需引用 Armstrong 公理系统中的任何规则，而是直接基于函数依赖的定义，一步步地展示逻辑蕴含的过程。

指向原始笔记的链接

最小函数依赖

一个函数依赖集 F 被称为极小函数依赖集，如果满足以下三个条件:

1. F 中任一函数依赖的右部仅含一个属性。
2. F 中不存在这样的函数依赖 X→A，使得从 F 中去掉 X→A 后得到的函数依赖集与 F 等价。
3. F 中不存在这样的函数依赖 X→A，X 有真子集 Z 使得将 F 中的 X→A 替换为 Z→A 后得到的函数依赖集与 F 等价（即对 X 的左部进行简化）。

计算最小函数依赖

计算（或构造）一个最小函数依赖集（也称为极小函数依赖集或最小覆盖）的步骤如下：

要从给定的函数依赖集 F 构造一个最小函数依赖集 Fm，可以采用以下三步处理方法 [1]:

1. 右部单一化：逐一检查 F 中的函数依赖 X→Y。如果 Y 是多个属性 A1A2…Ak (k>1)，则用{X→A1, X→A2, …, X→Ak}来取代 X→Y。这一步确保所有函数依赖的右部都只有一个属性。

2. 去除多余的函数依赖：逐一检查当前 Fm 中的每个函数依赖 X→A。令 G 为 Fm 去掉 X→A 后得到的函数依赖集。检查属性 A 是否能由 X 在函数依赖集 G 下推出（即 A 是否属于 X 关于 G 的闭包 XG+）。如果 A∈XG+，则 X→A 是多余的，可以从 Fm 中去掉。重复此步骤直到没有函数依赖可以被去除。

3. 左部最小化：逐一检查当前 Fm 中的每个函数依赖 X→A。假设 X 由多个属性 $B_1,B_2,\dots B_m$ 组成。逐一考察每个属性 $B_i(i=1,2,\dots ,m)$。检查属性 A 是否能由 X 去掉 Bi 后得到的属性集（$X-Bi$）在函数依赖集 $F_m$ 下去推出（即 A 是否属于 $(X-B_i)F_m^{+}$）。如果 $A\in (X-B_i)F_m^{+}$，则可以将 X 中的 Bi 去掉，用 X-Bi 取代 X 作为函数依赖的左部。对每个函数依赖的左部重复此步骤直到不能再简化。

经过以上三步处理后得到的函数依赖集就是一个最小函数依赖集 Fm [1]。需要注意的是，对于同一个原始函数依赖集 F，其最小函数依赖集 Fm 可能不是唯一的 [1]。

进行步骤 2 和步骤 3 时，需要用到计算属性集闭包 XF+ 的算法 [1]。引理 2 指出，X→Y 能由函数依赖集 F 根据 Armstrong 公理导出的充要条件是 Y⊆XF+ [1]。因此，判断 X→A 是否能从某个函数依赖集 G 推出（即是否 A∈XG+），可以通过计算 X 关于 G 的闭包 XG+ 并检查 A 是否包含在其中来完成 [1]。

指向原始笔记的链接

指向原始笔记的链接