数据库Database Systems(3)

3DesignTheoryforRelationalDatabasesFunctionalDependenciesRulesAboutFunctionalDependenciesDesignofRelationalDatabaseSchemasDecomposition:TheGood,Bad,orUglyThirdNormalFormMultivaluedDependenciesAnAlgorithmforDiscoveringMVD’s3.1FunctionalDependencies(函数依赖)Itiscommonforaninitialrelationalschematohaveroomforimprovement,especiallybyeliminatingredundancy(消除冗余).Thereisadesigntheoryforrelationsthatletsusexamineadesigncarefullyandmakeimprovementsbasedonafewsimplepriciples.Ourdiscussionstartswith“functionaldependencies”,ageneralizationoftheideaofakeyforarelation.3.1.1DefinitionofFunctionalDependencyThefunctionaldependencyXAholdsonRifandonlyifforanylegalrelationsr(R),wheneveranytwotuplest1andt2ofragreeontheattributesX,theyalsoagreeontheattributeA.–Say“Xfunctionallydetermine(函数决定)A.”–Say“Afunctionallydependon(函数依赖于)X.”3.1.1DefinitionofFunctionalDependencyAfunctionaldependency(FD)onarelationRisanassertion:iftwotuplesofRagreeonalloftheattributesA1,A2,…,An,thentheymustalsoagreeonallofanotherlistofattributesB1,B2,…,Bm.WewritethisFDformallyasA1A2…AnB1B2…BmorA={A1,A2,…,An},B={B1,B2,…,Bm}AB3.1.1DefinitionofFunctionalDependencyExample3.1：LetusconsidertherelationMovies(title,year,length,genre,studioName,starName)titleyearlengthgenrestudioNamestarNameStarWarsStarWarsStarWarsGoneWiththeWindWayne’sWorldWayne’sWorld1977197719771939199219921241241242319595SciFiSciFiSciFidramacomedycomedyFoxFoxFoxMGMParamountParamountCarrieFisherMarkHamillHarrisonFordVivienLeighDanaCarveyMikeMeyerstitleyearlengthgenrestudioNameconsider：titleyearstarName?3.1.1DefinitionofFunctionalDependencyRememberthataFD,likeanyconstraint,isanassertionabouttheschemaofarelation,notaboutaparticularinstance.Example:ConsiderR(A,B)withthefollowinginstance.Onthisinstance,ABdoesNOThold,butdoesBAhold?ABa1b1a2b3a1b23.1.1DefinitionofFunctionalDependencyCorollary(推论)1:–A1A2…AnB1–A1A2…AnB2–…–A1A2…AnBmiff(ifandonlyif)–A1A2…AnB1B2…BmCorollary2:–AA3.1.1DefinitionofFunctionalDependencyConsiderthefunctionaldependenciesinrelationstudents(Sno,Sname,gender,depid,dorm,Cno,Cname,score).SnoCnoscoreSnoSnamegenderdepiddormdepiddorm,CnoCname分析一个具体关系中的函数依赖：–根据属性之间的语义关系分析函数依赖。–Example:Borrow(date,bookid,Sno)–尽可能使函数依赖式的左面最小化，而右面最大化。SnoSnamegender？Snamegender?SnoSnamegender?Snoscore?SnoCno?SnoCnoscore?3.1.1DefinitionofFunctionalDependencyThreecasesofassertingfunctionaldependencies:–IftwotupleshavethesamevaluesintheirAcomponents,andtheyalsohavethesamevaluesintheirBcomponents,thenABholds.–IftwotupleshavethesamevaluesintheirAcomponents,buttheyhavenotthesamevaluesintheirBcomponents,thenABdoesnothold(AB).–Ifanytwotuplescan’thavethesamevaluesintheirAcomponents,thenABholds.3.1.1DefinitionofFunctionalDependency常见术语：部分函数依赖：若XY，且存在X的真子集X’，X’Y，则称Y对X部分函数依赖。完全函数依赖：若XY，且Y对X不是部分函数依赖，则称Y对X是完全函数依赖。传递函数依赖：若XY，YZ，且YX不成立，则称Z对X是传递函数依赖。3.1.2KeysofRelationsKey:Wesayasetofoneormoreattributes{A1,A2,...,An}isakeyforarelationRif:–{A1,A2,...,An}functionallydetermineallotherattributesoftherelationR.(superkey)ItisimpossiblefortwodistincttuplesofRtoagreeonallofA1,A2,...,An.–Nopropersubset(真子集)of{A1,A2,...,An}canfunctionallydetermineallotherattributesofR.(minimal)3.1.2KeysofRelationsKeyoftherelationMovies(title,year,length,genre,studioName,starName):–{title,year}?–{title,year,starName}?IfABholdsinR(A,B,C)–thekeysofR:–AC3.1.2KeysofRelationsCandidatekey(候选键):–Sometimesarelationhasmorethanonekey.–Allkeysofarelationarecandidatekeys.Primarykey(主键):–Itiscommontodesignateoneofthekeysastheprimarykey.Incommercialdatabasesystems,thechoiceofprimarykeycaninfluence(影响)someimplementationissues.–ThetheoryofFD’sgavesnospecialroleto“primarykeys.”3.1.3Superkeys(超键)Superkeys:–Supersetofakey.–Asetofattributesthatcontainsakey.–Thoseattributesfunctionallydetermineallotherattributesoftherelation.Therelationshipbetweenkeysandsuperkeys:–Keysaresuperkeys.{title,year,starName}–Somesuperkeysarenotkeys.{title,year,length,starName}3.1FunctionalDependencies(函数依赖)Exercises:Considerthefollowingrelationalschema:Sale(clerk,store,city,date,item#,size)//recordsthataclerksoldanitemonaparticulardayItem(item#,size,price)//recordspricesandavailablesizesforitemsMakethefollowingassumptions(假定),andonlytheseassumptions,abouttherealworldbeingmodeled:–Eachclerkworksinonestore.–Eachstoreisinonecity.–Agivenitem#alwayshasthesameprice,regardlessofsize.–Eachitemisavailableinoneormoresizes.Problems:–Basedontheassumptionsabove(andnoothers),specifyanappropriatesetoffunctionaldependenciesforrelationsSaleandItem.–Basedontheassumptionsabove(andnoothers),specifyallkeysforrelationsSaleandItem,respectively.3.1FunctionalDependencies(函数依赖)Answers:–Basedontheassumptionsabove(andnoothers),specifyanappropriatesetoffunctionaldependenciesforrelationsSaleandItem.clerk-store,store-city,item#-price–Basedontheassumptionsabove(andnoothers),specifyallkeysforrelationsSaleandItem,respectively.keyofsale:{clerk,date,item#,size}keyofitem:{item#,size}3.2RulesAboutFunctionalDependenciesReasoningaboutfunctionaldependencies–Supposewearetold