Transactions and Concurrency Control

By Mona Kumari|Updated : June 30th, 2021

A transaction is a single logical unit of work that accesses and possibly modifies the contents of a database. Transactions access data using read-and-write operations.

Download Formulas for GATE Electronics & Communication Engineering - Electronic Devices

  1. TRANSACTION
  2. Read Operation:
  • Read operation reads the data from the database and then stores it in the buffer in the main memory.
  • For example- Read(X)instruction will read the value of X from the database and will store it in the buffer in main memory.
  • Steps are:
  • Find the block that contains data item X.
  • Copy the block to a buffer in the main memory.
  • Copy item X from the buffer to the program variable named X.
  1. Write Operation:
  • Write operation writes the updated data value back to the database from the buffer.
  • For example- Write(X)will write the updated value of X from the buffer to the database.
  • Steps are:
  • Find address of block which contains data item X.
  • Copy disk block into a buffer in the main memory
  • Update data item X in main memory buffer.
  • Store the updated block from the buffer back to disk.

byjusexamprep

Download Formulas for GATE Electronics & Communication Engineering - Signals Systems

  1. ACID PROPERTIES
  • To ensure the consistency of database, certain properties are followed by all the transactions occurring in the system.
  • It is important to ensure that the database remains consistent before and after the transaction.
  • These properties are called as ACID Properties of a transaction.

                                                   byjusexamprep

Atomicity:

  • This property ensures that a transaction should execute all the operations, including commit or none of them, i.e. the transaction occurs completely or does not occur at all.
  • The Transaction Control Manager's responsibility is to ensure the atomicity of the transactions.

Consistency:

  • This means that integrity constraints must be maintained i.e. It ensures that the database remains consistent before and after the transaction.
  • The transaction must be logically correct, and the user should monitor correctness.
  • It is the responsibility of the DBMS and application programmer's responsibility to ensure the database's consistency.

Isolation:

  • The execution of one transaction is isolated from that of another transaction.
  • It ensures that the concurrent execution of transactions results in a system state that would be obtained if transactions were executed serially, i.e., one after the other.
  • The concurrency control manager's responsibility is to ensure isolation for all transactions.

Durability:

  • The changes applied to the database by a successfully committed transaction must persist in the database.
  • It also ensures that these changes exist permanently and are never lost, even if any failure occurs.
  • The recovery manager's responsibility is to ensure the durability of the database.

Download Formulas for GATE Electronics & Communication Engineering - Communication Systems

  1. SCHEDULE

The sequence indicates the chronological order in which instructions of concurrent transactions are executed.

byjusexamprep

3.1.   Strict Schedule:

  • All the transactions execute serially, one after the other i.e. after the commit of one transaction begins another transaction.
  • Every serial schedule result always preserves integrity.
  • When one transaction executes, no other transaction is allowed to execute.
  • Fewer users can use the database at a time.
  • The number of serial schedules possible with n transactions is n!

Example:

Transaction T1

Transaction T2

R(A)

 

W(A)

 

R(B)

 

W(B)

 

Commit

 

 

R(A)

 

W(B)

 

Commit

  • Transaction T1 executes first and after completion of T1, T2 is executed
  • So, this schedule is an example of a Serial Schedule.

3.2.   Concurrent Schedule:

  • Multiple transactions execute simultaneously.
  • Operations of all the transactions are interleaved or mixed with each other.
  • May cause inconsistency, so to maintain consistency transactions should satisfy the ACID property.

Example:

Transaction T1

Transaction T2

R(A)

 

W(B)

 

 

R(A)

R(B)

 

W(B)

 

Commit

 

 

R(B)

 

Commit

  • The operations of T1 and T2 are interleaved.
  • So, this schedule is an example of a Non-Serial Schedule.

Conflicts in Concurrent schedule:

The two operations become conflicting if all conditions satisfy:

  • Both belong to separate transactions.
  • They have the same data item.
  • They contain at least one write operation.
  1. Read-Write Conflict:

Ti

Tj

R(A)

W(A)

  1. Write-Read Conflict

Ti

Tj

 

W(A)

 

R(A)

→ uncommitted read

  1. Write-Write Conflict:

Ti

Tj

R(A)

W(A)

Concurrency Problems in DBMS

  • Dirty Read: Reading the data written by an uncommitted transaction is called a dirty read.

Transaction T1

Transaction T2

 

R(A)

 

 

W(B)

 

 

.

.

.

.

.

.

.

.

R(A)

//Dirty Read

W(A)

 

Commit

 

 

 

 

 

Failure

 

 

 

  • T2 reads the dirty value of A written by the uncommitted transaction T1.
  • T1 fails in later stages and roll backs.
  • Thus, the value that T2 read now stands to be incorrect.
  • Therefore, database becomes inconsistent.
  1. SERIALIZABILITY
  • It is the classical concurrency scheme. It ensures that a schedule for executing concurrent transactions is equivalent to one that executes the transactions serially in some order.
  • Some non-serial schedules may lead to inconsistency of the database.
  • Serializability is a concept that helps to identify which non-serial schedules are correct and will maintain the consistency of the database.

                    byjusexamprep

4.1.   Conflict Serializability:

  • A schedule is called conflict serializability if after swapping of non-conflicting operations, it can transform into a serial schedule.
  • The schedule will be a conflict serializable if it is conflict equivalent to a serial schedule.
  • Conflict serialisabiltiy: Instructions Ii and Ij of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both Ii and Ij, and at least one of these instructions wrote Q.

(i) Ii = read (Q), Ij = read (Q). Ii and Ij don’t conflict.

(ii) Ii = read (Q), Ij = write (Q). They conflict.

(iii) Ii = write (Q), Ij = read (Q). They conflict.

(iv) Ii = write (Q), Ij = write (Q). They conflict.

teps to check Conflict Serializable Schedule:

Schedule S is conflict serializable schedule iff precedence graph of schedule S is acyclic.

Step 1: List all the conflicting operations.

Step 2: For the precedence graph:

  • Draw an edge for each conflict pair such that if Xi(V) and Yj (V) forms a conflict pair then draw an edge from Ti to Tj, in which one of the V has to be a write operation.
  • This ensures that Tigets executed before Tj.

Step 3: Check for cycles in the graph. If there is no cycle, then conflict serializable otherwise not conflict serializable.

S : r1(A) w2(A) w2(B) r3(B) r3(C) w1(C) Test whether S is conflict serializable or not.

Sol. 

Here     

  r1 (A) – w2 (A)

  w2 (B) – r3 (B)

  r3 (C) – w1(C)

are the conflict pairs

                                                byjusexamprep

Conflict Equivalent:

Two schedules are conflict equivalent if one can be transformed to another by swapping non-conflicting operations.

Two schedules are said to be conflict equivalent if and only if:

  1. They contain the same set of the transaction.
  2. Conflict pairs must have the same precedence in both schedules.

Conflict Equal serial schedules are topological orders of precedence graph of schedule S.

Example: S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).

Non-serial schedule

 

Serial schedule

T1

T2

 

T1

T2

Read (A)

 

 

Read (A)

 

Write (A)

 

 

Write (A)

 

 

Read (A)

 

Read (B)

 

 

Write (A)

 

Write (B)

 

Read (B)

 

 

 

Read (A)

Write (B)

 

 

 

Write (A)

 

Read (B)

 

 

Read (B)

 

Write (B)

 

 

Write (B)

Schedule S1

 

Schedule S1

Schedule S2 is a serial schedule because, in this, all operations of T1 are performed before starting any operation of T2. Schedule S1 can be transformed into a serial schedule by swapping non-conflicting operations of S1.

After swapping of non-conflict operations, schedule S1 becomes:

T1

T2

Read(A)
Write(A)
Read(B)
Write(B)





Read(A)
Write(A)
Read(B)
Write(B)

Since, S1 is conflict serializable.

4.2.   View Serializability:

  • A schedule will view serializable if it is view equivalent to a serial schedule.
  • Conflict serializable which does not contain blind writes are view serializable.

View Equivalent Schedules:

Consider two schedules S1 and S2 each consisting of two transactions T1 and T2

Schedules S1 and S2 are called view equivalent if the following three conditions hold true for them-

  1. Initial readers must be same for all the data items:

For each data item X, if transaction Ti reads X from the database initially in schedule S1, then in schedule S2 also, Tmust perform the initial read of X from the database.

  1. The write-read sequence must be the same:

If transaction Ti reads a data item that has been updated by the transaction Tj in schedule S1, then in schedule S2 also, transaction Ti must read the same data item that has been updated by the transaction Tj

iii. Final writers must be same for all the data items:

NOTE:

·         Every conflict serializable schedule is also view serializable.

·         Every view serializable schedule that is not conflict serializable has blind writes.

For each data item X, if X has been updated at last by transaction Ti in schedule S1, then in schedule S2 also, X must be updated at last by transaction Ti.

byjusexamprep

  1. RECOVERABLE PROBLEMS

5.1.  Irrecoverable Schedule: It is not possible to roll back after the commitment of a transaction as the initial data is nowhere.

Example

                       byjusexamprep

5.2.  Recoverable Schedule: A schedule is recoverable if a transaction Tj reads a data items previously written by transaction Ti, the commit operation of Ti appears before the commit operation of Tj.

Example:

Ti

Tj

R(A)

 

W(A)

 

R(A)

Commit

W(B)

 

Commit

5.3.  Cascadeless Recoverable Schedule: For each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti the commit operation of Ti appears before the read operation of Tj. Every cascadeless schedule is also recoverable.

Example:

Ti

Tj

R(A)

 

W(A)

 

 

Commit

 

 

R(A)

 

Commit

Cascading roll back: A single transaction failure leads to a series of transaction rollbacks.

5.4.  Strict Recoverable Schedule: If transaction Ti updates the data item A, any other transaction Tj not allowed to R(A) or W(A) until commit or roll back of Ti.

  1. CONCURRENCY CONTROL PROTOCOLS

It is the procedure in DBMS for managing simultaneous operations without conflicting with each another.

Different concurrency control protocols offer different benefits between the amount of concurrency they allow and the amount of overhead that they impose.

  • Lock-Based Protocols
  • Two Phase Locking Protocols
  • Timestamp-Based Protocols

6.1.   Lock Based Protocol

A lock is a data variable which is associated with a data item. This lock signifies that operations that can be performed on the data item. Locks help synchronize access to the database items by concurrent transactions.

  1. Binary Locks:
  • A Binary lock on a data item can either locked (1) or unlocked (0) states.
  • Locked Objects cannot be used by any other transaction.
  • Unlocked objects are open to all the transactions.
  • Every transaction requires a lock and unlock operation for each data item that is accessed.
  • Every transaction locks before use of data item and release the lock after performing the operation.
  1. Shared/Exclusive:

In this type of protocol, any transaction cannot read or write data until it acquires an appropriate lock on it. There are two types of lock:

  • Shared lock(S):

o It is also known as a Read-only lock. In a shared lock, the data item can only read by the transaction.

o It can be shared between the transactions because when the transaction holds a lock, then it can't update the data on the data item.

  • Exclusive lock(X):

o In the exclusive lock, the data item can be both reads as well as written by the transaction.

o This lock is exclusive, and in this lock, multiple transactions do not modify the same data simultaneously.

6.2.   Two Phase Locking:

  • Two-Phase locking protocol which is also known as a 2PL protocol.
  • In this type of locking protocol, the transaction should acquire a lock after it releases one of its locks.
  • There are two phases of 2PL:

Growing phase: In the growing phase, a new lock on the data item may be acquired by the transaction, but none can be released.

Shrinking phase: In the shrinking phase, existing lock held by the transaction may be released, but no new locks can be acquired.

  • In the first part, when the execution of the transaction starts, it seeks permission for the lock it requires.
  • In the second part, the transaction acquires all the locks. The third phase is started as soon as the transaction releases its first lock.
  • In the third phase, the transaction cannot demand any new locks. It only releases the acquired locks.

Problem in 2PL:

  • Irrecoverability
  • Deadlock
  • Starvation

Strict Two- Phase Locking:

  • Basic 2PL with all exclusive locks should be held until commit/roll back.
  • It ensures serializability strict recoverable.

Problem in 2PL:

  • Starvation
  • Irrecoverability

6.3.   Time-Stamp Protocol:

  • This protocol ensures that every conflicting read and write operations are executed in timestamp order.
  • The priority of the older transaction is higher that's why it executes first. To determine the timestamp of the transaction, this protocol uses system time or logical counter.
  • The lock-based protocol is used to manage the order between conflicting pairs among transactions at the execution time. But Timestamp based protocols start working as soon as a transaction is created.

Basic Timestamp ordering protocol works as follows:

Let,

TS(Ti) denotes the timestamp of the transaction Ti.

R_TS(X) denotes the Read time-stamp of data-item X.

W_TS(X) denotes the Write time-stamp of data-item X.

  1. Check the following condition whenever a transaction Ti issues a Read (X)operation:
  • If W_TS(X) >TS(Ti) then the operation is rejected.
  • If W_TS(X) <= TS(Ti) then the operation is executed.
  • Timestamps of all the data items are updated.
  1. Check the following condition whenever a transaction Ti issues a Write(X)operation:
  • If TS(Ti) < R_TS(X) then the operation is rejected.
  • If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled back otherwise the operation is executed.

Thomas Write Rule Stamp Ordering Protocol

  1. Transaction T issues R(A) option:

(a) If WTS (A) > TS (T) then roll back T

(b) Otherwise execute successfully.

Set RTS (A) = max {TS (T), RTS (A)}

  1. Transaction T issues W (A) operation:

(a) If RTS (A) > TS (T) then roll back T.

(b) If WTS (A) > TS (T) then ignore W(A) and continue execution of trans T.

Strict Time Stamp Ordering Protocol

A transaction T2 that issues a R(A) or W(A) such that TS(T2) > WTS (X) has its read write option delayed until the transaction T1 that write the value X has committed or rolled back.

6.4.   Wait Die Protocol

  • Write the transaction in ascending order of time stamp values.
  • If T1 required resource that is hold by T2, T1 wait for T2 to unlock.
  • If T2 required resource that is hold by T1, then roll back T2 and restart with same time stamp value.

6.5.   Wound Wait Protocol

  • Write the transaction in ascending order of TS values.
  • If T1 required resource that is hold by T2 then roll back T2 and restart with same time stamp value.
  • If T2 required resource that is hold by T1 than T2 wait for T1 to unlock.
  • Both wait die and wound wait protocols may have starvation.

Candidates can practice 150+Mock Tests with BYJU'S Exam Prep Test Series for exams like GATE, ESE, NIELIT from the following link:

Click Here to Avail Electronics Engineering Test Series (150+ Mock Tests)

Get unlimited access to 24+ structured Live Courses all 150+ mock tests to boost your GATE 2021 Preparation with Online Classroom Program:

Click here to avail Online Classroom Program for Electronics Engineering

Thanks

Sahi Prep Hai To Life Set Hai.

 
Download BYJU'S Exam Prep, Best gate exam app for Preparation

 

 

Comments

write a comment

Follow us for latest updates