Graph--Based Processing of Logic Programs

Graph{BasedProcessingofLogicProgramsDietmarSeipelUniversityofTubingenSand13,D{72076Tubingen,[e-mail]lrecursivelogicqueriestoadeductivedatabaseareexpressedbylinearrecursiveDatalogprogramswithexactlyonerecursiverule,so-calledlinearsirups.Wegiveacharacterizationofk-sidedlinearDatalogsirups{theconceptwasintroducedbyNaughtonin[22]{basedonagraphmodelandpresentanormalformtowhicheverylinearDatalogsirupcanbetransformed.NormalizedlinearDatalogsirupscanbedecomposedbyacountingtechniqueintoklower-dimensionallinearsirupswhichcanbeevaluatedinparallelbyveryecientqueryevaluationalgorithms.Forcertainsetsoflinearsirupsdeningthesameintensionalpredicatewecanalsoderiveadecompositionapproachfromthegraphmodel.Anothertechniquebasedontheprexesofcompiledexpansionstransformsasetofchainruleswithbinarypredicatesymbols,aso-calledCFGprogram,intoatransitiongraph.CommonsubexpressionsbetweendierentcompiledformulascanbedetectedbythegraphminimizationalgorithmofHumanandMoore,cf.[16].Theminimizedgraphisusedtoguidetheordered,complete,butnon-redundantevaluationoftheprogram.Theresultinginterformulaoptimizationisageneralizationofthewell-knownwavefronttechniques,whichuseintermediateresultsfromoneiterationinfollowingiterations.Keywords:deductivedatabases,queryoptimization,linearrecursion,chainrules,wavefronttechniques,countingtechniques1IntroductionDeductivedatabasesusepredicatecalculusasapowerful,declarativequerylanguagetoretrievedatafromrelationaldatabases.Aqueryisformulatedasalogicprogram{morepreciselyasetofdenitehornclauses{andaquerygoalgivenbyasingleatom.Thepossiblyrecursiveprogramisevaluatediterativelyinaset{orientedfashionbasedontheprimitiveoperationsofrelationalalgebra{selection,projection,join{whichcanbeexecutedecientlyondatabases.Wavefronttechniques,cf.HanandLu[13],considerthecompletebinding{passingbehaviourofalogicprogram.TheydealwiththeexpansionofaprogramLPw.r.t.aquerygoalG,whichisgivenbyan(innite)sequenceofconjunctionsofatoms{eachconjunctioncalledastring{derivedviarepeatedSLD{resolutionbeginningwithgoalG.Thestringsarepartitionedinto1specialsubsetsof(transitively)connectedatomswhichareevaluatedseparately.SubsequentlytherelationsfortheintensionalpredicatesinLParecomposed.Wederiveoptimizationconceptsforprogramswithonerecursiverulebyinvestigatingtheques-tionhowtopartitionthestringsintoso{calledwavessuchthat(i)theresultofawaveinonestringisusefulforderivingtheresultsofrelatedwavesinotherstrings(multiplequeryoptimization),(ii)theintermediatewave{resultsformasuitabledecompositionofthenalresult.Foralinearrecursiverulewedeneagraph{representation,theaugmentedsubstitutiongraph,whichreectsthevariablesharingwithintherule.Thereisonenodeforeachargumentpositionoftheintensionalatomsandonenodeforeachextensionalatom.Theedgesconnectthosenodesthatsharevariables.Weshowhowthisgraphdescribesthegrowthofthewavesandhowtherulecanbedecomposedintoanitenumberofcertainlesscomplexlinearrecursiverules.Thisgeneralizesthecountingtechnique,cf.[2],fromlinearDatalogsirupsinlinearvariablepatterntoarbitrarylinearDatalogsirups.Note,thatthegeneralcountingtechniquesof[26],[27]donotidentifythewaves{theiremphasisisonthepropagationofquerybindings.Forasetoflinearrecursiverulesdeningthesameintensionalpredicateandhavingonlyunaryandbinaryextensionalpredicatesymbolswecanalsoderiveadecompositionapproachfromthesetoftheiraugmentedsubstitutiongraphs.ThereareseveralapproachesforprocessingrecursiveCFGprograms,e.g.themulti{formulamergedprocessingofHanandHenschen[12].Thisstack{directedprocessingalgorithmforbilinearCFGsirupsgeneratesmanysimilarstrings,whoseprocessingcanbeoptimizedbysharingandmergingoftheformulas.CFGprogramsarerelatedtocontext{freelanguages.Someexpressivenessresultsforthemaregivenin[8].TheapproachforgeneralCFGprogramspresentedhereisbasedonideasfromautomatatheoryandformallanguages.Thestringsareprocessedbyanalgorithmoperatingontheircorrespond-ingtransitiongraph,whichhasanodeforeachstring{prexandanedgefromeachnodetoitsdirectsuxes.Thus,severaltypesofredundancyintheprocessingofthestringscanbeavoided.ThereisasimilarrewritingtechniqueofHoutsmaandApers,cf.[17],whichisalsograph{based,butisonlyapplicableforregularmutuallyrecursivelogicprograms.1.1BasicDenitionsandNotationsSyntactically,adeductivedatabaseDDB=(DB;LP)isgivenbyasetDBoffacts,whichresemblearelationaldatabase,andalogicprogramLP,whichconsistsofasetofrulesforderivingnewfactsfromDB,cf.[21].Afactisanatomp(t1;:::;tn),wheretiisatermovervariables,constantsandfunctionsymbols.Agoalisgivenbyasequenceofatoms.Arulerisgivenbyr:p0(X0):p1(X1);:::;pn(Xn):wheretheatomp0(X0)iscalleditsheadandthegoalp1(X1);:::;pn(Xn)wheren2IN0iscalleditsbody.risaDatalogrule,iitcontainsnofunctionsymbolsinthetermsofitsatoms.2ThesemanticsofadeductivedatabaseDDB=(DB;LP)isdenedaccordingtothebottom-upornaiveevaluationalgorithms,cf.[3].Notionsofequivalenceforlogicprogramsareintroducedin[25].(i)Apredicatesymbolpisintensional,iitoccursintheheadofaruler2LP;otherwiseitisextensional.AlogicdatabaseDBisexte