数据库系统概念全套配套课件PPT appC.ppt 61页

'AppendixC:OtherRelationalLanguages AppendixC:OtherRelationalLanguagesQuery-by-Example(QBE)AccessDatalog Query-by-Example(QBE)BasicStructureQueriesonOneRelationQueriesonSeveralRelationsTheConditionBoxTheResultRelationOrderingtheDisplayofTuplesAggregateOperationsModificationoftheDatabase QBE—BasicStructureAgraphicalquerylanguagewhichisbased(roughly)onthedomainrelationalcalculusTwodimensionalsyntax–systemcreatestemplatesofrelationsthatarerequestedbyusersQueriesareexpressed“byexample” QBESkeletonTablesfortheBankExample QBESkeletonTables(Cont.) QueriesonOneRelationFindallloannumbersatthePerryridgebranch._xisavariable(optional;canbeomittedinabovequery)P.meansprint(display)duplicatesareremovedbydefaultToretainduplicatesuseP.ALLP._x QueriesonOneRelation(Cont.)DisplayfulldetailsofallloansP._xP._yP._zMethod1:Method2:Shorthandnotation QueriesonOneRelation(Cont.)FindnamesofallbranchesthatarenotlocatedinBrooklynFindtheloannumberofallloanswithaloanamountofmorethan$700 QueriesonOneRelation(Cont.)FindtheloannumbersofallloansmadejointlytoSmithandJones.FindallcustomerswholiveinthesamecityasJones. QueriesonSeveralRelationsFindthenamesofallcustomerswhohavealoanfromthePerryridgebranch. QueriesonSeveralRelations(Cont.)Findthenamesofallcustomerswhohavebothanaccountandaloanatthebank. NegationinQBEFindthenamesofallcustomerswhohaveanaccountatthebank,butdonothavealoanfromthebank.¬means“theredoesnotexist” NegationinQBE(Cont.)Findallcustomerswhohaveatleasttwoaccounts.¬means“notequalto” TheConditionBoxAllowstheexpressionofconstraintsondomainvariablesthatareeitherinconvenientorimpossibletoexpresswithintheskeletontables.ComplexconditionscanbeusedinconditionboxesExample:FindtheloannumbersofallloansmadetoSmith,toJones,ortobothjointly ConditionBox(Cont.)QBEsupportsaninterestingsyntaxforexpressingalternativevalues. ConditionBox(Cont.)Findallaccountnumberswithabalancegreaterthan$1,300andlessthan$1,500.Findallaccountnumberswithabalancegreaterthan$1,300andlessthan$2,000butnotexactly$1,500. ConditionBox(Cont.)FindallbranchesthathaveassetsgreaterthanthoseofatleastonebranchlocatedinBrooklyn. TheResultRelationFindthecustomer_name,account_number,andbalanceforallcustomerswhohaveanaccountatthePerryridgebranch.Weneedto:Joindepositorandaccount.Projectcustomer_name,account_numberandbalance.Toaccomplishthiswe:Createaskeletontable,calledresult,withattributescustomer_name,account_number,andbalance.Writethequery. TheResultRelation(Cont.)Theresultingqueryis: OrderingtheDisplayofTuplesAO=ascendingorder;DO=descendingorder.Example:listinascendingalphabeticalorderallcustomerswhohaveanaccountatthebank.Whensortingonmultipleattributes,thesortingorderisspecifiedbyincludingwitheachsortoperator(AOorDO)anintegersurroundedbyparentheses.Example:ListallaccountnumbersatthePerryridgebranchinascendingalphabeticorderwiththeirrespectiveaccountbalancesindescendingorder. AggregateOperationsTheaggregateoperatorsareAVG,MAX,MIN,SUM,andCNTTheaboveoperatorsmustbepostfixedwith“ALL”(e.g.,SUM.ALL.orAVG.ALL._x)toensurethatduplicatesarenoteliminated.Example:FindthetotalbalanceofalltheaccountsmaintainedatthePerryridgebranch. AggregateOperations(Cont.)UNQisusedtospecifythatwewanttoeliminateduplicates.Findthetotalnumberofcustomershavinganaccountatthebank. QueryExamplesFindtheaveragebalanceateachbranch.The“G”in“P.G”isanalogoustoSQL’sgroupbyconstruct.The“ALL”inthe“P.AVG.ALL”entryinthebalancecolumnensuresthatallbalancesareconsidered.Tofindtheaverageaccountbalanceatonlythosebrancheswheretheaverageaccountbalanceismorethan$1,200,wesimplyaddtheconditionbox: QueryExampleFindallcustomerswhohaveanaccountatallbrancheslocatedinBrooklyn.Approach:foreachcustomer,findthenumberofbranchesinBrooklynatwhichtheyhaveaccounts,andcomparewithtotalnumberofbranchesinBrooklyn.QBEdoesnotprovidesubqueryfunctionality,sobothabovetaskshavetobecombinedinasinglequery.Canbedoneforthisquery,buttherearequeriesthatrequiresubqueriesandcannotalwaysbeexpressedinQBE.InthequeryonthenextpageCNT.UNQ.ALL._wspecifiesthenumberofdistinctbranchesinBrooklyn.Note:Thevariable_wisnotconnectedtoothervariablesinthequery.CNT.UNQ.ALL._zspecifiesthenumberofdistinctbranchesinBrooklynatwhichcustomerxhasanaccount. QueryExample(Cont.) ModificationoftheDatabase–DeletionDeletionoftuplesfromarelationisexpressedbyuseofaD.command.Inthecasewherewedeleteinformationinonlysomeofthecolumns,nullvalues,specifiedby–,areinserted.DeletecustomerSmithDeletethebranch_cityvalueofthebranchwhosenameis“Perryridge”. DeletionQueryExamplesDeleteallloanswithaloanamountgreaterthan$1300andlessthan$1500.Forconsistency,wehavetodeleteinformationfromloanandborrowertables DeletionQueryExamples(Cont.)DeleteallaccountsatbrancheslocatedinBrooklyn. ModificationoftheDatabase–InsertionInsertionisdonebyplacingtheI.operatorinthequeryexpression.InsertthefactthataccountA-9732atthePerryridgebranchhasabalanceof$700. ModificationoftheDatabase–Insertion(Cont.)ProvideasagiftforallloancustomersofthePerryridgebranch,anew$200savingsaccountforeveryloanaccounttheyhave,withtheloannumberservingastheaccountnumberforthenewsavingsaccount. ModificationoftheDatabase–UpdatesUsetheU.operatortochangeavalueinatuplewithoutchangingallvaluesinthetuple.QBEdoesnotallowuserstoupdatetheprimarykeyfields.UpdatetheassetvalueofthePerryridgebranchto$10,000,000.Increaseallbalancesby5percent. MicrosoftAccessQBEMicrosoftAccesssupportsavariantofQBEcalledGraphicalQueryByExample(GQBE).GQBEdiffersfromQBEinthefollowingwaysAttributesofrelationsarelistedvertically,onebelowtheother,insteadofhorizontally.Insteadofusingvariables,lines(links)betweenattributesareusedtospecifythattheirvaluesshouldbethesame.Linksareaddedautomaticallyonthebasisofattributename,andtheusercanthenaddordeletelinks.Bydefault,alinkspecifiesaninnerjoin,butcanbemodifiedtospecifyouterjoins.Conditions,valuestobeprinted,aswellasgroupbyattributesareallspecifiedtogetherinaboxcalledthedesigngrid. AnExampleQueryinMicrosoftAccessQBEExamplequery:Findthecustomer_name,account_numberandbalanceforallaccountsatthePerryridgebranch. AnAggregationQueryinAccessQBEFindthename,streetandcityofallcustomerswhohavemorethanoneaccountatthebank. AggregationinAccessQBETherowlabeledTotalspecifies:whichattributesaregroupbyattributes.whichattributesaretobeaggregatedupon(andtheaggregatefunction).Forattributesthatareneithergroupbynoraggregated,wecanstillspecifyconditionsbyselectingwhereintheTotalrowandlistingtheconditionsbelow.AsinSQL,ifgroupbyisused,onlygroupbyattributesandaggregateresultscanbeoutput. DatalogBasicStructureSyntaxofDatalogRulesSemanticsofNonrecursiveDatalogSafetyRelationalOperationsinDatalogRecursioninDatalogThePowerofRecursion BasicStructureProlog-likelogic-basedlanguagethatallowsrecursivequeries;basedonfirst-orderlogic.ADatalogprogramconsistsofasetofrulesthatdefineviews.Example:defineaviewrelationv1containingaccountnumbersandbalancesforaccountsatthePerryridgebranchwithabalanceofover$700.v1(A,B):–account(A,“Perryridge”,B),B>700.Retrievethebalanceofaccountnumber“A-217”intheviewrelationv1.?v1(“A-217”,B).Tofindaccountnumberandbalanceofallaccountsinv1thathaveabalancegreaterthan800?v1(A,B),B>800 ExampleQueriesEachruledefinesasetoftuplesthataviewrelationmustcontain.E.g.,v1(A,B):–account(A,“Perryridge”,B),B>700isreadas:forallA,Bif(A,“Perryridge”,B)accountandB>700then(A,B)v1Thesetoftuplesinaviewrelationisthendefinedastheunionofallthesetsoftuplesdefinedbytherulesfortheviewrelation.Example:interest_rate(A,5):–account(A,N,B),B<10000interest_rate(A,6):–account(A,N,B),B>=10000 NegationinDatalogDefineaviewrelationcthatcontainsthenamesofallcustomerswhohaveadepositbutnoloanatthebank:c(N):–depositor(N,A),notis_borrower(N).is_borrower(N):–borrower(N,L).NOTE:usingnotborrower(N,L)inthefirstruleresultsinadifferentmeaning,namelythereissomeloanLforwhichNisnotaborrower.Topreventsuchconfusion,werequireallvariablesinnegated“predicate”toalsobepresentinnon-negatedpredicates. NamedAttributeNotationDatalogrulesuseapositionalnotationthatisconvenientforrelationswithasmallnumberofattributes.ItiseasytoextendDatalogtosupportnamedattributes.E.g.,v1canbedefinedusingnamedattributesasv1(account_numberA,balanceB):–account(account_numberA,branch_name“Perryridge”,balanceB),B>700. FormalSyntaxandSemanticsofDatalogWeformallydefinethesyntaxandsemantics(meaning)ofDatalogprograms,inthefollowingsteps:Wedefinethesyntaxofpredicates,andthenthesyntaxofrules.Wedefinethesemanticsofindividualrules.Wedefinethesemanticsofnon-recursiveprograms,basedonalayeringofrules.Itispossibletowriterulesthatcangenerateaninfinitenumberoftuplesintheviewrelation.Topreventthis,wedefinewhatrulesare“safe”.Non-recursiveprogramscontainingonlysaferulescanonlygenerateafinitenumberofanswers.Itispossibletowriterecursiveprogramswhosemeaningisunclear.Wedefinewhatrecursiveprogramsareacceptable,anddefinetheirmeaning. SyntaxofDatalogRulesApositiveliteralhastheformp(t1,t2...,tn)pisthenameofarelationwithnattributeseachtiiseitheraconstantorvariableAnegativeliteralhastheformnotp(t1,t2...,tn)ComparisonoperationsaretreatedaspositivepredicatesE.g.,X>Yistreatedasapredicate>(X,Y)“>”isconceptuallyan(infinite)relationthatcontainsallpairsofvaluessuchthatthefirstvalueisgreaterthanthesecondvalueArithmeticoperationsarealsotreatedaspredicatesE.g.,A=B+Cistreatedas+(B,C,A),wheretherelation“+”containsalltriplessuchthatthethirdvalueisthesumofthefirsttwo SyntaxofDatalogRules(Cont.)Rulesarebuiltoutofliteralsandhavetheform:p(t1,t2,...,tn):–L1,L2,...,Lm.headbodyeachLiisaliteralhead–theliteralp(t1,t2,...,tn)body–therestoftheliteralsAfactisarulewithanemptybody,writtenintheform:p(v1,v2,...,vn).indicatestuple(v1,v2,...,vn)isinrelationpADatalogprogramisasetofrules. SemanticsofaRuleAgroundinstantiationofarule(orsimplyinstantiation)istheresultofreplacingeachvariableintherulebysomeconstant.E.g.,Ruledefiningv1v1(A,B):–account(A,“Perryridge”,B),B>700.Aninstantiationaboverule:v1(“A-217”,750):–account(“A-217”,“Perryridge”,750),750>700.ThebodyofruleinstantiationR’issatisfiedinasetoffacts(databaseinstance)lif1.Foreachpositiveliteralqi(vi,1,...,vi,ni)inthebodyofR’,lcontainsthefactqi(vi,1,...,vi,ni).2.Foreachnegativeliteralnotqj(vj,1,...,vj,nj)inthebodyofR’,ldoesnotcontainthefactqj(vj,1,...,vj,nj). SemanticsofaRule(Cont.)WedefinethesetoffactsthatcanbeinferredfromagivensetoffactslusingruleRas:infer(R,l)={p(t1,...,tn)|thereisagroundinstantiationR’ofRwherep(t1,...,tn)istheheadofR’,andthebodyofR’issatisfiedinl}Givenansetofrules={R1,R2,...,Rn},wedefineinfer(,l)=infer(R1,l)infer(R2,l)...infer(Rn,l) LayeringofRulesDefinetheinterestoneachaccountinPerryridgeinterest(A,l):–perryridge_account(A,B),interest_rate(A,R),l=B*R/100.perryridge_account(A,B):–account(A,“Perryridge”,B).interest_rate(A,5):–account(N,A,B),B<10000.interest_rate(A,6):–account(N,A,B),B>=10000.Layeringoftheviewrelations LayeringRules(Cont.)Arelationisalayer1ifallrelationsusedinthebodiesofrulesdefiningitarestoredinthedatabase.Arelationisalayer2ifallrelationsusedinthebodiesofrulesdefiningitareeitherstoredinthedatabase,orareinlayer1.Arelationpisinlayeri+1ifitisnotinlayers1,2,...,iallrelationsusedinthebodiesofrulesdefiningapareeitherstoredinthedatabase,orareinlayers1,2,...,iFormally: SemanticsofaProgramDefineI0=setoffactsstoredinthedatabase.Recursivelydefineli+1=liinfer(i+1,li)Thesetoffactsintheviewrelationsdefinedbytheprogram(alsocalledthesemanticsoftheprogram)isgivenbythesetoffactslncorrespondingtothehighestlayern.Letthelayersinagivenprogrambe1,2,...,n.Letidenotethesetofallrulesdefiningviewrelationsinlayeri.Note:Caninsteaddefinesemanticsusingviewexpansionlikeinrelationalalgebra,butabovedefinitionisbetterforhandlingextensionssuchasrecursion. SafetyItispossibletowriterulesthatgenerateaninfinitenumberofanswers.gt(X,Y):–X>Ynot_in_loan(B,L):–notloan(B,L)ToavoidthispossibilityDatalogrulesmustsatisfythefollowingconditions.Everyvariablethatappearsintheheadoftherulealsoappearsinanon-arithmeticpositiveliteralinthebodyoftherule.Thisconditioncanbeweakenedinspecialcasesbasedonthesemanticsofarithmeticpredicates,forexampletopermittherulep(A):-q(B),A=B+1Everyvariableappearinginanegativeliteralinthebodyoftherulealsoappearsinsomepositiveliteralinthebodyoftherule. RelationalOperationsinDatalogProjectoutattributeaccount_namefromaccount.query(A):–account(A,N,B).Cartesianproductofrelationsr1andr2.query(X1,X2,...,Xn,Y1,Y1,Y2,...,Ym):–r1(X1,X2,...,Xn),r2(Y1,Y2,...,Ym).Unionofrelationsr1andr2.query(X1,X2,...,Xn):–r1(X1,X2,...,Xn),query(X1,X2,...,Xn):–r2(X1,X2,...,Xn),Setdifferenceofr1andr2.query(X1,X2,...,Xn):–r1(X1,X2,...,Xn),notr2(X1,X2,...,Xn), RecursioninDatalogSupposewearegivenarelationmanager(X,Y)containingpairsofnamesX,YsuchthatYisamanagerofX(orequivalently,XisadirectemployeeofY).Eachmanagermayhavedirectemployees,aswellasindirectemployees.Indirectemployeesofamanager,sayJones,areemployeesofpeoplewhoaredirectemployeesofJones,orrecursively,employeesofpeoplewhoareindirectemployeesofJones.Supposewewishtofindall(directandindirect)employeesofmanagerJones.WecanwritearecursiveDatalogprogram.empl_jones(X):-manager(X,Jones).empl_jones(X):-manager(X,Y),empl_jones(Y). SemanticsofRecursioninDatalogAssumption(fornow):programcontainsnonegativeliteralsTheviewrelationsofarecursiveprogramcontainingasetofrulesaredefinedtocontainexactlythesetoffactslcomputedbytheiterativeprocedureDatalog-FixpointprocedureDatalog-Fixpointl=setoffactsinthedatabaserepeatOld_l=ll=linfer(,l)untill=Old_lAttheendoftheprocedure,infer(,l)lInfer(,l)=lifweconsiderthedatabasetobeasetoffactsthatarepartoftheprogramliscalledafixedpointoftheprogram. ExampleofDatalog-FixPointIteration AMoreGeneralViewCreateaviewrelationemplthatcontainseverytuple(X,Y)suchthatXisdirectlyorindirectlymanagedbyY.empl(X,Y):–manager(X,Y).empl(X,Y):–manager(X,Z),empl(Z,Y)FindthedirectandindirectemployeesofJones.?empl(X,“Jones”).Candefinetheviewemplinanotherwaytoo:empl(X,Y):–manager(X,Y).empl(X,Y):–empl(X,Z),manager(Z,Y). ThePowerofRecursionRecursiveviewsmakeitpossibletowritequeries,suchastransitiveclosurequeries,thatcannotbewrittenwithoutrecursionoriteration.Intuition:Withoutrecursion,anon-recursivenon-iterativeprogramcanperformonlyafixednumberofjoinsofmanagerwithitself.Thiscangiveonlyafixednumberoflevelsofmanagers.Givenaprogramwecanconstructadatabasewithagreaternumberoflevelsofmanagersonwhichtheprogramwillnotwork. RecursioninSQLStartingwithSQL:1999,SQLpermitsrecursiveviewdefinitionE.g.,querytofindallemployee-managerpairswithrecursiveempl(emp,mgr)as(selectemp,mgrfrommanagerunionselectmanager.emp,empl.mgrfrommanager,emplwheremanager.mgr=empl.emp)select*fromempl MonotonicityAviewVissaidtobemonotonicifgivenanytwosetsoffactsI1andI2suchthatl1I2,thenEv(I1)Ev(I2),whereEvistheexpressionusedtodefineV.AsetofrulesRissaidtobemonotonicifl1I2impliesinfer(R,I1)infer(R,I2),Relationalalgebraviewsdefinedusingonlytheoperations:,|X|and(aswellasoperationslikenaturaljoindefinedintermsoftheseoperations)aremonotonic.Relationalalgebraviewsdefinedusingsetdifference(–)maynotbemonotonic.Similarly,Datalogprogramswithoutnegationaremonotonic,butDatalogprogramswithnegationmaynotbemonotonic. Non-MonotonicityProcedureDatalog-Fixpointissoundprovidedtherulesintheprogramaremonotonic.Otherwise,itmaymakesomeinferencesinaniterationthatcannotbemadeinalateriteration.E.g.,giventherulesa:-notb.b:-c.c.Thenacanbeinferredinitially,beforebisinferred,butnotlater.Wecanextendtheproceduretohandlenegationsolongastheprogramis“stratified”:intuitively,solongasnegationisnotmixedwithrecursion Non-Monotonicity(Cont.)ThereareusefulqueriesthatcannotbeexpressedbyastratifiedprogramExample:giveninformationaboutthenumberofeachsubpartineachpart,inapart-subparthierarchy,findthetotalnumberofsubpartsofeachpart.AprogramtocomputetheabovequerywouldhavetomixaggregationwithrecursionHowever,solongastheunderlyingdata(part-subpart)hasnocycles,itispossibletowriteaprogramthatmixesaggregationwithrecursion,yethasaclearmeaningTherearewaystoevaluatesomesuchclassesofnon-stratifiedprograms EndofAppendixC'