課件說明教案

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（數(shù)據(jù)冗余 DatabasePrinciples& redundency（數(shù)據(jù)冗余?wasteofdiskSnoSnameDeptSageCnoCnameGradeS0001WangC101ABC5S0001WangC102ACD5S0001WangC103BBC4S0001WangC105AEF3S0001WangBCF433S0002S0002ChenChenMAMAC103C105AEFS0003ZhangYimouC107BHD4Relation DatabasePrinciples& ?wasteof?usermightgetitSnSnamDepSagCnCnamGradS0001WangJianC17C101AB5S0001WangJianC17C102AC5S0001WangJianC17C103BB4S0001WangJianC17C105AE3S0001WangJianC17C110BC4S0002ChenYinM19C103BB3S0002ChenYinM19C105AE3S0003ZhangYimouC17C107BH4Relation 行上的時間開銷，也可能因為修改不徹底而導(dǎo)致數(shù)據(jù)不一致性?mightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33S0003ZhangYimCS17C107BHD4 執(zhí)執(zhí)行元組刪除操作，可能連帶刪除掉一些本不該被刪除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 假設(shè)需要刪除學(xué)生元組：“S0003,ZhangYimou,CS,3)abnormityof?mightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33S0003 ngYim CS17C107BHD477 abnormityof?mightlosesomeSnoSnameDeptSageCnoCnameGradeS0001WangJianCS17C101ABC5S0001WangJianCS17C102ACD5S0001WangJianCS17C103BBC4S0001WangJianCS17C105AEF3S0001WangJianCS17C110BCF4S0002S0002ChenYingChenYingMM1919C103C105BBCAEF33Relation （刪除后的結(jié)果關(guān)系2017-4- DatabasePrinciples& ?unsuccessfulSnoSnameDeptSageCnoCnameGradeS0001WangJianCSC101ABC5S0001WangJianCSC102ACD5S0001WangJianCSC103BBC4S0001WangJianCSC105AEF3S0001WangJianCSC110BCF4S0002S0002ChenYingChenYingMMC103C105BBCAEF33S0003ZhangYimouCSC107BHD4Relation 可能因 實體完整性約束而導(dǎo)致元組插入失敗 例如：“插入一條沒有選課信息的學(xué)生元組”將執(zhí) 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（聯(lián)系）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（二元聯(lián)系）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籃球聯(lián)賽信息管理q6.4.3聊天 q6.4.4郵件信息管理CaseStudy（例設(shè)有一個 閱理據(jù)知： 的屬性書號（有一）書；者屬借書證具唯每讀只有書證）、 、 、 ； 的屬性有 稱具唯性、址聯(lián)電話。 DatabasePrinciples& 6.4CaseStudy（例§每個球員的球衣號碼、 §每個球隊的名§每場比賽的比賽日期和比分§每個球員只能效§比賽采用主客 DatabasePrinciples& 6.4CaseStudy（例q假設(shè)需要設(shè)計一個用于網(wǎng)絡(luò) 用戶的用戶名 ，聯(lián)系地§帖子的帖子ID，標(biāo)題，內(nèi) DatabasePrinciples& CaseStudy（例q有一個§聯(lián)系人：用戶名， §郵件：郵件ID，郵件標(biāo)題，郵件內(nèi)容，收信人集§郵件之間的回復(fù)關(guān) DatabasePrinciples& Normalization(規(guī)范化):qNormalFormNF，范式qARunning?Figure6.15(pg.?Def.6.5.1Update?Def.6.5.2DeleteAnomaly,Insert DatabasePrinciples& qFunctionalDependencyFD函數(shù)依賴? 函數(shù)依賴來自于現(xiàn)實世界中數(shù)據(jù)qArmstrong’sAxiomsArmstrong公理?基本規(guī)則：自反規(guī)則，傳遞規(guī)則，增廣規(guī)?擴充規(guī)則：合并規(guī)則，分解規(guī) 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（自反規(guī)則）：Inclusion§IfYX，thenX→§IfX→YandY→Z，thenX→?Rule3（增廣規(guī)則）Augmentation§IfX→Y,thenXZ→qFigure6.19(pg.qFigure6.19(pg.1.1.InclusionXYTransitivityY YXXYZ6.6FunctionalqRule1:InclusionRuleIfYX，thenX→Y§設(shè)t1,t2是關(guān)系R中的任意兩個元組(t1R,且它們在屬性集X上的值相等(t1[X]=§由于Y是X的子集，即X§因此必有t1[Y] DatabasePrinciples& 6.6FunctionalqRule2:TransitivityIfX→YandY→Z，thenX→§設(shè)t1R,t2R,如果t1[X]= §由(2)及Y→Z得：t1[Z] DatabasePrinciples& 6.6FunctionalqRule3:AugmentationruleIfX→Y,thenXZ→YZ§設(shè)t1Rt2Rt1[XZt2[XZt1[X]= t1[Z]= §由(2)及(3)得：t1[YZ DatabasePrinciples& 6.6FunctionalqTheorem6.6.8SomeImplicationsofArmstrong’s（pg.363）?Rule4UnionRule（合并規(guī)則IfX→YandX→Z，thenX→?Rule positionRule（分解規(guī)則IfX→YZ，thenX→Y，andX→?Rule6PseudotransitivityRule（偽傳遞規(guī)則IfX→Y，andWY→Z，thenXW→?Rule7Setaccumulationrule（聚積規(guī)則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也可以按照如下順序考慮可能存在的函數(shù)依賴情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關(guān)系中，我們不用ACB，whyq因此，最后只需要考慮下面的一個FD是否可能成 AC→D√ABCDA→D→ABCAC→D

C→6.66.6Functional2017-4- DatabasePrinciples& q該關(guān)系上可能存在的函數(shù)依A→B C→BD→ABC 思考問題：

AC→左邊含有屬性D的其它的那些可能的右邊為單個屬性B的其它的那些可能的右邊為多個屬性的那些可能的ContentofqClosureofaSetofFDs(函數(shù)依賴集F的閉包)qFDSetCover(函數(shù)依賴集的覆蓋)qEquivalenceoftwosetsofFDS(函數(shù)依賴集的等價qClosureofaSetofAttributes(屬性集的閉包?AlgorithmqMinimalCover(最小覆蓋?Algorithm DatabasePrinciples& 6.6FunctionalqDef.6.6.9ClosureofaSetofFDs(函數(shù)依賴集F的閉包，記為F+)?GivenasetFofFDsonattributesofatableT,wedefinetheCLOSUREofF,symbolizedbyF+,tobethesetofallFDsimpliedbyF.F+根據(jù)F中已有的函數(shù)依賴，利用Armstrong公理系統(tǒng)能夠推導(dǎo)得到的所有函數(shù)依賴} 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(函數(shù)依賴集的覆蓋?AsetFofFDsonatableTissaidtoCOVERanothersetGofFDsonTifthesetGcanbederivedbyimplicationrulesfromthesetF,i.e.,ifGF+.q函數(shù)依?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)的函數(shù)依每一個函數(shù)依賴的左邊都沒有多余的屬?a沒有冗余(inessential)的函數(shù)依每一個函數(shù)依賴的左邊都沒有多余的屬 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個子關(guān)系模式，從所存在的函數(shù)依賴集為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(xiàn):{BD,ABCR(A,B, F:{AB,BA,ACR(A,B,C,D)，F(xiàn):{AC,CDB DatabasePrinciples& 6.8NormalR(A,B,C,D)，F(xiàn):{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}+