凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

关系数据理论详解（模式分解与四大范式）

作者：凡人多烦事01 | 2024-06-05 21:59:45

踩

关系数据理论

1. 问题的提出

关系数据库逻辑设计

针对具体问题，如何构造一个适合于它的数据模式
数据库逻辑设计的工具──关系数据库的规范化理论

1.1 概念回顾

关系
关系模式
关系数据库
关系数据库的模式

1.2 关系模式的形式化定义

关系模式由五部分组成，即它是一个五元组：
R(U, D, DOM, F)
R：关系名
U：组成该关系的属性名集合
D：属性组U中属性所来自的域
DOM：属性向域的映象集合
F：属性间数据的依赖关系集合

1.3 什么是数据依赖

1.3.1 完整性约束的表现形式

限定属性取值范围：例如学生成绩必须在0-100之间
定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键

1.3.2 数据依赖

一个关系内部属性与属性之间的约束关系
现实世界属性间相互联系的抽象
数据内在的性质
语义的体现

1.3.3 数据依赖的类型

函数依赖（Functional Dependency，简记为FD）
多值依赖（Multivalued Dependency，简记为MVD）
其他

1.4 关系模式的简化定义

关系模式R（U, D, DOM, F）
简化为一个三元组：R（U, F）
当且仅当U上的一个关系r满足F时，r称为关系模式 R（U, F）的一个关系

1.5 数据依赖对关系模式影响

1.5.1 [例1]

建立一个描述学校教务的数据库：
学生的学号（Sno）、所在系（Sdept）
系主任姓名（Mname）、课程名（Cname）
成绩（Grade）

单一的关系模式： Student <U、F>
U ＝｛ Sno, Sdept, Mname, Cname, Grade ｝
属性组U上的一组函数依赖F：
F ＝｛ Sno → Sdept, Sdept → Mname, (Sno, Cname) → Grade ｝

1.5.2 关系模式Student<U, F>中存在的问题

数据冗余太大
更新异常（Update Anomalies）
插入异常（Insertion Anomalies）
删除异常（Deletion Anomalies）

结论：Student关系模式不是一个好的模式。
“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少
原因：由存在于模式中的某些数据依赖引起的
解决方法：通过分解关系模式来消除其中不合适的数据依赖

1.5.3 分解关系模式

把这个单一模式分成3个关系模式：
S（Sno，Sdept，Sno → Sdept）;
SC（Sno，Cno，Grade，（Sno，Cno） → Grade）;
DEPT（Sdept，Mname，Sdept→ Mname）

2. 规范化

规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。

2.1 函数依赖

2.1.1 函数依赖

定义：设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称 “X函数确定Y” 或 “Y函数依赖于X”，记作X→Y。

所有关系实例均要满足
语义范畴的概念
数据库设计者可以对现实世界作强制的规定

2.1.2 平凡函数依赖与非平凡函数依赖

定义：在关系模式R(U)中，对于U的子集X和Y，
如果X→Y，但Y $\nsubseteq$ X，则称X→Y是非平凡的函数依赖
若X→Y，但Y ⊆ X, 则称X→Y是平凡的函数依赖
例：在关系SC(Sno, Cno, Grade)中，
非平凡函数依赖： (Sno, Cno) → Grade
平凡函数依赖： (Sno, Cno) → Sno
(Sno, Cno) → Cno

若X→Y，则X称为这个函数依赖的决定属性组，也称为决定因素（Determinant）。
若X→Y，Y→X，则记作X←→Y。
若Y不函数依赖于X，则记作X→Y。

2.1.3 完全函数依赖与部分函数依赖

定义：在R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’ ! $\rightarrow$ Y, 则称Y对X完全函数依赖，记作X $\overset{F}{\rightarrow}$ Y。
若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X $\overset{P}{\rightarrow}$ Y。

[例1] 中 (Sno,Cno) $\overset{F}{\rightarrow}$ Grade是完全函数依赖，

(Sno,Cno) $\overset{P}{\rightarrow}$ Sdept是部分函数依赖

因为Sno →Sdept成立，且Sno是（Sno，Cno）的真子集

2.1.4 传递函数依赖

定义：在R(U)中，如果X→Y，(Y $\nsubseteq$ X) ,Y!→X Y→Z，则称Z对X传递函数依赖。
记为：X $\overset{t}{\rightarrow}$ Z

注: 如果Y→X，即X←→Y，则Z直接依赖于X。

例: 在关系Std(Sno, Sdept, Mname)中，有：
Sno → Sdept，Sdept → Mname
Mname传递函数依赖于Sno

2.2 码

2.2.1 码

定义：设K为R<U,F>中的属性或属性组合。若K $\overset{F}{\rightarrow}$ U，则K称为R的侯选码（Candidate Key）。若候选码多于一个，则选定其中的一个做为主码（Primary Key）。

主属性与非主属性

包含在任何一个候选码中的属性，称为主属性（Prime attribute）
不包含在任何码中的属性称为非主属性（Nonprime attribute）或非码属性（Non-key attribute）

全码

整个属性组是码，称为全码（All-key）

[例2]
关系模式S（Sno，Sdept，Sage），单个属性Sno是码，
SC（Sno，Cno，Grade）中，（Sno，Cno）是码
[例3]
关系模式R（P，W，A）
P：演奏者 W：作品 A：听众
一个演奏者可以演奏多个作品
某一作品可被多个演奏者演奏
听众可以欣赏不同演奏者的不同作品
码为(P，W，A)，即All-Key

2.2.2 外部码

定义：关系模式 R 中属性或属性组X 并非 R的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码（Foreign key）也称外码

如在SC（Sno，Cno，Grade）中，Sno不是码，但Sno是关系模式S（Sno，Sdept，Sage）的码，则Sno是关系模式SC的外部码
主码与外部码一起提供了表示关系间联系的手段

2.3 范式

范式是符合某一种级别的关系模式的集合
关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式
范式的种类：

第一范式(1NF)
第二范式(2NF)
第三范式(3NF)
BC范式(BCNF)
第四范式(4NF)
第五范式(5NF)

各种范式之间存在联系：

某一关系模式R为第n范式，可简记为R∈nNF。
一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化

2.4 2NF

2.4.1 1NF的定义

如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF
第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库但是满足第一范式的关系模式并不一定是一个好的关系模式

2.4.2 S-L-C不是一个好的关系模式

[例4] 关系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade)
Sloc为学生住处，假设每个系的学生住在同一个地方

函数依赖包括：
(Sno, Cno) $\overset{F}{\rightarrow}$ Grade
Sno → Sdept
(Sno, Cno) $\overset{P}{\rightarrow}$ Sdept
Sno → Sloc
(Sno, Cno) $\overset{P}{\rightarrow}$ Sloc
Sdept → Sloc

S-L-C的码为(Sno, Cno)
S-L-C满足第一范式。
非主属性Sdept和Sloc部分函数依赖于码(Sno, Cno)

S-L-C不是一个好的关系模式

插入异常
删除异常
数据冗余度大
修改复杂

原因
Sdept、 Sloc部分函数依赖于码。
解决方法
S-L-C分解为两个关系模式，以消除这些部分函数依赖
SC（Sno， Cno， Grade）
S-L（Sno， Sdept， Sloc）

关系模式SC的码为（Sno，Cno）
关系模式S-L的码为Sno
这样非主属性对码都是完全函数依赖

2.4.2 2NF的定义

定义：若R∈1NF，且每一个非主属性完全函数依赖于码，则R∈2NF。

例：S-L-C(Sno, Sdept, Sloc, Cno, Grade) ∈1NF
S-L-C(Sno, Sdept, Sloc, Cno, Grade) $\notin$ 2NF
SC（Sno， Cno， Grade） ∈ 2NF
S-L（Sno， Sdept， Sloc） ∈ 2NF

采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。

2.5 3NF

2.5.1 3NF的定义

定义：关系模式R<U，F> 中若不存在这样的码X、属性组Y及非主属性Z（Z  Y）, 使得X→Y，Y→Z成立， Y !→ X，则称R<U，F> ∈ 3NF。

若R∈3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码

2.5.2 2NF存在的问题

例：2NF关系模式S-L(Sno, Sdept, Sloc)中
函数依赖：
Sno→Sdept
Sdept → Sno
Sdept→Sloc
可得：
Sno→Sloc，即S-L中存在非主属性对码的传递函数依赖，S-L $\notin$ 3NF

解决方法
采用投影分解法，把S-L分解为两个关系模式，以消除传递函数依赖：
S-D（Sno， Sdept）
D-L（Sdept，Sloc）
S-D的码为Sno， D-L的码为Sdept。
分解后的关系模式S-D与D-L中不再存在传递依赖

S-L(Sno, Sdept, Sloc) ∈ 2NF
S-L(Sno, Sdept, Sloc) $\notin$ 3NF
S-D(Sno，Sdept) ∈ 3NF
D-L(Sdept， Sloc)∈ 3NF

采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

将一个2NF关系分解为多个3NF的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。

2.6 BCNF

2.6.2 BCNF的定义

定义：关系模式R<U，F>∈1NF，若X !→Y且Y $\subseteq$ X时X必含有码，则R<U，F> ∈BCNF。

等价于：每一个决定属性因素都包含码

若R∈BCNF

所有非主属性对每一个码都是完全函数依赖
所有的主属性对每一个不包含它的码，也是完全函数依赖
没有任何属性完全函数依赖于非码的任何一组属性

2.6.2 举例说明

[例8]在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。
函数依赖：
(S，J)→T，(S，T)→J，T→J
(S，J)和(S，T)都是候选码

STJ∈3NF
没有任何非主属性对码传递依赖或部分依赖
STJ $\notin$ BCNF
T是决定因素，T不包含码

解决方法

将STJ分解为二个关系模式：
ST(S，T) ∈ BCNF， TJ(T，J)∈ BCNF

没有任何属性对码的部分函数依赖和传递函数依赖

如果R∈3NF，且R只有一个候选码

2.7 多值依赖

2.8 4NF

2.9 规范化小结

关系数据库的规范化理论是数据库逻辑设计的工具

目的：尽量消除插入、删除异常，修改复杂，数据冗余

基本思想：逐步消除数据依赖中不合适的部分

实质：概念的单一化

关系模式规范化的基本步骤

不能说规范化程度越高的关系模式就越好
在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式
上面的规范化步骤可以在其中任何一步终止

3. 数据依赖的公理系统

3.1 逻辑蕴含

定义：对于满足一组函数依赖 F 的关系模式R <U，F>，其任何一个关系r，若函数依赖X→Y都成立, （即r中任意两元组t，s，若t[X]=s[X]，则t[Y]=s[Y]），则称F逻辑蕴含X →Y

3.2 Armstrong公理系统

关系模式R <U，F >来说有以下的推理规则：

A1.自反律（Reflexivity）：若Y $\subseteq$ X $\subseteq$ U，则X →Y为F所蕴含。
A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z  U，则XZ→YZ为F所蕴含。
A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。

3.2.1 自反律

自反律: 若Y $\subseteq$ X $\subseteq$ U，则X →Y为F所蕴含

证: 设Y  X  U
对R <U，F> 的任一关系r中的任意两个元组t，s：
若t[X]=s[X]，由于Y  X，有t[y]=s[y]，
所以X→Y成立，自反律得证

3.2.2 增广律

增广律: 若X→Y为F所蕴含，且Z $\subseteq$ U，则XZ→YZ 为F所蕴含。

证：设X→Y为F所蕴含，且Z $\subseteq$ U。
设R<U，F> 的任一关系r中任意的两个元组t，s：
若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；
由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，
所以XZ→YZ为F所蕴含，增广律得证。

3.2.3 传递律

传递律：若X→Y及Y→Z为F所蕴含，则X→Z为 F所蕴含。

证：设X→Y及Y→Z为F所蕴含。
对R<U，F> 的任一关系 r中的任意两个元组 t，s：
若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；
再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。

3.3 导出规则

根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：

合并规则：由X→Y，X→Z，有X→YZ。（A2， A3）
伪传递规则：由X→Y，WY→Z，有XW→Z。（A2， A3）
分解规则：由X→Y及 Z $\subseteq$ Y，有X→Z。（A1， A3）

根据合并规则和分解规则，可得引理
引理： X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）

3.4 函数依赖闭包

3.4.1 Armstrong公理系统是有效的、完备的

有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；
完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来

3.4.2 函数依赖闭包

定义： 在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。
定义：设F为属性集U上的一组函数依赖，X $\subseteq$ U， XF+ ={ A|X→A能由F 根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的闭包

F={X $\rightarrow$ A1, …… , X $\rightarrow$ An}的闭包F+计算是一个NP完全问题

3.4.3 闭包的引理

引理：设F为属性集U上的一组函数依赖，X，Y $\subseteq$ U，X →Y能由F 根据Armstrong公理导出的充分必要条件是Y $\subseteq$ XF+
用途：将判定X→Y是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题

3.4.4 求闭包的算法

算法：求属性集X（X $\subseteq$ U）关于U上的函数依赖集F 的闭包XF+

输入：X，F

输出：XF+

步骤：
（1）令X（0）=X，i=0
（2）求B，这里B = { A |( $\exists$ V)( $\exists$ W)(V→W $\in$ F∧V $\subseteq$ X（i）∧A $\in$ W)}；
（3）X（i+1）=B∪X（i）
（4）判断X（i+1）= X （i）吗?
（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。
（6）若否，则 i=i+l，返回第（2）步。

[例1] 已知关系模式R<U，F>，其中
U={A，B，C，D，E}；
F={AB→C，B→D，C→E，EC→B，AC→B}。
求（AB）F+ 。

解：设X（0）=AB；
(1) X（1）=AB∪CD=ABCD。

(2) X（0）≠ X（1）
X（2）=X（1）∪BE=ABCDE。

(3) X（2）=U，算法终止
（AB）F+ =ABCDE。

[例2] 设有关系模式R(A,B,C,D,E)，其上的函数依赖集:F={A→BC，CD→E， B→D，E→A}
(1)计算B+;(2)求出R的所有候选关键字

解：
（1）X={B},X(0)={B}, X(1)={BD}, X(2)={BD}，所以B+={BD}
（2）根据候选关键字定义，R的候选关键字只可能由F中各函数依赖的只出现在左边属性和未出现在函数依赖中的属性构成，但是除此以外，对于即出现在左边，又出现在右边的属性，也可能构成候选关键字。所以可进行组合分析得到A,BC,CD ，E也为候选关键字
综上，候选关键字为：A,BC,CD,E

3.4.5 函数依赖依赖集等价

定义：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。
引理：F+ = G+ 的充分必要条件是F $\subseteq$ G+ ，和G $\subseteq$ F+

3.4.6 最小依赖集

定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

F中任一函数依赖的右部仅含有一个属性。
F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。
F中不存在这样的函数依赖X→A， X有真子集Z使得F-{X→A}∪{Z→A}与F等价。

[例2] 关系模式S<U，F>，其中：
U={ Sno，Sdept，Mname，Cno，Grade }，
F={ Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade }
设F’={Sno→Sdept，Sno→Mname，Sdept→Mname，(Sno，Cno)→Grade，(Sno，Sdept)→Sdept}
F是最小覆盖，而F’不是。
因为：F ’ - {Sno→Mname}与F ’等价
F ’ - {(Sno，Sdept)→Sdept}也与F ’等价

3.4.7 极小化过程

定理：每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。
证明: 构造性证明，找出F的一个最小依赖集。

(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2 …Ak，k > 2，
则用 { X→Aj |j=1，2，…， k} 来取代X→Y。

(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，
若A $\in$ XG+，则从F中去掉此函数依赖。

(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，
逐一考查Bi （i=l，2，…，m），若A $\in$ （X-Bi ）F+ ，
则以X-Bi 取代X。

[例3] F = {A→B，B→A，B→C，A→C，C→A}
Fm1、Fm2都是F的最小依赖集：
Fm1= {A→B，B→C，C→A}
Fm2= {A→B，B→A，A→C，C→A}

F的最小依赖集Fm不唯一
极小化过程也是检验F是否为极小依赖集的一个算法

[例4] 设关系模式R<A，B，C，D>，函数依赖集F＝{A→C，C→A， B→AC，D→AC，BD→A｝
求出F的最小函数依赖集。

将F中的函数依赖都分解为右部为单属性的函数依赖。
F＝｛A→C，C→A， B→A，B→C，D→A，D→C，BD→A｝
去掉F中冗余的函数依赖。
判断A→C是否冗余。
设：G1＝｛C→A，B→A，B→C，D→A，D→C，BD→A｝，得：A+ =A
∵C 不属于A+ ∴A→C不冗余
判断C→A是不冗余。
设：G2＝｛A→C，B→A，B→C，D→A，D→C，BD→A｝，得： C+ =C
∵A不属于 ∴C→A不冗余
判断B→A是否冗余。
设：G3＝｛A→C，C→A，B→C，D→A，D→C，BD→A｝，得： B+ =BCA
∵A属于∴B→A冗余
判断B→C是否冗余。
设：G4＝｛A→C，C→A， D→A，D→C，BD→A｝，得： B+ =B
∵C不属于 ∴B→C不冗余
判断D→A是否冗余。
设：G5＝｛A→C，C→A， B→C，D→C，BD→A｝，得： D+ =DCA
∵A不属于 ∴D→A不冗余
判断D→C是否冗余。
设：G6＝｛A→C，C→A， B→C，BD→A｝，得： D+ =D
∵C不属于 ∴D→C不冗余
判断BD→A是否冗余。
设：G7＝｛A→C，C→A， B→C，D→C｝，得： BD+ =BDCA
∵A属于 ∴BD→A冗余
F=｛A→C，C→A，B→C，D→C｝
由于各函数依赖在部都为单属性．故：
Fm=｛A→C，C→A，B→C，D→C｝。

[例5] 设关系模式R<A，B，C，D，E，F>，函数依赖集F＝{AB→E，BC→D，BE→C，CD→B，CE→AF，CF→BD，C→A，D→EF｝，
求F的最小函数依赖集。

将F中的函数依赖都分解为右部为单属性的函数依赖。
F＝｛AB→E，BC→D，BE→C，CD→B，CE→A，CE→F，CF→B，CF→D，C→A，D→E，D→F｝
去掉F中冗余的函数依赖。
判断AB→E是否冗余。
设：G1＝｛ BC→D，BE→C，CD→B，CE→A，CE→F，CF→B，CF→D，C→A，D→E，D→F｝
得： AB+ =AB
∵ E不属于AB+ ∴AB→E不冗余
判断BC → D是否冗余。
设：G2=｛ AB→E，BE→C，CD→B ，CE→A，CE→F，CF→B，CF→D，C→A， D→E，D→F｝、
得： BC + =BCAEFD
∵ D属于BC + ∴BC→D冗余
判断BE→C是否冗余。
设：G3=｛ AB→E，CD→B,CE→A ，CE→F，CF→B，CF→D，C→A，D→E，D→F｝
得： BE + =BE
∵ C不属于BE + ∴BE→C不冗余
判断CD → B是否冗余。
设：G4=｛ AB→E,BE→C,CE→A ,CE→F，CF→B，CF→D，C→A，D→E，D→F｝
得： CD + =CDAEFB
∵ B属于CD + ∴CD→B冗余
判断CE → A是否冗余。
设：G5=｛ AB→E，BE→C，CE→F，CF→B，CF→D，C→A，D→E，D→F｝
得： CE + =CEFBDA
∵ A属于CE + ∴CE→A冗余
判断CE → F是否冗余。
设：G6=｛ AB→E，BE→C，CF→B，CF→D，C→A，D→E，D→F｝、
得： CE + =CEA
∵ F不属于CE + ∴CE→F不冗余
判断CF → B是否冗余。
设：G7=｛ AB→E，BE→C，CE→F，CF→D，C→A，D→E，D→F｝
得： CF + =CFDEF
∵ B不属于CF + ∴CF→B不冗余、
判断CF→D是否冗余。、
设：G8=｛ AB→E，BE→C，CE→F，CF→B，C→A，D→E，D→F｝
得： CF + =CFABE
∵ D不属于CF + ∴CF→D不冗余
判断C→A是否冗余。
设：G9=｛ AB→E，BE→C，CE→F，CF→B，CF→D，D→E，D→F｝
得： C + =C
∵ A不属于C + ∴C→A不冗余
判断D → E是否冗余。
设：G10=｛ AB→E，BE→C，CE→F，CF→B，CF→D，C→A，D→F｝
得： D + =DF
∵ E不属于D + ∴D→E不冗余
判断D → F是否冗余。
设：G11=｛ AB→E，BE→C，CE→F，CF→B，CF→D，C→A，D→E｝
得： D + =DE
∵ F不属于D + ∴D→F不冗余
∴F=｛ AB→E，BE→C，CE→F，CF→B，CF→D，C→A，D→E，D→F｝
去掉F中冗余的属性。
对于CF→D ，在决定因素中去掉C,D不属于属性F的闭包不能以F→D代替CF→D；
在决定因素中去掉F。求得：CF=CA，D不属于属性C的闭包不能以C→D代替CF→D
同样验证AB→E， BE→C，CE→F，CF→B
最终得到最小依赖集为
｛AB→E，BE→C，CE→F，CF→B，CF→D，C→A，D→E，D→F

4. 模式的分解

把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的
只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义

4.1 关系模式分解

三种模式分解等价的定义：

分解具有无损连接性
分解要保持函数依赖
分解既要保持函数依赖，又要具有无损连接性

定义：关系模式R<U,F>的一个分解：ρ={ R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>} ，且不存在 Ui $\subseteq$ Uj，Fi 为 F在 Ui 上的投影

定义：函数依赖集合{X→Y | X→Y $\in$ F+∧XY $\subseteq$ Ui} 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影

例1: 已知R<U,F>,U＝{A,B,C,D}, F={A->BD, D->C}, 如果将R分解为R1(U1, F1)和R2(U2, F2), 其中U1={A,B,D}, U2={A,C}, 则F1,F2分别是？

例：S-L（Sno， Sdept， Sloc）
F={ Sno→Sdept,Sdept→Sloc,Sno→Sloc}
S-L∈2NF

分解方法可以有多种：
1. S-L分解为三个关系模式：SN(Sno)
SD(Sdept)
SO(Sloc)
2. S-L分解为下面二个关系模式：NL(Sno, Sloc)
DL(Sdept, Sloc)
3. 将S-L分解为下面二个关系模式：ND(Sno, Sdept)
NL(Sno, Sloc)

4.1.1

S-L分解为三个关系模式：SN(Sno)
SD(Sdept)
SO(Sloc)

分解后的数据库丢失了许多信息
例如无法查询95001学生所在系或所在宿舍。
如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息

4.1.2

2. S-L分解为下面二个关系模式：NL(Sno, Sloc)
DL(Sdept, Sloc)

NL∞DL比原来的SL关系多了3个元组无法知道95002、95004、95005究竟是哪个系的学生
元组增加了，信息丢失了

4.1.3

3. 将SL分解为下面二个关系模式：
ND(Sno, Sdept)
NL(Sno, Sloc)
分解后的关系为：

与SL关系一样，因此没有丢失信息。

4.1.4 具有无损连接性的模式分解

关系模式R<U,F>的一个分解 ρ={ R1<U1,F1>，R2<U2,F2>， …，Rn<Un,Fn>} 若R与R1、R2、…、Rn自然连接的结果相等，则称关系模式R的这个分解ρ具有无损连接性（Lossless join）
具有无损连接性的分解保证不丢失信息
无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题

第3种分解方法具有无损连接性

问题:这种分解方法没有保持原关系中的函数依赖

SL中的函数依赖Sdept→Sloc没有投影到关系模式ND、NL上

4.1.5 保持函数依赖的模式分解

设关系模式R<U,F>被分解为若干个关系模式
R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>
（其中U=U1∪U2∪…∪Un，且不存在Ui $\subseteq$ Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency）

4.将SL分解为下面二个关系模式：
ND(Sno, Sdept)
DL(Sdept, Sloc)
这种分解方法就保持了函数依赖

4.1.6 小结

如果一个分解具有无损连接性，则它能够保证不丢失信息
如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况
分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。

第1种分解方法既不具有无损连接性，也未保持函数依赖，它不是原关系模式的一个等价分解
第2种分解方法保持了函数依赖，但不具有无损连接性
第3种分解方法具有无损连接性，但未持函数依赖
第4种分解方法既具有无损连接性，又保持了函数依赖

4.2 分解算法

算法1 判别一个分解的无损连接性
算法2 （合成法）转换为3NF的保持函数依赖的分解。
算法3 转换为3NF既有无损连接性又保持函数依赖的分解
算法4 （分解法）转换为BCNF的无损连接分解
算法5 达到4NF的具有无损连接性的分解

4.2.1 算法1 判断一个分解的无损连接性

(1)构造初始表：构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性Aj属于关系模式Ri, 则在表的第一i行第j列置符号aj，否则置符号bij 。
(2)根据F中的函数依赖修改表内容：考察F中的每个函数依赖X→Y,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行，则修改这些行，则使这些行上属性组Y所在的列上元素相同。