函数依赖Functional Dependency, FD是关系数据库理论中的核心概念用于描述关系模式中属性之间的约束关系。形式化定义为在关系模式 $ R(U) $ 中若对 $ R $ 的任意两个元组 $ t_1 $ 和 $ t_2 $只要 $ t_1[X] t_2[X] $ 就必有 $ t_1[Y] t_2[Y] $则称属性集 $ X $ 函数决定 $ Y $记作 $ X \rightarrow Y $。其中 $ X, Y \subseteq UX $ 称为决定因素左部$ Y $ 为依赖项右部。候选键Candidate Key是能够唯一标识关系中每个元组的极小超键超键Superkey能唯一标识元组的属性集即其值在关系中无重复候选键不含多余属性的超键即若从其中移除任一属性就不再具有唯一标识能力即不满足超键性质。候选键一定是最小的函数决定全属性集 $ U $ 的属性集即满足 $ K \rightarrow U $且对任意真子集 $ K’ \subset K $均有 $ K’ \nrightarrow U $。二者关系密切所有候选键都必须满足 $ K \rightarrow U $即函数决定整个属性集通过给定的函数依赖集 $ F $可利用属性闭包算法如 $ X^ $ 计算判断某属性集是否为超键或候选键候选键的求解常依赖于函数依赖推理如Armstrong公理系统、属性闭包、最小覆盖等。例如关系模式 $ R(A,B,C,D) $函数依赖集 $ F {A \rightarrow B,, B \rightarrow C,, D \rightarrow A} $计算 $ D^ DAB C ABCD U $故 $ D $ 是超键又因单属性故 $ D $ 是候选键同理 $ A^ ABC \neq UB^ BCAD^ $ 非极小故仅 $ D $ 是候选键本例中。# 示例计算属性闭包 X⁺ 关于函数依赖集 Fdefcompute_closure(X,F,U):X: 初始属性集字符串或集合F: FD列表如 [(A,B), (B,C)]U: 全属性集closureset(X)changedTruewhilechanged:changedFalseforlhs,rhsinF:ifset(lhs).issubset(closure)andnotset(rhs).issubset(closure):closure.update(rhs)changedTruereturnclosure# 使用示例对应上述例子U{A,B,C,D}F[(A,B),(B,C),(D,A)]print(compute_closure({D},F,U))# 输出: {A, B, C, D} → 即 D⁺ U系统性地求出关系模式 $ R(U) $ 的所有候选键需结合函数依赖集 $ F $核心思想是找出所有极小的超键即满足 $ X^ U $属性闭包等于全属性集且 $ \forall A \in X $有 $ (X \setminus {A})^ \neq U $ 的属性子集 $ X \subseteq U $。以下是被广泛采用的经典算法基于属性闭包与搜索剪枝兼顾正确性与实用性适用于中小型属性集|U| ≤ 15~20✅ 步骤详解算法名称Candidate Key Enumeration via Closure and Minimality Check1.预处理计算所有单属性闭包对每个 $ A \in U $计算 $ A^ $若 $ A^ U $则 $ {A} $ 是候选键 → 加入结果集并跳过含 $ A $ 的更大集合因候选键必须极小。2.按大小分层枚举BFS 或逐级生成初始化候选集 $ \mathcal{C} \emptyset $令 $ k 1 $依次尝试大小为 $ k $ 的属性子集生成所有 $ \binom{|U|}{k} $ 个 $ k $-元子集 $ X $剪枝1超键检查若 $ X^ \neq U $跳过剪枝2极小性检查对每个真子集 $ Y \subset X|Y| k-1 $若已有 $ Y \in \mathcal{C} $则 $ X $ 不可能是候选键因含更小候选键跳过若通过两关则 $ X $ 是候选键加入 $ \mathcal{C} $当某层无新候选键且 $ k |U| $继续 $ k1 $若 $ k |U| $ 仍无解则无候选键理论不可能因 $ U $ 总是超键。3.优化技巧使用位掩码或整数编码子集提升生成与查重效率利用依赖闭包预先简化 $ F $如求最小覆盖 $ F_{\text{min}} $减少闭包计算开销对称性剪枝若 $ X $ 已是候选键则所有包含 $ X $ 的集合直接排除实际工具如数据库设计工具、pydbtools或SQLFacts常内置此算法。 示例演示设 $ R(A,B,C,D)F { A \rightarrow B,, B \rightarrow C,, D \rightarrow A } $$ U {A,B,C,D} $计算单属性闭包$ A^ ABC \neq U $$ B^ BC \neq U $$ C^ C $$ D^ DAB C U $ → ✅ $ {D} $ 是候选键排除所有含 $ D $ 的更大集合如 $ AD, BD, CD, ABD $ 等因其非极小剩余不含 $ D $ 的 2-元子集$ AB, AC, BC $$ AB^ ABC \neq U $$ AC^ AC $$ BC^ BC $3-元子集不含 $ DABC $ → $ ABC^ ABC \neq U $含 $ D $ 的已剪枝故唯一候选键$ {D} $⚠️ 注意事项最坏时间复杂度为 $ O(2^{|U|} \cdot \text{poly}(|F|)) $故不适用于超大属性集20此时需启发式或近似方法若存在多个候选键它们等价于逻辑上互不可导无函数依赖可由另一候选键推出所有候选键的并集称为主属性集Prime Attributes其余为非主属性。# 简化版 Python 实现仅示意生产环境建议用专业库如 sqlparse 自定义闭包fromitertoolsimportcombinationsdeffind_candidate_keys(U,F):Uset(U)candidate_keys[]# Step 1: check single attributesforainU:ifcompute_closure({a},F,U)U:candidate_keys.append({a})# Skip supersets of found singleton keysalready_coveredset().union(*candidate_keys)ifcandidate_keyselseset()# Step 2: try size-k subsets, k 2forkinrange(2,len(U)1):forXincombinations(U,k):Xset(X)# Prune: if contains any known candidate key → skipifany(candXandcand!Xforcandincandidate_keys):continueifcompute_closure(X,F,U)U:# Check minimality: no proper subset is a superkeyis_minimalTrueforrinrange(1,k):forYincombinations(X,r):Yset(Y)ifcompute_closure(Y,F,U)U:is_minimalFalsebreakifnotis_minimal:breakifis_minimal:candidate_keys.append(X)return[frozenset(k)forkincandidate_keys]# use frozenset for hashability