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

• 2 Phase locking
• Graph 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)

• If T.S (Ti) < W.T.S (Q), means Ti needs to read a value of Q that was already over. Hence request must be rejected and Ti must rollback.
• If T.S (Ti) >= W.T.S (Q) operation can be allowed and R.T.S (Q) will be max (R.T.S (Q), T.S (Ti))

Ti request for Write (Q)

• If T.S (Ti) < R.T.S (Q), means value of Q that Ti is producing was needed. Previously and the system assumed that the value would never be produced hence reject and rollback.
• If (T.S (Ti) >R.T.S (Q), Ti is attempting to write an absolute value of Q, reject and Rollback otherwise or, W.T.S (Q) =max (W.T.S (Q), T.S (Ti))

Properties of Time Stamping Protocol

• It ensures conflict Serializability
• It ensures view Serializability
• possibility of dirty read no restriction on commit, recoverable and cascading rollbacks are possible
• Now either we allow or reject so no idea of deadlock.
• May suffer from starvation, relatively slow.

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

• It modify time-stamping protocol in absolute write case when Ti request write(Q)
• If T.S (Ti) < W.T.S (Q), here Ti attempts to write absolute value of Q, rather than rolling back Ti ,write operation is ignored.

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.

• To provide better concurrency along with isolation we use different modes of locks.

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

• The protocol requires that each transition in a schedule will be two phased growing phase and shrinking phase.
• In growing phase transition can only obtain locks but cannot release any lock.
• In shrinking phase transaction can only release locks but cannot obtain any lock.
• Transition can perform read/write operation both in growing/shrinking phase.

Properties

• Schedules are conflict Serializable

• Unrecoverable Schedules

• Cascading Rollbacks

• Freedom from deadlocks.

Conservative/Static 2PL

• There is no growing phase in transaction first we acquire all the locks required and then directly will start from the lock point
• If all locks are not acquired then transaction must release the lock acquired so for and wait.
• Shrinking phase works as usual and transaction can unlock any data item.

Properties

• Conflict Serializable
• View Serializable
• Possibility of unrecoverable and cascading rollbacks.

Rigorous 2PL

• It is an improvement over 2PL protocol where we try to ensure recoverability and Cascadeless
• Rigorous 2PL requires that all the locks must be held until transaction consists, i.e. there is no shrinking phase in the life of a transaction.

Properties:

• Conflict Serializable
• View Serializable
• Recoverability
• Cascadeless
• Deadlock and inefficiency

Strict 2PL

• In this shrinking phase unlocking of exclusive locks are not allowed but unlocking of shared locks can be done.
• Provides better concurrency

Properties:

• Conflict Serializable
• View Serializable
• Recoverability
• Cascadeless
• Deadlock
• Better Concurrency

Graph Based Protocol

• For graph based protocol database items should have a prior knowledge in which the database items should occurred.
• We impose partial ordering -> or set all data items D= {d1, d2 _____dn} if di ->dj, then any transaction accessing both di and dj must access di before dj.
• Partial Ordering set of all database items D will now be viewed as directed acyclic graph called database graph.

Restrictions

• Graphs that are rooted tree
• Locks will be in exclusive modes only

Tree Protocol

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

• First lock by Ti may be on any data item.
• Subsequently a data item Q can be locked by Ti only if the parent of Q is currently locked by Ti
• Data item may be unlocked at any time.
• Data item Q that has been locked and unlocked by Ti cannot subsequently be relocked by Ti

Properties:

· Conflict Serializable

· Deadlock free

· Locks can be unlock anytime

· Unnecessary locking overhead

· Cascading Rollbacks