函数依赖（Functional Dependency, FD）是数据库理论中关系模式设计与规范化的核心概念，用于描述关系中属性之间的语义约束。形式化定义为：设R(U)是一个关系模式，U是属性集，X、Y ⊆ U。若对R的任意两个元组t₁和t₂，只要t₁[X] = t₂[X]，就有t₁[Y] = t₂[Y]，则称“X函数决定Y”，记作 X → Y。即Y的取值由X唯一确定。

函数依赖反映了数据内在的业务规则（如“学号 → 姓名”表示每个学号唯一对应一个姓名），是判断候选键、进行模式分解、消除数据冗余与异常（插入、删除、更新异常）的基础。它支撑着数据库规范化理论（如1NF、2NF、3NF、BCNF等范式）的设计与验证。

常见类型包括：

• 平凡函数依赖：Y ⊆ X（恒成立）；
• 非平凡函数依赖：Y ⊈ X；
• 完全函数依赖：X → Y 且Y不函数依赖于X的任何真子集；
• 部分函数依赖：存在X的真子集X’ ⊂ X，使得X’ → Y；
• 传递函数依赖：X → Y，Y ↛ X，Y → Z，且Z ∉ XY，则X → Z为传递依赖。

Armstrong公理系统（自反律、增广律、传递律）可用于从给定FD集F逻辑推导出所有隐含的FD（即F⁺，闭包）。

-- 示例：学生选课关系 SC(学号, 课程号, 成绩, 学生姓名, 课程名)-- 可能存在的函数依赖：-- {学号} → {学生姓名}-- {课程号} → {课程名}-- {学号, 课程号} → {成绩} （主键决定所有属性）-- 注意：{学号} → {成绩} 不成立（同一学生可选多门课），体现部分依赖问题，需分解以满足3NF。

计算属性集 $ X $ 关于函数依赖集 $ F $ 的闭包 $ X^+ $（读作“X正闭包”），是指在F的逻辑蕴涵下，所有能被X函数决定的属性的集合。它是判断函数依赖是否成立、求候选键、构造最小覆盖等操作的基础算法。

✅ 计算步骤（贪心算法，标准迭代法）：

设初始闭包 $ X^{(0)} = X $，然后反复应用F中的函数依赖，扩展当前闭包，直到不再变化：

1. 初始化：令 $ X^{(0)} = X $；
2. 迭代扩展：对每条 $ A \to B \in F $，若 $ A \subseteq X^{(i)} $，则将 $ B $ 加入闭包，即
   $ X^{(i+1)} = X^{(i)} \cup B $（注意：B是属性集，若 $ A \to B $ 中B为属性集，则加入全部属性）；
   实际中更准确的做法是：对每个 $ Y \to Z \in F $，若 $ Y \subseteq X^{(i)} $，则令 $ X^{(i+1)} = X^{(i)} \cup Z $；
3. 重复步骤2，直到 $ X^{(i+1)} = X^{(i)} $；
4. 终止：此时 $ X^+ = X^{(i)} $。

⚠️ 注意：每次迭代应扫描整个F，并尽可能多地应用所有可触发的FD（不需按顺序，但需确保本轮中新增属性能在本轮后续FD中被利用——因此常采用“循环+标记”或多次遍历策略；实际实现中可使用“队列驱动”或“逐轮扩展”确保收敛）。

🌟 示例：

设关系模式 $ R(A,B,C,D) $，函数依赖集
$ F = { A \to B,, B \to C,, D \to A } $，求 $ {A}^+ $ 和 $ {D}^+ $。

• 求 $ {A}^+ $：

  • 初始：$ {A}^+ = {A} $
  • $ A \to B：：：A \subseteq {A} $ ⇒ 加入B → $ {A,B} $
  • $ B \to C：：：B \subseteq {A,B} $ ⇒ 加入C → $ {A,B,C} $
  • 再无FD左部被包含 ⇒ 停止 ⇒ $ {A}^+ = {A,B,C} $

• 求 $ {D}^+ $：

  • 初始：$ {D} $
  • $ D \to A $ ⇒ 加A → $ {D,A} $
  • $ A \to B $ ⇒ 加B → $ {D,A,B} $
  • $ B \to C $ ⇒ 加C → $ {D,A,B,C} = {A,B,C,D} $
    ⇒ $ {D}^+ = {A,B,C,D} $，即D是超键。

💡 实用技巧：

• 若 $ X^+ $ 包含全部属性，则X是超键；
• 判断 $ X \to Y $ 是否属于 $ F^+ $？ ⇔ 检查 $ Y \subseteq X^+ $；
• 编程实现时可用集合+while循环，每次遍历F，记录是否发生扩展。

defcompute_closure(X,F):closure=set(X)changed=Truewhilechanged:changed=Falseforlhs,rhsinF:# F为[(left_set, right_set), ...]，如 ({'A'}, {'B'})iflhs.issubset(closure)andnotrhs.issubset(closure):closure|=rhs changed=Truereturnclosure# 示例调用：F=[({'A'},{'B'}),({'B'},{'C'}),({'D'},{'A'})]print(compute_closure({'A'},F))# {'A', 'B', 'C'}