自考数据库系统原理(第3章

1、1函数依赖：设有关系模式r（u），x和y是属性集u的子集，函数依赖（functional dependency，简记为fd）是形为xy的一个命题，只要r是r的当前关系，对r中任意两个元组t和s，都有tx=sx蕴涵ty=sy，那么称fd xy在关系模式r（u）中成立。这里tx表示元组t在属性集x上的值，其余类同。xy读作“x函数决定y”，或“y函数依赖于x”。fd是对关系模式r的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果x值相同，则要求y值也相同，即有一个x值就有一个y值与之对应，或者说y值由x值决定。因而这种依赖称为函数依赖。2平凡的函数依赖:对于fd xy，如果yx，那么称x

2、y是一个“平凡的fd”，否则称为“非平凡的fd”。正如名称所示，平凡的fd并没有实际意义，根据规则a1就可推出。人们感兴趣的是非平凡的fd。只有非平凡的fd才和“真正的”完整性约束条件相关。从规则a4和a5，立即可得到下面的定理。定理3.3 如果a1an是关系模式r的属性集，那么xa1an成立的充分必要条件是xai（i=1，n）成立。3函数依赖集f的闭包f+（closure）:设f是函数依赖集，被f逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集f的闭包（closure），记为f+。即f+= xy | f|=xy。4属性集x的闭包x+:设f是属性集u上的fd集，x是u的子集，那么（相对于f）属

3、性集x的闭包用x+表示，它是一个从f集使用fd推理规则推出的所有满足xa的属性a的集合：x+=属性a | f|=xa 5函数依赖的逻辑蕴含:设f是在关系模式r上成立的函数依赖的集合，xy是一个函数依赖。如果对于r的每个满足f的关系r也满足xy，那么称f逻辑蕴涵xy，记为f|=xy。6函数依赖集的等价:如果关系模式r（u）上的两个函数依赖集f和g，有f+=g+，则称f和g是等价的函数依赖集。7最小依赖集:如果函数依赖集g满足下列三个条件，则称为g是最小依赖集。（1）g中每个fd的右边都是单属性。（2）g中没有冗余的f，即g中不存在这样的函数依赖xy，使得gxy与g等价。（3）g中每个fd的左边没

4、有冗余的属性，即g中不存在这样的函数依赖xy，x有真子集w使得gxywy与g等价。显然，每个函数依赖集至少存在一个等价的最小依赖集，但并不一定惟一。8无损分解:设r是一个关系模式，f是r上的一个fd集。r分解成数据库模式=r1，r2rk。如果对r中满足f的每一个关系r，都有r=那么称分解相对于f是“无损连接分解”（lossless join decomposition），简称为“无损分解”，否则称为“损失分解”（lossy decomposition）。9泛关系假设:无损分解定义有一个先决条件，即r是r的一个关系。也就是先存在r（泛关系）的情况下，再去谈论分解，这就是关系数据库理论中著名的“泛

5、关系假设”（univarsal relation assumption）。有泛关系假设时，r与（r）之间的联系，可用图3.3表示。从图中可看出（r）有两个性质：（1）r（r）（2）设s=（r），则=rirrs=r1，r2rk r1，r2，rk图3.3 泛关系假设下关系模式分解的示意图10chase过程: “追踪”（chase）过程，用于测试一个分解是否是无损分解。追踪过程的算法（无损分解的测试）输入：关系模式r=a1an，f是r上成立的函数依赖集，=r1，rk是r的一个分解。输出：判断相对于f是否具有无损分解特征。方法：构造一张k行n列的表格，每列对于一个属性aj（1jn），每行对于一个模式r

6、i（1ik）。如果aj在ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。把表格看成模式r的一个关系，反复检查f中每个fd在表格中是否成立，若不成立，则修改表格中的值。修改反复如下：对于f中一个fd xy，如果表格中有两行在x值上相对，在y值上不相等，那么把这两行在y值上也改成相等的值。如果y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为chase过程）若修改的最后一张表格中有一行是全a，即a1a2an，那么称相对于f是无损分解，否则称损失分解。11保持函数依赖:分解的另一

7、个特征是在分解的过程中能否函数依赖集，如果不能保持fd，那么数据的语义就会出现混乱。设f是属性集u上的fd集，z是u的子集，f在z上的投影用表示，定义为设=r1，rk是r的一个分解，f是r上的fd集，如果有，那么称分解保持函数依赖集f。121nf如果关系模式r的每个关系r的属性值都是不可分的原子值，那么称r是第一范式（first normal form，简记为1nf）的模式。132nf如果关系模式r是1nf，且每个非主属性完全函数依赖于候选键，那么称r是第二范式（2nf）的模式。143nf如果关系模式r是1nf，且每个非主属性都不传递依赖于r的候选键，那么称r是第三范式（3nf）的模式。15b

8、cnf如果关系模式r是1nf，且每个属性都不传递依赖于r的候选键，那么称r是bcnf。16mvd设u是关系模式r的属性集，x，y是u的子集，z=u-x-y，小写的xyz表示属性集xyz的值。对于r的关系r，在r中存在元组（x，y1，z1）和（x，y2，z2）时，就也存在元组（x，y2，z1）和（x，y1，z2），那么称多值依赖（multivalued dependency，简记为mvd）xy在模式r上成立。17平凡的mvd对于属性集u上的mvd xy，如果yx或xy=u，那么称xy是一个平凡的mvd，否则称xy是一个非平凡的mvd。184nf设d是关系模式r上成立的fd和mvd集合。如果d中每

9、个非平凡的mvd xy的左部x都是r的超键，那么称r是4nf的模式。3.2试解释下面两个“数据冗余”概念：一、文件系统中不可避免的“数据冗余”在数据管理中，数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在系统中多次重复出现。在文件系统中，由于文件之间没有联系，引起一个数据在多个文件中出现。二、关系数据库设计中应该尽量避免的“数据冗余”数据库系统克服了文件系统的这种缺陷，但对于数据冗余问题仍然应加以关注。如果一个关系模式设计的不好，仍然会出现像文件系统一样的数据冗余、异常、不一致等问题。3.3关系模式的非形式化设计准则有哪几条？这些准则对数据库设计有什么帮助？在讨论关系模式质量时，有

10、四个非形式化的衡量准则。准则3.1 关系模式的设计应尽可能只包含直接联系的属性，不要包含有间接联系的属性。也就是，每个关系模式应只对应于一个实体类型或一个联系类型。准则3.2 关系模式的设计应尽可能使得相应关系中不出现插入、删除和修改等操作异常现象。如果出现任何异常，则要清楚地加以说明，并确保更新数据库的正确操作。设计成表准则3.3 关系模式的设计应尽可能使得相应关系之中避免放置经常为空的属性。准则3.4 关系模式的设计应尽可能使得关系的等值连接在主键和外键的属性上进行，并且保证连接以后不会生成额外的元组。3.4对函数依赖xy的定义加以扩充，x和y可以为空属性集，用表示，那么x，y，的含义是什

11、么？解：根据函数依赖的定义，以上三个表达式的含义为：1. 一个关系模式r（u）中，x，y是u的子集，r是r的任一具体关系，如果对r的任意两个元组t1、t2，由t1x=t2x必有t1=t2。即x表示空属性函数依赖于x。这是任何关系中都存在的。2. y表示y函数依赖于空属性。由此可知该关系中所有元组中y属性的值均相同。3. 表示空属性函数依赖于空属性。这也是任何关系中都存在的。3.5用a1、a2和a3三条推理规则来证明3.2.3节中的定理3.2（推理规则a4a8）试证明a1（自反性）：若yxu，则xy在r上成立。证：设t1和t2是关系r中的任意两个元组。如t1【x】=t2【x】，因yx，则有t1【

12、y】=t2【y】，故xy在r上成立。试证明a2（增广性）：若xy在r上成立，且zu，则xzyz在r上成立。证：设t1和t2是关系r中的任意两个元组。如果t1【xz】=t2【xz】，则有如t1【x】=t2【x】，t1【z】=t2【z】。已知xy，因此可得t1【y】=t2【y】，由上可知如t1【yz】=t2【yz】，故xzyz成立。试证明a3（传递性）：若xy和若yz在r上成立，则xz在r上成立。证：设t1和t2是关系r中的任意两个元组。根据传递函数依赖条件可知：如t1【x】=t2【x】，则t1【y】=t2【y】，如t1【y】=t2【y】，则t1【z】=t2【z】，由上可得：如t1【x】=t2【x

13、】，则t1【z】=t2【z】，即xz在r上成立。试证明a4（合并性）：xy，xz |=xyz。证：根据a2增广性，在xy的函数依赖表达式左部和右部分别并上x，得 xx y。在xz的函数依赖表达式左部和右部分别并上y，得 xyyz。根据a3传递性，由xx y和xyyz得xyz。试证明a5（分解性）xy，zy |=xz。证：根据a 1自反性，因为zy所以yz成立。已知xy又知，yz，根据a3，得xz。试证明a6（伪传递性）xy，wyz |=wxz。证：根据a2增广性，在xy的函数依赖表达式左部和右部分别并上w，得wxwy。根据a3传递性，由wxwy 和wyz得wxz。试证明a7（复合性）xy，wz

14、 |=wxyz。证：根据a2增广性，在xy的函数依赖表达式左部和右部分别并上w，的wxwy。在wz的函数依赖表达式左部和右部分别并上y，的wyzy。根据a3传递性，由wxwy和wyzy得wxyz。试证明a8（复合性）xy，wz|=x(wy)yz。证：根据a2增广性，在xy两边用（wy）扩充，得到x(wy)y(wy），而y(wy)=wy，因此有x(wy)wy。从已知wz，根据a2两边用y扩充，得到wyyz。在根据a3，从x(wy)wy和wyyz可得到x(wy)yz3.6设关系模式r有n个属性，在模式r上可能成立的函数依赖有多少个？其中平凡的fd有多少个？非平凡的fd有多少个？（要考虑所有可能的情

15、况,数学排列组合问题。对于数据库本身而言，本题没多大意义）解：这个问题是排列组合问题。fd形为xy，从n个属性值中选择属性组成x共有：种方法；同理，组成y也有种方法。因此组成xy形成应该有种方法。即可能成立的fd有个。平凡的fd要求yx，组合xy形式的选择有：即平凡的fd有。因而非平凡的fd有个。3.7已知关系模式r（abc），f是r上成立的fd集，f=ab，bc，试写出f的闭包f+（有43个）。 a ab ac abc b bc caa aba aca abca bb bcb ccab abb acb abcb bc bccac abc acc abcc bbc bcbcaab abab a

16、cab abcabaac abac acac abcacabc abbc acbc abcbcaabc ababc acabc abcabc解：1 先求属性集abc的子集、a、ab、ac、abc、b、bc、c2 求以上子集的闭包根据f=ab，bc，得：+=a+=abc a有： + + + =23=8个b+=bc b有： + + =22=4个c+=c c有： + =21=2个(ab)+=abc ab有：8个(ac)+=abc ac有：8个(bc)+=bc ab有：4个(abc)+=abc abc有：8个共43个。 3 求函数依赖根据属性集的闭包，得：根据：+=得：根据：a+=abc得：a、aa、

17、ab、ac、aab、aac、abc、aabc根据：b+=bc得：b、bb、bc、bbc根据：c+=c得：c、cc根据：ab+=abc得：ab、aba、abb、abc、abab、abac、abbc、ababc根据：ac+=abc得：ac、aca、acb、acc、acab、acac、acbc、acabc根据：bc+=bc得：bc、bcb、bcc、bcbc根据：abc+=abc得：abc、abca、abcb、abcc、abcab、abcac、abcbc、abcabc3.8设关系模式r（abcd），f是r上成立的fd集，f=ab，cb，则相对于f，试写出关系模式r的关键码。并说明理由。解：由于a、c属

18、性是l类属性，则a、c必为 r 的任一候选码的成员。由于d属性是n类属性，则d必为 r 的任一候选码的成员。到此，初步确定的关键码为acd。下一步根据f求出acd的闭包，得acd+=abcd。因为acd+包含了r的全部属性，acd是 r 的唯一关键键码。3.9设关系模式r（abcde），f是r上成立的fd集，f=abc，cde，deb，判断ab是r的候选键吗？abd呢？请做出解释。解：属性ab如果是候选键，那么ab的闭包必须包含r的全部属性。根据f得ab+=abc。ab+没有包含r的全部属性，故ab不是r的候选键。属性abc如果是候选键，那么abc的闭包必须包含r的全部属性。根据f得abd+=

19、abcde。abd+包含r的全部属性，故abd是r的候选键。3.10设关系模式r（abcd）上fd集为f，并且f=abc，cd，da 试从f求出所有非平凡的fd。 试求r的所有候选键 试求r的所有不是候选键的超键。解：要想求出、和，就必须先求出属性集的所有子集及其子集的闭包。1、求属性集abcd的子集。在属性集abcd中找出由一个属性组成的子集。a、b、c、d共4个。在属性集abcd中找出由两个属性组成的子集。共6个。abcdaabacadbbcbdccdd在属性集abcd中找出由三个属性组成的子集。共4个abcdababcabdacabcacdadabdacdbcabcbcdbdabdbcd

20、cdacdbcd在属性集abcd中找出由四个属性组成的子集。abcd 一个。属性集abcd的子集：共15个。abc dabbccdacbdadbcdabcabdacdabcd2、所有子集的闭包（参照f=abc，cd，da）。a+ =ab+ =bc+ =acdd+=daab+ =abcdbc+ =bcdacd+=cdaac+ =acdbd+ =bdacad+ =adbcd+=bcdaabc+ =abcdabd+ =abdcacd+ =acdabcd+=abcd求属性的闭包有两种算法（一是根据推理规则，而是根据闭包的算法）3、求出所有的函数依赖 1）根据 a+=a aa 平凡的函数依赖（1），非平

21、凡的函数依赖（0） 2）根据 b+=b bb 平凡的函数依赖（1），非平凡的函数依赖（0） 3）根据 c+=acd ca cac cad cacd cc ccd cd 平凡的函数依赖（1），非平凡的函数依赖（6） 4）根据 d+=ad da dd dda 平凡的函数依赖（1），非平凡的函数依赖（2） 5）根据 ab+=abcd aba abab abac abadababc ababd abacd ababcd abb abbc abbd abbcd abc abcd abd 平凡的函数依赖（3），非平凡的函数依赖（12） 6）根据 bc+=abcd bca bcab bcac bcad bc

22、abc bcabd bcacd bcabcd bcb bcbc bcbd bcbcd bcc bccd bcd 平凡的函数依赖（3），非平凡的函数依赖（12） 7）根据 cd+=acd cda cdac cdad cdacd cdc cdcd cdd 平凡的函数依赖（3），非平凡的函数依赖（4） 8）根据 ac+=acd aca acac acad acacd acc accd acd 平凡的函数依赖（3），非平凡的函数依赖（4） 9）根据 bd+=abcd bda bdab bdac bdad bdabc bdabd bdacd bdabcd bdb bdbc bdbd bdbcd bdc

23、bdcd bdd 平凡的函数依赖（3），非平凡的函数依赖（12）10）根据 ad+=ad ada adad add 平凡的函数依赖（3），非平凡的函数依赖（0）11）根据 bcd+=abcd bcda bcdab bcdac bcdad bcdabc bcdabd bcdacd bcdabcd bcdb bcdbc bcdbd bcdbcd bcdc bcdcd bcdd 平凡的函数依赖（7），非平凡的函数依赖（8）12）根据 abc+=abcd abca abcab abcac abcad abcabc abcabd abcacd abcabcd abcb abcbc abcbd abcbc

24、d abcc abccd abcd 平凡的函数依赖（7），非平凡的函数依赖（8）13）根据 abd+=abcd abda abdab abdac abdad abdabc abdabd abdacd abdabcd abdb abdbc abdbd abdbcd abdc abdcd abdd 平凡的函数依赖（7），非平凡的函数依赖（8）14）根据 acd+=acd acda acdac acdad acdacd acdcacdcd acdd 平凡的函数依赖（7），非平凡的函数依赖（0）15）根据 abcd+=abcd abcda abcdab abcdac abcdad abcdabc ab

25、cdabd abcdacd abcdabcd abcdb abcdbc abcdbd abcdbcd abcdc abcdcd abcdd 平凡的函数依赖（15），非平凡的函数依赖（0） 从已知的f可求出非平凡的fd有76个。譬如，左边是c的fd有6个：ca，cd，cad，cac，ccd，cacd。 左边是d的fd有2个：da，dad。 左边是ab的fd有12个：abc, abd, abcd, abac,。感兴趣的读者可以自行把这76个fd写齐。 1）根据 a+=a平凡的函数依赖（ 1），非平凡的函数依赖（ 0） 2）根据 b+=b平凡的函数依赖（ 1），非平凡的函数依赖（ 0） 3）根据 c

26、+=acd平凡的函数依赖（ 1），非平凡的函数依赖（ 6） 4）根据 d+=ad平凡的函数依赖（ 1），非平凡的函数依赖（ 2） 5）根据 ab+=abcd平凡的函数依赖（ 3），非平凡的函数依赖（12） 6）根据 bc+=abcd平凡的函数依赖（ 3），非平凡的函数依赖（12） 7）根据 cd+=acd平凡的函数依赖（ 3），非平凡的函数依赖（ 4） 8）根据 ac+=acd平凡的函数依赖（ 3），非平凡的函数依赖（ 4） 9）根据 bd+=abcd平凡的函数依赖（ 3），非平凡的函数依赖（12）10）根据 ad+=ad平凡的函数依赖（ 3），非平凡的函数依赖（ 0）11）根据 bcd+=a

27、bcd平凡的函数依赖（ 7），非平凡的函数依赖（ 8）12）根据 abc+=abcd平凡的函数依赖（ 7），非平凡的函数依赖（ 8）13）根据 abd+=abcd平凡的函数依赖（ 7），非平凡的函数依赖（ 8）14）根据 acd+=acd平凡的函数依赖（ 7），非平凡的函数依赖（ 0）15）根据 abcd+=abcd平凡的函数依赖（15），非平凡的函数依赖（ 0） -共计 （65） 共计（76） 候选键是能函数决定所有属性的不含多余属性的属性集。根据这个概念可求出r 的候选键有三个：ab、bc和bd。 r的所有不是候选键的超键有四个：abc、abd、bcd和abcd。3.11如果下列推理规则成

28、立，则用推理规则a1a8证明之；否则举出一个关系实例说明规则不成立。wy，xz|=wxyxy,xw,wyz|=xzxyz，yw|=xwzxz，yz|=xyxy，xyz|=xzxy，zw|=xzywxyz，zx|=zyxy，yz|=xyzxyz，zw|=xw解：wy，xz|=wxy根据推理规则a2（增广性）在fd wy两边同时并上x，得 wxxy。已知wy,又因wwx，故wxy成立。xy,xw,wyz|=xz根据fd的分解/合并规则，xy,xw可合并成xyw，再根据推理规则a3（传递性），xyw，wyz可得xzxyz，yw|=xwz根据推理规则a2（增广性）在fd yw两边同时并上x，得yxxw

29、。因为xyz，yxxw，z和xw没有包含或被包含的关系。故xyz，yw|=xwz不成立。例r（wxyz），f=xyz，yw，从以下函数依赖的图形化表示可以看出，不成立。r（w x y z）xz，yz|=xy因为fd xz，yz，x和y没有包含或被包含的关系。故上式不成立。xy，xyz|=xz根据推理规则a2（增广性）在fd xy两边同时并上x，得xxxy。再根据推理规则a3（传递性），xxxy，xyz，得xzxy，zw|=xzyw根据推理规则a2（增广性）在fd xy两边同时并上z，得xzyz。根据推理规则a2（增广性）在fd zw两边同时并上y，得yzyw。再根据推理规则a3（传递性），xz

30、yz，yzyw，得xzywxyz，zx|=zy因为fd xz，yz，x和y没有包含或被包含的关系。故上式不成立。xy，yz|=xyz根据推理规则a3（传递性）xy，yz，得xz。根据fd的分解/合并规则，xy,xz可合并成xyz。xyz，zw|=xw根据推理规则a3（传递性）xyz，zw，得xyw。故上式不成立。3.12 考虑以下两个fd集：f=ac，acd，ead，eh和g=acd，eah。试检查它们是否等价（应说出理由）。对f：a+=acd，c+=c，d+=d，e+=eadch=acdeh，h+=h，ac+=acd（ac+=a+c+abc）。对g：a+=acd，c+=c，d+=d，e+=e

31、ahcd=acdeh，h+=h，ac+=acd（ac+=a+c+abc）。故f与g等价。理由：f和g相等，意味着f中每一个fd都可以从g推导出来，并且g中每一个fd也都可以从f推导出来。同例：r(abcde)，f1=ab,abc,dac,de与f2=abc,dae等价？对f1：a+abc，b+b，c+c，d+abcde，e+e，(ab)+abc（ab+=a+b+=abc）。对f2：a+abc，b+b，c+c，d+abcde，e+e，(ab)+abc（ab+=a+b+=abc）。故f1与f2等价。3.13设关系模式r（abcd）上fd集为f，并且f=ab，bc 试写出属性集bd的闭包（bd）+。

32、 试写出所有左部是b的函数依赖（即形为“b？”）解： 有两种解法1）用推理规则 从已知的f，fd bc，根据a2（增广性），在两边同并上bd得bbdcbd 优化后，可推出bdbcd，所以(bd)+=bcd。2）用属性集的算法 1初始化，设x为所求属性集的闭包，x(0)=bd。 2计算x(1)，在f中扫描各个fd，找左部为bd或bd子集的fd，找到一个fd bc左边属性在x(0)中，而右边属性不在x(0)中，就把c和x(0)加到x(1) 中。然后再f中做上标记。因x(1)u，算法继续。 x(1)= x(0)c=bdc=bcd f=ab，bc 3计算x(2)，在f中扫描没做处理标记的fd，找左部为

33、bcd或bcd子集的fd， 没找到，x(1)= x(0)。算法终止。 由算法得：(bd)+= x(1)=bcd 首先计算b的闭包1 初始化，设x为所求属性b的闭包，x(0)=b。2 计算x(1),在f中扫描各个fd，找左边为b的fd，找到一个fd bc左边属性在x(0)中，右边属性不在x(0)中，就把c和x(0)加到x(1) 中。然后再f中做上标记。因x(1)u，算法继续。 x(1)= x(0)c=bc=bc f=ab，bc3 计算x(2)，在f中扫描没做处理标记的fd，找左部为bc或bc子集的fd，没找到，x(1)= x(0)。算法终止。有算法得：(b)+= x(1)=bc由于b+bc=bc

34、，因此左部是b的fd有四个：b，bb，bc，bbc。3.14设关系模式r（abcde）上fd集为f，并且f=abc，cde，bd，ea。 试求r的候选键。 试求b+的值。解： r的候选键有a、e、cd和bc最有把握的求法是：1） 求出关系属性集的所有子集。2） 求所有子集的闭包。3） 在所有子集的闭包中查找那些包含所有属性集的闭包，那些不含多余属性的属性集闭包就是我们要找的候选键。1）求属性集abcde的子集。 在属性集abcde中找出由一个属性组成的子集。a、b、c、d、e，共5个。 在属性集abcde中找出由两个属性组成的子集。共10个。abcdeaabacadaebbcbdbeccdce

35、ddee在属性集abcde中找出由三个属性组成的子集。共10个。abcdeababcabdabeacabcacdaceadabdacdadeaeabeaceadebcabcbcdbcebdabdbcdbdebeabebcebdecdacdbcdcdeceacebcecdedeadebdecde在属性集abcde中找出由四个属性组成的子集。共5个。abcdeabcabcdabceabdabcdabdeabeabceabdeacdabcdacdeaceabceacdeadeabdeacdebcdabcdbcdebceabcebcdebdeabdebcdecdeacdebcde在属性集abcde中找

36、出由五个属性组成的子集。abcde，共1个。至此，共找出 5+10+10+5+1=31个子集。它们是：a、b、c、d、eab、ac、ad、ae、bc、bd、be、cd、ce、deabc、abd、abe、acd、ace、ade、bcd、bce、bde、cdeabcd、abce、abde、acde、bcdeabcde2）求u=abcde所有子集的闭包（参照f=abc，cde，bd，ea）。abc+=abcdeabd+=abdce=abcdeabe+=abecd=abcdeacd+=acdbe=abcdeace+=acebd=abcdeade+=adebc=abcdebcd+=bcdea=abcde

37、bce+=bceda=abcdebde+=bdeac=abcdecde+=cdeab=abcdeabcd+=abcdeabce+=abced=abcdeabde+=abdec=abcdeacde+=acdeb=abcdebcde+=bcdea=abcdeabcde+=abcdea+=abcdeb+=bdc+=cd+=de+=eabcd=abcdeab+=abdac+=acbde=abcdead+=adbce=abcdeae+=aebcd=abcdebc+=bcdea=abcdebd+=bdbe+=bedac=abcdecd+=cdeab=abcdece+=ceabd=abcdede+=deab

38、c=abcde根据候选键的定义a+=abcde是候选键所有包含a的属性子集，闭包内容为abcde的都是超键。e+=abcde是候选键所有包含e的属性子集，闭包内容为abcde的都是超键。bc+=abcde是候选键所有包含bc的属性子集，闭包内容为abcde的都是超键。cd+=abcde是候选键所有包含cd的属性子集，闭包内容为abcde的都是超键。 b+=bd。1） 初始化，设x为所求属性b的闭包，x(0)=b2） 计算x（1），在f中扫描各个fd，找左边为b的fd。找到一个fd bd左边属性在x(0)中，而右边属性不在x(0)中，就把d和x(0)加的x(1)中，然后在f中做上标记。因x(1)

39、u，算法继续。 x(1)= x(0)d=bd=bd3） 计算x（1），在f中扫描没有做过处理标记的fd，找左边为bd或bd子集的fd，没有找到，x(1)= x(0)。算法终止。有算法得：(b)+= x(1)=bd3.15 设有关系模式r（abc），其关系r如图3.1所示。 试判断下列三个fd在关系r中是否成立？abbcaba 根据关系r，你能断定哪些fd在关系模式r上不成立？abc123423533 图3.1解： 在关系r中，ab成立，bca不成立，ba不成立。 在关系r中，不成立的fd有:ba，ca，cb，cab，bca。3.16 什么是寄生元组？什么是悬挂元组？各是怎么产生的？1寄生元组在

40、泛关系模式r分解成数据库模式=r，r时，泛关系r在的每一模式r（1in）上投影后再连接起来，比原来r中多出来的元组，称为“寄生元组”（spurious tuple）。2悬挂元组如果谈论模式分解时，先不提泛关系r的存在性，而先说存在一个数据库实例r，r，再设ri=s，那么 ri(s)记为si就未必与ri相等了，原因就是这些ri中可能存有“悬挂元组”（dangling tuple）在无泛关系假设时，对两个关系进行自然连接中被丢失的元组称为悬挂元组。3.17 设关系模式r（abc）分解成=ab，bc，如果r上的fd集f=ab，那么这个分解是损失分解。试举出r的一个关系r，不满足m（r）=r。解：这个

41、反例r可以举测试时的初始表格：abc aba1a2b13 bcb21a2a3ab和bc这两行中，因为f中只有 fd ab，所以，表格不能修改。又因表格不能修改，在表格中没有一行全是a，故泛模式r（abc）分解成=ab，bc是损失分解。设r是r上的一个关系，如下：a1a2b13b21a2a3r在模式ab和bc上的投影如下：ab（r）bc（r）abbca1a2a2b13b21a2a2a3模式ab和bc的连接，也就是在r上的投影如下，连接后比原来r的元组还要多。ab（r）bc（r）有四个元组：abca1a2b13a1a2a3b21a2b13b21a2a3即m（r）r。4.18 试解释数据库“丢失信息

42、”与“未丢失信息”两个概念。“丢失信息”与“丢失数据”有什么区别？答：数据库中丢失信息是指rm（r），未丢失信息是指r=m（r）。丢失信息：“无损中的“损”是指信息的丢失，而不是指元组的丢失。”所以丢失信息是指不能辨别元组的真伪。丢失数据：丢失数据是指丢失元组，是在无泛关系假设时，由数据库模式中的子模式自然连接中被丢失的元组。3.19 设关系模式r（abc），f是r上成立的fd集，f=ac，bc，试分别求f在模式ab和ac上的投影。答：分解后，f中fd ac，bc，在模式ab中没有投影，在模式ac中只保留了一个fd ac。另一个fd bc丢失了。即不保持f。ab（f）=（即不存在非平凡的fd）

43、ac（f）=ac3.20 设关系模式r（abc），f是r上成立的fd集，f=bc，ca，=ab，ac是r上的一个分解，那么分解是否保持是否无损分解和保持fd集f？并说明理由。答： 已知f=bc，ca， 而ab（f）=，ac（f）=ca 显然，这个分解丢失了fd bc 用测试过程可以知道，相对于f是损失分解。算法运用（b）修改后表格abcaba1a2b13aca1b21a3（a）初始表格abcaba1a2b13aca1b21a3根据函数依赖集f中fd bc，b列中没有相同的a值，故不能修改相应c列的值。函数依赖集fd ca，c列中没有相同的a值，故不能修改相应a列的值。因为在表格中没有一行具有相

44、同的数字a，故该分解为损失分解。3.21 设关系模式r（abcd），f是r上成立的fd集，f=ab，bc，ad，dc，=ab，ac，bd是r的一个分解。 相对于f，是无损分解吗？为什么？ 试求f在的每个模式上的投影。 保持f吗？为什么？答： 用测试过程可以知道，相对于f是损失分解。 1）根据函数依赖集f中fd ab，a列中ab与ac行单元格具有相同的内容a1值， b列ab单元的内容是a2，故可把b列ac行单元格中的内容改为a2。（a） 初始表格abcdaba1a2b13b14aca1b22a3b24bdb31a2b33a4（b） 修改1(ab)abcdaba1a2b13b14aca1a2a3b

45、24bdb31a2b33a4 2）根据函数依赖集f中fd bc，b列中ab与ac行单元格具有相同的内容a2值， c列ac单元的内容是a3，故可把c列ab行单元格中的内容改为a3。 3）根据函数依赖集f中fd ad，a列中ab与ac行单元格具有相同的内容a1值， d列ab与ac行单元格的内容没有一个是a值，故用其中一个下标较小的单元格 内容替代另外一个下标较大的单元格内容。（c） 修改3(ad)abcdaba1a2a3b14aca1a2a3b14bdb31a2a3a4（d） 修改2(bc)abcdaba1a2a3b14aca1a2a3b24bdb31a2a3a4 4）根据函数依赖集f中fd dc，d列中没有相同的内容a4，不能操作。再说c列 都是a3，不用操作。追踪过程完毕。（e） 修改4(dc)abcdaba1a2a3b14aca1a2a3b24bdb31a2a3a4得泛关系模式r（abcd）在数据库模式上的一个分解=ab，ac，bd是损失分解。 ab（f）=ab，ac（f）=ac，bd（f）=。ab，bc推理规则推