发帖
雷达卡
LLJD-DPD-3NF算法介绍
鉴于笔者水平有限，这里使用深圳大学杜智华教授的PPT辅助说明；如若介绍文档中存在问题请多多指正！一、算法概述
LLJD-DPD-3NF算法是一种专门用于关系数据库模式分解的技术。从名称上可以看出，该算法旨在实现无损连接分解（LLJD）、依赖保持分解（DPD），并确保分解后的模式达到第三范式（3NF）。
- LLJD (Lossless Join Decomposition): 无损连接分解，确保分解后的模式通过自然连接可以完全恢复原始关系，不丢失任何信息。
- DPD (Dependency Preserving Decomposition): 依赖保持分解，确保分解后的模式能够保持或推导出原始模式中的所有函数依赖。
- 3NF (Third Normal Form): 第三范式，确保关系模式中不存在非主属性对候选键的传递依赖。
二、相关基本概念
写在前面：这里最先补充一些定义;重要概念澄清
候选键（Candidate Key）
候选键是指能够唯一标识关系中元组且不包含多余属性的属性集。一个关系可以有多个候选键。例如，在员工表中，员工ID和身份证号都可能成为候选键。需要注意的是，候选键不同于主键，候选键是“可能成为主键的键”，而主键是从候选键中选定的一个。
主属性（Prime Attribute）
主属性是指构成候选键的属性。例如，如果候选键是{员工ID}，那么“员工ID”是主属性；如果候选键是{员工ID, 部门ID}，那么“员工ID”和“部门ID”都是主属性。
非主属性（Non-Prime Attribute）
非主属性是指不属于任何候选键的属性。例如，在员工表中，“姓名”、“工资”等属性是非主属性。
2.1 第三范式（3NF）
定义： 关系模式R属于第三范式，当且仅当：R属于第二范式（2NF），且不存在非主属性对候选键的传递依赖。
形式化定义： 对于关系模式R中的任意非平凡函数依赖 X → Y：
- X是超键，或者
- Y是主属性（属于某个候选键）。
2.2 无损连接分解（Lossless Join Decomposition）
定义： 将关系模式R分解为R1, R2, …, Rn，如果满足通过自然连接能够完全恢复原始关系，不丢失任何信息。
判定方法： 使用Chase算法或矩阵测试法。
R = R? ? R? ? ... ? R?2.3 依赖保持分解（Dependency Preserving Decomposition）
定义： 分解后的关系模式集合中，所有函数依赖都能在某个子模式中体现，或者能够通过子模式中的函数依赖推导出来。
判定方法： 对于函数依赖集F，检查F中的每个函数依赖是否都能在分解后的子模式中保持。
三、算法步骤
步骤1：寻找候选键
方法：
- 找出所有不在任何函数依赖右部出现的属性（所有只在函数依赖左部出现(L类)和未在任何函数依赖中出现(N类)的属性，这些属性一定包含在候选键中）。
- 计算这些属性的闭包。
- 如果闭包包含所有属性，则找到候选键；否则，逐步添加属性，直到闭包包含所有属性。
例如下图所示：
步骤2：计算函数依赖集的最小覆盖（Minimal Cover）
目的： 简化函数依赖集，去除冗余依赖。
子步骤：
- 右部单一化： 将形如 X → YZ 的依赖分解为 X → Y 和 X → Z。
- 去除左部冗余属性： 对于 X → Y，检查X的每个属性A是否冗余。如果 (X - {A})+ 包含Y，则A是冗余的，可以去除。
- 去除冗余依赖： 对于F中的每个依赖 f: X → Y，计算 F’ = F - {f} 的闭包 F’+。如果 Y ∈ X+ (在F’下)，则f是冗余的，可以去除。
示例：
原始FD集：{AB → C, A → B, B → C}
最小覆盖：{A → B, B → C}步骤3：3NF分解
算法：
输入：关系模式R，函数依赖集F的最小覆盖Fc
输出：满足3NF的分解ρ = {R?, R?, ..., R?}
1. 初始化：ρ = ?
2. 对于Fc中的每个函数依赖 X → Y：
如果X ∪ Y 不在ρ的任何模式中：
创建新关系模式 R? = X ∪ Y
将R?加入ρ
3. 如果ρ中没有任何模式包含R的候选键：
创建新关系模式 R? = 候选键
将R?加入ρ
4. 去除冗余模式：
如果某个模式R?的属性集被另一个模式R?完全包含：
从ρ中删除R?
5. 返回ρ步骤4：验证无损连接性
方法： 使用Chase算法或矩阵测试法验证分解是否无损。
矩阵测试法：
- 构造初始矩阵：行为分解后的关系模式，列为所有属性。
- 对于每个关系模式Ri，在对应行中，属于Ri的属性标记为ai，否则标记为bij。
- 对于每个函数依赖 X → Y，如果某行在X列上全为a，则将Y列统一为a。
- 如果最终矩阵中有一行全为a，则分解是无损的。
步骤5：验证依赖保持性
方法：
- 对于F中的每个函数依赖 X → Y，检查是否存在某个分解后的关系模式Ri，使得 X ∪ Y Ri。
- 如果所有依赖都能在某个子模式中找到，则依赖保持。
- 如果某些依赖不在单个子模式中，需要验证能否通过子模式的依赖推导出来。
四、算法示例
示例1：基本分解
给定：
- 关系模式：R(A, B, C, D, E)
- 函数依赖集：F = {AB → C, C → D, D → E}
步骤1：计算最小覆盖
F已经是右部单一化。
检查左部冗余：AB → C，A+ = A，B+ = B，都不包含C，无冗余。
检查冗余依赖：无冗余。
最小覆盖： Fc = {AB → C, C → D, D → E}
步骤2：寻找候选键
不在右部出现的属性：A, B
(AB)+ = ABCDE（包含所有属性）
候选键： AB
步骤3：3NF分解
对于 AB → C：创建 R1(A, B, C)
对于 C → D：创建 R2(C, D)
对于 D → E：创建 R3(D, E)
候选键AB在R1中，无需额外添加。
分解结果： ρ = {R1(A, B, C), R2(C, D), R3(D, E)}
步骤4：验证无损连接
使用矩阵测试法验证分解的无损性
通过矩阵测试法，可以验证该分解是否为无损分解。
步骤5：验证依赖保持
确保以下函数依赖在R中得以保持：
- AB → C
- C → D
- D → E
这些依赖在分解后的模式中应继续保持。
五、算法特点
优点
- 保证3NF： 分解后的所有关系模式均符合第三范式。
- 无损连接： 通过自然连接，可以完整地恢复原始关系。
- 依赖保持： 所有函数依赖在分解后的模式中仍然有效。
- 算法完备： 对于任意关系模式，总能找到符合条件的分解。
局限性
- 可能不是BCNF： 3NF分解可能不符合更严格的BCNF（Boyce-Codd范式）。
- 可能产生冗余： 尽管满足3NF，但仍可能存在数据冗余。
- 分解可能过多： 复杂的函数依赖集可能导致较多的子模式生成。
六、与其他范式的关系
范式层次结构如下图所示：
1NF ? 2NF ? 3NF ? BCNF ? 4NF ? 5NF3NF vs BCNF
3NF： 允许主属性对非主属性的传递依赖。
BCNF： 更严格，要求所有函数依赖的左部必须是超键。
LLJD-DPD-3NF算法
该算法确保3NF和依赖保持，但不保证达到BCNF。
BCNF分解
BCNF分解可能无法保持所有依赖关系。
七、算法复杂度
- 最小覆盖计算： O(n)，其中n为函数依赖的数量。
- 候选键计算： O(m·n)，其中m为属性数量。
- 分解过程： O(n)。
- 验证过程： O(n·m)。
- 总体复杂度： O(n + m·n + n·m)。
八、实际应用
应用场景
- 数据库设计： 规范化数据库模式。
- 模式优化： 减少数据冗余，提高数据一致性。
- 数据库重构： 将非规范化模式转换为规范化模式。
注意事项
- 分解后需维护外键约束。
- 查询可能需要多表连接，可能影响性能。
- 需在规范化和性能之间找到平衡。
九、复习要点总结
核心概念
- 第三范式（3NF）的定义和判定。
- 无损连接分解的判定方法。
- 依赖保持分解的判定方法。
算法流程
- 计算最小覆盖。
- 寻找候选键。
- 执行3NF分解。
- 验证无损连接性。
- 验证依赖保持性。
关键技巧
- 掌握Chase算法和矩阵测试法。
- 理解函数依赖闭包的计算。
- 熟练运用属性闭包寻找候选键。
十、练习题建议
- 给定关系模式和函数依赖集，执行完整的LLJD-DPD-3NF分解。
- 验证给定分解是否满足无损连接和依赖保持。
- 比较3NF分解和BCNF分解的差异。
- 分析分解对查询性能的影响。
参考资料
- 《数据库系统概念》
- 《数据库系统原理》
- 数据库课程（华姐的）PPT和教材
京公网安备 11010802022788号
