数据库原理第16讲

AnIntroductiontoDatabaseSystem数据库原理第六章关系数据理论(习题课)AnIntroductiontoDatabaseSystem模式分解中常用概念对于关系模式R(U,F)及其上的一个分解＝{R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn)}•属性保持若R中的每一个属性都应该至少出现在分解中的一个关系模式Ri中，即∪Ui＝U，则这种分解我们称为属性保持。AnIntroductiontoDatabaseSystem模式分解中常用概念•分解的无损连接性•保持函数依赖令F‘=F1∪F2∪…∪Fn，若F’+=F+,则我们称这种分解为保持函数依赖的分解。AnIntroductiontoDatabaseSystem范式举例1.R(X,Y,Z)F={XY→Z}2.R(X,Y,Z)F={Y→Z,XZ→Y}3.R(X,Y,Z)F={Y→Z,Y→X,X→YZ}4.R(X,Y,Z)F={X→Y,X→Z}5.R(W,X,Y,Z)F={X→Z,WX→Y}参考答案：BCNF、3NF、BCNF、BCNF、1NFAnIntroductiontoDatabaseSystem范式举例（续）•考虑已出版书的关系：BOOK(Book_title,Authorname,Book_type,Listprice,Author_affil,Publisher)Author_affil是指作者的联盟。假设存在以下依赖：Book_title→Publisher,Booke_typeBook_type→ListpriceAuthorname→Athor_affil•关系属于第几范式？解释你的回答。•运用规范化直到不能再进一步分解关系为止。说明分解原因。AnIntroductiontoDatabaseSystem函数依赖集等价•考虑以下两个函数依赖集：F={A→C,AC→D,E→AD,E→H}和G={A→CD,E→AH}。检查它们是否等价。AnIntroductiontoDatabaseSystem求取候选码设有关系模式R(A,B,C,D,E),其上的函数依赖集F={A→BC,CD→E,B→D,E→A}①计算A+和B+②求R的所有候选码参考答案：ABCDE，BD候选码是A，BC，CD，EAnIntroductiontoDatabaseSystem•设有关系模式R(A,B,C,D,E),其上的函数依赖集F={AB→C,CD→E,DE→B}问AB是该关系的候选码吗？如果不是，那候选码是什么？请解释你的回答。求取候选码（续）AnIntroductiontoDatabaseSystem•设有关系模式R(A,B,C,D,E,F,G,H,I,J),其上的函数依赖集F={AB→C,A→DE,B→F,F→GH,D→IJ}问R的候选码是什么？将R先分解成2NF关系，然后再分解成3NF关系。求取候选码（续）AnIntroductiontoDatabaseSystem设有关系模式R(A,B,C,D),其上的函数依赖集F={A→C,C→A,B→AC,D→AC}①计算(AD)+②求F的最小函数依赖集Fm③求R的码④将R分解为满足3NF且保持函数依赖⑤将R分解为满足3NF并具有无损连接性和保持函数依赖⑥将R分解为满足BCNF且具有无损连接性AnIntroductiontoDatabaseSystem基本知识点需要了解的：什么是一个“不好”的数据库模式；什么是模式的更新异常；规范化理论的重要意义。需要牢固掌握的：关系的形式化定义；数据依赖的基本概念(函数依赖、平凡函数依赖、非平凡函数依赖、部分函数依赖、完全函数依赖、传递函数依赖、码、候选码、外码、多值依赖)；范式的概念；从1NF到4NF的定义；规范化的含义和作用。AnIntroductiontoDatabaseSystem基本知识点（续）需要举一反三的：四个范式的理解与应用，各个级别范式中存在的问题(插入异常、删除异常、数据冗余)和解决方法；能够根据应用语义，完整地写出关系模式的数据依赖集合，并能根据数据依赖分析某一个关系模式属于第几范式。难点：各个级别范式的关系及其证明。AnIntroductiontoDatabaseSystem1.理解并给出下列术语的定义：函数依赖、部分函数依赖、完全函数依赖、传递依赖、候选码、主码、外码、全码、1NF、2NF、3NF、BCNF、多值依赖、4NF。答：函数依赖：设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作X→Y。AnIntroductiontoDatabaseSystem解析：⑴函数依赖是最基本的、也是最重要的一种数据依赖。⑵函数依赖是属性之间的一种联系，体现在属性值是否相等。由定义可知，若X→Y，则r中任意两个元组，如果它们在X上的属性值相等，那么在Y上的属性值也一定相等。⑶要从属性间实际存在的语义来确定它们之间的函数依赖。⑷函数依赖不是指关系模式R在某个时刻的关系(值)满足的约束条件，而是指R在任何时刻的一切关系均要满足的约束条件。AnIntroductiontoDatabaseSystem完全函数依赖、部分函数依赖：在关系模式R(U)中，若X→Y，且对于X的任何一个真子集X’，都有X’↛Y,则称Y完全函数依赖于X，记作XｆY。若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XPY。传递函数依赖：在关系模式R(U)中，若X→Y，Y→Z，且Y⊈X，Y↛X，则称Z传递函数依赖于X，记作XtZ。AnIntroductiontoDatabaseSystem候选码、主码：设K为关系模式RU,F中的属性或属性组合，若KｆU，则K称为R的一个侯选码。若候选码多于一个，则选定其中的一个为主码。外码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码。全码：整个属性组是码，称为全码。AnIntroductiontoDatabaseSystem1NF：若关系模式R的所有属性都是不可分的基本数据项，则R1NF。1NF是对关系模式的最起码要求，不满足1NF的数据库模式不能称为关系数据库。1NF2NF3NFBCNF4NF。2NF：若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。3NF：关系模式R中若不存在这样的码X、属性组Y及非主属性Z(Z⊈Y),使得X→Y，Y↛X，Y→Z成立，则称R3NF。AnIntroductiontoDatabaseSystemBCNF：设关系模式R1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么RBCNF。多值依赖：设关系模式R(U)中，X、Y和ZU，且Z＝U－X－Y，多值依赖X→→Y成立当且仅当对R的任一关系r，r在(X,Z)上的每个值对应一组Y值，这组值仅决定于X值而与Z值无关。4NF：关系模式RU,F1NF，如果对于R的每个非平凡多值依赖X→→Y(YX)，X都含有候选码，则R4NF。AnIntroductiontoDatabaseSystem2.建立一个关于系、学生、班级、学会等诸信息的关系数据库。描述学生的属性有：学号、姓名、生日、系名、班号、宿舍区。描述班级的属性有：班号、专业名、系名、人数、入校年份。描述系的属性有：系号、系名、系办公室地点、人数。描述学会的属性有：学会名、成立年份、地点、人数。有关语义如下：一个系有若干专业，每个专业每年只招一个班，每个班有若干学生。一个系的学生住在同一宿舍区。每个学生可参加若干学会，每学会有若干学生。学生参加某学会有一个入会年份。请给出关系模式，写出每个关系模式的极小函数依赖集，指出是否存在传递函数依赖，对于函数依赖左部是多属性的情况讨论函数依赖是完全函数依赖，还是部分函数依赖。指出各关系的候选码、外部码，有没有全码存在？AnIntroductiontoDatabaseSystem答：关系模式有：学生S(S#,SN,SB,DN,C#,SA)班级C(C#,CS,DN,CNUM,CDATE)系D(D#,DN,DA,DNUM)学会P(PN,DATE1,PA,PNUM)学生–学会SP(S#,PN,DATE2)其中：S#为学号，SN为姓名，SB为生日，DN为系名，C#为班号，SA为宿舍区，CS为专业名，CNUM为班级为数，CDATE为入校年份，D#为系号，DA为系办公室地点，DNUM为系人数，PN为学会名，DATE1为学会成立年月，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#→DNUMP：PN→DATE1，PN→PA，PN→PNUMSP：(S#,PN)→DATE2S中存在传递函数依赖：S#→DN，S#→SA，C#→SAC中存在传递函数依赖：C#→DN(CS,CDATE)→C#和(S#,PN)→DATE2都是完全函数依赖。AnIntroductiontoDatabaseSystem学生S(S#,SN,SB,DN,C#,SA)班级C(C#,CS,DN,CNUM,CDATE)系D(D#,DN,DA,DNUM)学会P(PN,DATE1,PA,PNUM)学生–学会SP(S#,PN,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#→DNUMP：PN→DATE1，PN→PA，PN→PNUMSP：(S#,PN)→DATE2关系候选码外部码全码SS#C#,DN无CC#和(CS,CDATE)DN无DD#和DN无无PPN无无SP(S#,PN)S#,DN无AnIntroductiontoDatabaseSystem3.试由Armostrong公理系统推导出下面三条推理规则：⑴合并规则：若X→Z，X→Y，则有X→YZ⑵伪传递规则：由X→Y，WY→Z，则有XW→Z⑶分解规则：若X→Y，ZY，则有X→Z证明：⑴已知X→Z，由增广律知XY→YZ，又因X→Y，可得XX→XY→YZ，根据传递律有X→YZ⑵已知X→Y，由增广律知XW→WY，又因WY→Z，可得XW→WY→Z，根据传递律有XW→Z⑶已知ZY，由自反律知Y→Z，又因X→Y，所以由传递律可得X→ZAnIntroductiontoDatabaseSystem4.关于多值依赖的另一种定义是：给定一个关系模式R(X,Y,Z)，其中，X,Y,Z可以是属性或属性组。设xX，yY，zZ，xz在R中的像集为：Yxz={r.Y|r.X=x∧r.Z=z∧rR}。定义：R(X,Y,Z)当且仅当Yxz=Yxz’对于每一组(x,z,z’)都成立，则Y对X多值依赖，记作X→→Y。这里，允许Z为空集，在Z为空集时，称为平凡的多值依赖。证明：设Yxz=Yxz’对于每一组(x,z,z’)都成立，并设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的条件是等价的，所以两定义等价。AnIntroductiontoDatabaseSystem5.试举出3个多值依赖的实例。答：⑴关系模式MSC(M,S,C)中，M为专业，S为学生，C为该专业的必修课。假设每个专业有多个学生，有一组必修课。设同专业内所有学生选修的必修课相同。