On Correctness of Non-serializable Executions Work

OnCorrectnessofNon-serializableExecutionsRajeevRastogi1SharadMehrotra2YuriBreitbart1HenryF.Korth1AviSilberschatz11AT&TBelllaboratories.600MountainAvenue,MurrayHill,NJ07974-0636.2DepartmentofComputerScienceUniversityofIllinoisatUrbanaChampaign1304W.SpringeldAve.Urbana,IL61801WorksupportedinpartbyNSFgrantIRI-8904932.1AbstractInanumberofapplicationenvironments(e.g.,computeraideddesign),serializability,thetra-ditionallyacceptednotionofcorrectnesshasbeenfoundtobetoorestrictive,andanumberofalternatecriteriahavebeenproposedintheliterature.Onesuchcriterionispredicate-wiseserial-izability(PWSR),whichrequiresonlyrestrictionsofschedulesthataccesssubsetsofthedatabaseoverwhichintegrityconstraintsaredened,tobeserializable.Inthispaper,weidentifyrestrictionsonthestructureoftransactionprograms,theirconcurrentexecutionandtheiraccesscharacteristicsunderwhichPWSRschedulespreservedatabaseconsistency.Keywords:Transactions,Schedules,ConcurrencyControl,IntegrityConstraints,DatabaseStates.Note:PreprintoftheversionthatappearsinJournalofComputerSystemsandSoftware(JCSS)21IntroductionInthestandardtransactionmodel[3],adatabasestateissaidtobeconsistentifalldatabaseintegrityconstraintsaresatised.Eachtransaction,whenexecutedinisolation,mapsaconsistentdatabasestatetoanotherconsistentdatabasestate.Inthecaseofconcurrenttransactionexecutions,databaseconsistencyisensuredbyrequiringthattheresultingexecutionbeserializable;thatis,equivalenttosomeserialexecutionofthetransactions.Sinceeachtransaction,whenexecutedalone,preservesdatabaseconsistency,aserializableexecutionpreservesdatabaseconsistency.Whilethistheoryisattractivefromthepointofviewofsimplicity,inrecentyears,severalpapershaveshownthatemployingthestandardtransactionmodelforcertain\newdatabaseapplicationsorinadistributeddatabaseenvironmenthasunacceptablepracticalconsequences.Forexample,inapplicationssuchascomputer-aideddesign,wheretransactionsareofalongduration,thestandardtransactionmodelmayresultinlong-durationwaitsimposedbythelockingprotocols.Indistributeddatabaseapplications,apotentiallossofthelocalautonomyoftheparticipatingdatabasesmayresult.Theseproblemsarenotonlyissuesconcerningperformancebutalsoissuesconcerningusability,sincemanyofthe\newapplicationsareinteractiveand/ordistributed.Theapproachestakentoalleviatetheabovementionedproblemscanbebroadlyclassiedintothefollowingthreecategories:Therstapproachistoexploitthesemanticsofthedatabaseoperations,whilestillensur-ingserializabilityofexecutions.Atransactioncanbeconsideredasasequenceofhigh-leveloperations(e.g.,increment.)Commutativityamongoperations,andnotthesetofreadandwritesresultingfromtheirexecution,isusedtodetermineconictsbetweentransactions,thusenhancingconcurrency.Earlyworkinthisareaincludes[10].Morerecentworkincludes[14,9,2,5].Thesecondapproachistoexploitthesemanticsoftransactions[6,7,8].Inthisapproach,atransactionisbrokenintoasetofsubtransactions,witheachofwhichatypeisassociated.Theapplicationadministrator,thendeterminesthesetofinterleavingsofthesubtransactionsthatareacceptableandthatwouldnotresultintheviolationofdatabaseconsistency.Asanexample,considerthesagatransactionmodelinwhichatransactionTisbrokenintoasequenceofsubtransactionsT1;T2;:::;Tn.EachTiisanindependentactivitybyitself.AftertheterminationofTithelocksondataitemsheldbyTicanbereleasedandtheeectsofTiex-3ternalized.Thus,inthesagatransactionmodelallpossibleinterleavingsofthesubtransactionsarepermitted.Thethirdapproachistoexploittheknowledgeoftheintegrityconstraintsofthesystem.Afundamentaltechniqueusedinseveralapplicationdomainsistopartitionthedatabaseintosubdatabases,eachwithitsownconsistencyconstraints.Basedontheapplicationdomain,assumptionscanbemaderegardingthedegreetowhichthesesubdatabasesareindependent(asintheconceptofglobalandlocaldatausedinsomeworkinmultidatabasesystems[12])orregardingthenatureoftransactionsexecutingagainstthesesubdatabases(suchasanas-sumptionofpreservationofsubdatabaseconsistency).Onesuchapplicationdomainisthecomputer-aideddesignandmanufacturingenvironmentforwhichpredicate-wiseserializability(PWSR)wasintroducedasacorrectnesscriterionin[11].Inanutshell,thePWSRcorrect-nesscriterionstatesthatifthedatabaseconsistencyconstraintisexpressedasaconjunctionofpredicates,thenforeachpossiblescheduleS,therestrictionofStooperationsthataccessdataitemsineveryconjunctisserializable.Whilesubstantialresearchhasbeendonetowardsdevelopingapproachestorelaxtheserializabilityrequirement,verylittleworkhasbeendoneonidentifyingwhatconsistencyguaranteesresultfromtheaboveapproachestoextendingthestandardtransactionmodel.Forexample,littleworkexistsoncharacterizingtheapplicationdomainsinwhichtheusageofthesagatransactionmodelensuresdatabaseconsistency.Inthispaper,westudytheformalimplicationsofchoosingPWSRasthecorrectnesscriterion.TheimportanceofthePWSRcorrectnesscriterionhasbeendemonstratedin[11,4].In[11],itwasshownthatthePWSRcorrectnesscriterioncanbeusedtoalleviatethelong-durationwaitsassociatedwithlong-durationtransactionsincomputer-aideddesignandmanufacturingenviron-ment