求最小函数依赖集例题

第一部分：一、求最小依赖集例：设有依赖集：F={AB→C，C→A，BC→D，ACD→B，D→EG，BE→C，CG→BD，CE→AG}，计算与其等价的最小依赖集。

解：1、将依赖右边属性单一化，结果为：F1={AB→C，C→A，BC→D，ACD→B，D→E，D→G，BE→C，CG→B，CG→D，CE→A，CE→G }2、在F1中去掉依赖左部多余的属性。

对于CE→A，由于C →A成立，故E是多余的；对于ACD→B，由于（CD）+=ABCEDG，故A是多余的。

删除依赖左部多余的依赖后：F2={AB→C，C→A，BC→D，CD→B，D→E，D→G，BE→C，CG→B，CG→D，CE→G }3、在F2中去掉多余的依赖。

对于CG→B，由于（CG）+=ABCEDG，故CG→B是多余的。

删除依赖左部多余的依赖后：F3={AB→C，C→A，BC→D，CD→B，D→E，D→G，BE→C，CG→D，CE→G }CG→B与CD→B不能同时存在，但去掉任何一个都可以，说明最小依赖集不唯一。

二、求闭包例：关系模式R（U，F），其中U={A，B，C，D，E，I}，F={A →D，AB→E，BI→E，CD→I，E→C}，计算（AE）+。

解：令X={AE}，X（0）=AE；计算X（1）；逐一扫描F集合中各个函数依赖，在F中找出左边是AE子集的函数依赖，其结果是：A →D，E→C。

于是X（1）=AE∪DC=ACDE；因为X（0）≠X（1），且X（1）≠U，所以在F中找出左边是ACDE子集的函数依赖，其结果是：CD→I。

于是X（2）=ACDE∪I=ACDEI。

虽然X（2）≠X（1），但在F中未用过的函数依赖的左边属性已没有X（2）的子集，所以不必再计算下去，即（AE）+=ACDEI。

三、求候选键例1：关系模式R（U，F），其中U={A，B，C，D}，F={A→B，C→D}，试求此关系的候选键。

解：首先求属性的闭包：（A）+=AB，（B）+ =B，（C）+ =CD，（D）+ =D（AB）+ =AB，（AC）+=ABCD=U，（AD）+ =ABD，（BC）+ =BCD，（BD）+ =BD，（CD）+ =CD（ABD）+ =ABD，（BCD）+ =BCD，因（AC）+=ABCD=U，且（A）+=AB，（C）+ =CD，由闭包的定义，AC→A，AC→B，AC→B，AC→D，由合并规则得AC→ABCD=U；由候选码的定义可得AC 为候选码。

1、要建立关于系、学生、班级、研究会等信息的一个关系数据库。

规定：一个系有若干专业、每个专业每年只招一个班，每个班有若干学生，一个系的学生住在同一个宿舍区，一个系只有一个系名，一个系名也只给一个系用。

每个学生可参加若干研究会，每个研究会有若干学生。

描述学生的属性有：学号、姓名、出生年月、系名、班号、宿舍区。

描述班级的属性有：班号、专业名、系名、人数、入校年份。

描述系的属性有：系号、系名、系办公室地点、人数。

描述研究会的属性有：研究会名、成立年份、地点、人数。

学生参加某研究会，有一个入会年份。

试给出上述数据库的关系模式；写出每个关系的最小依赖集（即基本的函数依赖集，不是导出的函数依赖）；指出是否存在传递函数依赖；对于函数依赖左部是多属性的情况，讨论其函数依赖是完全函数依赖还是部分函数依赖，指出各关系的候选键、外部关系键。

（课本P176）参考答案：关系模式：学生（学号，姓名，出生年月，系名，班号，宿舍区）班级（班号，专业名，系名，人数，入校年份）系（系号，系名，系办公室地点，人数）研究会（研究会名，成立年份，地点，人数）入会（学号，研究会名，入会年份）关系的最小函数依赖集：学生：{学号→姓名，学号→出生年月，学号→班号，班号→系名，系名→宿舍区}候选键：学号；外键：班号，系名不存在部分函数依赖，但存在传递函数依赖：学号→系名，所以该关系最高属于2NF。

班级：{班号→专业名，专业名→系名，班号→人数，班号→入校年份，{专业名，入校年份}→班号}候选键：班号，{专业名，入校年份}；外键：系名存在部分函数依赖：班号→系名，所以该关系最高属于1NF。

系：{系号→系名，系号→系办公室地点，系号→人数}候选键：系号；外键：无不存在部分函数依赖，也不存在传递函数依赖，所以该关系最高属于3NF。

研究会：{研究会名→成立年份，研究会名→地点，研究会名→人数}候选键：研究会名；外键：无不存在部分函数依赖，也不存在传递函数依赖，所以该关系最高属于3NF。

数据库函数依赖例题数据库函数依赖是数据库系统中一个非常重要的概念，它可以帮助设计更有效率的数据库系统。

按照函数依赖理论，一个关系可以被定义为一组属性和一组函数依赖，函数依赖被定义为当函数f（X）= f（Y）时，X 与 Y 之间存在函数依赖。

本文档将用一个例题来讨论函数依赖，并讨论它在数据库设计中的重要性以及如何用来提高数据库的有效性。

二、例题一个数据库系统中有一张表，表名为“学生”，它有两个属性：学号（K）和姓名（N），每个学生都有一个唯一的学号，姓名不能相同。

假定这里有两个函数：f1（K）= N f2（N）= K，即学号与姓名之间有一种函数依赖，即学号可以确定一个学生的姓名，而姓名也可以确定一个学生的学号。

三、函数依赖的意义函数依赖的意义很重要，它是用来定义数据库系统的结构以及表之间的关系的一个非常有用的概念。

函数依赖可以帮助用户限制数据库管理系统中的信息流。

正确的函数依赖关系可以有效地减少冗余的数据，还可以帮助更容易地识别数据库之间的内在关系，更快地完成查询等功能。

四、函数依赖的重要性函数依赖有助于更好地设计数据库，可以减少数据库中的冗余数据，确保数据的一致性。

函数依赖还可以使数据库更加规范，减少记录和表之间的关系，帮助数据库管理者实现最佳化，并且帮助用户实现最佳数据库设计。

五、实现函数依赖的方法函数依赖的实现方法有很多，比如解决视图和查询优化的方法以及属性拆分的方法，采用属性拆分的方法可以更有效地实现函数依赖，将一个属性拆分成多个属性，这样就可以增加函数依赖，并有效地减少数据冗余。

另外，还可以使用视图和查询优化的方法，可以有效地改善现有的查询，减少冗余数据的产生。

六、结论数据库函数依赖是一个非常重要的概念，函数依赖能够有效地管理数据库，减少数据冗余。

它能够让数据库更加规范，帮助提高数据库的有效性。

通过使用属性拆分的方法和视图和查询优化的方法，可以有效地实现数据库函数依赖，最终达到比较理想的效果。

最小函数依赖集Fm的求法：1.根据分解规则，将函数依赖的右端分解成单个属性2.对于F中的每个函数X→A，设G=F-{X→A}，如果A∈X G+，则将X→A从中删除，否则保留。

3.对于F中每一个左端包含多个属性的X→A，选择X的每个子集Z，如果A∈Z F+，则用Z→A代替X→A。

例如：F={BE→G,BD→G,CDE→AB,CD→A,CE→G,BC→A,B→D,C→D}求Fm。

解：1）右端分解成单个属性F={BE→G,BD→G,CDE→A, CDE→B,CD→A,CE→G,BC→A,B→D,C →D}2）设G=F-{X→A}，如果A∈X G+，则将X→A删除，否则保留（1）G=F-{ BE→G }={BD→G,CDE→A, CDE→B,CD→A,CE→G,BC →A,B→D,C→D}，则（BE）G+=BEDG，包含G，则删除。

（2）G=F-{BD→G, }={ CDE→A, CDE→B,CD→A,CE→G,BC→A,B →D,C→D}，则（BD）G+=BD，不包含G，则保留。

（3）G=F-{CDE→A}={ BD→G, CDE→B,CD→A,CE→G,BC→A,B →D,C→D}，则（CDE）G+= CDEBGA，包含A，则删除。

（4）G=F-{CDE→B}={ BD→G, CD→A,CE→G,BC→A,B→D,C→D}，则（CDE）G+= CDEAG，不包含B，则保留。

（4）G=F-{CD→A,}={ BD→G, CDE→B，CE→G,BC→A,B→D,C→D}，则（CD）G+= CD，不包含A，则保留。

（5）G=F-{ CE→G,}={ BD→G, CDE→B，CD→A, BC→A,B→D,C →D}，则（CE）G+= CEDBAG，包含G，则删除。

（5）G=F-{ BC→A,}={ BD→G, CDE→B，CD→A, B→D,C→D}，则（BC）G+= BCDGA，包含A，则删除。

（6）G=F-{ B→D,}={ BD→G, CDE→B，CD→A, C→D}，则（B）G+= B，不包含D，则保留。

关系模式R(U，F)中，U=ABCDEG，F={B->D，DG->C,BD->E,AG->B,ADG->BC} 求F的最小函数依赖集方法如下：1.根据分解规则，将函数依赖的右端分解成单个属性该题目的话要将：BC分解成单个属性。

F={ADG->B,ADG->C,······}2.对于F中的每个函数X->A,设G=F-{X->A},如果A属于X的闭包，则将X->A从中删除，否则保留。

该题目：1)G=F-{B->D},则B的闭包={B},包不含D,则保留2)G=F-{DG->C},则DG的闭包={DG},不包含C,则保留3)G=F-{BD->E},则BD的闭包={BD},不包含E,则保留4)G=F-{AG->B},则AG的闭包={AG},不包含B,则保留5)G=F-{ADG->B},则ADG的闭包={ADGBCE},包含B,则删除6)G=F-{ADG->C},则ADG的闭包={ADGBCE},包含C,则删除F={B->D,DG->C,BD->E,AG->B}R(U, F)，U=ABCDEF, F={AD→E, AC→E, BC→F, BCD→AF, BD→A, AB→F, A→C}求最小函数依赖集答案是：分解右部为属性组的函数依赖，得F={AD→E,AC→E,BC→F,BCD→A,BCD→F,BD→A,AB→F,A→C}对于AD→E，∵(AD)的闭包=ADCE, 又∵E不属于ACDE∴AD→E 冗余对于AC→E，∵(AC)的闭包＝AC,又∵E不属于AC，∴AC→E不冗余对于BC→F，∵(BC)的闭包＝BC，又∵F不属于BC，∴BC→F 不冗余对于BCD→A，∵(BCD)的闭包=ABCDEF，又∵A不属于ABCDEF ∴BCD→A 冗余对于BCD→F，∵(BCD)的闭包=ABCDEF，又∵F不属于ABCDEF ∴BCD→F 冗余对于BD→A，∵(BD)的闭包=BD，又∵A不属于BD，∴BD→A 不冗余对于AB→F，∵(AB)的闭包=ABCDEF，又∵F属于ABCDEF ∵AB→F 冗余对于A→C，∵A的闭包=A，又∵C不属于A，∴A→C 不冗余∴F的最小函数依赖集为{AC→E,BC→F,BD→A,A→C}。

分解为BCNF的例子：例如：有U = {学号, 课程号, 课程名, 学习期限, 成绩, 奖学金}，F= {课程号→学习期限，( 学号, 课程号)→成绩，成绩→奖学金，课程名→课程号，课程号→课程名}。

现将函数依赖模式( U, F) 做转化为BCNF的分解。

步骤如下：( 1) 求出F的等价的最小函数依赖集合F’=F，令ρ= {( U, F) }；( 2) 因检查到：成绩→奖学金∈F，但这里成绩不属于KEY(U, F)，所以(U, F)不属于 BCNF，应做如下分解：U={成绩，奖学金}(= X∪{A})F= {成绩→奖学金}U= {学号, 课程号, 课程名, 学习期限, 成绩} ( = U - {A})F= {课程号→学习期限，(学号, 课程号) →成绩，课程号→课程名，课程名→课程号}令ρ= {( U, F) , (U, F) }(3) ρ中(U, F)已属于BCNF，但在(U, F)中检查到：课程号→学习期限∈F，但这里课程号不属于KEY(U, F)，所以(U, F)仍不属于BCNF，于是将(U, F)再做如下分解：U= {课程号, 学习期限} ( = X∪{A})F= {课程号→学习期限}U= {学号, 课程号, 课程名, 成绩} ( = U - {A})F= {(学号, 课程号) →成绩, 课程号→课程名, 课程名→课程号}令ρ= {( U, F) , (U, F) , (U, F) }(4) ρ中(U, F) , (U, F)都已属于BCNF，但在(U, F) 中仍检查到：课程号→课程名∈ F，但课程号不属于KEY(U, F)，所以知(U, F)仍不属于BCN F，于是再做如下的分解：U= {课程号, 课程名} ( = X ∪ {A})F= {课程号→课程名, 课程名→课程号}U= {课程号, 学号, 成绩} ( = U - {A})F= {( 学号, 课程号) →成绩}令ρ= {( U, F) , (U, F) , (U, F) , (U, F) }ρ中的所有函数依赖模式全属于BCN F，算法终止。

习题课1．设有函数依赖集F = { D→G，C→A，CD→E，A→B}，计算闭包D+，(AC)+，(ACD)+。

2．设有关系模式R（U，F），其中：U={A，B，C，D，E}，F = { A→BC，CD→E，B→D，E→A}。

求R的所有候选码。

3．设有关系模式R（U，F），其中：U={E，F，G，H}，F={E→G，G→E，F→EG，H→EG，FH →E}，求F的最小依赖集。

4．设有关系R和函数依赖F：R（W，X，Y，Z），F = { X→Z，WX→Y }。

试求下列问题：（1）关系R属于第几范式？（2）如果关系R不属于BCNF，请将关系R逐步分解为BCNF。

要求：写出分解过程。

候选键：WZ部分函数依赖：Z部分函数依赖于WX存在部分函数依赖，不是2NF，是1NF分解结果为：R1（X,Z）R2(W,X,Y)5．设有关系模式R（U，F），其中U=ABCDE，F = { A→B，BC→E ，ED→AB }。

①计算A F+、(AB)F+、(ABC)F+及(BCD)F+；②求R的所有候选码，并说明理由；③R最高满足第几范式？为什么？④若R不属于BCNF，试改进该关系数据库设计，使它满足BCNF。

6．设有关系模式R（U，F），其中U={A,B,C,D,E}，F = { A→D，E→D，D→B，BC→D ，DC→A }。

①计算D F+、(DC)F+、(BC)F+及(CE)F+；②求R的所有候选码，并说明理由；③R最高满足第几范式？为什么？④若R不属于BCNF，试改进该关系数据库设计，使它满足BCNF。

主属性CE;非主属性ABD由于D对于CE的部分函数依赖，只是1NF1)候选键CE，唯一1.最小化函数依赖集1）A F+=A; E F+=E; D F+=D; BC F+=BC; DC F+=BCD（出现在右侧的）2）B F+=B; C F+=C; D F+=BD（未出现在右侧的）F为最小化函数依赖集2.求候选键为CE3.不存在不在F中出现的属性4.不存在函数依赖X→Y,满足XY=U5.按左部相同的原则分组，得到ρ={R1（A,D）,R2(E,D),R3(D,B),R4(B,C,D),R5(D,C,A)}6.考虑候选键CE,ρ*=Ρu R6(C,E)7．已知R<U,F>，U={ A,B,C,D,E }，F={AB →C, C →D,D →E}，R的一个分解ρ={ R1( A,B,C )，R2(C,D)，R3(D,E) }判断ρ是否为无损连接？8．设有关系模式R（A，B，C，D），其上的函数依赖集：F={A→C，C→A，B→AC，D→AC}（1）求F的最小等价依赖集F C。

有关模式分解题目重点放在三范式的分解上，包括分解算法及无损连接性的判断，这类题目的解题步骤一般分为三步：第一步、将已有的函数依赖集转化为最小的函数依赖集（我们已经练习很多，不再多讲）第二步、进行三范式分解（分解算法见书P192——算法5.3）第三步、判断分解是否具有无损连接性（分解算法见书P190——算法5.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}；试求最小依赖集，然后采用模式分解算法将其进行规范化处理，规范为三范式，并用算法说明该分解是否具有无损连接性。

1、求最小函数依赖集（1）利用分解规则，将F中所有函数依赖变成右边是单个属性的函数依赖，得：F1={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→B，CG→D，ACD→B，CE→A，CE→G }（2）去掉F1中多余的函数依赖：对AB→C，在F1-{ AB→C }中计算（AB）G +=AB∵C∈AB，∴AB→C不是多余的函数依赖，不能去掉对D→E，在F1-{ D→E }中计算（D）G +=DG∵E∈DG，∴D→E不是多余的函数依赖，不能去掉对D→G，在F1-{ D→G }中计算（D）G +=DE∵G∈DE，∴D→G不是多余的函数依赖，不能去掉对C→A，在F1-{ C→A }中计算（C）G +=C∵A∈C，∴C→A不是多余的函数依赖，不能去掉对BE→C，在F1-{ BE→C }中计算（BE）G +=BE∵C∈BE，∴BE→C不是多余的函数依赖，不能去掉对BC→D，在F1-{ BC→D }中计算（BC）G +=ABC∵D∈ABC，∴BC→D不是多余的函数依赖，不能去掉对CG→B，在F1-{ CG→B }中计算（CG）G +=ABCDEG∵B∈ABCDEG，∴CG→B是多余的函数依赖，可以去掉对CG→D，在F1-{ CG→D ，CG→B }中计算（CG）G +=ACG∵D∈ACG，∴CG→D不是多余的函数依赖，不能去掉对ACD→B，在F1-{ ACD→B，CG→B }中计算（ACD）G +=ACDEG∵B∈ACDEG，∴ACD→B不是多余的函数依赖，不能去掉对CE→A，在F1-{ CE→A，CG→B }中计算（CE）G +=ABCDEG∵A∈ABCDEG，∴CE→A是多余的函数依赖，可以去掉对CE→G，在F1-{ CE→G ，CG→B ，CE→A }中计算（CE）G +=ACE∵G∈ACE，∴CE→G不是多余的函数依赖，不能去掉经上述计算得：F2={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，ACD→B，CE→G }（3）去掉F2中函数依赖左部多余的属性：对AB→C，在F2中分别计算对于A，求（B）F +=B，∵C∈B，∴A不是多余的属性，不可以去掉对于B，求（A）F +=A，∵C∈A，∴B不是多余的属性，不可以去掉对BE→C，在F2中分别计算对于B，求（E）F +=E，∵C∈E，∴B不是多余的属性，不可以去掉对于E，求（B）F +=B，∵C∈B，∴E不是多余的属性，不可以去掉对BC→D，在F2中分别计算对于B，求（C）F +=AC，∵D∈AC，∴B不是多余的属性，不可以去掉对于C，求（B）F +=B，∵C∈B，∴C不是多余的属性，不可以去掉对CG→D，在F2中分别计算对于C，求（G）F +=G，∵D∈G=（G）+，∴C不是多余的属性，不可以去掉对于G，求（C）F +=AC，∵D∈AC=（C）+，∴C不是多余的属性，不可以去掉对ACD→B，在F2中分别计算对于A，求（CD）F +=ABCDEG，∵B∈ABCDEG =（CD）+，∴A是多余的属性，可以去掉F2={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，CD→B，CE→G }对CD→B，在F2中分别计算对于C，求（D）+=DEG，∵B∈DEG，∴C不是多余的属性，不可以去掉对于D，求（C）+=AC，∵B∈AC，∴D不是多余的属性，不可以去掉对CE→G，在F2中分别计算对于C，求（E）+=E，∵G∈E=（E）+，∴C不是多余的属性，不可以去掉对于E，求（C）+=AC，∵G∈AC=（C）+，∴E不是多余的属性，不可以去掉最终得最小的函数依赖集：F m={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，CD→B，CE→G }2、规范化处理分解为三范式（1）找在Fm中不出现的属性，没有；（2）在Fm中找X→A,XA=U，没有；（3）对Fm按具有相同左部的原则分解为：ρ={ABC, DEG, BCE, BCD, CDG,，CEG }分解为三范式后的结果为：R1（A，B，C）R2（D，E，G）R3（B，C，E）R4（B，C，D）R5（C，D，G）R6（C，E，G）3、判断该分解是否具有无损连接性首先构造初始表，如下图：由BC→D可以把B14、B34改为A4，由BC→E可以把B15、B45改为A5，由D→G可以把B16、B36、B46改为A6，此时表中第一行为A1、A2、A3、A4、A5、A6，所以此分解具有无损连接性。