Tree Protocol(Cont.) Unlocking may occur earlier in the tree-locking protocol than in the two-phase locking protocol x shorter waiting times, and increase in concurrency x protocol is deadlock-free, no rollbacks are required However, in the tree-locking protocol, a transaction may have to lock data items that it does not access x increased locking overhead, and additional waiting time x potential decrease in concurrency 标 Database System Concepts 3rd Edition 16.16 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.16 ©Silberschatz, Korth and Sudarshan rd Edition Tree Protocol(Cont.) Unlocking may occur earlier in the tree-locking protocol than in the two-phase locking protocol. shorter waiting times, and increase in concurrency protocol is deadlock-free, no rollbacks are required However, in the tree-locking protocol, a transaction may have to lock data items that it does not access. increased locking overhead, and additional waiting time potential decrease in concurrency
nestamp-Based Protocols(基于财间戳的协议) Each transaction is issued a timestamp when it enters the system. If an old transaction T, has time-stamp TS(Ti),a new transaction T; is assigned time-stamp TS(T) such that TS(Ti) <TS(T The protocol manages concurrent execution such that the time-stamps determine the serializability order In order to assure such behavior, the protocol maintains for each data Q two timestamp values xW-timestamp(Q)is the largest time-stamp of any transaction that executed write(Q)successfully x R-timestamp(Q)is the largest time-stamp of any transaction that executed read(Q) successfully Database System Concepts 3rd Edition 16.17 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.17 ©Silberschatz, Korth and Sudarshan rd Edition Timestamp-Based Protocols (基于时间戳的协议) Each transaction is issued a timestamp when it enters the system. If an old transaction Ti has time-stamp TS(Ti ), a new transaction Tj is assigned time-stamp TS(Tj ) such that TS(Ti ) <TS(Tj ). The protocol manages concurrent execution such that the time-stamps determine the serializability order. In order to assure such behavior, the protocol maintains for each data Q two timestamp values: W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q) successfully. R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q) successfully
Y Timestamp-Based Protocols (Cont) The timestamp ordering protocol ensures that any conflicting read and write operations are executed in timestamp order Suppose a transaction Ti issues a read(Q) If TS(TsW-timestamp(Q), then T; needs to read a value of Q that was already overwritten. Hence, the read operation is rejected, and T; is rolled back 2. If TS(Tiz W-timestamp(Q), then the read operation is executed, and R-timestamp(Q)is set to the maximum of R-timestamp(@)and TS(Ti) 标 Database System Concepts 3rd Edition 16.18 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.18 ©Silberschatz, Korth and Sudarshan rd Edition Timestamp-Based Protocols (Cont.) The timestamp ordering protocol ensures that any conflicting read and write operations are executed in timestamp order. Suppose a transaction Ti issues a read(Q) 1. If TS(Ti ) W-timestamp(Q), then Ti needs to read a value of Q that was already overwritten. Hence, the read operation is rejected, and Ti is rolled back. 2. If TS(Ti ) W-timestamp(Q), then the read operation is executed, and R-timestamp(Q) is set to the maximum of R-timestamp(Q) and TS(Ti )