以下为《关系规范化基础》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

第三章 关系规范化基础

一、内容提要

关系数据库的设计中，一个非常重要的被视为理论问题的内容是如何构造合理的关系，使之能准确地反应现实世界，有利于应用和具体的操作。这一问题就是关系规范化要研究的问题。

通过本章的学习，应重点掌握：

(1)函数依赖及Armstrong公理系统

(2)为什么要对模式进行分解，如何分解

(3)如何判断关系模式达到几范式

(4)如何求属性的闭包及如何求最小函数依赖集

(5)判断分解后的关系模式是不是无损连接或保持函数依赖

(6)判断分解后的关系模式既无损连接又保持函数依赖

(一)函数依赖及相关概念

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

(1)完全函数依赖：在R(U)中，如果X
Y，并且对于X的任何一个真子集X`，都有X`不能决定Y，则称Y对X完全函数依赖，记作： X
Y

例 给定一个学生选课关系SC(Sno，Cno，G)，我们可以得到 F={(Sno，Cno)
G}，对(Sno，Cno)中的任何一个真子集Sno或Cno都不能决定G，所以，G完全依赖于Sno，Cno。

(2)平凡的函数依赖：如果X
Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：X
Y

(3)传递依赖：在R(U)中，如果X
Y，(Y
X)，Y
X，Y
Z

则称Z对X传递依赖。

(4)码：设K为R(U，F)中的属性的组合，若K
U，则K为R的候选码，若有多个候选码，选一个作为主码。

注: 候选码也称候选关键字。

 (5) 主属性和非主属性：包某某任何一个候选码中的属性叫做主属性，否则叫做非主属性。

(6) 外码：若R(U)中的属性或属性组X非R的码，但是另一关系的码，则称X为外码。

范式

在关系数据库中的一个非常重要的问题就是如何评价分解后的各个关系模式的好坏。通常可以通过判断分解后的模式达到几范式来评价模式的好坏。范式有：1NF、2NF、3NF、BCNF、4NF和5NF。这几种范式之间的关系如下： 1NF
2NF
3NF
BCNF
4NF
5NF

通过模式分解，将低一级范式的关系模式分解成了若干个高一级范式的关系模式的集合，这种过程叫做规范化。下面将给出各个范式的定义。

1．1NF(第一范式)

定义 若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)。

例 供应者和它所提供的零件信息，关系模式如下：

FIRST (Sno，Sname，Status，City，Pno，Qty)并且有F＝{Sno
Sname， Sno
Status，Status
City，(Sno，Pno)
Qty}。

具体的关系如图5—l所示。

Sno

Sname

Status

City

Pno

Qty



S1

精益

20

天津

P1

200



S1

精益

20

天津

P2

300



S1

精益

20

天津

P3

480



S2

盛某某

10

北京

P2

168



S2

盛某某

10

北京

P3

500



S3

东方红

30

北京

P1

300



S3

东方红

30

北京

P2

280



S4

泰达

20

上海

P2

460





从图5—1中可以看出，每一个分量都是不可再分的数据项，所以是1NF。但是，1NF带来四个问题：

(1)冗余度大：例如每个供应者的Sno，Sname，Status，City要与零件的种类一样多；

(2)引起修改操作的不一致性：例如供应者S1从“天津”搬到 “上海”，若稍不注意，就会使一些数据被修改，另一些数据没有被修改，导致数据修改的不一致性；

(3)插入异常：若某个供应者的其它信息未提供时，如“零件号”，则不能进行插入操作；

(4)更新异常：若供应商S4的P2零件销售完了，删除后，在基本关系FIRST找不到S4，可S4又是客观存在的。

正因为上述原因引入了2NF。

2．2NF(第二范式)

定义 若关系模式R
1NF，且每一个非主属性完全依赖于码，则关系模式R
2NF。

即当1NF消除了非主属性对码的部分函数依赖，则成为 2NF。

例 FIRST关系中的码是Sno、Pno，而Sno
Status，因此非主属性Status部分函数依赖于码，故非2NF的。

若此时，将FIRST关系分解为：

FIRSTl(Sno，Sname，Status，City)
2NF

FIRST2(Sno，Pno，Qty)
2NF

因为FIRSTl和FIRST2中的码分别为Sno和Sno，Pno每一个非主属性完全依赖于码。

3．3NF(第三范式)

定义 若关系模式R(U，F)中不存在这样的码X，属性组Y及非主属性Z(Z
Y)使得X
Y，(Y
X)Y
Z成立，则关系模式R
3NF。

即当2NF消除了非主属性对码的传递函数依赖，则成为3NF。

例 FIRSTl
3NF，因为在分解后的关系模式FIRSTl中有：

Sno
Status，Status
City，存在着非主属性City传递依赖于码Sno。 4．BCNF(巴克斯范式)；

定义 若关系模式R
1NF，若X
Y且Y X时，X必含有码，则关系模式R
BCNF。

即当3NF消除了主属性对码的部分和传递函数依赖，则成为 BCNF。

结论 一个满足BCNF的关系模式，应有如下性质：

(1)所有非主属性对每一个码都是完全函数依赖；

(2)所有非主属性对每一个不包含它的码，也是完全函数依赖；

(3)没有任何属性完全函数依赖于非码的任何一组属性。

(三)多值依赖

1．多值依赖

定义 若关系模式R(U)中，X、Y、Z是U的子集，并且Z＝U—X—Y。当且仅当对R(U)的任何一个关系r，给定一对(x，z) 值，有一组Y的值，这组值仅仅决定于x值而与z值无关，则称“Y 多值依赖于X”或“X多值决定Y”成立。记为：X
Y。

2．多值依赖的性质

多值依赖具有如下六条性质：

(1)多值依赖具有对称性。即若X
Y，则X
Z，其中Z＝U—X—Y

(2)多值依赖的传递性。即若X
Y，Y
Z，则X
Z—Y

(3)函数依赖可以看成是多值依赖的特殊情况

(4)若X
Y，X
Z，则X
YZ

(5)若X
Y，X
Z，贝，X
Y
Z；

(6)若X
Y，X
Z，则X
Z—Y。

3．4NF(第四范式)

定义 (4NF)若关系模式R
1NF，若对于R的每个非平凡多值依赖X
Y且Y X时，X必含有码，则关系模式R(U，F)
4NF。

(四)函数依赖的公理系统

Armstrong公理系统：设关系模式R(U，F)，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：

(1)A1自反律：若Y
X
U，则X
Y为F所蕴涵；

(2)A2增广律：若X
Y为F所蕴涵，且Z
U，则XZ
YZ为F所蕴涵；

(3)A3传递律：若X
Y，Y
Z为F所蕴涵，则X
Z为F所蕴涵。

根据上述三条推理规则又可推出下述三条推理规则：

合并规则：若X
Y，X
Z，则X
YZ为F所蕴涵

伪传递率：若X
Y，WY
Z，则XW
Z为F所蕴涵

分解规则：若X
Y，Z
Y，则X
Z为F所蕴涵。

引理：X
A：A1…A2… A1成立的充分必要的条件是X
Ai成立

（I=1，2，3…，k）

(五)函数依赖的闭包F+及属性的闭包X +：

函数依赖的闭包

定义 关系模式R(U，F)中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为：F+。

属性的闭包

定义 设F为属性集U上的一组函数依赖，X
U， ＝{A | X
A能由F根据Armstrong公理导出}，则称 为属性集X关于数依赖集F的闭包。

求属性X的闭包X吉的算法

算法 求属性的闭包

输入 X，F

输出

步骤

令X(0)=X，i＝0

求B，B＝{A |(
v)(
w)}(V
W
F
V
X(i)
A
W)}

X(i+1)＝B
X(i)

判断X(i+1)= X(i) 吗

(5)若相等，或X(i)=U，则X(i)为属性集X关于函数依赖集F的闭包。且算法终止

(6)若不相等，则i＝i+1，返回第二步

例1 已知关系模式R(U，F)，U＝{A，B，C，D，E)；

F＝{A
B，D
C，BC
E，AC
B}

求

解 求 ，由上述算法，设X(0)=AE

计算X(1): 逐一扫描F中的各个函数依赖，找到左某某A、E或AE的函数依赖，得到一个：A
B。故有X(1)=AE
B。

计算X(2)：逐一扫描F中的各个函数依赖，找到左某某ABE或ABE子集的函数依赖，因为找不到这样的函数依赖，所以，X(1)＝X(2)。算法终止，

＝ABE。

求(AD)；，由上述算法，设XtO’＝AD

计算X‘”：逐一扫描F中的各个函数依赖，找到左某某A、D或AD的函数依赖，得到两个：A+B，D--~C函数依赖。故有

XCl’：ADUBC。

计算X‘n：逐一扫描F中的各个函数依赖，找到左某某ADBC或ADBC子集的函数依赖，得到两个：BC—E，AC—B函数依赖。故有X‘2，：ABCDUE。所以，X(2’：ABCDE：U，算法终止， (AD)吉：ABCDE。

(六)最小函数依赖集

1．等价和覆盖

定义 一个关系模式R(U，F)上的两个依赖集F和G，如果

F’＝G’，则称F和G是等价的，记做F三G。

若F三G，则称G是F的一个覆盖，反之亦然。两个等价的函

数依赖集在表达能力上是完全相同的。

2．最小函数依赖集

定义 如果函数依赖集F满足下列条件，则称F为最小函数

依赖集或最小覆盖。； (1)F中的任何一个函数依赖的右部仅含有一个属性；” (2)F中不存在这样一个函数依赖X—A，使得F与F一{X— A}等价；扩 (3)F中不存在这样一个函数依赖X—A，X有真子集Z使得 F一{X—A}U{Z+A}与F等价。；· 3．计算最小函数依赖集的算法。 算法 计算最小函数依赖集。

输入 一个函数依赖集

输出 F的一个等价的最小函数依赖集G。

步骤

(1)用分解的规则，使F中的任何一个函数依赖的右部仅含有一个属性；，：’ (2)去掉多余的函数依赖：从第一个函数依赖X+Y开始将其从F中去掉，然在剩下的函数依赖中求X的闭包X’，看X’是否包含Y，若是，则去掉X—Y；否则不能去掉，依次做下去。直到拽不到冗余的函数依赖；

(3)去掉各依赖左部多余的属性。一个一个地检查函数依赖宏部非单个属性的依赖。例如XY+A，若要判Y为多余的，则以醑+A代替XY+A是否等价?若AE(X)’，则Y是多余属性，可以去掉。

例2 已知关系模式R(U，F)，U＝{A，B，C，D，E，G}；江 F＝{AB+C，D—EG，C—A，BE+C扩 BC—D，CG—BD，ACD-~B，CE—AG}； 请将F化为最小函数依赖集。； 解 此题可以有两种求解方法，求解过程如下：辈 方法1 (利用算法求解，使得其满足三个条件)； (1)利用分解规则，将所有的函数依赖变成右边都是单个属：

性的函数依赖，得F为：

F＝{AB—C，D+E，D+G，C—A，BE—C

BC—D，CG—B，CG—D，ACD—B，

CE+A，CE—G}

(2)去掉F中多余的函数依赖，具体做法如下：从第一个函数依赖开始从F中去掉它(假定它为X—Y)，剩下的函数依赖F’求 X’的闭包，看X’是否含Y，若包含Y，则X+Y为冗余函数依赖，则去掉它，否则不去。依次下去，直到能满足定义最小依赖的第二个条件。故有：

①设AB—C为冗余的函数依赖，则去掉AB+C得

F1＝{D+E，D—G，C+A，BE—C

BC+D，CG—B，CG—D，ACD+B，

CE—A，CE+G}

因为从Fl中找不到找到左某某AB或AB子集的函数依赖，则(AB)击＝①。

所以AB+C非冗余的函数依赖，不能去掉。

②设CG—B为冗余的函数依赖，则去掉CG—B得

F2＝{AB+C，D—E，D+G，C+A，BE—C

BC+D，CG+D，ACD+B，

CE—A，CE+G}

求(CG)左

设X‘*)：CG

计算X”’：逐一扫描F2中的各个函数依赖，找到左某某C、(；或CG的函数依赖，得到一个：C—A函数依赖。故有X“’＝ CGA。

计算X‘“：逐一扫描F2中的各个函数依赖，找到左某某CGA或CGA子集的函数依赖，得到一个：CG+D函数依赖。故有 X‘9’＝ACDG。

：： 计算X‘“：逐一扫描F2中的各个函数依赖，找到左某某AC—拓或ACDG子集的函数依赖，得到两个：ACD—B，D，>E函数依瓤故有XCa)2ABCDEG。；：扭 因为X‘’’＝ABCDEG；U，算法终止，(CG)占＝ABCDE。· 所以CG—B为冗余的函数依赖，从F2中去掉。。：’ ③设CG+D为冗余的函数依赖，则去掉CG—D得；捍 F3＝{AB+C，D-*E，D+G，C---,-A，BE—C

BC+D，ACD-~B，CE—A，CE+G}： 求(CG)占；； 设XCO)：CG： 计算Xm：逐一扫描F3中的各个函数依赖，找到左某某C、G城CG的函数依赖，得到一个：C+A函数依赖。故有Xu’：；ACG。熟 计算X‘”：逐一扫描F3中的各个函数依赖，找到左某某ACG诚ACG子集的函数依赖，周为找不到这样的函数依赖。故有谨‘’’＝X”’，算法终止。(CG)占＝ACG。： 因为ACG芒D，所以CG+D非冗余的函数依赖，不能从F3冲去掉。；· ④设CE+A为冗余的函数依赖，则去掉CE—A得瞰 F4＝{AB--*'C，D--~E，D-*G，C+A，BE—C； BC-*-D，CG—D，ACD-~B，CE+G)： 求(CZ)击； 设X(O’：CE芝 计算X-)：逐一扫描F4中的各个函数依赖，找到左某某C、E藏CE的函数依赖，得到一个：C—A函数依赖。故有：X(1’＝ 5ACE。 [ 计算XC2)：逐一扫描F4中的各个函数依赖，找到左某某ACE；藏ACE子集的函数依赖，得到一个：CE—G函数依赖。故有：骚

X‘2)＝ACEG。

计算X”’：逐一扫描F4中的各个函数依赖，找到左某某

ACEG或ACEG子集的函数依赖，得到一个：CG—D函数依赖。

故有：

X‘’’＝ACDEG。

计算X‘“：逐一扫描F4中的各个函数依赖，找到左某某AC—

DEG或ACDEG子集的函数依赖，得到一个：ACD—B函数依赖。

故有：

X‘‘’＝ABCDEG。

因为X“’＝ABCDEG＝U，算法终止，(CE)占：ABCDEG。

所以CE+A为冗余的函数依赖，从F4中去掉。

又因为F4中无多余函数依赖所以转(3)。

(3)去掉F4中各函数依赖左边多余的属性。

函数依赖ACD+B，属性A是多余的，去掉A得CD—B，因

为C—A，所以可推导出ACD—B。

故最小函数依赖集为：

FMIN＝{AB+C，D—E，D+G，C—A，BE—C

BC+D，CG—D，CD+B，CE—G}

方法2 (利用Armstrong公理系统的推理规则求解)

①假设CG—B为冗余的函数依赖，那么，从F中去掉它后能

根据Armstrong公理系统的推理规则导出。

因为 CG+D C—A (已知)

所以 CGA—ACD (增广律)

因为 ACD—B (已知)

所以 CGA—B (传递律)

因为 C—A (已知)

所以 CG—B (蕴涵)

②同理可证：CE—A是冗余的。

③又因 C—A，CD—B可知，ACD-~B L 故 去掉左边多余的属性得CD-~B。

需要注意的是，F的最小依赖集FMIN不一定是惟一的，它与对各函数依赖FDi及X—A中X各属性的处理顺序有关。

例3 已知关系模式R(U，F)，U＝{A，B，C}；

F＝{A+B，B—A，B+C，A+C，C—A}

求最小函数依赖集。

分析 此题可以有两种不同的答案，下面分别叙述如下。

答案1 设B—A是冗余的，将其从F中去掉，看能否根据，Armstrong公理系统的推理规则导出。

因 B--~C，C—A (已知)

故 B—A (传递律)

故B-,-A是冗余的，将其从F中去掉，得n为

F1：{A+B，B--~C，A+C，C+A}。

又设A—C为冗余，将其从F1中去掉 ·

因 A—B，B--~C (已知)· 故 A—C (传递律)

故A+C是冗余的，将其从n中去掉，得Fm为：… FM，＝{A—B，B+C，G+A}。’ 因为在FM，中的其它函数依赖是非冗余的，所以，FMl为最小函数依赖集。

答案2 设B—C是冗余的，将其从F中去掉，看能否根据、Armstrong公理系统的推理规则导出。： 因 B—A，A+C (已知)

故 B—C (传递律)

故B+C是冗余的，将其从F中去掉，得FM2为

FM2＝{A—B，B+C，A—C，C—A}。：i 因为在Fm中的其它函数依赖是非冗余的，所以，FM2为最小

函数依赖集。

从上分析我们可以得到两个最小函数依赖集Fh4，和Fht。，因此，F的最小函数依赖集不是惟一的。

(七)模式分解

1．分解

定义 (分解)关系模式R(U，F)的一个分解是指，P‘{Rl

(Ul，P1)，R2(U2，F2)，…R。(U。，F。)}，其中：

n

U＝UU，并且没有U(U，1≤i，j≤n，E是F在U上的投影。

其中Fi＝{X—Y[X—YEF’八XY三Ui}

对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有三种情况：

(1)分解具有无损连接性；

(2)分解要保 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 据DE—C，CE—A不能修改此表所以修改后的表如卜 · i声5—16所示。 ———

摹 ” 。 ‘”： ③根据A—C，对上表进行处理，由于属性列A上第1，2，5府相同，但属性列C上对应的1，2，5行上有a3元素，所以，只能将藻1，5行b13改为a3。又根据C+D将属性列D上b2‘bs：改为a4，：修改后的表如图5—17所示。

④根据CE+A，对上表进行处理，由于属性列CE上第4，5行相伺，但属性列A上对应的5行为al元素，所以，将第4行b41改为a，。修改后的表如图5—18所示。

⑤继续扫描F不能修改此表，由于找不到一行全为a，所以该分解是有损的。

(3)考虑A—C，因为AC不包含候选关键字，所以AC不是 BCNF，故将ABCDE分解为两个子模式R1(AC)R2(ABDE)。此时，R1正BCNF。 ，

继续分解R2，考虑B—D，将ABDE分解为两个子模式R21 (BD)R22(ABE)，此时，R21和R22均属于BCNF。所以R分解为BCNF，并具有无损连接性的分解如下：

P＝{AC，BD，ABE}

[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《关系规范化基础》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。