A-Relational-Model-of-Data-for-Large-Shared-Data-B

1ARelationalModelofDataforLargeSharedDataBanksE.F.CoddIBMResearchLaboratory,1970PresentedbyQingminLiu*Getslideson“~liuqmin/cs757.ppt”2Including......IntroductionRelationalModelNormalFormOperationsonRelationsRedundancyConsistencySummary3IntroductionFutureusersoflargedatabasemustbeprotectedfromhavingtoknowhowthedataisorganizedintheinternalrepresentation.Apromptingservicewhichsuppliessuchinformationisnotasatisfactorysolution.Activitiesofusersofterminalsandmostapplicationprogramsshouldremainunaffectedwhentheinternalrepresentationofdataischangedandevenwhensomeaspectsoftheexternalrepresentationarechanged.Changesindatarepresentationwilloftenbeneededasaresultofchangesinquery,update,andreporttrafficandnaturalgrowthintypesofstoredinformation.4IntroductionTherelationalmodelissuperiorinseveralrespectstothegraphornetworkmodel:–Itprovidesameansofdescribingdatawithitsnaturalstructureonly,thatis,withoutsuperimposinganyadditionalstructureformachinerepresentationpurposes.–Itformsasoundbasisfortreatingderivability,redundancy,andconsistencyofrelations.–Itpermitsaclearerevaluationofthescopeandlogicallimitationsofpresentformatteddatasystems,andalsotherelativemeritsofcompetingrepresentationsofdatawithinasingesystem.5RelationalModelWhyRelationalModel?–Varietyofdatarepresentationcharacteristicswhichcanbechangedwithoutlogicallyimpairingsomeapplicationprograms.–Toremovethreeoftheprincipalkindsofdatadependencies:Orderingdependence:confusedbysystemandapplicationIndexingdependence:slowdownresponsetoinsertion,deletions.Accesspathdependence:impairedapplicationprogramsiftreeornetworkdataarechangedinstructure.6RelationalModelWhatRelationalModel?–Risarelationonnsets(S1,S2,…Sn)ifitisasetofntupleseachofwhichhasitsfirstelementfromS1,secondelementfromS2,andsoon.–SjisreferredasthejthdomainofrelationR.–Rissaidtohavedegreen.Degree1–unaryDegree2–binaryDegree3–ternaryDegreen–n-ary7RelationalModelPropertiesofn-aryrelationR–Eachrowrepresentsann-tupleofR.–Theorderingofrowsisimmaterial.–Allrowsaredistinct.–Theorderingofcolumnsissignificant.–Thesignificanceofeachcolumnispartiallyconveyedbylabelingitwiththenameofthecorrespondingdomain.8RelationalModelExampleof4-aryrelationSupply(supplierpartprojectquantity)12517135232379275441112RelationNameDomainNameAtupleDegree49RelationalModelConcepts–Primarykey:onedomain(orcombination)hasvalueswhichuniquelyidentifyeachelementoftherelation.It’snon-redundant.–Foreignkey:adomainthatisnottheprimarykeyofRbutitselementsarevaluesoftheprimarykeyofsomerelationS.–Simpledomain:itselementisatomicvalue.–Non-simpledomain:itselementisnonatomic.10NormalFormNormalformisawaytoestablishrelationalmodel.Arelationwhosedomainsareallsimplecanberepresentedinstoragebyatwodimensionalcolumn-homogeneousarrayasdiscussedabove.Somemorecomplicateddatastructureisnecessaryforarelationwithoneormorenonsimpledomains.11NormalFormNormalization:–Eliminationprocedureofnonsimpledomains.Procedure:–Startwiththerelationatthetopofthetree,takeitsPKandexpandeachoftheimmediatelysubordinaterelationsbyinsertingthisPKdomainordomaincombination.–ThePKofeachexpandedrelationconsistsofthePKbeforeexpansionaugmentedbythePKcopieddownfromtheparentrelation.–Strikeoutfromtheparentrelationallnonsimpledomains,removethetopnodeofthetree.–Repeatthesamesequenceoneachremainingsubtree.12NormalFormNormalizationExample–Unnormalizedsetofrelationemployeeemployee(man#,name,birthday,jobhistory,children)jobhistory(jobdate,title,salaryhistory)salaryhistory(salarydate,salary)children(childrenname,birthdate)–Normalizedsetofemployeeemployee’(man#,name,birthday)jobhistory’(man#,jobdate,title)salaryhistory’(man#,jobdate,salarydate,salary)children’(man#,childrenname,birthdate)employeejobhistorychildrensalaryhistory13OperationsonRelationsSelect()–SelectsalltuplesthatsatisfytheselectionconditionfromrelationR.selectcondition(R).Project()–ProducesanewrelationwithonlysomeoftheattributesofR,andremovesduplicatetuples.attributelist(R)Cartesianproduct()–ProducearelationthathastheattributesofR1andR2andincludesastuplesallpossiblecombinationsoftuplesfromR1andR2.R1R2.14OperationsonRelationsSetOperationsUnioncompatible:R(A1,A2,…An)andS(B1,B2,…Bn)areunioncompatibleifRandShavesamedegreen,anddom(Ai)=dom(Bi)–Union():producearelationthatincludesallthetuplesinR1orR2orbothR1andR2.R1R2.–Intersection():producearelationthatincludesallthetuplesinbothR1andR2.R1R2.–Difference():producearelationthatincludesallthetuplesinR1thatarenotinR2.R1R2.Join–Thetajoin():produceallcombinationsoftuplesfromR1andR2thatsatisfythejoinconditions(=:equijoin,,,,,).R1cR2.–Naturaljoin(*):sameasequijoinexceptthatthejoinattributesofR2arenotincludedintheresultingrelation.R1*R2.15RedundancyStrongRedundancy–Asetofrelationsisstronglyredundantifitcontainsatleastonerelationthatpossessesaprojectionwhichisderivablefromotherprojectionsofrelationsintheset.–Existenceofstrongredundanciesisuserconvenience,whichenablesasystemordatabaseadministratorgreaterfreedomintheselectionofstoredrepresentationtocopemoreefficientlywithcu