Concurrency in Transaction

Concurrency

Concurrency means allowing more than one transaction to operate simultaneously on a same database.

Concurrency has many advantages

1. Reduces waiting time

2. Reduces the Response time.

3. Increases resource utilization

4. Increases Efficiency.

Problems

1.

If t2 reads a value of A from T1 and commits the value and afterwards T1 due to some circumstances rollbacks or change the value of A. Now T2 has committed the value that doesn’t exists in the system. This problem is known as dirty read Problem.

Solution:

If T2 commits the value after T1 has committed then we can solve the problem of dirty read.

2.

In this first T1 and T2 reads a value of A. Afterwards T1 changes the value of A. Now when T2 try to read the value it observes that the value of A has changed. As T2 was thinking that it’s the only transaction running in the system due to ACID properties. Now the system is in inconsistent state because T2 is in a dilemma of who has changed the value of A.

3.

In this T1 and T2 reads a value of A. Afterwards T1 deletes A and it’s no more in the system. Now when T2 try to read the value of A again. Then got an error that value doesn’t exist. Now T2 goes in the dilemma and thinks that if it is the only transaction running at that time (i.e. there is logical isolation).Then who has deleted the value of A.

4.

T2 comes and change the value of A. This type of write is known as blind write in which a transaction writes on a value without reading it.T2 now commits the value and now in the database the value has changed now T1 also commits the value that was changed by T2.Now the problem arises T1 has commit that value that it shouldn’t have. According to T1 it should have committed 11 but it has committed 50.So the system goes in the inconsistent state.

Conditions

If any system wants to be free from concurrency related problem or inconsistency that we observed above it should have schedules that are

1. Conflict Serializable.

2. View Serializable

3. Recoverable

4. Cascadeless

1. Conflict Serializability

If we can convert a non serial schedule into a serial schedule by swapping of non conflicting instructions then the schedule is conflict Serializable.

Conflicting Instructions

If there are two instructions belonging to different transactions and if they are operating on same data value and one of them is a write instruction then we cannot swap.

These instructions are conflicting instructions and cannot be swapped.

Another way to check whether a schedule is conflict Serializable of not we make an incoming edge between the transactions if there is a swap of conflicting instructions. And if the cycle exists then the schedule is not conflict Serializable

2. View Serializability

If a schedule is conflict Serializable than it is also view Serializable.

If any non serial schedule is view equivalent with a serial schedule than it is view Serializable

There should be a blind write if we are checking for view Serializability

For View Equivalent we consider the following.

1. Intial read should be same

2. Final write should be same

3. Intermediate reads should also be same

3. Recoverable and Cascadeless schedules

A schedule is recoverable and Cascadeless if it doesn’t consists of dirty reads.

Concurrency Control Techniques

Now we will generate protocols that guarantee to satisfy these properties especially like conflict Serializability

Protocols which are required to generate these schedules are

1. Time Stamping protocols.

2. Lock-Based Protocols

Time Stamping Protocols.

Basic idea of Time Stamping is to decide the order between the transactions before that enter into the system so that in case of conflict during execution we can resolve the conflict using ordering

The reason we call time-stamp not stamp because for stamping we use value of the system clock (as it will always be unique and cannot repeat itself)

Two ideas of Time Stamping

Timestamp with Transaction-With each transaction Ti we associate a time stamp denoted by T.S( Ti ),it is the value of the system clock when a transaction enters into the system so if a new transaction Tj enters after Ti then , T.S(Ti ) < T.S(Tj ) always unique, will remain fixed through the execution.

Also determine the Serializability order if T.S (Ti) <T.S (Tj) then system ensure that in the resultant Conflict Serializable Schedule Ti will execute first before Tj

Timestamp with data item: For each data item Q, protocols maintains two timestamps

W-timestamp (Q): is the largest time-stamp on any transaction that executed write (Q) successfully

R-timestamp (Q): is the largest time-stamp of any transaction that executed read (Q) successfully

Ti request for Read (Q)

Ti request for Write (Q)

Properties of Time Stamping Protocol

Thomas Write Rule

Modify time stamping protocol to make some improvements and may generate those schedules that are View Serializable but not conflict Serializable and provides better concurrency

Since transaction T2 is performing a blind write so it hardly matters whether Ti has changed the value of Q or not. So we can ignore the write operation that was missed by T.S (Ti).Rest all the properties are same as time stamping protocol.

Lock Based Protocol

To achieve consistency isolation is the most important idea. Locking is

The simplest idea to achieve isolation is first obtain a lock on a data item then perform a desired operation and then unlock it.

Two Phase locking Protocol (2PL)/Base 2PL

Properties

• Schedules are conflict Serializable

• Unrecoverable Schedules

• Cascading Rollbacks

• Freedom from deadlocks.

Conservative/Static 2PL

Properties

Rigorous 2PL

Properties:

Strict 2PL

Properties:

Graph Based Protocol

Restrictions

Tree Protocol

Each transaction Ti can lock a data item Q with following rules

Properties:

· Conflict Serializable

· Deadlock free

· Locks can be unlock anytime

· Unnecessary locking overhead

· Cascading Rollbacks