1Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1Concurrency ControlDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 2Goal of Concurrency Control Transactions should be executed so that it is as though they executed in some serial order Also called Isolation or Serializability Weaker variants also possible Lower “degrees of isolation”Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 3Example Consider two transactions (Xacts):T1: BEGIN A=A+100, B=B-100 ENDT2: BEGIN A=1.06*A, B=1.06*B END T1 transfers $100 from B’s account to A’s account T2 credits both accounts with 6% interest If submitted concurrently, net effect should be equivalent to Xacts running in some serial order No guarantee that T1 “logically” occurs before T2 (or vice-versa) – but one of them is trueDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 4Solution 11) Get exclusive lock on entire database2) Execute transaction3) Release exclusive lock Similar to “critical sections” in operating systems Serializability guaranteed because execution is serial! Problems? Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 5Solution 21) Get exclusive locks on accessed data items2) Execute transaction3) Release exclusive locks Greater concurrency Problems? Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 6Solution 31) Get exclusive locks on data items that are modified; get shared locks on data items that are only read2) Execute transaction3) Release all locks Greater concurrency Conservative Strict Two Phase Locking (2PL) Problems? SXS XYes NoNoNo2Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 7Solution 41) Get exclusive locks on data items that are modified and get shared locks on data items that are read2) Execute transaction and release locks on objects no longer needed during execution Greater concurrency Conservative Two Phase Locking (2PL) Problems? Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 8Solution 51) Get exclusive locks on data items that are modified and get shared locks on data items that are read, but do this during execution of transaction (as needed)2) Release all locks Greater concurrency Strict Two Phase Locking (2PL) Problems? Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 9Solution 61) Get exclusive locks on data items that are modified and get shared locks on data items that are read, but do this during execution of transaction (as needed)2) Release locks on objects no longer needed during execution of transaction3) Cannot acquire locks once any lock has been released Hence two-phase (acquiring phase and releasing phase) Greater concurrency Two Phase Locking (2PL) Problems? Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 10Summary of Alternatives Conservative Strict 2PL No deadlocks, no cascading aborts But need to know objects a priori, when to release locks Conservative 2PL No deadlocks, more concurrency than Conservative Strict 2PL But need to know objects a priori, when to release locks, cascadingaborts Strict 2PL No cascading aborts, no need to know objects a priori or when torelease locks, more concurrency than Conservative Strict 2PL But deadlocks 2PL Most concurrency, no need to know object a priori But need to know when to release locks, cascading aborts, deadlocksDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 11Method of Choice Strict 2PL No cascading aborts, no need to know objects a priori or when torelease locks, more concurrency than Conservative Strict 2PL But deadlocks  Reason for choice Cannot know objects a priori, so no Conservative options Thus only 2PL and Strict 2PL left 2PL needs to know when to release locks (main problem)• Also has cascading aborts Hence Strict 2PL Implication Need to deal with deadlocks!Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 12Lock Management Lock and unlock requests are handled by the lock manager Lock table entry: Number of transactions currently holding a lock Type of lock held (shared or exclusive) Pointer to queue of lock requests Locking and unlocking have to be atomic operations Lock upgrade: transaction that holds a shared lock can be upgraded to hold an exclusive lock3Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 13Outline Formal definition of serializability Deadlock prevention and detection Advanced locking techniques Lower degrees of isolation Concurrency control for index structuresDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 14Example Consider a possible interleaving (schedule):T1: A=A+100, B=B-100 T2: A=1.06*A, B=1.06*B This is OK. But what about:T1: A=A+100, B=B-100 T2: A=1.06*A, B=1.06*B The DBMS’s view of the second schedule:T1: R(A), W(A), R(B), W(B)T2: R(A), W(A), R(B), W(B)Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 15Scheduling Transactions Serial schedule: Schedule that does not interleave the actions of different transactions. Equivalent schedules: For any database state The effect (on the set of objects in the database) of executing the schedules is the same The values read by transactions is the same in the schedules• Assume no knowledge of transaction logic Serializable schedule: A schedule that is equivalent to some serial execution of the transactions.(Note: If each transaction preserves consistency, every serializable schedule preserves consistency. )Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 16Anomalies with Interleaved Execution Reading Uncommitted Data (WR Conflicts, “dirty reads”): Unrepeatable Reads (RW Conflicts):T1: R(A), W(A), R(B), W(B), AbortT2: R(A), W(A), CT1: R(A), R(A), W(A), CT2: R(A), W(A), CDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 17Anomalies (Continued) Overwriting Uncommitted Data (WW Conflicts):T1: W(A), W(B), CT2: W(A), W(B), CDatabase Management Systems 3ed, R. Ramakrishnan and J. Gehrke 18Conflict Serializable Schedules Two schedules are conflict equivalent if: Involve the same actions of the same transactions Every pair of conflicting actions is ordered the same way Schedule S is conflict serializable if S is conflict