A first course in database systems(3).ppt

3TheRelationalDataModel,Whatarerelationaldatamodels?HowtoconvertE/Rmodelsintorelationaldatamodels?Howtoassure(保证)certainformconditionbydecomposing(分解)relationalmodel?,3.1BasicsoftheRelationalModel,Relation:Atwo-dimensionaltablecalledarelation.,Movies,3.1BasicsoftheRelationalModel,Stars-in,3.1.1Attributes,Attribute(属性):Namesforthecolumnsoftherelation,describethemeaningofentriesinthecolumnbelow.SuchaslengthofMovies.Anattributehaveaname.Anytwoattributesofarelationcanthavesamename.,3.1.2Schemas(模式),Relationschema=relationnameandsetofattributes.Example:Movies(title,year,length,filmtype)orMovies(title:string,year:int,length:int,filmtype:string)Database=collectionofrelations.Databaseschema=setofallrelationschemasinthedatabase.,3.1.3Tuples,Tuples(元组):Therowsofarelation,otherthantheheaderrowcontainingtheattributes,arecalledtuples.Theremaybenotupleinarelation.Atuplehasonecomponent(分量)foreachattributeoftherelation.Howtodescribeatuple?Usecommastoseparatecomponents,anduseparentheses(圆括号)tosurroundthetuple.Example:(StarWars,1977,124,color)Weshouldalwaysusetheorderinwhichtheattributeswerelistedintherelationschema.,3.1.3Tuples,Themappingoftuplesandobjects:ArelationaclassAtupleaobjectAcomponentofatupleapropertyofaobjectThedifferenceoftuplesandobjects:Objectshaveidentities(标识),whiletupleshavenot.Aclasscouldhavetwodifferentobjectswiththesamevaluesinallattributes,butatuplecantappearmorethanonceinarelation.,3.1.4Domains,Domains:Adomainisanelementary(基本的)type,suchasinteger,char(n),date,time.Eachattributeofarelationisadomain,thatis,aparticularelementarytype.Eachcomponentofanytuplemustbeatomic(原子的).Atomic:Cannotbebrokenintosmallercomponents,3.1.5EquivalentRepresentationsofaRelation,Wecanreordertheattributesofarelation,withoutchangingtherelation.Wecanreorderthetuplesofarelation,withoutchangingtherelation.,3.1.6RelationInstances,Therelationshipbetweenschemaandtuples:Theschemaofarelationisrelativelystatic,whilethetupleschangeovertime.Relationinstances(实例):Asetoftuplesforarelationisaninstanceoftherelation.Theinstanceofarelationchangesovertime.Thesetoftuplesthatareintherelation“now”is“currentinstance(当前实例)”.,3.1BasicsoftheRelationalModel,Exercises:p643.1.1,3.2FromE/RDiagramstoRelationalDesigns,HowtoconvertanE/Rdiagramtoarelation?Mainidea:ConversionfromentitysetstorelationsConversionfromrelationshipstorelationsHandlingweakentitysets,3.2.1FromEntitySetstoRelations,Entityset-relation.Attributes-attributes.,Movies(title,year,length,filmType)Stars(name,address)Studios(name,address),3.2.2FromE/RRelationshipstoRelations,Howtoconvertmultiwayrelationshipstorelations?Convertmultiway(多元)relationshipstobinary(二元)relationshipsfirstly.,Howtoconvertbinaryrelationshipstorelations?Accordingtomultiplicityoftherelationship:Amany-manyrelationshipRfromE1toE2ConvertRtoarelationwhoseattributesarecomposedoftheattributesofRandthekeyattributesofE1andE2.Example:Enrollment(注册)betweenStudentsandCoursesEnrollment(Sno,Cno,score),3.2.2FromE/RRelationshipstoRelations,Movies(title,year,length,filmType)Stars(name,address)Studios(name,address),Stars-in(title,year,starName),3.2.2FromE/RRelationshipstoRelations,2.Amany-onerelationshipRfromE1toE2Rcanbeconvertedtoarelation,butnotmustbe.AddthekeyattributesofE2totherelationE1.Example:BelongbetweenDepartmentsandEmployees,Employees(EmpID,name,.)Departments(DeptID,name)Belong(EmpID,DeptID),DeptID,3.2.2FromE/RRelationshipstoRelations,Movies(title,year,length,filmType)Stars(name,address)Studios(name,address),Stars-in(title,year,starName),Movies(title,year,length,filmType,studiosName),3.2.2FromE/RRelationshipstoRelations,3.Aone-onerelationshipRfromE1toE2Rcanbeconvertedtoarelation,butusuallynot.Therearetwoways:AddthekeyattributesofE2totherelationE1.AddthekeyattributesofE1totherelationE2.Anone-onerelationshipsmaybemergedintoanother.Example:HeaderbetweenDepartmentsandEmployees,Employees(EmpID,name,.,leadDept)Departments(DeptID,name),Employees(EmpID,name,.)Departments(DeptID,name,leaderID),3.2.4HandlingWeakEntitySets,Conversionfromweakentitysetstorelations：ConvertweakentitysetEtoarelationwhoseattributesarecomposedoftheattributesofEandthekeyattributesofF.CannotconvertRtoarelation.,3.2.4HandlingWeakEntitySets,Studios(name,address)Crews(studioName,number),Crews,number,Unit-of,Studios,name,address,3.2.4HandlingWeakEntitySets,Contracts(starName,studioName,title,year,salary,signdate),3.3ConvertingSubclassstructurestoRelations,Subclasses:ThreeApproachesObject-oriented:Onerelationpersubsetofsubclasses,withallrelevantattributes.Usenulls:Onerelation;entitieshaveNULLinattributesthatdontbelongtothem.E/Rstyle:Onerelationforeachsubclass:Keyattribute(s).Attributesofthatsubclass.,3.3ConvertingSubclassstructurestoRelations,Example:,3.3ConvertingSubclassstructurestoRelations,Object-orientedmovies(title,year,length,FilmType)Murder-Mysteries(title,year,length,FilmType,weapon)Usenullsmovies(title,year,length,FilmType,weapon)E/Rstylemovies(title,year,length,FilmType)Murder-Mysteries(title,year,weapon),converttorelations,AmarketingmanagementsystemCustomer(custid,name,prov,city,phone,unit)Product(prodid,factory,type,spec,price,desc)Salesman(empid,idno,name,gender,phone,deptid)Department(deptid,name,headerid)Salesorder(orderno,signdate,empid,custid)Salesitem(orderno,lineno,prodid,singlecost,quantity),3.2FromE/RDiagramstoRelationalDesigns,Exercises:P7.2,3.4FunctionalDependencies(函数依赖),用形式化方法研究一个关系中各属性之间的语义关系。Mainidea:MeaningofFDsKeysSuperkeysFindkeysfromE/Rdiagrams,3.4.1DefinitionofFunctionalDependency,X-Aisanassertion(断言)aboutarelationRthatwhenevertwotuplesofRagreeonalltheattributesofX,thentheymustalsoagreeontheattributeA.Say“X-Aholds(成立)inR.”Say“XfunctionallydetermineA.”,3.4.1DefinitionofFunctionalDependency,若关系R的任意两个元组在属性A1、A2、An上的值一致(即有相同分量值)，则这两个元组在属性B上的值必也一致，称属性A1A2An函数决定B，或称属性B函数依赖于A1A2An。记为：A1A2AnBExample：InStudents(sno,sname,gender)snosnamesnogenderconsider：snamegender？,3.4.1DefinitionofFunctionalDependency,Letusconsidertherelationstudents(sno,sname,cno,score)snosname？and：snoscore？or：snocnoscore?,3.4.1DefinitionofFunctionalDependency,Corollary(推论)1:A1A2AnB1A1A2AnB2A1A2AnBmiff(ifandonlyif)A1A2AnB1B2BmCorollary2:AA,3.4.1DefinitionofFunctionalDependency,Example3.12：LetusconsidertherelationMovies(title,year,length,filmType,studioName,starName),titleyearlengthfilmTypestudioNameconsider：titleyearstarName?,3.4.1DefinitionofFunctionalDependency,Considerthefunctionaldependenciesinrelationstudent(stuid,name,gender,depid,dorm,courseid,coursename,score).,stuidcourseidscorestuidnamegenderdepiddormdepiddorm,courseidcoursename,如何分析一个具体关系中的函数依赖：根据属性之间的语义关系分析函数依赖。应考虑所有可能的属性组合。尽可能使函数依赖式的左面最小化，而右面最大化。注意：函数依赖是针对关系模式，而不是针对特定实例，故只从关系实例不能确切断定函数依赖。,stuidnamegender？namegender?stuidscore?stuidcourseid?stuidcourseidscore?,3.4.1DefinitionofFunctionalDependency,Threecasesofassertingfunctionaldependencies:IftwotupleshavethesamevaluesintheirAcomponents,andtheyalsohavethesamevaluesintheirBcomponents,thenABholds.IftwotupleshavethesamevaluesintheirAcomponents,buttheyhavenotthesamevaluesintheirBcomponents,thenABdoesnothold.IfanytwotuplescanthavethesamevaluesintheirAcomponents,thenABholds.,3.4.1DefinitionofFunctionalDependency,常见术语：部分函数依赖：若XY，且存在X的真子集X，XY，则称Y对X部分函数依赖。完全函数依赖：若XY，且Y对X不是部分函数依赖，则称Y对X是完全函数依赖。传递函数依赖：若XY，YZ，且YX不成立，则称Z对X是传递函数依赖。,3.4.2KeysofRelations,Key:WesayasetofoneormoreattributesA1,A2,.,AnisakeyforarelationRif:A1,A2,.,AnfunctionallydetermineallotherattributesoftherelationR.(superkey)Nopropersubset(真子集)ofA1,A2,.,AncanfunctionallydetermineallotherattributesofR.(minimal),3.4.2KeysofRelations,KeyoftherelationMovies(title,year,length,filmtype,studioName,starName):title,year?title,year,starName?IfABholdsinR(A,B,C),thekeysofR?,3.4.2KeysofRelations,Primarykey:Sometimesarelationhasmorethanonekey,andoneofthekeysisdesignatedastheprimarykey.Candidate(候选)key:Allkeysofarelation.,3.4.3Superkey(超键),Superkeys:Superset(超集)ofakey.Asetofattributesthatcontainsakey.Thoseattributesfunctionallydetermineallotherattributesoftherelation.Therelationshipbetweenkeysandsuperkeys:Keysaresuperkeys.title,year,starNameSomesuperkeysarenotkeys.title,year,length,starName,3.4.4DiscoveringKeysforRelations,Howtoexpressakeyofarelationschema?UnderlinetheattributesoftheprimarykeyHowtodeterminethekeyfortherelationcomingfromanentityset?Thekeyfortherelationisthekeyattributesofthisentityset.Example:Movies(title,year,length,fileType)Stars(name,address)Studios(name,address),3.4.4DiscoveringKeysforRelations,HowtodeterminethekeyfortherelationRcomingfromabinaryrelationship?Accordingtomultiplicity(多重性)oftherelationship,therearethreecases:many-many:thekeysofbothconnectedentitysetsarethekeyattributesforR.many-onefromE1toE2:thekeyattributesofE1arekeyattributesofR,butthoseofE2arenot.one-one:thekeyattributesforeitheroftheconnectedentitysetsarekeyattributesofR.Example:StarsIn(title,year,starName)Owns(title,year,studioName)canbemergedintherelationMovies:Movies(title,year,length,fileType,studioName),Customer(custid,name,prov,city,phone,unit)Product(prodid,factory,type,spec,price,desc)Salesman(empid,idno,name,gender,phone,deptid)Department(deptid,name,headerid)Salesorder(orderno,signdate,empid,custid)Salesitem(orderno,lineno,prodid,singlecost,quantity),3.5RulesAboutFunctionalDependencies,Whatarerulesaboutfunctionaldependencies?Whyweneedthem?Supposewearetoldofasetofdependenciesthatarelationsatisfies,wecandeduce(演绎出)otherdependenciesbyrulesaboutfunctionaldependencies.Theabilitytodiscoveradditionaldependenciesisessentialwhenwediscussthedesignofgoodrelationschemas.,3.5RulesAboutFunctionalDependencies,Example3.17:p90IfwearetoldthatarelationR(A,B,C)satisfiesthefunctionaldependenciesABandBC,thenwecandeduce(推论)thatRalsosatisfiesthedependencyAC.Proof:Set(a,b1,c1)and(a,b2,c2)asthetuplesofR.SinceAB,thenb1=b2SinceBC,thenc1=c2So:ACisholdinR.,3.5RulesAboutFunctionalDependencies,Someimportantrulesaboutfunctionaldependencies:Thesplitting/combiningrule(分解/合并规则)Thetrivial-dependencyrule(平凡依赖规则)Thetransitiverule(传递规则)Armstrongsaxioms(公理),3.5RulesAboutFunctionalDependencies,两个函数依赖集之间的关系：设T是关系R上的函数依赖集，若对R的所有实例，函数依赖XY都成立，则称T“逻辑蕴含”XY。(XY可由T推导出来)设S是关系R上的另一函数依赖集，若对R的所有实例，S中的所有函数依赖均成立，则称函数依赖集S“蕴含于”函数依赖集T。(S可由T推导出来)若函数依赖集S“蕴含于”T，同时T“蕴含于”S，则函数依赖集S“等价于”函数依赖集T。,3.5RulesAboutFunctionalDependencies,Therelationshipbetweentwosetsoffunctionaldependencies:IfeveryrelationinstancethatsatisfiesallthedependenciesinasetoffunctionaldependenciesTalsosatisfiesallthedependenciesinasetoffunctionaldependenciesS,wesaythatSfollowsfrom(蕴含于)T.IfSfollowsfromTandTfollowsfromS,thenSandTareequivalent(等价).,3.5RulesAboutFunctionalDependencies,蕴含和等价关系的作用：可用等价的更简单的函数依赖集代替复杂的函数依赖集。可在一个函数依赖集S中增加蕴含其中的其它函数依赖。可判断一个函数依赖是否蕴含于已知的函数依赖集。,3.5.1TheSplitting/CombiningRule,Splitting/CombiningRule:,Thereisnosplittingruleorcombiningruleforleftsides.,3.5.1TheSplitting/CombiningRule,Example：InMoviestitleyearlengthfilmTypestudioNameisequivalentto：titleyearlengthtitleyearfileTypetitleyearstudioNameBut，snocnoscorecannotsplitthetheleftsideinto：snoscorecnoscore,3.5.2TrivialDependencies,Trivialdependency(平凡依赖):AfunctionaldependencyA1A2.AnBissaidtobetrivialifBisoneoftheAs.Everytrivialdependencyholdsineveryrelation.AdependencyA1A2.AnB1B2.BmisTrivialiftheBsareasubsetoftheAs.NontrivialifatleastoneoftheBsisnotamongtheAs.Completelynontrivial(完全非平凡)ifnoneoftheBsisalsooneoftheAs.Example:titleyearyearlengthisnontrivialtitleyearlengthiscompletelynontrivial,3.5.2TrivialDependencies,Thetrivial-dependencyrule:Wecanremovefromtherightsideofafunctionaldependencythoseattributesthatappearontheleft.Thatis:ThefunctionaldependencyA1A2.AnB1B2.BmisequivalenttoA1A2.AnC1C2.Ck,wheretheCsareallthoseBsthatarenotalsoAs.,3.5.3ComputingtheClosureofAttributes,属性的闭包设S是关系R上的函数依赖集，A=A1,A2,An是R上的属性集，则属性集A可函数决定的最大属性集合称做A的闭包，记做：A+(或A+s)。这个集合如何计算？这种计算有何用途？,3.5.3ComputingtheClosureofAttributes,Theclosure(闭包)ofattributes:SupposeA1,A2,.,AnisasetofattributesandSisasetoffunctionaldependencies.TheclosureofA1,A2,.,AnunderthedependenciesinSisthesetofattributesBsuchthateveryrelationthatsatisfiesallthedependenciesinsetSalsosatisfiesA1A2.AnB.Thatis,A1A2.AnBfollowsfromthedependenciesofS.Wedenote(表示)theclosureofasetofattributesA1,A2,.,AnbyA1,A2,.,An+.A1,A2,.,AnarealwaysinA1,A2,.,An+.IfA1A2.AnX,thenXB.,3.5.3ComputingtheClosureofAttributes,计算属性的闭包：对于给定的函数依赖集S，和属性集A=A1,A2,An设属性集X是A的闭包，将X初始化为A1,A2,An，即为闭包的最小集合。对于S中的每个函数依赖式：B1B2BmC。如果B1,B2,Bm都在X中，而C不在X中，则把C加入X中。重复第2步，直到遍历完S中所有函数依赖，而没有新属性能加入到X中。属性集X即为属性集A在函数依赖集S下的闭包A+。,3.5.3ComputingtheClosureofAttributes,Example3.19:p93LetusconsiderarelationwithschemaR(A,B,C,D,E,F)andasetoffunctionaldependenciesS:ABC,BCAD,DE,CFBPleasecomputerA,B+.Solution：FirstX(1)=A,BSinceABC，soX(2)=A,B,CSinceBCAD，soX(3)=A,B,C,DSinceDE，soX(4)=A,B,C,D,ENomoredependencycanbeused,thusA，B+=A,B,C,D,E,3.5.3ComputingtheClosureofAttributes,Whywecomputetheclosureofattributes?SupposewehavearelationRwithasetofdependenciesS,andadependencyA1A2.AnB.WecantestwhetherthedependencyfollowsfromthedependenciesofS.ComputerA1,A2,.,An+usingthesetofdependenciesS.IfBisinA1,A2,.,An+,thenA1A2.AnBfollowsfromS.IfBisnotinA1,A2,.,An+,thenA1A2.AnBdoesnotfollowfromS.A1A2.AnB1B2.BmfollowsfromsetofdependenciesSiffAllofB1,B2,.,BmareinA1,A2,.,An+.,3.5.3ComputingtheClosureofAttributes,Example3.20:LetusconsiderarelationwithschemaR(A,B,C,D,E,F)andasetoffunctionaldependenciesS:ABC,BCAD,DE,CFBPleasetestwhetherABDandDAfollowfromthedependenciesofS?,3.5.3ComputingtheClosureofAttributes,Closuresandkeys:A1,A2,.,An+isthesetofallattributesifandonlyifA1,A2,.,Anisasuperkeyfortherelation.,3.5.5TheTransitiveRule,Thetransitive(传递)rule:Cascade(级联)twofunctionaldependencies.IfA1A2.AnB1B2.BmandB1B2.BmC1C2.CkholdinrelationR,thenA1A2.AnC1C2.CkalsoholdsinR.Example:MovieStudio(title,year,length,fileType,studioName,studioAddr)title,yearstudioNamestudioNamestudioAddrthentitle,yearstudioAddr,3.5.6ClosingSetsofFunctionalDependencies,Wecanderiveanewsetofdependenciesfromasetofgivendependenciesusingrulesaboutfunctionaldependencies.Anysetofgivendependenciesfromwhichwecaninferallthedependenciesforarelationwillbecalledabasis(基)forthatrelation.Arelationmayhaveseveralbases.Ifnopropersubsetofthedependenciesinabasiscanalsoderivethecompletesetofdependencies,thenwesaythebasisisminimal.Arelationmayhaveseveralminimalbases.,3.5.6ClosingSetsofFunctionalDependencies,Example3.22:p98ConsiderarelationwithschemaR(A,B,C)andasetofdependenciesFD:AB,AC,BA,BC,CA,CBThentheminimalbasesare:AB,BA,BC,CB,AB,BC,CAandsoon.,3.5.6ClosingSetsofFunctionalDependencies,Armstrongsaxioms:Reflexivity(自反律).IfB1,B2,BmA1,A2,An,thenA1A2AnB1B2Bm.(trivial)Augmentation(增长律).IfA1A2AnB1B2Bm,thenA1A2AnC1C2CkB1B2BmC1C2CkforanysetofattributesC1,C2,Ck.Transitivity(传递律).IfA1A2AnB1B2BmandB1B2BmC1C2Ck,thenA1A2AnC1C2Ck.,3.5.7ProjectingFunctionalDependencies,SupposearelationhasschemaR(U)andasetofdependenciesF.IfRisdecomposedintoS(U1)andT(U2),thenweneedfindwhatfunctionaldependenciesstillholdinS.,3.5.7ProjectingFunctionalDependencies,Algorithm:ConsidereachsetofattributesXthatiscontainedinthesetofattributesofS.ComputeX+.ThenforeachattributeBsuchthatBisanattributeofS,BisinX+,andBisnotinX,thefunctionaldependencyXBholdsinS.,3.5.7ProjectingFunctionalDependencies,Example:LetRhaveschemaR(A,B,C,D),andsupposethefunctionaldependenciesABandBCaregivenforR.LetS(A,C)beoneoftherelationinadecompositionofR.PleasecomputethedependenciesthatholdinS.Solution:A+=A,B,C,thenACholdsinS.C+=CA,C+=A,B,C,3.5.7ProjectingFunctionalDependencies,Example:ConsiderR(A,B,C,D,E)decomposedintoS(A,B,C)andanotherrelation.LetthefunctionaldependenciesofRbeAD,BEandDEC.PleasecomputethedependenciesthatholdinS.Solution:A+=A,DB+=B,EC+=CA,B+=A,B,C,D,E,thenABCholdsinSA,C+=A,C,DB,C+=B,C,EA,B,C+=A,B,C,D,E,Exercise3.5.1,ConsiderarelationwithschemaR(A,B,C,D)andfunctionaldependenciesABC,CDandDA.Whatareallthenontrivialfunctionaldependenciesthatfollowfromthegivendependencies?WhatareallthekeysofR?WhatareallthesuperkeysforRthatarenotkeys?,solution：ComputingtheClosuresofallthesubsetofattributes:A+=AB+=BC+=C,D,ACADD+=D,AA,B+=A,B,C,DABCDA,C+=A,C,DACDA,D+=A,DB,C+=B,C,D,ABCADB,D+=B,D,A,CBDACC,D+=C,D,ACDAA,B,C+=A,B,C,DABCDA,B,D+=A,B,D,CABDCA,C,D+=A,C,DB,C,D+=B,C,D,ABCDAA,B,C,D+=A,B,C,D(b)Allkeys：A,B,B,C,B,D(c)Allsuperkeys：A,B,B,C,B,DA,B,C,A,B,D,B,C,D,A,B,C,D,3.5RulesAboutFunctionalDependencies,Exercise:P1003.5.2i),3.6DesignofRelationalDatabaseSchemas,Causesofredundancy(冗余)：Afactisrepeatedinmorethanonetuple.Themostcommoncausefortheredundancy:attempstogroupintoonerelationbothsingle-valueandmultivaluedpropertiesofanobject.,Example:Student,Howtosolvethisredundancy?Exploreinmoredetailtheproblemsthatarisewhenourschemaisflawed(有缺陷的).Introducetheideaof“decomposition”,breakingarelationschemaintotwosmallerschemas.Introduce“Boyce-Coddnormalform”,or“BCNF”,aconditiononarelationschemathateliminatestheseproblems.ExplainhowtoassuretheBCNFconditionbydecomposingrelationschemas.RelaxBCNFrequirementslightly,andintroduce“Thirdnormalform”,or“3NF”.Introduce“1NF”and“2NF”.,3.6DesignofRelationalDatabaseSchemas,3.6.1Anomalies(异常),Anomaly:即不符合规范的设计，导致操作数据库时，出现影响数据一致性的现象。Goalofrelationalschemadesignistoavoidanomalies.Theprincipalkindsofanomalies:Redundancy:Informationmayberepeatedunnecessarilyinseveraltupels.UpdateAnomalies(更新异常):Wemaychangeinformationinonetuplebutleavethesameinformationunchangedinanother.DeletionAnomalies(删除异常).validfactislostwhenatupleisdeleted.,3.6.1Anomalies(异常),Example:Student,3.6.2DecomposingRelations,Decomposingrelations:GivenarelationRwithschemaA1,A2,.,An,wemaydecomposeRintotworelationsSandTwithschemasB1,B2,.,BmandC1,C2,.,Ck,suchthatA1,A2,.,An=B1,B2,.,BmC1,C2,.,Ck.Thetuplesinrela