关系模式的规范化

复习定位

规范化是将一个冗余度高、容易产生更新异常的关系模式分解为多个较小模式的过程——以减少数据冗余和避免更新/插入/删除异常。每个范式级别消除特定类型的函数依赖——1NF→2NF→3NF→BCNF逐级递增——4NF处理多值依赖。考试中给定一个关系模式及函数依赖集——要判断它属于第几范式——并分解到3NF或BCNF。

函数依赖

函数依赖(X→Y)表示X的值确定Y的值——是现实世界的语义约束——不是数据快照的巧合。例如——学号→姓名(每个学号唯一确定一个姓名)。

完全函数依赖——X→Y且X的任意真子集不能决定Y——(学号,课程号)→成绩是完会依赖；学号→姓名是(学号,课程号)→姓名的部分依赖。

传递函数依赖——X→Y,Y→Z,Y↛X——则Z传递依赖于X。例如——学号→系号,系号→系主任——系主任传递依赖于学号。

1NF→2NF→3NF→BCNF

1NF——所有列都不可再分——值必须是原子的。

2NF——在1NF基础上——所有非主属性完全依赖于每一个候选码——消除部分依赖。例：选课表(学号,课程号,成绩,姓名)中——姓名只依赖于学号(部分依赖)不符合2NF。分解为(学号,姓名)和(学号,课程号,成绩)。

3NF——在2NF基础上——消除非主属性对码的传递依赖。例：(学号,系号,系主任)中——系主任传递依赖于学号——分解为(学号,系号)和(系号,系主任)。

BCNF——在3NF基础上——对于任何非平凡函数依赖X→Y(不管X是否为候选码)——X必须包含候选码。即——消除主属性之间的依赖。3NF可能允许某些X→Y在X不是超码但对Y是主属性的情况下保持——BCNF不允许任何这样的情况。

Armstrong公理系统

• 自反律——若Y⊆X⊆U——则X→Y。
• 增广律——若X→Y——则XZ→YZ。
• 传递律——若X→Y,Y→Z——则X→Z。

推论——合并规则(X→Y,X→Z→X→YZ)、分解规则(X→YZ→X→Y,X→Z)、伪传递规则(X→Y,YZ→W→XZ→W)。

无损连接与保持依赖

无损连接分解——自然连接分解后的子关系能还原为原关系——没有多余或丢失的信息。检验——对R分解(R1,R2)——如果(R1∩R2)→R1或(R1∩R2)→R2(即在F⁺中)——则分解是无损的。

保持函数依赖——原关系R上的所有函数依赖都能在分解后的某个子关系上直接验证——而不需要连接所有子关系再判断。保持依赖是3NF分解能保证但BCNF不一定保证的性质。

复习检查

1. 2NF消除了什么异常——消除了非主属性对候选码的部分依赖——即那些只用候选码的一部分就能确定的属性的冗余(如姓名在选课表中随每条选课记录重复出现)。

2. BCNF与3NF的区别——BCNF要求所有依赖的决定因素(X)必须是超码——3NF只要求非主属性不传递依赖于码——主属性之间的依赖在3NF中允许——在BCNF中不允许。

3. 函数依赖的决定——Armstrong公理中的传递律定义了如果X→Y、Y→Z则可以推出X→Z——传递依赖就是在此定义基础上非主属性通过另一个非主属性间接由码决定。

4. 无损连接分解的判定条件——如果(R1∩R2)→R1在F+中成立——那么分解(R1,R2)是无损的——检查R1∩R2的属性在F+下能否决定R1的所有属性。

5. 保持函数依赖为什么重要——如果没有保持函数依赖——插入或更新一行后——依赖关系无法在单表级别直接检查——连接所有的子关系来统一检查在工程上复杂且代价高。

函数依赖的详细分类示例

完全函数依赖——X→Y——且X的任意真子集都不能决定Y。

示例——选课表SC(学号,课程号,成绩)——函数依赖{(学号,课程号)→成绩}——仅靠学号或仅靠课程号都不能决定成绩——所以成绩完全依赖于(学号,课程号)——属于完全函数依赖。

部分函数依赖——X→Y——但X的某个真子集Z也满足Z→Y。

示例——如果选课表SC中有学生姓名列(学号,课程号,成绩,姓名)——函数依赖(学号,课程号)→姓名——但学号→姓名也成立。姓名部分依赖于候选码(学号,课程号)——因为候选码的一部分(学号)就能决定姓名。

传递函数依赖——X→Y,Y→Z——且Y↛X——X通过传递决定Z。

示例——关系(学号,系号,系主任)——学号→系号——系号→系主任——系号↛学号——系主任传递依赖于学号。

理解这三类函数依赖是正确判断范式等级的基础。

关系模式规范化的分解算法

将一个关系模式规范化为3NF的算法(保证无损连接且保持依赖)：

1. 求出函数依赖集F的最小覆盖Fmin
2. 对Fmin中的每个函数依赖X→Y——创建子关系R_i(XY)
3. 如果没有任何R_i包含R的任一候选码——再创建一个仅含候选码的关系
4. 删除被其他关系包含的冗余子关系

规范化为BCNF的算法(保证无损连接但不一定保持依赖)：

1. 如果R不是BCNF——找出违反BCNF的X→Y(X不是超码)
2. 将R分解为R1(XY)和R2(R-Y)
3. 对R1和R2递归应用步骤1——直到所有关系都属于BCNF

当BCNF分解不能保持依赖时——通常选择停留在3NF以保证依赖的保持——因为丢失的依赖必须在应用层通过额外的检查来弥补——这增加了应用程序的复杂度且可能产生数据不一致。

多值依赖与4NF

多值依赖(MVD, Multi-Valued Dependency)——当关系R中——对于X的一个确定值——Y有一组独立的值与之对应——且这组值与Z(R-X-Y)无关——则X→→Y。

示例——课程教师教材关系CTM(课程,教师,教材)。一门课可以有多个教师和多个教材——教师和教材是独立的——课程→→教师、课程→→教材。

4NF要求——如果R存在非平凡多值依赖X→→Y——则X必须包含R的候选码——否则应将R分解为R1(XY)和R2(XZ)——分别消除多值依赖。

规范化范式等级判断综合流程

给定一个关系模式R和函数依赖集F——判断R满足第几范式：

1. 计算所有候选码(码的闭包)
2. 列出非主属性(不属于任何候选码的属性)
3. 检查是否存在非主属性对候选码的部分依赖→若存在——最高1NF
4. 检查是否存在非主属性对候选码的传递依赖→若存在——最高2NF
5. 检查是否存在主属性之间的依赖(即非平凡函数依赖X→Y中X不是超码)→若存在——最高3NF——否则BCNF

这一流程按顺序检查——每一步不满足则确定了R的最高范式级别。

候选码的求解——属性闭包算法

给定R和F——求R的所有候选码：

1. 将R的属性分为四类:
   L类: 只出现在函数依赖的左边的属性
   R类: 只出现在函数依赖的右边的属性
   LR类: 既出现在左边又出现在右边的属性
   N类: 不出现在任何函数依赖中的属性
2. L类和N类属性一定属于每一个候选码
3. 计算L+N的闭包——如果闭包=U——则L+N是唯一候选码
4. 否则——尝试在L+N的基础上逐个添加LR类属性——每次添加后求闭包——如果=U则该属性集是候选码——继续寻找其他候选码

这一算法可以准确找出关系模式的所有候选码——是后续范式判断和模式分解的关键步骤。

复习检查（续）

6. 部分依赖与传递依赖的根本区别——部分依赖是候选码的某些子集决定了非主属性——传递依赖是非主属性通过另一个非主属性间接依赖于候选码。

7. 3NF分解的算法步骤——求函数依赖的最小覆盖Fmin——对Fmin每个依赖创建子关系——如果没有任何子关系包含候选码则添加候选码关系——删除冗余子关系。

8. BCNF分解可能丢失函数依赖的原因——BCNF要求X→Y中X必须是超码——当分解使得某个依赖无法在单一子关系中验证时——该依赖丢失——必须在应用层弥补。

9. 多值依赖X→→Y与函数依赖X→Y的区别——多值依赖中X确定Y的一组值(而非一个值)——这组值与Z独立——反映的是两个独立的多对多关系。

10. 候选码求解的LRN分类法——L类(只出现在左边的属性)——N类(两侧都不出现)——这两类必然属于候选码——再尝试添加LR类属性求闭包。

范式等级判断的完整示例

判断关系R(ABCDE)和函数依赖F={A→B, BC→E, ED→A}满足第几范式：

1. 求候选码:
   - L类属性: C,D(只出现在左边)
   - N类属性: 无(所有属性都在依赖中出现)
   - LR类属性: A,B,E(左右都出现)
   - C,D ++ → (CD)⁺= CD——不等于U——需要添加LR类属性
   - (CDA)⁺= ABCDE=U——(A,C,D)是候选码
   - (CDB)⁺= CDBE——不等于U
   - (CDE)⁺= CDEAB=U——(C,D,E)也是候选码
   候选码: (A,C,D)和(C,D,E)
   
2. 非主属性: B(不在任何候选码中)
   - 检查A→B——主属性A决定非主属性B——但A是主属性吗——A在候选码(ACD)中——所以A是候选码的一部分——这属于主属性决定非主属性——B完全依赖于A——不存在部分依赖——所以R满足2NF
   - 检查是否存在传递依赖——没有非主属性通过另一个非主属性决定链——满足3NF
   - 检查BCNF——A→B——A不是超码(A单独不能确定所有属性)——所以R不满足BCNF——R的最高范式是3NF

反规范化(Denormalization)的实际工程决策

在数据库设计时——如果严格遵循范式化——可能导致太多表(JION太多)——严重影响查询性能。在性能关键场景下——工程师可能决定反规范化：在表中加入冗余列以减少JOIN次数。

场景: 订单表需要频繁查询客户姓名和地址

规范化方案:
  订单表(order_id, customer_id, order_date, total)
  客户表(customer_id, name, address, phone)
  每次查询需要ORDER JOIN CUSTOMER —— 大量JOIN消耗性能

反规范化方案:
  订单表(order_id, customer_id, customer_name, customer_address, order_date, total)
  查询不需要JOIN —— 直接读取订单表即可获得客户姓名和地址
  代价: 客户修改姓名/地址时必须更新所有关联的订单记录——需要应用层或触发器保证冗余数据的一致性

反规范化应该在性能瓶颈明确由过多JOIN导致时采用——而不是在设计之初就这样做——且需要确保冗余数据的更新机制。

复习检查（续二）