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

第四章 关系数据库设计理论 第一节 概述 第二节 函数依赖 第三节 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）＝