函数依赖理论第二讲.ppt

Cliquez pour modifier le style du titre,Cliquez pour modifier les styles du texte du masque,Deuxime niveau,Troisime niveau,Quatrime niveau,Cinquime niveau,*,*,函数依赖理论第二讲,主要内容,无关属性、正则覆盖、无损连接分解、有损连接分解,第一范式,(1NF),、第二范式,(2NF),、,Boyce-Codd,范式,(BCNF),、第三范式,(3NF),、,无关属性,给定,函数依赖集,F,及,F,，如果去除,或,的一个属性不会改变,F,+,，则称,该属性是无关的,。,给定,函数依赖集,F,及,F,，若,A,，且,F,逻辑蕴涵,(,F,-,),(,-,A,),，则属性,A,在,中是无关的（,左无关,）。,给定,函数依赖集,F,及,F,，若,A,，且,(,F,-,),(,(,-,A,),逻辑蕴涵,F,，则属性,A,在,中是无关的（,右无关,）。,无关属性检测算法,设,r,(,R,),为关系模式，,F,是函数依赖集，则检测,上的属性,A,左无关或右无关的算法分别如图,(a),或,(b),所示。,if,A,:,-,A,;,计算,F,下,的闭包,+,;,if,+,A,在,中是无关的,;,if,A,F,:=(,F,-,),(,(,-,A,);,计算,F,下,的闭包,+,;,if,A,+,A,在,中是无关的,;,(a),(b),图,5-9,无关属性检测算法,无关属性检测举例,设,F,AB,CD,A,E,E,C,，证明,C,在,AB,CD,中为无关属性。,证明：,由于,C,是,AB,CD,中的右边属性，依图,(b),的算法：,计算,F,：,F=,AB,D,A,E,E,C,；,计算,F,下,(,AB,),+,：,(,AB,),+,=ABCDE,；,判断,C,是否属于,(,AB,),+,：,C,ABCDE,。,因此，,C,是,AB,CD,中的无关属性,。证毕。,正则覆盖定义和计算方法,正则覆盖,(canonical cover),F,c,是一个依赖集，使得,F,逻辑蕴涵,F,c,中的所有依赖，,F,c,逻辑蕴涵,F,中的所有依赖，而且必须具有下列特性：,F,c,中的任何函数依赖都不包含无关属性；,F,c,中函数依赖的左半部都是唯一的,，即,F,c,中不存在两个依赖,1,1,和,2,2,，且,1,2,。,根据上述性质，计算,F,的正则覆盖,F,c,分为两个步骤：,合并函数依赖,：将,F,中所有形如,1,1,、,1,2,的函数依赖合并为,1,1,2,，得到新函数依赖集,F,。,去除无关属性,：对,F,中的每个函数依赖，依次判断是否包含无关属性。若发现无关属性，则用去除无关属性后的函数依赖代替,F,中的原函数依赖。,计算正则覆盖举例,考虑关系模式,r,(,R,),=r,(,A,B,C,),和函数依赖集,F,=,A,BC,B,C,A,B,AB,C,计算,F,的正则覆盖,F,c,。,第,1,步，合并函数依赖：,将,A,BC,和,A,B,合并为,A,BC,。,F=,A,BC,B,C,AB,C,。,第,2,步，去除无关属性：,对于,AB,C,，根据图,5-9(a),的算法可检测,A,是无关的。因此，去除无关属性,A,后，,AB,C,变为,B,C,，而,B,C,已在,F,中存在，则,F=,B,C,A,BC,。,对于,B,C,，由于其左右两边都为单属性，故不存在无关属性。,对于,A,BC,，根据图,5-9(b),的算法可检测,C,是无关的。因此，去除无关属性,C,后，,A,BC,变为,A,B,，,则,F=,B,C,A,B,。,F,中的函数依赖左半部都是唯一的，且都不存在无关属性，因此,F,c,=,B,C,A,B,。,无损连接分解,给定关系模式,r,(,R,),及函数依赖集,F,，若,r,(,R,),的任意一个满足函数依赖集,F,的关系实例,r,都有,=r,，其中,r,1,(R,1,),、,r,2,(R,2,),分别为分解后的子模式，则称该分解对于,F,是,无损连接,的。,无损连接分解能够根据分解后的关系通过连接来还原原来的关系实例。,如何判定一分解是否是无损的？,无损连接分解判断方法,给定关系模式,r,(,R,),及函数依赖集,F,，则将,r,(,R,),分解成,r,1,(R,1,),、,r,2,(R,2,),的分解是无损连接分解，当且仅当,F,+,包含函数依赖,R,1,R,2,R,1,或,R,1,R,2,R,2,。,因此，当一个关系模式分解为两个关系模式时，该分解为无损连接分解的,充要条件是两分解关系的公共属性包含,r,1,(,R,1,),的码或,r,2,(,R,2,),的码,。,无损连接分解判断举例,假设关系模式,r,(,R,)=,r,(,A,B,C,D,E,),F,=,A,BC,CD,E,B,D,E,A,，则,可将,r,(,R,),进行两种不同的分解：,分解,1,：,r,1,(,R,1,),=,r,1,(,A,B,C,),，,r,2,(,R,2,),=,r,2,(,A,D,E,),；,分解,2,：,r,1,(,R,1,),=,r,1,(,A,B,C,),，,r,2,(,R,2,),=,r,2,(,C,D,E,),。,对于分解,1,，,R,1,R,2,A,，且,A,R,1,，故此分解,是无损连接分解,。,而对于分解,2,，,R,1,R,2,C,，且,C,R,1,、,C,R,2,，故,此分解,不是无损连接分解,。,保持依赖分解,关系数据库模式分解的另一个目标是,保持依赖,。,给定关系模式,r,(,R,),及函数依赖集,F,，,r,1,(,R,1,),r,2,(,R,2,),.,r,n,(,R,n,),为,r,(,R,),的分解。,F,在,R,i,的投影,为,闭包,F,+,中所有只包含,R,i,属性的函数依赖的集合,，记为,F,i,。即如果,在,F,i,中，则,和,的所有属性均在,R,i,中。,称具有函数依赖集,F,的关系模式,r,(,R,),的分解,r,1,(,R,1,),r,2,(,R,2,),.,r,n,(,R,n,),为,保持依赖分解,，当且仅当,(,F,1,F,2,F,n,),+,=,F,+,。,保持依赖分解判断举例,设关系模式,r,(,R,)=,r,(,A,B,C,),，,F=,A,B,B,C,，有两种分解：,r,1,(,R,1,)=r,1,(,A,B,),、,r,2,(,R,2,),=r,2,(,B,C,),r,1,(,R,1,)=r,1,(,A,B,),、,r,2,(,R,2,),=r,2,(,A,C,),。,显然，,前一种分解是保持依赖分解,；,而后一种分解不是保持依赖分解,，因为分解后，函数依赖,B,C,既不能从,F,在,R,1,的投影,F,1,中推导出来，也不能从,F,在,R,2,的投影,F,2,中推导出来。,范式概述,基于函数依赖理论，关系模式可分成,第一范式,(1NF),第二范式,(2NF),第三范式,(3NF),Boyce-Codd,范式,(BCNF),这几种范式的要求一个比一个严格，它们之间的联系为,BCNF,3NF,2NF,1NF,。即满足,BCNF,范式的关系一定满足,3NF,范式，满足,3NF,范式的关系一定满足,2NF,范式，满足,2NF,范式的关系一定满足,1NF,范式。,第一范式,(1,NF),如果一关系模式,r,(,R,),的每个属性对应的域值都是不可分的（即原子的），则称,r,(,R,),属于第一范式，记为,r,(,R,),1NF,。,第一范式的目标是：,将基本数据划分成称为实体集或表的逻辑单元，当设计好每个实体后，需要为其指定主码。,第二范式,(2,NF),第二范式的目标是：,将只部分依赖于主码（即依赖于主码的部分属性）的数据移到其他表中。,也就是说，在满足第一范式的实体中，如果有复合主码（即多个属性共同构成主码），那么所有非主属性必须依赖于全部的主码，而不能只是依赖于部分的主码属性。,违背了,2NF,的模式，即存在非主属性对,候选码,的,部分依赖,，则可能导致例,5.1,所述的数据冗余及异常问题。,对于,非,2NF,范式的关系模式，可通过分解进行规范化，以,消除部分依赖,。如将关系模式,SCE,分解为关系模式,S,、,C,和,E,。这样在每个关系模式中，所有非主属性对候选码都是完全函数依赖，因此都属于,2NF,范式。,2NF,范式虽然消除了由于非主属性对主码的部分依赖所引起的冗余及各种异常，但,并没有排除,传递依赖,。,因此，,还需要对其进一步规范化,。,Boyce-Codd,范式,(,BCNF),给定关系模式,r,(,R,),及函数依赖集,F,，若,F,+,中的所有函数依赖,(,R,，,R,),至少满足下列条件之一：,是平凡函数依赖,(,即,),；,是,r,(,R,),的一个,超码,(,即,+,包含,R,的全部属性,),。,即起决定作用的属性必须是超码！,则称,r,(,R,),属于,Boyce-Codd,范式,，记为,r,(,R,),BCNF,。,换句话说，在关系模式,r,(,R,),中，,如果,F,+,中的每一个非平凡函数依赖的,决定属性集,都包含候选码,，则,r,(,R,),BCNF,。,特别说明：,为确定,r,(,R,),是否满足,BCNF,范式，,必须考虑,F,+,而不是,F,中的每个依赖,。,从函数依赖角度可得出，一个满足,BCNF,的关系模式必然满足下列结论：,所有,非主属性,都,完全函数依赖于,每个,候选码,；,所有,主属性,都,完全函数依赖于,每个,不包含它的候选码,；,没有,任何属性,完全函数依赖于,非候选码,的任何一组属性。,BCNF,范式排除了：,任何属性,(,包括主属性和非主属性,),对,候选码,的,部分依赖,和,传递依赖,；,主属性之间的,传递依赖,。,Boyce-Codd,范式判断举例,例,1,r,(,R,),=,r,(,A,B,C,),，,F,=,A,B,B,C,。,r,(,R,),的,候选码为,A,，,r,(,R,),BCNF,，因为函数依赖,B,C,中的,决定属性,B,不是超码,。,例,2,r,(,R,),=,r,(,A,B,C,),，,F,=,AB,C,C,A,。,r,(,R,),的候选码为,AB,或,BC,，,r,(,R,),BCNF,，因为,C,A,的,决定属性,C,不是超码,。,例,3,r,(,R,),=,r,(,A,B,C,),，,F,=,AB,C,BC,A,。,r,(,R,),的候选码为,AB,或,BC,，,r,(,R,),BCNF,，因为两个函数依赖中的,决定属性,AB,或,BC,都是,r,(,R,),的候选码,。,Boyce-Codd,范式存在问题,对于非,BCNF,范式的关系模式，可通过分解进行规范化，以消除,部分依赖,和,传递依赖,。,将例,5.13,中的,r,(,R,),分解为,r,1,(,R,1,),=,r,1,(,A,B,),、,r,2,(,R,2,),=,r,2,(,B,C,),或,r,1,(,R,1,),=,r,1,(,A,B,),、,r,2,(,R,2,),=,r,2,(,A,C,),显然，这两种分解得到的,r,1,(,R,1,),和,r,2,(,R,2,),都属于,BCNF,范式。,但是，,后一种分解不是保持依赖分解,（例,5.12,已分析）。,因此，,满足,BCNF,范式要求的模式分解，可能不是保持依赖分解,。,第三范式,(3,NF),给定关系模式,r,(,R,),及函数依赖集,F,，若对,F,+,中的所有函数依赖,(,R,R,),至少满足下列条件之一：,是平凡函数依赖,(,即,),；,是,r,(,R,),的一个,超码,(,即,+,包含,R,的全部属性,),；,-,中的每个属性是,r,(,R,),的,候选码的一部分,。,则称,r,(,R,),属于,第三范式,，记为,r,(,R,),3NF,。,3NF,与,BCNF,范式的区别在于第,3,个条件。,放松之处：,允许存在,主属性,对候选码的传递依赖和部分依赖,。,注意：,3NF,的第,3,个条件,不要求,-,中的每个属性,必须包含在,r,(,R,),的一个候选码,中，,即,中的每个属性,可以包含在,r,(,R,),的不同候选码,中,第三范式的目标是：,去掉表中不依赖于主码的数据。,也就是说，在满足第二范式的实体中，,非主属性不能依赖于另一个非主属性,，即所有的,非主属性,应该直接依赖于,全部的主属性,（即,必须完全依赖,，,这是,2NF,的要求,），并且彼此之间,无相互依赖,关系（即,不能存在部分依赖,，,这是,3NF,的要求,）。,换一句话说，,非主属性,不能包括它们自己的属性，如果属性不包括属性，则它们就是真正的实体。,3NF,范式判断举例,例,1 r,(,R,),=,r,(,A,B,C,),，,F,=,A,B,B,C,。,r,(,R,),的,候选码为,A,，,r,(,R,),3NF,，且,r,(,R,),BCNF,。,例,2 r,(,R,),=,r,(,A,B,C,),，,F,=,AB,C,C,A,。,r,(,R,),的候选码为,AB,或,BC,，,r,(,R,),3NF,，但,r,(,R,),BCNF,。,例,3 r,(,R,),=,r,(,A,B,C,),，,F,=,AB,C,BC,A,。,r,(,R,),的候选码为,AB,或,BC,，,r,(,R,),3NF,，且,r,(,R,),BCNF,3NF,与,BCNF,比较,BCNF,比,3NF,严格。,BCNF,要求所有的非平凡函数依赖,中的,是超码,，而,3NF,则放松了该约束，允许,不是超码。,若关系模式属于,BCNF,范式就一定属于,3NF,范式。反之，则不一定成立。,3NF,存在数据冗余和异常问题,，而,BCNF,是基于函数依赖理论能够达到的最好关系模式,。,BCNF,范式分解是,无损分解,，但,不一定是保持依赖分解,；而,3NF,分解既是,无损分解,，又是,保持依赖分解,。,谢谢观看！,