课件说明教案

Chapter6DatabaseDesignCh6DatabaseqLogicalDatabaseØalsoknown§Database§Database DatabasePrinciples& Ch6DatabaseqDatabasedesignistheprocessofproducingadetaileddatamodelofadatabase.qThislogicaldatamodelcontainsalltheneededlogicalandphysicaldesignchoicesandphysicalstorageparametersneededtogenerateadesigninaDataDefinitionLanguage,whichcanthenbeusedtocreateadatabase.qAfullyattributeddatamodelcontainsdetailedattributesforeachentity. DatabasePrinciples& Ch6Databaseqhowdoyzeanlistthedataitemsforadecidehowtoplacethesedataitemscolumnsinrelationaltables DatabasePrinciples& Ch6DatabaseqForexample:student-coursedatabaseØattributesofstudent:sno,sname,dept,sageØattributesofcourse:cno,cnameØattributeofstudent&course:qwecanputthemallinthesameR(sno,sname,dept,sage,cno,cname,qconsidertheSCGdatabase(nextslide),seeanyproblemswiththat? DatabasePrinciples& TheSCGWang5Wang5Wang4Wang3Wang4Chen3Chen3Zhang4 Ch6Databaseqredundency（数据冗余 DatabasePrinciples& redundency（数据冗余ØwasteofdiskSnoSnameDeptSageCnoCnameGradeS0001WangC101ABC5S0001WangC102ACD5S0001WangC103BBC4S0001WangC105AEF3S0001WangBCF433S0002S0002ChenChenMAMAC103C105AEFS0003ZhangYimouC107BHD4Relation DatabasePrinciples& ØwasteofØusermightgetitSnSnamDepSagCnCnamGradS0001WangJianC17C101AB5S0001WangJianC17C102AC5S0001WangJianC17C103BB4S0001WangJianC17C105AE3S0001WangJianC17C110BC4S0002ChenYinM19C103BB3S0002ChenYinM19C105AE3S0003ZhangYimouC17C107BH4Relation 行上的时间开销，也可能因为修改不彻底而导致数据不一致性ØmightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33S0003ZhangYimCS17C107BHD4 执执行元组删除操作，可能连带删除掉一些本不该被删除3)abnormityofØmightlosesomeSno Sname Dept Sage

Cno

Cname

GradeS0001S0001S0001S0001S0001S0002S0002

WangJian CS 17WangJian CS 17WangJian CS 17WangJian CS 17WangJian CS 17ChenYing M 19ChenYing M 19

C101C102C103C105C110C103C105

ABC ACD BBC AEF BCF BBC AEF S0003 ZhangYim CS 17Relation

C107R

BHD 假设需要删除学生元组：“S0003,ZhangYimou,CS,3)abnormityofØmightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33S0003 ngYim CS17C107BHD477 abnormityofØmightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33Relation （删除后的结果关系2017-4- DatabasePrinciples& ØunsuccessfulSnoSnameDeptSageCnoCnameGradeS0001WangJianCSC101ABC5S0001WangJianCSC102ACD5S0001WangJianCSC103BBC4S0001WangJianCSC105AEF3S0001WangJianCSC110BCF4S0002S0002ChenYingChenYingMMC103C105BBCAEF33S0003ZhangYimouCSC107BHD4Relation 可能因 实体完整性约束而导致元组插入失败 例如：“插入一条没有选课信息的学生元组”将执 CnCnCnamC10ABC10ACC10BBC10AEC10BHC11BC

SnoCnoGradeS0001SnoCnoGradeS0001C1015S0001C1025S0001C1034S0001C1053S00014S0002C1033S0002C1053S0003C1074

Relatio TheSCGDatabase IntroductiontoE-RFurtherDetailsofE-RAdditionalE-RCase Normal DatabasePrinciples& 6.1IntroductiontoE-RqAnEntity-Relationship(ER)modelisanwaytodescribeadatabase.qAdesignapproach,calledEntity-Relationshipmodelling,ismoreintuitive,lessmechanical,butbasicallyleadstothesameenddesign. DatabasePrinciples& 6.1IntroductiontoE-RqEntity-RelationshipØProposedbyPeterChenTheEntity-RelationshipModel:TowardaUnifiedViewofDataqPeterChen(Pin-shan DatabasePrinciples& 6.1IntroductiontoE-RqE-RØthreefundamentaldataclassificationqthecontentsofthisØEntities,Attributes,andSimpleE-RØTransformingEntitiesandAttributestoØRelationshipsamong DatabasePrinciples& 6.1IntroductiontoE-RqEntities,Attributes,andSimpleE-RØDef6.1.1Entity（实体§Anentityisacollectionofdistinguishablereal-worldobjectswithcommonproperties.–E.g.,collegeregistration§§§§§Ødifferentofferingsofasinglecourse,generallyatdifferenttimesbydifferentinstructors DatabasePrinciples& 6.1IntroductiontoE-RqNormallyØanentitysuchismappedtoarelationaltable§representsasetofØeachrowisanentityoccurrence,orentityinstance§representsaparticular DatabasePrinciples& 6.16.1IntroductiontoE-RqDef.6.1.2Attribute（属性ØAnattributeisadataitemthatdescribesapropertyofanentityorarelationship(definedbelow).Figure6.2ExampleofE-RDiagramswithEntitiesand DatabasePrinciples&

Attributesof

AttributesofFigure6.2ExampleofE-RDiagramswithEntitiesand

'hobbies'is'hobbies'isamulti-valuedattribute,andothersaresingle-valuedattributes threeattributesofFigure6.2ExampleofE-RDiagramswithEntitiesand(FigureqspecialterminologyforspecialkindsofØidentifier:Students.sid,ØØsingle-valued:sid,eid,Øcompositeattribute:student_name,Ømulti-valuedattribute: DatabasePrinciples& 6.1IntroductiontoE-R ØAnidentifierisanattributeorsetofattributesthatuniquelyidentifiesanentityØTheremightbemorethanoneidentifierforagivenentity primaryidentifier（主键 asinglekeyidentifiedby DatabasePrinciples& IntroductiontoE-RPrimary DatabasePrinciples& IntroductiontoE-RPrimaryPrimary DatabasePrinciples& IntroductiontoE-RqdescriptorØAdescriptorisanon-keyattribute,§§qcompositeØagroupofsimpleattributesthattogetherdescribeaproperty.§§qmulti-valuedØcantakeonmultiplevaluesforasingleentity DatabasePrinciples& IntroductiontoE-R

student_nameisacompositeattribute

DatabasePrinciples& IntroductiontoE-R emp_addressisacompositeattribute DatabasePrinciples& IntroductiontoE-R hobbiesisamulti-valuedattribute DatabasePrinciples& Review1:Entity&E-RqaØrepresentingasaqasingle-valuedØrepresentingasaØattachedbyastraightlinetotheqacompositeØisalsoinanovalattacheddirectlytotheØthesimpleattributesthatmakeupthecompositeareattachedtothecompositeoval.qamulti-valuedØisattachedbyadoublelinetotheentityit DatabasePrinciples& IntroductiontoE-RqTransformingEntitiesandAttributestoRelations-TransformationRule1§Anentityismappedtoasingletable.Thesingle-valuedattributesoftheEntityaremappedtocolumns(compositeattributesaremappedtomultiplesimplecolumns).§Entityoccurrences erowsoftheØExample6.1.1,Fig. DatabasePrinciples& TransformationRuleFigure6.2ExampleofE-RDiagramswithEntitiesandStudents(sid,lname,fname,midiaitia)Employees(eid,staddress,city,state,zipcode)IntroductiontoE-RqTransformingEntitiesandAttributestoRelations-TransformationRule2ØAmulti-valuedattributemustbemappedtoitsowntable.Employees(eid,staddress,city,state,zipcode)hobbies(hobby,eid)IntroductiontoE-RqRelationships（联系）amongØDef.6.1.3.Relationship(pg.§Givenanorderedlistofmentities,E1,E2,...,Em,(wherethesameentitymayoccurmorethanonceinthelist)§arelationshipRdefinesaruleofcorrespondencebetweentheinstancesoftheseentities.§Specifically,Rrepresentsasetofm-tuples,asubsetoftheCartesianproductofentity DatabasePrinciples& qFigure6.3:ExamplesofRelationshipsInstructorsteachesCourse_sections DatabasePrinciples& qFigure6.3:ExamplesofRelationshipsEmployeesworks_onProjects(percentoftime) DatabasePrinciples& qFigure6.3:ExamplesofEmployeesmanages

§ring,orrecursive DatabasePrinciples& qFigure6.3:ExamplesofRelationshipsInstructorsteachesCourse_sectionsEmployeesworks_onProjects(percentoftime)EmployeesmanagesEmployeesFigure6.3:ExamplesofE-RDiagramswithworks_onworks_onhastheconnectedattribute§percentisavaluewitheachrelationship§TherelationshipinstancerepresentsaspecificpairingofanEmployeesinstancewithaProjectsinstance;§percentrepresentsthepercentoftimeanemployeeinstanceworksonthat2017-4-2017-4- DatabasePrinciples&qdatabasedesign/databaseqEntity&qTransformationRule1&ØfromEntity&AttributestorelationqRelationshipØrelationshipbetweenØconnectedFurtherDetailsofE-RqCardinalityofEntityParticipationinaØLookatFigure§EntitiesEandF,relationship§LinesbetweenDotsareentityLinesarerelationship DatabasePrinciples& FurtherDetailsofE-RØIfalldotsintheentityEhaveATMOSTonelinecomingout,wesay:§max-card(E,R)=ØIfmorethanonelineoutispossible,we§max-card(E,R)=ØIfalldotsintheentityEhaveATLEASTonelinecomingout,wesay:§min-card(E,R)=ØIfsomedotsmightnothavealinecomingout,wesay:§min-card(E,R)= DatabasePrinciples& 6.2FurtherDetailsofE-Rmax-card(E,R)=min-card(E,R)=

DatabasePrinciples& 6.2FurtherDetailsofE-Rmax-card(E,R)= max-card(F,R)=min-card(E,R)= DatabasePrinciples& 6.26.2FurtherDetailsofE-RqDef.6.2.1Card(E,ØWecombinethese,bysayingcard(E,R)=(x,y)if:min-card(E,R)=xandmax-card(E,R)=§xiseither0or1,andyiseither1orcard(E,R)=(0,card(F,R)=(1, (0, (1,(0,(1, (0,(0,Figure6.7:AnE-RDiagramswithLabels(x,y)onEntity-RelationshipConnections6.26.2FurtherDetailsofE-R(0,reports-(0,qEmployee1inEmps_OneisamanagerofEmployee2inEmps_Two.2017-4- DatabasePrinciples& 6.26.2FurtherDetailsofE-RqDefØifmax-card(X,R)=1thenXissaidtohavesingle-valuedparticipation()intherelationshipR.ØIfmax-card(XRNthenXissaidtobemulti-participatio2017-4-(0, (1,(0,(1, (0,(0,2017-4- DatabasePrinciples& 6.26.2FurtherDetailsofE-RqDefØIfmin-card(X,R)=1,Xissaidtohavemandatoryparticipatio）intherelationshipRØifmin-card(X,R)=0,thenoptional2017-4-(0, (1,(0,(1, (0,(0,mandatoryoptional2017-4- DatabasePrinciples& FurtherDetailsofE-RqOne-to-One,Many-to-Many,andMany-to-OneRelationship(Figure6.6)ØOne-to-One(1-1)§bothentitiesaresingle-valuedintherelationship(max-cardconceptonly)ERFERFFurtherDetailsofE-RqOne-to-One,Many-to-Many,andMany-to-OneRelationship(Figure6.6)§oneentityismulti-valuedandoneissingle FurtherDetailsofE-RqOne-to-One,Many-to-Many,andMany-to-OneRelationship(Figure6.6)§bothentitiesaremulti-ERFERF(0, (1,(0,(1, (0,(0, DatabasePrinciples& FurtherDetailsofE-RqTransformingBinaryRelationships（二元联系）toRelationsØTransformationRule3.N-N§WhentwoentitiesEandFtakepartinamany-to-manybinaryrelationshipR,therelationshipismappedtoarepresentativetableTintherelatedrelationaldatabase DatabasePrinciples& 6.2FurtherDetailsofE-RqTransformationRule3.ØThetableTcontainscolumnsforallattributesintheprimarykeysofbothtablestransformedfromentitiesEandF.§thissetofcolumnsformstheprimarykeyforthetableT.ØTalsocontainscolumnsforallattributesattachedtotherelationship. DatabasePrinciples& FurtherDetailsofE-RØExample§Projects(prid,proj_name,§works_on(eid,prid,(1,N)works_on(0, DatabasePrinciples& FurtherDetailsofE-RqTransformationRule4.N-1Ørepresentwithforeignkeyinentitywithsinglevaluedparticipation(theManyside).§Sincemax-card(F,R)=1,eachrowofTisrelatedbyaforeignkeyvaluetoatmostoneinstanceoftheentityE.ØExample6.2.3:§Instructors(insid,lname,§Course_sections(secid,insid,course, DatabasePrinciples& FurtherDetailsofE-RqTransformationRule5&6.1-1ØOptionalonone§Representastwotables,foreignkeycolumninonewithmandatoryparticipation:columndefinedtobeNOTØMandatoryonboth§nevercanbreakapart.It'sappropriatetothinkofthisastwoentitiesinasingle DatabasePrinciples& AdditionalE-RqCardinalityofØDef6.3.1(Figure6.10,pg.347§(0,?)meansdon'thavetosaynotnull§(1,?)meansdo sid,student_name,lname,fname,city,......§(?,1)singlevaluedsid,§(?,N)multi- DatabasePrinciples& 6.3AdditionalE-R(1,(1,(1,(1,(0,Figure6.10(1) DatabasePrinciples& 6.3AdditionalE-R(1,(0,

(1,(1,

(1,1)(1,

(1,Figure6.10(2) DatabasePrinciples& AdditionalE-RqWeakØDef§Aweakentityisanentitywhoseoccurrencesaredependentfortheirexistence,througharelationshipR,ontheoccurrenceofanother(strong)entity.§Figure6.11,pg. DatabasePrinciples& qFigure DatabasePrinciples& AdditionalE-RqGeneralizationØFigure6.12,pg.ss DatabasePrinciples& CaseqFigure6.13&ØE-RDesignforaSimpleAirlineReservationDatabase

Travels_On(Passengers,FlightsHas_Seat(Flights,SeatsSeat_Assign(Passengers,SeatsMarshals(Flights,Gates DatabasePrinciples& Caseq6.4.1 q6.4.2篮球联赛信息管理q6.4.3聊天 q6.4.4邮件信息管理CaseStudy（例设有一个 阅理据知： 的属性书号（有一）书；者属借书证具唯每读只有书证）、 、 、 ； 的属性有 称具唯性、址联电话。 DatabasePrinciples& 6.4CaseStudy（例§每个球员的球衣号码、 §每个球队的名§每场比赛的比赛日期和比分§每个球员只能效§比赛采用主客 DatabasePrinciples& 6.4CaseStudy（例q假设需要设计一个用于网络 用户的用户名 ，联系地§帖子的帖子ID，标题，内 DatabasePrinciples& CaseStudy（例q有一个§联系人：用户名， §邮件：邮件ID，邮件标题，邮件内容，收信人集§邮件之间的回复关 DatabasePrinciples& Normalization(规范化):qNormalFormNF，范式qARunningØFigure6.15(pg.ØDef.6.5.1UpdateØDef.6.5.2DeleteAnomaly,Insert DatabasePrinciples& qFunctionalDependencyFD函数依赖Ø 函数依赖来自于现实世界中数据qArmstrong’sAxiomsArmstrong公理Ø基本规则：自反规则，传递规则，增广规Ø扩充规则：合并规则，分解规 DatabasePrinciples& 6.66.6FunctionalqFunctionalDependencyqDef.6.6.1A→B(AfunctionallydeterminesB,orBisfunctionallydependentonA)ØForanyrowsr1andr2inifr1(A)=r2(A)thenr1(B)=qExample DatabasePrinciples& uTheSCGuWang5Wang5Wang4Wang34Chen334TheTheSCG55434334SnoSno→Sname DatabasePrinciples& TheTheSCG55434334Sno→DeptSno→Dept DatabasePrinciples& TheTheSCG55434334Sno→CnoSno→SnameSno→Cno DatabasePrinciples& TheTheSCG55434334Sno→Sname Sno→Dept Sno→Cno×Cno→Cname DatabasePrinciplesCno→Cname55434334Sno→ Cno→

Sno→ Sno→Cno×TheSCGCno→Sno2017-4- TheSCGCno→Sno55434334TheTheSCGSnoSno→Cno→ 2017-4-

Sno→ DatabasePrinciples&

Sno→CnoCnoSno→CnoEachEachvalueofAcorrespondstoonlyonevalueofB.Figure6.18(a)GraphicalDepictionofFunctionalSomeSomevaluesofAcorrespondtomorethanonevalueofB.AdoesnotfunctionallydetermineFigure6.18(b)GraphicalDepictionofFunctionalFigure6.18GraphicalDepictionofFunctionalFigure6.18GraphicalDepictionofFunctional

AdoesnotfunctionallydetermineB.SomevaluesofAcorrespondtomorethanonevalueofB.E→F→

F→ FunctionalqExampleABA→B?B→A

A→ DatabasePrinciples& 6.6FunctionalqExampleABA→B?B→A

X1X1 A→B→ DatabasePrinciples& 6.6FunctionalqExampleABA→B?B→A

X1X1 B→ DatabasePrinciples& 6.6FunctionalqExampleABA→B?B→A

X1X1 DatabasePrinciples& 6.6FunctionalqExample ABA→BB→A

ABA→BB→A

ABA→BB→A

ABA→BB→A DatabasePrinciples&

B→

B→

DatabasePrinciples&6.6FunctionalqArmstrong’sW.W.Armstrong的 被称作“Armstrong公理” DatabasePrinciples& 6.6FunctionalqArmstrong’sØRule1（自反规则）：Inclusion§IfYX，thenX→§IfX→YandY→Z，thenX→ØRule3（增广规则）Augmentation§IfX→Y,thenXZ→qFigure6.19(pg.qFigure6.19(pg.1.1.InclusionXYTransitivityY YXXYZ6.6FunctionalqRule1:InclusionRuleIfYX，thenX→Y§设t1,t2是关系R中的任意两个元组(t1R,且它们在属性集X上的值相等(t1[X]=§由于Y是X的子集，即X§因此必有t1[Y] DatabasePrinciples& 6.6FunctionalqRule2:TransitivityIfX→YandY→Z，thenX→§设t1R,t2R,如果t1[X]= §由(2)及Y→Z得：t1[Z] DatabasePrinciples& 6.6FunctionalqRule3:AugmentationruleIfX→Y,thenXZ→YZ§设t1Rt2Rt1[XZt2[XZt1[X]= t1[Z]= §由(2)及(3)得：t1[YZ DatabasePrinciples& 6.6FunctionalqTheorem6.6.8SomeImplicationsofArmstrong’s（pg.363）ØRule4UnionRule（合并规则IfX→YandX→Z，thenX→ØRule positionRule（分解规则IfX→YZ，thenX→Y，andX→ØRule6PseudotransitivityRule（伪传递规则IfX→Y，andWY→Z，thenXW→ØRule7Setaccumulationrule（聚积规则IfX→YZandZ→W，thenX→ DatabasePrinciples&6.6FunctionalqRule4:UnionIfX→YandX→Z，thenX→ Wehave(a)X→Yand(b)ByArmstrong'sAugmentationruleand(a),wehave(c)XX→XY.ButXXisXUNIONX=X,so(c)canberewritten(d)X→XY.Nowby(b)andaugmentation,wehave(e)Andby(d)and(e)andtransitivity,wehaveX→YZ,thedesiredresult. DatabasePrinciples& 6.6FunctionalqRule positionIfX→YZ,thenX→Y,and Wehave(a)ByArmstrong'sInclusionRule,wehave(b)YZ→Yand(c)YZ→Z.By(a)and(b)andArmstrong’sTransitivityRule,wehaveX→Y.By(a)and(c)andArmstrong’sTransitivityRule,wehaveX→Z. DatabasePrinciples& 6.6FunctionalqRule6:PseudotransitivityIfX→Y,andWY→Z,then Wehave(a)X→Yand(b)ByArmstrong'sAugmentationRuleand(a),wehave(c)WX→WY.By(c)and(b)andArmstrong’sTransitivityRule,wehave(d)WX→Z.ButWX=XW,so(d)canberewrittenXW→Z,thedesiredresult. DatabasePrinciples& 6.6FunctionalqRule7:SetAccumulationIfX→YZandZ→W,thenX→ Wehave(a)X→YZand(b)ByArmstrong'sAugmentationRuleand(b),wehave(c)YZZ→YZW.ButYZZ=(YZ)Z=Y(ZZ)=Y=YZ,so(c)canberewritten(d)By(a)and(d)andArmstrong’sTransitivityRule,wehaveX→YZW,thedesired DatabasePrinciples& 6.6FunctionalqExample6.6.4:relationABCDqFindFDsinrelation DatabasePrinciples& 6.6FunctionalABCDq首先考虑决定因素和依赖因素都是单个属性的情A→BA→BA→CA→DB→AB→CB→DC→AC→B√C→DD→A√D→BD→C DatabasePrinciples& 6.6FunctionalABCDq也可以按照如下顺序考虑可能存在的函数依赖情A→B√AA→B√A→CA→DB→AB→CB→DC→AC→B√C→DD→A√D→B√D→C DatabasePrinciples& ABCDA→ C→ D→其次，再考虑决定因素是多个属性在FD的左边不需要考虑含有属性D的情况，why在FD的左边不需要考虑含有属性B的情况，why因此只需要考虑下述的FD是否成AC→B AC→DABCDA→C→D→AC→BD→AC→DD→q在上述的FD关系中，我们不用ACB，whyq因此，最后只需要考虑下面的一个FD是否可能成 AC→D√ABCDA→D→ABCAC→D

C→6.66.6Functional2017-4- DatabasePrinciples& q该关系上可能存在的函数依A→B C→BD→ABC 思考问题：

AC→左边含有属性D的其它的那些可能的右边为单个属性B的其它的那些可能的右边为多个属性的那些可能的ContentofqClosureofaSetofFDs(函数依赖集F的闭包)qFDSetCover(函数依赖集的覆盖)qEquivalenceoftwosetsofFDS(函数依赖集的等价qClosureofaSetofAttributes(属性集的闭包ØAlgorithmqMinimalCover(最小覆盖ØAlgorithm DatabasePrinciples& 6.6FunctionalqDef.6.6.9ClosureofaSetofFDs(函数依赖集F的闭包，记为F+)ØGivenasetFofFDsonattributesofatableT,wedefinetheCLOSUREofF,symbolizedbyF+,tobethesetofallFDsimpliedbyF.F+根据F中已有的函数依赖，利用Armstrong公理系统能够推导得到的所有函数依赖} DatabasePrinciples& 6.6Functional ExampleF={A→B,B→C,C→D,D→E,E→F,F→G,G→HallFDsinFareelementofbyArmstrong’sinclusionrule,A→A,AB→B......areelementofbyArmstrong’stransitivityrule,A→C,A→D,areelementofbyArmstrong’saugmentationrule,AD→BD,ABD→BCD,......areelementofF+byArmstrong’sunionrule,A→AB,A→BC,A→ABC,...,A→ABCDEFGH,......areelementofF+AnotherAnother DatabasePrinciples& 6.6FunctionalqDef.6.6.10FDSetCover(函数依赖集的覆盖ØAsetFofFDsonatableTissaidtoCOVERanothersetGofFDsonTifthesetGcanbederivedbyimplicationrulesfromthesetF,i.e.,ifGF+.q函数依ØIfFcoversGandGcoversF,wesaythetwosetsofFDsareequivalent,FG. DatabasePrinciples& 6.6Functional–Example6.6.6:ConsiderthetwosetsofFDsonthesetofattributesF={B→CD,AD→E,B→AG={B→CDE,B→ABC,AD→EØFcoversGØGcoversF DatabasePrinciples& FunctionalqEx.F:(f1)B→CDG:(g1)B→CDEFcoversG

(f2)AD→E(g2)B→ABC

(f3)B→A(g3)AD→E}Øg1canbederivedfromthesetFbyf1andf3andunionrule,wehavebyf2andaugmentationrule,we②CDAD→CDE,andcanberewrittenby①and③andtransitivityrule,wehave DatabasePrinciples& FunctionalqEx.F:(f1)B→CDG:(g1)B→CDEFcoversG

(f2)AD→E(g2)B→ABC

(f3)B→A(g3)AD→E}Øg2canbederivedfromthesetFbyf1 positionrule,wehaveby①andf3andunionrule,wehaveby②andaugmentationrule,wehaveg2 DatabasePrinciples& FunctionalqEx.F:(f1)B→CDG:(g1)B→CDE

(f2)AD→E(g2)B→ABC

(f3)B→A(g3)AD→E}FFcoversGØg3isanelementoftheset DatabasePrinciples& qEx.F:(f1)B→CDG:(g1)B→CDE GcoversF

(f2)AD→E(g2)B→ABC

(f3)B→A(g3)AD→E}6.6FunctionalØf1canbederivedfromthesetG6.6Functional1)byg1and positionrule,wehavef1Øf2isanelementofthesetØf3canbederivedfromthesetG1)byg2and positionrule,wehavef3 qDef.6.6.11ClosureofaSetof（属性集的闭包ØGivenasetXofattributesinatableTandasetFofFDsonT,wedefinetheCLOSUREofthesetX(underF),denotedbyX+orX+F,asthelargestsetofattributesYsuchthatX→YisinX+F={A|X→A∈F+ DatabasePrinciples& FunctionalalgorithmX+:=repeatoldX+:=foreachYZinFifYX+thenX+:=X+}}until(oldX+=X+ DatabasePrinciples& Exp6.6.7:computeF={(f1) (f2) (f3)B→AqsetX={B}+={Bqfirsttheleftsideoff1isasubsetof{B}+,then{B}+={B}+union{C,D}={B,C,D}theleftsideoff2isn’tasubsetof{B}+,thenf2doesnotapplyatthistimetheleftsideoff3isasubsetof{B}+,then{B}+={B}+union{A}={A,B,C,D}X{B}+,gotostep qsecondX={B}+={A,B,C,DskiptheFDsthathavebeentheleftsideoff2isasubsetof{B}+,{B}+={B}+union{E}=X{B}+,gotostepqthirdX={B}+=loopthroughFDsinFendwithX= q F+={X→A|X→AcanF+={X→A|X→AcanbederivedfromFFcoverGiff"eachFcoverGiff"eachX→AofGcanderivedfromF"FcoversGandGFcoversGandGcoversqDef.6.6.11ClosureofaSetofXXF+={A|X→AcanbederivedfromF(X→A∈F+)} DatabasePrinciples& qAlgorithm6.6.13MinimalCover最小覆盖没有冗余(inessential)的函数依每一个函数依赖的左边都没有多余的属Øa没有冗余(inessential)的函数依每一个函数依赖的左边都没有多余的属 DatabasePrinciples& pstep1:FromthesetFofFDs,wecreateanequivalentsetHofFDs,withonlysingleattributesontherightside.pstep2:FromthesetHofFDs,successivelyremoveindividualFDsthatareinessentialinH.pstep3:FromthesetHofFDs,successivelyreplaceindividualFDswithFDsthathaveasmallernumberofattributesontheleft-handside,aslongastheresultdoesnotchangeH+.pstep4:FromtheremainingsetofFDs,gatherallFDswithequalleft-handsidesandusetheunionruletocreateanequivalentsetofFDsMwhereallleft-handsidesareunique.BCADBCADEFFigure6.20ExampleofanInessentialFD:qstep2:FromthesetHofFDs,successivelyremoveindividualFDsthatareinessentialinH.ØAnFDX→YisinessentialinasetHofFDs,ifX→YcanberemovedfromH,withresultsothatH+=J+,orØThatis,removaloftheFDfromHhasnoeffectonH+.BCABCADEFFigure6.20ExampleofanInessentialFD:F={B→D,D→E,C→F,BC→A,EF→AqremoveBC→AfromH={B→D,D→E, EF→AqBC→AisinessentialinFbecauseof DatabasePrinciples& XBCDAEFigure6.21ExampleofanFD:X→AwhereBXBCDAEqstep3:FromthesetHofFDs,successivelyreplaceindividualFDswithFDsthathaveasmallernumberofattributesontheleft-handside,aslongastheresultdoesnotchangeH+. DatabasePrinciples& XBCDAEFigure6.21ExampleofanFD:X→AwhereBXBCDAEqLet:F={C→E,E→B,qWesayBcanberemovedfromBCD→ABCDACDA)ØLet:H={C→E,E→B,CD→A}ØWehave:F+= DatabasePrinciples& Østep4:FromtheremainingsetofFDs,gatherallFDswithequalleft-handsidesandusetheunionruletocreateanequivalentsetofFDsMwhereallleft-handsidesareunique. DatabasePrinciples& Functional计算过计算过ØSupposeX={a,b,c,d}F={a→ bc→ ac→dØGivetheminimalcoverMforthesetFqExampleØSupposeY={a,b,c,d}G={a→a b→ab d→abcØGivetheminimalcoverNforthesetG DatabasePrinciples& FunctionalqExample6.6.8ConstructtheminimalcovercoverMforthesetFofFDs.ØABD→AC→BAD→BB→计计算 DatabasePrinciples& ContentofqTheprocessof positionsofqLossless position&Lossyposition(无损分解)ØTheorem6.7.3&qFD (依赖保持 DatabasePrinciples& qTheprocessof poseatableintotwoormoresmall§projectingontotwoormoresubsetsofcolumnsthatcoverallcolumnsandhavesomecolumnsincommon.Øbutitdoesn'talwaysworkwhenjoinbackthatkeepallinformationoforiginaltable.§AlwaysgetALLrowsback,§mightget–seeexample6.7.1(pg.374,next DatabasePrinciples& 6.7 qexample

ABC≠ABjoinABCABCABCABCABABBC DatabasePrinciples& Def.6.7.1Lossless position(无损性分解) ForanytableTwithanassociatedsetoffunctionaldependenciesF,a ofTintoktablesisasetoftables{T1,T2,...,Tk},withtwoproperties:foreverytableTiintheset,Head(Ti)isapropersubsetofHead(T);Head(T)= DatabasePrinciples& qDef.6.7.1ØGivenanyspecificcontentofT,therowsofTareprojectedontothecolumnsofeachTiasaresultofthe positionofatableTwithanassociatedsetFofFDsissaidtobea positionif,foranypossiblefuturecontentofT,theFDsinFguaranteethatthefollowingrelationshipwillhold:TT1joinT2join...joinTk DatabasePrinciples& qLossy positionofTis{T1,T2,...,ØWejointhetablesofthe wemightgetbackotherrowsthatwerenotoriginallypresent,soTT1joinT2join...join DatabasePrinciples& qEx6.7.1A ABCABCABC ABABBC DatabasePrinciples& ABC=ABjoinqEx6.7.2ADifferentContentABC=ABjoinABCABCABABC ABABBC DatabasePrinciples& qDef.6.7.2Adatabaseschemaisthesetofheadingsofalltablesinadatabase,togetherwiththesetofallFDsthatthedesignerwishestoholdonthejoinofthosetables.qEx6.7.3TableABCwithaFD:–Assumethetablecontentofis

ABCABC qEx6.7.3TableABCwithaFD:ABC–Ifwetriedtoinsertarow(a4,200,c4),thisinsertwouldfail.Why? DatabasePrinciples& qEx6.7.3TableABCwithaFD:ABC–but,wecaninsertarow(a4,200,c2)tothistable. DatabasePrinciples& qEx6.7.3TableABCwithaFD:ABCABCAB

ABCBCABCABjoinBC,DatabasePrinciples& qTheorem6.7.4.GivenatableTwithasetFofFDsvalidonT,thena positionofTintotwotables{T1,T2}isalossless ifoneofthefollowingfunctionaldependenciesisimpliedbyF:Head(T1)Head(T2)Head(T1)Head(T2) DatabasePrinciples& qEx6.7.4:InExampleABCABCABC ABABBC DatabasePrinciples& qEx6.7.5qEx6.7.6LosslessJoin withMultipleTables:T{T1,T2,...,Tk}Øwecandemonstratelosslessnessbyusingthetwo-tableresultinarecursive(((T1joinT2)joinT3)...join DatabasePrinciples& qEx.Givea positionoftableT(A,B,C)withasetFofFDs:={T1,T2}Isitaposition1)F={ABT1(A,T2(A,2)F={AC,BCT1(A,T2(A,3)F={ABT1(A,T2(B,4)F={AB,BCT1(A,T2(B, DatabasePrinciples& qEx.Givea positionoftableT(A,B,C,D)withasetFofFDs{AB,BC,AD,DC}:T1 T2 T3ØIsita position–§T1andT2isa position§(T1T2)andT3isa DatabasePrinciples& Normalqemp_info(emp_id,emp_name,emp_phone,dept_name,dept_phone,dept_mgrname,skill_id,skill_name,skill_date,skill_lvl)dept_name{dept_phone,dept_mgrname}Figure6.22& DatabasePrinciples& 6.8Normalemps(emp_id,emp_name,emp_phone,dept_name,dept_phone,dept_mgrname)emp_id{emp_name,emp_phone,dept_name}dept_name{dept_phone,dept_mgrname}{emp_id,skill_id}{skill_date,Figure DatabasePrinciples& 6.8NormalqPropositionØThekeyfortheemp_infotableistheattributeset(emp_id,skill_id)§Thisisalsothekeyfortheskills§theempstablehasakeyconsistingofthesingleattributeemp_idqØByTheorem DatabasePrinciples& 6.8NormalqPropositionØThefactorizationoftheemp_infotableintotheempstableandskillstableisatrue qØBythetheorem DatabasePrinciples& NormalqFigureØemps(emp_id,emp_name,emp_phone,Ødepts(dept_name,dept_phone,dept_mgrname)Øemp_skills(emp_id,skill_id,skill_date,skill_lvl)Øskills(skill_id,skill_name)qExØFigureØFigureØFigure DatabasePrinciples& NormalqDef.6.8.3FD (依赖保持性ØGivenadatabaseschemawithauniversaltableTandasetoffunctionaldependenciesF,let{T1,T2,......,Tk}bealosslesspositionofØThenanFDXYofFissaidtobeinthe positionofT,oralternativelythepositionofTp theFDXY,ifforsometableTiofthe ØWhenthisisthecase,wealsosaythattheFDXYisp inTiorthatitliesinTiorisinTi. DatabasePrinciples& 6.8NormalqDef.6.8.3依赖保持R分解为{T1,T2,......,Tk这k个子关系模式，从所存在的函数依赖集为Fii=1,2,…,k)等价的，即F+F1F2…Fk)+，则我们称该 DatabasePrinciples& ContentofqSuperkey&ØAlgorithmtoFindCandidateØPRIMEATTRIBUTE(主属性ØNON-PRIMEATTRIBUTE(非主属性qNormalØ2NF,3NF,qAlgorithm DatabasePrinciples& 6.8NormalqTheorem6.7.3.GivenatableTwithasetofFDsFandasetofattributesXinHead(T)Xisasuperkeyof Xfunctionallydeterminesallattributesin( F

=Head(T) DatabasePrinciples& 6.8NormalqAnAlgorithmtoFindCandidateØGivenatableTwithasetFofsetK:=Head(T)foreachattributeAinK{compute(K-A)F +if(K- contais+thensetK:=K-{A}}} DatabasePrinciples& 6.8NormalqFindcandidatekeyforthistableR(A,B,C,D)，F:{BD,ABCR(A,B, F:{AB,BA,ACR(A,B,C,D)，F:{AC,CDB DatabasePrinciples& 6.8NormalR(A,B,C,D)，F:{BD,ABC解：KA,BCD∵{K–A}+={B,C,D}+={B,C,D}∵{K–B}+={A,C,D}+={A,C,D}∵{K–C}+={A,B,D}+={A,B,D,C}=∴K=K–C=∵{K–D}+