Concurrency control
Concurrency control is the process of managing simultaneous execution of transactions (such as queries, updates, inserts, deletes and so on) in a multiprocessing database system without having them interfere with one another.
This property of DBMS allows many transactions to access the same database at the same time without interfering with each other.
The primary goal of concurrency is to ensure the atomicity of the execution of transactions in a multi-user database environment. Concurrency controls mechanisms attempt to interleave (parallel) READ and WRITE operations of multiple transactions so that the interleaved execution yields results that are identical to the results of a serial schedule execution.
Problems of Concurrency Control :
When concurrent transactions are executed in an uncontrolled manner, several problems can occur.
The concurrency control has the following three main problems:
- Lost updates.
- Dirty read (or uncommitted data).
- Unrepeatable read (or inconsistent retrievals).
Lost Update Problem :
A lost update problem occurs when two transactions that access the same database items have their operations in a way that makes the value of some database item incorrect.
In other words, if transactions T1 and T2 both read a record and then update it, the effects of the first update will be overwritten by the second update.
Example:
Consider the situation given in figure that shows operations performed by two transaactions, Transaction- A and Transaction- B with respect to time.
Transaction- A |
Time |
Transaction- B |
----- |
t0 |
---- |
Read X |
t1 |
---- |
---- |
t2 |
Read X |
Update X |
t3 |
---- |
---- |
t4 |
Update X |
---- |
t5 |
---- |
At time t1 , Transactions-A reads value of X.
At time t2 , Transactions-B reads value of X.
At time t3,Transactions-A writes value of X on the basis of the value seen at time t1.
At time t4,Transactions-B writes value of X on the basis of the value seen at time t2.
So,update of Transactions-A is lost at time t4,because Transactions-B overwrites it without looking at its current value.
Such type of problem is reffered as the Update Lost Problem, as update made by one transaction is lost here.
Dirty Read Problem :
A dirty read problem occurs when one transaction updates a database item and then the transaction fails for some reason.The updated database item is accessed by another transaction before it is changed back to the original value.In other words, a transaction T1 updates a record, which is read by the transaction T2.
Then T1 aborts and T2 now has values which have never formed part of the stable database.
Example:
Consider the situation given in figure :
Transaction- A |
Time |
Transaction- B |
---- |
t0 |
---- |
---- |
t1 |
Update X |
Read X |
t2 |
---- |
---- |
t3 |
Rollback |
---- |
t4 |
---- |
At time t1 , Transactions-B writes value of X.
At time t2 , Transactions-A reads value of X.
At time t3 , Transactions-B rollbacks.So,it changes the value of X back to that of prior to t1.
So,Transaction-A now has value which has never become part of the stable database.
Such type of problem is reffered as the Dirty Read Problem, as one transaction reads a dirty value which has not been commited.
Inconsistent Retrievals Problem :
Unrepeatable read (or inconsistent retrievals) occurs when a transaction calculates some summary (aggregate) function over a set of data while other transactions are updating the data.
The problem is that the transaction might read some data before they are changed and other data after they are changed, thereby yielding inconsistent results.
In an unrepeatable read, the transaction T1 reads a record and then does some other processing during which the transaction T2 updates the record. Now, if T1 rereads the record, the new value will be inconsistent with the previous value.
Example:
Consider the situation given in figure that shows two transactions operating on three accounts :
Account-1 Account-2 Account-3
Balance = 200 Balance = 250 Balance = 150
Transaction- A |
Time |
Transaction- B |
----- |
t0 |
---- |
Read Balance of Acc-1
sum <-- 200
Read Balance of Acc-2 |
t1 |
---- |
Sum <-- Sum + 250 = 450 |
t2 |
---- |
---- |
t3 |
Read Balance of Acc-3 |
---- |
t4 |
Update Balance of Acc-3
150 --> 150 - 50 --> 100 |
---- |
t5 |
Read Balance of Acc-1 |
---- |
t6 |
Update Balance of Acc-1
200 --> 200 + 50 --> 250 |
----
Read Balance of Acc-3 |
t7 |
COMMIT
|
Sum <-- Sum + 250 = 450 |
t8 |
---- |
Transaction-A is summing all balances;while, Transaction-B is transferring an amount 50 from Account-3 to Account-1.
Here,the result produced by Transaction-A is 550,which is incorrect. if this result is written in database, database will be in inconsistent state, as actual sum is 600.
Here,Transaction-A has seen an inconsistent state of database, and has performed inconsistent analysis.
Degree of Consistency :
Following four levels of transaction consistency have been defined by Gray (1976):
consistency |
Description |
Level 0 |
In general, level 0 transactions are not recoverable since they may have interactions with the external word which cannot be undone. They have the following properties:
The transaction T does not overwrite other transaction's dirty (or uncommitted) data. |
Level 1 |
level 1 transaction is the minimum consistency requirement that allows a transaction to be recovered in the event of system failure. They have the following properties:
The transaction T does not overwrite other transaction's dirty (or uncommitted) data.
The transaction T does not make any of its updates visible before it commits. |
Level 2 |
Level 2 transaction consistency isolates from the updates of other transactions. They have the following properties:
The transaction T does not overwrite other transaction's dirty (or uncommitted) data.
The transaction T does not make any of its updates visible before it commits.
The transaction T does not read other transaction's dirty (or uncommitted) data. |
Level 3 |
Level 3 transaction consistency adds consistent reads so that successive reads of a record will always give the same values. They have the following properties:
The transaction T does not overwrite other transaction's dirty (or uncommitted) data.
The transaction T does not make any of its updates visible before it commits.
The transaction T does not read other transaction's dirty (or uncommitted) data.
The transaction T can perform consistent reads, that is, no other transaction can update data read by the transaction T before T has committed. |
Permutable Actions :
An action is a unit of processing that is indivisible from the DBMS's perspective.In systems where the granule is a page, the actions are typically read-page and write-page.
The actions provided are determined by the system designers, but in all cases they are independent of side-effects and do not produce side-effects.
A pair of actions is permutable if every execution of A, followed by Aj has the same result as the execution of Aj followed by A, on the same granule. Actions on different granules are always permutable.
For the actions read and write we have:
- Read-Read: Permutable .
- Read-write: Not permutable, since the result is different depending on whether read is first or write is first.
- Write-Write: Not permutable, as the second write always nullifies the effects of the first write.
Schedule :
A schedule (also called history) is a sequence of actions or operations (for example, reading writing, aborting or committing) that is constructed by merging the actions of a set of transactions, respecting the sequence of actions within each transaction.
As long as two transactions T1 and T2 access unrelated data, there is no conflict and the order of execution is not relevant to the final result. Thus, DBMS has inbuilt software called scheduler, which determines the correct order of execution.
The scheduler establishes the order in which the operations within concurrent transactions are executed.
The scheduler interleaves the execution of database operations to ensure serialisability (as explained in next section).The scheduler bases its actions on concurrency control algorithms, such as locking or time stamping methods.
The schedulers ensure the efficient utilization of central processing unit (CPU) of computer system.
It can be observed that the schedule does not contain an ABORT or COMMIT action for either transaction.
Schedules which contain either an ABORT or COMMIT action for each transaction whose actions are listed in it are called a
complete schedule.
If the actions of different transactions are not interleaved, that is, transactions are executed one by one from start to finish, the schedule is called a
serial schedule.
A non-serial schedule is a schedule where the operations from a group of concurrent transactions are interleaved.
A serial schedule gives the benefits of concurrent execution without giving up any correctness.
The disadvantage of a serial schedule is that it represents inefficient processing because no interleaving of operations form different transactions is permitted.
This can lead to low CPU utilization while a transaction waits for disk input/output (I/O), or for another transaction to terminate, thus slowing down processing considerably.
Serializable Schedules :
A serial sable schedule is a schedule that follows a set of transactions to execute in some order such that the effects are equivalent to executing them in some serial order like a serial schedule. The execution of transactions in a serialisable schedule is a sufficient condition for preventing conflicts.
The serial execution of transactions always leaves the database in a consistent state.
Serialisability describes the concurrent execution of several transactions.
The objective of Serialisability is to find the non-serial schedules that allow transactions to execute concurrently without interfering with one another and thereby producing a database state that could be produced by a serial execution.
Serialisability must be guaranteed to prevent inconsistency from transactions interfering with one another. The order of Read and Write operations are important in serialisability.
The Serialisability rules are as follows:
- If two transactions T1 and T2 only Read a data item, they do not conflict and the order is not important.
- If two transactions T1 and T2 either Read or Write completely separate data items, they do not conflict and the execution order is not important.
- If one transaction T1 Writes a data item and another transaction T2 either Reads or Writes the same data item, the order of execution is important.
Serailisability can also be depicted by constructing a precedence graph.
A precedence relationship can be defined as, transaction T1 precedes transaction T2 and between T1 and T2 if there are two non-permutable actions A1and A2 and A1 is executed by T1 before A2 is executed by T2.
Given the existence of non-permutable actions and the sequence of actions in a transaction it is possible to define a partial order of transactions by constructing a precedence graph.
A precedence graph is a directed graph in which:
- The set of vertices is the set of transactions.
- An arc exists between transactions T1 and T2 if T1 precedes T2.
- A schedule is serialisable if the precedence graph is cyclic.
- The serialisability property of transactions is important in multi-user and distributed databases, where several transactions are likely to be executed concurrently.
Ask Question