Concurrency control in real-time database

Concurrency control in real-time database, How concurrency control is achieved in a real-time database? Pessimistic and Optimistic concurrency control mechanism, Explain concurrency control in real-time database 

Concurrency Control in Real-Time Database

A database transaction normally involves one or more data items to be accessed in read mode or write mode. A transaction is said to be successfully completed if and only if,

• It is able to use all the required data items,
• Make necessary changes to the data items (if any) consistently, and
• Store the changes permanently in the permanent storage.

In this process, a transaction may consume considerable time depends on the size of a transaction, the number of data items needed, the availability of CPU, etc. In a conventional database, to increase the number of transactions that is completed in a given time, we need to execute several transactions simultaneously. Here we need to ensure ACID properties for individual transactions. Execution of all active transactions concurrently is referred as concurrent transactions.

Concurrency control is about ensuring non-interference among transactions by restricting concurrent transactions to be serializable. A concurrent execution of a set of transactions is said to be serializable if and only if the database operations carried out by them is equivalent to some serial execution of these transactions.

Concurrency control protocols usually adopt any of the following types of approaches; concurrency control mechanisms used in a conventional database may not fit for real-time database. Hence, the modified versions of these protocols according to the real-time requirements of a database are presented below;

• Pessimistic Concurrency Control Protocols(Lock based protocols) 
• Achieving concurrency control by disallowing certain transactions based on the data items they locked. CLICK to continue.

• Optimistic Concurrency Control Protocols  
• Achieving concurrency control by allowing all the transactions and pruning (or validating) them at the time of commit for further allowing them. CLICK to continue.

• Speculative Concurrency Control Protocols 
• Achieving concurrency control by applying the combination of both pessimistic and optimistic protocols on a transaction. CLICK to continue.

• Multi-version Concurrency Control Protocols 
•  CLICK to continue.

********************

Go to REAL TIME DATABASE Home page

List of sources of unpredictability of dead-line in real-time database

The list of sources of unpredictability in real-time database that makes the prediction of a transaction’s deadline difficult, Why it is difficult to predict the deadline in a real-time database transaction?

List of sources of unpredictability:

The following are the list of sources of unpredictability in real-time database that makes the prediction of a transaction’s deadline difficult;

The nature of any database transactions or the environment in which a transaction has to execute has one or more of the following. The uncertain nature in terms of time of the following points makes it difficult to identify the deadline exactly.

Dependency of the execution sequence of any transaction on the data values

-         The order of execution (execution sequence) of a transaction is highly depend on the values of the data items being accessed. For example, data items may be held by some other transactions, or the instructions that are part of the given transaction may be in a sequence.

Data and resource conflicts

-         A transaction may have to wait until it is allocated with the required resources. This may happen because of conflicting nature of concurrent transactions. Sometimes, a transaction may be forced to wait for resources such as CPU and I/O devices.

Dynamic paging and I/O

-         Unpredictability of disc access time involved in bringing required data page into memory and page faults

Transaction aborts and the resulting rollbacks and restarts

-         Transactions may be aborted due to many reasons such as, not able to complete the transaction because of failures (power failure, software failure, or system crash), deadlocks, or forced aborts. This will definitely lead a transaction to restart from scratch or rollback the changes made.

Because of these problems, it is hard to identify whether the transaction is able to meet its deadline or not. These are the points that have to be considered in terms of transaction in a conventional database systems. The necessary modification on the concurrency control mechanisms may alter this.

**************************

Go back to Real-time Databases - Home page

Real time database - formal definition of temporal consistency

Formal definition of temporal consistency in real-time database, Explain temporal consistency with examples, when would we say that data items are relatively consistent?

Formal definition of temporal consistency

Temporal consistency has two components, namely, Absolute consistency, and Relative consistency.

Let us denote the data item in real-time database by,

d: (value, avi, timestamp)

where,

d_value - the current state (current value) of d at the time d_timestamp

-         This shows the value of the data item as observed by the controlling system.

d_timestamp – the time at which the d_value observed

-         This shows the time at which the value is read by the controlling system.

d_avi – absolute validity interval of d_value.

-         This shows the length of the time interval the d_value is considered to have absolute validity. That is, d_value is absolutely valid between d_timestamp and d_timestamp + d_avi.

The set of data items that are relatively consistent with each other, form a relative consistency set R. Each such set R is associated with a relative validity interval denoted by R_rvi.

Assume that d Є R, then we can define the conditions for absolute and relative consistency as follows;

Absolute consistency: a data item d is absolutely valid if and only if,

|Current time – d_timestamp| ≤ d_avi.

Relative consistency: a set R of data items is relatively consistent if and only if,  

∀d, ∀d’ Є R, |d_timestamp – d’_timestamp| ≤ R_rvi.

Example:

Assume that the current altitude of a taking-off aircraft is 100 metres. If you have observed this value at time 2000 msec, and if that aircraft can maintain this altitude for at most 20 msec more, then this data item is temporally specified as,

d_altitude: (100 metres, 20 msec, 2000 msec)

or

altitude = (100, 20, 2000)

The given value (100 metres) can be absolutely valid for 20 msec since the time it was observed. That means, at the time 2021 msec (at time > 2000 + 20) the validity will be lost.

Let us assume the relative consistency set R as {altitude, cabin-pressure}. And the relative validity interval R_rvi = 5, then set R is relatively consistent if the difference between the observation times of altitude and cabin-pressure is less than or equal to R_rvi, ie. 5.

Altitude = (100, 20, 2000) and Cabin-pressure = (50, 25, 2002) are temporally consistent (both absolutely and relatively consistent) at time 2020.

Altitude = (100, 20, 2000) and Cabin-pressure = (50, 25, 2006) are absolutely consistent but not relatively consistent at time 2020. Because, |Altitude_timestamp – Cabin_pressure_timestamp| = 6, which is greater than the given R_rvi 5.

****************

Go to Temporal Consistency page to view explanation.

Go to REAL TIME DATABASE Home page