《數(shù)據(jù)庫系統(tǒng)》英文教學(xué)課件

《數(shù)據(jù)庫系統(tǒng)》英文教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),英文,教學(xué),課件 1Database SystemsLecture#4Guifeng ZhengSchool of Software,SYSUGuifeng Zheng,DBMS,SS/SYSU2AgendanLast time:relational modelnThis time:1.Functional dependenciesqKeys and superkeys in terms of FDsqFinding keys for relations2.Extended E/R example3.Rules for combining FDsnNext time:anomalies&normalizationGuifeng Zheng,DBMS,SS/SYSU3Where are we going,where have we been?nGoal:manage large amounts of data effectivelyn Use a DBMSn must define a schemanDBMSs use the relational modelqBut initial design is easier in E/Rn Must design an E/R diagramn Must then convert it to rel.modelGuifeng Zheng,DBMS,SS/SYSU4Where are we going,where have we been?nAt this pt,often find problems redundancyqHow to fix?n Convert the tables to a special“normal”formqHow to do this?n First step is:check which FDs there areqThe reason we looked at FDs last timeqWill have to look at all true FDs of the tableqThen well do decompositionsGuifeng Zheng,DBMS,SS/SYSU5Next topic:Functional dependenciesnFDs are constraintsqLogically part of the schemaqcant tell from particular relation instancesqFD may hold for some instances“accidentally”nFinding all FDs is part of DB designqUsed in normalizationGuifeng Zheng,DBMS,SS/SYSU6Functional dependenciesnDefinition:nNotation:nRead as:Ai functionally determines BjIf two tuples agree on the attributes A1,A2,Anthen they must also agree on the attributesB1,B2,BmA1,A2,An B1,B2,BmGuifeng Zheng,DBMS,SS/SYSU7Typical Examples of FDsnProductqname price,manufacturernPersonqssn name,ageqfathers/husbands-name last-nameqzipcode stateqphone state(notwithstanding inter-state area codes?)nCompanyqname stockprice,presidentqsymbol nameqname symbolGuifeng Zheng,DBMS,SS/SYSU8Functional dependenciesnTo check A B,erase all other columns;for all rows t1,t2ni.e.,check if remaining relation is many-oneqno“divergences”qi.e.,if AB is a well-defined functionqthus,functional dependencyBm.B1Am.A1t1t2if t1,t2 agree here then t1,t2 agree hereGuifeng Zheng,DBMS,SS/SYSU9FD exampleProduct(name,category,color,department,price)name colorcategory departmentcolor,category priceConsider these FDs:What do they say?Guifeng Zheng,DBMS,SS/SYSU10FD exampleFDs as properties:On some instances they hold On others they dontnamecategorycolordepartmentpriceGizmoGadgetGreenToys49TweakerGadgetGreenToys99Does this instance satisfy all the FDs?name colorcategory departmentcolor,category priceGuifeng Zheng,DBMS,SS/SYSU11FD examplenamecategorycolordepartmentpriceGizmoGadgetGreenToys49TweakerGadgetBlackToys99GizmoStationaryGreenOffice-supp.59What about this one?name colorcategory departmentcolor,category priceGuifeng Zheng,DBMS,SS/SYSU12nQ:Is PositionPhone an FD here?nA:It is for this instance,but no,presumably not in generalnOthers FDs?nEmpID Name,Phone,Positionnbut Phone PositionRecognizing FDsEmpIDNamePhonePositionE0045Smith1234ClerkE1847John9876SalesrepE1111Smith9876SalesrepE9999Mary1234LawyerGuifeng Zheng,DBMS,SS/SYSU13Keys(candidate key)of relationsnA1A2A3An is a key for relation R if qA1A2A3An functionally determine all other attsnUsual notation:A1A2A3An B1B2Bknrels=sets distinct rows cant agree on all Ai qA1A2A3An is minimal(candidate key)nNo proper subset of A1A2A3An functionally determines all other attributes of RnPrimary key:chosen if there are several possible keysGuifeng Zheng,DBMS,SS/SYSU14Keys examplenRelation:Student(ssn,Name,Address,DoB,Email,Credits)nWhich(/why)of the following are keys?qSSNqName,Address(on reasonable assumptions)qName,SSNqEmail,SSNqEmailnNB:minimal!=smallestGuifeng Zheng,DBMS,SS/SYSU15SuperkeysnDf:A set of attributes that contains a keynSatisfies first condition:determinationnMight not satisfy the second:minimalityqSome superkey attributes may be superfluousqkeys are superkeysnkey are special case of superkeyqsuperkey set is superset of key setnname;ssn is a superkey but not a keyGuifeng Zheng,DBMS,SS/SYSU16Discovering keys for relationsnRelation entity setqKey of relation=(minimized)key of entity set nRelation binary relationshipqMany-many:union of keys of both entity setsqMany(M)-one(O):only key of M(why?)qOne-one:key of either entity set(but not both!)Guifeng Zheng,DBMS,SS/SYSU17Review:entity setsnKey of entity set=key of relationnStudent(Name,Address,DoB,SSN,Email,Credits)StudentNameAddressDoBSSNEmailCreditsGuifeng Zheng,DBMS,SS/SYSU18Review:many-manynMany-many key:union of both ES keysStudentEnrollsCourseSSNCreditsCourseIDNameEnrolls(SSN,CourseID)Guifeng Zheng,DBMS,SS/SYSU19Review:many-onenKey of the many ES but not of the one ESqkeys from both would be non-minimalCourseMeetsInRoomCourseIDNameRoomNoCapacityMeetsIn(CourseID,RoomNo)Guifeng Zheng,DBMS,SS/SYSU20Review:one-onenKeys of both ESs included in relationnKey is key of either ES(but not both!)HusbandsMarriedWivesSSNNameSSNNameMarried(HSSN,WSSN)or Married(HSSN,WSSN)Guifeng Zheng,DBMS,SS/SYSU21Review:multiway relshipsnMultiple ways may not be obviousnR:F,G,HE is many-one Es key is includedqbut not part of keyqRecall that relship atts are implicitly many-oneCourseEnrollsStudentCourseIDNameSSNNameSectionRoomNoCapacityEnrolls(CourseID,SSN,RoomNo)Guifeng Zheng,DBMS,SS/SYSU22Extended E/R example:Exercise 2.3nProfs have:ssn,name,age,rank,specialtynProjs have:proj#,sponsor name(e.g.NSF),start date,end date,budgetnGrad students have:ssn,name,age,degree programnEach proj:managed by one profnEach proj:worked on by one or more profsnEach proj:worked on by one or more grad studentsnWhen grad students work on a proj,a prof must supervise their work.Grad students may have different supervisors for each proj.nDepts have:dept#,dept name,main officenProfs work in one or more departments,and a percent-worked in each deptnGrad students have one major dept in which they worknThen convert to relationsGuifeng Zheng,DBMS,SS/SYSU23Extended E/R example:Exercise 2.7nPatients are IDed by ssn,and they have names,addresses,and agesnDoctors are IDed by ssn.For each doctor,record name,specialty,years of experiencenEach pany is IDed by name and has a phone numbernFor each drug,the trade name and foruma are recorded.Each is sold by a given pany,and the trade name IDs a drug uniquely from the products of that company.If a pany is deleted,you need not keep track of its products any longer.nEach pharmacy has:name,address,phone numbernEvery patient has a primary physician.Doctors can have multiple patients.nEach pharmacy can sell several drugs and has a price of each.A drug price could vary between pharmacies.nDoctors prescribe drugs for patients.A doctor could prescribe multiple drugs for multiple patients,and a patient could obtain prescriptions from multiple doctors.Each prescription has a date and quantity.Assume that if a doctor prescribes the same drug for the same patient multiple times,we only record the last prescription.nA pany can contract with several pharmacies,and vice versa.For each contract,store the text and start and end dates.nPharmacies appoint a unique supervisor for each contract.nHow would this change if each drug had a single price?Guifeng Zheng,DBMS,SS/SYSU24Guifeng Zheng,DBMS,SS/SYSU25Next topic:Combining FDsIf some FDs are satisfied,thenothers are satisfied tooIf all these FDs are true:name colorcategory departmentcolor,category priceThen this FD also holds:name,category priceWhy?Guifeng Zheng,DBMS,SS/SYSU26Rules for FDs(quickly)nReasoning about FDs:given a set of FDs,infer other FDs usefulqE.g.A B,B C A CnDefinitions:for FD-sets S and TqT follows from S if all relation-instances satisfying S also satisfy T.qS and T are equivalent if the sets of relation-instances satisfying S and T are the same.qI.e.,S and T are equivalent if S follows from T,and T follows from S.Guifeng Zheng,DBMS,SS/SYSU27Splitting&combining FDs(quickly)Splitting rule:Combining rule:Note:doesnt apply to the left sideQ:Can you split and combine the As,too?A1A2An B1B2BmA1,A2,An B1A1,A2,An B2 .A1,A2,An BmBm.B1Am.A1t1t2Guifeng Zheng,DBMS,SS/SYSU28Reflexive rule:trivial FDs(quickly)nFD A1A2An B1B2Bk may beqTrivial:Bs are a subset of AsqNontrivial:=1 of the Bs is not among the AsqCompletely nontrivial:none of the Bs is among the AsnTrivial elimination rule:qEliminate common attributes from Bs,to get an equivalent completely nontrivial FDA1,A2,An Aiwith i in 1.n is a trivial FDA1AnttGuifeng Zheng,DBMS,SS/SYSU29Transitive rule(quickly)IfandthenA1,A2,An B1,B2,BmB1,B2,Bm C1,C2,CpA1,A2,An C1,C2,CpA1AmB1BmC1.CpttGuifeng Zheng,DBMS,SS/SYSU30Augmentation rule(quickly)IfthenA1,A2,An BA1,A2,An,C B,C,for any CA1AmB1BmC1.CpttGuifeng Zheng,DBMS,SS/SYSU31Rules summary(quickly)1.A B AC B(by definition)2.Separation/Combination3.Reflexive4.Augmentation5.TransitivitynLast 3 called Armstrongs AxiomsqComplete:entire closure follows from theseqSound:no other FDs follow from thesenDont need to memorize detailsGuifeng Zheng,DBMS,SS/SYSU32Inferring FDs example(quickly)Start from the following FDs:Infer the following FDs:1.name color2.category department3.color,category priceInferred FDWhich Ruledid we apply?4.name,category name5.name,category color6.name,category category7.name,category color,category8.name,category priceReflexive ruleTransitivity(4,1)Reflexive rulecombine(5,6)or Aug(1)Transitivity(3,7)Guifeng Zheng,DBMS,SS/SYSU33Problem:infer all FDsGiven a set of FDs,infer all possible FDsHow to proceed?nTry all possible FDs,apply all rulesqE.g.R(A,B,C,D):how many FDs are possible?nDrop trivial FDs,drop augmented FDsqStill way too manynBetter:use the Closure AlgorithmGuifeng Zheng,DBMS,SS/SYSU34Closure of a set of AttributesGiven a set of attributes A1,An The closure,A1,An+=B in Atts:A1,An Bname colorcategory departmentcolor,category priceExample:Closures:name+=name,color name,category+=name,category,color,department,price color+=colorGuifeng Zheng,DBMS,SS/SYSU35Closure AlgorithmStart with X=A1,An.Repeat:if B1,Bn C is a FD and B1,Bn are all in X then add C to X.until X doesnt changename,category+=name,category,color,department,pricename colorcategory departmentcolor,category priceExample:Guifeng Zheng,DBMS,SS/SYSU36ExampleCompute A,B+X=A,B,Compute A,F+X=A,F,R(A,B,C,D,E,F)A,B CA,D EB DA,F BIn class:Guifeng Zheng,DBMS,SS/SYSU37Next timenRead ch.19,sections 4-5