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

自考数据库系统原理第三章关系模式设计理论课后习题答案2009-08-2423:083.1名词解释(1)函数依赖：FD(functiondependency)，设有关系模式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)平凡的函数依赖：对于FDX→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:ABCABa1a2b13ACa1b22a3ABCa1a2b13a1a2a3(1)构造表(2)根据A→B进行处理结果第二行全是a行，因此分解是无损联接分解。第2种解法:(定理4.8)设R1=AB，R2=ACR1∩R2=AR2-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=ACR1∩R2=AR2-R1=C∵A→C,∴该分解是无损联接分解。然后，检查分解是否保持函数依赖πR1（F2）={按自反率推出的一些函数依赖}πR2（F2）={A→C，以及按自反率推出的一些函数依赖}∵F1中的B→C没有被蕴涵，所以该分解没有保持函数依赖。(3)设R(ABC)，F3={A→B},在R上成立,ρ3={AB,BC}.首先，检查是否具有无损联接特点：第1种解法：ABCABa1a2b13BCb21a2a3ABCa1a2a3a1b22a3(1)构造表(2)根据A→B进行处理没有一行全是a行。因此这个分解不具有无损联接特性。第2种解法:(定理4.8)设R1=AB，R2=BCR1∩R2=BR2-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=BCR1(AC)∩R2(BC)=CR2-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)ABCDABa1a2b13b14ACa1b22a3b24ADa1b32b33a4ABCDa1a2a3a4a1a2a3a4a1a2a3a4(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.2ABCDABa1a2b13b14ACDa1b22a3a4BCDb31a2a3a4ABCDa1a2a3b14a1b22a3a4b31a2a3a4(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.2ABCDABa1a2b13b14BCb21a2a3b24CDb31b32a3a4ABCDa1a2a3b14b21a2a3b24b31b32a3a4(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)