函数依赖（Functional Dependency, FD）是数据库理论中关系模式设计与规范化的核心概念

函数依赖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 → YY ↛ XY → Z且Z ∉ XY则X → Z为传递依赖。Armstrong公理系统自反律、增广律、传递律可用于从给定FD集F逻辑推导出所有隐含的FD即F⁺闭包。-- 示例学生选课关系 SC(学号, 课程号, 成绩, 学生姓名, 课程名)-- 可能存在的函数依赖-- {学号} → {学生姓名}-- {课程号} → {课程名}-- {学号, 课程号} → {成绩} 主键决定所有属性-- 注意{学号} → {成绩} 不成立同一学生可选多门课体现部分依赖问题需分解以满足3NF。计算属性集 $ X $ 关于函数依赖集 $ F $ 的闭包 $ X^ $读作“X正闭包”是指在F的逻辑蕴涵下所有能被X函数决定的属性的集合。它是判断函数依赖是否成立、求候选键、构造最小覆盖等操作的基础算法。✅ 计算步骤贪心算法标准迭代法设初始闭包 $ X^{(0)} X $然后反复应用F中的函数依赖扩展当前闭包直到不再变化初始化令 $ X^{(0)} X $迭代扩展对每条 $ A \to B \in F $若 $ A \subseteq X^{(i)} $则将 $ B $ 加入闭包即$ X^{(i1)} X^{(i)} \cup B $注意B是属性集若 $ A \to B $ 中B为属性集则加入全部属性实际中更准确的做法是对每个 $ Y \to Z \in F $若 $ Y \subseteq X^{(i)} $则令 $ X^{(i1)} X^{(i)} \cup Z $重复步骤2直到 $ X^{(i1)} X^{(i)} $终止此时 $ 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 BA \subseteq {A} $ ⇒ 加入B → $ {A,B} $$ B \to CB \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):closureset(X)changedTruewhilechanged:changedFalseforlhs,rhsinF:# F为[(left_set, right_set), ...]如 ({A}, {B})iflhs.issubset(closure)andnotrhs.issubset(closure):closure|rhs changedTruereturnclosure# 示例调用F[({A},{B}),({B},{C}),({D},{A})]print(compute_closure({A},F))# {A, B, C}