在数据库理论中函数依赖Functional Dependency, FD和候选键Candidate Key是关系模式规范化的核心概念。函数依赖设关系模式 R(U)U 是属性集X、Y ⊆ U。若对 R 的任意合法实例 r只要 r 中任意两个元组在 X 上取值相同则它们在 Y 上的取值也必然相同则称 “X 函数决定 Y”记作 X → Y。例如在学生表Student(Sno, Sname, Dept, Head)中若每个学号 Sno 唯一确定学生姓名 Sname 和所在系 Dept且每个系 Dept 唯一对应系主任 Head则有Sno → Sname, DeptDept → Head。候选键是能唯一标识关系中每个元组的最小属性集即无冗余。它满足两个条件唯一性Uniqueness在关系的任一实例中不同元组在该属性集上的取值不重复即该属性集的值可唯一确定元组最小性Minimality其任何真子集都不满足唯一性。例如若Sno → {Sname, Dept, Head}且Sno是最小的即单个属性则Sno是候选键若Sno, Sname也能唯一标识元组但Sno已足够则{Sno, Sname}不是候选键因不满足最小性。函数依赖是推导候选键的基础通过给定的函数依赖集 F可计算属性集的闭包 X⁺即 X 能逻辑蕴含的所有属性若 X⁺ U全属性集且 X 的所有真子集闭包 ≠ U则 X 是候选键。-- 示例从函数依赖推导候选键概念性伪代码-- 给定 R(A,B,C,D), F {A→B, B→C, D→A}-- 计算 A⁺ {A,B,C} ≠ U → 不是键-- 计算 D⁺ {D,A,B,C} U → D 是超键又因 D 单属性 → 是候选键-- 进一步验证无更小超键 → D 是唯一候选键系统性地求解关系模式 R(U) 在函数依赖集 F 下的所有候选键需结合属性闭包Attribute Closure和最小超键搜索策略。以下是标准、可靠的算法步骤适用于中小型属性集对大规模问题可优化✅ 步骤概览基于闭包的穷举剪枝法1.预处理消除冗余函数依赖可选但推荐使用 Armstrong 公理化系统简化 F如合并、去除冗余依赖便于后续计算。2.确定“必须包含”的属性Leverage LHS/RHS 分析L-attributes只出现在左部或未出现可能属于候选键R-attributes只出现在右部且从不出现于左部不可能属于任何候选键因无法决定自身也不能被其他属性“生成”来参与唯一标识LR-attributes既在左部又在右部需进一步验证N-attributes从未在 F 中出现必须包含在所有候选键中因其无任何函数依赖约束只能靠自身取值区分元组。✅ 关键推论设 N {A ∈ U | A 不在 F 的任何 FD 左右部出现}则每个候选键 K 必满足 N ⊆ K。3.生成候选超键集合自底向上枚举 闭包检验令U U \ N剔除必须包含的 N 后剩余属性按属性个数 k 0, 1, 2, …, |U’| 枚举 U’ 的所有子集 X对每个 X计算闭包(X ∪ N)⁺注意必须含 N若(X ∪ N)⁺ U则X ∪ N是超键在所有超键中保留极小者即其任意真子集都不是超键→ 即为候选键。4.高效剪枝技巧避免全枚举若某集合 X 已是超键则其所有超集无需再检查因非最小若某集合 X 的闭包(X ∪ N)⁺不含某关键属性如某 R-attribute可提前跳过其超集使用广度优先搜索BFS从 |X|0 开始一旦找到超键即停止该层并记录再继续下一层以找更小/其他候选键。 示例演示设 R(A,B,C,D), F {A→B, B→C, D→A}U {A,B,C,D}F 中所有属性均出现 → N ∅枚举子集按大小k1{A}⁺ {A,B,C} ≠ U{B}⁺ {B,C}{C}⁺ {C}{D}⁺ {D,A,B,C} U → ✅ {D} 是候选键k2检查 {A,B} 等——但因 {D} 已是最小超键且无更小k1其他解故仅一个候选键{D}⚠️ 注意事项该算法时间复杂度最坏为 O(2^|U|·|F|·|U|)故实际应用中常配合启发式如先找“源属性”——入度为0的节点在FD图中加速工具辅助可借助数据库设计工具如Heath’s algorithm变种、Python 库如pydeps或自定义闭包函数实现自动化多候选键时需确保彼此互不包含候选键之间无子集关系。# Python 伪代码核心片段属性闭包计算defclosure(X,F):resultset(X)changedTruewhilechanged:changedFalseforlhs,rhsinF:# lhs→rhs 是一个FDifset(lhs).issubset(result)andnotset(rhs).issubset(result):result|set(rhs)changedTruereturnresult# 主逻辑枚举并验证略去剪枝细节U{A,B,C,D}F[([A],[B]),([B],[C]),([D],[A])]N{aforainUifall(anotinlhsrhsforlhs,rhsinF)}# 此例 N∅candidates[]forkinrange(1,len(U)1):forXincombinations(U,k):ifclosure(X,F)U:ifall(notset(K).issubset(X)forKincandidates):# 最小性检查candidates.append(X) 在数据库理论中，**函数依赖（Functional Dependency, FD）** 和 **候选键（Candidate Key）** 是关系模式规范化的核心概念
在数据库理论中函数依赖Functional Dependency, FD和候选键Candidate Key是关系模式规范化的核心概念。函数依赖设关系模式 R(U)U 是属性集X、Y ⊆ U。若对 R 的任意合法实例 r只要 r 中任意两个元组在 X 上取值相同则它们在 Y 上的取值也必然相同则称 “X 函数决定 Y”记作 X → Y。例如在学生表Student(Sno, Sname, Dept, Head)中若每个学号 Sno 唯一确定学生姓名 Sname 和所在系 Dept且每个系 Dept 唯一对应系主任 Head则有Sno → Sname, DeptDept → Head。候选键是能唯一标识关系中每个元组的最小属性集即无冗余。它满足两个条件唯一性Uniqueness在关系的任一实例中不同元组在该属性集上的取值不重复即该属性集的值可唯一确定元组最小性Minimality其任何真子集都不满足唯一性。例如若Sno → {Sname, Dept, Head}且Sno是最小的即单个属性则Sno是候选键若Sno, Sname也能唯一标识元组但Sno已足够则{Sno, Sname}不是候选键因不满足最小性。函数依赖是推导候选键的基础通过给定的函数依赖集 F可计算属性集的闭包 X⁺即 X 能逻辑蕴含的所有属性若 X⁺ U全属性集且 X 的所有真子集闭包 ≠ U则 X 是候选键。-- 示例从函数依赖推导候选键概念性伪代码-- 给定 R(A,B,C,D), F {A→B, B→C, D→A}-- 计算 A⁺ {A,B,C} ≠ U → 不是键-- 计算 D⁺ {D,A,B,C} U → D 是超键又因 D 单属性 → 是候选键-- 进一步验证无更小超键 → D 是唯一候选键系统性地求解关系模式 R(U) 在函数依赖集 F 下的所有候选键需结合属性闭包Attribute Closure和最小超键搜索策略。以下是标准、可靠的算法步骤适用于中小型属性集对大规模问题可优化✅ 步骤概览基于闭包的穷举剪枝法1.预处理消除冗余函数依赖可选但推荐使用 Armstrong 公理化系统简化 F如合并、去除冗余依赖便于后续计算。2.确定“必须包含”的属性Leverage LHS/RHS 分析L-attributes只出现在左部或未出现可能属于候选键R-attributes只出现在右部且从不出现于左部不可能属于任何候选键因无法决定自身也不能被其他属性“生成”来参与唯一标识LR-attributes既在左部又在右部需进一步验证N-attributes从未在 F 中出现必须包含在所有候选键中因其无任何函数依赖约束只能靠自身取值区分元组。✅ 关键推论设 N {A ∈ U | A 不在 F 的任何 FD 左右部出现}则每个候选键 K 必满足 N ⊆ K。3.生成候选超键集合自底向上枚举 闭包检验令U U \ N剔除必须包含的 N 后剩余属性按属性个数 k 0, 1, 2, …, |U’| 枚举 U’ 的所有子集 X对每个 X计算闭包(X ∪ N)⁺注意必须含 N若(X ∪ N)⁺ U则X ∪ N是超键在所有超键中保留极小者即其任意真子集都不是超键→ 即为候选键。4.高效剪枝技巧避免全枚举若某集合 X 已是超键则其所有超集无需再检查因非最小若某集合 X 的闭包(X ∪ N)⁺不含某关键属性如某 R-attribute可提前跳过其超集使用广度优先搜索BFS从 |X|0 开始一旦找到超键即停止该层并记录再继续下一层以找更小/其他候选键。 示例演示设 R(A,B,C,D), F {A→B, B→C, D→A}U {A,B,C,D}F 中所有属性均出现 → N ∅枚举子集按大小k1{A}⁺ {A,B,C} ≠ U{B}⁺ {B,C}{C}⁺ {C}{D}⁺ {D,A,B,C} U → ✅ {D} 是候选键k2检查 {A,B} 等——但因 {D} 已是最小超键且无更小k1其他解故仅一个候选键{D}⚠️ 注意事项该算法时间复杂度最坏为 O(2^|U|·|F|·|U|)故实际应用中常配合启发式如先找“源属性”——入度为0的节点在FD图中加速工具辅助可借助数据库设计工具如Heath’s algorithm变种、Python 库如pydeps或自定义闭包函数实现自动化多候选键时需确保彼此互不包含候选键之间无子集关系。# Python 伪代码核心片段属性闭包计算defclosure(X,F):resultset(X)changedTruewhilechanged:changedFalseforlhs,rhsinF:# lhs→rhs 是一个FDifset(lhs).issubset(result)andnotset(rhs).issubset(result):result|set(rhs)changedTruereturnresult# 主逻辑枚举并验证略去剪枝细节U{A,B,C,D}F[([A],[B]),([B],[C]),([D],[A])]N{aforainUifall(anotinlhsrhsforlhs,rhsinF)}# 此例 N∅candidates[]forkinrange(1,len(U)1):forXincombinations(U,k):ifclosure(X,F)U:ifall(notset(K).issubset(X)forKincandidates):# 最小性检查candidates.append(X)