北京工业大学研究生数据库复试笔试课件chap4-关系数据库理论-128

1第4章关系数据库理论数据库模式:一组相关的关系模式关系模式R(A1,A2,…,An)24.1函数依赖4.1.1函数依赖的基本概念一、关系模式的优劣与数据依赖1.关系模式集性能比较3例1：学生数据库方案1：各类数据放在一个关系模式中Students(Sno,Sname,Cno,Grade,Sdept,Sloc)键(Sno，Cno)4问题：①冗余：一个学生选20门课学生系宿舍区的信息重复存储5②潜在不一致(修改复杂)学生改名对于所选的若干门课若干行到处修改潜在的不一致修改复杂6③插、删异常没选课Cno为NULL学生信息无法插入选课信息输入错误删除同时删学生信息7方案2：选课信息单独存放Students(Sno,Sname,Sdept,Sloc)键：SnoSC(Sno,Cno,Grade)键：(Sno,Cno)有所改进:与选课无关的信息只存一次8仍有问题:1.冗余系与宿舍区的对应关系一个系1000个学生系与宿舍区的对应关系存放1000次92.潜在不一致系换宿舍区到处修改潜在的不一致修改1000次复杂103.删插异常有相应学生的信息才能插入系以及宿舍区的信息学生全部毕业系与宿舍区的联系同时删除112.产生冗余及更新异常的原因关系模式内部属性值之间的内在联系——数据依赖主要的数据依赖：函数依赖、多值依赖12一个Sno，m个Cnom行学生信息一个系1000个Sno,1000行系与宿舍区的n:1联系键SnoCnoGradeSlocSdeptSname133.关于数据依赖属性值之间相关联系的表达语义的体现构成数据的约束大多数数据依赖是函数依赖14二、函数依赖的定义1.函数依赖设R(U)是一个关系模式，U是关系R的属性全集；X，Y是R的属性组（X，YU）；若对于R上任意一个可能的关系实例r满足：t1,t2∈r,t1[X]=t2[X]则t1[Y]=t2[Y]则称“X函数决定Y”或“Y函数依赖于X”记为：XYX称为决定因素对关系模式15函数依赖XY的含义为:任何时刻表中任一元组:属性组X上的值（a1a2...an）唯一地决定在属性组Y上的值(b1b2...bm)16R(A,B,C,D)一个实例:ABCDt1a1b1c1d1t2a2b2c2d2t3a2b2c2d3t4a3b2c2d4?元组t2,t3A的取值相同B,C的取值相同实例判定函数依赖？no17若对于任何时刻(任意实例)有A的取值相同时B,C上的取值相同则A(B,C)18函数依赖的例：例Movies(title,year,length,genre,studioName,starName)(title,year)length?决定？(title,year)genre?函数依赖？(title,year)studioName即(title,year)(length,genre,studioName)关系实例P38图3-21-3行5-6行19例:Students(Sno,Sname,Sage,Class_no,Sdept)此关系模式上有许多函数依赖如：Sno(Sname,Sage,Class_no,Sdept)Class_noSdept(Sno,Sname)(Sage,Class_no)……202.平凡函数依赖如果函数依赖XY，YX；则称为平凡函数依赖否则称为非平凡的函数依赖例：(Sno,Sname)Sname平凡函数依赖(Sno,Cno)Cno平凡函数依赖SnoSname非平凡的函数依赖21所有平凡的函数依赖保持“恒真”通常我们讨论的都是非平凡的函数依赖包含平凡的函数依赖有时简化规则的陈述A1A2…AnB1B2…Bm平凡:B1B2…Bm是A1A2…An子集非平凡:每一个Bi不是A1A2…An子集(通常讨论)224.1.2函数依赖与键设R(U)是一个关系模式，U是关系R的属性全集；X是R的属性组（XU）；若XU,且不存在X’X,X’U则称X为R的键(候选键)。X能决定所有属性X中属性缺一则不可决定所有属性23键举例：例Movies(title,year,length,genre,studioName,StarName)影片影星键:(title,year,StarName)能决定所有属性三个属性缺一不可所以是键24例：Students(Sno,Sname,Sage,Class_no,Sdept)键Sno(Sno,Sname)是超键不是键真子集Sno可以决定所有属性25设R(U)是一个关系模式，U是关系R的属性全集；X是R的属性组（XU）；若XU,则称X为R的超键。与键比较26超键举例：Students(Sno,Sname,sage,Class_no,Sdept)超键有：Sno(含自身)(Sno,Sname)(Sno,Class_no)(Sno,Sname,Sage,Class_no,Sdept)…274.1.3函数依赖的规则P40如何推导函数依赖已知某关系所满足的函数依赖,推出它满足的另一些函数依赖。例3.4R(A,B,C)由AB,BC推导AC思路:考察R的任意两个A上取值相同的元组看看C上取值是否相同28假设这样的两个元组为(a,b1,c1)(a,b2,c2)由ABA上值相同则B上值相同有b1=b2记为b得到(a,b,c1)(a,b,c2)由BCB上值相同则C上值相同有c1=c2即C上取值相同所以A上取值相同的元组C上取值相同所以AC29函数依赖集S蕴涵于函数依赖集T:满足T中函数依赖的关系实例也满足S中函数依赖R(A,B,C)T:{AB,BC}S{AB,BC,AC}30函数依赖集等价:函数依赖集S蕴涵于函数依赖集T函数依赖集T蕴涵于函数依赖集SS与T是等价的31P40分解规则:A1A2…AnB1B2…..Bm则A1A2…AnBii=1,…m例:(title,year,length,genre)(title,year)(length,genre)则(title,year)length(title,year)genre32合并规则:P40组合/结合A1A2…AnBii=1,…m则A1A2…AnB1B2…..Bm例:(title,year,length,genre)(title,year)length(title,year)genre则(title,year)(length,genre)33P42平凡依赖规则:A1A2…AnB1B2…..Bm等价于A1A2…AnC1C2…..Ck去掉A中出现的属性非平凡例:(title,year)(studioName,year)(title,year)(studioName)34**属性集的闭包函数依赖集F属性组X若有属性组Y包含所有满足下述条件的属性AXA蕴涵于F中的函数依赖称Y为属性组X对于函数依赖集F的闭包,记为XF+35P43例3.8:R(A,B,C,D,E,G)F={ABC,BCAD,DE,CGB}{A,B}+={A,B,C,D,E}F36闭包与键例:R(A,B,C,D)F={AD,BCA}{B,C}+={A,B,C,D}决定属性全集B+={B}C+={C}最小性BC是键FFF37求键时的一些考虑：1.一个属性不在函数依赖右边出现，则一定是键属性2.此外，考虑含函数依赖左边属性的属性集的闭包（不含不在左边、在右边的属性）3.不必考虑以键作为真子集的属性集的闭包4.不必考虑属性全集的闭包(全键情况除外)38例:R(A,B,C,D)F={AC,CB,BA}求所有键分析：键中必含D键属性涉及左边的A，B，C解:{A,D}+={A,C,B,D}{B,D}+={B,A,C,D}{C,D}+={C,B,A,D}D不是键，不含D的属性组也不能作键{A,D}{B,D}{C,D}为键不必考虑以上述键作为真子集的属性组这是所有的键FFF39定理:当且仅当Bi在A+中i=1..mAB1B2…..Bm?蕴涵于?函数依赖集FF40定理的例:例：R(A,B,C,D,E,G)F={ABC,BCAD,DE,CGB}1)ABD是否蕴涵于?上述函数依赖?{A,B}+={A,B,C,D,E}ABD蕴涵于...2)DA是否蕴涵于上述函数依赖?{D}+={DE}DA不蕴涵于...FF41传递规则:A1A2…AnB1B2…..BmB1B2…..BmC1C2…..Ck则A1A2…AnC1C2…..Ck42P44例3.10Movies(title,year,length,genre,studioName,StudioAddr)(title,year)studioNamestudioNameStudioAddr(title,year)StudioAddr43**函数依赖集的闭包:由给定的函数依赖集推导出的所有函数依赖的集合**对于关系模式:能导出关系模式的所有函数依赖的给定的函数依赖集,称为“基本集”,如果基本集的任何真子集不能导出关系上的所有依赖,此基本集为最小的.最小基本集又称为极小的函数依赖集等价44极小的函数依赖集(1)F中任一函数依赖的右部仅含一个属性(3)F中每个函数依赖的左部都没有多余的属性即：不存在这样的函数依赖XA，对于X的真子集Z使F与F-{XA}∪ZA等价(2)F中没有多余的函数依赖即：不存在这样的函数依赖XA使F与F-{XA}等价45计算极小函数依赖集的算法：(1)应用分解规则，使F中每一个函数依赖的右部属性单一化(3)F3=F2={AB,BC}极小集(2)F2=F1={AB,AC,BC,AC}={AB,AC,BC}(1)F1=F={AB,AC,BC,ABC}例：F={ABC,BC,ABC}(3)去掉多余的函数依赖(2)去掉各函数依赖左部多余的属性46Armstrong公理:推导函数依赖的规则自反律BA则AB增长律(增广律)AB则任意CACBC传递律ABBC则ACA，B，C为属性组474.2关系数据库模式设计4.2.1有关函数依赖完全函数依赖设R(U)是一个关系模式，U是关系R的属性全集；X,Y是R的属性组（X，YU）；若XY,且不存在X’X,X’Y则称Y完全函数依赖于X；记作：XY。f48完全函数依赖含义：元组在属性组Y上的值依赖于在属性组X中所有属性上的值。49部分函数依赖设R(U)是一个关系模式，U是关系R的属性全集；X,Y是R的属性组（X，YU）；若XY,且存在X’X,X’Y则称Y部分函数依赖于X；记作：XY。P50部分函数依赖含义：元组在属性组Y的值，只依赖于属性组X的一部分属性的值。51例：Students(Sno,Sname,Cno,Grade,Sdept,Sloc)键(Sno，Cno)SnoSname完全函数依赖(Sno，Cno)Sname部分函数依赖由于SnoSnamefp52传递函数依赖R(U)是一个关系模式，U是关系R的属性全集；X,Y,Z是R的属性组（X，Y,ZU）；若XY,YZ且ZY,YX则称Z传递函数依赖于X；记作：XZt53关于传递函数依赖的解释:ZY:不考虑平凡函数依赖YX:例：SnoSSNSSN(Sname,Sage)，由于SSNSnoSno（Sname,Sage）是直接函数依赖，同一实体两个键存储上没有冗余！?54传递函数依赖的含义：Z上的值可间接地依赖于X上的值，关系模式中含两个多对一联系形成的链，从而导致数据冗余。55例：Students(Sno,Sname,Sdept,Sloc)有SnoSdeptSdeptSloc于是SnoSloc是传递函数依赖，这里Sloc不仅依赖于键Sno还依赖于非键属性Sdept56不同Sno可以对应相同的Sdept不同的Sdept对应相同的Sloc。表中同一Sdept与Sloc的信息对不同Sno多次重复。数据冗余，由此带来潜在不一致性(修改时)。574.2.2关系模式的规范化为区分关系模式的优劣分为不同的范式(NormalForm)一、第一范式到第三范式1.第一范式(1NF)关系模式R属于1NF，当且仅当R中的每一属性A的值域只包含原子