数据库系统概念全套配套课件PPT ch14.ppt 53页

'Chapter14:Transactions Chapter14:TransactionsTransactionConceptTransactionStateConcurrentExecutionsSerializabilityRecoverabilityImplementationofIsolationTransactionDefinitioninSQLTestingforSerializability. TransactionConceptAtransactionisaunitofprogramexecutionthataccessesandpossiblyupdatesvariousdataitems.E.g.transactiontotransfer$50fromaccountAtoaccountB:1.read(A)2.A:=A–503.write(A)4.read(B)5.B:=B+506.write(B)Twomainissuestodealwith:Failuresofvariouskinds,suchashardwarefailuresandsystemcrashesConcurrentexecutionofmultipletransactions ExampleofFundTransferTransactiontotransfer$50fromaccountAtoaccountB:1.read(A)2.A:=A–503.write(A)4.read(B)5.B:=B+506.write(B)Atomicityrequirementifthetransactionfailsafterstep3andbeforestep6,moneywillbe“lost”leadingtoaninconsistentdatabasestateFailurecouldbeduetosoftwareorhardwarethesystemshouldensurethatupdatesofapartiallyexecutedtransactionarenotreflectedinthedatabaseDurabilityrequirement—oncetheuserhasbeennotifiedthatthetransactionhascompleted(i.e.,thetransferofthe$50hastakenplace),theupdatestothedatabasebythetransactionmustpersisteveniftherearesoftwareorhardwarefailures. ExampleofFundTransfer(Cont.)Transactiontotransfer$50fromaccountAtoaccountB:1.read(A)2.A:=A–503.write(A)4.read(B)5.B:=B+506.write(B)Consistencyrequirementinaboveexample:thesumofAandBisunchangedbytheexecutionofthetransactionIngeneral,consistencyrequirementsincludeExplicitlyspecifiedintegrityconstraintssuchasprimarykeysandforeignkeysImplicitintegrityconstraintse.g.sumofbalancesofallaccounts,minussumofloanamountsmustequalvalueofcash-in-handAtransactionmustseeaconsistentdatabase.Duringtransactionexecutionthedatabasemaybetemporarilyinconsistent.WhenthetransactioncompletessuccessfullythedatabasemustbeconsistentErroneoustransactionlogiccanleadtoinconsistency ExampleofFundTransfer(Cont.)Isolationrequirement—ifbetweensteps3and6,anothertransactionT2isallowedtoaccessthepartiallyupdateddatabase,itwillseeaninconsistentdatabase(thesumA+Bwillbelessthanitshouldbe).T1T21.read(A)2.A:=A–503.write(A)read(A),read(B),print(A+B)4.read(B)5.B:=B+506.write(BIsolationcanbeensuredtriviallybyrunningtransactionsseriallythatis,oneaftertheother.However,executingmultipletransactionsconcurrentlyhassignificantbenefits,aswewillseelater. ACIDPropertiesAtomicity.Eitheralloperationsofthetransactionareproperlyreflectedinthedatabaseornoneare.Consistency.Executionofatransactioninisolationpreservestheconsistencyofthedatabase.Isolation.Althoughmultipletransactionsmayexecuteconcurrently,eachtransactionmustbeunawareofotherconcurrentlyexecutingtransactions.Intermediatetransactionresultsmustbehiddenfromotherconcurrentlyexecutedtransactions.Thatis,foreverypairoftransactionsTiandTj,itappearstoTithateitherTj,finishedexecutionbeforeTistarted,orTjstartedexecutionafterTifinished.Durability.Afteratransactioncompletessuccessfully,thechangesithasmadetothedatabasepersist,eveniftherearesystemfailures.Atransactionisaunitofprogramexecutionthataccessesandpossiblyupdatesvariousdataitems.Topreservetheintegrityofdatathedatabasesystemmustensure: TransactionStateActive–theinitialstate;thetransactionstaysinthisstatewhileitisexecutingPartiallycommitted–afterthefinalstatementhasbeenexecuted.Failed--afterthediscoverythatnormalexecutioncannolongerproceed.Aborted–afterthetransactionhasbeenrolledbackandthedatabaserestoredtoitsstatepriortothestartofthetransaction.Twooptionsafterithasbeenaborted:restartthetransactioncanbedoneonlyifnointernallogicalerrorkillthetransactionCommitted–aftersuccessfulcompletion. TransactionState(Cont.) ConcurrentExecutionsMultipletransactionsareallowedtorunconcurrentlyinthesystem.Advantagesare:increasedprocessoranddiskutilization,leadingtobettertransactionthroughputE.g.onetransactioncanbeusingtheCPUwhileanotherisreadingfromorwritingtothediskreducedaverageresponsetimefortransactions:shorttransactionsneednotwaitbehindlongones.Concurrencycontrolschemes–mechanismstoachieveisolationthatis,tocontroltheinteractionamongtheconcurrenttransactionsinordertopreventthemfromdestroyingtheconsistencyofthedatabaseWillstudyinChapter16,afterstudyingnotionofcorrectnessofconcurrentexecutions. SchedulesSchedule–asequencesofinstructionsthatspecifythechronologicalorderinwhichinstructionsofconcurrenttransactionsareexecutedascheduleforasetoftransactionsmustconsistofallinstructionsofthosetransactionsmustpreservetheorderinwhichtheinstructionsappearineachindividualtransaction.AtransactionthatsuccessfullycompletesitsexecutionwillhaveacommitinstructionsasthelaststatementbydefaulttransactionassumedtoexecutecommitinstructionasitslaststepAtransactionthatfailstosuccessfullycompleteitsexecutionwillhaveanabortinstructionasthelaststatement Schedule1LetT1transfer$50fromAtoB,andT2transfer10%ofthebalancefromAtoB.AserialscheduleinwhichT1isfollowedbyT2: Schedule2AserialschedulewhereT2isfollowedbyT1 Schedule3LetT1andT2bethetransactionsdefinedpreviously.Thefollowingscheduleisnotaserialschedule,butitisequivalenttoSchedule1.InSchedules1,2and3,thesumA+Bispreserved. Schedule4Thefollowingconcurrentscheduledoesnotpreservethevalueof(A+B). SerializabilityBasicAssumption–Eachtransactionpreservesdatabaseconsistency.Thusserialexecutionofasetoftransactionspreservesdatabaseconsistency.A(possiblyconcurrent)scheduleisserializableifitisequivalenttoaserialschedule.Differentformsofscheduleequivalencegiverisetothenotionsof:1.conflictserializability2.viewserializability SimplifiedviewoftransactionsWeignoreoperationsotherthanreadandwriteinstructionsWeassumethattransactionsmayperformarbitrarycomputationsondatainlocalbuffersinbetweenreadsandwrites.Oursimplifiedschedulesconsistofonlyreadandwriteinstructions. ConflictingInstructionsInstructionsliandljoftransactionsTiandTjrespectively,conflictifandonlyifthereexistssomeitemQaccessedbybothliandlj,andatleastoneoftheseinstructionswroteQ.1.li=read(Q),lj=read(Q).liandljdon’tconflict.2.li=read(Q),lj=write(Q).Theyconflict.3.li=write(Q),lj=read(Q).Theyconflict4.li=write(Q),lj=write(Q).TheyconflictIntuitively,aconflictbetweenliandljforcesa(logical)temporalorderbetweenthem.Ifliandljareconsecutiveinascheduleandtheydonotconflict,theirresultswouldremainthesameeveniftheyhadbeeninterchangedintheschedule. ConflictSerializabilityIfascheduleScanbetransformedintoascheduleS´byaseriesofswapsofnon-conflictinginstructions,wesaythatSandS´areconflictequivalent.WesaythatascheduleSisconflictserializableifitisconflictequivalenttoaserialschedule ConflictSerializability(Cont.)Schedule3canbetransformedintoSchedule6,aserialschedulewhereT2followsT1,byseriesofswapsofnon-conflictinginstructions.ThereforeSchedule3isconflictserializable.Schedule3Schedule6 ConflictSerializability(Cont.)Exampleofaschedulethatisnotconflictserializable:Weareunabletoswapinstructionsintheabovescheduletoobtaineithertheserialschedule,ortheserialschedule. ViewSerializabilityLetSandS´betwoscheduleswiththesamesetoftransactions.SandS´areviewequivalentifthefollowingthreeconditionsaremet,foreachdataitemQ,IfinscheduleS,transactionTireadstheinitialvalueofQ,theninscheduleS’alsotransactionTimustreadtheinitialvalueofQ.IfinscheduleStransactionTiexecutesread(Q),andthatvaluewasproducedbytransactionTj(ifany),theninscheduleS’alsotransactionTimustreadthevalueofQthatwasproducedbythesamewrite(Q)operationoftransactionTj.Thetransaction(ifany)thatperformsthefinalwrite(Q)operationinscheduleSmustalsoperformthefinalwrite(Q)operationinscheduleS’.Ascanbeseen,viewequivalenceisalsobasedpurelyonreadsandwritesalone. ViewSerializability(Cont.)AscheduleSisviewserializableifitisviewequivalenttoaserialschedule.Everyconflictserializablescheduleisalsoviewserializable.Belowisaschedulewhichisview-serializablebutnotconflictserializable.Whatserialscheduleisaboveequivalentto?Everyviewserializableschedulethatisnotconflictserializablehasblindwrites. OtherNotionsofSerializabilityTheschedulebelowproducessameoutcomeastheserialschedule,yetisnotconflictequivalentorviewequivalenttoit.Determiningsuchequivalencerequiresanalysisofoperationsotherthanreadandwrite. TestingforSerializabilityConsidersomescheduleofasetoftransactionsT1,T2,...,TnPrecedencegraph—adirectgraphwheretheverticesarethetransactions(names).WedrawanarcfromTitoTjifthetwotransactionconflict,andTiaccessedthedataitemonwhichtheconflictaroseearlier.Wemaylabelthearcbytheitemthatwasaccessed.Example1 TestforConflictSerializabilityAscheduleisconflictserializableifandonlyifitsprecedencegraphisacyclic.Cycle-detectionalgorithmsexistwhichtakeordern2time,wherenisthenumberofverticesinthegraph.(Betteralgorithmstakeordern+ewhereeisthenumberofedges.)Ifprecedencegraphisacyclic,theserializabilityordercanbeobtainedbyatopologicalsortingofthegraph.Thisisalinearorderconsistentwiththepartialorderofthegraph.Forexample,aserializabilityorderforScheduleAwouldbeT5T1T3T2T4Arethereothers? TestforViewSerializabilityTheprecedencegraphtestforconflictserializabilitycannotbeuseddirectlytotestforviewserializability.Extensiontotestforviewserializabilityhascostexponentialinthesizeoftheprecedencegraph.TheproblemofcheckingifascheduleisviewserializablefallsintheclassofNP-completeproblems.Thusexistenceofanefficientalgorithmisextremelyunlikely.Howeverpracticalalgorithmsthatjustchecksomesufficientconditionsforviewserializabilitycanstillbeused. RecoverableSchedulesRecoverableschedule—ifatransactionTjreadsadataitempreviouslywrittenbyatransactionTi,thenthecommitoperationofTiappearsbeforethecommitoperationofTj.Thefollowingschedule(Schedule11)isnotrecoverableifT9commitsimmediatelyafterthereadIfT8shouldabort,T9wouldhaveread(andpossiblyshowntotheuser)aninconsistentdatabasestate.Hence,databasemustensurethatschedulesarerecoverable.Needtoaddresstheeffectoftransactionfailuresonconcurrentlyrunningtransactions. CascadingRollbacksCascadingrollback–asingletransactionfailureleadstoaseriesoftransactionrollbacks.Considerthefollowingschedulewherenoneofthetransactionshasyetcommitted(sothescheduleisrecoverable)IfT10fails,T11andT12mustalsoberolledback.Canleadtotheundoingofasignificantamountofwork CascadelessSchedulesCascadelessschedules—cascadingrollbackscannotoccur;foreachpairoftransactionsTiandTjsuchthatTjreadsadataitempreviouslywrittenbyTi,thecommitoperationofTiappearsbeforethereadoperationofTj.EverycascadelessscheduleisalsorecoverableItisdesirabletorestricttheschedulestothosethatarecascadeless ConcurrencyControlAdatabasemustprovideamechanismthatwillensurethatallpossibleschedulesareeitherconflictorviewserializable,andarerecoverableandpreferablycascadelessApolicyinwhichonlyonetransactioncanexecuteatatimegeneratesserialschedules,butprovidesapoordegreeofconcurrencyAreserialschedulesrecoverable/cascadeless?Testingascheduleforserializabilityafterithasexecutedisalittletoolate!Goal–todevelopconcurrencycontrolprotocolsthatwillassureserializability. ConcurrencyControl(Cont.)Schedulesmustbeconflictorviewserializable,andrecoverable,forthesakeofdatabaseconsistency,andpreferablycascadeless.Apolicyinwhichonlyonetransactioncanexecuteatatimegeneratesserialschedules,butprovidesapoordegreeofconcurrency.Concurrency-controlschemestradeoffbetweentheamountofconcurrencytheyallowandtheamountofoverheadthattheyincur.Someschemesallowonlyconflict-serializableschedulestobegenerated,whileothersallowview-serializableschedulesthatarenotconflict-serializable. ConcurrencyControlvs.SerializabilityTestsConcurrency-controlprotocolsallowconcurrentschedules,butensurethattheschedulesareconflict/viewserializable,andarerecoverableandcascadeless.ConcurrencycontrolprotocolsgenerallydonotexaminetheprecedencegraphasitisbeingcreatedInsteadaprotocolimposesadisciplinethatavoidsnonseralizableschedules.WestudysuchprotocolsinChapter16.Differentconcurrencycontrolprotocolsprovidedifferenttradeoffsbetweentheamountofconcurrencytheyallowandtheamountofoverheadthattheyincur.Testsforserializabilityhelpusunderstandwhyaconcurrencycontrolprotocoliscorrect. WeakLevelsofConsistencySomeapplicationsarewillingtolivewithweaklevelsofconsistency,allowingschedulesthatarenotserializableE.g.aread-onlytransactionthatwantstogetanapproximatetotalbalanceofallaccountsE.g.databasestatisticscomputedforqueryoptimizationcanbeapproximate(why?)SuchtransactionsneednotbeserializablewithrespecttoothertransactionsTradeoffaccuracyforperformance LevelsofConsistencyinSQL-92Serializable—defaultRepeatableread—onlycommittedrecordstoberead,repeatedreadsofsamerecordmustreturnsamevalue.However,atransactionmaynotbeserializable–itmayfindsomerecordsinsertedbyatransactionbutnotfindothers.Readcommitted—onlycommittedrecordscanberead,butsuccessivereadsofrecordmayreturndifferent(butcommitted)values.Readuncommitted—evenuncommittedrecordsmayberead.LowerdegreesofconsistencyusefulforgatheringapproximateinformationaboutthedatabaseWarning:somedatabasesystemsdonotensureserializableschedulesbydefaultE.g.OracleandPostgreSQLbydefaultsupportalevelofconsistencycalledsnapshotisolation(notpartoftheSQLstandard) TransactionDefinitioninSQLDatamanipulationlanguagemustincludeaconstructforspecifyingthesetofactionsthatcompriseatransaction.InSQL,atransactionbeginsimplicitly.AtransactioninSQLendsby:Commitworkcommitscurrenttransactionandbeginsanewone.Rollbackworkcausescurrenttransactiontoabort.Inalmostalldatabasesystems,bydefault,everySQLstatementalsocommitsimplicitlyifitexecutessuccessfullyImplicitcommitcanbeturnedoffbyadatabasedirectiveE.g.inJDBC,connection.setAutoCommit(false); EndofChapter14 Figure14.01 Figure14.02 Figure14.03 Figure14.04 Figure14.05 Figure14.06 Figure14.07 Figure14.08 Figure14.09 Figure14.10 Figure14.11 Figure14.12 Figure14.13 Figure14.14 Figure14.15 Figure14.16'