VLDBJournal2(1):75-111

(1993)FredJ.
Maryanski,EditorVLDB75UsingDifferentialTechniquestoEfficientlySupportTransactionTimeChristianS.
Jensen,LeoMark,NickRoussopoulos,andTimosSellisReceivedMay30,1990;revisedversionreceivedFebruary28,1992;acceptedJune25,1992.
Abstract.
Wepresentanarchitectureforqueryprocessingintherelationalmodelextendedwithtransactiontime.
Thearchitectureintegratesstandardqueryop-timizationandcomputationtechniqueswithnewdifferentialcomputationtech-niques.
Differentialcomputationcomputesaqueryincrementallyordecremen-tallyfromthecachedandindexedresultsofpreviouscomputations.
Theuseofdif-ferentialcomputationtechniquesisessentialinordertoprovideefficientprocess-ingofqueriesthataccessverylargetemporalrelations.
Alternativequeryplansareintegratedintoastatetransitionnetwork,wherethestatespaceincludesbacklogsofbaserelations,cachedresultsfrompreviouscomputations,acacheindex,andintermediateresults;thetransitionsincludestandardrelationalalgebraoperators,operatorsforconstructingdifferentialfiles,operatorsfordifferentialcomputation,andcombinedoperators.
Arulesetispresentedtopruneawaypartsofstatetran-sitionnetworksthatarenotpromising,anddynamicprogrammingtechniquesareusedtoidentifytheoptimalplansfromtheremainingstatetransitionnetworks.
Anextendedlogicalaccesspathservesasa"structuring"indexonthecachedre-suitsandcontains,inaddition,vitalstatisticsforthequeryoptimizationprocess(includingstatisticsaboutbaserelations,backlogs,andqueries--previouslycom-putedandcached,previouslycomputed,orjustpreviouslyestimated).
KeyWords.
Temporaldatabases,transactiontime,efficientqueryprocessing,in-crementalanddecrementalcomputation.
1.
IntroductionTherelationalmodelpresentedbyE.
ECoddtwentyyearsago(Codd,1970,1979)hasgainedimmensepopularityandisregardedtodayasadefactostandardforbusinessapplications.
Amainreasonforthesuccessisthegeneralityofthemodel;itmakesChristianJensen,Ph.
D.
,isAssistantProfessor,DepartmentofMathematicsandComputerScience,Aal-borgUniversity,Fr.
BajersVej7,DK-9220,Ost,Denmark.
LeoMark,Ph.
D.
,isAssociateProfessor,Col-legeofComputing,GeorgiaTech,Atlanta,GA30332,LISA.
NickRoussopoulos,Ph.
D.
,isFullProfessor;andTimosSellis,Ph.
D.
,isAssociateProfessor,DepartmentofComputerScience,UniversityofMaryland,CollegePark,MD20742,USA.
76veryfewassumptionsaboutspecificapplicationareas.
This,however,hasimdraw-backsbecausethemodeldoesnotprovidedetailedandcustomizedsupportforsomeapplicationareas.
Extensionsthatmaketherelationalmodelmoresuitablefortheapplicationareashavebeenatopicofinterestinthedatabaseresearchcommunityeversincetherelationalmodelwaspresented.
Thisarticlepresentsanimplementationmodel,IMfI'(ImplementationModel/Time),foranextensionoftherelationalmodelsupportingtransactiontime,DM/T(DataModel/Time)(Jensenetal.
,1991,1992).
Dataareneverdeletedonceenteredintoadatabaseinthismodel;itispossibletoseethedatabasefromanytimeinthepast,anditispossibletoanalyzethechangehistory.
Manyapplicationswillbenefitfromefficienttransactiontimesupport.
Intheliterature,engineering,econometrics,banking,inventorycontrol,medicalrecords,andairlinereservationshavebeenmen-tionedascandidates(McKenzieandSnodgrass,1991).
Traditionalimplementationmodelscannotcopeefficientlywithhuge,evergrow-ingquantitiesofhistoricaldata.
Thepredominantapproachtakentosolvethisproblemhasbeenpartitionedstorage,wheredataofindividualrelationsareparti-tioned,andastoragehierarchyismaintainedthatfavorsefficientsupportofqueriessolelyaccessingrecentdata(Lumetal.
,1984;SalzbergandLomet,1989).
Whilestillallowingforpartitionedstorage,thedataorganizationofIM/Tallowsefficientaccesstofrequentlyaccessedstatesofindividualrelations,recentorold,thusprovidingefficientsupportofanystate.
IM/Texploitscachingofqueryresults.
Cachingistheideaofstoringresults,onsecondarymemory,ofpreviouscomputationsandsubsequentlyusingthemtoavoidredoingexpensivecomputations(Roussopoulos,1982b,Sellis,1988a).
Cachingtradesreplicationofdataforspeedofretrieval.
Itispotentiallyaverypowerfultechnique,butanumberofissuesmustbedealtwithintelligentlyinordertogainthefullbenefits.
Letusmentionthemostimportantones,someofwhichareaddressedinthisarticlewhileothersarestillissuesforfutureresearch.
First,thereisthequestionofhowtocacheresults.
InIM/'I~queryresultscanbestoredasactualdataoraspointerstobasedata,possiblyviaseverallevelsofindirection.
Pointercachestoragegivesafixed,smalltuplesizeandmakesresultsverycompactthusallowingforefficientuseofmainmemory(Roussopoulos,1991).
Fortransaction-timedatabases,however,onebasedatapagemustbereadforeachpointerinextremecases.
Datacachestoragesolvesthispotentialproblembecauseitallowsforcontroloflocalityofreference.
Additionally,itallowsforreductionofreferencestoslowerstorageareas.
Whilethearchitectureallowsforbothdataandpointercaching,adetailedstudyoftherelativemeritsofthetwoisstillwarranted.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction"time77Figure1.
ThreeIM/Tstores:basedata,deriveddata,ELAPIlllllllll"llllllll]lllllllllllllllIIIIIIII!
111111111[i][311][i][i][1][i][31313E]DE]DTSTT°o°°°.
.
'°~.
°S'°°/"TT.
'#°i/i/.
i%.
o.
.
.
.
.
.
;OOOO1M,rI"hasthreestores,oneforbasedata,oneforderiveddata,andonefortheELAP,containingstatisticsandrepresentingthestructureofbaseandderiveddata.
Duringqueryoptimization,plansusingthestoreddataareenumeratedinSTNs.
Second,theutilityofcachingcanbeimprovedbymeansofcacheindexing.
IM/Textendsthelogicalaccesspath(Roussopoulos,1982b)intoanExtendedLogicalAccessPath(ELAP),whichallowsforefficientidentificationofallpotentiallyusefulresultsduringqueryprocessing.
Itisapersistentquerygraphwithnodesforallcached,computed,orjustestimatedresults.
WhilethealgorithmsformaintainingandusingtheELAPhavenotbeendeveloped,ithasbeendemonstratedthatanappropriateextensionofthealgorithmsforthelogicalaccesspathisfairlystraightforward,i.
e.
,therule-accesspath(Sellisetal.
,1990).
Third,togainthefullbenefits,cachingshouldbeusedinconjunctionwithdifferentialcomputationtechniques(Roussopoulos,1991).
Theapplicationofsuchtechniquesprolongstheusefulnessofcachedresultsbecauseslightlyoutdatedresultsneednotbediscardedandrecomputed,butcaninsteadbeefficientlyincrementedordecrementedtoansweraquery.
IM/Tgeneralizesincrementalcomputationtodifferentialcomputationusingbothincrementalanddecrementaltechniques,anditunifiesdifferentialcomputationandtraditionalrecomputation.
Differentialcomputationisthefocusofthisarticle,anditistreatedingreatdetail.
Fourth,onlypotentiallybeneficialresultsshouldbecached.
Ifthecacheisfull,appropriatereplacementstrategiesmustbeused.
IM/Thasacachemanagementcomponentthatsupportsselectivecachingandcachereplacement.
Thepurposeforselectivecachingisthatneithercachingofallresults(anddifferentialcomputation)or78nocachingatall(andrecomputation)issuperiortotheotherineverygivensituation.
Cachingisattractiveinenvironmentscharacterizedbymanyqueries,fewupdates,verylargeunderlyingbaserelations,andcomparablysmallresults.
Methodsofadaptingthenumerouscontributionsoncachemanagementintoappropriatestrategiesforselectivecachingandcachereplacementinthiscontextarediscussedelsewhere(Hanson,1987;Sellis,1987,1988a,"Jhingran,1988;JhingranandStonebraker,1989).
Fifth,thefactthatcachedresultsbecomeoutdatedmustbeaddressed.
Anypossibleupdatestrategyrangingfrom"eager"(i.
e.
,whenrelevantbasedataareentered),overthreshold-triggered,to"lazy"(i.
e.
,whentheresultisrequested)ispossible(RonssopoulosandKang,1986;Hanson,1987).
Thedetailsofcacheupdatingarenotpartofthisarticle.
Inatemporalsettingthemaintenanceofstoredresultsislikelytobemorefeasiblethaninasnapshotsetting.
Thereasonsarethatrelationsarelargebecausepreviousstatesareretainedandessentialadditionalsemanticsfortheprocessofselectivecachingisavailable.
Forexample,fixedviewsareprimarycandidatesforcachingbecausetheyneverbecomeoutdated,andthefutureoutdatednessoftime-dependentviewsissuedagainstpaststatescanbeestimatedatthetimeofcomputation.
Query-plangenerationinIM/Tusestheconceptofstatetransitionnetwork(STN;LafortuneandWong,1986).
Query-planselectionusesdynamicprogramming(seeFigure1).
WepresentasetofrulesforpruningtheSTNsgenerated,theideabeingtoavoidgeneratinginferiorpaths,thussavingbothspaceandtimeduringcostestimation.
Duringquery-plangenerationandselectionweuseresultsfromthecache,andweusebothrecomputationanddifferentialcomputationversionsoftheoperatorsofthequerylanguageofDM/TaspossibletransitionsinSTNs.
Apartfromdefiningtheoperators,wediscusshowtoefficientlyimplementthedifferentialversions.
Inaddition,combinedoperatorsareintroducedtominimizetheneedforstorageofintermediateresultsduringquerycomputation.
Efficientqueryprocessingisacentralthemeindatabaseresearch,andconse-quentlytheworkofthisarticleisrelatedtoanumberofpreviousefforts.
Thetransaction-timeextensionofthisarticlewasdesignedtobetransparenttothenaiveuserofthestandardrelationalmodel.
Toourknowledge,noneoftheothertemporalextensionsoftherelationalmodelsharesthischaracteristic(Bubenko,1977;Bolouretal.
,1982;SnodgrassandAlan,1985;Snodgrass,1987;StamandSnodgrass,1988;McKenzieandSnodgrass,1991).
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransactionTime79IM/Tallowsforpartitionedstorageandsupportsbothreverseandforwardchaining.
Relatedeffortscanbefound(Dadametal.
,1984;Lumetal.
,1984;Ahn,1986;SnodgrassandAhn,1988;KolovsonandStonebraker,1989;SalzbergandLomet,1989).
Gridfileshavebeensuggestedasameansofimplementationoftemporaldata(ShoshaniandKawagoe,1986),buttheyseeminappropriatebecausesurrogates,forwhichnonaturalorderingexists,wouldbeonedimensionandtimetheother.
Inaddition,indexingofotherattributesisnotallowed,whichagainisunsatisfactory.
ThesubjectofRotemandSegev(1987)ismulti-dimensionalfilepartitionforstaticfileswithtimeasoneofmultipledimensions.
Someresearch(GunadhiandSegev,1989;Gunadhietal.
,1989;SegevandGunadhi,1989)concentratesondifferentkindsoftemporaljoins(time-union,time-intersection,andevent-joins)andtemporal-selectivityestimation.
Thisresearch,whileinteresting,isnotaddressedhere.
ThefocusoftheworkpresentedbyMcKenzie(1988)isthedatamodelforatemporaldatabase,anditiscloselyrelatedtoourwork.
Itformallydefinesincrementalalgebraoperators,resemblingthoseofourstate-transitionspace.
Inaddition,itsurveysapplicationsofincrementaltechniquesintherelationalmodel,anddiscusseswaystocombinepreviouseffortsintoanimplementationsupportingbothtransactiontimeandvalid(logical)time.
Ourworkconcentratesonlyonimplementationandontransactiontime.
Wepresentadetaileddesignofanimplementationmodelandconcentrateonqueryoptimizationandprocessing.
IM/Texploitscachingofviewsandtheliteraturecontainsmanycontributionstotheunderstandingofitsmanyaspects.
Aspectsofmaterializedviewsrelevanttodis-tributedprocessingarepresentedinSegevandFang(1989,1990).
Theperformanceofthreetechniques(lazyincrementalcomputation,eagerincrementalcomputation,andrecomputation)hasbeencomparedbyHanson(1987),whodemonstratedthatnoneofthetechniquesweresuperiortotheothersinallcases.
Cachingofqueryresultshasbeenaddressedtosupportquerylanguageprocedures(programs,rules)efficientlystoredinrelationalfieldsQhingran,1988;Sellis,1987,1988a).
TechniquesaimedatreducingthecostofmaintainingmaterializedviewshavebeenrecentlyreportedbyBlakelyetal.
(1986,1989)whoattempttodetectbasedataupdatesthatdonotaffectaview,andtodetectwhenaviewcanbecorrectlyupdatedusingonlythedataalreadypresent.
IM/Tgeneralizesandunifiestraditionalrecomputationandincrementalcomputationsothatasinglequerycanbeprocessedusingre-computation,incrementalcomputation,anddecrementalcomputation.
'Itaditionalsystems,e.
g.
,Ingres(WongandYouseffi,1976)andSystemR(Selingeretal.
,1979)userecomputation.
KinsleyandDriscoll(1979,1984)havedescribedhowtoextendtheRAQUELIIdatabasemanagementsystemtosupportdynamicderived80relationsusingeagerincrementalupdate.
InADMS(±),adatabasemanagementsystemimplementingthestandardrelationalmodel,incrementalcomputationofviewsstoredaspointerstructuresisused(Roussopoulos,1982a,1987,1991).
OurworkhassomeresemblancetoPostgres,whereprevioushistoryisalsoretained.
Thetemporalsupport,however,neverwasthefocus,andtimestampsandbacklogqueriesarenotsupportedasinIM/EPostgresexploitscaching,butsinceindexing,differentialcachemaintenance,andqueryexecutionaremissing,thefullpotentialofcachingisnotachieved(RoweandStonebraker,1987).
Forpreviousworkonqueryoptimization,andfurtherreferences,seeSmithandChang(1975),Selingeretal.
(1979),JarkeandKoch(1984),andSellisandShapiro(1985).
Statetransitionnetworkshave,toourknowledge,neverbeenappliedinatemporalsettingorinsettingsinvolvingcaching.
LafortuneandWong(1986)usedSTNsasaframeworkforqueryoptimizationinadistributedenvironment.
HongandWong(1989)appliedSTNstomultiplequeryoptimization.
Thestructureoftheremainingpartofthisarticleisasfollows:Section2servesasaspecificationofthefunctionalitytobesupportedbyIM/'ETheconceptoftransactiontime,datastructures,andthequerylanguageofDM/Tarepresented.
TheremainingsectionsaredevotedtoIM/TandtheefficientprocessingofDM/Tqueries.
Section3describesthethreestoresofIM/T--basedata,cache,andELAP.
InSection4,STNsareusedforenumeratingalternativequeryplansanddynamicprogrammingisusedtocollectcostsofentireplansfromcostsofsingletransitions.
Theconcretestateandtransitionspaces,incorporatingtheuseofcachedresults,differentialcomputation,standardquerycomputationtechniques,andsupportforcombinedoperators,areintroduced.
AlsodiscussedistheuseofELAPtofindpromisingresultsfromthecache,consideredwhenSTNsaregenerated.
InSection5wefirstpresentthecasestoconsiderwhenimplementingoperatorsandthendiscussthethreetypesofoperators:Recomputationoperators,operatorsthatconstructdifferentialfiles,anddifferentialoperators.
Section6presentsrulesforreducingthesizesofthegeneratedSTNs.
Section7concludesthisarticle.
2.
TransactionTimeintheRelationalModel,DM/TInthissectionwebrieflyintroducethetransactiontimeextensionofthebasicrelationalmodel(Codd,1970,1979;Jensenetal.
,1991).
OurpurposeistoidentifythekindsofqueriesthatshouldbesupportedbyIM/TThepropertiesofthetimeconceptofferedbyDM/TareoutlinedinFigure2andarediscussedbelow.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'Iime81Figure2.
CharacterizationofthetimeconceptofferedbyDM/T.
/trisection//reu){iscre/{logicalx[~]x[stepwisecont.
[*srbitrary*manualTwoorthogonaltimedimensionshavebeenstudiedintemporaldatabases(SnodgrassandAlan,1985).
Logicaltimemodelstimeinthepartofrealitymodeledbyadatabase.
Transactiontimemodelstimeinthepartoftherealitythatsurroundsthedatabase,theinputsubsystem.
Whilelogicaltimeisapplication-dependent,transactiontimedependsonlyonthedatabasemanagementsystem,andisinherentlyapplication-independent.
First,DM/Tsupportstransactiontimeasopposedtologicaltime.
Second,adomainisregularifthedistancesbetweenconsecutivevaluesoftheactivedomainareidentical.
Otherwisethedomainisirregular.
DM/Tsupportsanirregulartimedomain.
Third,atimedomaincanbediscreteorstepwisecontinuous.
Tapleswithdiscretetimestampsareonlyvalidattheexacttimesoftheirtimestamps.
Incontrast,tupleshaveanintervalofvalidityinastepwisecontinuousdomain.
TheDM/Ttimedomainhasthisproperty(alsotermedstability)becausethevaluesofarelationremainthesameuntiltherelationischangedbyanewtransaction.
Fourth,DM/Tsupportstruetimeasopposedtoarbitrarytime.
Truetimereflectstheactualtimeoftheinputsubsystemwhileanarbitrarytimedomainonlyneedstohaveametricandatotalorderdefinedonit;thesetofnaturalnumbersisapossiblearbitrarytimedomain.
Fifth,DM/Thasautomatictime-stamping,whichisthenaturalchoicefortransactiontime.
Manual,user-suppliedtimestampvaluesarenaturalforlogicaltime.
Wehavechosentuplestampingasopposedtoattributevaluestamping.
Themajorreasonhasbeentoprovideafirstnormal-formmodelwhichisasimpleandyetpowerfulextensionofthestandardrelationalmodel.
Inordertorecorddetailedtemporaldataandstillbeabletousetheoperatorsofthebasicrelationalmodel,wehaveintroducedtheconceptofabacklogrelation.
Abacklog,BR,forarelation,R,isarelationthatcontainsthecompletehistoryofchangerequeststorelationR(RoussopoulosandKang,1986).
BacklogBRcontainsthreeattributesinadditiontothoseofR.
AttributeIdisdefinedoveradomainoflogical,systemgenerateduniqueidentifiers,i.
e.
,surrogates.
Thevaluesof/drepresenttheindividualtuples,termedchangerequests.
TheattributeOpisdefinedovertheenumerateddomainofoperationtypes,andvaluesofOpindicate82Figure3.
System-controlledinsertionsintoabacklog.
RequestedoperationonR:insertR(tuple)EffectonB~:illiinsertBR(id,Ins,time,tuple)deleteR(key)insertBR(id,Del,time,tuple(key))modifyP~(key,newvalue)insertBR(id,Mod,time,tuple(key,newvalue))Thefunction"tuple"returnsthetupleidentifiedbyitsargument.
whetheraninsertion(Ins),adeletion(Del)oramodification(Mod)isrequested.
1Finally,theattributeTimeisdefinedoverthedomainoftransactiontimestamps,TTIME,aspreviouslydiscussed.
DM/Tautomaticallygeneratesandmaintainsabacklogforeachbaserelation(i.
e.
,user-definedrelationsandschemarelations).
Figure3showstheeffectonbacklogsresultingfromoperationrequestsontheircorrespondingrelations.
Asaconsequenceoftheintroductionoftimestamps,abaserelationisnowafunctionoftime.
Toretrieveabaserelationitmustfirstbetimesliced.
Todefinetimeslice,assumethatRhastheattributesA1,A2,.
.
.
,A,~andlettE[tlnit;NOW]wheretlnitisthetimewhenthedatabaseisinitializedandNOWisaspecialvariablewiththecurrenttimeasitsvalue.
Now,Rattimetisdefinedasfollows:R(t){xl3s(BR(s)Ax[1]=s[1]Ax[2]=a[2]A.
.
.
Ax[n]=a[n]As[Time]30((Emp(tl))~Emp(tl).
Id=Emp(t2).
Id(Emp(t2)))Q27['Emp(tl).
Id,E~rt~p('2).
So.
l(O'Sal~30(Emp(tl))MEmp(tl).
ld=Emp(tz).
Id(Emp(t2)))Q3rEmv(t~).
Ia,Emp(,:).
S,t(rId(aS,l>_30(emp(ta)))t~Emp(,1).
/d=E,~p(t~).
td(TrZd,SaZ(emp(t2))))Eachqueryreturnstheld'sandSal'sattimet2ofemployeesthatwereemployedatbothtimetlandt2andthatearnedmorethan$30,000.
attl.
Yet,theyaredifferentexpressionswithdifferentprocessingcharacteristics.
TheELAPfortheseexpressionsisshowninFigure4.
Itfollowsthatacachedresultofanodecouldhavebeencomputedinseveralways,andthatitsubsequentlycanbecomputedinseveralways.
Anodetellsfromwhichexpressionacachedresultwasmostrecentlycomputed.
Thereisatmostonecacheentrypernode.
86Figure4.
Threeequivalentqueryexpressions.
iiiiiiiirllllllllllllE]IIEEI1.
111111111111111102t~~DI[EIIIIIIIIIIIIII]E2[Theviewcorrespondingtoanodecanbecomputedfromseveralquerylanguageexpressions.
Thefigurerepresentsthreeequivalentqueryexpressions,firstseparateandthencombined.
Nodescanbelongtooneofseveralcategories,dependingonthecomputationalstatusofthelabelingqueryexpressions.
Theresultofaqueryexpressioncanbecachedasdataorpointers;theresultofthequeryexpressionscanhavebeencachedpreviouslyasdataorpointers;itispossiblethatnoresultofthequeryexpressionshaseverbeencached,butresultsmighthavebeencomputedorjustestimated;VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransactionTime87finally,anodecandenoteabacklog.
Differenttypesofstatisticscanbekeptineachofthesixtypesofnodes.
Individualstatisticsshouldonlybemaintainedifthecostofdoingsoislessthanthebenefitsachievedfromhavingthemavailableduringqueryoptimization.
Practicalexperimentsareneededtodeterminewhenthisisthecase.
Possiblestatisticsinclude:cardinalityofstoredresult;resultstoredaspointerordata;tuplesize;whichexpressioniscached;up-to-datestatus;howoftenused;usage;computationcost;whendeleted;whydeleted;andavailableindices.
4.
QueryPlanGenerationandSelectionToefficientlycomputeaquery,thesystemgeneratesastatetransitionnetwork(STN)wheretheinitialstatecontainstheuncomputedquery,thebacklogrelations(inwhichtermsitisdefined)thecache,andtheELAEAstatetransitionoccurswhenthecostofapartialcomputationtowardthetotalcomputationofthequeryisestimated.
Thenewstateisidenticaltothepredecessorstateexceptitisassumedthatthecost-estimatedcomputationhasbeenperformed.
Afinalstateisreachedwhenthecostsofallcomputationshavebeenestimated.
Byfollowingallpathsfromtheinitialtoafinalstateandaccumulatingcostsforeachpath,thetotalcostsofcomputingthequeryindifferentwaysareobtained,andwecanchoosethequeryplanwiththelowestcost.
Thepurposeofthissectionistoformalizeandelaborateonthegenerationofqueryplansasjustdescribed.
4.
1StateTransitionNetworkAnSTNforaquery,~isalabeledDAG,andcanbedefinedasSTN(Q)=(S,79,P,F,Zo,Xs)whereSisasetofstates(nodes);eachnodecontainswhatremainstobecalculatedofqueryQalongwiththedatastructuresthatcanbeusedtocomputethequery~(i.
e.
,intermediateresults,theELAP,thecache,backlogs).
79isasetofoperatorswhichdescribethequeryprocessingandlabeltheedgesoftheDAG.
Pisamapping:,S--~2p,whichmapsthestatespaceintothepowersetspaceofoperations,anddescribesthesetofoperationsapplicableatagivenstate.
I~isthesetoftransitions,rCSxP(S)*S;thus,anedgeisatriplet,(xl,p,x2),containingastartstate,2.
Notethatnocomputationsareactuallycarriedout.
Wearemerelyestimatingassumedcomputations.
Figure5.
AnoutlineofanSTN.
alabel,andanendstate.
Thelasttwoelementsoftheequation,XoES,and,yCSaretheinitialandthefinalstates,respectively.
Theinitialstatecontainstheuncomputedquery,andafinalstatecontainsthecomputedquery,andpossiblyvariousintermediateresults.
Aplanforaquery,Q,andastate,x,tellswhichsequenceofoperatorstoapplytothepartiallycomputedqueryQatstatexinordertoarriveatthefinalstate.
Ifx~Xothentheplanispartial.
IfweletPl0xdenotetheapplicationofoperatorPlatstatexthenaplancanbeexpressedasPl,P2,P3,.
.
.
,P,~wherep~0.
.
.
0P30P20Pl0xEXfWeassociateacostCwitheachplanintheobviousway.
First,wedefinecost:(S,P(S),S)~[0;cxs)tobethecostofapplyinganoperatortoastatetogetanewstate(i.
e.
,thecostofanedgeinourDAG).
ThenthecostofaplanisC(x,pa,P2,P3,.
.
.
,Pn)=cost(x,pl,s2)+cost(s2,P2,S3)--l-cost(sa,ps,s4)cost(s,~,p,~,xf)wherex!
EX/;Figure5showsthisplanasapartofalargernetwork.
Theminimalcostofaquery,Q,isdefinedastheminimumoverallpossibleVLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'I~me89plansforQandx:CQ(X)=min{C(x,pl,p2,P3,.
.
.
,p,)IPn0.
.
.
0p30P2oPl0xE,~gf}AplanPl,P2,P3,P~forwhichC(x,Pl,P2,P3,P~)=CQ(x)isoptimal.
4.
2PlanSelectionAssumingwehavecostsforallsinglestatetransitions,thecheapestqueryplaninthenetworkcanbefoundbyapplyingdynamicprogrammingtechniques.
ThefunctionCQ(X)oftheprevioussubsectioncanbeexpressedas:CO(Z)=rain{cost(x,p,x')+CO(Z')}peP(x)DynamicprogrammingisapplicablebecausethecostofasingletransitioninanSTNdependsonlyonlocalinformationandnot,forexample,onthenatureofprevioustransitionsthatledtothestateofthecurrenttransition.
Thishasbeentermedtheseparationassumption(LafortuneandWong,1986).
Whenusingdynamicprogramming,thetaskoffindingagoodqueryplanisconceptuallydividedintotwophases:generationoftheSTNofthequerytobecomputed;andestimationandselectionoftheoptimalpathintheSTN.
InpracticethewholeSTNneednotbecomputedbeforephasetwoisinitiated;partsneededduringphasetwomust,however,bemadeavailablewhenneededand,uponcompletion,alloftheSTNwillbeneeded.
Forthisreason,dynamicprogrammingrequiresarelativelylargeamountofstoragespace(RND,Sedgewick,1988).
AmongtheheuristictechniquestheA*algorithm(Rich,1983)isanalternative,butuntilaneasilycomputableandpreciseheuristicfunctionhasbeenfound,dynamicprogrammingseemsmorepromising.
Toreducethepotentiallylargesearchspaceandimproveperformance,weintroducepruningrules(Section6)thatspecifythefunctionP.
Theyallowustoeliminatepathsthataregenerallynotcompetitive,andthereforelimitthesearchspacewithlittlechanceofeliminatingadvantageousplans.
4.
3StateandTransitionSpacesWenowpresentthespecificdesignofthetypeofSTNtobeusedinIMfF.
Wedescribewhatconstitutesastateandwhichtransitionsarepossibleonthestates.
4.
3.
1StateSpacesoflM/T.
IM/TgeneratesaseparateSTNforeachqueryitoptimizes,andeachSTNhasitsownstatespace.
Astatespaceisasetofstates,eachconsisting90ofasetofobjects.
Allthetypesofobjectsinastatespacearestoredonsecondarymemory,andcanberead,3used,andasaresultnewobjectscanbecreated.
ThequeryofanSTNisultimatelydefinedintermsofasetofbacklogs.
ThesearepartofallthestatesforthatSTN.
Togetherwiththebacklogs,cachedresultsconstitutetheoutsetsforquerycomputation,andthecontentofthecacheispartofallstates.
Thecacheisnotchangedduringplanenumerationandselection,butcanbeupdatedwhentheselectedplanisprocessed.
Similarly,theELAPispartofeachstateofanySTN.
Thefinalcomponentofstatesisintermediateresults.
Anintermediateresultisanyquerythatcanbeexpressedintermsofbacklogs,cachedresults,andexistingintermediateresults.
Thus,differentialfilesarealsointermediateresults.
GenerallyastatewillcontainasetofintermediateresultstobeusedinfurthercomputationsinordertoachievetheevaluationofthequeryoftheSTNathand.
Withtheexceptionofdifferentialfiles,suchresultscanlaterbestoredinthecacheiftheyarepartoftheplanchosenforactualexecution.
Inthiscase,theELAPisupdatedtoreflectthenewstateofthecache.
Evenifthestateofthecacheisnotchanged,theELAPcanbeupdatedwithstatisticsofcomputed,orestimated,temporaryresults.
Twostateswithmutuallyequivalentobjectsareidenticalstates.
4.
3.
2TransitionSpaceofIM/T.
Wedefinethetransitionspacebelow.
InSection5wewilldiscussimplementationoftheoperatorsofthetransitionspace.
Theconventionalrelationaloperators,projection(Tr),selection(or),andequiojoin(M)areincluded.
Differentialoperatorsareincluded.
Indifferentialcomputation,previouslycomputedqueryresultsarereusedinconjunctionwithdifferentialfilestocomputedesiredqueries.
Tomorepreciselydefinethedifferentialoperators,wefirstconsiderdifferentialfilesinmoredetail.
LetQandQtbequeryexpressionsthatevaluatetorelationswithidenticalschemas.
AdifferentialfilefromQtoQ',~(Q~Q'),satisfiestworequirements.
First,itconsistsofanorderedpairofrelationswithschemasidenticaltothoseofQandQ'.
6(Q~Q')=(6-(Q~Q'),6+(Q~Q'))Second,theresultofqueryQ~maybecomputedfromtheresultofqueryQbyapplyingthedifferentialfileasfollows.
Q'=(Q-~-(Q~Q'))t.
.
J6+(Q~Q')3.
Objectsstillexistaftertheyhavebeenread.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'lime91Forthisexpression,wewillusethenotationQ'=DIF(Q,6(Q--rQ')).
Now,differentialselection,projection,andjoinmaybedefinedasfollows.
DIF-i(iF(Q),6(Q~Q'))=(oF(Q))'DIF-Tr(TrA(Q),6(Q~Q'))=(TrA(Q))'DIF-M(Q1t~Q2,Qi,6(Qi"-~Q~),Q2,6(Q2~Q~))=(Q1t~Q2)~Here,wedefine(iF(Q))'=iF(Q)',(~A(Q))'=7ra(Q)',and(Q1NQ2)'=Q~t~Q~.
Indifferentialselection,thedesiredquery,(IF(Q))',maybecomputedfromanalreadycomputedquery,IF(Q),andthedifferentialfile6(Q--~Q').
ThiscontrastsrecomputationwherefirstQ'is(re-)computedandthentheselection,iF,isre-applied.
Operatorsthatprovidethedifferentialfilesusedinthedifferentialformulasareincludedinthetransitionspace.
DELTA(tl~t2,BR)DELTA-If(r,6(Q~Q'))DELTA-r(A,6(Q~Q'))DELTA-M(Qi,6(Q1--+Qi),Q:,6(Q~~Q~))=6(R(t~)~R(t2))=6(iF(Q)-~(iF(Q))')=6(rA(Q)~(rA(Q))')=6((Qi~Q2)~(Qi~Q2)~)Thefirstoftheseoperatorstakesabacklogrelation,BR,andtwotimevalues,Q,t2,asarguments.
Theresultisthedifferentialfilethat,whenappliedtoR(tl)resultsinR(t2).
Thisisthebasecaseoperator.
Theremainingoperatorsarethestepcaseoperators.
Forexample,theDELTA-i-operatorwill,givenaselectioncriterion,F,andadifferentialfilefromQtoQ',returnthedifferentialfilefromiF(Q)to(iF(Q))'.
Finally,combinedoperatorsareincludedsothatcombinedoperatorsmaybemoreefficientlyprocessedthansequencesofuncombinedoperators.
Toillustratethis,assumethatwehaveavailabletheresultofthequery7rA(O'F(R(tl)))andthatwewanttocomputethequery7rA(ir(R(t2))).
Withtheoperatorsabove,wemayproceedasfollows.
1.
EvaluateDELTA(t1---+t2,BR)toget6(R(tl)~R(t2)).
2.
EvaluateDELTA-i(F,6(R(tl)~R(t2)))toget6(iF(R(Q))IF(R(t~))).
3.
EvaluateDIF-r(rA(IF(R(tl))),6(IF(R(tl))~IF(R(t2)))toobtainthefinalresult.
92ThisimpliesthattheresultsofbothStep1andStep2arewrittentodisk.
AcombinedoperatorsuchasDIF-Tro(TrA(O'F(Q)),6(Q~Q'))eliminatesthestorageoftheresultofStep2byprocessing7rAandO'Finasinglepass.
Ingeneral,weallowforcombiningselectionandprojectionwithanotheroperator(cry7r~~,orcombined)intoacombinedoperator.
4.
3.
3IdentilyTransformations.
Auserquerycanbeprocessedinmanywaystoproducethedesiredresult.
Duringqueryoptimization,equivalencetransformationrulesforalgebraexpressionsareutilizedtoenumeratethepossibleexecutionordersforaquery.
Weaddthefollowingthreerulestotheonespresentedintheliterature(Ullman,1982;JarkeandKoch,1984;SmithandChang,1975).
1.
Substitutingselectionanddifferentialselection.
O'))_=ffF(DIF(Q,O')))2.
Substitutingprojectionanddifferentialprojection.
DIF-Tr(Tra(O),6(O~Q'))~7rA(DIF(Q,6(Q~O')))3.
Substitutingjoinanddifferentialjoin.
DIF-N(Qi~Q:,Q1,6(Q1~QI),Q2,6(Q2~Qi))-=DIF(Q1,6(Qi~Qi))t~DIF(Q2,6(Q2~Q[))Theproofsoftheseequivalencesaresimilarandstraightforward.
Forexample,thelefthandsideofthethirdruleisequivalentto(Q1MQ2)',bydefinition.
ThisinturnisequivalenttoQ~MQ~.
BydefinitionofDELTA,therighthandsideofthethirdruleisequivalenttoQ~IXlQ~.
Thus,therulefollows.
4.
4UsingtheELAPforCacheAccessWehaveincludedacacheforviewsinIM/F,andwehavedefinedanELAPasa"structuringindex"onthecache.
TheroleoftheELAPistoallowforefficientidentificationofcachedresultsthatcanbeusedtocomputeaqueryathand.
LetDBbeadatabaseinstance(i.
e.
,aninstanceofthebacklogstore)andQCthedefiningexpressionofacachedresult,thenQC(DB)isthecachedresultofQConDB.
TheresultQC(DB)isonlyusefulforthecomputationofa(sub-)query,Q,,ifthedataofQs(DB)areallcontainedinQC(DB),andcanbeextractedfromQ~(DB)usinganexpression,E,ofthequerylanguage(YangandLarson,1985).
Ifthisisthecaseforanydatabaseinstance,wesaythatQ~coversQs,Q,_EQC.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'lame93Coverageisanintensionalproperty.
Formally,QsEQC---E(Oc))where0denotesQwheretemporalinformation(timeslice)isignored.
Thus,a~>as(R(tl))a~_>lo(R(t2)),evenifta~t2,becauseaz>ls(R)~O'x~15(a~>lo(R)).
Thecoveringquerieswearemostintereestedinaretheonesthataremostcheaplymodifiedtotherequestedquery,i.
e.
,theminimalcoveringqueries.
Certainly,ifQ1EQ2EQ3then,consideringonlycoverage,wewouldprefertouseQ2insteadofQ3tocomputeQ1-Orthogonaltotheissueofcoveragethereistheissueoftemporalclosenesswhichwehavedisregardedsofar.
Thereisbothanintensionalandanextensionalaspect.
Weaddresstheintensionalaspectfirst.
Whenwehaveretrievedaresultfromthecacheitmightnotreflectthestateweareinterestedin.
IfweletQs=ax>_lO(R(Q))andletQ~=a~_>lo(R(ta))thenthetwoqueriesareidenticalundercoverage,butiftl~ta,theoperatorDIF(probably)stillneedstobeappliedtoQ~andanappropriatedifferentialfiletomakeitcorrectlyreflectthedesiredstate.
AssumetheexistenceofQ~=o'~>_lO(R(tb)).
IfthetemporalexpressionstaandtbarebothfixedthenwewouldchooseQ~iftaisclosertotlthanistbotherwise,wewouldchooseQ~.
Theconceptofclosenessisdefinedintermsofthecostofthedifferentialcomputationthathastobecarriedoutinordertoreachthedesiredstate,anditdependsonthesizeoftheportionsoftheassociatedbacklogthathastobeprocessed.
Thedistancebetweentimestampsisanintensionalpropertywhichcanbeusedforcomparingcloseness.
However,ift~_lO(R(tl)),andthecachecontainsQ~=a~>_lO(R(tl))andQ~=ax_>10(R(t2)),whereta~t2thenQ~stillcanbemoreusefulthanQ~.
ThisissobecausetlcouldbetimedependentandQ~couldbeveryoutdated.
Outdatednessofacachedqueryresultisdefinedastheclosenessbetweenthedefiningqueryexpressionatthetimeitwascomputedandthecurrentdefiningqueryexpression.
ForeachcachedresulttheELAPstoresthevalueofthevariableNOWatthetimewhentheresultwascomputedsothatthestatesofcachedresultscanbeinferredwithoutactuallyaccessingthem.
AlsotheELAPholdsstatisticsthatcanhelpestimatetheoutdatednessofresults(i.
e.
,estimatethenumberofchangerequestsbetweentwopointsintimeandthecostofprocessingthemappropriately).
94Figure6.
ImplementationofoperatorsofSTNs.
datapointerMDELTAxxdataDECRDELTA-o"DELTA-n"DELTA-M{}dataDIFxpointerDIF-o*DIF-rDIF-M5.
ImplementationofOperatorsofSTNsHerewediscusstheoperatorsinmoredetail.
Initially,weoutlinethedifferentcasestoconsider.
Basedonthese,wediscussalternativesforimplementationoftheoperators.
5.
1OverviewofOperatorsTheoperatorsconsideredareoutlinedinFigure6.
Thefigurehas22entries,eachcorrespondingtoaseparatecase.
InIM/Tresultscanbestoredaseitheractualdataorpointersthatpointtothedata.
Theentries"data"and"pointer"indicatethetypeofarguments.
Alloperatorsmustworkonbothkindsofarguments,withoneexception:TheDELTAoperatorinboththeincrementalandthedecrementalcaseisappliedtoabacklogwhichisadataargument.
IntheFigure6,thetypeoftheresultreturnedbyanoperatorisassumedtobethesameasthetypeofthearguments.
However,iftheargumentsaredata,bothdataandpointerresultsarepossible,theonlyrestrictionbeingthatdifferentialfilesareassumedtobedata.
Thisgivesanadditionalsevencases(i.
e.
,threeforo',7r,andMwithdataarguments;VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransactionTime95fourforDIF,DIF-tr,DIF-Tr,andDIF-Nwithdataarguments).
Asthefirstsixentries,wefindtheordinaryoperatorso',7r,andM.
4Theseoperatorshavetheirstandardsemanticsandcanbeimplementedassuggestedintheliterature(e.
g.
,Selingeretal.
,1979;Shapiro,1986.
)Theremainingsixteencasesconcernthenewoperators.
TheoperatorDELTAincrementallyordecrementallyprocessessequencesofchangerequestsstoredinbacklogstogetdifferentialfiles.
ThethreeremainingcasesoftheDELTAoperatorarethecomputationsofdifferentialfilesofrelationsfromwhichtheyarederivedbyeitherprojection,selection,orjoin.
ThefourDIFoperatorsdifferentiallyupdateastoredresulttocorrectlyreflectadesiredstate.
Theoperatorsdifferonhowtheoutsetisrelatedtothedifferentialfile(s)tobeused.
Itispossibletousethedifferentialfileofarelationfromwhichtheoutsetisderivedbyaprojection(includingtheidentityprojection)oraselection.
Thedifferentialfilesofrelationsfromwhichtheoutsetisderivedbyajoincanbeusedalso.
Finally,selectionsandprojectionscanbedoneonthefly,meaningthataselectionandaprojectioncanbeperformedinterleavedwithanotheroperator(selection,projection,orjoin)inasinglepasswithoutstorageofintermediateresults.
Inthefollowing,wewillgenerallyconsideronlythecaseswheretheoperatorstakedataargumentsandproducedataresults.
5.
2Selection,Projection,andJoinThetraditionalrelationalalgebraoperators,selection,projection,andjoin,canbeappliedtoanyrelation,includingdifferentialfiles,(~-(Q~Q'),~+(Q~Q')).
TheexpressionFoftheselectionoperator,O'F(Q),cancontainaconjunctionofselectioncriteriaoftheformAtt_NameopAtt_NameorAtt_NameopValuewhereopisoneofor~,andAtt_NameisanattributeidentifieroftherelationvaluedexpressionQ.
Themostadvantageousimplementationofselectiondependsonnumerousfactorsandhasbeenaddressedalreadyinmanysettings.
Consequentlywewillnotaddressithere.
Theprojectionexpression,A,of7rA(Q)isanysubsetofattributesofQ.
Whenwedodifferentialcomputations,wewouldliketobeabletodistributeprojectionsoverdifference.
Inordertomakethislegal,wemustatalltimesmakesurethatuniqueidentificationoftuplesispossible.
Wechoosetodothisbyalwaysretainingtheprimarykeyofrelations,rememberingwhetheritwasremovedbyprojection4.
Inthefollowing,Dtxthenweareinthedecrementalcase.
Theconstructionprocedurefor6+(R(t,)--~R(t=))and6-(R(t,)R(t=))startswiththeinitializationofthesetoemptyrelations.
Theschemaof6+(R(Q)--~R(t=))isthesameasthatofR,andtheschemaof6-(R(ta)R(tx))onlycontainstheprimarykeyattributeofthatofR.
5Thenweprocesschangerequestsfromtheoutsetinthedirectionoft=untilthenextchangerequesttobeprocessedhasatimestampthatisnotinthehalf-openintervalfromt,to,andincluding,t=.
Eachrequestisprojectedtoremovesuperfluousattributevalues.
Assumingthatweareintheincrementalcase,insertionrequestsgointo6+(R(ta)~R(t=))whichoptionallycanbekeptsortedonkeyvalues,or/andan(hash)indexonkeyvaluescanbemaintained.
Adeletionrequestreferstoeitheratupleintheoutsetortoatuplein5.
Onlythekeyisneededinanactualimplementation,butinalgebraexpressionsweassumeforsimplicitythattheschemaisthesameasthatofR.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'Iime97+(R(ta)~R(t~)).
6First6+(R(t~)~R(t~))issearchedforatuplematchingthedeletionrequest,andifamatchisfound,thentherequestisdisregarded,andthematchingtupleofthecurrent6+(R(t~)~R(tx))isdeleted,becausetheneteffectisthatnochangetakesplace;otherwise,thedeletionrequestgoesinto6-(R(t~)~R(t~)).
Notethatnoactionwastakenwhenweencounteredaninsertionrequestofapreviouslyencountereddeletionrequest.
Suchcorrespondingdeletionandinsertionrequestsmustbecarriedoutbecausetheyupdateimplicittimestampattributesofbaserelations;suchattributesarehidden,butcanbeseenbyexplicitprojections.
Here,weignoretheseimplicitattributes.
Tuplesof6+(R(t~)--~R(t~))and6-(R(t~)~R(t~))arewrittentosecondarymemoryonepageatatime.
Notethattherearenoreferencesfrom6-(R(t~)~R(t~))to6+(R(t,)~R(t~)),makingthesequenceofoperationintheformulaabovevalidinthesensethattheoutcomeofDIF-(R(t.
),6(R(t~)-~R(t~)))is,infact,R(t~).
Alsonotethattherecanbereferencesfrom(~+(R(t,)--~R(tz))to6-(R(ta)~R(t~)),makingthesequenceofoperationintheformulatheonlyvalidone.
Whentherearenomorechangerequests,bothdifferentialsarestoredsortedonkeyvalues,andtheoptionalindexon6+(R(t~)~R(t~))isdeleted.
Inthedecrementalcase,theonlychangeisthatdeletionrequestsassumetheroleofinsertionrequests,andviceversa.
5.
3.
2TheStepCases.
Now,weconsiderthecaseswhereadifferentialfileofaresultisconstructedfromthedifferentialfileofanotherresult.
InDELTA-a(F,6(Q--~Q')),theoperatorconstructsthedifferentialfilefromoF(Q)to(O'F(Q)fusingthedifferentialfilefromQtoQ',6(Q~Q'),whereQdenotesanyqueryexpression.
Thisisjustaselection:DELTA-cr(F,6(Q--~Q'))=aF(6(Q~Q'))=(OF(6-(Q~Q')),O~F(6+(Q~Q')))Claimingthatthiscorrectlycomputes6(CrF(Q)~(aF(Q))')isequivalenttoclaimingthatthefollowingexpressioncorrectlycomputes(aF(Q)f.
(dE(Q)-aF(6-(Q~Q')))UaF(6+(Q~Q'))6.
Notethateagerlymaintainedcurrentstatesofuser-definedrollbackrelationsallowforcheckingthatdeletionsandinsertionsactuallymakesense,i.
e.
,thatdeletionsactuallydeletesomethingexistingand,con-versely,thatinsertionsactuallyinsertsomethingnotalreadyexisting.
Thesearesystemenforcedintegrityconstraints.
98Figure7.
TheDELTA-o-andDELTA-~-operators.
QI÷!
0"tIJI!
IQ-+!
7g-+Thisexpressionisequivalenttothefollowing.
aF((Q--~-(O~O'))t_J~+(O~Q'))CorrectnessfollowsasthisisequivalenttoO'F(Q')which,inturn,isequivalentto(oF(Q))'.
Next,inDELTA-Tr(A,~(Q---~Q')),wemakeaprojection:DELTA-Tr(A,~(Q~Q'))=7rA(~(Q~Q'))=(TrA(~-(Q-->Q')),Q'))Rememberthatkeyinformationisretainedtoovercometheproblemofindistin-guishabletupleswhendistributingaprojectionoveradifference.
TheproofofcorrectnessissimilartothatoftheDELTA-ooperator.
Figure7isaschematicalrepresentationoftheDELTA-o"andDELTA-Troperators.
Thelastcaseisthejoin:DELTA-M(QI,~(QI~QI),Q2,~(Q:~Q~)).
ToconstructthedifferentialfileofQIMQ2,weneedbothQ1,Q2,~(Q1-+Qi),and~(Q2--~Q~).
Inordertoexplainthederivationoftheformulaforcomputing~((Q1MQ2)~(Q1MQ2)'),considerthefollowingthreeequalities:Q'IMQ~=(Q1MQ~)'(1)(Q1MQ2)':[(Q~MQ2)-~-((QiMQ2)-~(Q~MQ2)')](2)U(~+((Q1MQ2)~(Q1MQ2)')QiMQ~=[((Q1-~-(Q1~Q~))u8+(Q1~Qi)]M(3)[((Q2-~-(Q2-~Q~))t-J~+(Q2~Qi)]VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransactionTime99Wederive(i((Q1~Q2)~(Q1NQ2)')bytransformingtherighthandsideofequality(3)intoanequivalentexpressionoftheform[(Q1~Q2)-~]u~.
Then,byequalities(1)and(2),((i-((Q1~Q2)~(Q~~Q2)'),6+((Q1Q2)-~(Q1pdQ2)Todothetransformation,weneedtwotransformationrules:(Q1uQ2)~Q8-=(Q1pdQa)u(Q2~Qs)(Q1-Q2)~Q8---(Q1NQ3)-(Q2NQ8)Toderivethefirst,observethat(Q1uQ2)xQ3_~(Q1xQ3)u(Q2xQ8).
Because,inaddition,Q1NQ2---OfF(Q1XQ2)whereFistheequi-joincondition,then(QiuQ2)~Q~---o'[(QiuQ2)xQ~]-=~-F[(QIxQ3)u(Q2xQ8)]_--o~(q~xq~)uoF(q2xq~)---(Qi~Q~)u(Q2NQ~)Thesecondisprovenasfollows.
First,assumethatxE(Q~-Q2)NQ3;then,weprovethatxE(Qa~Q3)-(Q2~Q~).
Theelementxisoftheform(x1,~2)whereXl~(Q1-Q2)and~2eQ3.
Further,XleQ1andxlQ2.
Hence,(zl,x2)~Q1~Q3,and(Xl,X2)Q2~Qa.
Second,weassumetheconverseandprovethatxE(Q1-Q2)pdQ3.
Here,xCQ1pdQ3,andxQ2NQ3.
Consequently,xI~Q1,andX2~Q3,andalsoXlQ2.
ButthenXlEQ1-Q2.
Usingtheabbreviations(ix+/-and(i2+/-for(i+/-(Q~~Qi)and6+/-(Q2Q~),respectively,wenowhave[(Q1-(il-)u(il+]pd[(Q2-(i2)u(i2+]-={(Q1-6~-)N[(Q2-(i~-)u(i2+]}u{61+N[(Q2-(i~)u(i2+]}----{[(Qi-(I~)N(Q2-6~)]u[(Q1-6~-)N62+]}u{[(i~~(Q2-6~-)]u((i~-N(itt)}~-{{[qls(q2-(ii-)]-[(ii-~(q2-(ii-)]}u[(qlN6~-)-((iFN(i~-)]}u{[((ittNQ2)-(6~~(ii)]u((itN(itt)}_--{{[(ql~q2)-(qls6i-)]-[(6i-Nq2)-(6~-~(ii-)]}u[(Q,N6~-)-(6~-N62+)]}u{[(6~+NQ2)-(6tN(i~-)]o(61+N(it)}_--{(Q~NQ2)-(Q~N(i~-)-[(6i-NQ2)-((i~-N(i~-)]}u[(Q1~62+)-(6~ixl62+)]u[(61+pdQ2)-(61+N6~)]U(6~+N6~-)100Thetwolastrighthandsidescontaindifferentexpressionsforthedifferentialfileofajoin.
Forexample,usingthelastone,wehaveDELTA-N(Qi,~(Q1~Q~),Q~,~(Q2~Q~))=-(~-((Q~~Q2)~(Q1t~Q2)'),~+((Q1t~Q2)~(Q1MQ2)'))=-([01~~u(~-t~Q,1],yzThecomponentsof~-((Q1t~Q2)~(Q1MQ2)')are:(a)thedeletionstoQ1~Q2duetodeletionsfromQ2;and(b)thedeletionstoQ1NQ2duetodeletionsfromQ1,butwithoverlappingdeletions(i.
e.
,6-(Q1~Q~)N6-(Q2~Q~))removed.
Thecomponentsof6+((Q1NQ2)~(Qa~Q2)')are:(x)insertionstotheoutsetduetotuplesfromQ1matchinginsertionstoQ:,butnotincludingtuplesduetomatchesbetweeninsertionstoQ2anddeletionstoQ1;(y)acomponentsymmetric,inQ1andQ2,to(x);(z)insertionstotheoutsetduetomatchesbetweeninsertionsinQ1andinsertionsinQ2.
Figure8showsalltheconstituentjoinsof~-((Q1~Q2)~(Q1~Q2)')and6+((Q1~Q2)~(Q1NQ2)')bymeansofdottedlinesconnectingtworelations.
Therearenodeletionsofinsertionsinthedifferentialfileofajoin,DELTA-(Qi,~(Qi--~QI),Q2,~(Q2~Q~)).
Toseewhy,observethatneitherofthetwocomponents(aandb)for~-((Q1)4Q2)---r(Q1~Q2)I)overlapanyofthethreecomponentsof~-((Q1~Q2)--+(QiNQ2)~)(x,y,andz).
(a,x)and(a,z):disjointbecause~-(Q2~Q~)and(~+(Q2--+Q2)aredisjoint.
(b,y)and(b,z):disjointbecause~-(Q1~Q~)and~+(Q1--rQi)aredisjoint.
(a,y):disjointbecause~-(Q2~Q2)andQ2-~-(Q2~Q~)aredisjoint.
@,x):disjointbecause(~-(Q1~Q~)andQ1-~-(Q1--rQ~)aredisjoint.
Asshown,thedifferentialofajoinisacomplexqueryanditcanbecomputedinmanyways(Blakelyetal.
,1986).
Techniquesfrommultiplequeryoptimizationcanheexploited(Jarke,1984;Kim,1984;ChakravarthyandMinker,1986;SeUis,1986,1988b).
Forexample,keepingallsixargumentrelationssorted,joinscanbedoneinterleavedandpagewise(pipe-linejoin).
ItisstraightforwardtoimplementoperatorssuchasDELTA-Tro(A,F~~(Q--+Q~))whereprojectionandselectioniscombined.
Thisisdoneusingcombinedoperatorsoftheprevioussubsection.
"Combined"generationofdifferentialfilesdirectlyfromchangerequestsandselections/projectionsispossiblealso.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'Iime101Figure8.
Computationofdifferentialsofjoins.
Deletions-!
I+-+"Q1Q2i-+Q1~Q~I.
5.
4Incrementing/DecrementlngRelationsNowwediscusstheimplementationofthefouroperatorsfordifferentialcomputationinturn.
5.
4.
1TimeSlicingBaseRelations--TheBaseCases.
FortheDIFoperatorwewillinvestigatetwocases.
FirstweconsiderthespecialcaseofcomputingDIF(R(t=),tS(R(t=)~R(ty)))whereweusethebacklogBRdirectlyasanalternativetofirstcomputingtS(R(t=)--~R(ty)).
Second,weconsiderthegeneralcase,DIF(Q,6(Q~O')).
ThefirstcaseisillustratedinFigure9.
Notethatbothincrementalanddecrementalcomputationarealwayspossible(witht==tinitandt==NOW,respectively).
Inthiscase,changerequestsareprocessedoneatatimetowardstherequestedstatefromtheoutsetuntilthetimestampofthenextchangerequesttobeconsideredexceedsthetimeofthedesiredstate.
Theresultofaninsertionrequestisthatthetupleoftherequestisenteredintothecurrentoutset,andtheresultofadeletionrequestisthatthetupleidentifiedbytherequestisremovedfromthecurrentstate.
102Figure9.
Time-slicingabaserelation.
t~ni,Time1BRll~[tttn(*~)n(t~)NOW1Inthegeneralcase,DIF(Q,(5-(Q---~Q'),~+(Q~Q'))),weinitiallysort5-(0~~')and5+(0~Q')iftheywerenotsortedalready.
BothG-filesarethensimultaneous"merged"withtheoutset:firstapageofdeletionsisread,thenthefirstrelevantpageoftheoutsetandthefirstrelevantpageoftheinsertionsareread.
Deletionsareperformedontheoutsetfirst,thenrelevantinsertionsareperformed.
Wheneverapageistotallyread,thenextpageoftherelationisread.
Inthecaseoftheoutset,processedpagesarewritten,andonlypagesthatarerelevantforthedeletionsareread(irrelevantpagescanbeconsideredprocessedandwrittenalready).
Whenthereareneitherdeletionsnorinsertionsleft,theprocessingterminates.
Followingthisprocedure,pagesofthethreerelationsareonlyreadonce,andirrelevantpagesoftheoutsetneednotbereadatall.
WhencomputingDIF(R(t~),6(R(t~)~R(tv)))weusethecharacteristicsofthearguments(i.
e.
,thesizeoftheoutsetused)andthedifferentialfile,ascriteriaforchosingbetweenthefirstandavariationofthesecondstrategy.
Theframeworkincludesacomponentthat,giventhenameofabacklogandastartandanendtime,returnsestimates:thenumberofinsertions,thetotalnumberofchangerequests,andthenumberofdeletionsofinsertions.
Theinputtothecomponentisproducedduringnon-eagerprocessingofchangerequests.
Ifthefirststrategyisused,countsofinsertionsanddeletionsareused;ifthesecondstrategyisused,againcountsofinsertionsanddeletionsareavailable,butsoisalsothefinalnumberofinsertions.
Howtheseinputsaremostefficientlyusedtogeneratetheoutputisatopicofcurrentresearch.
Thefirststrategyisadvantageousifthetotalnumberofchangerequeststobeprocessedislow.
Thechoiceofkeeping~+(Q~Q')sortedornotdependsonVLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction"Iime103Figure10.
Differentialselection,projection,andjoin.
DIFDIF-o'/DIF-Tr][DIF-~U_1thenumberofinsertionsinto6+(Q~Q')comparedtothenumberofdeletionstobeprocessedagainst6+(Q~Q').
Ifsortingisadopted,insertionhasanoverhead,andifnot,thensearchfordeletionsmustbedonebysequentialscan.
5.
4.
2TheStepCases.
Thedifferentialselectionandprojectionoperators,DIF-o"(O'F(Q),6(Q--~Q'))andDIF-Tr(TrA,6(Q~Q')),respectively,maybecom-putedasfollows.
DIF-a(aF(Q),8(Q~Q'))=(aF(Q)-aF(8-(Q~Q')))UaF(8+(Q~Q'))DIF-r(~rA(Q),8(Q~Q'))=(rA(Q)-rA(8-(Q-+Q')))urA(8+(Q-+Q'))ThecorrectnessoftheseobservationsfollowsfromtheobservationsaF(6(QQ'))=6(trF(Q)~trF(Q)')and7rA(6(Q~Q')):6(TrA(Q)--~7rA(Q)').
Differentialselection,projection,andjoinareillustratedinFigure10.
Foreachoftheoperators,theargumentsareshown.
ThebrokenboxofDIF-o'/DIF-Trisnotanargument--itispresentonlytoindicatetherelationshipbetweenthearguments.
'ThefinalcaseisDIF-~(Q1t~Q2,Qi,6(Q1~Q1),Q2,(Q2--~Q~)),thedifferentialjoin.
FromSubsection5.
3,wehave(again,weabbreviate6+/-(Q1Q~)and6+/-(Q2---~Q~)by61+/-and62+/-,respectively).
DIF(Q1t~Q2,Q1,~Q~,Q2,~Q~)[(Q1Mu[(~1"NQ~i)]u104Letusconsiderprocessingofthedeletionstotheoutset.
Thetwocomponentscanbeexplainedasfollows.
1.
Q1~6-(Q2~Q~)areallthedeletionsfromtheoutsetduetOdeletionstoQ2;2.
(6-(Q~~Qi)t~Q2)-(6-(Q1~Qi)M6-(Q2~Q[))areallthedeletionstotheoutsetduetodeletionstoQ1withduplicatedeletionsduetooverlapsbetween6-(Q1--~Q~)and6-(Q2~Q~)andalreadyincludedin(1)removed.
Theoverlapscanbeignoredwithoutaffectingthecorrectnessofthefinalresult,andthedeletionsrepresentedbythetworemainingtermscanbeperformedusingonlyQ1NQ2,6-(Q1~Q~),and6-(Q2~Q~).
Atupleoftheoutsetisoftheform(zoo,XQ2)whereXolisatuplecompatiblewithQ1andxo2isatuplecompatiblewithQ2.
TuplesofQ1NQ2whereXQ2matchatuplein6-(Q2~Q~)aresimplydeleted;similarlytupleswherexolmatchatuplein6-(Q1~Q~)aredeleted.
Now,letusturntotheinsertions.
Itisinstructivetoreformulatetheexpressionfor(Q1~Q2)'asfollows(with6-((Q1NQ2)----r(Q1NQ2)')abbreviatedby6~-2).
(Q1MQ2)'(Q~-6~)M(Q2-6~-)u[(Q~-6i-)M6~]u{6~M[(Q2-6~-)u62+])=--Q1MQ2-6~u[(Q1-61-)u61+-61t]N62+]U(61+t~[(Q2-6~-)U62+]}=-Q1t~Q2-6~-2u{[(Q~-6;)u61+]N62+}-[61+N6~-]u{6~-N[(Q2-6;)u6~-]}--=Q1MQ2-61-2u{[(Q,-6;)u61+]t~6~-}u!
6~+t~(Q2-6;)!
7Theinsertion,6+((Q1MQ2)~(Q1~Q2)'),isnowdefinedbytwojoins.
Thefirst(1)has6+(Q2~Qi)asoneargument,andthesecond(2)has6+(Q1~Qi)asoneargument.
Thisexplainsthesuperiorityofdifferentialcomputationwhendifferentialsaresmallandrelationslargebecauseinsuchcasesanexpensivejoinoftwolargerelations,Q~andQ~,isavoidedandtwojoinsofasmallrelationwithalargerelationisdoneinstead.
77.
Differentialcomputationandrecomputationbothinvolveadditionalprocessingapartfromjoins,but,becausejoinisthemostexpensiveoperation,weignorethis.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction"rime105Algorithms,costs,andefficientimplementationofincrementaljoinforpointerviewsintheADMSsystemarediscussedindetailinStamenas(1989)andRous-sopoulous(1991).
6.
PruningtheSearchSpaceWealreadyhavepresentedacompleteframeworkforqueryoptimization.
HereweintroducetheconceptofpruningaSTN.
Pruningisameansoffurtheroptimizationofplanselection.
ThepurposeistoreducethesizesoftheSTNsgeneratedwithoutleavingoutpromisingqueryplans.
ReducedSTNsmeanreducedcostsofestimatingcostsofsingletransitionsandasmallerargumentofthedynamicprogrammingalgorithmwhichthereforeexecutesmoreefficiently.
ThepurposeofintroducingthemappingPinthedefinitionofanSTNwasexactlytobeabletoincludepruningintotheframework.
Therulesofthissectionrestrictthenumberofpossibletransitionsatastate.
TherulesbelowillustratethekindofrulesthatcanbeintegratedintoIM/TRulesfromstandardqueryoptimization(Ullman,1982)canbeapplied,too.
Rule1.
Onlyapplyadifferentialtoitsoutsetifexactlytheselections/projectionsperformedontheoutsethavebeenperformedonthedifferentia~too.
Obeyingthisrulewillensurethatselections/projectionsaredoneononlytheoutsetorthedifferential,andneverontheupdatedoutset.
Thisisreasonablebecauseatleastthedifferentialcanbeassumedtobemuchsmallerthantheupdatedoutset.
Rule2.
Applyoperatorsasearlyaspossible.
IftheargumentsinstateXbofanoperationp(transformingXbintoxc)arepresentinanpredecessorstate,xaofXbthenpshouldbeappliedtoxainsteadoftoXb.
Rule3.
Onlycomputeadifferentialofanoutset,iftheoutsetalreadyexists.
Bothse-quencesarepossible,butanSTNshouldonlyincludeoneofthem,andadifferentialisnotusefuliftheoutsetisnotavailable.
Rule4.
Applicationofmaximalcombinedoperatorsispreferabletothesequentialappli-cationoftheconstituentoperatorsofthecombinedoperators.
Rule5.
Onlyusethesmallestcachedresultoutofcoveringresultsequallyoutdatedwithrespecttothedesiredstate.
ThisandthefollowingruleattempttoconsideronlythemostpromisingcachedresultsduringgenerationafanSTN.
Rule6.
Onlyusetheleastoutdatedcachedresultoutofcoveringresultsofequalsize.
1067.
ConclusionandFutureResearchExtendingtherelationalmodeltoautomaticallyrecordtransactiontimeisnotanewidea,butimplementingtheextendedmodelbystoringthecompletehistoryofchangeinrelationbacklogsis.
Suchanimplementationwillsupportnotonlyqueriesonpreviousdatabasestates,butqueriesonthenatureofchangeitself.
Weexpectqueriesonthenatureofchangetoplayakeyroleinfutureinformationsystems.
Withever-increasingamountsofconstantlychanginginformation,itwillbeimpossibleforanindividualusertodigestalltheinformationthatpertainstoagivensituationandstayabreastofallitschanges.
Wewillseeapplicationswheretheuserisnotinterestedinthecurrentstateofthedatabaseandthechangesmadetoit,aslongastheyarebothnormal.
Ontheotherhand,ifthecurrentstateofthedatabaseorthechangemadetoitisabnormal,thentheuserisinterestedandmustbenotified.
Thepricepaidfortheaddedfunctionalityisasubstantialincreaseofspaceconsumptionandadecreaseofqueryprocessingefficiency.
Thetopicofthisarticlehasbeentheefficientsupportoftransactiontimeintherelationalmodel.
Theconcreteresultsinclude:atransparentextensionoftherelationalmodel(DMfF)wherethetransparencyissupportedbytheunderlyingimplementation(IM/T)ageneralqueryoptimizationandprocessingarchitecturewhichutilizespar-titionedbacklogstorage,selectivepointeranddata-viewcaching,eager/lazyviewupdate,cacheindexing,andstatetransitionnetworkswithdynamicprogramming.
integrationofrecomputationanddifferentialcomputationofqueriesasymmetrical,generalnotionofdifferentialcomputationintegratingincre-mentalanddecrementalcomputationformulasfordifferentialcomputationageneralizationofthenotionofquerysubsumptiontoutilizedifferentialcomputationaugmentationofstandardqueryoptimizationwithrulesforoptimizationofdifferentialqueryprocessingSeveralaspectsoftheindividualcomponentsofIM/Tarethesubjectsoffutureresearch.
Theyinclude:VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction"Hme107therelativemeritsofdataandpointercachingtheextensionofexistingalgorithmsforthelogicalaccesspathtotheELAPtheadaptionofexistingcachemanagementstrategiestherelativemeritsofeagerandlazycacheupdatetheefficientapplicationofstatetransitionnetworksforqueryplanenumer-ationoftransactiontimequeriesSubstantialresearcheffortsarerequiredinordertoclarifyeachoftheseaspects(Snodgrass,1990).
Otherresearchtopicsincludethecachingofdifferentialfiles,statisticsforqueryoptimization,optimalalgorithmsforoperatorsofSTNs,andsupportforgeneralversioning.
ReferencesAhn,I.
PerformanceModelingandaccessmethodsfortemporaldatabasemanage-mentsystems.
TR86-018,UniversityofNorthCarolina,1986.
Bassiouni,M.
A.
Datacompressioninscientificandstatisticaldatabases.
1EEETSE,11(10):1047-1058,1985.
Blakeley,J.
A.
,Coburn,N.
,andLarson,P.
Updatingderivedrelations:Detectingirrelevantandautonomouslycomputableupdates.
TR,CS--86-17,ComputerScienceDepartment,UniversityofWaterloo,Canada,1986.
Blakeley,J.
A,Coburn,N.
,andLarson,EUpdatingderivedrelations:Detectingirrelevantandautonomouslycomputableupdates.
ACMTODS,14(3):369-400,1989.
Bolour,A,Anderson,T.
L.
,Dekeyser,LJ.
,andWong,H.
K.
T.
Theroleoftimeininformationprocessing:Asurvey.
ACMSIGMODRecord,12(3):27-50,1982.
Bubenko,jr,J.
A.
Thetemporaldimensionininformationmodeling.
In:Nijssen,G.
M.
,ed.
ArchitectureandModelsinDataBaseManagementSystems,NorthHol-land:Amsterdam,1977.
Chakravarthy,U.
S.
andMinker,J.
Multiplequeryprocessingindeductivedatabasesusingquerygraphs.
TwelfthInternationalConferenceonVLDB,Kyoto,Japan,1986.
Christodoulakis,S.
Analysisofretrievalperformanceforrecordsandobjectsusingopticaldisktechnology.
ACMTODS,12(2):137-169,1987.
108Codd,E.
EArelationalmodelofdataforlargeshareddatabanks.
CACM13(6):377-387,1970.
Codd,E.
EExtendingthedatabaserelationalmodeltocapturemoremeaning.
ACMTODS,4(4):397-434,1979.
Dadam,P.
,Lum,V.
,andWerner,H.
D.
Integrationoftimeversionsintoarelationaldatabasesystem.
TenthInternationalConferenceonVLDB,Singapore,1984.
Gunadhi,H.
andSegev,A.
Aframeworkforqueryoptimizationintemporaldata-bases.
ProceedingsoftheFifthInternationalConferenceonStatisticalandScienttficDatabaseManagemeng1989.
Gunadhi,H.
,Segev,A.
andShantikumar,G.
J.
Selectivityestimationintempo-raldatabases.
TR,LBL-27435,InformationandComputerScienceDivision,LawrenceBerkeleyLaboratory,1989.
Hanson,E.
N.
Aperformanceanalysisofviewmaterializationstrategies.
InternationalConferenceontheManagementofData,SanFrancisco,1987.
Hong,W.
andWong,E.
Multiplequeryoptimizationthroughstatetransitionanddecomposition.
Memorandum,UCB/ERLM89/25,ElectricalResearchLab,CollegeofEngineering,UniversityofCalifornia,Berkeley,1989.
Jarke,M.
andKoch,J.
Queryoptimizationindatabasesystems.
ComputerSurveys,16(2):111-152,1984.
Jarke,M.
Commonsubexpressionisolationinmultiplequeryoptimization.
In:Kim,W.
,Reiner,D.
S.
,andBatory,D.
S.
,eds.
,QueryProcessinginDatabaseSystems,Springer-Verlag:Boston,1984,pp.
191-205.
Jensen,C.
S.
andMark,LAframeworkforvacuumingtemporaldatabases.
CS-TR-2516andUMIACS-TR-90-105,DepartmentofComputerScience,UniversityofMaryland:CollegePark,1990.
Jensen,C.
S.
andMark,L.
Queriesonchangeinanextendedrelationalmodel.
IEEETransactionsonKnowledgeandDataEngineering,4(2):192-200,1992.
Jensen,C.
S.
,Mark,LeoandRoussopoulos,N.
Incrementalimplementationmodelforrelationaldatabaseswithtransactiontime.
IEEETransactionsonKnowledgeandDataEngineering3(4):461-473,1991.
Jhingran,A.
Aperformancestudyofqueryoptimizationalgorithmsonadatabasesystemsupportingprocedures.
FourteenthInternationalConferenceonVLDB,LosAngeles,1988.
Jhingran,A.
andStonebraker,M.
Alternativesincomplexobjectrepresentation:Aperformanceperspective.
Memorandum,UCB/ERLM89/18ElectricalResearchLab,CollegeofEngineering,UniversityofCalifornia,Berkeley,1989.
Kinsley,K.
C.
andDriscoll,J.
R.
DynamicderivedrelationswithintheRAQUELIIDBMS.
ACMAnnualConference,Detroit,MI,1979.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'I~me109Kinsley,K.
C.
andDriscoll,J.
R.
Ageneralizedmethodformaintainingviews.
NationalComputerConference,1984.
Kim,W.
Globaloptimizationofrelationalqueries:Afirststep.
In:Kim,W.
,Reiner,D.
S.
,andBatory,D.
S.
,eds.
,QueryProcessinginDatabaseSystems,Springer-Verlag:Berlin,1984,pp.
206--216.
Kolovson,C.
andStonebraker,M.
Indexingtechniquesforhistoricaldatabases.
ProceedingsoftheFifthInternationalConferenceonDataEngineering~1989.
Lafortune,S.
andWong,E.
Astatetransitionmodelfordistributedqueryprocessing.
ACMTODS,11(3):294-322,1986.
Lure,V.
,Dadam,R.
,Erbe,R.
,Guenauer,J.
,Pistor,P.
,Walch,G.
,Werner,H.
,andWoodfill,J.
DesigningDBMSsupportforthetemporaldimension.
ACMSIGMODInternationalConferenceontheManagementofData,Boston,MA,1984.
Mahanti,A.
andBagchi,A.
AND/ORgraphheuristicsearchmethods.
JACM,32(1):28-51,1985.
McKenzie,L.
E.
Analgebraiclanguageforqueryandupdateoftemporaldatabases.
TR88-050,DepartmentofComputerScience,UniversityofNorthCarolina,1988.
McKenzie,L.
E.
andSnodgrass,R.
Anevaluationofalgebrasincorporatingthetimedimensionindatabases.
ComputerSurveys,23(4):501-543,1991.
Rich,FE.
ArtificialIntelligence.
McGraw-Hill:NewYork,1983.
Rotem,D.
andSegev,A.
Physicalorganizationoftemporaldata.
ProceedingsoftheThirdInternationalConferenceonDataEngineering1987.
Roussopouios,N.
Viewindexinginrelationaldatabases.
ACMTODS,7(2):258--290,1982a.
Roussopoulos,N.
Thelogicalaccesspathschemaofadatabase.
IEEETSE,8(6):563--573,1982b.
Roussopoulos,N.
OverviewofADMS:Ahighperformancedatabasemanagementsystem.
ProceedingsoftheFallJointComputerConference,1987.
Roussopoulos,N.
AnincrementalaccessmethodforViewCache:Concept,algo-rithms,andcostanalysis.
ACMTODS,16(3):535-563,1991.
Roussopoulos,N.
andKang,H.
PrinciplesandtechniquesinthedesignofADMS±.
Computer,19(12):19--25,1986.
Rowe,L.
A.
andStonebraker,M.
R.
,eds.
ThePostgresPapers.
Memorandum,UCB/ERLM86/85,ElectricalResearchLab,CollegeofEngineering,UniversityofCaliforniaatBerkeley,1987.
Salzberg,B.
J.
andLomet,D.
Accessmethodsformultiversiondata.
ACMSIGMODInternationalConferenceontheManagementofData,Portland,OR,1989.
Sedgewick,R.
Algorithms,2ndedition.
Addison-Wesley:Reading,MA,1988.
110Segev,A.
andFang,W.
Optimalupdatepoliciesfordistributedmaterializedviews.
TR-LBL--26104,InformationandComputerScienceDivision,LawrenceBerkeleyLaborarory,1989.
Segev,A.
andGunadhi,H.
Event-joinoptimizationintemporalrelationaldata-bases.
TR-LBL-26600,InformationandComputerScienceDivision,LawrenceBerkeleyLaboratory,1989.
AlsoinFifteenthInternationalConferenceonVLDB,Amsterdam,1989.
Segev,A.
andFang,W.
Currency-basedupdatestodistributedmaterializedviews.
TR-LBL-27359,InformationandComputerScienceDivision,LawrenceBerkeleyLaboratory,1989.
AlsoinSixthInternationalConferenceonDataEngineering,1990.
Selinger,P.
G.
,Astrahan,M.
M.
,Chamberlain,D.
D.
,Lorie,R.
A,andPrice,T.
G.
Ac-cesspathselectioninarelationaldatabasemanagementsystem.
ACMSIGMODInternationalConferenceontheManagementofData,1979.
Sellis,T.
Globalqueryoptimization.
ACMSIGMODInternationalConferenceontheManagementofData,Washington,DC,1986.
Sellis,T.
Efficientlysupportingproceduresinrelationaldatabasesystems.
ACMSIGMODInternationalConferenceontheManagementofData,SanFrancisco,1987.
Sellis,T.
Intelligentcachingandindexingtechniquesforrelationaldatabasesystem.
Information~stems,13(2):175-185,1988a.
Sellis,T.
Multiple-queryoptimization.
ACMTODS13(1):23-52,1988b.
SeUis,T.
andShapiro,L.
Optimizationofextendeddatabasequerylanguages.
ACMSIGMODInternationalConferenceontheManagementofData,Austin,'IX,1985.
Sellis,T.
,Roussopoulos,N.
,andNg,R.
T.
Efficientcompilationoflargerulebasesusinglogicalaccesspaths.
Information~stems,15(1):73--84,1990.
Shapiro,L.
D.
Joinprocessingindatabasesystemswithlargemainmemories.
ACMTODS,11(3):239-264,1986.
Shoshani,A.
andKawagoe,K.
Temporaldatamanagement.
TwelfthInternationalConferenceonVLDB,Kyoto,Japan,1986.
Smith,J.
M.
andChang,P.
Y-T.
Optimizingtheperformanceofarelationalalgebrainterface.
CACM,18(10):569-579,1975.
Snodgrass,R.
ThetemporalquerylanguageTQuel.
ACMTODS,12(2):247-298,1987.
Snodgrass,R.
Temporaldatabases:Statusandresearchdirections.
ACMSIGMODRecord,19(4):83--89,1990.
Snodgrass,R.
andAhn,I.
Ataxonomyoftimeindatabases.
ACMSIGMODInternationalConferenceontheManagementofData,Austin,TX,1985.
VLDBJournal2(1)Jensen:DifferentialTechniquestoSupportTransaction'rime111Snodgrass,R.
andAhn,I.
Partitionedstoragefortemporaldatabases.
InformationSystems,13(4):369-391,1988.
Stare,R.
B.
andSnodgrass,R.
Abibliographyontemporaldatabases.
DataEngi-neering,7(4):53-61,1988.
Stamenas,A.
G.
Highperformanceincrementalrelationaldatabases.
UMIACS-TR-89--49,CS-TR-2245,DepartmentofComputerScience,UniversityofMaryland,1989.
UUman,J.
D.
PrinciplesofDatabaseSystems,2ndedition,ComputerSciencePress:RockviUe,MD,1982.
Wong,E.
andYousefli,K.
Decomposition--Astrategyforqueryprocessing.
/tCMTOD$,1(3):223-241,1976.
Yang,H.
7_,.
andLarson,E-A.
Computingqueriesfromderivedrelations.
EleventhIntemmionalConferenceonVLDB,Stockholm,1985.