Database Management Systems - Transaction Processing Concepts

Transaction Processing Concepts

  • Overview of concurrency control, Transaction Model, Significance of concurrency Control & Recovery, Transaction States, System Log, Desirable Properties of transactions.
  • Serial schedules, Concurrent and Serializable Schedules, Conflict equivalence and conflict serializability, Recoverable and cascade-less schedules, Locking, Two-phase locking and its variations. Log-based recovery, Deferred database modification, check-pointing.
  • Introduction to NoSQL Databases, Main characteristics of Key-value DB (examples from: Redis), Document DB (examples from: MongoDB)
  • Main characteristics of Column - Family DB (examples from: Cassandra) and Graph DB (examples from : ArangoDB)

Schedules

  • A schedule (or history) S of n transactions T1, T2, …, Tn is an ordering of the operations of the transactions.
  • Operations from different transactions can be interleaved in the schedule S.

Recoverable Schedules

  • Schedules in which transactions commit only after all transactions whose changes they read commit are called recoverable schedules.
  • If some transaction Tj is reading value updated or written by some other transaction Ti, then the commit of Tj must occur after the commit of Ti.
  • Example:
    • T1 reads A, then T2 writes A and reads A and commits. T1 writes A and commits.
    • This is a recoverable schedule since T1 commits before T2, that makes the value read by T2 correct.

Irrecoverable Schedule

  • A schedule with two transactions, T1 reads and writes A and that value is read and written by T2.
  • T2 commits, but later on, T1 fails.
  • So we have to rollback T1. Since T2 has read the value written by T1, it should also be rollbacked.
  • But we have already committed that.
  • So this schedule is irrecoverable schedule.
  • When Tj is reading the value updated by Ti and Tj is committed before committing of Ti, the schedule will be irrecoverable.

Recoverable with Cascading Rollback

  • A schedule with two transactions, T1 reads and writes A and that value is read and written by T2.
  • But later on, T1 fails. So we have to rollback T1.
  • Since T2 has read the value written by T1, it should also be rollbacked.
  • As it has not committed, we can rollback T2 as well. So it is recoverable with cascading rollback.
  • If Tj is reading value updated by Ti and commit of Tj is delayed till commit of Ti, the schedule is called recoverable with cascading rollback.
  • Cascading Rollback (or cascading abort) to occur in some recoverable schedules, where an uncommitted transaction has to be rolled back because it read an item from a transaction that failed.

Cascadeless Recoverable Schedule

  • A schedule with two transactions, T1 reads and writes A and commits and that value is read by T2.
  • But if T1 fails before commit, no other transaction has read its value, so there is no need to rollback other transaction.
  • So this is a Cascadeless recoverable schedule.
  • If Tj reads value updated by Ti only after Ti is committed, the schedule will be cascadeless recoverable.
  • A schedule is said to be cascadeless, or to avoid cascading rollback, if every transaction in the schedule reads only items that were written by committed transactions.

Serial Schedules

  • Schedules in which the transactions are executed non-interleaved
  • A serial schedule is one in which no transaction starts until a running transaction has ended are called serial schedules.
  • Example: Consider the schedule involving two transactions T1 and T2. This is a serial schedule since the transactions perform serially in the order T1 -> T2
    • T1: R(A), W(A), R(B), W(B)
    • T2: R(A), R(B)

Non-Serial Schedules

  • This is a type of Scheduling where the operations of multiple transactions are interleaved.
  • Unlike the serial schedule where one transaction must wait for another to complete all its operation, in the non-serial schedule, the other transaction proceeds without waiting for the previous transaction to complete.
  • This might lead to a rise in the concurrency problem.
  • It can be of two types namely, Serializable and Non-Serializable Schedule.

Serializable Schedules

  • This is used to maintain the consistency of the database.
  • It is mainly used in the Non-Serial scheduling to verify whether the scheduling will lead to any inconsistency or not.
  • These are of two types: Conflict Serializable and View Serializable

Conflict Serializable

  • A schedule is called conflict serializability if after swapping of non-conflicting operations, it can transform into a serial schedule.
  • The schedule will be a conflict serializable if it is conflict equivalent to a serial schedule.

Conflicting Operations

  • The two operations become conflicting if all conditions satisfy:
    • Both belong to separate transactions.
    • They have the same data item.
    • They contain at least one write operation.

Conflict Equivalent

  • In the conflict equivalent, one can be transformed to another by swapping non-conflicting operations.
  • Two schedules are said to be conflict equivalent if and only if:
    • They contain the same set of the transaction.
    • If each pair of conflict operations are ordered in the same way.

Conflict Equivalent Schedule

  • Schedule S1 can be transformed into a serial schedule by swapping non-conflicting operations of S1.
    • T1: Read(A), Write(A), Read(B), Write(B)
    • T2: Read(A), Write(A), Read(B), Write(B)

Algorithm for Determining Conflict Serializability

  1. Create a node T in the graph for each participating transaction in the schedule.
  2. For the conflicting operation readitem(X) and writeitem(X) – If a Transaction Tj executes a readitem (X) after Ti executes a writeitem (X), draw an edge from Ti to Tj in the graph.
  3. For the conflicting operation writeitem(X) and readitem(X) – If a Transaction Tj executes a writeitem (X) after Ti executes a readitem (X), draw an edge from Ti to Tj in the graph.
  4. For the conflicting operation writeitem(X) and writeitem(X) – If a Transaction Tj executes a writeitem (X) after Ti executes a writeitem (X), draw an edge from Ti to Tj in the graph.
  5. The Schedule S is serializable if there is no cycle in the precedence graph.

Examples of Conflict Serializability

  • Example 1: No Cycle/Loop - Conflict Serializable
    • Transactions: T1, T2, T3
    • Operations:
      • T1: R(x), W(x)
      • T2: R(z), W(z), R(y), W(z)
      • T3: R(y), R(x), W(y)
    • Edges:
      • T2 -> T1 (due to R(z) in T2 and W(z) in T1)
      • T3 -> T1 (due to R(x) in T3 and W(x) in T1)
      • T2 -> T3 (due to R(y) in T2 and W(y) in T3)
  • Example 2: Cycle/Loop - Non-Conflict Serializable
    • Transactions: T1, T2, T3
    • Operations:
      • T1: R(A), W(A)
      • T2: W(A)
      • T3: W(A)
  • Example 3: No Cycle/Loop - Conflict Serializable
    • Transactions: T1, T2, T3
    • Operations:
      • T1: R(x), W(x)
      • T2: R(x)
      • T3: R(x), W(x)

View Serializability

  • View Serializability is a process to find out that a given schedule is view serializable or not.
  • To check whether a given schedule is view serializable, we need to check whether the given schedule is View Equivalent to its serial schedule.
  • Example:
    • Schedules S1 and S2 with transactions T1, T2, T3 and operation W(A).

Conditions for View Equivalence

  • Two schedules S1 and S2 are said to be view equivalent if they satisfy the following conditions:
    • Initial Read: An initial read of both schedules must be the same.
      • Suppose two schedule S1 and S2. In schedule S1, if a transaction T1 is reading the data item A, then in S2, transaction T1 should also read A.
    • Updated Read: In schedule S1, if Ti is reading A which is updated by Tj then in S2 also, Ti should read A which is updated by Tj.
    • Final Write: A final write must be the same between both the schedules. In schedule S1, if a transaction T1 updates A at last then in S2, final writes operations should also be done by T1.

View Serializability - Example

  • Non-Serial Schedule S1 with transactions T1 and T2:
    • T1: R(X), W(X), R(Y), W(Y)
    • T2: R(X), W(X), R(Y), W(Y)
  • Serial Schedule S2 with transactions T1 and T2:
    • T1: R(X), R(Y), W(X), W(Y)
    • T2: R(X), R(Y), W(X), W(Y)
  • Checking for view serializability:
    • Initial Read: T1 first reads X and Y in both S1 and S2.
    • Final Write: T2 performs the final write on X and Y in both S1 and S2.
    • Update Read: T2 reads X and Y after they are written by T1 in both S1 and S2.
  • Result: Since all three conditions are satisfied, S1 and S2 are view equivalent, and S1 is view serializable.

Database Transaction

  • A Database Transaction is a logical unit of processing in a DBMS which entails one or more database access operation.
  • The operations performed in a transaction include one or more of database operations like insert, delete, update or retrieve data.

Single User and Multi User Database Systems

  • Single User Database Systems
    • A DBMS is single-user if at most one user at a time can use the system.
    • Single-User DBMSs are mostly restricted to personal computer systems.
    • Single user databases do not have multiprogramming thus, single CPU can only execute at most one process at a time.
    • Example: Personal Computers.
  • Multi User Database Systems
    • A DBMS is multi-user if many/multi users can use the system and hence access the database concurrently.
    • Most DBMSs are multi user, like databases of airline reservation systems, banking databases, etc.
    • Multiple users can access databases and use computer systems simultaneously because of the concept of Multiprogramming.
    • Example: Databases of Banks, insurance agencies, stock exchanges, supermarkets, etc.
  • The figure shows two processes, A and B, executing concurrently in an interleaved fashion.
  • if the computer system has multiple hardware processors (CPUs), parallel processing of multiple processes is possible, as illustrated by processes C and D in the figure.

Low Level Operations

  • Each high level operation can be divided into a number of low level tasks or operations.
  • For example, a data update operation can be divided into three tasks
    • read_item() − reads data item from storage to main memory.
    • modify_item() − change value of item in the main memory.
    • write_item() − write the modified value from main memory to storage.

Transaction Operations

  • The low level operations performed in a transaction are −
    • begin_transaction − A marker that specifies start of transaction execution.
    • readitem or writeitem − Database operations that may be interleaved with main memory operations as a part of transaction.
    • end_transaction − A marker that specifies end of transaction.
    • commit − A signal to specify that the transaction has been successfully completed in its entirety and will not be undone.
    • rollback − A signal to specify that the transaction has been unsuccessful and so all temporary changes in the database are undone. A committed transaction cannot be rolled back.

Concurrency Problems

  • When multiple transactions execute concurrently in an uncontrolled or unrestricted manner, then it might lead to several problems.
  • These problems are commonly referred to as concurrency problems in database environment.
  • The five concurrency problems that can occur in database are:
    • Temporary Update Problem
    • Incorrect Summary Problem
    • Lost Update Problem
    • Unrepeatable Read Problem
    • Phantom Read Problem

Temporary Update (Dirty Read) Problem

  • Temporary update or dirty read problem occurs when one transaction updates an item and fails.
  • But the updated item is used by another transaction before the item is changed or reverted back to its last value.
  • In this example, if transaction 1 fails for some reason then X will revert back to its previous value.
  • But transaction 2 has already read the incorrect value of X.

Incorrect Summary Problem

  • Consider a situation, where one transaction is applying the aggregate function on some records while another transaction is updating these records.
  • The aggregate function may calculate some values before the values have been updated and others after they are updated.
  • In this example, transaction 2 is calculating the sum of some records while transaction 1 is updating them.
  • Therefore the aggregate function may calculate some values before they have been updated and others after they have been updated.

Unrepeatable Read Problem

  • The unrepeatable problem occurs when two or more read operations of the same transaction read different values of the same variable.
  • In this example, once transaction 2 reads the variable X, a write operation in transaction 1 changes the value of the variable X.
  • Thus, when another read operation is performed by transaction 2, it reads the new value of X which was updated by transaction 1.

Lost Update Problem

  • In the lost update problem, update done to a data item by a transaction is lost as it is overwritten by the update done by another transaction.
  • In this example, transaction 1 changes the value of X but it gets overwritten by the update done by transaction 2 on X.
  • Therefore, the update done by transaction 1 is lost.

Types of Failures

  • Whenever a transaction is submitted to a DBMS for execution
  • The system is responsible for making sure that either all the operations in the transaction are completed successfully and their effect is recorded permanently in the database or that the transaction does not have any effect on the database or any other transactions.
  • Types of Failures
    • A computer failure (system crash). A hardware, software, or network error occurs in the computer system during transaction execution.
    • A transaction or system error. Some operation in the transaction may cause it to fail,
      • Integer overflow or division by zero.
      • Erroneous parameter values
      • Logical programming error.
      • User may interrupt the transaction during its execution
    • Local errors or exception conditions detected by the transaction
      • During transaction execution, certain conditions may occur that necessitate cancellation of the transaction.
      • Eg: Insufficient account balance in a banking database, may cause a transaction, such as a fund withdrawal, to be canceled.
    • Disk failure
      • Some disk blocks may lose their data because of a read or write malfunction or because of a disk read/write head crash.
      • This may happen during a read or a write operation of the transaction.
    • Physical problems and catastrophes.
      • This refers to an endless list of problems that includes power or air-conditioning failure, fire, theft, sabotage, overwriting disks or tapes by mistake, and mounting of a wrong tape by the operator.

States of Transactions

  • Active State: A transaction enters into an active state when the execution process begins. During this state read or write operations can be performed.
  • Partially Committed: A transaction goes into the partially committed state after the end of a transaction.
  • Committed State: When the transaction is committed to state, it has already completed its execution successfully. Moreover, all of its changes are recorded to the database permanently.
  • Failed State: A transaction considers failed when any one of the checks fails or if the transaction is aborted while it is in the active state.
  • Terminated State: State of transaction reaches terminated state when certain transactions which are leaving the system can't be restarted.

Transaction State Transitions

  1. Once a transaction states execution, it becomes active. It can issue READ or WRITE operation.
  2. Once the READ and WRITE operations complete, the transactions becomes partially committed state.
  3. Next, some recovery protocols need to ensure that a system failure will not result in an inability to record changes in the transaction permanently. If this check is a success, the transaction commits and enters into the committed state.
  4. If the check is a fail, the transaction goes to the Failed state.
  5. If the transaction is aborted while it’s in the active state, it goes to the failed state. The transaction should be rolled back to undo the effect of its write operations on the database.
  6. The terminated state refers to the transaction leaving the system.

System Log

  • To be able to recover from failures that affect transactions, the system maintains a log
  • to keep track of all transaction operations that affect the values of database items,
  • as well as other transaction information that may be needed to permit recovery from failures.
  • In a stable storage, logs for each transaction are maintained.
  • Any operation which is performed on the database is recorded is on the log.
  • Prior to performing any modification to database, an update log record is created to reflect that modification.

Log Records

  1. [start_transaction, T]. Indicates that transaction T has started execution.
  2. [writeitem, T, X, oldvalue, newvalue]. Indicates that transaction T has changed the value of database item X from oldvalue to new_value.
  3. [read_item, T, X]. Indicates that transaction T has read the value of database item X.
  4. [commit, T]. Indicates that transaction T has completed successfully, and affirms that its effect can be committed (recorded permanently) to the database.
  5. [abort, T]. Indicates that transaction T has been aborted.

ACID Properties

  • ACID Properties are used for maintaining the integrity of database during transaction processing.
  • ACID in DBMS stands for Atomicity, Consistency, Isolation, and Durability.

Atomicity

  • By this, we mean that either the entire transaction takes place at once or doesn’t happen at all.
  • There is no midway i.e. transactions do not occur partially.
  • Each transaction is considered as one unit and either runs to completion or is not executed at all.
  • It involves the following two operations.
    • Abort: If a transaction aborts, changes made to database are not visible.
    • Commit: If a transaction commits, changes made are visible.
  • Atomicity is also known as the ‘All or nothing rule’.
  • Consider the following transaction T consisting of T1 and T2: Transfer of 100 from account X to account Y.
  • If the transaction fails after completion of T1 but before completion of T2.( say, after write(X) but before write(Y)), then amount has been deducted from X but not added to Y.
  • This results in an inconsistent database state. Therefore, the transaction must be executed in entirety in order to ensure correctness of database state.

Consistency

  • This means that integrity constraints must be maintained so that the database is consistent before and after the transaction.
  • It refers to the correctness of a database.
  • Referring to the example above,
  • The total amount before and after the transaction must be maintained.
  • Total before T occurs = 500 + 200 = 700.
  • Total after T occurs = 400 + 300 = 700.
  • Therefore, database is consistent. Inconsistency occurs in case T1 completes but T2 fails. As a result T is incomplete.

Isolation

  • In a database system where more than one transaction are being executed simultaneously and in parallel,
  • the property of isolation states that all the transactions will be carried out and executed as if it is the only transaction in the system.
  • No transaction will affect the existence of any other transaction.
  • Let X= 500, Y = 500. Consider two transactions T and T”.
  • Suppose T has been executed till Read (Y) and then T’’ starts. As a result , interleaving of operations takes place due to which T’’ reads correct value of X but incorrect value of Y and sum computed by
  • T’’: (X+Y = 50, 000+500=50, 500) is thus not consistent with the sum at end of transaction:
  • T: (X+Y = 50, 000 + 450 = 50, 450).
  • This results in database inconsistency, due to a loss of 50 units. Hence, transactions must take place in isolation and changes should be visible only after they have been made to the main memory.

Durability

  • The database should be durable enough to hold all its latest updates even if the system fails or restarts.
  • If a transaction updates a chunk of data in a database and commits, then the database will hold the modified data.
  • If a transaction commits but the system fails before the data could be written on to the disk, then that data will be updated once the system springs back into action.