2023年7月7日发(作者：)

数据库的函数依赖、属性集的闭包、覆盖、模式分解、范式、3NF的分解、BCNF的分解Functional Dependency 函数依赖1. K 是关系模式R 的超码 当且仅当 K ->R2. K 是关系模式R 的候选码 当且仅当K -> R, 并且不存在 a属于 K, a-> R函数依赖集：若⼲个函数依赖组成的集合如果⼀个关系 r 没有违反函数依赖集 F, 那么称关系 r 满⾜函数依赖集 F （ r satisfies F ）如果关系模式 R 的所有关系都满⾜函数依赖集 F, 那么称函数依赖集F 在关系模式 R 上成⽴ （ F holds on R ）Closure of Attribute Sets 属性集的闭包根据⼀个给定的函数依赖集 F，由属性集 a 可推出的所有属性组成的集合，称为 a 的闭包，记为 a+计算属性集的闭包属性集闭包的⽤途:判断⼀个属性集是否超码要判断 a 是不是 R 的超码，只要看 a+ 是不是包含 R判断⼀个函数依赖是否成⽴要判断 a->b 是不是成⽴，只要看b属于a+ 是不是成⽴Canonical Cover 最⼩覆盖/规范覆盖把函数依赖集 F 中多余的函数依赖和多余的属性删除，得到“最⼩的”函数依赖集合，称为 F 的最⼩覆盖或规范覆盖1. 函数依赖集中的某些函数依赖是多余的例如. {A ->B, B -> C, A ->C} 可以简化为等价的函数依赖集合{A ->B, B -> C}2. 函数依赖中的某些属性是多余的例如. {A ->B, B ->C, A ->CD} 可以简化为等价的函数依赖集合{A ->B, B ->C, A -> D}例如. {A ->B, B ->C, AC ->D} 可以简化为等价的函数依赖集合{A -> B, B ->C, A -> D}Decomposition（模式分解）Lossless Decomposition ⽆损分解Closure of a Set of Functional Dependencies函数依赖集的闭包由函数依赖集 F 可推断出的所有函数依赖所组成的集合，叫做 F 的闭包，记为 F+F+ 是 F 的超集Dependency Preservation（保持函数依赖）1. 分解关系模式 R 后, 得到关系模式 R1, R2,…,Rn2. 把 F+ 中只包含 R1 属性的函数依赖⼦集合记为 F13. 把 F+ 中只包含 R2 属性的函数依赖⼦集合记为 F2如此类推4. 把 F+ 中只包含 Rn 属性的函数依赖⼦集合记为 Fn保持函数依赖. 如果F1 并 F2 并 … 并 Fn 和 F 是等价的那么称这个分解是保持函数依赖的（dependency preserving）Normal Forms(范式)范式是关系的集合1NF (First Normal Form，第1范式)如果⼀个关系模式R的所有属性域都是原⼦域，那么R属于第⼀范式以下哪些域是原⼦域？⾷品 = { 可乐，薯条，鸡翅，⾯条，饺⼦，汤，…… }套餐 = { (可乐，薯条，鸡翅)，(⾯条，饺⼦，汤)，……}车票 = { D7727次02车20A号，D7712次08车04A号，…… }车次 = { D7727次，D7712次，…… }车厢 = { 02车，08车，…… }座位 = { 20A号，04A号，…… }答案⾷品，车次，车厢，座位3NF (Third Normal Form)BCNF (Boyce-Codd Normal Form)BCNF定义. 如果 F+ ⾥⾯的所有⾮平凡函数依赖 a->b的 a 都是 R 的超码，那么 R 属于 BCNF实际上，只需要检查 F 的函数依赖，不需要检查 F+ 的全部函数依赖Example. 以下关系模式不属于 BCNF:instr_dept (ID, name, salary, dept_name, building, budget )因为存在⾮平凡函数依赖 dept_name-> building, budget但是 dept_name 不是超码3NF vs BCNF1. Redundancy 冗余BCNF 能消除⽤函数依赖发现的冗余3NF 还有⼀些冗余2. Dependency-preserving decomposition 保持函数依赖分解所有关系模式都有保持函数依赖的 3NF 分解有⼀些关系模式，它们的 BCNF 分解不能保持函数依赖Decomposition Algorithms(分解算法)3NF 分解算法以下 3NF 分解算法是保持函数依赖的：1. 先求出 F 的最⼩覆盖 Fc2. 为 Fc 的每个函数依赖 a->b ⽣成⼀个新的关系模式 a U b3. 如果⽣成的每⼀个关系模式都不包含 R 的候选码， 就选择 R 的任意⼀个候选码 A，⽣成⼀个新的关系模式 A4. 检查⽣成的关系模式，如果有 R1 属于 R2，就把 R1 删掉分解以下关系模式:cust_banker_branch = (customer_id, employee_id, branch_name, type )函数依赖集:customer_id, employee_id -> branch_name, typeemployee_id -> branch_namecustomer_id, branch_name -> employee_id⾸先计算最⼩覆盖 Fc1. 第⼀个函数依赖中的 branch_name 是多余的FC = { customer_id, employee_id -> type employee_id -> branch_name customer_id, branch_name -> employee_id }为每个函数依赖⽣成⼀个关系模式:(customer_id, employee_id, type )(employee_id, branch_name)(customer_id, branch_name, employee_id)(customer_id, employee_id, type ) 已经包含了原关系模式的候选码, 所以不⽤为候选码⽣成新的关系模式第⼆个关系模式是第三个关系模式的⼦集，可以删掉最终得到的分解:(customer_id, employee_id, type)(customer_id, branch_name, employee_id)BCNF 分解算法假设关系模式 R 有⼀个⾮平凡函数依赖 a->b （且a并b = 空 ），a不是超码我们可以把 R 分解为以下两个关系模式a U b 和 R – b如果分解后的两个关系模式还不是BCNF, 就继续分解下去注意：要判断分解后得到的关系模式 Ri 是否属于 BCNF时, 要⽤函数依赖集Fi ，⽽不是⽤函数依赖集 F例如：R = (A, B, C, D, E)F = { A-> B, BC-> D}考虑 A -> B，A 不是超码，所以把 R 分解为R1 = (A,B)R2 = (A,C,D,E)F 的函数依赖，都不是仅包含 (A,C,D,E)所以不能根据 F 来判断 R2 是否属于BCNF实际上, F+ 中的 AC-> D 使得 R2 不属于 BCNF所以还要继续对 R2 进⾏分解