Graph-Based Protocols Graph-based protocols are an alternative to two-phase locking Impose a partial ordering->on the set D={d,,d2,...,dh}of all data items. If d;>d,then any transaction accessing both d;and d;must access d before accessing d;. Implies that the set D may now be viewed as a directed acyclic graph, called a database graph. The tree-protocolis a simple kind of graph protocol. Database System Concepts-7th Edition 18.18 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 18.18 ©Silberschatz, Korth and Sudarshan th Edition Graph-Based Protocols ▪ Graph-based protocols are an alternative to two-phase locking ▪ Impose a partial ordering → on the set D = {d1 , d2 ,..., dh } of all data items. • If di → dj then any transaction accessing both di and dj must access di before accessing dj . • Implies that the set D may now be viewed as a directed acyclic graph, called a database graph. ▪ The tree-protocol is a simple kind of graph protocol
Tree Protocol Only exclusive locks are allowed. The first lock by T;may be on any data item.Subsequently,a data Q can be locked by 7;only if the parent of Q is currently locked by T. Data items may be unlocked at any time. A data item that has been locked and unlocked by 7;cannot subsequently be relocked by T; B E H Database System Concepts-7th Edition 18.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.19 ©Silberschatz, Korth and Sudarshan th Edition Tree Protocol ▪ Only exclusive locks are allowed. ▪ The first lock by Ti may be on any data item. Subsequently, a data Q can be locked by Ti only if the parent of Q is currently locked by Ti . ▪ Data items may be unlocked at any time. ▪ A data item that has been locked and unlocked by Ti cannot subsequently be relocked by Ti
Graph-Based Protocols (Cont.) The tree protocol ensures conflict serializability as well as freedom from deadlock. ■ 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 ■Drawbacks Protocol does not guarantee recoverability or cascade freedom Need to introduce commit dependencies to ensure recoverability Transactions may have to lock data items that they do not access. increased locking overhead,and additional waiting time potential decrease in concurrency Schedules not possible under two-phase locking are possible under the tree protocol,and vice versa. Database System Concepts-7th Edition 18.20 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 18.20 ©Silberschatz, Korth and Sudarshan th Edition Graph-Based Protocols (Cont.) ▪ The tree protocol ensures conflict serializability as well as freedom from deadlock. ▪ Unlocking may occur earlier in the tree-locking protocol than in the twophase locking protocol. • Shorter waiting times, and increase in concurrency • Protocol is deadlock-free, no rollbacks are required ▪ Drawbacks • Protocol does not guarantee recoverability or cascade freedom ▪ Need to introduce commit dependencies to ensure recoverability • Transactions may have to lock data items that they do not access. ▪ increased locking overhead, and additional waiting time ▪ potential decrease in concurrency ▪ Schedules not possible under two-phase locking are possible under the tree protocol, and vice versa
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. T3 Ta lock-X(B) read(B) B:=B-50 write(B) lock-S(4) read() lock-S(B) lock-X(4) Database System Concepts-7th Edition 18.21 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.21 ©Silberschatz, Korth and Sudarshan th Edition 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
Deadlock Handling Deadlock prevention protocols ensure that the system will neverenter into a deadlock state.Some prevention strategies: Require that each transaction locks all its data items before it begins execution (pre-declaration). 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). Database System Concepts-7th Edition 18.22 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.22 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Handling ▪ Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies: • Require that each transaction locks all its data items before it begins execution (pre-declaration). • 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)