数据依赖与关系模式规范化PPT课件

第10章数据依赖与关系模式规范化,2008.12,Lastupdate:Dec.2008,-,2,目录Contents,10.1概述10.2函数依赖与范式10.3多值依赖与范式10.4模式分解理论,Lastupdate:Dec.2008,-,3,10.1概述,10.1.1关系模式的设计10.1.2“不好的”（Bad）关系模式10.1.3如何设计“好的”关系模式10.1.4权衡：规范化若BA，则称此函数依赖为非平凡依赖(NontrivialDependency);若BA=，则称此函数依赖为完全非平凡依赖(CompletelyNontrivialDependency)。例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)Grade平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)Cno对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明，我们总是讨论非平凡函数依赖。,Lastupdate:Dec.2008,-,28,10.2.1函数依赖,平凡依赖规则(TheTrivial-dependencyRule)ABABA。定义:完全依赖/部分依赖设A,B是某模式的两个不同属性集,若有AB，且不存在CA，使CB，则称AB为完全依赖(FullDependency),记为：AB；否则称为部分依赖(PartialDependency),记为：AB。例:在关系SC(Sno,Cno,Grade)中，由于：SnoGrade，CnoGrade，因此：(Sno,Cno)Grade。,Lastupdate:Dec.2008,-,29,10.2.1函数依赖,定义：传递依赖A,B,C是某模式的三个不同属性集，若有：AB,BA,BC,则称C传递函数依赖于A,记为：AC。为了使得函数依赖在表示形式上的简单化，传递函数依赖与非传递函数依赖在表示形式上没有区别。传递规则(TheTransitiveRule)AB,BCAC。例:在关系Std(Sno,Sdept,Deanname)中，有：SnoSdept，SdeptDeanname，所以,Deanname传递函数依赖于Sno，即SnoDeanname,Lastupdate:Dec.2008,-,30,10.2.2范式,回顾概念键(key)：在关系模式R(U)中，如有KU且满足：KU,则K称为R的一个侯选键(CandidateKey)，简称键。也就是说：决定性：这个属性（组）K的值唯一地决定了其他属性的值（因而也决定了整个元组）；最小性条件：这个属性（组）K的任何真子集均不满足决定性条件。主键(PrimaryKey)：在关系模式机器实现时，若关系模式R有多个候选码，则选定其中的一个做为主键。其他键称为候补键(AlternateKey)。超键(Superkey)：关系模式中包含键的属性(组)称为超键。全键(allkey)：主键是由所有的属性构成的，这称为全键。,Lastupdate:Dec.2008,-,31,10.2.2范式,回顾概念(cont.)主属性(集)由关系模式R的所有键中的属性所构成的集合被称为关系模式R的主属性集。主属性集中的属性被称为关系模式R的主属性。非主属性(集)由主属性集之外的其它属性所构成的集合被称为关系模式R的非主属性集。非主属性集中的属性被称为关系模式R的非主属性。,Lastupdate:Dec.2008,-,32,10.2.2范式,范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)各种范式之间存在联系：,Lastupdate:Dec.2008,-,33,10.2.2范式,定义:1NF设有一个关系模式R,若R的任一关系实例r中的属性值均是原子数据(属性都是不可分的基本数据项),则称R属于1NF，记为R1NF。注1NF条件是传统关系数据库系统的基本要求，目前大多数RDBMS均要求如此。但是满足第一范式的关系模式并不一定是一个好的关系模式。突破这一条件称非第一范式(non-firstnormalform,NF2)条件。E/R中的非原子属性在转化为关系时要这样处理：对集合属性：纵向展开对元组属性：横向展开,Lastupdate:Dec.2008,-,34,10.2.2范式,定义:2NF设有一个关系模式R1NF,若R的每个非主属性均完全函数依赖于键,则称R属于2NF，记为R2NF。注A.R2NFR1NFB.考察R(SNO,CNO,G,T,DEPT)1NF，因SNO,CNOG,CNOT,TDEPTCNODEPTCNOT,DEPT故Key=SNO,CNO。但KeyT,DEPT,故R2NF。,Lastupdate:Dec.2008,-,35,10.2.2范式,R(SNO,CNO,G,T,DEPT)不是一个好的关系模式数据冗余度大插入异常删除异常更新复杂原因T,DEPT部分函数依赖于键SNO,CNO。,Lastupdate:Dec.2008,-,36,10.2.2范式,解决方法模式分解：消除这些部分函数依赖R1(SNO,CNO,G)2NF,R2(CNO,T,DEPT)2NF。但R2仍有问题：c01t1d1c02t1d1冗余c03t1d1c04t2d2原因：Key=CNO，因TDEPT,而T非超键,DEPT又非主属性。采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。,Lastupdate:Dec.2008,-,37,10.2.2范式,定义:3NF设有一个关系模式R1NF，若R的任一非平凡函数依赖XA满足下列两个条件之一:(1)X是超键,(2)A是主属性，则称R属于3NF，记为R3NF。注A.若R3NF，意味着：A非主属性，X又非超键：(1)X是键的真子集：非主属性A部分依赖于键；(2)X既非超键又非键的真子集：KeyX,XAKeyA,即：非主属性A传递依赖于键。故3NF消除了非主属性对键的部分依赖和传递依赖。B.R3NFR2NF。,t,Lastupdate:Dec.2008,-,38,10.2.2范式,例：将关系模式R(SNO,CNO,G,T,DEPT)分解得到R1(SNO,CNO,G)2NF,R2(CNO,T,DEPT)2NF，由于关系模式R2中存在非主属性DEPT对键的传递依赖，所以采用投影分解法，把R2分解为两个关系模式，以消除传递函数依赖：R21(CNO,T)3NF,R22(T,DEPT)3NF,即CNOT,TDEPT。,Lastupdate:Dec.2008,-,39,10.2.2范式,若R3NF，则R的每一个非主属性既不部分函数依赖于候选键也不传递函数依赖于键。采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,Lastupdate:Dec.2008,-,40,10.2.2范式,定义:BCNF设有一个关系模式R1NF，若R的任一非平凡函数依赖XA满足下列条件：决定子X必是超键，则称R属于BCNF，记为RBCNF。注：A.RBCNFR3NF。B.BCNF消除了(非主/主)属性对键的部分依赖和传递依赖。C.关系模式达到BCNF后，在函数依赖范畴内已彻底规范化了，并消除了冗余和异常。D.任何全键关系模式必属于BCNFE.任何两属性关系模式必属于BCNFF.关系模式无损分解成BCNF的策略,Lastupdate:Dec.2008,-,41,10.2.2范式,D.任何全键关系模式必属于BCNF证明：设R(A1,A2,An)是全键关系模式,即Key=A1,A2,An,反证法：假设RBCNF，则必存在一非平凡函数依赖XAi,而决定子X不是超键。注意,XA1,A2,An，AiX；XA1,A2,AnAi=A1,A2,Ai-1,Ai+1,An，故Key=A1,A2,Ai-1,Ai+1,An。这与全键的条件矛盾！命题得证。,Lastupdate:Dec.2008,-,42,10.2.2范式,E.任何两属性关系模式必属于BCNF证明：设R(A1,A2)是两属性关系模式，则有4种非平凡函数依赖的情形：(1)无任何非平凡的函数依赖：无冒犯BCNF条件的函数依赖或R是全键，故RBCNF。(2)A1A2，但A2A1：Key=A1，唯一的决定子A1是超键，故RBCNF。(3)A2A1，但A1A2：Key=A2，唯一的决定子A2是超键，故RBCNF。(4)A1A2，且A2A1：Key1=A1,Key2=A2，两个决定子均是超键，故RBCNF。,Lastupdate:Dec.2008,-,43,10.2.2范式,F.关系模式无损分解成BCNF的策略启发式算法设关系模式R(XAB)，X,A,B均是R的属性(子集)，(1)针对冒犯BCNF条件的某个非平凡函数依赖：XA,(X非超键),分解成两个模式:R1(XA),R2(BX)。一般地，R1BCNF，R2BCNF。(2)对不属于BCNF的模式R2(和R1)重复步骤(1)，直到全部属于BCNF为止。,Lastupdate:Dec.2008,-,44,10.2.2范式,例：M(title,year,length,color,star,star-gender,star-add,studio,studio-add,studio-class)根据通常的语义，有以下函数依赖：(1)starstar-gender,star-add(2)studiostudio-add,studio-class(3)title,yearlength,color,studio故Key=title,year,star。因式(1),(2),(3)均冒犯BCNF条件，故MBCNF。,Lastupdate:Dec.2008,-,45,10.2.2范式,模式分解对式(1)，将M分解成：STAR(star,star-gender,star-add)BCNFM1(title,year,length,color,studio,studio-add,studio-class,star)因M1的Key未变，且式(2),(3)仍成立，故M1BCNF。对式(2)，将M1分解成：STUDIO（studio,studio-add,studio-class）BCNFM2（title,year,length,color,star,studio）因M2的Key未变，且式(3)仍成立，故M2BCNF。对式(3)，将M2分解成：MOVIE（title,year,length,color,studio）BCNFSTARS-IN（title,year,star）BCNF。全键关系模式。故，将M规范化成BCNF的一个无损分解为：=STAR,STUDIO,MOVIE,STARS-IN。,Lastupdate:Dec.2008,-,46,关系模式规范化的基本步骤,关系模式规范化的基本步骤1NF消除非主属性对键的部分函数依赖2NF消除非主属性对键的传递函数依赖3NF消除主属性对键部分和传递函数依赖BCNF,Lastupdate:Dec.2008,-,47,目录Contents,10.1概述10.2函数依赖与范式10.3多值依赖与范式10.4模式分解理论,Lastupdate:Dec.2008,-,48,10.4模式分解理论,模式分解理论（仅在函数依赖范畴内讨论）定义逻辑蕴涵设一关系模式R(U,F)，其中U为R的属性集，F为R的函数依赖集，若对任意的rR，函数依赖XY在r上实际是成立的，则此时称F逻辑蕴涵XY。记为F|=XY。e.g.若F=AB,BC,则F|=AC。定义F的闭包(Closure)F+函数依赖集F所逻辑蕴涵的函数依赖的全体，称F的闭包。记为F+。即：F+=XY|F|=XY。,Lastupdate:Dec.2008,-,49,10.4模式分解理论,Armstrom公理(Armstrongsaxioms):三条基本推理规则自反律(Reflexivity)：IfYXU，ThenXY.扩展律(Augmentation)：IfXYandZU,ThenXZYZ.传递律(Transitivity)：IfXYandYZ,ThenXZ.F+可由Armstrong公理从F导出,Lastupdate:Dec.2008,-,50,10.4模式分解理论,定义关系模式R的一个分解/关系r在Ui上的投影/函数依赖集F在Ui上的投影设一关系模式R(U,F),若可用一个关系模式的集合R1(U1),R2(U2),Rk(Uk)，U1U2Uk=U来取代原关系模式R，则称此集合为R的一个分解。记为=R1,R2,Rk。关系rR在Ui上的投影定义为：Ui(r)=tUi|tr。函数依赖集F在Ui上的投影定义为：Ui(F)=XY|XYF+XYUi。,Lastupdate:Dec.2008,-,51,10.4模式分解理论,定义无损分解(losslessdecomposition)设=R1(U1),R2(U2),Rk(Uk)是对关系模式R(U)的一个分解，若对任意的关系rR满足：r=U