自考数据库系统原理第三章关系模式设计理论课后习题答案.doc

自考数据库系统原理 第三章 关系模式设计理论 课后习题答案
2009-08-24 23:08
3.1　名词解释

(1) 函数依赖：FD(function dependency)，设有关系模式R(U)，X，Y是U的子集， r是R的任一具体关系，如果对r的任意两个元组t1,t2,由t1[X]=t2[X]导致t1[Y]=t2[Y], 则称X函数决定Y,或Y函数依赖于X，记为X→Y。X→Y为模式R的一个函数依赖。
(2) 平凡的函数依赖：对于FD X→Y，如果Y∈X 那么称X→Y 是一个“平凡的函数依赖”，否则称为“非平凡的FD”。
(3) 函数依赖集F的闭包F+: 被逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包(closure),记为F+。
(5) 函数依赖的逻辑蕴涵：设F是关系模式R的一个函数依赖集，X，Y是R的属性子集， 如果从F中的函数依赖能够推出X→Y，则称F逻辑蕴涵X→Y,记为F|=X→Y。
(6) 依赖集的覆盖和等价：关系模式R(U)上的两个函数依赖集F和G，如果满足F+=G+，则称F和G是等价的。 如果F和G等价，则可称F覆盖G或G覆盖F。
(7) 最小依赖集：如果函数集合F满足以下三个条件：(1)F中每个函数依赖的右部都是单属性； (2)F中的任一函数依赖X→A，其F-{X→A}与F是不等价的；(3)F中的任一函数依赖X→A，Z为X的子集，（F-{X→A}）∪{Z→A}与F不等价。则称F为最小函数依赖集合，记为Fmin。
(8) 无损联接：设R是一关系模式，分解成关系模式ρ={R1,R2...,Rk},F是R上的一个函数依赖集。 如果对R中满足F的每一个关系r都有r=πR1(r)πR2(r)...πRk(r)则称这个分解相对于F是"无损联接分解"。
(10) 保持依赖集:所谓保持依赖就是指关系模式的函数依赖集在分解后仍在数据库中保持不变， 即关系模式R到ρ={R1,R2,...,Rk}的分解，使函数依赖集F被F这些Ri上的投影蕴涵。
(11) 1NF：第一范式。如果关系模式R的所有属性的值域中每一个值都是不可再分解的值, 则称R是属于第一范式模式。如果某个数据库模式都是第一范式的，则称该数据库存模式属于第一范式的数据库模式。 第一范式的模式要求属性值不可再分裂成更小部分，即属性项不能是属性组合和组属性组成。
(12) 2NF：第二范式。如果关系模式R为第一范式，并且R中每一个非主属性完全函数依赖于R的某个候选键， 则称是第二范式模式；如果某个数据库模式中每个关系模式都是第二范式的，则称该数据库模式属于第二范式的数据库模式。 (注：如果A是关系模式R的候选键的一个属性，则称A是R的主属性，否则称A是R的非主属性。)
(13) 3NF：第三范式。如果关系模式R是第二范式，且每个非主属性都不传递依赖于R的候选键， 则称R是第三范式的模式。如果某个数据库模式中的每个关系模式都是第三范式，则称为3NF的数据库模式。
(14) BCNF：BC范式。如果关系模式R是第一范式，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。
(17) 4NF：第四范式。设R是一个关系模式，D是R上的多值依赖集合。如果D中成立非平凡多值依赖X→→Y时， X必是R的超键，那么称R是第四范式的模式。
3.4 对函数依赖X→Y的定义加以扩充，X和Y可以为空属性集，用φ表示， 那么X→φ，φ→Y，φ→φ的含义是什么?
根据函数依赖的定义，以上三个表达式的含义为：
(1)一个关系模式R(U)中，X，Y是U的子集，r是R的任一具体关系，如果对r的任意两个元组t1,t2, 由t1[X]=t2[X]必有t1[φ]=t2[φ]。即X→φ表示空属性函数依赖于X。这是任何关系中都存在的。
(2)φ→Y表示Y函数依赖于空属性。由此可知该关系中所有元组中Y属性的值均相同。
(3)φ→φ表示空属性函数依赖于空属性。这也是任何关系中都存在的。
3.6关系模式R有n个属性，在模式R上可能成立的函数依赖有多少个? 其中平凡的函数依赖有多少个?非平凡的函数依赖有多少个?
(要考虑所有可能的情况,数学排列组合问题。对于数据库本身而言，本题没多大意义）     所有属性相互依赖时，函数依赖最多。平凡的函数依赖：对于函数依赖X→Y，如果YX，那么称X→Y是一个“平凡的函数依赖”。
3.7已知关系模式R(ABC)，F={A→C，B→C},求F+。
   可以直接通过自反律、增广律、传递律加以推广：
F+={φ→φ，A→φ，B→φ，C→φ，A→C，B→C，AB→φ，AB→A，AB→B，AB→C，AB→BC，AB→AB，AB→ABC，BC→φ，BC→C，BC→B，BC→BC，AC→φ，AC→C，AC→A，AC→AC，ABC→φ，ABC→A，ABC→B，ABC→C，ABC→BC，ABC→AB，ABC→ABC}
4.6 试分析下列分解是否具有无损联接和保持函数依赖的特点：
(1)设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。

首先，检查是否具有无损联接特点：
第1种解法--算法4.2:

A
B
C
AB
a1
a2
b13
AC
a1
b22
a3

A
B
C
a1
a2
b13
a1
a2
a3

(1) 构造表
(2)根据A→B进行处理

结果第二行全是a行，因此分解是无损联接分解。

第2种解法:(定理4.8)
设 R1=AB，R2=AC
　　R1∩R2=A
　　R2- R1=B
　　∵A→B,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖
　　πR1（F1）={A→B，以及按自反率推出的一些函数依赖}
　　πR2（F1）={按自反率推出的一些函数依赖}
　　F1被πR1（F1）所蕴涵，∴所以该分解保持函数依赖。

(2)设R(ABC)，F2={A→C，B→C}在R上成立，ρ2={AB,AC}

首先，检查是否具有无损联接特点：
第1种解法（略）
第2种解法:(定理4.8)
设 R1=AB，R2=AC
　　R1∩R2=A
　　R2- R1=C
　　∵A→C,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖
πR1（F2）={按自反率推出的一些函数依赖}
πR2（F2）={A→C，以及按自反率推出的一些函数依赖}
∵F1中的B→C没有被蕴涵，所以该分解没有保持函数依赖。

(3)设R(ABC)，F3={A→B},在R上成立,ρ3={AB,BC}.

首先，检查是否具有无损联接特点：
第1种解法：

A
B
C
AB
a1
a2
b13
BC
b21
a2
a3

A
B
C
a1
a2
a3
a1
b22
a3

(1) 构造表
(2)根据A→B进行处理

没有一行全是a行。因此这个分解不具有无损联接特性。

　　第2种解法:(定理4.8)
   设 R1=AB，R2=BC
　　R1∩R2=B
　　R2- R1=C，R1- R2=A
　　∵B→C,B→A不在F3中 ∴该分解不具有无损联接特性。

然后，检查分解是否保持函数依赖
　　πR1（F3）={A→B，以及按自反率推出的一些函数依赖}
　　πR2（F3）={按自反率推出的一些函数依赖}
　　F1被πR1（F3）所蕴涵，所以该分解保持函数依赖。

(4)设R(ABC)，F4={A→B，B→C}在R上成立，ρ4={AC,BC}

首先，检查是否具有无损联接特点：
第1种解法（略）

　　第2种解法:(定理4.8)
   设 R1=AC，R2=BC
　　R1(AC)∩R2(BC)=C
　　R2- R1=B，R1- R2=A
　　∵C→B,C→A不在F4中 ∴该分解不具有无损联接特性。

然后，检查分解是否保持函数依赖
　　πR1（F2）={按自反率推出的一些函数依赖}
　　πR2（F2）={B→C，以及按自反率推出的一些函数依赖}
　　∵F1中的A→B没有被蕴涵，所以该分解没有保持函数依赖。

4.7 设R=ABCD,R上的函数依赖集F={A→B，B→C，A→D，D→C},R的一个分解ρ={AB,AC,AD},求:(1)F在ρ的每个模式上的投影。(2)ρ相对于F是无损联接分解吗?(3)ρ保持依赖吗?
(1)
πAB(F)={A→B，及按自反律所推导出的一些平凡函数依赖}
πAC(F)={A→C，及按自反律所推导出的一些平凡函数依赖}
πAD(F)={A→D，及按自反律所推导出的一些平凡函数依赖}
(2)

A
B
C
D
AB
a1
a2
b13
b14
AC
a1
b22
a3
b24
AD
a1
b32
b33
a4

A
B
C
D
a1
a2
a3
a4
a1
a2
a3
a4
a1
a2
a3
a4

(1) 构造表
(2)根据A→B，B→C，A→D，D→C进行处理

每一行都是a，ρ相对于F是无损联接分解。

(3)πAB(F)∪πAC(F)∪πAD(F)={A→B，A→C，A→D},
没有满足B→C，D→C函数依赖，
因此ρ相对于F的这个分解不保持函数依赖。

4.8 设R=ABCD,R上的F={A→C，D→C，BD→A}, 试证明ρ={AB,ACD,BCD}相对于F不是无损联接分解。
根据算法4.2

A
B
C
D
AB
a1
a2
b13
b14
ACD
a1
b22
a3
a4
BCD
b31
a2
a3
a4

A
B
C
D
a1
a2
a3
b14
a1
b22
a3
a4
b31
a2
a3
a4

(1) 构造表
(2)根据A→C，D→C，BD→A进行处理

没有一行都是a，所以，ρ相对于F不是无损联接分解。

4.9 设R=ABCD,R上的F={A→B,B→C，D→B}，把R分解成BCNF模式集。
(1)若首先把R分解成{ACD,BD}，试求F在这两个模式上的投影。
(2)ACD和BD是BCNF吗?如果不是，请进一步分解。

(1)πACD(F)={A→C}
　　πBD(F)={D→B}

(2)因为根据BCNF的定义，要求关系模式是第一范式，且每个属性都不传递依赖于R的侯选键。 BCD中（A，D）为候选键，可是（A,D)→A, A→C,所以它不是BCNF模式。
它可进一步分解为：{AC,DC},此时AC，DC均为BCNF模式。

BD是BCNF，因为R2(BD)是第一范式，且每个属性都不传递依赖于D(候选键)，所以它是BCNF模式。

4.10 设R=ABCD,ρ={AB,BC,CD}。F1={A→B，B→C}；F2={B→C，C→D}；
(1)如果F1是R上的函数依赖集，此时ρ是无损联接分解吗?若不是，试举出反例。
(2)如果F2是R上的函数依赖集呢?
(1)不是无损联接。可由算法4.2判断或由定理4.8判断。
根据算法4.2

A
B
C
D
AB
a1
a2
b13
b14
BC
b21
a2
a3
b24
CD
b31
b32
a3
a4

A
B
C
D
a1
a2
a3
b14
b21
a2
a3
b24
b31
b32
a3
a4

(1) 构造表
(2)根据A→B,B→C进行处理

结果没有出现一行全a的情况，所以它不是无损联接。举例如下：
设模式R的一关系r为{(a1b1c1d1),(a2b2c1d2)}
则有：r1=πAB(r)={(a1b1),(a2b2)}
　　　r2=πBC(r)={(b1c1),(b2c1)}
　　　r3=πCD(r)={(c1d1),(c1d2)}
令a=r1r2r3={ (a1b1c1d1),(a1b1c1d2),(a2b2c1d1),(a2b2c1d2)}
r≠a，所以ρ不是无损联接。

(2)如果F2是R上的函数依赖，则可以判断，ρ是无损联接。判断过程同上。

4.11 设关系模式R(S#,C#,GRADE,TNAME,TADDR),其属性分别表示学生学号、 选修课程的编号，成绩、任课教师地址等意义。如果规定，每个学生每学一门课只有一个成绩； 每门课只有一个教师任教；每个教师只有一个地址(此处不允许教师同名同姓)。
(1)试写出关系模式R基本的函数依赖和候选键。
(2)试把R分解成2NF模式集并说明理由。
(3)试把R分解成3NF模式集，并说明理由。

(1)F={(S#,C#)→GRADE，C#→TNAME，TNAME→TADDR}
侯选键是（S#,C#）。

(2)在模式R中，TNAME不完全依赖于键(S#，C#),因此需进行分解，可分解为下列两个关系。
SC={S#,C#,GRADE} C={C#,TNAME,TADDR}
分解后，SC中，GRADE完全依赖于侯选键(S#,C#),在C中，主属性是C#，TNAME、TADDR均完全依赖于C#。 因此，该分解符合2NF模式。

(3)3NF：若每个关系模式是2NF，则每个非主属性都不传递于R的候选键。
按上述已分好的两个模式，SC中已满足“每个非主属性都不传递于R的候选键”，已是3NF,而在C中， C#→TNAME，TNAME→TADDR，TADDR传递依赖于C#，因此还需分成两个模式：CT(C#,TNAME), T(TNAME,TADD)。
分解后，总共有SC={S#,C#,GRADE},CT(C#,TNAME), T(TNAME,TADD)三个模式。
该分解符合3NF模式。

4.12 图4.6表示一个公司各部门的层次结构，对每个部门，数据库中包含部门号 (唯一的)D#，预算费(BUDGET)以及此部门领导人员的职工号(唯一的)E#等信息。 对每一个部门，还存有部门的全部职工，生产科研项目以及办公室的信息。

职工信息包括：职工号，他所参加的生产科研项目号(J#)，他所在办公室的电话号(PHONE#)。
生产科研项目包含：项目号(唯一的)，预算费。
办公室信息包含：办公室号(唯一的)，面积。
对每个职工，数据库中有他曾担任过的职务以及担任某一职务时的工资历史。对每个办公室包含此办公室中全部电话号吗的信息。

请给出你认为合理的数据依赖，把这个层次结构转换成一组规范化的关系。
提示：此题可分步完成，先转换成一组1NF的关系，然后逐步转换成2NF，3NF，...。
先得到一个泛关系的模式如下:
D={D#,Manager_E#,Budget，E#,J#,Phone#,Business,Sa_History,Office#,Area}
D#:部门号, Manager_E#:部门领导人员的职工号, E#:职工号, J#:生产科研项目号, Phone#:办公室的电话号,Business:职工职务,Sa_History:工资历史,Office#:办公室号,Area:办公室面积
根据所给信息，给出下列数据依赖：
F={D#→Manager_E#，E#→Office#,(E#,Business)→Sa_History,J#→Budget,E#→J#， Office#→Area,Office→D#,#Phone#→Office#}
（假设一个部门可能有多个办公室，有多个项目，一个办公室只属于一个部门，有多部电话， 一个员工只参加一个项目，一个项目可能属于多个部门）
只要保证每个属性值不可分割，以上范式即为1NF。候选键为（E#,Business，Phone#)

转换成2NF关系(消除局部依赖）：
Em_Dep(E#,D#,Manager_E#,Office#,Area,J#，Budget)
   对应 F={D#→Manager_E#，E#→Office#,J#→Budget,E#→J#，Office#→Area，Office→D#}
History(E#,Business,History)
   对应 F={(E#,Business)→Sa_History}
Phone(Phone#,Office#)
   对应 F={Phone#→Office#}

转换成3NF关系(消除非主属性对侯选键的传递依赖）：
Department(D#,Manager_E#)
Office(Office#,Area，D#)
Emproee(E#,J#,Office#)
History(E#,Business,History)
Phone(Phone#,Office#)
Project(J#,Budget)
注意：由于对题意理解的不同，可能答案不唯一。

4.13 设关系模式R(ABC)上有一个多值依赖A→→B。 如果已知R的当前关系中存在三组(ab1c1)、(ab2c2)和(ab3c3),那么这个关系中至少还应存在哪些元组?
   从多值依赖的定义可以得出，至少应存在下列元组：
(ab1c2)、(ab1c3)、(ab2c1)、(ab2c3)、(ab3c1)、(ab3c2)