数据库管理系统概述英文版课件：16 Timestamp Protocol

1、COMP231Timestamp ProtocolPrepared by Raymond WongPresented by Raymond WongCOMP2311OutlineTimestamp Concurrency Control2PL versus TimestampingCOMP2312Concurrency ControlConcurrency ControlObjective:Given a non-serial schedule, We want to determine the serialization orderTwo Phase LockingWe can determ

2、ine the serialization order according to the ordering that transactions obtain the locks (i.e., during the execution of transactions)Timestamp Ordering ProtocolWe can determine the serialization order according to the pre-defined information of transactions, specifically timestamps (i.e., before the

3、 execution of transactions)Timestamp of TransactionsTimestamp (TS) of a transactionCan be assigned by a centralized serverE.g.,TS(T1) = 5TS(T2) = 6Serialization order = T1 T2T1: W(A) R(B)T2: R(A) W(A)COMP2314Timestamp of ObjectsTimestamp (TS) of an objectRead Timestamp (RTS) of Object OThe largest t

4、imestamp of any transaction that executed R(O) successfullyE.g., RTS(O) = 10Write Timestamp (WTS) of Object OThe largest timestamp of any transaction that executed W(O) successfullyE.g., WTS(O) = 9COMP2315Timestamp Concurrency ControlTimestamp Ordering ProtocolIdea: Consider that action ai of transa

5、ction Ti conflicts with action aj of transaction TjWe should guarantee thatIf TS(Ti) TS(Tj), ai must occur before aj. Else restart the violating transactions.Timestamp Concurrency ControlWhen Transaction T wants to read Object OWhen Transaction T wants to write Object OExampleCOMP2317When Transactio

6、n T wants to read Object OIf TS(T) = WTS(O):The read operation of T is accepted and executed.Set RTS(O) to max(RTS(O), TS(T)In this case, restart T with a new, larger TS. (If it is restarted with the same TS, T will fail again!)When Transaction T wants to read Object OTotherTT: R(O)Tother: W(O)ReadO

7、bjective:Serial schedule Tother T where Tother corresponds to the latesttransaction writing object OTS(Tother) = TS(T)WTS(O) = TS(T)COMP2319Timestamp Concurrency ControlWhen Transaction T wants to read Object OWhen Transaction T wants to write Object OExampleCOMP23110If TS(T) RTS(O), The value of O

8、that T is producing was needed previously and the system assumed that that value would never be produced.The write operation of T is rejected.If TS(T) = RTS(O) and TS(T) = WTS(O)The write operation of T is accepted and executed.Set WTS(O) to TS(T)When Transaction T wants to Write Object OWhen Transa

9、ction T wants to Write Object OTotherTT: W(O)Tother: R(O)ReadObjective:Serial schedule Tother T where Tother corresponds to the latesttransaction reading object OTS(Tother) = TS(T)RTS(O) = TS(T)TotherTT: W(O)Tother: W(O)Objective:Serial schedule Tother T where Tother corresponds to the latesttransac

10、tion writing object OTS(Tother) = TS(T)WTS(O) TS(T1)Thus, this schedule is NOT accepted by the timestampordering protocol.COMP23124Schedule 2 2PLT1: R(C) W(A)T2: R(A) W(B)E.g.4 Consider the following schedule.Is the schedule accepted by two-phaselocking (2PL) protocol?Yes. Why?COMP23125OutlineTimestamp Concurrency Control2PL versus TimestampingCOMP231262PL versus Ti