北邮数据库课程讲义chapter13.ppt

Thomas’ Write Rule DataBase System Concepts Suppose that transaction Ti issues a read(Q) or write(Q) operation. Let Qk denote the version of Q whose write timestamp is the largest write timestamp less than or equal to TS(Ti). 1. If transaction Ti issues a read(Q), then the value returned is the content of version Qk. 2. If transaction Ti issues a write(Q): if TS(Ti) R-timestamp(Qk) then transaction Ti roll back Else if TS(Ti) = W-timestamp(Qk) overwrite the contents of Qk Else create a new version of Q DataBase System Concepts Reads always succeed; A write by Ti is rejected if some other transaction Tj that (in the serialization order defined by the timestamp values) should read Tis write, has already read a version created by a transaction older than Ti. DataBase System Concepts Deadlock Handling System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set,and none of the transactions can ever proceed with its normal executions. T1 T2 lock-X on X write (X) lock-X on Y write (X) wait for lock-X on X wait for lock-X on Y DataBase System Concepts Deadlock Prevention Strategies Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Require that each transaction locks all its data items before it begins execution (predeclaration). Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order (graph-based protocol). Timeout-Based Schemes : a transaction waits for a lock only for a specified amount of time. After that, the wait times out and the transaction is rolled back. wait-die scheme If TS(Ti) TS(Tj) then Ti Waits Else RollBack Ti Restart Ti with the same TS(Ti) Endif wound-wait scheme If TS(Ti) TS(Tj) then Ti Waits Else RollBack Tj Restart Tj with the same TS(Tj