文档详情

数据库系统原理及应用 丁忠俊 第四章 关系数据库理论.ppt

发布:2017-05-19约3.51万字共99页下载文档
文本预览下载声明
第四章 关系数据库设计理论 第一节 概述 第二节 函数依赖 第三节 F D 公理 四.FD集的等价和覆盖(求F 的最小集) 定义:设F和G是两个函数依赖集,若F+=G +则称F和G等价;如果F和G等价,则说F覆盖G,同时G覆盖F。 引理1:设F和G是函数依赖集,则F + =G +的充分必要条件是F G + 且G F + 。 证明略。 这说明,检查F和G是否等价并不困难,只要检查 F ? G +且G ? F +是否成立。 检查F ? G + 是否成立,即F中的每一个FD是否属于G + 。 例如:对于X Y ∈F,则在G上计算X + ,看是否满足Y X + ,若满足,则X Y ∈G + 。继续检查其他所有依赖,若全部满足,则F G + 。同理,对G中每个依赖作同样的处理来检查G F +才能确定F + =G +. 引理2:每一个函数依赖集F都可以由一个右端只有单个属性的函数依赖集G所覆盖。 证明:设G由行为X A(A为单属性)的函数依赖组成。A∈Y且X Y在F中。 此时,显然能从X Y按分解规则导出X A,从而有G F + 。 . 反之,如果Y=A1A2…An,而且X A1,X A2,…,X An在G中,可根据合并规则得:X A1…An,因而有F G + 。 由此得:F=G,即F被G覆盖。 在研究FD时,它的最小集是很有用处的。 定义:对于给定的一个函数依赖集F,当满足下列条件时,称为F的最小集,记为F ’(最小集也称为最小覆盖)。 (1) F ’的每个依赖的右部都是单个属性; (2)对于F ’的任一函数依赖X A来说, F ’-﹛X A﹜与F ’都不等价; (3)对于F ’的任一函数依赖X A来说,( F ’- ﹛X A﹜)U ﹛Z A﹜ 与F ’都不等价,其中Z为X的任一子集。 这个定义中:条件(1)保证了每个依赖的右边都是单属性 条件(2)保证在F中不存在多余的依赖 条件(3) )保证在F中的每一个依赖的左边没有多余的属性 定理:每一个函数依赖集F都与它的最小依赖集F ’等价 这个定理的证明按最小依赖集的定义考虑其三个条件,证明的过程也是计算最小集的过程。证明过程见书。 例:设F=﹛AB C,C A, BC D,ACD B, D EG, BE C , CG BD,CE AG﹜求F ’ 解:按最小覆盖依赖集的定义,分别考虑三个条件。 (1)用分解规则,将F中所有的FD变为右边是单属性的依赖 AB C,C A, BC D, ACD B, D E, D G, BE C , CG B,CG D,CE A,CE G (2)去掉F中函数依赖左边多余的属性 方法:逐个检查F中左边非单属性的依赖,如:XY A,若判Y是否为多余属性,只要在F中求X + ,若X +包含A,则Y为多余属性,否则Y不多于,依法判F中其它FD。 考察:ACD B ∵(CD) + =CDAEGB ∴A为多余属性,应去掉,即用CD B代替ACD B 再考察:CE A (C )=CA (C A) ∴E为多余属性,用C A代替CE A AB C,C A, BC D, CD B, D E, D G, BE C ,CG B,CG D,C A,CE G (3)去掉F中多余的依赖 方法:从F中的第一个FD开始,将它从F中去掉(设为X Y),然后从剩下的依赖求X,看X是否包含Y,若包含,则X Y是多余的,应去掉,这样依次做下去。 显然:上面F中有两个C A,应去掉一个 .考察;CG B 先去掉CG B则:CG D保留 (CG)=CGD (CG D) (CG)=CGDB (CD B) ∴CG B为多余FD。 得: F’={AB C,C A, BC D, CD B, D E, D G, BE C , CG D,CE G} 注:求出的F’不是唯一的。 注:依F中的顺序不同,则F’是不同的 若先考察:CD B ∵(CD)=CDG (D G) (CD)=
显示全部
相似文档