搜索
1.关于多值依赖的另一种定义是：给定一个关系模式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为空集时，称为平凡的多值依赖。请证明这里的定义和《概论》5.2.7节中定义5.9是等价的。2.试证明《概论》上给出的关于FD和MVD公理系统的A4，A6和A8。A4：若X→→Y，V?W?U，则XW→→YV设Z=U-X-Y已知X→→Y，设r是R上的任一关系，s、t∈r，且t[X]=s[X]，则存在元组p、q∈r，使p[X]=q[X]=t[X]，而p[Y]=t[Y]，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]（由V?W知t[V]=s[V]），q[YV]=s[YV]，p[U-YV-XW]=s[U-YV-XW](因为U-YV-XW?Z)，q[U-YV-XW]=t[U-YV-XW]。所以XW→→YV。A6：若X→→Y，Y→→Z则X→→Z-Y由Y→→Z容易证得Y→→Z-Y。设R1=U－X－Y，R2=U－Y－Z，R3=U-X-Z+Y。已知X→→Y，设r是R上的任一关系，s、t∈r，且t[X]=s[X]，则存在元组p、q∈r，使p[X]=q[X]=t[X]，而p[Y]=t[Y]，p[Ｒ１]=s[Ｒ１]，q[Y]=s[Y]，q[Ｒ１]=t[Ｒ１]。对元组ｔ、ｐ，已知ｔ[Y]=p[Y]，t[X]=p[X]，由Y→→Z-Y知：存在元组m∈r，使m[Z-Y]=p[Z-Y]，m[R2]=t[R2]。因为（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-Y]=t[Z-Y]，即n[R3]=s[R3]。综上所述，对t、s∈r，t[X]=s[X]，存在元组m、n∈r，使m[X]=n[X]=t[X]，而m[Z-Y]=s[Z-Y]，m[R3]=t[R3]，n[Z-Y]=t[Z-Y]，n[R3]=s[R3]。A8：若X→→Y，W→Z，W∩Y=Φ，Z?Y，则X→Z。设r是R上的任一关系，对任意s、t∈r，若t[X]=s[X]，设R1=U-X-Y，则根据X→→Y知：存在元组p、q∈r，使p[X]=q[X]=t[X]，而p[Y]=t[Y]，p[Ｒ１]=s[Ｒ１]，q[Y]=s[Y]，q[Ｒ１]=t[Ｒ１]。因为W∩Y=Φ，所以s[W]=p[W]，又W→Z，所以s[Z]=p[Z]；因为Z?Y，且p[Y]=t[Y]，所以p[Z]=t[Z]；所以可得t[Z]=s[Z]，即X→Z。3.设关系模式为R（U，F），X，Y为属性集，X，Y?U。证明:（1）X?XF+（2）（XF+）F+=XF+（3）若X?Y则XF+?YF+（4）UF+=U（1）因为X→X所以X?XF+（根据XF+的定义）（2）*解析1要证明（XF+）F+=XF+只要证明XF+?（XF+）F+并且（XF+）F+?XF+而XF+?（XF+）F+是显然的，因此只要证明（XF+）F+?XF+2这里的证明要用集合论的基本知识，同学们应该复习一下有关集合论中的有关概念和证明方法。证明：下面求证（XF+）F+?XF+任意A∈（XF+）F+，（由题意知）存在B∈XF+，使B→A能由F根据Armstrong公理导出，而从B∈XF+可知X→B能由F根据Armstrong公理导出，根据公理中的传递律可知X→A能由F根据Armstrong公理导出，所以A∈XF+，因此（XF+）F+?XF+。所以（XF+）F+=XF+。（3）对任意A∈XF+，可知X→A能由F根据Armstrong公理导出，因为X?Y，由自反律可以得Y→X，由传递律得Y→A，所以A∈YF+。XF+?YF+得证。（4）*解析要证明UF+=U只要证明U?UF+并且UF+?UU?UF+是显然的；下面证明UF+?U，即证U由F据Armstrong公理推出的集合仍属于U：自反律：Y?U，U→Y为F所蕴含。显然U由F据Armstrong公理的自反律推出的Y仍属于U；增广律：U→Y为F所蕴含，且Z?U，则UZ→YZ为F所蕴含，YZ?U。传递律：U→Y和Y→Z都为F所蕴含，则U→Z为F所蕴含。Z?U。4.设关系模式为R（U，F），若XF+=X，则称X相对于F是饱和的。定义饱和集?F={X|X=XF+}，试证明?F={XF+|X?U}。证：1）证?F?{XF+|X?U}对任意A∈?F，由已知条件得A=AF+，因为A?U，A=AF+所以A∈{XF+|X?U}。2）证{XF+|X?U}??F对任意A∈{AF+|A?U}，因为（AF+）F+=AF+（见习题7），令B=AF+，有BF+=B所以B∈?F即AF+∈?F，A∈?F得证。5.试证明，若并发事务遵守两段锁协议，则对这些事务的并发调度是可串行化的。首先以两个并发事务T1和T2为例，存在多个并发事务的情形可以类推。根据可串行化定义可知，事务不可串行化只可能发生在下列两种情况：1．事务T1写某个数据对象A，T2读或写A；2．事务T1读或写某个数据对象A，T2写A。下面称A为潜在冲突对象。设T1和T2访问的潜在冲突的公共对象为{A1,A2,…,An}。不失一般性，假设这组潜在冲突对象中X={A1,A2,…,Ai}均符合情况1。Y={Ai+1,…,An}符合所情况2。?x?X，T1需要Xlockx①T2需要Slockx或Xlockx②（1）如果操作①先执行，则T1获得锁，T2等待由于遵守两段锁协议，T1在成功获得X和Y中全部对象及非潜在冲突对象的锁后，才会释放锁这时如果?w?X或Y，T2已获得w的锁，则出现死锁否则，T1在对X、Y中对象全部处理完毕后，T2才能执行这相当于按T1、T2的顺序串行执行根据可串行化定义，T1和T2的调度是可串行化的。（2）操作②先执行的情况与（1）对称因此，若并发事务遵守两段锁协议，在不发生死锁的情况下，对这些事务的并发调度一定是可串行化的。