Database Security Lecture 03 PDF

Database Security LECTURE (3) TWO PHASE LOCKING PROTOCOL DR.MURTADA MALIK ADAM ELHAJ ASSISTANT PROFESSOR – IT DEPARTMENT Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025 ...

Database Security LECTURE (3) TWO PHASE LOCKING PROTOCOL DR.MURTADA MALIK ADAM ELHAJ ASSISTANT PROFESSOR – IT DEPARTMENT Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Lecture Objectives 2  Locking Technique.  Locking Technique Basic Rules.  Locking Technique Examples.  Locking Technique in Centralized Database.  2PL & S2PL in Centralized Database.  Solving Some CC Problem By 2PL.  Locking problems in Centralized Database.  Locking Technique in Distributed Database.  C2PL,PC2PL,D2PL,M2PL in Distributed Database.  Locking Problems in Distributed Database. Dr.Murtada-Two Phase Locking protocol- lectrue 1 January 2025 03  Locking Technique 3 Transaction uses locks to deny access to other transactions and so prevent incorrect updates.  Most widely used approach to ensure serializability.  Generally, a transaction must claim a shared (read) or exclusive (write) lock on a data item before read or write.  Lock prevents another transaction from modifying item or even reading it, in the case of a write lock. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique- Basic Rules 4  If transaction has shared lock on item, can read but not update item.  If transaction has exclusive lock on item, can both read and update item.  Reads cannot conflict, so more than one transaction can hold shared locks simultaneously on same item.  Exclusive lock gives transaction exclusive access to that item. Dr.Murtada-Two Phase Locking protocol- lectrue 03 1 January 2025  Locking Technique- Basic Rules 5  Some systems allow transaction to upgrade read lock to an exclusive lock, or downgrade exclusive lock to a shared lock. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique- Examples 6 Incorrect Locking Schedule:  For two transactions above, a valid schedule using these rules is: S = {write_lock(T9, balx), read(T9, balx), write(T9, balx), unlock(T9, balx), write_lock(T10, balx), read(T10, balx), write(T10, balx), unlock(T10, balx), write_lock(T10, baly), read(T10, baly), write(T10, baly), unlock(T10, baly), commit(T10), write_lock(T9, baly), read(T9, baly), write(T9, baly), unlock(T9, baly), commit(T9) } Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique- Examples 7 Incorrect Locking Schedule:  If at start, balx = 100, baly = 400, result should be:  balx = 220, baly = 330, if T9 executes before T10, or  balx = 210, baly = 340, if T10 executes before T9.  However, result gives balx = 220 and baly = 340.  S is not a serializable schedule. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique- Examples 8 Incorrect Locking Schedule:  Problem is that transactions release locks too soon, resulting in loss of total isolation and atomicity.  To guarantee serializability, need an additional protocol concerning the positioning of lock and unlock operations in every transaction. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique in Centralized Database 9 2PL(Relaxed S2PL) S2PL Dr.Murtada-Two Phase Locking protocol- lectrue 1 January 2025 03  Two-Phase Locking (2PL) in centralized DB 10 Transaction follows 2PL protocol if all locking operations precede first unlock operation in the transaction.  Two phases for transaction:  Growing phase - acquires all locks but cannot release any locks.  Shrinking phase - releases locks but cannot acquire any new locks. Dr.Murtada-Two Phase Locking protocol- lectrue 1 January 2025 03  Two-Phase Locking (2PL) in centralized DB 11 Lock-po int Number of loc ks Locks Locks released acquired Transactio n Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Solving Some CC Problem By 2PL 12  Preventing Lost Update Problem : Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Solving Some CC Problem By 2PL 13  Preventing Uncommitted Dependency Problem: Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Solving Some CC Problem By 2PL 14  Preventing Inconsistent Analysis Problem : Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL Problem: Cascading Rollback 15  If every transaction in a schedule follows 2PL, schedule is serializable.  However, problems can occur with interpretation of when locks can be released. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL Problem: Cascading Rollback 16 Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL Problem: Cascading Rollback 17  Transactions conform to 2PL.  T14 aborts.  Since T15 is dependent on T14, T15 must also be rolled back. Since T16 is dependent on T15, it too must be rolled back.  This is called cascading rollback.  To prevent this with 2PL, leave release of all locks until end of transaction(S2PL) Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Strict 2 Phase Locking (S2PL) in centralized DB 18 Rules: Growing phase:  “A txn that has to read/write a data object first has to request a read/write lock on it.” Non - Shrinking phase:  “Txn releases all locks only when it completes.” Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Strict 2 Phase Locking (S2PL) in centralized DB 19 Lock-point Locks held till trans action completion Number of locks Locks acquired Locked data items used Transaction Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL & S2PL in centralized DB Examples 20 Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL & S2PL in centralized DB Differences 21  2PL Cascading aborts Conflict serializable schedules (not all) High concurrency  S2PL No cascading aborts Serializable schedules Low concurrency Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL with Index Structures in centralized DB 22  Could treat each page of index as a data item and apply 2PL.  However, as indexes will be frequently accessed, particularly higher levels, this may lead to high lock contention.  Can make two observations about index traversal:  Search path starts from root and moves down to leaf nodes but search never moves back up tree. Thus, once a lower-level node has been accessed, higher-level nodes in that path will not be used again. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL with Index Structures in centralized DB 23  When new index value (key and pointer) is being inserted into a leaf node, then if node is not full, insertion will not cause changes to higher-level nodes.  Suggests only have to exclusively lock leaf node in such a case, and only exclusively lock higher-level nodes if node is full and has to be split. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  2PL with Index Structures in centralized DB 24  Thus, can derive following locking strategy:  For searches, obtain shared locks on nodes starting at root and proceeding downwards along required path. Release lock on node once lock has been obtained on the child node.  For insertions, conservative approach would be to obtain exclusive locks on all nodes as we descend tree to the leaf node to be modified.  For more optimistic approach, obtain shared locks on all nodes as we descend to leaf node to be modified, where obtain exclusive lock. If leaf node has to split, upgrade shared lock on parent to exclusive lock. If this node also has to split, continue to upgrade locks at next higher level. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking problem(Deadlock)in centralized DB 25 An impasse that may result when two (or more) transactions are each waiting for locks held by the other to be released. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking problem(Deadlock)in centralized DB 26  Only one way to break deadlock: abort one or more of the transactions.  Deadlock should be transparent to user, so DBMS should restart transaction(s).  Three general techniques for handling deadlock:  Timeouts.  Deadlock prevention.  Deadlock detection and recovery. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Technique in Centralized Database 27  Centralized Locking(C2PL).  Primary Copy 2PL(PC2PL).  Distributed 2PL(D2PL)  Majority Locking(M2PL). Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Centralized Locking (C2PL) in Distributed DB 28  Single site that maintains all locking information.  One lock manager for whole of DDBMS.  Local transaction managers involved in global transaction request and release locks from lock manager.  Or transaction coordinator can make all locking requests on behalf of local transaction managers.  Advantage - easy to implement.  Disadvantages - bottlenecks and lower reliability. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Centralized Locking (C2PL) in Distributed DB 29 User application User application TM TM Replica control protocol LM C2PL DP DP Local data Local data Site#1 Site#2 Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Primary copy Locking (PC2PL) in Distributed DB 30  Lock managers distributed to a number of sites.  Each lock manager responsible for managing locks for set of data items.  For replicated data item, one copy is chosen as primary copy, others are slave copies  Only need to write-lock primary copy of data item that is to be updated.  Once primary copy has been updated, change can be propagated to slaves. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Primary copy Locking (PC2PL) in Distributed DB 31  Disadvantages - deadlock handling is more complex; still a degree of centralization in system.  Advantages - lower communication costs and better performance than centralized 2PL. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Distributed Locking (D2PL) in Distributed DB 32  Lock managers distributed to every site.  Each lock manager responsible for locks for data at that site.  If data not replicated, equivalent to primary copy 2PL.  Otherwise, implements a Read-One-Write-All (ROWA) replica control protocol. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Distributed Locking (D2PL) in Distributed DB 33  Using ROWA protocol:  Any copy of replicated item can be used for read.  All copies must be write-locked before item can be updated.  Disadvantages - deadlock handling more complex; communication costs higher than primary copy 2PL. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Distributed Locking (D2PL) in Distributed DB 34 User application User application TM TM Replica control protocol LM LM D2PL DP DP Local data Local data Site#1 Site#2 Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Locking Problem(Deadlock) in Distributed DB 36  Distributed deadlock is More complicated if lock management is not centralized.  Local Wait-for-Graph (LWFG) may not show existence of deadlock.  May need to create GWFG, union of all LWFGs.  Look at three schemes:  Centralized Deadlock Detection.  Hierarchical Deadlock Detection.  Distributed Deadlock Detection. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  References and Resources 37  Thomas Connolly,Carolyn Begg - database systems, A Practical Approach to Design,Implementation, and Management - 4th edition ,2005.  Rishikesh Mandvikar, lectures notes , engr.smu.edu , https://s2.smu.edu/~mhd/8330sp04/mandvikar.ppt , retrieved 05- aprial-2019 10:30 pm. Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025  Thank,,, 38 ANY QUESTIONS OR DISCUSSION? Dr.Murtada-Two Phase Locking protocol- lecture 03 1 January 2025