Introduction to Database SystemsCSE 444Lecture 11 Transactions: concurrency control (part 1)CSE 444 - Summer 2010 1Outline• Serial and Serializable Schedules (18.1)• Conflict Serializability (18.2)• Locks (18.3)Next time:Next time:• Concurrency control by timestamps (18.8)•Concurrency control by validation (18.9)Concurrency control by validation (18.9)Some additional material not in the bookCSE 444 - Summer 2010 2The Problem• Multiple transactions running concurrentlyT1, T2, …• They read/write common elements A1, A2, …• How can we prevent unwanted interference ?p•The SCHEDULER is responsible for thateSC U s espo s b e o aCSE 444 - Summer 2010 3Some Famous Anomalies• What could go wrong if we didn’t have concurrency control?– Dirty reads– Inconsistent readsUtbld–Unrepeatable reads– Lost updatesMany other things can go wrong tooCSE 444 - Summer 2010 4Conflicts• Write-Read – WR • Read-Write –RW• Write-Write – WWCSE 444 - Summer 2010 5Dirty ReadsWrite-Read Conflict: WRITE(A) T1: WRITE(A) T: READ(A)T: ABORTT2: READ(A)T1: ABORTCSE 444 - Summer 2010 6Inconsistent ReadWrite-Read ConflictT1: A := 20; B := 20;T: WRITE(A)T1: WRITE(A) T2: READ(A);T: READ(B);T1: WRITE(B) T2: READ(B); CSE 444 - Summer 2010 7Unrepeatable ReadRead-Write Conflict()T2: READ(A);T1: WRITE(A)T: READ(A);T2: READ(A);CSE 444 - Summer 2010 8Lost UpdateWitWit C fli tTREAD(A)Write-Write ConflictT1: READ(A) T2: READ(A);T1: A := A+52T2:A:=A*1.3T1: WRITE(A) T2: A : A 1.3T: WRITE(A);T2: WRITE(A);CSE 444 - Summer 2010 9Schedules• Given multiple transactions–A schedule is a sequence of interleaved actions from all transactions–A serial schedule is one in which transactions appear one after the other in some order with noappear one after the other in some order with no overlapCSE 444 - Summer 2010 10ExampleT1 T2READ(A, t)READ(A, s)READ(A, t)READ(A, s)t := t+100 s := s*2WRITE(At)WRITE(A s)WRITE(A, t)WRITE(A,s)READ(B, t) READ(B,s)t := t+100s:=s*2t := t+100s := s2WRITE(B,t) WRITE(B,s)CSE 444 - Summer 2010 11A Serial ScheduleT1 T2READ(A, t)t := t+100WRITE(A, t)()READ(B, t)t := t+100WRITE(B,t)WRITE(B,t)READ(A,s)s := s*2WRITE(A s)WRITE(A,s)READ(B,s)s := s*2WRITE(B s)WRITE(B,s)CSE 444 - Summer 2010 12Serializable Schedule• A schedule is serializable if it is equivalent to a serial scheduleCSE 444 - Summer 2010 13A Serializable ScheduleT1 T2READ(A, t)t := t+100WRITE(A,t)WRITE(A, t)READ(A,s)s := s*2WRITE(A s)WRITE(A,s)READ(B, t)t := t+100WRITE(B t)WRITE(B,t)READ(B,s)s := s*2WRITE(B)Notice:Thii NOT il hdlWRITE(B,s)This is NOT a serial scheduleCSE 444 - Summer 2010 14A Non-Serializable ScheduleT1 T2READ(A, t)t := t+100WRITE(A,t)WRITE(A, t)READ(A,s)s := s*2WRITE(A s)WRITE(A,s)READ(B,s)s := s*2WRITE(B s)WRITE(B,s)READ(B, t)t := t+100WRITE(B t)WRITE(B,t)CSE 444 - Summer 2010 15Ignoring Details• Sometimes transactions’ actions can commute accidentally because of specific updatesS i li bilitididbl!–Serializabilityis undecidable!•Scheduler should notlookat transactiondetails•Scheduler should not look at transaction details•Assumeworst caseupdates•Assume worst case updates– Only care about reads r(A) and writes w(A)– Not the actual values involvedCSE 444 - Summer 2010 16NotationT1: r1(A); w1(A); r1(B); w1(B)T2: r2(A); w2(A); r2(B); w2(B)CSE 444 - Summer 2010 17Conflict SerializabilityConflicts:r(X)(Y)Ttib t tiTri(X); wi(Y)Two actions by same transaction Ti:wi(X); wj(X)Two writes by Ti, Tjto same elementwi(X); rj(X)Read/write by Ti, Tjto same element(X)(X)ri(X); wj(X)CSE 444 - Summer 2010 18Conflict SerializabilityA sched le isconflictseriali ableif it can be•A schedule is conflict serializableif it can be transformed into a serial schedule by a series ofswappingsof adjacent non-conflictingof swappingsof adjacent nonconflicting actionsExample:Example:r1(A); w1(A); r2(A); w2(A); r1(B); w1(B); r2(B); w2(B)r1(A); w1(A); r1(B); w1(B); r2(A); w2(A); r2(B); w2(B)r1(A); w1(A); r1(B); w1(B); r2(A); w2(A); r2(B); w2(B)CSE 444 - Summer 2010 19The Precedence Graph TestIs a schedule conflict-serializable?Simple test:• Build a graph of all transactions Ti• Edge from Tito Tjif Timakes an action that conflicts with one of Tjand comes first• The test: if the graph has no cycles, then it is conflictserializable!conflict serializable!CSE 444 - Summer 2010 20Example 1r(A); r(B); w(A); r(A); w(B); w(A); r(B); w(B)r2(A); r1(B); w2(A); r3(A); w1(B); w3(A); r2(B); w2(B)1 2 3ABThis schedule is conflictserializableThis schedule is conflict-serializableCSE 444 - Summer 2010 21Example 2r(A); r(B); w(A); r(B); r(A); w(B); w(A); w(B)r2(A); r1(B); w2(A); r2(B); r3(A); w1(B); w3(A); w2(B)1 2 3ABBThis schedule is NOT conflictserializableBThis schedule is NOT conflict-serializableCSE 444 - Summer 2010 22View Equivalence• A serializable schedule need not be conflict serializable, even under the “worst case update” assumption(X)(X)(Y)(Y)(Y)w1(X); w2(X); w2(Y); w1(Y); w3(Y);Lost writew1(X); w1(Y); w2(X); w2(Y); w3(Y);Equivalent but can’tswapEquivalent, but can t swap23CSE 444 - Summer 2010View EquivalentT1 T2 T3W1(X)T1 T2 T3W1(X)()W2(X)W2(Y)W1(X)W1(Y)CO1CO2W1(Y)CO1W2(X)W2(Y)CO2CO1W3(Y)CO3CO2W3(Y)CO3LostSerializable, but not conflict serializableView EquivalenceTwo schedules S, S’ are view equivalent if:• If T reads an initial value of A in S, then T also reads the initial value of A in S’• If T reads a value of A written by T’ in S, then T also reads a value of A written by T’ in S’• If T writes the final value of A in S, then it writes the final value of A in S’25CSE 444 - Summer 2010Schedules with AbortedSchedules with Aborted Transactions• When a transaction aborts, the recovery manager undoes its updates• But some of its updates may have affected other transactions !26CSE 444 - Summer 2010Schedules with AbortedSchedules with Aborted TransactionsT1 T2R(A)W(A)R(A)W(A)()R(B)W(B)CommitCommitAbortCannot abort T1 because cannot undo T2Recoverable Schedules• A schedule is recoverable if whenever a transaction T commits, all transactions who have written elements read by T have already committed28CSE 444 - Summer 2010Recoverable SchedulesT1 T2R(A)T1 T2R(A)W(A)R(A)W(A)R(A)W(A)R(A)W(A)()R(B)W(B)CommitW(A)R(B)W(B)AbortCommitAbortAbortCommit29Nonrecoverable RecoverableCSE 444 - Summer 2010Cascading Aborts• If a transaction T aborts, then we need to abort any other transaction T’ that has read an element written by T• A schedule is said to avoid cascading abortsif
View Full Document