第4章-模式设计理论习题.doc
《第4章-模式设计理论习题.doc》由会员分享，可在线阅读，更多相关《第4章-模式设计理论习题.doc（13页珍藏版）》请在冰点文库上搜索。
第4章模式设计理论
4.1基本知识点
4.1.1本章重要概念
（1）关系模式的冗余和异常问题。
（2）FD的定义、逻辑蕴涵、闭包、推理规则、与关键码的联系；平凡的FD；属性集
的闭包；推理规则的正确性和完备性；FD集的等价；最小依赖集。
（3）无损分解的定义、性质、测试；保持依赖集的分解。
（4）关系模式的范式：
1NF，2NF，3NF，BCNF。
分解成2NF、3NF模式集的算法。
（5）MVD、4NF、JD和5NF的定义。
4.1.2本章的重点篇幅
（1）教材中P148的例4.13。
（无损联接和保持FD的例子）
（2）教材中P149的例4.14和P150的例4.15。
（分解成2NF和3NF的例子）
4.2教材中习题4的解答
4.1名词解释
?
数据冗余：
指同一个数据在系统中多次重复出现。
?
函数依赖（FD）：
在关系模式R（U）中，FD是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t[X]=s[X]蕴涵t[Y]=s[Y]，那么称FDX→Y在关系模式R（U）中成立。
?
平凡的FD：
如果X→Y，且Y?
X，则称X→Y是一个“平凡的FD”。
?
FD集F的闭包F+：
被F逻辑蕴涵的函数依赖全体构成的集合，称为F的闭包，记为F+，即F+={X→Y|F?
X→Y}。
?
属性集X的闭包X+：
从已知的FD集F使用FD推理规则推出的所有满足X→A的属性A的集合，称为X的闭包，记为X+，即X+=｛属性A|X→A在F+中｝。
?
FD的逻辑蕴涵：
如果从已知的FD集F能推导出X→Y成立，那么称F逻辑蕴涵
X→Y，记为F?
X→Y。
?
FD集的等价：
对于两个FD集F和G，有F+=G+，则称F和G是等价的依赖集。
?
最小依赖集：
设F是属性集U上的FD集，Fmin是F的最小依赖集，那么Fmin应满足下列四个条件：
Fmin+=F+；每个FD的右边都是单属性；Fmin中没有冗余的FD；每个FD的左边没有冗余的属性。
?
无损分解：
设关系模式R，F是R上的FD集，ρ=｛R1，…，Rk｝是R的一个分解。
如果对R中满足F的每一关系r，都有r=?
πRi（r），那么称分解ρ相对F是“无损分解”。
?
泛关系假设：
指数据库中每一个关系都是全部属性构成的关系的投影，此时，由全部属性构成的关系称为泛关系。
?
chase过程：
根据已知FD集，对R分解成ρ构造的初始表格的值进行修改，使之符合FD集，这个过程称为chase过程。
?
保持FD：
设关系模式R，F是R上的FD分解，ρ=｛R1，…，Rk｝是R的一个分解，如果有∪πRi（F）?
F，那么称分解ρ保持FD集F。
?
1NF：
如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是1NF的模式。
?
2NF：
如果R是1NF的模式，且每个非主属性完全函数依赖于R的候选键，那么称R是2NF的模式。
?
3NF：
如果R是1NF的模式，且每个非主属性都不传递依赖于R的候选键，那么称R是3NF的模式。
?
BCNF：
如果R是1NF的模式，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。
?
4NF：
设D是关系模式R上成立的FD和MVD集合。
如果D中每个非平凡的MVDX→→Y的左部X都是R的超键，那么称R是4NF模式。
?
5NF：
如果关系模式R的每个JD均由R的候选键蕴涵，那么称R是5NF的模式。
?
多值依赖（MVD）：
设关系模式R（U），X和Y是U的子集，Z=U-X-Y。
对于R的关系r，若在r中存在元组（x，y1，z1）和（x，y2，z2），就也应存在元组（x，y2，z1）和（x，y1，z2），那么称MVDX→→Y在模式R上成立。
?
联接依赖（JD）：
设关系模式R（U），R1、…、Rn是U的子集，并满足U=R1∪…∪Rn，ρ=｛R1，…，Rn｝是R的一个分解。
如果对于R的每个关系r都有mρ（r）=r，那么称JD*（R1，…，Rn）在模式R上成立。
4.2用A1、A2和A3三条推理规则来证明4.2.3节中的定理4.2（推理规则A4～A8）。
（1）A4（合并性，union）：
｛X→Y，X→Z｝?
X→YZ。
证明：
已知X→Y，根据A2，两边用X扩充，得到X→XY。
从已知X→Z，根据A2两边用Y扩充，得到XY→YZ。
再根据A3，从X→XY和XY→YZ可得到X→YZ。
（2）A5（分解性，decomposition）：
｛X→Y，Z?
Y｝?
X→Z。
证明：
已知Z?
Y，可得Y→Z。
从Y→Z和已知X→Y，可得X→Z成立。
（3）A6（伪传递性）：
｛X→Y，WY→Z｝?
WX→Z。
证明：
已知X→Y，根据A2，两边用W扩充，得到WX→WY。
据WX→WY和已知的WY→Z，。
再根据A3，可得WX→Z成立。
（4）A7（复合性，composition）：
｛X→Y，W→Z｝?
XW→YZ。
证明：
已知X→Y，根据A2，两边用W扩充，得到WX→WY。
从已知W→Z，根据A2两边用Y扩充，得到WY→YZ。
再根据A3，从WX→WY和WY→YZ可得到XW→YZ成立。
（5）A8｛X→Y，W→Z｝?
X∪（W－Y）→YZ。
证明：
已知X→Y，根据A2，两边用（W-Y）扩充，得到X∪（W-Y）→Y∪（W-Y），而
Y∪（W-Y）=WY，因此有X∪（W-Y）→WY。
从已知W→Z，根据A2两边用Y扩充，得到WY→YZ。
再根据A3，从X∪（W-Y）→WY和WY→YZ可得到X∪（W－Y）→YZ。
4.3对函数依赖X→Y的定义加以扩充，X和Y可以为空属性集，用φ表示，那么X→φ，φ→Y，φ→φ的含义是什么？
答：
据推理规则的自反律可知，X?
ф和ф?
ф是平凡的FD，总是成立的。
而ф?
Y表示在当前关系中，任意两个元组的Y值相等，也就是当前关系的Y值都相等。
4.4设关系模式R有n个属性，在模式R上可能成立的函数依赖有多少个？
其中平凡的FD有多少个？
非平凡的FD有多少个？
解：
这个问题是排列组合问题。
FD形为X?
Y，从n个属性值中选择属性组成X共有C０ｎ+C１ｎ+…+Cｎｎ=2n种方法；同理，组成Y也有2n种方法。
因此组成X?
Y形式应该有2n?
2n=4n种方法。
即可能成立的FD有4n个。
平凡的FD要求Y?
X，组合X?
Y形式的选择有：
C０ｎ?
C００+C１ｎ?
（C０１+C１１）+C２ｎ?
（C０２＋C１２+C２２）+…+Cｎｎ（C０ｎ＋C１ｎ+…Cｎｎ）=C０ｎ?
20+C１ｎ?
21+C２ｎ?
22+…+Cｎｎ?
2n=（1+2）n=3n
即平凡的FD有3n。
因而非平凡的FD有4n－3n个。
4.5已知关系模式R（ABC），F是R上成立的FD集，F=｛A→B，B→C｝，试写出F的闭包F+。
解：
据已知条件和推理规则，可知F+有43个FD：
A?
ф AB?
ф AC?
ф ABC?
ф B?
ф C?
ф
A?
A AB?
A AC?
A ABC?
A B?
B C?
C
A?
B AB?
B AC?
B ABC?
B B?
C ф?
ф
A?
C AB?
C AC?
C ABC?
C B?
BC
A?
AB AB?
AB AC?
AB ABC?
AB BC?
ф
A?
AC AB?
AC AC?
AC ABC?
AC BC?
B
A?
BC AB?
BC AC?
BC ABC?
BC BC?
C
A?
ABC AB?
ABC AC?
ABC ABC?
ABC BC?
BC
4.6设关系模式R（ABCD），F是R上成立的FD集，F=｛A→B，C→B｝，则相对于F，试写出关系模式R的关键码。
并说明理由。
解：
R的关键码为ACD。
因为从已知的F，只能推出ACD→ABCD。
4.7设关系模式R（ABCD）上FD集为F，并且F=｛AB→C，C→D，D→A｝。
①试从F求出所有非平凡的FD。
②试求R的所有候选键。
③试求R的所有不是候选键的超键。
解：
①从已知的F可求出非平凡的FD有76个。
譬如，左边是C的FD有6个：
C→A，C→D，C→AD，C→AC，C→CD，C→ACD。
左边是D的FD有2个：
D→A，D→AD。
左边是AB的FD有12个：
AB→C，AB→D，AB→CD，AB→AC，……。
感兴趣的读者可以自行把这76个FD写齐。
②候选键是能函数决定所有属性的不含多余属性的属性集。
根据这个概念可求出R的候选键有三个：
AB、BC和BD。
③R的所有不是候选键的超键有四个：
ABC、ABD、BCD和ABCD。
4.8试举出反例说明下列规则不成立：
①｛A→B｝?
｛B→A｝
②｛AB→C，A→C｝?
｛B→C｝
③｛AB→C｝?
｛A→C｝
答：
设有三个关系：
r1 A B r2 A B C r3 A B C
1 1 2 1 2 1 2 3
2 1 2 2 2 1 3 4
3 2 3
（1）在关系r1中，A→B成立，但B→A不成立。
（2）在关系r2中，AB→C和A→C成立，但B→C不成立
（3）在关系r3中，AB→C成立，但A→C不成立。
4.9设关系模式R（ABCD），F是R上成立的FD集，F=｛A→B，B→C｝，
① 试写出属性集BD的闭包（BD）+。
② 试写出所有左部是B的函数依赖（即形为“B→？
”）。
解：
①从已知的F，可推出BD→BCD，所以（BD）+=BCD。
②由于B+=BC，因此左部是B的FD有四个：
B→φ，B→B，B→C，B→BC。
4.10设关系模式R（ABCDE）上FD集为F，并且F=｛A→BC，CD→E，B→D，E→A｝。
①试求R的候选键。
②试求B+的值。
解：
①R的候选键有四个：
A、E、CD和BC。
②B+=BD。
4.11设有关系模式R（ABC），其关系r如图4.1所示。
①试判断下列三个FD在关系r中是否成立？
A→B BC→A B→A
②根据关系r，你能断定哪些FD在关系模式R上不成立？
A B C
1 2 3
4 2 3
5 3 3
图4.1
解：
①在关系r中，A→B成立，BC→A不成立，B→A不成立。
②在关系r中，不成立的FD有:
B→A，C→A，C→B，C→AB，BC→A。
4.12设关系模式R（ABC）分解成ρ=｛AB，BC｝，如果R上的FD集F=｛A→B｝，那么这个分解是损失分解。
试举出R的一个关系r，不满足mρ（r）=r。
解：
这个反例r可以举测试时的初始表格：
A B C
AB a1 a2 b13
BC b21 a2 a3
πAB（r）?
πBC（r）有四个元组：
A B C
a1 a2 b13
a1 a2 a3
b21 a2 b13
b21 a2 a3
即mρ（r）≠r。
4.13试解释数据库“丢失信息”与“未丢失信息”两个概念。
“丢失信息”与“丢失数据”有什么区别？
答：
数据库中丢失信息是指r≠mρ（r），未丢失信息是指r=mρ（r）。
丢失信息是指不能辨别元组的真伪，而丢失数据是指丢失元组。
4.14设关系模式R（ABC），F是R上成立的FD集，F=｛A→C，B→C｝，试分别求F在模式AB和AC上的投影。
答：
πAB（F）=φ（即不存在非平凡的FD）
πAC（F）={A→C}
4.15设关系模式R（ABC），F是R上成立的FD集，F=｛B→A，C→A｝，ρ=｛AB，BC｝是R上的一个分解，那么分解ρ是否保持FD集F？
并说明理由。
答：
已知F={B→A，C→A}，而πAB（F）={B→A}，πBC（F）=φ，
显然，分解ρ丢失了FDC→A。
4.16设关系模式R（ABC），F是R上成立的FD集，F=｛B→C，C→A｝，那么分解ρ=｛AB，AC｝相对于F，是否无损分解和保持FD？
并说明理由。
答：
①已知F={B→C，C→A}，
而πAB（F）=φ，πAC（F）={C→A}
显然，这个分解丢失了FDB→C
②用测试过程可以知道，ρ相对于F是损失分解。
4.17设关系模式R（ABCDEG）上FD集为F，并且F=｛D→G，C→A，CD→E，A→B｝。
①求D+，C+，A+，（CD）+，（AD）+，（AC）+，（ACD）+。
②试求R的所有候选键。
③用ρ1=｛CDEG，ABC｝替换R，这个分解有什么冗余和异常现象？
④用ρ2=｛DG，AC，CDE，AB｝替换R，这个分解是无损分解吗？
⑤用ρ3=｛CDE，AC，DG，BCD｝替换R，先求F在ρ3的每个模式上的投影πRi（F），再判断分解ρ3保持FD吗？
解：
①D+=DG，C+=ABC，A+=AB，（CD）+=ABCDEG，（AD）+=ABDG，（AC）+=ABC，（ACD）+=ABCDEG。
②R的候选键只有一个：
CD。
③用ρ1=｛CDEG，ABC｝替换R，在模式CDEG中，有局部依赖CD→G，此时在关系中，一个D值只有一个G值，但当这个D值与10个C值对应时，就要出现10个元组，则G值就要重复10次。
在模式ABC中，有传递依赖（C→A和A→B），此时在关系中，一个A值只有一个B值，但当这个A值与10个C值对应时，就要出现10个元组，则B值就要重复10次。
④用ρ2=｛DG，AC，CDE，AB｝替换R，据chase过程可知，相对于F，R分解成ρ是无损分解。
⑤用ρ3=｛CDE，AC，DG，BCD｝替换R，
则F在模式CDE上的投影为｛CD→E｝，F在模式AC上的投影为｛C→A｝，
F在模式DG上的投影为｛D→G｝，F在模式BCD上的投影为｛C→B｝，
显然从这四个投影集中的FD推不出原来F中的A→B，因此分解ρ3不保持FD集。
4.18设关系模式R（ABCD），F是R上成立的FD集，F=｛A→B，B→C，A→D，D→C｝，ρ=｛AB，AC，BD｝是R的一个分解。
① 相对于F，ρ是无损分解吗？
为什么？
② 试求F在ρ的每个模式上的投影。
③ ρ保持F吗？
为什么？
答：
①用测试过程可以知道，ρ相对于F是损失分解。
②πAB（F）={A→B}，πAC（F）={A→C}，πBD（F）=φ。
③显然，分解ρ不保持FD集F，丢失了B→C、A→D和D→C等三个FD。
4.19设关系模式R（ABCD），R上的FD集F=｛A→C，D→C，BD→A｝，试说明ρ=｛AB，ACD，BCD｝相对于F是损失分解的理由。
答：
据已知的F集，不可能把初始表格修改为有一个全a行的表格，因此ρ相对于F是损失分解。
4.20设关系模式R（ABCD）上FD集为F，并且F=｛A→B，B→C，D→B｝。
①R分解成ρ=｛ACD，BD｝，试求F在ACD和BD上的投影。
②ACD和BD是BCNF吗？
如不是，试分解成BCNF。
解：
①F在模式ACD上的投影为｛A→C，D→C｝，F在模式BD上的投影为｛D→B｝。
②由于模式ACD的关键码是AD，因此显然模式ACD不是BCNF。
模式ACD应分解成｛AC，AD｝或｛CD，AD｝。
但是这个分解不保持FD，丢失了FDD→C或A→C。
另外，模式BD已是BCNF。
4.21设关系模式R（ABCD），ρ=｛AB，BC，CD｝是R的一个分解。
设F1=｛A→B，B→C｝，F2=｛B→C，C→D｝。
①如果F1是R上的FD集，此时ρ是否无损分解？
若不是，试举出反例。
②如果F2是R上的FD集呢？
解：
①据chase过程可知，相对于F1，R分解成ρ是损失分解。
据构造初始表的规则，这个反例可以是下面的表格：
r A B C D
1 1 0 0
0 1 1 0
0 0 1 1
对于这个r而言，显然r≠mρ（r）。
②据chase过程可知，相对于F2，R分解成ρ是无损分解。
4.22设关系模式R（ABCD），F是R上成立的FD集，F=｛AB→CD，A→D｝。
① 试说明R不是2NF模式的理由。
② 试把R分解成2NF模式集。
答：
①从已知FD集F，可知R的候选键是AB。
另外，AB→D是一个局部依赖，因此R不是2NF模式。
②此时R应分解成ρ={AD，ABC}，ρ是2NF模式集。
4.23设关系模式R（ABC），F是R上成立的FD集，F=｛C→B，B→A｝。
① 试说明R不是3NF模式的理由。
② 试把R分解成3NF模式集。
答：
①从已知FD集F，可知R的候选键是C。
从C→B和B→A，可知C→A是一个传递依赖，因此R不是3NF模式。
②此时R应分解成ρ={CB，BA}，ρ是3NF模式集。
4.24设有关系模式R（职工编号，日期，日营业额，部门名，部门经理），该模式统计商店里每个职工的日营业额，以及职工所在的部门和经理信息。
如果规定：
每个职工每天只有一个营业额；每个职工只在一个部门工作；每个部门只有一个经理。
试回答下列问题：
（1）根据上述规定，写出模式R的基本FD和关键码；
（2）说明R不是2NF的理由，并把R分解成2NF模式集；
（3）进而分解成3NF模式集。
解：
（1）基本的FD有三个：
（职工编号，日期）→日营业额
职工编号→部门名
部门名→部门经理
R的关键码为（职工编号，日期）。
（2）R中有两个这样的FD：
（职工编号，日期）→（部门名，部门经理）
职工编号→（部门名，部门经理）
可见前一个FD是局部依赖，所以R不是2NF模式。
R应分解成R1（职工编号，部门名，部门经理）
R2（职工编号，日期，日营业额）
此处，R1和R2都是2NF模式。
（3）R2已是3NF模式。
在R1中，存在两个FD：
职工编号→部门名
部门名→部门经理
因此，“职工编号→部门经理”是一个传递依赖，R1不是3NF模式。
R1应分解成R11（职工编号，部门名）
R12（部门名，部门经理）
这样，ρ={R11，R12，R2}是一个3NF模式集。
4.25设有关系模式
R（运动员编号，比赛项目，成绩，比赛类别，比赛主管）
存储运动员比赛成绩及比赛类别、主管等信息。
如果规定：
每个运动员每参加一个比赛项目，只有一个成绩；每个比赛项目只属于一个比赛类别；每个比赛类别只有一个比赛主管。
试回答下列问题：
（1）根据上述规定，写出模式R的基本FD和关键码；
（2）说明R不是2NF的理由，并把R分解成2NF模式集；
（3）进而分解成3NF模式集。
解：
（1）基本的FD有三个：
（运动员编号，比赛项目）→成绩
比赛项目→比赛类别
比赛类别→比赛主管
R的关键码为（运动员编号，比赛项目）。
（2）R中有两个这样的FD：
（运动员编号，比赛项目）→（比赛类别，比赛主管）
比赛项目→（比赛类别，比赛主管）
可见前一个FD是局部依赖，所以R不是2NF模式。
R应分解成R1（比赛项目，比赛类别，比赛主管）
R2（运动员编号，比赛项目，成绩）
这里，R1和R2都是2NF模式。
（3）R2已是3NF模式。
在R1中，存在两个FD：
比赛项目→比赛类别
比赛类别→比赛主管
因此，“比赛项目→比赛主管”是一个传递依赖，R1不是3NF模式。
R1应分解成R11（比赛项目，比赛类别）
R12（比赛类别，比赛主管）
这样，ρ={R11，R12，R2}是一个3NF模式集。
4.26设关系模式R（ABCD），在R上有五个相应的FD集及分解：
（1）F={B→C，D→A}，ρ={BC，AD}
（2）F={AB→C，C→A，C→D}，ρ={ACD，BC}
（3）F={A→BC，C→AD}，ρ={ABC，AD}
（4）F={A→B，B→C，C→D}，ρ={AB，ACD}
（5）F={A→B，B→C，C→D}，ρ={AB，AD，CD}
试对上述五种情况分别回答下列问题：
①确定R的关键码。
②是否无损分解？
③是否保持FD集？
④确定ρ中每一模式的范式级别。
解：
（1）①R的关键码为BD。
②ρ不是无损分解。
③ρ保持FD集F。
④ρ中每一模式已达到BCNF级别。
（2）①R有两个关键码：
AB和BC。
②ρ是无损分解。
③因为πACD（F）={C→A，C→D}，πBC（F）=φ（没有非平凡的FD），所以ρ不保持FD，丢失了AB→C。
④ρ中两模式均已达到BCNF级别。
（3）①R有两个关键码：
A和C
②ρ是无损分解。
③因为πABC（F）={A→BC，C→A}，πAD（F）={A→D}，所以ρ保持FD。
④在模式ABC中，关键码是A或BC，属性全是主属性，但有传递依赖（A→BC，BC→A）。
因此模式ABC是3NF，但不是BCNF。
而模式AD显然已是BCNF。
（4）①R的关键码为A。
②ρ是无损分解。
③因为πAB（F）={A→B}，πACD（F）={A→C，C→D}，从这两个依赖集推不出原来的B→C，因此ρ不保持FD，丢失了B→C。
④模式AB是BCNF，模式ACD不是3NF，只达到2NF级别。
（5）①R的关键码为A。
②ρ不是无损分解。
③因为πAB（F）={A→B}，πAD（F）={A→D}，πCD（F）={C→D}，从这三个依赖集推不出原来的B→C，因此ρ不保持FD，丢失了B→C。
④ρ中每个模式均是BCNF级别。
4.27设有关系模式R（ABC），其关系r如图4.2所示。
试判断下列FD和MVD在关系r中是否成立？
①A→B ②A→→B ③BC→A ④BC→→A
⑤B→C ⑥B→→C
A B C
1 2 3
4 2 3
5 3 3
5 3 4
图4.2
解：
①A→B在r中成立， ②A→→B在r中成立
③BC→A在r中不成立 ④BC→→A在r中成立
⑤B→C在r中不成立 ⑥B→→C在r中成立
4.28设有关系模式R（ABCDE），现有R的七个关系，如图4.3所示。
试判断FDBC→D和MVDBC→→D分别在这些关系中是否成立？
A B C D E A B C D E A B C D E
（空关系） a 2 3 4 5 a 2 3 4 5
2 a 3 5 5 2 a 3 5 5
a 2 3 4 6
（a）关系r1 （a）关系r2 （a）关系r3
A B C D E A B C D E A B C D E
a 2 3 4 5 a 2 3 4 5 a 2 3 4 5
2 a 3 4 5 2 a 3 7 5 2 a 3 4 5
a 2 3 6 5 a 2 3 4 6 a 2 3 6 5
a 2 3 6 6
（a）关系r4 （a）关系r5 （a）关系r6
A B C D E
a 2 3 4 5
a 2 3 6 5
a 2 3 6 6
升级会员 