kc第8讲数据库规范化理论.ppt

第8讲:(第7章)关系数据库设计：规范化理论(一)重庆大学计算机学院,课程名称:数据库系统-,第8讲：关系数据库设计：规范化理论(一),项目驱动目标：如何得到一个优化的关系数据库结构！一、良好关系模式的标准二、第一范式(1NF)三、函数依赖四、巴赫范式while(changestoresult)doforeachinFdobeginifresultthenresult:=resultend例子：计算属性集的闭包,5.2属性集的闭包,5-6什么是属性集的闭包？,5-7如何计算a+？,问题7答案,ExampleofAttributeSetClosure,R=(A,B,C,G,H,I)F=ABACCGHCGIBH(AG)+1.result=AG2.result=ABCG(ACandAB)3.result=ABCGH(CGHandCGAGBC)4.result=ABCGHI(CGIandCGAGBCH)IsAGacandidatekey?IsAGasuperkey?DoesAGR?=Is(AG)+RIsanysubsetofAGasuperkey?DoesAR?=Is(A)+RDoesGR?=Is(G)+R,5.2属性集的闭包,UsesofAttributeClosure,Thereareseveralusesoftheattributeclosurealgorithm:判定超键：Testingforsuperkey:Totestifisasuperkey,wecompute+,andcheckif+containsallattributesofR.判定函数依赖：TestingfunctionaldependenciesTocheckifafunctionaldependencyholds(or,inotherwords,isinF+),justcheckif+.Thatis,wecompute+byusingattributeclosure,andthencheckifitcontains.Isasimpleandcheaptest,andveryuseful计算F+：ComputingclosureofFForeach属性集R,wefindtheclosure+,andforeachS+,weoutputafunctionaldependencyS.,5.2属性集的闭包,5-8属性集闭包有何用途？,CanonicalCover-要求,三大冗余现象：Setsoffunctionaldependenciesmayhaveredundantdependenciesthatcanbeinferredfromtheothers依赖冗余现象：Forexample:ACisredundantin:AB,BCPartsofafunctionaldependencymayberedundant右方冗余现象：E.g.:onRHS:AB,BC,ACDcanbesimplifiedtoAB,BC,AD左方冗余现象：E.g.:onLHS:AB,BC,ACDcanbesimplifiedtoAB,BC,AD正则覆盖的直观要求：Intuitively,acanonicalcoverofFisa“minimal”setoffunctionaldependenciesequivalenttoF,havingnoredundantdependenciesorredundantpartsofdependencies(冗余属性)(除不要求右方单属性外，等效于：1数据库原理王能斌，p.380,最小函数依赖集概念),5.3正则覆盖,5-9什么是正则覆盖？,返回,Extraneous多余Attributes,ConsiderasetFoffunctionaldependenciesandthefunctionaldependencyinF.AttributeAisextraneousinifAandFlogicallyimplies(F)(A).AttributeAisextraneousinifAandthesetoffunctionaldependencies(F)(A)logicallyimpliesF.Note:implicationintheoppositedirectionistrivial微不足道的ineachofthecasesabove,sincea“stronger”functionaldependencyalwaysimpliesaweakerone.即上述左、右方是相互蕴含的(等价的)!(学生作业)Example:GivenF=AC,ABCBisextraneousinABCbecauseAC,ABClogicallyimpliesAC(I.e.theresultofdroppingBfromABC).Example:GivenF=AC,ABCDCisextraneousinABCDsinceABCcanbeinferredevenafterdeletingC,5.3正则覆盖,5-10正则覆盖中的冗余属性指什么？,TestingifanAttributeisExtraneous,ConsiderasetFoffunctionaldependenciesandthefunctionaldependencyinF.左方冗余属性的判定：TotestifattributeAisextraneousincompute(A)+usingthedependenciesinFcheckthat(A)+contains;ifitdoes,Aisextraneousin右方冗余属性的判定：TotestifattributeAisextraneousincompute+usingonlythedependenciesinF=(F)(A),checkthat+containsA;ifitdoes,Aisextraneousin,5.3正则覆盖,5-11如何判定是否存在冗余属性？,CanonicalCover-定义及计算,形式化定义：AcanonicalcoverforFisasetofdependenciesFcsuchthatFlogicallyimpliesalldependenciesinFc,andFclogicallyimpliesalldependenciesinF,andNofunctionaldependencyinFccontainsanextraneousattribute,andEachleftsideoffunctionaldependencyinFcisunique.Havingnoredundantdependencies(注：书中没有这一条!)TocomputeacanonicalcoverforF:repeatUsetheunionruletoreplaceanydependenciesinF11and12with112FindafunctionaldependencywithanextraneousattributeeitherinorinIfanextraneousattributeisfound,deleteitfromuntilFdoesnotchangeNote:Unionrulemaybecomeapplicableaftersomeextraneousattributeshavebeendeleted,soithastobere-applied例子：计算正则覆盖,5.3正则覆盖,5-12如何计算函数依赖集的正则覆盖？,ComputingaCanonicalCover-例子,R=(A,B,C)F=ABCBCABABCCombineABCandABintoABCSetisnowABC,BC,ABCAisextraneousinABCCheckiftheresultofdeletingAfromABCisimpliedbytheotherdependenciesYes:infact,BCisalreadypresent!SetisnowABC,BCCisextraneousinABCCheckifACislogicallyimpliedbyABandtheotherdependenciesYes:usingtransitivityonABandBC.CanuseattributeclosureofAinmorecomplexcasesThecanonicalcoveris:ABBC,5.3正则覆盖,Lossless-joinDecomposition,形式化定义：ForthecaseofR=(R1,R2),werequirethatforallpossiblerelationsronschemaR（注：多个模式分解类似）r=R1(r)R2(r)充分必要条件(仅一分为二情形)：AdecompositionofRintoR1andR2islosslessjoinifandonlyifatleastoneofthefollowingdependenciesisinF+:R1R2R1R1R2R2例子：无损连接分解(一分为二情形),5.4无损连接分解与依赖保持,5-12什么叫无损连接分解？,Example-无损连接分解,R=(A,B,C)F=AB,BCCanbedecomposedintwodifferentways分解方式一：R1=(A,B),F1=AB;R2=(B,C),F1=BCLossless-joindecomposition:R1R2=BandBBC即R1R2R2Dependencypreserving分解方式二：R1=(A,B),F1=AB;R2=(A,C),F1=ACLossless-joindecomposition:R1R2=AandAAB即R1R2R1Notdependencypreserving(cannotcheckBCwithoutcomputingR1R2),5.4无损连接分解与依赖保持,DependencyPreservation,形式化定义：LetFibethesetofdependenciesF+thatincludeonlyattributesinRi.Adecompositionisdependencypreserving,if(F1F2Fn)+=F+依赖不保持的缺点：Ifitisnot,thencheckingupdates数据更新forviolationoffunctionaldependenciesmayrequirecomputingjoins,whichisexpensive.,5.4无损连接分解与依赖保持,5-13什么叫依赖保持？,5-14依赖不保持的分解有何不足？,TestingforDependencyPreservation,计算方法：TocheckifadependencyispreservedinadecompositionofRintoR1,R2,Rnweapplythefollowingtest(withattributeclosuredonewithrespecttoF)result=while(changestoresult)doforeachRiinthedecomposition根据各子模式上的函数依赖判定决定属性集t=(resultRi)+Riresult=resulttIfresultcontainsallattributesin,thenthefunctionaldependencyispreserved.WeapplythetestonalldependenciesinFtocheckifadecompositionisdependencypreserving效率：Thisproceduretakespolynomialtime,insteadoftheexponentialtimerequiredtocomputeF+and(F1F2Fn)+例子：判定依赖保持,5.4无损连接分解与依赖保持,5-15如何检查分解是否保持依赖？,Example-判定保持依赖,R=(A,B,C)F=ABBCKey=ARisnotinBCNFDecompositionR1=(A,B)F1=ABR2=(B,C)F2=BCR1andR2isinBCNFLossless-joindecompositionDependencypreservingAB,BC显然属于(F1F2)+判定AC是否属于(F1F2)+最初：result=A然后：t=(resultR1)+R1=A+A,B=A,Bresult=A,B最终：t=(resultR2)+R2=B+B,C=B,Cresult=A,B,C可见C属于属性集result中,故为依赖保持的分解！,5.4无损连接分解与依赖保持,假设F还有AC,项目驱动目标：关系数据库优化设计有哪些有效的实现途径：一、实用的范式分解算法二、多值依赖与4NF知识三、关系模式设计注意事项四、触发器及其用途主要讨论问题：是否总可无损分解为一组BCNF？是否总可保持依赖分解为一组3NF？可否实现双保持的分解？什么是多值依赖？什么是4NF？如何分解为4NF？关系模式设计需要注意什么？什么是触发器？如何设计触发器？什么时候使用触发器？,练习8：,P.201实践习题7.4,7.5P.202习题7.21PPT32证明函数依赖集的等价性(互相蕴含),Thankyou!,End!,六*附录(额外例子),CombineSchemasSupposewecombineinstructoranddepartmentintoinst_dept(Noconnectiontorelationshipsetinst_dept)Resultispossiblerepetitionofinformation,模式合并产生冗余的例子,ACombinedSchemaWithoutRepetitionConsidercombiningrelationssec_class(sec_id,building,room_number)andsection(course_id,sec_id,semester,year)intoonerelationsection(course_id,sec_id,semester,year,building,room_number)Norepetitioninthiscase,六*附录(额外例子),模式合并产生冗余的例子,ALossyDecomposition,六*附录(额外例子),有损分解的例子,LosslessjoindecompositionDecompositionofR=(A,B,C)R1=(A,B)R2=(B,C),六*附录(额外例子),无损分解的例子,