protocols of concurrency control

This will tell about the three of the Protocols(Lock-Based Protocols, Timestamp-Based Protocols, Validation-Based Protocols) of Concurrency Control used in the database management system.

1. CONCURRENCY CONTROL DATABASE MANAGEMENT SYSTEM Mohit Dadu

2. Concurrency Control CONCURRENCY : In computer science, concurrency  is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. Concurrency control is the process of managing simultaneous operations on the database without having them interfere with one another. Concurrent access is relatively easy if all users are only reading data, as there is no way that they can interfere with one another.

3. Concurrency Control Purpose of Concurrency Control To enforce Isolation (through mutual exclusion) among conflicting transactions. To preserve database consistency through consistency preserving execution of transactions. To resolve read-write and write-write conflicts. Example: In concurrent execution environment if T1 conflicts with T2 over a data item A, then the existing concurrency control decides if T1 or T2 should get the A and if the other transaction is rolled-back or waits.

4. Concurrency Control Simultaneous execution of transactions over a shared database can create several data integrity and consistency problems: Lost Updates. Uncommitted Data. Inconsistent retrievals. Why we need Concurrency Control

5. Concurrency Control When we need Concurrency Control The amount of data is sufficiently great that at any given time only fraction of the data can be in primary memory & rest should be swapped from secondary memory as needed. Even if the entire database can be present in primary memory, there may be multiple processes.

6. Concurrency Control Lock-Based Protocols Timestamp-Based Protocols Validation-Based Protocols Multiple Granularity Deadlock Handling Insert and Delete Operations

7. Concurrency Control Lock-Based Protocols Timestamp-Based Protocols Validation-Based Protocols

8. Concurrency Control Timestamp-Based Protocols

9. This is the most commonly used concurrency protocol. This protocol uses e ither S ystem Time or Logical C ounter as a timestamp. Lock-based protocols manage the order between the conflicting pairs among transactions at the time of execution, whereas timestamp-based protocols start working as soon as a transaction is created . Timestamp-Based Protocol

10. Timestamp-Based Protocol Every transaction has a timestamp associated with it, and the ordering is determined by the age of the transaction. Every data item is given the latest read and write-timestamp. This lets the system know when the last ‘read and write’ operation was performed on the data item. Timestamp based algorithm uses timestamp to serialize the execution of concurrent transactions.

11. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the timestamp values of the transactions . The timestamp of transaction T i  is denoted as TS(T i ) . Read time-stamp of data-item X is denoted by R-timestamp( X ). Write time-stamp of data-item X is denoted by W-timestamp( X ). Timestamp-Based Protocol

12. Timestamp-Based Protocol 1. Transaction T i issues a write_item (X ) operation : If TS( T i ) < R-timestamp( X ), then the value of X that T i is producing was needed previously, and the system assumed that that value would never be produced. Hence, the write operation is rejected, and T i is rolled back. If TS( T i ) < W-timestamp( X ) , then T i is attempting to write an obsolete value of X . Hence, this write operation is rejected, and T i is rolled back. Otherwise , the write operation is executed, and W-timestamp( X ) is set to TS( T i ).

13. Timestamp-Based Protocol If TS( T i )  W-timestamp( X ) , then T i needs to read a value of X that was already overwritten. Hence, the read operation is rejected , and T i is rolled back . If TS( T i )  W-timestamp( X ), then the read operation is executed , and R-timestamp( X ) is set to the maximum of R-timestamp( X ) and TS( T i ). 2. Transaction T issues a read_item (X) operation:

14. Timestamp-Based Protocol Advantages: – Schedules are serializable (like 2PL protocols) – No waiting for transaction, thus, no deadlocks ! • Disadvantages: -- Starvation is possible (if the same transaction is continually aborted and restarted )

15. Timestamp-Based Protocol Thomas’s Write Rule: If read_TS (X) > TS( T i ) then abort and roll-back T i and reject the operation. If write_TS (X) > TS( T i ), then just ignore the write operation and continue execution. This is because the most recent writes counts in case of two consecutive writes. If the conditions given in 1 and 2 above do not occur, then execute write_item (X) of T i and set write_TS (X) to TS( T i ).

16. Concurrency Control Validation-Based Protocols

17. Validation-Based Protocol Execution of transaction T i is done in three phases. 1. Read and execution phase : Transaction T i writes only to temporary local variables 2. Validation phase : Transaction T i performs a ``validation test'' to determine if local variables can be written without violating serializability . 3. Write phase : If T i is validated, the updates are applied to the database; otherwise, T i is rolled back. Also called as optimistic concurrency control since transaction executes fully in the hope that all will go well during validation

18. Validation-Based Protocol Each transaction T i has 3 timestamps Start ( T i ) : the time when T i started its execution Validation ( T i ): the time when T i entered its validation phase Finish ( T i ) : the time when T i finished its write phase Serializability order is determined by timestamp given at validation time, to increase concurrency. Thus TS ( T i ) is given the value of Validation ( T i ). This protocol is useful and gives greater degree of concurrency if probability of conflicts is low. That is because the serializability order is not pre-decided and relatively less transactions will have to be rolled back.

19. Validation-Based Protocol If for all T i with TS ( T i ) < TS ( T j ) either one of the following condition holds : finish ( T i ) < start ( T j ) start ( T j ) < finish ( T i ) < validation ( T j ) and the set of data items written by T i does not intersect with the set of data items read by T j . then validation succeeds and T j can be committed. Otherwise, validation fails and T j is aborted .

20. Validation-Based Protocol Justification : Either first condition is satisfied, and there is no overlapped execution, or second condition is satisfied and 1. the writes of T j do not affect reads of T i since they occur after T i has finished its reads. 2. the writes of T i do not affect reads of T j since T j does not read any item written by T i .

21. Validation-Based Protocol Example of schedule produced using validation T 14 T 15 read ( B ) read ( B ) B:- B-50 read ( A ) A:- A+50 read ( A ) ( validate ) display ( A + B ) ( validate ) write ( B ) write ( A )

22. Thank you