《数据库原理与应用 教学课件 ppt 作者 陆慧娟 主编 吴达胜 刘建平 黄长城 副主编 第4章 关系数据库理论》由会员分享，可在线阅读，更多相关《数据库原理与应用 教学课件 ppt 作者 陆慧娟 主编 吴达胜 刘建平 黄长城 副主编 第4章 关系数据库理论（107页珍藏版）》请在金锄头文库上搜索。
1、第四章 关系数据库理论,本章要点,数据库设计不当而引发的问题，冗余、插入异常、删除异常、潜在的不一致性 函数依赖 关系模式的分解 关系模式的规范化,4.1问题的提出,我们来分析一下这样的关系模式在实际使用中会存在什么问题。表41为这个关系模式的一个可能的具体关系。,表41 商品供应表,4.1.1冗余量大 从表4.1中可以看到，对每一个供应商供应 的每一个零件，都要重复存放一次这个供应商的DITY的值，显然冗余量很大。,4.1.2插入异常 假如供应商的名字是互不相同的，且每一个供应商所在的城市是唯一的，那么供应商的CITY值依赖于供应商的名字，即如果供应商的名字确定了。又由于各种不同的零件具有不
2、相同的名字，那么零件数量依赖于供应商的名字和所,供应的零件，即确定了哪个供应商供应的哪一种零件，才能确定零件的数量，于是可以确定这个关系模式具有一个唯一的关键字，它是由供应商名和零件名这两个属性组成的。 如果某一个供应商当前还没有供应任何零件，那么我们不能记录CITY值，因为一个元组是以关键字标识的，而现在还缺关键字中的PART值，因此，这个供应商不可能出现在这个关系模式的具体关系中。,4.1.3删除异常 如果删去了一个供应 商供应 的全部零件，这时就会把该供应产的名字连同他的所在城市CITY等信息都删去了，这是因为 删去了关键字的组成部分PART的全部值，而每个元组是由关键字的值来标识的。这
3、样就丢失了访供应商的名字SN和所在城市CITY的信息。,4.1.4潜在的不一致性 作为冗余的后果，有可能更新了关系中一个元组中的供应 商所在的城市而忘了更新另一元组中同一供应商的所在的城市。于是，关系中包含的信息可能不是像我们以为的那样每一供应商都有唯一的城市所在地。,4.2函数信赖性,4.2.1函数依赖 定义4.1 设有关系模式R（U），其中U=U=A1 , A2 , ,An ,X、Y U，r 是R的任何一个可能的关系，u、v 是r中的任意两个元组。如果uX= vX蕴含uY= vY，那么我们说X函数决定Y，或Y函数依赖于X，记为X Y。,4.2.2函数依赖的蕴涵性 定义4.2 设有R（U）为
4、一个关系模式，F是R（U）上的一个已给定的函数依赖集，X，Y是U的子集。如果对R（U）的每一个满足F中的函数依赖的关系 r ，也满足X Y，则说F逻辑蕴涵X Y。,一般来说，由函数依赖集F可以导出不止一个函数依赖，而是一组函数依赖，即另一个函数依赖集。我们把被F逻辑蕴含的所有函数依赖的集合称为F的闭包，以F+表示。如果F+=F，则说明F是一个全函数信赖族。,例41 设R（U，F），其中U=A，B，C，F=AB，BC。那时， F+由所有这样的函数依赖XY组成： X含有A。例如ABCAB，ABBC，AC。 X含有B但不含A，且Y不含A。例如BCB，BC，B。 XY是CC和C其中之一。,于是，我们有
5、 F+= A，AA，AB，AC，AAB，AAC，ABC，AABC， AB，ABA，ABB，ABC，ABAB，ABAC，ABBC，ABABC，,ABC，ABCA，ABCB，ABCC，ABCAB，ABCAC，ABCBC，ABCABC， AC，ACA，ACB，ACC，ACAB，ACAC，ACBC，ACABC， B，BB，BC，BBC，BC，BCB，BCC，BCBC，C，CC,4.2.3关键字 定义4.3 设有关系模式R（U，F），其中F是它的函数依赖集，X是U的一个子集。如果 1）X A1A2An F+； 2）不存在X的真子集Y，使得Y A1A2An F+。 则称X是R的一个关键字。,例42 在商品
6、供应关系模式S（SN，CITY，PART，QTY）中，属性组SN，PART函数决定SN，CITY，PART，QTY，而单个属性SN或PART都不能，因此属性组SN，PART是S的一个关键字，事实上S只有这一个关键字。 例41中的关系R和依赖集F，R存在一个关键字，即A，因为AABC，而任何不包含A的X都不能函数决定ABC。,4.3关于函数信赖性的公理系统,4.3.1阿姆斯特朗公理 阿姆斯特朗公理 设关系模式R（U，F），其中U是它的全部属性的集合，F是U上的一个函数依赖集。对R（U，F）来说有以下推导规则： （1）自反性 如果Y X U，则F逻辑蕴涵XY。,（2）增广性 如果X U，Y U，Z
7、 U，且F逻辑蕴涵X Y，则F逻辑蕴涵XZYZ。 （3）传递性 如果X U，Y U，Z U，且F逻辑蕴涵X Y,YZ, 则F逻辑蕴涵XZ。 阿姆斯特朗公理系统由以上三条热传导规则组成，其中第一条实际上跟F无关，它总是成立的（平凡的函数依赖）。,引理4.1阿姆斯特朗公理是有效的。换句话说，若XY能从F利用公理推出，则在F为真的任何关系里，XY也真。 证明： 显然，自反性是有效的。不可能有一个关系r，它的某两个元组在X上相同而在X的某个子集上不相同。, 对于增广性，我们假设有一个关系r，它满足XY，且有两个元组u和v，它们 在属性XZ上相同，但在YZ上不同。既然它们不可能在Z上不同， u和v一定是
8、在Y的某属性上不同。但u和v在X上相同而在Y上不相同是与在r上成立XY的假设矛盾的。, 对于传递性，设r是R的任意一个关系，u，v是r的任意两个元组。如果uX=vX，则由XY，应有uY=vY，又由YZ，推出有uZ=vZ。也就是说当uX=vX时有uZ=vZ。这就说明XZ成立，即传递性是正确的。 证毕。,从阿姆斯特朗公理能导出若干条其他推导规则。在下一个引理里，我们给出其中的三个。 引理4.2 1）合并律：若XY且XZ，则有XYZ。 2）伪传递律：若XY且WYZ，则有XYZ。 3）分解律：若XY且Z Y，则有XZ。,证明： 由XY利用增广性得XXYX（即XYX），由XZ利用增广性得YXYZ。再利用
9、传递性，由XYX和YXYZ推出XYZ。, 由XY和增广性得WXWY，又已知WYZ，故按传递性有WXZ。 由A1和A3立即可得分解律。 合并律和分解律的一个重要推论是：如果A1A2A k是属性集，则XA1A2A k的充分必要条件是XAi（i=1，2，k）成立。,4.3.2阿姆斯特朗公理的完备性 定义4.4 设R（U，F）是属性集U上的一个关系模式，F是U上的一个函数依赖集，XU。我们定义XF+ =A|X A能由F根据阿姆斯特朗公理推出，把XF+称为属性集X关于函数依赖集F的闭包。,例43 设F=AB，BC是关系模式R（A，B，C）的一个函数依赖集，则 （A） F+=A，B，C （B） F+=B，
10、C （C） F+=C （BC） F+=B，C,引理43 设F是属性集U上的一个函数依赖集，XY能用Armstrong公理从F推出的充分必要条件是YX F+。 证明： 必要性：设Y=A1A2Ak，AiU（i=1，2，k）是单个属性。如果用Armstrong公理从F能推出XY，则根据分解规则，有XAi（i =1，2，k），于是由XF+的定义知Ai XF+ （i =1，2，k），从而YXF+。, 充分性：设Y同上，如果YXF+ ，由定义44可知能用Armstrong公理从F可以推导出XAi（i=1，2，k）。再由合并规则可知能用Armstrong公理从F可以推导出XY。,定理41 Armstrong
11、公理是有效的和完备的。 有效性已在引理41给出。这里我们只需要证明完备性。 证明方法如下：,设F是属性集U上的个函数依赖集，假定有一个函数依赖XY不能从F根据Armstrong公理推导出来。对此，我们只需要证明以下两部分： 第一，F中的所有函数依赖均成立；,第二，XY不成立，即F不逻辑蕴涵XY。 为此，我们构造一个如图41所示的R（U，F）的关系r，其中有两个元组v、u， XF+是对于F的属性集闭包。 图41 R（U，F）的关系r,为了证明F中的所有函数依赖在r上均成立，设VW是F中的任一函数依赖。V有两种情况： VXF+。这时，根据引理43有XV。按假设VW，根据函数依赖的可传递性，可推出X
12、W成立，因而有W XF+。既然V、W均包含于XF+ ，那么由图41可知，u、v两个元组在V、W上的值相同，所以VW在关系r中成立。 。由图41可见，V在u、v两个元组上的属性值必不一致。这时，不管是否存在WXF+，VW在关系r中一定成立。,结论：只要XY不能根据Armstrong公理从F中推导出来，F就不逻辑蕴涵XY。换句话说，凡是被F逻辑蕴涵的函数依赖一定能用Armstrong公理推导出来。证毕。 从Armstrong公理的完备性和有效性能推出两条重要的结论：, 我们曾定义XF+是这样的属性集合，对于集合中的每一个A，能从F借助公理导出XA。现在我们可以给出一个等价的定义： XF+是所有那样
13、的属性A的集合，对于每个A，XA被F逻辑蕴涵。 代替定义F+是所有被F逻辑蕴涵的函数依赖之集合，也能定义F+是所有利用阿姆斯特朗公理从F导出的函数依赖之集合。,4.3.3闭包的计算 算法4.1 计算属性集X（X U）关于U上的函数依赖集F的闭包XF+ 。 输入：有限的属性集合U，它上面的函数依赖集F和U的一个子集X。 输出：X关于F的闭包XF+ 。,方法：按如下规则计算属性序列X（0），X（1） 。 1）令X（i）=X,i=0; 2）求B，这里B=A|(V)(W)(VWFV X（i）A W)；,3） X（i+1） = X（i）B; 4）判断X（i+1） = X（i） ？ 5）若否，则使用i+1
14、来取代i，返回第二步； 6）若相等，则XF+就是X（i） ，算法终止。,例44 已知关于模式R（U，F），U=A，B，C，D，E，G，F包括以下八个函数依赖： ABC，CA，BCD，ACDB，DEG，BEC，CGBD，CEAG 计算（BD）F+。,设X=BD，按算法41，置X（0）=BD。为计算，我们逐一扫描F集合中的各个函数依赖，找出左端是B、D或BD的函数依赖，只有一个，即DEG。现在把E和G并入X（0），得到X（1）=BDEG。因为X（1）与X（0）不相等，所以再计算X（2）。在F集合中找出左端是 X（1）的子集的那些函数依赖，有DEG和BEC，于是X（2）= X（1）CEG=BCDEG
15、。,同样因为X（2）与X（1）仍然不相等，需再计算X（3），F集合中除了上述两个函数依赖外，还有CA、BCD、CGBD和CEAG的左端是X（2）的子集，这导致X=ABCDEG，它包括了U的全部属性。显然将有X（3）= X（4）=U。于是有（BD）F+=ABCDEG.。,4.3.4函数依赖集的等价、覆盖、和最小集 定义4.5 设有两个函数依赖集F和G，如果它们的闭包相等，则称这两个函数依赖集等价。 由定义可知，等价的函数依赖集所蕴涵的函数依赖是一致的。,引理4.4 F+=G+的充分必要条件是F G+且G F+。 证明：必要性显然，只证充分性。 若FG+，则XF+XG+。 任取XYF+，有YXF+XG+，所以，XY（G+）+=G+，即F+G+。 同理可证G+F+。得证F+=G+。,引理45 一个函数依赖集F总可找到另一个其所有函数依赖的右端均只有一个属性的函数依赖集G，F被G所覆盖。 证明：令G是由所有这样的XA组成的函数依赖集：如果XYF且AY，则XA在G中。,这时，显然能由XY按分解律导出XA，从而有GF+ 。但又有FG+成
