《数据库系统概念教学课件》a

AppendixC OtherRelationalLanguages AppendixC OtherRelationalLanguages Query by Example QBE AccessDatalog Query by Example QBE BasicStructureQueriesonOneRelationQueriesonSeveralRelationsTheConditionBoxTheResultRelationOrderingtheDisplayofTuplesAggregateOperationsModificationoftheDatabase QBE BasicStructure Agraphicalquerylanguagewhichisbased roughly onthedomainrelationalcalculusTwodimensionalsyntax systemcreatestemplatesofrelationsthatarerequestedbyusersQueriesareexpressed byexample QBESkeletonTablesfortheBankExample QBESkeletonTables Cont QueriesonOneRelation FindallloannumbersatthePerryridgebranch xisavariable optional canbeomittedinabovequery P meansprint display duplicatesareremovedbydefaultToretainduplicatesuseP ALL P x QueriesonOneRelation Cont Displayfulldetailsofallloans P x P y P z Method1 Method2 Shorthandnotation QueriesonOneRelation Cont FindnamesofallbranchesthatarenotlocatedinBrooklyn Findtheloannumberofallloanswithaloanamountofmorethan 700 QueriesonOneRelation Cont FindtheloannumbersofallloansmadejointlytoSmithandJones FindallcustomerswholiveinthesamecityasJones QueriesonSeveralRelations FindthenamesofallcustomerswhohavealoanfromthePerryridgebranch QueriesonSeveralRelations Cont Findthenamesofallcustomerswhohavebothanaccountandaloanatthebank NegationinQBE Findthenamesofallcustomerswhohaveanaccountatthebank butdonothavealoanfromthebank means theredoesnotexist NegationinQBE Cont Findallcustomerswhohaveatleasttwoaccounts means notequalto TheConditionBox Allowstheexpressionofconstraintsondomainvariablesthatareeitherinconvenientorimpossibletoexpresswithintheskeletontables ComplexconditionscanbeusedinconditionboxesExample FindtheloannumbersofallloansmadetoSmith toJones ortobothjointly ConditionBox Cont QBEsupportsaninterestingsyntaxforexpressingalternativevalues ConditionBox Cont Findallaccountnumberswithabalancegreaterthan 1 300andlessthan 1 500 Findallaccountnumberswithabalancegreaterthan 1 300andlessthan 2 000butnotexactly 1 500 ConditionBox Cont FindallbranchesthathaveassetsgreaterthanthoseofatleastonebranchlocatedinBrooklyn TheResultRelation Findthecustomer name account number andbalanceforallcustomerswhohaveanaccountatthePerryridgebranch Weneedto Joindepositorandaccount Projectcustomer name account numberandbalance Toaccomplishthiswe Createaskeletontable calledresult withattributescustomer name account number andbalance Writethequery TheResultRelation Cont Theresultingqueryis OrderingtheDisplayofTuples AO ascendingorder DO descendingorder Example listinascendingalphabeticalorderallcustomerswhohaveanaccountatthebank Whensortingonmultipleattributes thesortingorderisspecifiedbyincludingwitheachsortoperator AOorDO anintegersurroundedbyparentheses Example ListallaccountnumbersatthePerryridgebranchinascendingalphabeticorderwiththeirrespectiveaccountbalancesindescendingorder AggregateOperations TheaggregateoperatorsareAVG MAX MIN SUM andCNTTheaboveoperatorsmustbepostfixedwith ALL e g SUM ALL orAVG ALL x toensurethatduplicatesarenoteliminated Example FindthetotalbalanceofalltheaccountsmaintainedatthePerryridgebranch AggregateOperations Cont UNQisusedtospecifythatwewanttoeliminateduplicates Findthetotalnumberofcustomershavinganaccountatthebank QueryExamples Findtheaveragebalanceateachbranch The G in P G isanalogoustoSQL sgroupbyconstruct The ALL inthe P AVG ALL entryinthebalancecolumnensuresthatallbalancesareconsidered Tofindtheaverageaccountbalanceatonlythosebrancheswheretheaverageaccountbalanceismorethan 1 200 wesimplyaddtheconditionbox QueryExample FindallcustomerswhohaveanaccountatallbrancheslocatedinBrooklyn Approach foreachcustomer findthenumberofbranchesinBrooklynatwhichtheyhaveaccounts andcomparewithtotalnumberofbranchesinBrooklyn QBEdoesnotprovidesubqueryfunctionality sobothabovetaskshavetobecombinedinasinglequery Canbedoneforthisquery buttherearequeriesthatrequiresubqueriesandcannotalwaysbeexpressedinQBE InthequeryonthenextpageCNT UNQ ALL wspecifiesthenumberofdistinctbranchesinBrooklyn Note Thevariable wisnotconnectedtoothervariablesinthequery CNT UNQ ALL zspecifiesthenumberofdistinctbranchesinBrooklynatwhichcustomerxhasanaccount QueryExample Cont ModificationoftheDatabase Deletion DeletionoftuplesfromarelationisexpressedbyuseofaD command Inthecasewherewedeleteinformationinonlysomeofthecolumns nullvalues specifiedby areinserted DeletecustomerSmithDeletethebranch cityvalueofthebranchwhosenameis Perryridge DeletionQueryExamples Deleteallloanswithaloanamountgreaterthan 1300andlessthan 1500 Forconsistency wehavetodeleteinformationfromloanandborrowertables DeletionQueryExamples Cont DeleteallaccountsatbrancheslocatedinBrooklyn ModificationoftheDatabase Insertion InsertionisdonebyplacingtheI operatorinthequeryexpression InsertthefactthataccountA 9732atthePerryridgebranchhasabalanceof 700 ModificationoftheDatabase Insertion Cont ProvideasagiftforallloancustomersofthePerryridgebranch anew 200savingsaccountforeveryloanaccounttheyhave withtheloannumberservingastheaccountnumberforthenewsavingsaccount ModificationoftheDatabase Updates UsetheU operatortochangeavalueinatuplewithoutchangingallvaluesinthetuple QBEdoesnotallowuserstoupdatetheprimarykeyfields UpdatetheassetvalueofthePerryridgebranchto 10 000 000 Increaseallbalancesby5percent MicrosoftAccessQBE MicrosoftAccesssupportsavariantofQBEcalledGraphicalQueryByExample GQBE GQBEdiffersfromQBEinthefollowingwaysAttributesofrelationsarelistedvertically onebelowtheother insteadofhorizontally Insteadofusingvariables lines links betweenattributesareusedtospecifythattheirvaluesshouldbethesame Linksareaddedautomaticallyonthebasisofattributename andtheusercanthenaddordeletelinks Bydefault alinkspecifiesaninnerjoin butcanbemodifiedtospecifyouterjoins Conditions valuestobeprinted aswellasgroupbyattributesareallspecifiedtogetherinaboxcalledthedesigngrid AnExampleQueryinMicrosoftAccessQBE Examplequery Findthecustomer name account numberandbalanceforallaccountsatthePerryridgebranch AnAggregationQueryinAccessQBE Findthename streetandcityofallcustomerswhohavemorethanoneaccountatthebank AggregationinAccessQBE TherowlabeledTotalspecifies whichattributesaregroupbyattributes whichattributesaretobeaggregatedupon andtheaggregatefunction Forattributesthatareneithergroupbynoraggregated wecanstillspecifyconditionsbyselectingwhereintheTotalrowandlistingtheconditionsbelow AsinSQL ifgroupbyisused onlygroupbyattributesandaggregateresultscanbeoutput Datalog BasicStructureSyntaxofDatalogRulesSemanticsofNonrecursiveDatalogSafetyRelationalOperationsinDatalogRecursioninDatalogThePowerofRecursion BasicStructure Prolog 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 ExampleQueries Eachruledefinesasetoftuplesthataviewrelationmustcontain 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 10000 NegationinDatalog Defineaviewrelationcthatcontainsthenamesofallcustomerswhohaveadepositbutnoloanatthebank 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 NamedAttributeNotation Datalogrulesuseapositionalnotationthatisconvenientforrelationswithasmallnumberofattributes ItiseasytoextendDatalogtosupportnamedattributes E g v1canbedefinedusingnamedattributesasv1 account numberA balanceB account account numberA branch name Perryridge balanceB B 700 FormalSyntaxandSemanticsofDatalog Weformallydefinethesyntaxandsemantics meaning ofDatalogprograms inthefollowingsteps Wedefinethesyntaxofpredicates andthenthesyntaxofrules Wedefinethesemanticsofindividualrules Wedefinethesemanticsofnon recursiveprograms basedonalayeringofrules Itispossibletowriterulesthatcangenerateaninfinitenumberoftuplesintheviewrelation Topreventthis wedefinewhatrulesare safe Non recursiveprogramscontainingonlysaferulescanonlygenerateafinitenumberofanswers Itispossibletowriterecursiveprogramswhosemeaningisunclear Wedefinewhatrecursiveprogramsareacceptable anddefinetheirmeaning SyntaxofDatalogRules Apositiveliteralhastheformp 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 SemanticsofaRule Agroundinstantiationofarule 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 LayeringofRules DefinetheinterestoneachaccountinPerryridgeinterest 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 Layeringoftheviewrelations LayeringRules Cont Arelationisalayer1ifallrelationsusedinthebodiesofrulesdefiningitarestoredinthedatabase Arelationisalayer2ifallrelationsusedinthebodiesofrulesdefiningitareeitherstoredinthedatabase orareinlayer1 Arelationpisinlayeri 1ifitisnotinlayers1 2 iallrelationsusedinthebodiesofrulesdefiningapareeitherstoredinthedatabase orareinlayers1 2 i Formally SemanticsofaProgram DefineI0 setoffactsstoredinthedatabase Recursivelydefineli 1 li infer i 1 li Thesetoffactsintheviewrelationsdefinedbytheprogram alsocalledthesemanticsoftheprogram isgivenbythesetoffactslncorrespondingtothehighestlayern Letthelayersinagivenprogrambe1 2 n Let idenotethesetofallrulesdefiningviewrelationsinlayeri Note Caninsteaddefinesemanticsusingviewexpansionlikeinrelationalalgebra butabovedefinitionisbetterforhandlingextensionssuchasrecursion Safety Itispossibletowriterulesthatgenerateaninfinitenumberofanswers gt X Y X Ynot in loan B L notloan B L ToavoidthispossibilityDatalogrulesmustsatisfythefollowingconditions Everyvariablethatappearsintheheadoftherulealsoappearsinanon arithmeticpositiveliteralinthebodyoftherule Thisconditioncanbeweakenedinspecialcasesbasedonthesemanticsofarithmeticpredicates forexampletopermittherulep A q B A B 1Everyvariableappearinginanegativeliteralinthebodyoftherulealsoappearsinsomepositiveliteralinthebodyoftherule RelationalOperationsinDatalog Projectoutattributeaccount 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 RecursioninDatalog Supposewearegivenarelationmanager 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 SemanticsofRecursioninDatalog Assumption fornow programcontainsnonegativeliteralsTheviewrelationsofarecursiveprogramcontainingasetofrules aredefinedtocontainexactlythesetoffactslcomputedbytheiterativeprocedureDatalog FixpointprocedureDatalog Fixpointl setoffactsinthedatabaserepeatOld l ll l infer l untill Old lAttheendoftheprocedure infer l lInfer l lifweconsiderthedatabasetobeasetoffactsthatarepartoftheprogramliscalledafixedpointoftheprogram ExampleofDatalog FixPointIteration AMoreGeneralView Createaviewrelationemplthatcontainseverytuple 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 ThePowerofRecursion Recursiveviewsmakeitpossibletowritequeries suchastransitiveclosurequeries thatcannotbewrittenwithoutrecursionoriteration Intuition Withoutrecursion anon recursivenon iterativeprogramcanperformonlyafixednumberofjoinsofmanagerwithitself Thiscangiveonlyafixednumberoflevelsofmanagers Givenaprogramwecanconstructadatabasewithagreaternumberoflevelsofmanagersonwhichtheprogramwillnotwork RecursioninSQL StartingwithSQL 1999 SQLpermitsrecursiveviewdefinitionE g querytofindallem