DATABASE CONCURRENCY

If you have any queries please leave a message here
Your Message
×


A transaction is the execution of a program that accesses or changes the contents of a database. It is a logical unit of work on the database that is either completed in its entirety (COMMIT) or not done at all. In the latter case, the transaction has to clean up its own mess, known as ROLLBACK. A transaction could be an entire program, a portion of a program or a single command.

Interleaved Concurrency

Many computer systems, including DBMSs, are used simultaneously by more than one user. This means the computer runs multiple transactions (programs) at the same time. For example, an airline reservations system is used by hundreds of travel agents and reservation clerks concurrently. Systems in banks, insurance agencies, stock exchanges and the like are also operated by many users who submit transactions concurrently to the system. If, as is often the case, there is only one CPU, then only one program can be processed at a time. To avoid excessive delays, concurrent systems execute some commands from one program (transaction), then suspended that program and execute some commands from the next program, and so on. A program is resumed at the point where it was suspended when it gets its turn to use the CPU again. This is known as interleaving.

Simultaneous Concurrency

If the computer system has multiple hardware processors (CPUs), simultaneous processing of multiple programs is possible, leading to simultaneous rather than interleaved concurrency.






CONCURRENCY PROBLEM

Consider a simple airline reservation database in which each record is stored for each airline flight. Each record includes the number of reserved seats on that flight as a named data item, among other information. The figure below shows examples of two very simple transactions.

Transaction T1

read_item(X);
X := X - N;
write_item(X);
Transaction T2

read_item(X);
X := X + M;
write_item(X);


Transaction T1 cancels N reservations from flight F1, whose number of reserved seats is stored in the database item named X and reserves the same number of seats on another flight, whose number of reserved seats is stored in the database item named Y. Transaction T2 just reserves M seats on the flight F1 referenced in transaction T1.

The above two transactions submitted by any two different users may be executed concurrently and may access and update the same database items (e.g. X). If this concurrent execution is uncontrolled, it may lead to problems such as an inconsistent database. Some of the problems that may occur when concurrent transactions execute in an uncontrolled manner are discussed here.






UPDATE PROBLEM

Suppose the two transactions T1 and T2 are submitted at approximately the same time. So that their operations are interleaved by the operating system as shown in the figure below :

TimeT1T2Comments
1read_item(X);Transaction T1 read the seat reservation value from data item X for flight F1
2read_item(X);Transaction T2 read the seat reservation value from data item X for flight F1
3X := X - N;Transaction T1 minus N seats to cancel reservation.
4X := X + M;Transaction T2 add M seats to reserved.
5write_item(X);Transaction T1 write the new seat reservation value on data item X for flight F1
6write_item(X);Transaction T2 write the new seat reservation value on data item X for flight F1

Now if X = 80, originally there were 80 reservations on the flight, N = 5, T1 cancels 5 seats on the flight corresponding to X and M = 4, T2 reserves 4 seats on X then final result should be X = 80 – 5 + 4 = 79; but in the concurrent operations X = 84 because the update that cancelled 5 seats in T1 was lost.

TimeT1T2Value
1read_item(X);X = 80
2read_item(X);X = 80
3X := X - N;X = 80 - 5 = 75
4X := X + M;X = 80 + 4 = 84
5write_item(X);X = 75 is written into database
6write_item(X);X = 84 over writes X = 75 (A wrong record is written in database.)






UNCOMMITTED DEPENDENCY (DIRTY READ / TEMPORARY UPDATE)

Uncommitted dependency occurs when a transaction is allowed to retrieve or update a record that has been updated by another transaction, but which has not yet been committed by that other transaction.

Transaction T1

read_item(X);
X := X - N;
write_item(X);
read_item(Y);
Y := Y + N;
write_item(Y);
Transaction T2

read_item(X);
X := X + M;
write_item(X);

The figure below shows an example where T1 updates item X and then fails before completion, so the system must change X back to its original value. Before it can do so, however, transaction T2 reads the ‘temporary’ value of X, which will not be recorded permanently in the database because of the failure of T1. The value of item X that is read by T2 is called dirty data, because it has been created by a transaction that has not been completed and committed yet; hence this problem is also known as the dirty read problem.

TimeT1T2Comments
1read_item(X);
2X := X - N;
3write_item(X);X is temporarily updated
4read_item(X);
5X := X + M;
6write_item(X);
7write_item(Y);
  ...  ...  ...
ROLLBACK
T1 fails and must change the value of X back to its old value; meanwhile T2 has read the temporary incorrect value of X.

If there is a condition where transaction T2 may already have terminated (commit) before the rollback of transaction T1 then the following situation is arise.

TimeT1T2Comments
1read_item(X);
2X := X - N;
3write_item(X);X is temporarily updated
4read_item(X);
5X := X + M;
6write_item(X);
6
COMMIT
Transaction T2 loss update change
7write_item(Y);
  ...  ...
ROLLBACK
T2 depends on uncommitted value and loses and update at time step 7.


In the above example, the rollback in T1 causes data item X to be restored to its value before time step 1. for this reason T2 loses the update which is done at time step 7.





CONCURRENCY CONTROL

In a multiprogramming environment where multiple transactions can be executed simultaneously, it is highly important to control the concurrency of transactions. We have concurrency control protocols to ensure atomicity, isolation, and serializability of concurrent transactions. Concurrency control protocols can be broadly divided into two categories −


TIMESTAMP BASED PROTOCOLS

The most commonly used concurrency protocol is the timestamp based protocol. This protocol uses either system time or logical counter 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.

Every transaction has a timestamp associated with it, and the ordering is determined by the age of the transaction. A transaction created at 0002 clock time would be older than all other transactions that come after it. For example, any transaction 'y' entering the system at 0004 is two seconds younger and the priority would be given to the older one.

The timestamp ordering protocol also maintains the timestamp of last 'read' and 'write' operation on a data.


Timestamp Ordering Protocol

The timestamp-ordering protocol ensures serializability among transactions in their conflicting read and write operations. 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.

Timestamp ordering protocol works as follows −


Timestamp Ordering Protocol Working Process

Whenever a transaction begins, it receives a timestamp. This timestamp indicates the order in which the transaction must occur, relative to the other transactions. So, given two transactions that affect the same object, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.

Every object in the database has a read timestamp, which is updated whenever the object's data is read, and a write timestamp, which is updated whenever the object's data is changed.

If a transaction wants to read an object,

If a transaction wants to write to an object,






ACID

A transaction in a database system must maintain Atomicity, Consistency, Isolation, and Durability − commonly known as ACID properties − in order to ensure accuracy, completeness, and data integrity.

Atomicity - A transaction must be fully complete, saved (committed) or completely undone (rolled back). A sale in a retail store database illustrates a scenario which explains atomicity, e.g., the sale consists of an inventory reduction and a record of incoming cash. Both either happen together or do not happen - it's all or nothing.

Consistency - The transaction cannot break the database’s constraints. For example, if a database table’s Phone Number column can only contain numerals, then consistency dictates that any transaction attempting to enter an alphabetical letter may not commit.

Isolation - A transaction should not make its updates visible to other transactions until it is committed; this property, when enforced strictly, solves the temporary update problem and makes cascading rollbacks of transactions unnecessary.

Durability - When a transaction has made a change to the database state and the change is committed, this change is permanent and should be available to all other transactions.



ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us