数据库系统原理练习题3)

练习题33.1解释下列名词1．函数依赖：设有关系模式R（U），X和Y是属性集U的子集，函数依赖（functionaldependency，简记为FD）是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t[X]=s[X]蕴涵t[Y]=s[Y],那么称FDX→Y在关系模式R（U）中成立。这里t[X]表示元组t在属性集X上的值，其余类同。X→Y读作“X函数决定Y”，或“Y函数依赖于X”。FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果X值相同，则要求Y值也相同，即有一个X值就有一个Y值与之对应，或者说Y值由X值决定。因而这种依赖称为函数依赖。2．平凡的函数依赖对于FDX→Y,如果YX，那么称X→Y是一个“平凡的FD”，否则称为“非平凡的FD”。正如名称所示，平凡的FD并没有实际意义，根据规则A1就可推出。人们感兴趣的是非平凡的FD。只有非平凡的FD才和“真正的”完整性约束条件相关。从规则A4和A5，立即可得到下面的定理。定理3.3如果A1……An是关系模式R的属性集，那么X→A1……An成立的充分必要条件是X→Ai（i=1,…，n）成立。3．函数依赖集F的闭包F+（Closure）设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包（Closure），记为F+。即F+={X→Y|F|=X→Y}。4．属性集X的闭包X+设F是属性集U上的FD集，X是U的子集，那么（相对于F）属性集X的闭包用X+表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合：X+={属性A|F|=X→A}5．函数依赖的逻辑蕴含设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖。如果对于R的每个满足F的关系r也满足X→Y，那么称F逻辑蕴涵X→Y，记为F|=X→Y。6．函数依赖集的等价如果关系模式R（U）上的两个函数依赖集F和G，有F+=G+，则称F和G是等价的函数依赖集。7．最小依赖集如果函数依赖集G满足下列三个条件，则称为G是最小依赖集。（1）G中每个FD的右边都是单属性。（2）G中没有冗余的F，即G中不存在这样的函数依赖X→Y，使得G—{X→Y}与G等价。（3）G中每个FD的左边没有冗余的属性，即G中不存在这样的函数依赖X→Y，X有真子集W使得G—{X→Y}∪{W→Y}与G等价。显然，每个函数依赖集至少存在一个等价的最小依赖集，但并不一定惟一。8．无损分解设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式={R1，R2…Rk}。如果对R中满足F的每一个关系r，都有r=12()()()kRRRrrr那么称分解相对于F是“无损连接分解”（LosslessJoinDecomposition），简称为“无损分解”，否则称为“损失分解”（LossyDecomposition）。9．泛关系假设无损分解定义有一个先决条件，即r是R的一个关系。也就是先存在r（泛关系）的情况下，再去谈论分解，这就是关系数据库理论中著名的“泛关系假设”（UnivarsalRelationAssumption）。有泛关系假设时，r与m（r）之间的联系，可用图3.3表示。从图中可看出m（r）有两个性质：（1）rm（r）（2）设s=m（r），则()iRr=ri10．Chase过程“追踪”（chase）过程，用于测试一个分解是否是无损分解。追踪过程的算法（无损分解的测试）输入：关系模式R=A1…An，F是R上成立的函数依赖集，={R1，…，Rk}是R的一个分解。输出：判断相对于F是否具有无损分解特征。Rrs={R1，R2…Rk}r1，r2，…，rk图3.3泛关系假设下关系模式分解的示意图方法：①构造一张k行n列的表格，每列对于一个属性Aj（1≤j≤n），每行对于一个模式Ri（1≤i≤k）。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。②把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改反复如下：对于F中一个FDX→Y，如果表格中有两行在X值上相对，在Y值上不相等，那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为Chase过程）③若修改的最后一张表格中有一行是全a，即a1a2…an，那么称相对于F是无损分解，否则称损失分解。11．保持函数依赖分解的另一个特征是在分解的过程中能否函数依赖集，如果不能保持FD，那么数据的语义就会出现混乱。设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用()ZF表示，定义为(){|,XYZ}ZFXYXYF且设={R1，…，Rk}是R的一个分解，F是R上的FD集，如果有ikRi1F|F（），那么称分解保持函数依赖集F。12．1NF如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式（FirstNormalForm，简记为1NF）的模式。13．2NF如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式（2NF）的模式。14．3NF如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选键，那么称R是第三范式（3NF）的模式。15．BCNF如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF。16．MVD设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），那么称多值依赖（MultivaluedDependency，简记为MVD）X→→Y在模式R上成立。17．平凡的MVD对于属性集U上的MVDX→→Y，如果YX或XY=U，那么称X→→Y是一个平凡的MVD，否则称X→→Y是一个非平凡的MVD。18．4NF设D是关系模式R上成立的FD和MVD集合。如果D中每个非平凡的MVDX→→Y的左部X都是R的超键，那么称R是4NF的模式。3.2试解释下面两个“数据冗余”概念：一、文件系统中不可避免的“数据冗余”在数据管理中，数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在系统中多次重复出现。在文件系统中，由于文件之间没有联系，引起一个数据在多个文件中出现。二、关系数据库设计中应该尽量避免的“数据冗余”数据库系统克服了文件系统的这种缺陷，但对于数据冗余问题仍然应加以关注。如果一个关系模式设计的不好，仍然会出现像文件系统一样的数据冗余、异常、不一致等问题。3.3关系模式的非形式化设计准则有哪几条？这些准则对数据库设计有什么帮助？在讨论关系模式质量时，有四个非形式化的衡量准则。准则3.1关系模式的设计应尽可能只包含直接联系的属性，不要包含有间接联系的属性。也就是，每个关系模式应只对应于一个实体类型或一个联系类型。准则3.2关系模式的设计应尽可能使得相应关系中不出现插入、删除和修改等操作异常现象。如果出现任何异常，则要清楚地加以说明，并确保更新数据库的正确操作。设计成表准则3.3关系模式的设计应尽可能使得相应关系之中避免放置经常为空的属性。准则3.4关系模式的设计应尽可能使得关系的等值连接在主键和外键的属性上进行，并且保证连接以后不会生成额外的元组。3.4对函数依赖X→Y的定义加以扩充，X和Y可以为空属性集，用Φ表示，那么X→Φ，Φ→Y，Φ→Φ的含义是什么？解：根据函数依赖的定义，以上三个表达式的含义为：1.一个关系模式R（U）中，X，Y是U的子集，r是R的任一具体关系，如果对r的任意两个元组t1、t2，由t1[X]=t2[X]必有t1[φ]=t2[φ]。即X→φ表示空属性函数依赖于X。这是任何关系中都存在的。2.φ→Y表示Y函数依赖于空属性。由此可知该关系中所有元组中Y属性的值均相同。3.φ→φ表示空属性函数依赖于空属性。这也是任何关系中都存在的。3.5用A1、A2和A3三条推理规则来证明3.2.3节中的定理3.2（推理规则A4～A8）试证明A1（自反性）：若YXU，则X→Y在R上成立。证：设t1和t2是关系R中的任意两个元组。如t1【X】=t2【X】，因YX，则有t1【Y】=t2【Y】，故X→Y在R上成立。试证明A2（增广性）：若X→Y在R上成立，且ZU，则XZ→YZ在R上成立。证：设t1和t2是关系R中的任意两个元组。如果t1【XZ】=t2【XZ】，则有如t1【X】=t2【X】，t1【Z】=t2【Z】。已知X→Y，因此可得t1【Y】=t2【Y】，由上可知如t1【YZ】=t2【YZ】，故XZ→YZ成立。试证明A3（传递性）：若X→Y和若Y→Z在R上成立，则X→Z在R上成立。证：设t1和t2是关系R中的任意两个元组。根据传递函数依赖条件可知：如t1【X】=t2【X】，则t1【Y】=t2【Y】，如t1【Y】=t2【Y】，则t1【Z】=t2【Z】，由上可得：如t1【X】=t2【X】，则t1【Z】=t2【Z】，即X→Z在R上成立。试证明A4（合并性）：{X→Y，X→Z}|=X→YZ。证：根据A2增广性，在X→Y的函数依赖表达式左部和右部分别并上X，得X→XY。在X→Z的函数依赖表达式左部和右部分别并上Y，得XY→YZ。根据A3传递性，由X→XY和XY→YZ得X→YZ。试证明A5（分解性）{X→Y，ZY}|=X→Z。证：根据A1自反性，因为ZY所以Y→Z成立。已知X→Y又知，Y→Z，根据A3，得X→Z。试证明A6（伪传递性）{X→Y，WY→Z}|=WX→Z。证：根据A2增广性，在X→Y的函数依赖表达式左部和右部分别并上W，得WX→WY。根据A3传递性，由WX→WY和WY→Z得WX→Z。试证明A7（复合性）{X→Y，W→Z}|=WX→YZ。证：根据A2增广性，在X→Y的函数依赖表达式左部和右部分别并上W，的WX→WY。在W→Z的函数依赖表达式左部和右部分别并上Y，的WY→ZY。根据A3传递性，由WX→WY和WY→ZY得WX→YZ。试证明A8（复合性）{X→Y，W→Z}|=X∪（W→Y）→YZ。证：根据A2增广性，在X→Y两边用（W－Y）扩充，得到X∪（W－Y）→Y∪（W－Y），而Y∪（W－Y）=WY，因此有X∪（W－Y）→WY。从已知W→Z，根据A2两边用Y扩充，得到WY→YZ。在根据A3，从X∪（W－Y）→WY和WY→YZ可得到X∪（W→Y）→YZ3.6设关系模式R有n个属性，在模式R上可能成立的函数依赖有多少个？其中平凡的FD有多少个？非平凡的FD有多少个？（要考虑所有可能的情况,数学排列组合问题。对于数据库本身而言，本题没多大意义）解：这个问题是排列组合问题。FD形为X→Y，从n个属性值中选择属性组成X共有：0122nnnnnnCCCC种方法；同理，组成Y也有2n种方法。因此组成X→Y形成应该有224nnn种方法。即可能成立的FD有4n个。平凡的FD要求YX，组合X→Y形式的选择有：001012012012011222()()()nnnnnnnnCCCCCCCCCCCCC0011222222(12)3nnnnnnnnCCCC即平凡的FD有3n。因而非平凡的FD有43nn个。3.7已知关系模式R（ABC），F是R上成立的FD集，F=｛A→B，B→C｝，试写出F的闭包F+（有43个）。A→ΦAB→ΦAC→ΦABC→ΦB→ΦBC→ΦC→ΦA→AAB→AAC→AABC→AB→BBC→BC→CA→BAB→BAC→BABC→BB→CBC→CΦ→ΦA→CAB→CAC→CABC→CB→BCBC→BCA→ABAB→ABAC→ABABC→ABA→ACAB→ACAC→ACABC→ACA→BCAB→BCAC→BCABC→BCA→ABCAB→ABCAC→ABCABC→ABCφ→φA+=ABCA