模式分解
一、模式分解的基本概念
1. 模式分解的定义
关系模式$R(U)$的分解是指用一组子集$\rho = {R_1(U_1), R_2(U_2), \dots, R_k(U_k)}$代替原模式
满足条件：$U = U_1 \cup U_2 \cup \dots \cup U_k且U_i \not\subset U_j(i \neq j)$
2. 投影连接运算
- 对于关系$r$，其向$(\rho)$的投影连接记为：
$m_\rho(r) = \pi_{R_1}(r) \bowtie \pi_{R_2}(r) \bowtie \dots \bowtie \pi_{R_k}(r) = \bowtie_{i=1}^k \pi_{R_i}(r)$
3. 分解的核心关注点
无损连接性：分解后的数据内容与原模式等价
保持依赖性：分解后的数据依赖与原模式等价
二、模式分解存在的关键问题
数据冗余问题：分解后可能产生多余数据
依赖丢失问题：函数依赖可能无法在分解后保留
异常操作问题：可能导致插入、删除、更新异常
三、无损连接分解及其检验
1. 无损连接分解的定义
- 对于关系模式$R(U, F)$，若对任意满足$F$的关系$r$，都有$r = m_\rho(r)$，则称$\rho$为无损连接分解
2. 无损连接性检验算法
算法步骤：
构造k行n列的表（k为分解后的模式数，n为属性数）
若属性$A_j$属于$R_i$，则在表中第i行第j列填$a_j$，否则填$b_{ij}$
对每个函数依赖$X \to Y$，找到X属性列符号全相同的行，将Y属性列统一为相同符号（若有$a_j$则统一为$a_j$，否则统一为$b_{ij}$）
若某行变为全a，则分解为无损连接分解
应用示例：
关系模式R(ABCDE)，$F = {A \to C, B \to C, C \to D, DE \to C, CE \to A}$
分解$\rho = {R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE)}$
通过检验算法确认该分解为无损连接分解
四、保持依赖分解及其检验
1. 保持依赖分解的定义
- 若$\cup_{i=1}^k \pi_{R_i}(F)$逻辑蕴涵$F$的所有依赖，则称分解$\rho$保持依赖
2. 保持依赖性检验算法
算法步骤：
计算$G = \cup_{i=1}^k \pi_{R_i}(F)$
对每个$X \to Y \in F$，计算$X$在$G$中的属性闭包$X_G^+$：
- 初始化$Z = X$
- 循环执行$Z = Z \cup ((Z \cap R_i)_G^+ \cap R_i)$，直到$Z$不再变化
- 若$Z$包含$Y$，则$G$蕴涵$X \to Y$
- 若$G$蕴涵$F$的所有依赖，则分解保持依赖
应用示例：
分解$\rho = {R1(AC), R2(BC), R3(CDE)}$，$F = {A \to C, B \to C, C \to D, DE \to C}$
检验发现$A \to C$和$DE \to C$被保持，但$CE \to A$未被保持
五、关系模式分解算法
1. 分解为 BCNF 的无损连接算法
初始$\rho = {R}$
若存在模式$s \notin BCNF$，找到非超键依赖$X \to A$，用${XA, s - A}$替代$s$
重复步骤 2 直至所有模式均为 BCNF
2. 分解为 3NF 的保持依赖算法
去除不在$F$中的属性并单独成模式
对每个$X \to A \in F$，以$XA$组成模式，合并同类$X \to A_1A_2\dots A_m$为$XA_1A_2\dots A_m$
六、数据库设计要点
规范化目标：避免数据冗余和异常，遵循 1NF 至 5NF 范式
设计折中：
- 规范化可减少冗余，但增加连接查询开销
- 需平衡范式要求与查询效率
- 完整设计流程：包含概念设计、逻辑设计和物理设计（存储方式、索引优化等）
举例
一、无损连接分解示例：学生信息表分解
（一）原关系模式
学生(学号, 姓名, 课程, 成绩)（二）数据示例
| 学号 | 姓名 | 课程 | 成绩 |
|---|---|---|---|
| 1001 | 张三 | 数学 | 90 |
| 1001 | 张三 | 英语 | 85 |
| 1002 | 李四 | 数学 | 80 |
（三）分解方式
- 分解为两个模式：
学生基本信息(学号, 姓名)学生成绩(学号, 课程, 成绩)
（四）分解后数据
学生基本信息
学号 姓名 1001 张三 1002 李四 学生成绩
学号 课程 成绩 1001 数学 90 1001 英语 85 1002 数学 80
（五）无损连接验证
通过自然连接 学生基本信息 ⋈ 学生成绩，结果与原表完全一致，说明分解为无损连接分解。
二、保持依赖分解示例：员工部门表分解
（一）原关系模式
员工(工号, 姓名, 部门, 部门负责人)（二）函数依赖
工号 → 姓名, 部门部门 → 部门负责人
（三）数据示例
| 工号 | 姓名 | 部门 | 部门负责人 |
|---|---|---|---|
| E001 | 张三 | 技术部 | 李四 |
| E002 | 王五 | 市场部 | 赵六 |
（四）正确分解方式（保持依赖）
- 分解为：
员工信息(工号, 姓名, 部门)部门信息(部门, 部门负责人)
（五）投影依赖集
员工信息：工号→姓名, 工号→部门部门信息：部门→部门负责人- 并集 工号姓名工号部门部门部门负责人，覆盖原依赖，分解保持依赖。
三、非保持依赖分解反例
（一）错误分解方式
- 分解为：
工号姓名(工号, 姓名)工号部门负责人(工号, 部门, 部门负责人)
（二）依赖丢失分析
| 分解模式 | 包含属性 | 是否保留部门→部门负责人 |
|---|---|---|
工号姓名 | 工号、姓名 | 不包含部门和部门负责人，依赖丢失 |
工号部门负责人 | 工号、部门、部门负责人 | 依赖保留 |
（三）结论
原依赖部门→部门负责人未被工号姓名保留，导致分解后的依赖并集无法覆盖原依赖，因此该分解不保持依赖。
| 类型 | 核心目标 | 示例场景 | 验证关键 |
|---|---|---|---|
| 无损连接分解 | 分解后数据可通过连接还原 | 学生表分解后连接无数据丢失 | 连接结果与原表一致 |
| 保持依赖分解 | 分解后函数依赖不丢失 | 部门表分解后依赖仍成立 | 投影依赖并集覆盖原依赖 |