第五章--关系数据理论

第五章关系数据理论习题1．理解并给出下列术语的定义：函数依赖、部分函数依赖、完全函数依赖、传递依赖、候选码、主码、外码、全码（All-key）、1NF、2NF、3NF、BCNF、多值依赖、4NF。2．联立一个关于系、学生、班级、学会等诸信息的关系数据库。描述学生的属性有：学号、姓名、出生年月、系名、班号、宿舍区。描述班级的属性有：班号、专业名、系名、人数、入校年份。描述系的属性有：系名、系号、办公室地点、人数。描述学会的属性有：学会名、成立年份、地点、人数。有关语义如下：一个系有若干学生，每个专业每年只招一个班，每个班有若干学生。一个系的学生住在同一宿舍区。每个学生可参加若干学会，每个学会有若干学生。学生参加某学会有一个入会年份。请给出关系模式，写出每个关系模式的极小函数依赖集，指出是否存在传递函数依赖，对于函数依赖左部是多属性的情况讨论函数依赖是完全函数依赖，还是部分函数依赖。指出各关系的候选码、外部码，有没有全码存在？3．试由Armstrong公理系统推导下面三条推理规则：（1）合并规则：若XZ，XY，则有XYZ（2）伪传递规则：由XY，WYZ，有XWZ（3）分解规则：XY，ZY，有XZ4．关于多值依赖的另一种定义试：给定一个关系模式R（X，Y，Z），其中X，Y，Z可以是属性或属性组合。设xX，yY，zZ，xy在R中的像集伪：{.|..}xzYrYrXxrZzrR定义R（X，Y，Z）当且仅当xzxzYY对于每一组（x，z，z）都成立，则Y对X多值依赖，记作XY。这里，允许Z为空集，在Z为空集时，称为平凡的多值依赖。请证明这里的定义和《概论》5。2。7节中定义5。9是等价的。5．试举出3个多值依赖的实例。*6．试证明《概论上》给出的关于FD和MVD公理系统的A4，A6和A8。*7．设关系模式为R（U，F），X，Y为属性集，X，YU。证明：（1）FXX（2）()FFFXX（3）若XY则FFXY（4）FUU*8．设关系模式R（U，F），若，则FXX称X相对于F是饱和的。定义饱和集{|}FFXXX，试证明{|}FFXXU。9．《概论》上图5。12表示一个公司各部门的层次结构，重画如下。部门电话办公室生产科研项目工资史职务职工对每个部门，数据库中包含部门号（唯一的）D＃、预算费（BUDGET）以及此部门领导人员的职工号E＃（唯一的）信息。对每一个部门，还存有关于此部门的全部职工、生产与科研项目以及办公室的信息。职工信息包括：职工号、他所参与的生产与科研项目号（J＃）、他所在办公室的电话号码（PHONE＃）。生产科研项目包括：项目号（唯一的）、预算费。办公室信息包含办公室房间号（唯一的）、面积。对每个职工，数据库中有他曾担任过的职务以及担任某一职务时的工资历史。对每个办公室包含此办公室中全部电话号码的信息。请给出你认为合理的数据依赖，把这个层次结构转换称一组规范化的关系。提示：此题可分步完成，第一步先转换成一组1NF的关系，然后逐步转换为2NF，3NF，BCNF。10．在一个订货系统的数据库中，存有顾客、货物和订货单的信息。每个顾客包含顾客号CUST＃（唯一的）、收货地址ADDRESS、订货日期DATE、订货细则LINE＃（每个订货单有若干条），每条订货细则内容为货物号ITEM以及订货数量QTYORD。每种货物包含货物号ITEM＃（唯一的）、制造厂商PLANT＃、每个厂商的实际存货量QTYOH、规定的最低存货量DANGER和货物描述DESCN。由于处理上的要求，每个订货单ORD＃的每一订货细则LINE＃中还应有一个未发货量QTYOUT（此值初始时为订货数量，随着发货将减为零）。为这些数据设计一个数据库，如第9题那样，首先给出合理的数据依赖。11．设在第10题中实际上只有很少量的顾客（例如1％），却有多个发货地址，由于这些少数的而又不能忽视的情形使得不能按一般的方式来处理问题。你能发现第10题答案中的问题吗？能设法改进吗？12．下面的结论哪些是正确的，哪些是错误的？对于错误的结论请给出理由或给出一个反例说明之。（1）任何一个二目关系都是属于3NF的。（2）任何一个二目关系都是属于BCNF的。（3）任何一个二目关系都是属于4NF的。（4）当且仅当函数依赖A→B在R上成立，关系R（A，B，C）等于其投影R1(A，B)和R2(A，C)的连接。（5）若R。A→R。B，R。B→R。C，则R。A→R。C（6）若R。A→R。B，R。A→R。C，则R。A→R。(B，C)（7）若R。B→R。A，R。C→R。A，则R。(B，C)→R。A（8）若R。(B，C)→R。A，则R。B→R。A，R。C→R。A参考答案1．答：函数依赖：设R(U)是一个关系模式，U和R的属性集合，X和Y是U的子集。对于R(U)的任意一个可能的关系r，如果r中不存在两个元组，它们在X上的属性值相同，而在Y上的属性值不同，则称”X函数确定Y”或”Y函数依赖于X”，记作XY。答：完全函数依赖、部分函数依赖：在R(U)中，如果XY，并且对于X的任何一个真子集X`，都有'XY则称Y对X完全函数依赖，记作：FXY若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：PXY传递依赖：在R(U)K，如果XY，（YX），YX，YZ，则称Z对X传递函数依赖。候选码、主码：设K为R﹤U，F﹥中的属性或属性组合，若FKU则K为R的候选码（Candidatekey）。若候选码多于一个，则选定其中的一个为主码（Primarykey）。答：外码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreignkey），也称外码。全码：整个属性组是码，称为全码（AII-Key）。答：INF：如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈INF。答：2NF：若关系模式R∈INF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。3NF：关系模式R﹤U，F﹥中若不存在这样的码X，属性组Y及非主属性Z（ZY）使得XY(YX)，YZ，成立，则称R﹤U，F﹥∈3NFBCNF：关系模式R﹤U，F﹥∈3NF。若XY且YX时X必含有码，则R﹤U，F﹥∈BCNF。答：多值依赖：设R(U)是属性集U上的一个关系模式。X，Y，Z是U的子集，并且Z=U-X-Y。关系模式R(U)中多值依赖XY成立，当且仅当对R（U）的任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于X值而与Z值无关。4NF：关系模式R﹤U，F﹥∈1NF，如果对于R的每个非平凡多值依赖XY(YX)，X都含有码，则称R﹤U，F﹥∈4NF。2．答：关系模式：学生S(S＃，SN。SB，DN，C＃，SA)班级C(C＃，CS，DN，CNUM，CDATE)系D(D＃，DN，DA，DNUM)学会P（PN，DATEI，PA，DATE2）学生-学会SP(S＃，PN，DATE2)其中，S＃-学号，SN-姓名，SB-出生年月，SA-宿舍区C＃-班号，CS-专业名，CNUM-班级人数，CDATE-入校年份D＃-系号，DN-系名DA系办公室地点，DNUM-系人数PN-学会名，DATEI-成立年月，PA-地点，PNUM-学会人数，DATE2-入会年份每个关系模式的极小函数依赖集：S：S＃→SN，S＃→SB，S＃→C＃，C＃→DN，DN→SAC：C＃→CS，C＃→CNUM，C＃→CDATE，CS→DN，(CS，CDATE)→C＃/﹡因为每一个专业每年只招一个班﹡/D：D＃→DN，DN→D＃，D＃→DA，D＃→DNUM/﹡按照实际情况，系名和系号是一一对应的﹡/P：PN→DATEI，PN→PA，PN→PNUMSP：(S＃，PN)→DATE2S中存在传递函数依赖：S＃→DN，S＃→SA，C＃→SA/﹡因为S＃→C＃，C＃→DN，DN→SA﹡/C中存在传递函数依赖：C＃→DN/﹡因为C＃→CS＃，CS→DN﹡/(S＃，PN)→DATE2和（CS，CDATE）→C＃均为SP中的函数依赖，是完全函数依赖。关系候选码外部码全码SS#C#，DN无CC#，(CS，CDATE)DN无DD#和DN无无PPN无无SP(S#，PN)S#PN无3．证明：（1）已知X→Z，由增广律知XY→YZ，又因为X→Y，可得XX→XY→YZ，最后根据传递律得X→YZ。（2）已知X→Y，根据增广律得XW→WY，因为WY→Z，所以XW→WY→Z，通过传递律可知XW→Z。（3）已知Z⊆Y，根据自反律知Y→Z，又因为X→Y，所以由传递律可得X→Z。4．证明：设Yxz＝Yxz’对于每一组（x，z，z’）都成立，现证其能推出定义5。9得条件：设s，t是关系r中得两个元组，s[X]=t[X]，由新定义得条件可知对于每一个z值，都对应相同一组y值。这样一来，对相同得x值，交换y值后所得的元组仍然属于关系r，即定义5。9的条件成立；如果定义5。9的条件成立，则对相同的x值，交换y值后所得的元组仍然属于关系r，由于任意性及其对称性，可知每个z值对应相同的一组y值，所以Yxz=Yxz’对于每一组（x，z，z’）都成立。综上可知，新定义和定义5。9的条件是等价的，所以新定义和定义5。9是等价的。5．答：（1）关系模式MSC(M，S，C)中，M表示专业，S表示学生，C表示该专业的必修课。假设每个专业有多个学生，有一组必修课。设同专业内所有学生选修的必修课相同，实例关系如下。按照语义对于M的每一值Mi，S有一完整的集合与之对应而不问C取何值，所以M→→S。由于C与S的完全对称性必然有M→→C成立。MSCM1S1C1M1S1C2M1S2C1M1S2C2………………（2）关系模式ISA(I，S，A)中，I表示学生兴趣小组，S表示学生，A表示某兴趣小组的活动项目。假设每个兴趣小组有多个学生，有若干活动项目。每个学生必须参加所在兴趣小组的所有活动项目，每个活动项目要求该兴趣小组的所有学生参加。按照语义I→→S，I→→A成立。（3）关系模式RDP(R，D，P)中，R表示医院的病房，D表示责任医务人员，P表示病人。假设每个病房住有多个病人，有多个责任医务人员负责医治和护理该病房的所有病人。按照语义有R→→D，R→→P成立。6．证明：A4：若XY，VWU，则XWYV设Z＝U-X-Y已知XY，设r是R上的一个关系，s、t∈r，且t[X]=s[X]，则存在元组p、q∈r，使p[X]=t[X]，p[Z]=s[Z]，q[Y]=s[Y]，q[Z]=t[Z]。设t[XW]=s[XW]，我们以上构造的元组p和q，是某部分属性在s和t上翻转而成，所以p[W]=q[W]，可知p[XW]=q[XW]，同理p[YV]=t[YV]（由VW知t[V]=s[V]），q[YV]=s[YV]，p[U-YV-YW]=s[U-YV-YW](因为UYVYWZ)，q[U-YV-YW]=t[U-YV-YW]。所以，XWYV。A6：XY，YZ，则XZY由YZ容易证得YZY。设R1＝U-X-Y，R2=U-Y-Z，R3=U-X-Z+Y。已知XY，设r是R上的任一关系s、t∈r，且t[X]=s[X]，则存在元组p、q∈r，使p[X]=q[X]=t[X]，而p[Y]=t[Y]，p[R1]=s[R1]，q[Y]=s[Y]，q[R1]=t[R1]。对元组t、p，已知t[Y]=p[Y]，t[X]=p[X]，由YZY知：存在元组m∈r，使m[Z-Y]=p[Z-Y]。因为（Z-Y）R1，又p[R1]=s[R1]，所以，m[Z-Y]=s[Z-Y]。因为元组p和s在除属性Y之外的属性上值相等，所以m[R2]=t[R2]，另外元组m由元组t和p交换某些属性上的值而产生的，而t和p在属性X上值相等，显然m[X]=t[X]，所以m[U-(Z-Y)]=t[U-(Z-Y)]，即m[R3]=t[R3]。对元组s、q，同理可知s[Y]=q[Y]，存在元组n，使n[Z