DBPA · 6.2

依赖推理与模式分解

用依赖保持与无损连接检验模式分解

VER. 2608.2 Built with impress.js

学习目标

Armstrong 公理、属性闭包和分解准则把函数依赖判断变成可计算的设计工具

01用 Armstrong 公理推导函数依赖
02求属性闭包并判断候选码
03用闭包检验依赖集等价并构造最小覆盖
04判断分解是否保持函数依赖
05区分无损连接与依赖保持
06描述 3NF、BCNF 与 4NF 分解的保证与代价

2/17

LEARNING OBJECTIVES

三条公理把依赖语义变成推理规则

传递律可以推出 A→B、B→C 所蕴含的 A→C

公理	形式	直观含义
自反律	`Y ⊆ X` 则 `X → Y`	已有属性决定其子集
增广律	`X → Y` 则 `XZ → YZ`	两端共同增加上下文
传递律	`X → Y` 且 `Y → Z`，则 `X → Z`	依赖链可以传递

例：`A→B、B→C　⇒　A→C（传递律）派生规则：合并 X→Y、X→Z⇒X→YZ；分解 X→YZ⇒X→Y；伪传递 X→Y、WY→Z⇒XW→Z`

Takeaway

公理系统既有效又完备，推出的依赖恰好对应逻辑蕴涵

3/17

ARMSTRONG AXIOMS

属性闭包回答 X 能推出哪些属性

反复应用左部已包含在当前集合中的依赖，直到集合不再变化；先判断超码，再检查真子集

TEXT

01
02
03
04
05
06
07U = {A, B, C, D, E}
F = {AB→C, B→D, C→E}
A+ = A
B+ = BD
AB+：
  AB → ABCD   （AB→C、B→D）
  ABCD → ABCDE （C→E）

若 Y ⊆ X_F+→F 能推出 X→Y 若 X_F+=U→X 是超码本例：`A+≠U、B+≠U`→AB 的真子集都不是超码→AB 是候选码

Takeaway

AB+ = U 只先说明 AB 是超码；还要检查真子集，才能判定候选码

4/17

ATTRIBUTE CLOSURE

最小依赖集保留语义，减少推理负担

最小覆盖不改变规则语义，只保留不可由其他规则替代的部分

拆分右部

把每条依赖的右部拆成一个属性

删除冗余依赖

删除后依赖集闭包不改变的规则

简化左部

删除左部中不影响依赖语义的属性

覆盖：`F^+=G^+。微例：A→BC 先拆成 A→B、A→C；若 A→C` 可由其他依赖推出，就删除它

Takeaway

不同处理顺序可能得到多个等价的最小依赖集

5/17

MINIMAL COVER

分解把一个关系模式拆成多个局部模式

属性并集覆盖原模式只是起点，还要检查局部约束与连接后的可恢复性

ρ={R1(U1,F1), ..., Rk(Uk,Fk)} U=U1 ∪ ... ∪ Uk Fi={X→Y | X→Y∈F+且 XY⊆Ui}

Takeaway

Fi 是 F+ 在 Ui 上的投影，不是只筛选原始依赖；分解后的约束和可恢复性都要单独验证

6/17

DECOMPOSITION

保持函数依赖意味着约束仍能局部检查

分解后的局部依赖闭包应与原依赖闭包等价

F+＝　(F1 ∪ F2 ∪ … ∪ Fk)+

检查对象	需要回答	设计价值
原依赖集	哪些规则必须保持	业务语义
局部依赖集	哪些规则能在子表检查	约束维护
闭包比较	两者是否等价	判断保持依赖

反例：R(Sno,School,Mname) 分解为 (Sno,School) 与 (Sno,Mname) 后，`School→Mname` 不能由局部依赖保持

7/17

DEPENDENCY PRESERVING

算法 6.2：3NF 合成法优先保证依赖保持

先最小化依赖，再按相同左部组织关系

01求函数依赖的最小覆盖
02按相同决定因素分组
03用每组的 X ∪ {A...} 形成局部关系
04为不出现在依赖中的属性补关系，并删除被包含的关系
05检查属性并集覆盖原模式，得到保持依赖的 3NF 分解

Takeaway

算法 6.2 保证 3NF 与依赖保持；若还要求无损连接，算法 6.4 还需补入包含候选码的关系并进行检验

8/17

3NF SYNTHESIS

无损连接要求投影自然连接能恢复原关系

分解不能制造原来不存在的伪元组；要求对所有满足 F 的合法关系都成立

Takeaway

r → πR1(r)、πR2(r) → πR1(r) ⋈ πR2(r)；二元例 R1(A,B)、R2(B,C) 共享 B。无损时 mρ(r)=πR1(r)⋈...⋈πRk(r)=r；r⊆mρ(r) 总成立，关键是不多出伪元组

9/17

LOSSLESS JOIN

依赖保持与无损连接解决不同问题

同时满足通常更理想，但实际设计仍可能需要权衡

准则	满足时意味着什么	判断视角
依赖保持	原依赖可由局部依赖推出并检查	依赖闭包
无损连接	投影自然连接恢复原关系且无伪元组	投影与自然连接
两者同时	约束可局部检查，数据可无伪恢复	设计取舍

10/17

TWO CRITERIA

两项准则可以分别失效

无损不保证依赖保持，依赖保持也不保证无损

反例	分解	失去哪一项
`R1(学号,姓名)`、`R2(课程号,课程名)`	无公共属性，连接退化为笛卡儿积	保持依赖但有损
`(Sno,School)`、`(Sno,Mname)`	`Sno→School` 可支持无损，但 `School→Mname` 不在局部	无损但不保持依赖

11/17

TWO CRITERIA

追赶表把无损连接判断变成可操作步骤

先把依赖拆成单属性右部；行对应子关系，列对应属性

TEXT

01
02
03
04
05
06
07
08
09
10U={A,B,C,D,E}   F={AB→C, C→D, D→E}
ρ={R1(A,B,C), R2(C,D), R3(D,E)}

初始表：       A    B    C    D     E
R1             a1   a2   a3   b14   b15
R2             b21  b22  a3   a4    b25
R3             b31  b32  b33  a4    a5

C→D：R1 的 D 改为 a4；D→E：R1、R2 的 E 改为 a5
R1             a1   a2   a3   a4    a5

12/17

LOSSLESS TEST

追赶表判断无损连接的四步

反复传播函数依赖，直到出现全 a 行或表格稳定

01子关系已有属性填 a 符号，其余填 b 符号
02若依赖左部符号相同，右部统一传播为同一个符号
03重复扫描直到表不再变化
04出现一行全 a 判无损；稳定后仍没有全 a 行判有损

13/17

LOSSLESS TEST

分解算法优先保证的目标不同

不同算法优先保证的设计准则不同

算法	保证与适用	可能代价
3NF 合成 6.2	3NF、保持函数依赖	不自动保证无损连接
补码关系 6.4	在 6.2 结果上同时获得无损与保持依赖	关系集合可能增加
BCNF 分解 6.5	无损连接、达到 BCNF	不一定保持函数依赖
4NF 分解 6.6	无损处理非平凡多值依赖	不承诺保持所有函数依赖

14/17

NORMAL FORM CHOICES

用闭包和分解准则验证模式设计

依赖推理让模式分解可以根据闭包、依赖保持和无损连接准则验证

推理

Armstrong 公理、属性闭包和最小覆盖用于推导依赖

分解

算法 6.2 和 6.4 通过局部依赖保持约束

无损与选择

无损自然连接不增加伪元组，BCNF 和 4NF 还需要结合设计取舍

Takeaway

设计准则不同，分解结果和范式上限也可能不同

15/17

RECAP

本节知识地图

16/17

KNOWLEDGE MAP

本节问题

01对 F={AB→C,B→D,C→E} 逐步求 AB+，判断 AB 是否为候选码？
02用 Armstrong 公理由 A→B、B→C 推出 A→C 的步骤是什么？
03求 F={A→BC,A→B,B→C} 的一个最小覆盖，并说明删去了什么？
04判断 R(Sno,School,Mname) 分解为 (Sno,School)、(Sno,Mname) 是否保持 School→Mname？
05比较 R1(A,B)、R2(B,C) 在有无 B→C 时是否满足二元无损判据？
06若优先保持依赖、同时要求无损、或必须处理多值依赖，应分别优先考虑哪种算法？

17/17

CHECK YOUR UNDERSTANDING