Tree Protocol B 1.Only exclusive locks are allowed. 2.The first lock by 7;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. 3.Data items may be unlocked at any time. 4.A data item that has been locked and unlocked by T;cannot subsequently be relocked by T; Database System Concepts -5th Edition,Oct 5,2006 16.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.17 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Tree Protocol 1. Only exclusive locks are allowed. 2. 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 . 3. Data items may be unlocked at any time. 4. 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 tree protocol,and vice versa. Database System Concepts-5th Edition,Oct 5,2006 16.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 16.18 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 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 tree protocol, and vice versa
Multiple Granularity Allow data items to be of various sizes and define a hierarchy of data granularities,where the small granularities are nested within larger ones Can be represented graphically as a tree(but don't confuse with tree- locking protocol) When a transaction locks a node in the tree explicitly,it implicitly locks all the node's descendents in the same mode. Granularity of locking (level in tree where locking is done): fine granularity (lower in tree):high concurrency,high locking overhead coarse granularity (higher in tree):low locking overhead,low concurrency Database System Concepts-5th Edition,Oct 5,2006 16.19 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.19 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Multiple Granularity Allow data items to be of various sizes and define a hierarchy of data granularities, where the small granularities are nested within larger ones Can be represented graphically as a tree (but don't confuse with treelocking protocol) When a transaction locks a node in the tree explicitly, it implicitly locks all the node's descendents in the same mode. Granularity of locking (level in tree where locking is done): fine granularity (lower in tree): high concurrency, high locking overhead coarse granularity (higher in tree): low locking overhead, low concurrency
Example of Granularity Hierarchy DB A2 名 《M 水 Cm The levels,starting from the coarsest (top)level are database area file record Database System Concepts -5th Edition,Oct 5,2006 16.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 16.20 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Example of Granularity Hierarchy The levels, starting from the coarsest (top) level are database area file record
Intention Lock Modes In addition to S and X lock modes,there are three additional lock modes with multiple granularity: intention-shared(IS):indicates explicit locking at a lower level of the tree but only with shared locks. intention-exclusive (IX):indicates explicit locking at a lower level with exclusive or shared locks shared and intention-exclusive(SIX):the subtree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks. intention locks allow a higher level node to be locked in S or X mode without having to check all descendent nodes. Database System Concepts-5th Edition,Oct 5,2006 16.21 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.21 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Intention Lock Modes In addition to S and X lock modes, there are three additional lock modes with multiple granularity: intention-shared (IS): indicates explicit locking at a lower level of the tree but only with shared locks. intention-exclusive (IX): indicates explicit locking at a lower level with exclusive or shared locks shared and intention-exclusive (SIX): the subtree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks. intention locks allow a higher level node to be locked in S or X mode without having to check all descendent nodes