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

《数据库系统原理练习题3)》由会员分享，可在线阅读，更多相关《数据库系统原理练习题3)（17页珍藏版）》请在金锄头文库上搜索。

1、练习题练习题 3 33.1 解释下列名词解释下列名词 1函数依赖：函数依赖： 设有关系模式 R R（U U） ，X X 和 Y Y 是属性集 U U 的子集，函数依赖（functionalfunctional dependencydependency，简记为 FDFD）是形为 XYXY 的一个命题，只要 r r 是 R R 的当前关系，对 r r 中任意 两个元组 t t 和 s s，都有 tX=sXtX=sX蕴涵 tY=sYtY=sY,那么称 FDFD XYXY 在关系模式 R R（U U）中成 立。 这里 tXtX表示元组 t t 在属性集 X X 上的值，其余类同。XYXY 读作“X X

2、 函数决定 Y Y” ，或 “Y Y 函数依赖于 X X” 。FDFD 是对关系模式 R R 的一切可能的关系 r r 定义的。对于当前关系 r 的任 意两个元组，如果 X X 值相同，则要求 Y 值也相同，即有一个 X X 值就有一个 Y Y 值与之对应， 或者说 Y Y 值由 X X 值决定。因而这种依赖称为函数依赖。2平凡的函数依赖平凡的函数依赖 对于 FDFD XYXY,如果 Y YX X，那么称 XYXY 是一个“平凡的 FDFD” ，否则称为“非平凡的 FDFD” 。 正如名称所示，平凡的 FDFD 并没有实际意义，根据规则 A1A1 就可推出。人们感兴趣的是 非平凡的 FDFD。

3、只有非平凡的 FDFD 才和“真正的”完整性约束条件相关。 从规则 A4 和 A5，立即可得到下面的定理。 定理 3.3 如果 A1An 是关系模式 R 的属性集，那么 XXA1An 成立的充分必要 条件是 XAi（i=1,，n）成立。3 3函数依赖集函数依赖集 F F 的闭包的闭包 F F+ +（ClosureClosure） 设 F F 是函数依赖集，被 F F 逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集 F F 的 闭包（ClosureClosure） ，记为 F F+ +。即F F+ += XY | F|=XY。4 4属性集属性集 X 的闭包的闭包 X+ 设 F 是属性集 U 上

4、的 FD 集，X 是 U 的子集，那么（相对于 F）属性集 X 的闭包用 X+表示，它是一个从 F 集使用 FD 推理规则推出的所有满足 XA 的属性 A 的集合： X+=属性 A | F|=XA 5 5函数依赖的逻辑蕴含函数依赖的逻辑蕴含 设 F F 是在关系模式 R R 上成立的函数依赖的集合，XYXY 是一个函数依赖。如果对于 R R 的 每个满足 F F 的关系 r r 也满足 XYXY，那么称 F F 逻辑蕴涵 XYXY，记为 F|=XYF|=XY。6 6函数依赖集的等价 如果关系模式 R（U）上的两个函数依赖集 F 和 G，有 F+=G+，则称 F 和 G 是等价的 函数依赖集。7

5、 7最小依赖最小依赖集 如果函数依赖集 G 满足下列三个条件，则称为 G 是最小依赖集。 （1）G 中每个 FD 的右边都是单属性。 （2）G 中没有冗余的 F，即 G 中不存在这样的函数依赖 XY，使得 GXY与G 等价。 （3）G 中每个 FD 的左边没有冗余的属性，即 G 中不存在这样的函数依赖 XY，X 有真子集 W 使得 GXYWYWY与 G G 等价。 显然，每个函数依赖集至少存在一个等价的最小依赖集，但并不一定惟一。8 8无损分解无损分解 设 R 是一个关系模式，F 是 R 上的一个 FD 集。R 分解成数据库模式=R1，R2Rk。 如果对 R 中满足 F 的每一个关系 r，都有

6、r= 12( )( )( ) kRRRrrr那么称分解相对于 F 是“无损连接分解” （Lossless Join Decomposition） ，简称为 “无损分解” ，否则称为“损失分解” （Lossy Decomposition） 。9 9泛关系假设泛关系假设 无损分解定义有一个先决条件，即 r 是 R 的一个关系。也就是先存在 r（泛关系）的 情况下，再去谈论分解，这就是关系数据库理论中著名的“泛关系假设” （Univarsal Relation Assumption） 。有泛关系假设时，r 与（r）之间的联系，可用图 3.3 表示。从图中可看出m（r）有两个性质：m（1）r（r） m

7、（2）设 s=（r） ，则=rim( ) iRr1010ChaseChase 过程过程“追踪” （chase）过程，用于测试一个分解是否是无损分解。 追踪过程的算法（无损分解的测试）输入：关系模式 R=A1An，F 是 R 上成立的函数依赖集，=R1，Rk是 R 的Rrs=R1，R2Rkr1，r2，rk图 3.3 泛关系假设下关系模式分解的示意图一个分解。 输出：判断相对于 F 是否具有无损分解特征。 方法：构造一张 k 行 n 列的表格，每列对于一个属性 Aj（1jn） ，每行对于一个模式Ri（1ik） 。如果 Aj在 Ri中，那么在表格的第 i 行第 j 列处填上符号 aj，否则填上bij

8、。把表格看成模式 R 的一个关系，反复检查 F 中每个 FD 在表格中是否成立，若不成立， 则修改表格中的值。修改反复如下： 对于 F 中一个 FD XY，如果表格中有两行在 X 值上相对，在 Y 值上不相等，那么把这两行在 Y 值上也改成相等的值。如果 Y 值中有一个是 aj，那么另一个也改成 aj；如果没有 aj，那么用其一个 bij替换另一个值（尽量把下标 ij 改成较小的数） 。一直到表格不能修改为止。 （这个过程称为 Chase 过程）若修改的最后一张表格中有一行是全 a，即 a1a2an，那么称相对于 F 是无损分解，否则称损失分解。1111保持函数依赖保持函数依赖 分解的另一个特

9、征是在分解的过程中能否函数依赖集，如果不能保持 FD，那么数据的 语义就会出现混乱。设 F 是属性集 U 上的 FD 集，Z 是 U 的子集，F 在 Z 上的投影用表示，定义为( )ZF( )|,XYZZFXY XYF且设=R1，Rk是 R 的一个分解，F 是 R 上的 FD 集，如果有，那 ikR i 1F | F（）么称分解保持函数依赖集 F。12121NF1NF 如果关系模式 R 的每个关系 r 的属性值都是不可分的原子值，那么称 R 是第一范式 （First Normal Form，简记为 1NF）的模式。13132NF2NF 如果关系模式 R 是 1NF，且每个非主属性完全函数依赖于

10、候选键，那么称 R 是第二范 式（2NF）的模式。14143NF3NF 如果关系模式 R 是 1NF，且每个非主属性都不传递依赖于 R 的候选键，那么称 R 是第 三范式（3NF）的模式。1515BCNFBCNF 如果关系模式 R 是 1NF，且每个属性都不传递依赖于 R 的候选键，那么称 R 是 BCNF。1616MVDMVD 设 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） ，那么称多值依赖

11、（Multivalued Dependency，简记为 MVD）XY 在模式 R 上成立。1717平凡的平凡的 MVDMVD 对于属性集 U 上的 MVD XY，如果 YX 或 XY=U，那么称 XY 是一个平凡的 MVD，否则称 XY 是一个非平凡的 MVD。18184NF4NF 设 D 是关系模式 R 上成立的 FD 和 MVD 集合。如果 D 中每个非平凡的 MVD XY 的左 部 X 都是 R 的超键，那么称 R 是 4NF 的模式。3.2 试解释下面两个试解释下面两个“数据冗余数据冗余”概念：概念： 一、文件系统中不可避免的一、文件系统中不可避免的“数据冗余数据冗余” 在数据管理中，

12、数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在 系统中多次重复出现。在文件系统中，由于文件之间没有联系，引起一个数据在多个文件 中出现。 二、关系数据库设计中应该尽量避免的二、关系数据库设计中应该尽量避免的“数据冗余数据冗余” 数据库系统克服了文件系统的这种缺陷，但对于数据冗余问题仍然应加以关注。如果 一个关系模式设计的不好，仍然会出现像文件系统一样的数据冗余、异常、不一致等问题。3.3 关系模式的非形式化设计准则有哪几条？这些准则对数据库设计有什么帮助？关系模式的非形式化设计准则有哪几条？这些准则对数据库设计有什么帮助？ 在讨论关系模式质量时，有四个非形式化的衡量准则。 准则准

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

14、和和 Y Y 可以为空属性集，用可以为空属性集，用 表示，那么表示，那么 XX，YY， 的含义是什么？的含义是什么？ 解：根据函数依赖的定义，以上三个表达式的含义为： 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 三条推理规则来证明三条推理

15、规则来证明 3. .2. .3 节中的定理节中的定理 3. .2（推理规则（推理规则 A4 4A8）试证明 A1（自反性）：若 YXU，则 XY 在 R 上成立。 证：设 t1 和 t2 是关系 R 中的任意两个元组。 如 t1【X】=t2【X】 ，因 YX，则有 t1【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】 ，则 t1【Z】=t2