函数依赖

1. 良构关系模式

考虑教师-系别关系模式：in_dept(teacher_id, salary, dept_name, budget)

• 实际应用中，只要知道了teacher_id就可以知道salary，而不关注其他属性的值
• 实际应用中，只要知道了dept_name就可以知道budget，而不关注其他属性的值
• 实际应用中，可以添加一个暂时没有系的老师，或者一个暂时没有老师的系

分解：将关系模式分解为多个子关系模式

• 有损分解（lossy）：通过子关系的自然连接无法完全恢复原始关系模式
• 无损分解（lossless）：通过子关系的自然连接能够完全恢复原始关系模式

冗余（redundancy）：冗余不等价于重复数据，而是在数据量变多的同时，信息量没有变多

范式（Normal Form,NF）：规范的关系模式，是设计关系模式的追求目标，范式越高阶，冗余度就越低，设计越好，并且高阶范式一定满足低阶范式

规范化（normalization）：通过无损分解关系模式来满足一定范式，从而减少数据冗余、提高数据一致性，并确保数据库结构的合理性

2. 函数依赖

定义：给定一个关系模式R，其中X和Y是R的属性子集，对于R的任意两个元组t1,t2，如果t1和t2在属性集X的值相同，那么t1和t2在属性集Y的值也相同，则称Y函数依赖于X，记作$X \rightarrow Y$

• 完全依赖：X没有任何真子集Z也满足Z->Y
• 部分依赖：X存在一个真子集Z也满足Z->Y
• 直接依赖：不存在Z使得X->Z->Y
• 传递依赖：存在Z使得X->Z->Y
• 多值依赖：X->Y且X->Z，但是Y与Z之间不存在依赖关系

3. 范式

概念回顾：

• 超码：唯一标识元组的属性集
• 候选码：唯一标识元组的最小属性集
• 主码：由用户选择的一个候选码
• 外码：引用另一个关系的主码
• 主属性：出现在任一候选码的属性
• 非主属性：没有出现在任一候选码的属性

3.1 第一范式（1NF）

定义：关系模式中的每个属性都是原子值，不可再分

意义：确保每个属性都是最小的数据单元

3.2 第二范式（2NF）

定义：所有非主属性必须完全函数依赖于主码

意义：消除部分依赖

假设存在关系

学生	课程	教材	老师	教室
达斯	数据库	数据库系统概念	小迪	101

候选码是(学生,课程)，但是存在部分依赖课程->教材，因此该关系模式不满足第二范式，存在以下问题：

• 插入：如果某门课程新增一本教材，需要为每个选修该课程的学生插入一条记录，导致空间开销大
• 删除：如果某门课程结课，删除所有选修该课程的记录时，课程和教材的映射信息也会丢失
• 更新：如果某门课程的教材名称需要修改，必须更新所有选修该课程的记录，导致时间开销大且容易出错

3.3 第三范式（3NF）

定义：所有非主属性必须直接函数依赖于主码

意义：消除传递依赖

假设存在关系

学生	课程	老师	职位
达斯	数据库	小帅	系主任

候选码是(学生，课程)，但是存在传递依赖(学生，课程)->老师->职位，因此该关系模式不满足第三范式，存在以下问题：

• 插入：如果新老师尚未教授任何课程，则无法插入该老师的职位信息
• 删除：如果某个老师只教授一门课程，当该课程结课后删除对应记录，则该老师的职位信息也会丢失
• 更新：如果老师的职位发生变化，需要更新所有包含该老师的元组，导致时间开销大且容易出错

3.4 巴斯-科德范式（BCNF）

定义：所有非平凡函数依赖的左部必须是超码

意义：消除了某些异常情况

假设有如下关系（仓库ID，物品ID，管理员ID，物品数量），其中有条件：一个管理员只负责一个仓库，一个仓库只有一个管理员，一个仓库可以有多个物品，一个物品可以位于多个仓库

易得候选码有（仓库ID，物品ID）和（管理员ID，物品ID），也就是说非主属性只有物品数量，同时物品数量完全依赖且直接依赖于候选码，所以该模式满足3NF，但是由于存在仓库ID->管理员ID，管理员ID->仓库ID，所以该模式不满足BCNF，存在以下问题

• 插入：无法做到插入一个新仓库但不分配管理员，或者插入一个新管理员但不分配仓库
• 删除：清空仓库的物品，则会删除仓库ID和管理员ID
• 更新：如果要更新管理员，需要对全部元组进行更新，造成相当大的时间开销

3.5 第四范式（4NF）

定义：所有非平凡多值依赖的左部必须是超码

意义：消除了多对多关系

假设存在如下表：对于每个 StudentID，可以有多个 Course 和多个 Hobby，意味着一个学生可以选修多门课程，一个学生也可以有多个爱好，并且Course和Hobby显然没有任何关系，所以我们说 StudentID 多值依赖于 Course 和 Hobby

StudentID	Course	Hobby
1	Math	basketball
1	Science	football
1	English	music
2	Math	music
2	History	basketball

4. 函数依赖理论

4.1 阿姆斯特朗公理

三个公理：

• 自反律：如果Y是X的子集，那么X->Y成立
• 增补律：如果X->Y，那么对于任意属性集Z，XZ->YZ成立
• 传递律：如果X->Y和Y->Z都成立，那么X->Z成立

三个引理：

• 合并律：如果X->Y成立且X->Z成立，则X->YZ成立
• 分解律：如果X->YZ成立，则X->Y成立且X->Z成立
• 伪传递律：如果X->Y成立且ZY->W成立，这XZ->W成立

4.2 函数依赖集的闭包

给定一组函数依赖集F，F的闭包F+是从F出发，通过Armstrong公理推导出的所有函数依赖的集合

令F+ = F
应用自反律生成所有的平凡依赖
repeat
  for each f in F+
    在f上应用增补律，将结果加入F+中
  for each f1,f2 in F+
    if f1和f2可以应用传递律
      将结果加入F+中
until F+不再变化

4.3 属性集的闭包

给定一个属性集X和一组函数依赖F，属性集X的闭包X+是指从X出发，通过F推导出的所有属性的集合

X+ = X
repeat
  for each f：A->B in F
    if A是X+的子集
      将B加入X+中
until X+不再变化

超码的闭包是整个属性集

4.4 正则覆盖

正则覆盖：能保持与原函数依赖集F相同闭包的最小函数依赖集Fc

无关属性：对于函数依赖集合F中的某个函数依赖$f: X \rightarrow Y$，如果删除X或Y中的某个属性A，函数依赖集F的闭包F+保持不变，则称A是无关属性

F = {AB->C,A->D,D->C}，由A->D->C得到A->C，因此在AB->C中B是无关属性

步骤

1. 将函数依赖右边拆分为单个属性（消除右边的无关属性）
2. 去除函数依赖左边的无关属性
3. 去除重复的函数依赖
4. 去除冗余的函数依赖（即某个函数依赖能被其他函数依赖推导出来）

考虑F = {A->BC,B->C,A->B,AB->C}

1. A->BC可以变为A->B,A->C：{A->C,A->B,B->C,A->B,AB->C}
2. 因为存在A->C，所以AB->C中的B是无关的：{A->C,A->B,B->C,A->B,A->C}
3. 去除重复的函数依赖：{A->C,A->B,B->C}
4. 因为A->C能够从A->B,B->C中推出：{A->B,B->C}

4.5 保持依赖

保持依赖：将关系模式$R$分解为多个子模式$R_1,R_2,\ldots,R_n$后，原有的函数依赖集$F$能够被分解后的子模式推导出来

方法一：闭包测试

1. 计算原函数依赖集 F 的闭包 F+
2. 计算 F 对每个子关系模式 Ri 的限定 Fi（是 F+ 中只包含 Ri 的函数依赖）
3. 合并所有 Fi 得到 F’
4. 计算 F’ 的闭包 F’+
5. 判断 F’+ 是否等于 F+

方法二：函数依赖测试

1. 遍历 F 中的每个函数依赖 X->Y
2. 检查 X->Y 是否在某个子关系模式 Ri 中被保持
   1. 若$X \subseteq R_i$且$Y \subseteq R_i$，则 X->Y 在Ri 中被保持
   2. 若 X 关于限定 Fi 的闭包 X+ 包含 Y，则 X->Y 在 Ri 中被保持
3. 判断是否所有函数依赖都被保持

5. 分解

5.1 3NF分解

1. 求出 F 的正则覆盖 Fc
2. 对于 Fc 中所有的函数依赖 fi: X->Y，令 Ri = XY，添加到R’中
3. 检查候选码是否被包含
   1. 如果存在一个 Ri 包含候选码，则直接进入下一步
   2. 如果所有 Ri 都不包含候选码，则添加任意一个候选码到 R’ 中
4. 对于 R’ 中的所有 Ri，如果 Ri 被另一个子关系包含，则删除 Ri

关系模式R(A,B,C,D,E,G)，主码是CE，函数依赖集F={B->G,CE->B,C->A,CE->G,B->D,C->D}

1. 正则覆盖为 Fc = {B->DG,CE->B,C->AD}
2. 根据正则覆盖可以得到：R1 = (B,D,G), R2 = (C,E,B), R3 = (C,A,D)
3. 主码是CE，其中(C,E,B)包含CE
4. R1,R2,R3之间没有包含关系

综上，R’ = {(B,D,G),(C,E,B),(C,A,D)}

5.2 BCNF分解

1. 令 R’ = {R}
2. 如果 R’ 中的 Ri 保持的函数依赖中存在 X->Y 不满足BCNF，将 Ri 用 R1 = XY，R2 = Ri - Y 来替换
3. 重复第2步，直到全部子模式都满足BCNF

关系模式R(A,B,C,D,E,G)，主码是AD，函数依赖集F={A->B,B->C,AD->G,D->E}

1. R的主码为AD，A->B不满足BCNF，令R1 = AB，R2 = ACDEG
2. R2的主码为AD，其中D->E不满足BCNF，令R3 = DE，R4 = ACDG
3. R4的主码为AD，其中AD->G满足BCNF

综上，，R’ = {(A,B),(D,E),(A,C,D,G)}

5.3 4NF分解

1. 令R’ = {R}
2. 如果 R’ 中的 Ri 保持的函数依赖中存在 X->->Y 不满足4NF，将 Ri 用 R1 = XY，R2 = Ri - Y 来替换
3. 重复第2步，直到全部子模式都满足4NF

关系模式R(A,B,C,D)，主码是AC，F={A->->B,A->C,C->->D}

1. R的主码为AC，A->->B违反4NF，令R1=(A,B)，R2=(A,C,D)
2. R2的主码为AC，C->->D违反4NF，令R3=(C,D)，R4=(A,C)

综上，R分解为{(A,B),(A,C),(C,D)}