R(name,street,city,movietitle,movieyear)是BCNF，但是否是一个好的关系模式？数据冗余：
一名演员参演了几部电影，其地址就要重复几次；插入操作复杂：当某个演员参演一部新的电影，其地址有多少个就要插入多少个相应的元组；
删除操作复杂：某个演员删除某个地址，则他参演了多少部影片就要删除多少个元组；修改操作复杂：某个演员修改某个地址，则他参演了多少部
影片就要修改多少个元组。产生原因：存在多值依赖！理解2：在R（U）的任一关系r中，如果存在元组t，s使得t[X]=s[X]
，那么就必然存在元组w，v?r，（w，v可以与s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=
s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为X→→Y
。这里，X，Y是U的子集，Z=U-X-Y。txy1z2
sxy2z1wx
y1z1vxy2z2多值依赖（续）平
凡多值依赖和非平凡的多值依赖 若X→→Y，而Z＝φ，则称X→→Y为平凡的多值依赖 否则称X→→Y为非平凡的多值依赖
解决方法：SLC分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Grade）
SL（Sno，Sdept，Sloc）SC（Sno，Cno，Gra
de）∈2NF且∈3NFSL（Sno，Sdept，Sloc）∈2NF但∈3NFSnoCnoGrade
SCSLSnoSdeptSloc解决方法：把SL分解为两个关系模式SD（Sno，Sdept）
DL（Sdept，Sloc）SD的键为Sno，DL的键为Sdept。SnoSdeptSD
SdeptSlocDLSnoCnoGradeSC机械三P52习题3.3.1a)b)习题3
.3.4P60习题3.5.1i)ii)第三章关系数据库设计理论3.1函数依赖3.2函数依赖
的规则3.3关系数据库模式设计3.4分解的优劣3.5第三范式3.6多值依赖1.属性独立及随之产生的冗余
BCNF仍然可能存在冗余；BCNF模式中最常见的冗余一般是把（两个或多个）多对多联系置于同一个关系中。P61例3.28包括
影星的地址集合，地址集合包括街道和城市；还包括某个影星出演的电影名称和年份的集合由于影星的地址和参演的电影相互独立，表达这种独立
的方法是将地址和电影的各种组合都罗列出来，因此产生了冗余。不存在任何非平凡FD，键由全部属性集(name,street
,city,title,year）构成，是BCNF。2.多值依赖的定义（1）在关系R中当给定某个属性集合的值时，存在有一组与关
系中所有其他属性值相独立的属性值。若给定R中属于A的各属性的值，则存在一个属性集B，B的值独立于R中既不属于A也不属于B的属性集
合的值，则称R中MVDA1,A2,..,An→→B1,B2,..,Bm成立。其中独立的含义是指不能互相决定，即相互之间的取值
包含所有组合。理解1：设U是关系模式R的属性集合，X，Y，Z是U的子集，并且Z=U-X-Y。R中存在多值依赖X→→Y，当且仅当对
于R中的任一关系r，给定一对（x，z）值，有一组Y值，这组Y值仅仅决定于x值而与z值无关。多值依赖其它例子学校中一门课由多个教
员讲授，他们使用同一套参考书，每个教员可以讲授多门课，每一种参考书可以供多个教员使用，则教员、课程、参考书之间的关系如下图则关系
模式teaching(C,T,B)的键是(C,T,B)。Teaching属于BCNF，但仍存在插入删除问题，如去掉一本参考书
，或某一门课增加一个教员。原因：存在多值依赖C→→T课程教员参考书物理李勇王军普通物理学广电原理物理习题集
高数李勇张苹数学分析微分方程高等代数计算数学张苹周峰数学分析……………………课程C教员T参考书B物
理李勇普通物理学物理李勇广电原理物理李勇物理习题集物理王军普通物理学物理王军广电原理物理王军物理
习题集高数李勇数学分析高数李勇微分方程高数李勇高等代数高数张苹数学分析高数张苹微分方程高数张苹
高等代数………2.多值依赖（2）多值依赖的定义对于R中每个在A上取值相同的元组对t和u，能找到满足下列条件的元组v：
在A属性上的取值与t和u相同；在B属性上的取值与t相同；在AB外的其他所有属性上取值与u相同。隐含：即包含了B与“其他”的
所有取值组合。为什么?当交换t和u，则v?2.多值依赖（2）图3-40。注意标题含义：对于已有的t和u，多值依赖可以确保必定
有v的存在。交换t和u?2.多值依赖（2）P61例3.28根据多值依赖的定义，验证图3.39中的关系实例
是否满足给定的多值依赖。name→→streetcity元组t
元组u元组v3.多值依赖的推论平凡依赖规则如果{B1,B2,..,Bm}?{A1,A2,..,An}，则MVDA1,A
2,..,An→→B1,B2,..,Bm在任何关系中成立。传递规则如果关系中存在A1,A2,..,An→→B1,B2,..,
Bm和B1,B2,..,Bm→→C1,C2,..,Ck，则A1,A2,..,An→→C1,C2,..,Ck也成立。C的任何也属
于A的属性要从右边除去。MVD不遵循分解规则（P63例3.30）函数依赖是多值依赖的特殊情况。即若X→Y，则X→→Y。每个F
D也是MVD，即若A1,A2,..,An→B1,B2,..,Bm成立，则A1,A2,..,An→→B1,B2,..,Bm也成立。
证明：假设在关系R上存在FDA1,A2,..,An→B1,B2,..,Bm，并假设t和u是R中在A上取值相同的元组。为了证明
A1,A2,..,An→→B1,B2,..,Bm成立，需要证明R也包含元组v，它与t和u在A上取值相同，与t在B上取值相同，与u
在其他属性上取值相同。取v=u，由于FDA1,A2,..,An→B1,B2,..,Bm成立，确保了u和t在B上取值相同，显然u与
其自身在其他属性上也相同。b1互补规则(对称性)：互换BC符号即可得，即Z=U-X-Y，R中存在多值依赖X→→Y，则R中也
存在多值依赖X→→Z。多值依赖的对称性可以用完全二分图直观地表示出来。例3.31
互补规则说明：name→→titleyearXiZi1Zi2…ZimYi1Yi
2…Yin物理普通物理学光学原理物理习题集李勇王军4
.第四范式背景：在BCNF的基础上进一步消除冗余。MVDA1,A2,..,An→→B1,B2,..,Bm是非平凡的R中
存在除了A和B之外的其他属性第四范式定义在R中，若任一非平凡MVD成立时，都有左边是超键的结论，则R属于第四范式.第四范式是
BCNF的特例，所以满足4NF则满足BCNF，违反BCNF则违反4NF，反之不然。4NF?BCNF为什么
例3.325.分解到第四范式若多值依赖左边不是超键，则违反了4NF条件，运用投影分解方法将对应的关系R分解为两个关系：含
有A和B的全部属性含有A的全部属性和不在AB中的全部属性与BCNF中的左右圆分解方法非常相似！例3.34注意非平凡多
值依赖的定义。由于4NF是BCNF的特例，其分解方法也是左右圆法，所以相关的重组正确性结论不需证明依然有效。6.范式间的联系
图3-123NF:任何非平凡函数依赖的左侧是超键或右侧是主属性；BCNF：任何非平凡函数依赖的左侧是超键；4NF:
任何非平凡多值依赖的左侧是超键；第四范式是广义的BCNF，由于每个FD都是MVD，因此每个BCNF的违例也同
时是4NF的违例，即每个属于4NF的关系也属于BCNF；然而存在一些属于BCNF但不属于4NF的关系，如(name,title,
year,street,city)6.范式间的联系图3-13注意实用中一般到3NF即可，原因是考虑到FD的保持性。本
章小结关系模式、实例函数依赖闭包范式关系分解多值依赖机械三P65习题3.6.1习题3.6.2习题3.6.3
a)P70习题3.7.3a)习题3.7.4a)证明MVD的联合规则，即X,Y,Z都是属性集合，若X→→Y和
X→→Z成立，则X→→(Y∪Z)成立。证明：令U为R中属性的全集，W=U-X-Y-Z，假设任意两个元组(x,y1,z
1,w1)和(x,y2,z2,w2)，由X→→Y，则(x,y2,z1,w1)和(x,y1,z2,w2)必∈R；
又因(x,y1,z1,w1)和(x,y1,z2,w2)∈R，且X→→Z，所以(x,y1,z2,w1)(x,y1,z1,
w2)也∈R；又由(x,y2,z2,w2)和(x,y2,z1,w1)∈R，且X→→Z，所以(x,y2,z1
,w2)(x,y2,z2,w1)也∈R；综上所述，对任意的(x,y1,z1,w1)和(x,y2,z2,w2)∈R，由于
X→→Y和X→→Z，可得到(x,y1,z1,w2)和(x,y2,z2,w1)也∈R，因此MVDX→→(Y∪
Z)成立。给出反例，证明下列MVD规则：若A→→BC，则A→→B不正确；ABCDabc
dabcd’ab’c’dab’c’d’FDC→A为什么不考虑？原因是，若考虑，则A，B，C都是
键，关系R就BCNF，无需再分解。8.投影函数依赖假设一个含有FD集合S的关系R，通过计算R1=πL(R)得到R对其部分属
性L的投影，那么R1中成立的FD称为函数依赖集S的投影，由满足以下两个条件的FD组成：从S推断而来只包含R1的属性如何根据原
关系的FD集来计算投影属性集的FD集？满足原关系的所有FD（不是原关系的FD集，而是原关系所有FD集的闭包）中保留那些只含有投影
结果属性的即可算法3计算函数依赖集的投影输入：关系R和通过投影R1=πL(R)计算得到的关系R1，以及R中成立的FD的集
合S。输出：在R1中成立的FD集合。步骤：令T为最终输出的FD集合，初始化T为空集。对于R1的属性集合的每一个子集X，计算
X+。该计算依据FD集合S，可能会涉及一些在R模式中但不在R1模式中的属性。对于所有在X+中且属于R1的属性A，将所有非平凡的FD
X→A添加到T中。现在，T是在R1中成立的FD基本集，但可能不是最小化基本集，通过计算最小函数依赖集来完成，参看算法2。P4
6例3.13假设R(A,B,C,D)中有FD：A→B,B→C和C→D。假设要对R投影，删除属性B，得到关系R1(A
,C,D)，计算R1的FD集合。为了得到满足原关系的所有FD，需要计算{A,C,D}的八个子集的闭包，并使用FD集合的完全集。给
出一些简化规则。除去空集和不能推出非平凡FD的属性集合；如果已知集合X的闭包包含了全部的属性，那么就不能再通过X的超集来寻找新
的FD；注意该例子中还用到了Armstrong公里中的增广律∵{A}+={A,B,C,D},所以FDA→C和A→D在
R1中成立，要注意A→B在R中成立，但B不是R1中的属性；又因{C}+={C,D},所以可以得到FDC→D
；而{D}+={D},所以不能添加新的FD,至此单元素集闭包计算完成。由于{A}+包含了R1的所有属性
，因此没有必要考虑{A}的任何超集；而{C,D}+={C,D},即不能再添加任何的FD，闭包计算到此为止。
所以得到的FD是：A→C，A→D和C→D。函数依赖内容逻辑思路函数依赖及其概念键与超键函数依赖的蕴含关系
?属性集的闭包求属性集的闭包算法属性集闭包能做什么？证明某个FD可以从初始的FD集S推出从给定的FD集判断某个属性集是否
为关系模式的键函数依赖集的闭包解释引入的目的：为关系模式的分解中进行FDs的投影函数依赖集闭包的求解方法通过属性集闭包求解
算法及其简化规则Armstrong公理系统函数依赖关系基本集相关算法补充如何求最小基本集：对每个FD，判断其是否是冗余投
影函数依赖P47习题3.2.1是在基本概念上建立的基本题目习题3.2.3b)增广律c)假传递习题3.2.
4是在例题基础上派生出的代表性题型，必须做习题3.2.7是结论比较有特色的证明题，建议可能的话做一做本节习题
假设有关系R(A,B,C,D,E)和一些FD集，要把这些FD投影到关系S(A,B,C)上。根据下面给出的R中的FD集合，
求出在S中成立的FD集合。a)AB?DE,C?E,D?C和E?A补充机械第三版P48习题3.2
.10a)和例题非常相似，将来考中的概率也就相应较大，建议必做：证明(X+)+=X+证明分两步：1、若B∈X+，则
B∈(X+)+2、若B∈(X+)+，则B∈X+证明：(1)很显然，因为由求闭包的算法（求A的闭包，则闭包的
初始集为{A}，即A一定在A的闭包集中）可知，X+?(X+)+。(2)若B∈(X+)+，根据闭包定义，则应存在A1
?B且A1∈X+才把B加入X+的闭包中，分以下两种情况：（a）A1∈X，由于A1?B，则B∈X+；（b）A1不属于X，
则存在A2?A1，A2∈X。以此类推，若A2不属于X，则存在A3?A2，A3∈X。……即总能找到一个Ai∈X，而且函数依赖集中存在
{Ai?Ai-1,Ai-1?Ai-2,…,A2?A1}，这样才能使A1∈X+，由A1?B和求闭包算法可知，B∈X+。
在a和b两种情况下都有，若B∈(X+)+，则B∈X+，则(X+)+?X+由(1)(2)可知，(X+)+=X+
。第三章关系数据库设计理论3.1函数依赖3.2函数依赖的规则3.3关系数据库模式设计3.4分解的优劣
3.5第三范式3.6多值依赖关系数据库模式设计的目标是在保证正确反映数据模型的基础上尽量避免冗余和数据不一致。设计
步骤当模式有问题时，深入分析模式本身，引入“分解”的思想，即把一个关系模式分解成两个较小的模式；引入“BC范式”，针对性地消除
某些冗余等异常情况，本质上是通过分解确保满足范式，即如果分解前的模式不满足范式，就要使得分解后的两个较小的模式均满足范式。3.3
关系数据库模式设计当一个关系中含有过多信息时产生冗余等问题叫做异常。冗余：信息被没有必要地多次重复。更新异常：如
果修改了某些元组信息但没有同时修改其它相关元组相关信息可能会引发的错误。删除异常：删除某些元组的某些值会丢失信息。可以使用分解
关系的方法来消除异常。分解不仅仅是指将一个关系的属性集分为两部分（可能有非空交集，即部分属性可能要拷贝）；还要将原关系的元组信息正
确地转移到这两个新关系中。1.异常2.关系分解基本描述给定一个模式为{A1,A2,..,An}的关系R，要将其分解为关系S
和T，它们的模式分别为{B1,B2,..,Bm}和{C1,C2,..,Ck}，并满足{A1,A2,..,An}={B1,B2
,..,Bm}∪{C1,C2,..,Ck}S=πB1,B2,..,Bm(R).即S中的元组是R中所有元组在S属性集{B1
,B2,..,Bm}上的投影，即对R的任何一个元组，取其在{B1,B2,..,Bm}的分量，作为S当前实例的对应元组。T=πC
1,C2,..,Ck(R).即T中的元组是R中所有元组在T属性集{C1,C2,..,Ck}上的投影注意：投影后可能会产生重
复结果，此时两元组只保留一个（元组也要满足单值约束）P49例3.14。注意分析中用例子解释了为什么这种分解消除了异常。不能消
除的“异常”是原关系的键“冗余”，不算冗余1.冗余消除了，关系Movies2的每部电影的片长只出现一次。2.
更新的风险消除了，只需修改Movies2中的一个StarWars元组上的Length值，不会造成同一部电影有不同片长的情况。
3.删除异常的风险消除了，如果删除Gonewiththewind的影星，将导致这部电影从Movie3中消失，但这部电影的其
他信息仍可以从Movie2中得到。3.BCNFBCNF的定义1关系R满足BCNF当且仅当：如果R中非平凡FDA1,A2,
..,An→B成立，则{A1,A2,..,An}是关系R的超键。即每个非平凡FD的左边都必须是超键。由于超键不一定要最小化，因此
可以等价描述为，每个非平凡FD的左边都必须包含键。例3.15只要找到一个FD其左边不是超键，就说明该关系违反BCNF。例3.
16例3.17（例3.35）任意一个二元关系属于BCNF。有趣的结论要记住！设二元关系属性为A和B，共分四种情况讨论：
没有非平凡FD;A→B成立，但B→A不成立；B→A成立，但A→B不成立；A→B和B→A都成立；（则A和B都是键）
注意第四种情况引出的一点说明：多个键情况下只要包含任一个键都算满足BCNF的条件！4.分解为BCNF重复使用适当的分解，可以
把任一关系模式分解为具有以下性质的多个真子集：每个真子集都满足BCNF；原始关系中的数据都正确反映在分解后的关系上，即原始关系
实例应能从分解后的几个关系实例中重构。关系分解为多个二元关系则必定满足第一条，但不一定满足第二条，所以分解时必须小心分解的方法
是寻找违反BCNF的非平凡FDA→B，尽可能将A能决定的属性都找到，放到该FD的右端。然后将关系模式直接分解为两部分：一部分
为该FD的左端A和右端属性集一部分为该FD的左端A和该FD未包括的所有属性这两部分分别对应图3-24的右圆和左圆原因何在？单
纯从A的角度考虑：右圆是BCNF，因为对右圆包含的属性集，A就是键左圆是BCNF，因为左圆中的“其他”并不属于FD，所以“其他
”和独立的A不可能同列某个FD的右和左，所以不会出现因为左边的A不是超键而同时决定右边某属性的违反BCNF的情况。例3.18
将Movies1(title,year,length,genre,studioName,starName),FD:
title,year→length,genre,studioName分解为BCNF。解：由于{title,year
,starName}是Movies1的唯一键，而{title,year}不是超键，因此FD:title,year→len
gth,genre,studioName违反了BCNF；在该FD中，已经包含了{title,year}所能函数
决定的所有属性，因此基于这个BCNF违例把Movies1分解为：Movies2(title,
year,length,genre,studioName)和Movies3(title,
year,starName)可以证明Movies2和Movies3均属于BCNF。问题：分解后的左圆不会出现
因为独立的A在FD左边而引发的违例，那么会不会出现别的违例情况呢？答：有可能。因为“其他”和A放在一个关系中后可能会发现某些FD
（左边不是A）不满足BCNF。怎么办？处理办法很简单^-^。对左圆找出其中违反条件的非平凡FD，继续用左右圆分解法分解。迭代到当
前左圆也满足条件为止。每次分解后对右圆是否需要验证？需要。考虑右圆生成的原则，可能B中包含有违例的FD，尽管A在左端的FD不再
可能违例。左右圆的进一步验证P51例3.19{title,year,studioName,president,pr
esAddr}，title,year→studionamestudioname→presidentp
resident→presAddr这个例子中出现了一次分解得到的右圆仍然不满足BCNF条件的情况。初始关系有三个FD，第一
个不违反条件，后两个都违反，所以可以选择后两个中任一个作为分解的起点。教材上是选择了studioName→president分解
后的右圆包含两个FD，其中第二个不满足条件，所以要以其为新起点再进行分解，分解后新的右圆满足条件，可以得到结果第三章关系数据库
设计理论3.1函数依赖3.2函数依赖的规则3.3关系数据库模式设计3.4分解的优劣3.5第三范式3
.6多值依赖关系模式分解的重要性质1.消除异常2.信息的可恢复分解后子模式的自然连接得到的元组等于原关系的元组P4
9例3.14中的关系movies2和movies3进行自然连接后可得到关系movies13.依赖的保持如果FD的投影在分解
后的关系上成立，能否确保对分解后的关系用连接重构获取的原始关系仍然满足原来的FD?BCNF的分解可以保证1、2，但不一定能保
证3。1.从分解中恢复信息提出背景：为什么左右圆分解方法能保持原关系的信息？原始元组的投影可被重新连接，得到与原元组完全相
同的元组(不多也不少)。例子：关系R(A,B,C)和一个违反BCNF条件的FDB→C。两种题设情况：①另有FDA→B，
唯一的键是{A}②若B→C是唯一的非平凡FD，此时键是{A,B}(why?)两种情况下左右圆分解得到的都是{A,B}和{B,
C}，对任意一个元组t(a,b,c)来说，分解后得到(a,b)和(b,c)，通过自然连接(a,b,c)可以恢复回来。即分解后不会丢
失原有的元组！---（1）分解后会增加原来没有的元组吗？R中元组t(a,b,c)和v(d,b,e)，分解后再连接可能会出现x(
a,b,e)，这个x是不是R的元组？是就没问题，否就说明分解方法有问题（改变了原有信息）。由于原关系有FDB→C，所以e=c
，即x=t，因此没问题！即按照左右圆法分解后再组合生成的每一个元组都是原关系中的元组。---（2）由(1)(2)可知，按照左右圆
法分解后再组合可以得到和原关系实例对应的所有元组，且一一对应，不多也不少。该结论在属性集X,Y,Z上的推广：如果Y→Z在关
系R上成立，且R的属性集为X∪Y∪Z，那么R=πX∪Y(R)πY∪Z(R)。即根据左右圆分解
方法对一个关系进行分解，则原始关系可以通过自然连接来精确地恢复。对应刚才的例子，实际上这种一般情况都归结为刚才的推导过程。得到
一般性结论：用左右圆法分解关系，一定可以通过重新连接正确恢复原始关系（同时兼顾模式和实例）反例：P543.21如果不存在Y→
Z或其对称的Y→X成立，则可能无法恢复关系。2.依赖的保持如果FD的投影在分解后的关系上成立，那么对分解后的关系用连接重构获
取的原始关系仍然满足原来的FDBCNF无法保证依赖的保持P57例3.25Bookings(title,theater,
city)和FD:theater→city，titlecity→theaterBookings的键是{title,
city}和{theater,title}存在theater→city这个BCNF的违例，按照该违例对关系进行分解得到
两个关系模式：{theater,city}和{theater,title}=满足theater→city不满足c
itytitle→theater第三章关系数据库设计理论3.1函数依赖3.2函数依赖的规则3.3关系数据库
模式设计3.4分解的优劣3.5第三范式3.6多值依赖关于范式第一范式：每个元组的各分量是原子值第二范式：不
允许存在左边是键真子集且右边是非主属性的非平凡FD(不存在部分函数依赖)例如关系模式S-L-C(SNO,SDEPT,SLOC
,CNO,G)第三范式：非平凡FD的左边是超键或者右边是主属性（键中的属性）BC范式：非平凡FD的左边必须是超键第四范式
：与多值依赖有关，后面介绍。P57例3.25中体现了什么问题？分解后的关系模式中可能会丢失原关系的某些FD。为避免这个问题，
提出第三范式，它比BCNF范式的要求低，有些按照BCNF范式的要求需要分解的关系按照第三范式的要求就不需要分解了。例3.25的原
关系按照第三范式的要求就已经达到了，可以不再分解。如果提高要求到BCNF，则分解后会满足BCNF，但会丢失某些FD。任一关系模式
均可无信息丢失地分解到3NF，且原FD仍存在于分解后的新关系中。3NF在实际应用中已经够了，但要注意与BCNF相比，它保留了相当
多的冗余。第三范式（3NF）3NF模式综合算法算法3.26给出了将关系R分解为一系列满足以下条件的关系：分解得到的关系都
属于3NF；分解包含无损连接；分解具有依赖保持性质。输入：关系R和其上成立的函数依赖集F。输出：由R分解出的关系集合，其中
每个关系均属于3NF。分解具有无损连接和依赖保持性质。方法：依次执行以下步骤：1.找出F的一个最小基本集，记为G。2.对于G
中的每一个FDX→A，将XA作为分解出的某个关系的模式。3.如果分解出的关系模式均不包含R的超键，则增加一个关系，其模式为R
的任何一个键。例3.27考虑关系R(A,B,C,D,E)，其上的FD有AB→C,C→B,和A→D。判断
R是否是3NF,若不是则分解使其成为3NF。关系R有两个键：{A,B,E}和{A,C,E}，存在3NF的违例
A→D，所以不是3NF。求解FD的最小基本集:{AB→C,C→B,和A→D}，这三个FD的任何一个都不可以
由另两个导出；且任一个FD左边的属性都不可以去除。根据3NF的综合算法，将每个FD所包含的属性作为一个关系模式，从而得到R1(A
,B,C)，R2(B,C)和R3(A,D)，由于R2是R1的子集，可以去除。关系R的键为：{A,B,E}和{A,C,E}
，而R1和R3都不包含键，所以增加一个模式为键的关系，记为R4=(A,B,E)综上所述，关系R最终被分解为：R1(A,B,
C),R3(A,D)和R4=(A,B,E)。SLC的键为(Sno，Cno)存在左边是键真子集且右边是非主属性的非平凡FD
：Sno→Sdept，Sno→Sloc，因此不属于2NF。SnoCnoGradeSdeptSloc
SLC例:关系模式SLC(Sno，Sdept，Sloc，Cno，Grade)，Sloc为学生住处，假设每个系的学生住在
同一个地方。第三章关系数据库设计理论第三章关系数据库设计理论清P823.5节～3.8节
3.1函数依赖3.2函数依赖的规则3.3关系数据库模式设计3.4分解的优劣3.5第三范式3.6多
值依赖3.1函数依赖一个关系R上的函数依赖FD是指如果R的两个元组在属性A1,A2,…,An上一致，那么它们在其他属性B1,
B2,…,Bm上的值也必定相同。写为：A1A2…An→B1,B2,…,Bm称作：
A1,A2,…,An函数决定B1,B2,…,Bm1.函数依赖的定义函数依赖的右边往往是单个属性，而
FD:A1A2…An→B1,B2,…,Bm等价于一组FD的集合：A1A2…An→B1
A1A2…An→B2……
A1A2…An→Bm注意：FD是针对模式而非实例的！不能仅通过一个关系实例确定FD。P38例3.1从图3
-2（清P82例3.20图3.27）中判断正确的FD?错误的FD?ExampleDrinkers(name
,addr,beersLiked,manf,favBeer)ReasonableFD’stoassert:nam
e->addrname->favBeerbeersLiked->manfExampleDataname a
ddr beersLiked manf favBeerJaneway Voyager Bud A.B.
WickedAleJaneway Voyager WickedAle Pete’s WickedAleSpock Ent
erprise Bud A.B. BudBecausename->addrBecausename->fav
BeerBecausebeersLiked->manf满足两个条件，就认为属性或属性集合{A1,A2,…,An}是关系R
的键：这些属性函数决定关系的所有其他属性；没有一个{A1,A2,…,An}的真子集能函数决定R的其他属性。注意：键必须是最
小的，但键的最小化不代表最小值，容易产生错误理解。例如，{A,B,C}和{D,E}均为最小化的键，然而只有{D,E}是
所有键中属性数最小的。键只包括单属性A时，记作A而不是{A}！2.关系的键例3.13，证明关系Movies(
title,year,length,genre,studioName,starName)的键为{title,year
,starName}。证明：首先证明title,year,starN
ame→length,genre,studioName然后进一步证明{title,year,
starName}的任何真子集都不能函数决定其他属性。有时一个关系可能会有多个键，通常指定其中一个为主键(primaryke
y)。一个包含键的属性集叫做超键(superkey)。因此，超键能够函数决定关系中所有其他属性的属性集。每个键都是超键，而某些
超键不是键(最小化)。例3.14，在例3.13中除了键{title,year,starName}是超键，任何包含
这个集合的超集都是超键，例如{title,year,length,starName}3.
超键ExampleDrinkers(name,addr,beersLiked,manf, favBeer){name
,beersLiked}isasuperkeybecausetogethertheseattributesdet
erminealltheotherattributes.name->addr，favBeerbeersLiked
->manf{name,beersLiked}isakeybecauseneither{name}nor{
beersLiked}isasuperkey.namedoesn’t->manfbeersLikeddoesn’
t->addrTherearenootherkeys,butlotsofsuperkeys.Anysup
ersetof{name,beersLiked}.课堂习题机三P40习题3.1.2习题3.1.3（清P87
习题3.5.2、习题3.5.4）做好的并最先正确回答（即思路正确合理，计算结果也准确无误）第三章关系数据库设计理论3.1
函数依赖3.2函数依赖的规则3.3关系数据库模式设计3.4分解的优劣3.5第三范式3.6多值依赖
本节目标：如何从关系中已知的FD集合推导出其他FD？例3.17(函数依赖的传递规则)：如果关系R(A,B,C
)满足FD：A→B和B→C，那么就可以推断出R也满足FD：A→C。证明：假设任意两个在A上取值相同的元
组为(a,b1,c1)和(a,b2,c2)，由于R满足A→B，又已知两个元组在A上取值相同，因此它们在B上的值也相同，即b
1=b2，即元组等价于(a,b,c1)和(a,b,c2)，这里b=b1=b2.又因B→C，且这两个元
组在B上的值相同，所以他们在C上的取值也相同，即c1=c2.由此，证明了R中只要两个元组在A上取值相同，则他们在C上
也取值相同，即存在FD：A→C。3.2函数依赖的规则1.函数依赖的推导分解规则：可以用FD的集
合A1A2…An→Bi(i=1,2,…,m)替换FD：A1A2…An→B1,B2,…,Bm组合规则：
可以用一个FD：A1A2…An→B1,B2,…,Bm替换FD集合A1A2…An→Bi(i=1,2,…,m
)机P40例3.5（清P89例3.20）分解规则只针对FD的右边，不针对左边机P40例3.6
（清P89例3.27）2.分解/组合规则FD:A1A2…An→B1,B2,…,Bm其中，{B1,B2,
…,Bm}{A1A2…An}平凡函数依赖非平凡函数依赖完全非平凡函数依赖注意二者区别平凡依赖规则去掉右边的
平凡项P42图3-3（P90图3.28）3.平凡函数依赖闭包的基本概念{A1,A2,…An}的闭包记作{A1,A2
,…An}+假设{A1,A2,…An}是属性集合，S是FD的集合。则S下的属性集合{A1,A2,…An}的闭包是集合B
，使得每一个满足S中所有FD的关系，也同样满足：A1,A2,…An?B(式1)。即式1是从S的FD中推断出来的。
理解：U为关系的所有属性集，S为U上的一组FD集合，属性集合{A1,A2,…An}是U的子集，{A1,A2,…An}在FD集合
S下的闭包{A1,A2,…An}+={B|{A1,A2,…An}?B能从S推导出}，即所有能从{A1,A2,…An}推导出的属性
的集合就是{A1,A2,…An}的闭包。{A1,A2,…An}总是在{A1,A2,…An}+中，因为{A1,A2,…An}?
{A1,A2,…An}4.计算属性的闭包闭包的计算过程从初始属性集合出发，只要某个FD左边的属性全部包含在这个属性集中，就
将其右边的属性也包含进去，迭代到不再有新属性为止。闭包计算过程的详细描述输入：属性集合{A1,A2,…An}，FD的集合S
输出：闭包{A1,A2,…An}+1.如果必要，分解S中的FD，使每个FD的右边只有一个属性2.设X是属性集合，也就是闭包。首
先，将X初始化为{A1,A2,…An}3.反复寻找这样的FD:B1,B2,…,Bm?C,使得B1,B2,…,Bm在X中，而C
不在X中，若找到则把C加入X，并重复这个过程。因为集合X只能增长，而任何一个关系模式中的属性集合都是有限的，所以最终没有任何元素能
再加入X时，本步骤结束。4.当不能再添加任何属性时，集合X就是{A1,A2,…An}+。P43例3.8（P90例3.
28）计算闭包的一个用途判断当前FD是否由给定的FD集合S推断而来，只要看它右侧的属性是否被包含在左侧初始属性集在S下的闭包中
即可。例3.9（P92例3.29），注意后半部分的反例中，初始属性集选择当前FD的左边属性集合。引申：为什么能用闭
包算法判断当前FD是否能从给定的S中推断出来？证明：分别证明以下两个条件正确性：闭包中所有FD都是正确的/满足S的理
解：即证明若属性D∈{A1,A2,…,An}+，则任满足S的关系R一定满足A1,A2,…,An?D完备性：闭包算法可以找到从S中
推断出来的所有FD。（任何满足S的FD都包含在闭包里）5.闭包算法为何有效证明条件一（正确性）：闭包中所有FD都是正确的/满
足S的分两种情况：1、A1,A2,…,An?D是平凡FD，则显而易见。2、A1,A2,…,An?D不是平凡FD证明：
设D通过B1,B2,…,Bn?D加入{A1,A2,…,An}+，则必须B1,B2,…,Bn在{A1,A2,…,An}+中，即
：A1,A2,…,An?B1,B2,…,Bn，由传递规则，A1,A2,…,An?D。证明条件二（完备性）闭包算法可以找
到从S中推断出来的所有FD即：假设算法3.7认为FDA1,A2,…,An?B(1)不能从S中推断，也就是说{A1,A
2,…,An}关于S的闭包中不包含B，必须证明FDA1,A2,…,An?B确实不能从S中推断，即证明至少存在一个关系实例满足S中
所有FD集合，但不满足A1,A2,…,An?B。教材的证明过程实际上是在证明这个逆否命题！该实例构造见P44图3-5
该证明又分为两部分证明该实例满足S中的所有FD。（反证法，假定不满足某个FD，则出现矛盾）证明该实例不满足式1。证明传
递规则若关系R中FDA1A2…An→B1,B2,…,Bm和B1B2…Bm→C1,C2,…,Ck都成立，那么FDA1A2
…An→C1,C2,…,Ck在R中也成立。证明：从FDA1A2…An→B1,B2,…,Bm可知，B1,B2,…,Bm
均属于{A1，A2，…,An}+，且由于存在FDB1B2…Bm→C1,C2,…,Ck，可以把C1,C2,…,Ck加入到
{A1，A2，…,An}+。因为C集合中所有的元素都属于{A1，A2，…,An}+，所以可以得出结论：对于任何
满足A1A2…An→B1,B2,…,Bm和B1B2…Bm→C1,C2,…,Ck的关系而言，A1A2…An→C1,C2,…,
Ck都成立。P44例3.10（清P92例3.30）6.用闭包测试证明传递规则和键证明{A1，A2，…，An}是一
个关系的键只有超键才能函数决定所有其他属性，因此第一步是检查{A1，A2，…,An}+是否包含了该关系的全部属性；最小化特征
验证：从属性集合中拿走一个属性，剩余的属性集合计算闭包，是否还能包含对应关系的所有属性？如不能，则找到键；否则为非键的超键。函数
依赖的公理系统函数依赖的公理系统是模式分解算法的基础函数依赖有一个有效而完备的公理系统—Armstrong公理Armstro
ng公理系统：设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R。对R来说有以下的推理规则
：自反律：若Y?X?U，则X?Y为F所蕴涵，称为平凡FD。增广律：若X?Y为F所蕴涵，且Z?U，则XZ?YZ
为F所蕴涵。传递律：若X?Y及Y?Z为F所蕴涵，则X?Z为F所蕴涵。根据上述的三个推理规则，可以得到下面三条很有用的推理
规则：合并规则：由X?Y且X?Z，则X?YZ伪传递规则：由X?Y且WY?Z，则XW?Z分解规则：由X?Y且Z?
Y，则X?Z函数依赖的公理系统7.函数依赖的闭包集合可以在给定FD集合的基础上运用一些规则或闭包算法推断出其他FD定
义：若F为关系模式R(U,F)的函数依赖集，我们把F以及所有被F逻辑蕴涵的FD的集合称为F的闭包，记为F+。即：F+={X→
Y|X→Y∈F∨“应用Armstrong公理从F中导出的任何X→Y”}F包含于F+。规定：若X为U的子集，X→Φ
属于F+。如果F=F+，则F为函数依赖的一个完备集。例1:已知关系模式R(A，B，C)，F={A→C,B→C},求F+
解：∵U={A，B，C}，左部不同的属性集组合有7种：A、B、C、AB、BC、AC、ABC。（1）∵{A}+={AC}
∴A→Φ、A→A、A→C、A→AC。（2）∵{B}+={BC}∴B→Φ、B→B、B
→C、B→BC。（3）∵{C}+={C}∴C→Φ、C→C。（4）∵{AB}+={ABC}∴AB→Φ、AB→AB、AB→A、AB→B、AB→C、AB→BC、AB→AC、AB→ABC。（5）∵{BC}+={BC}∴BC→Φ、BC→BC、BC→B、BC→C。（6）∵{AC}+={BC}∴AC→Φ、AC→BC、AC→B、AC→C。（7）∵{ABC}+={ABC}∴ABC→Φ、ABC→ABC、ABC→A、ABC→B、ABC→C、ABC→BC、ABC→AB、ABC→AC。所以F+如下：∴A→?、A→A、A→C、A→AC、B→Φ、B→B、B→C、B→BC、C→Φ、C→C、AB→?、AB→AB、AB→A、AB→B、AB→C、AB→BC、AB→AC、AB→ABC、BC→Φ、BC→BC、BC→B、BC→C、AC→Φ、AC→BC、AC→B、AC→C、ABC→Φ、ABC→ABC、ABC→A、ABC→B、ABC→C、ABC→BC、BC→AB、ABC→AC最小函数依赖集F’满足以下三个条件：⑴F’中的每个函数依赖的右部都是单个属性。⑵对于F’中的任一函数依赖X→Y来说，F’-{X→Y}与F’都不等价。⑶对于F’中的任一函数依赖X→Y来说，(F’-{X→Y})∪{Z→Y}与F’都不等价，其中Z为X的真子集。算法2：设有关系模式R(U,F)，求最小函数依赖集F’输入：函数依赖F输出：最小函数依赖F’步骤：⑴将F中的所有依赖变为右部是单属性的依赖。⑵依次考察F中的函数依赖。假设为X→Y，在F-{X→Y}中求X+，看X+是否包含Y，如果是则删去X→Y，否则不能删去X→Y。直到F中的最后一个。⑶逐个检查F中每个函数依赖左部的每个属性，消去冗余属性，判断XY→Z中属性Y是否冗余，即判断F-{XY→Z}∪{X→Z}与F是否等价。在F中求X+，如果X+中包含Z，则X→Z成立，XY→Z可用X→Z代替。否则，Y不能消去。P47习题3.2.9（P95习题3.6.9）R(A,B,C)F={A→B，B→A，B→C，A→C，C→A，C→B}，求最小函数依赖集。P47习题3.2.9（P95习题3.6.9）R(A,B,C)F={A→B，B→A，B→C，A→C，C→A，C→B}，求最小函数依赖集。解得：Fmin1={B→C，A→C，C→A，C→B},Fmin2={A→B，B→C，C→A},Fmin3={A→B，B→A，A→C，C→A}Fmin4={B→A，A→C,C→B}。讨论：F的最小依赖集Fmin并不一定是唯一的，得到的Fmin的结果与检查F中的函数依赖的次序有关。FDC→A为什么不考虑？原因是，若考虑，则A，B，C都是键，关系R就BCNF，无需再分解。 |
|
