Taking IO seriously Resolution reconsidered for di

TakingI/OSeriously:ResolutionReconsideredforDiskJulianaFreire,TerranceSwiftandDavidS.WarrenDepartmentofComputerScienceStateUniversityofNewYorkatStonyBrookfjuliana,tswift,[e-mail]tiontechniquescangivePrologprograms,inthebestcases,aspeedcomparabletoC.However,Prologhasproventobeunacceptablefordata-orientedqueriesfortwomajorreasons:itspoorterminationandcomplexitypropertiesforDatalog,anditstuple-at-a-timestrategy.Anumberoftablingframeworksandsystemshaveaddressedtherstproblem,includingtheXSBsystemwhichhasachievedPrologspeedsfortabledprograms.YettablingsystemssuchasXSBcontinuetousethetuple-at-a-timeparadigm.Asaresult,thesesystemsarenotamenabletoatightinterconnectionwithdisk-residentdata.However,inatablingframeworkthedierencebetweentuple-at-a-timebehaviorandset-at-a-timecanbeviewedasoneofscheduling.Accordingly,wedeneabreadth-rstset-at-a-timetablingstrategyandproveititerationequivalenttoaformofsemi-naivemagicevaluation.Thatis,weextendthewell-knownasymptoticresultsofSeki[10]byprovingthateachiterationofthetablingstrategyproducesthesameinformationassemi-naivemagic.Further,thisset-at-a-timeschedulingisamenabletoimplementationinanenginethatusesPrologcompilation.Wedescribeboththeengineanditsperformance,whichiscomparablewiththetuple-at-a-timestrategyevenforin-memoryDatalogqueries.BecauseofitsperformanceanditsnelevelofintegrationofPrologwithadatabase-stylesearch,theset-at-a-timeengineappearsasanimportantkeytolinkinglogicprogramminganddeductivedatabases.1IntroductionItisoftennecessarytoleavetherelationalmodeltoreasonaboutthecontentsofadatabase,aproblemwhichdeductivedatabasesseektoremedy.Deductivedatabaseschooseastheirdatamodelrst-orderlogicorarestrictionsuchasDat-alog.First-orderlogichasprovenexpressiveasadataquerylanguage,andmanyevaluationstrategies,mostnotablymagicevaluation,havebeendevelopedtoem-bedrecursivegoal-orientationintheframeworkofdatabaseevaluation.Whilemagicaddsgoal-orientationtodatabaseevaluation,tablingmethodshaveaddedfeaturesofdatabaseevaluationtologicprogramminglanguages.Magicevaluationcloselyresemblestabling.Bothmagicandtablingcombinetop-downgoalorientationwithbottom-upredundancychecking.Indeed,forrange-restrictedprograms,theyhavebeenproventobeasymptoticallyequivalent[10,8]undercertainassumptions.Despitethesewell-knownequivalences,magic-stylesys-temshavetraditionallydieredfromtablingsystems.Magic-stylesystems,suchasAditi[15],CORAL[7],andLDL[3],arebuiltuponset-at-a-timesemi-naiveengines,whiletablingsystems,suchasXSB[9],useatuple-at-a-timestrategythatreectstheirgenesisinthelogicprogrammingcommunity.Eachclassofsystemshasitsadvantagesanddisadvantages.Presentlyforin-memoryDatalogqueries,thefastesttablingsystemsshowanorderofmagnitudespeedupovermagic-stylesystemsduetothetablingsystems’useofPrologcompilationtechnology[9].How-ever,thetuple-at-a-timestrategyoftablingsystemsisnotecientlyextendibletodisk.Acloselookattablingindicatesthatthereisnoreasonwhyaset-at-a-timestrategycannotbecloselyintegratedintoatablingengine.Doingsooerstremen-dousadvantages.In-memorypredicatescanbeevaluatedatthebestin-memoryspeeds,whilequeriestodiskhavethesameaccesspatternsasthebestset-at-a-timemethods.Furthermore,bothoftheseapproachescanbeintegratedfullyintothewell-knownPrologenvironment.ThispaperpresentsboththeoreticalandpracticalresultsonusingPrologcompilationtechnologytoecientlyimplementaset-at-a-timetablingsystemfordeniteprograms.Themajorresultsofthispaperare:DerivationofaTightEquivalencebetweenTablingandtheSemi-NaiveEvaluationofaMagic-TransformedProgram(SNMT).Broadequivalencesbetweentablingandmagic-stylemethodshavelongbeenknown.In[10]SekiobtainedanasymptoticequivalencebetweenanaiveevaluationofaprogramrewrittenusingAlexanderTemplatesandaversionofatablingmethod.Afterspecifyingabreadth-rstsearchstrategyfortabling,weextendtheequivalenceofSekiintwoways.First,weuseasemi-naiveevaluationratherthannaiveevaluationforboththetablingandtherewritemethod.Secondandmoreimportantly,wedeneanaturalmeasureofiterationequivalencebetweenset-at-a-timetablingandSNMT.Usingiterationequivalence,wedemonstratethateveryanswerofeveryiterationofourtablingstrategyisproducedatthecorrespondingiterationofSNMT.DesignandImplementationofanEnginetoEvaluateBreadth-FirstTabling.Othertablingmethodswithset-at-a-timepropertieshavebeendeveloped,mostnotablytheSLD-ALstrategyof[16].Inadditiontoiterationequivalencetomagic,theenginedescribedherehastheadvantageofusingthelow-leveldatastructuresandcompilationtechniquesofPrologtechnology.Aspresentedin[13],thistech-nology,asimplementedintheSLG-WAM,leadstoanextremelyfast,robust,andexibleimplementationofadeductivedatabaseengine.Theresultingimplementa-tionoftheBreadth-FirstXSBisavailableuponrequest.OtherversionsofXSBarecurrentlyinstalledatnearly1000registeredcommercial,academicandgovernmen-talsites.PerformanceAnalysisoftheSet-at-a-timeEngine.Surprisingly,theresultingset-at-a-timeengineisonlymarginallyslowerthanpreviouslypublishedSLG-WAMtimesforDatalogprogramswithin-memorydataonarepresentativeset