RRK-Unit5-Transactions

Introduction to Transaction Processing Concepts and Theory

Topics

This unit covers the following topics:

• Introduction to Transaction Processing (20.1)
• Transaction and System Concepts (20.2)
• Desirable Properties of Transactions (20.3)
• Characterizing Schedules Based on Recoverability (20.4)
• Characterizing Schedules Based on Serializability (20.5)
• Transaction Support in SQL (20.6)
• Two-Phase Locking Techniques for Concurrency Control (21.1)

What is a Transaction?

• A transaction is a single logical unit of work that accesses and possibly modifies the contents of a database.
• Transactions access data using read and write operations.
• Transaction processing systems:
  • Systems with large databases and hundreds of concurrent users.
  • Require high availability and fast response time.
• To maintain consistency in a database before and after the transaction, certain properties, called ACID properties, are followed.

20.1 Introduction to Transaction Processing

• Single-user DBMS: At most one user at a time can use the system (e.g., home computer).
• Multiuser DBMS: Many users can access the system (database) concurrently (e.g., airline reservations system).
• Multiprogramming: Allows the operating system to execute multiple processes concurrently.
  • Executes commands from one process, then suspends that process and executes commands from another process, etc.

20.1.2 Transactions, Database Items, Read and Write Operations, and DBMS Buffers

• Transaction: An executing program that forms a logical unit of database processing.
• Begin and end transaction statements: Specify transaction boundaries.
• Read-only transaction: Only reads data.
• Read-write transaction: Reads and writes data.

Database Items

• Database represented as a collection of named data items.
• The size of a data item is called its granularity.
• Data item:
  • Record
  • Disk block
  • Attribute value of a record
• Transaction processing concepts are independent of item granularity.

Read and Write Operations

• read_item(X):
  1. Find the address of the disk block that contains item X.
  2. Copy that disk block into a buffer in main memory (RAM) if it's not already there. The buffer size is the same as the disk block size.
  3. Copy item X from the buffer to the program variable named X.
  • Hard Disk (disk block) → main memory (RAM) → program variable named X
• write_item(X):
  1. Find the address of the disk block that contains item X.
  2. Copy that disk block into a buffer in main memory (RAM) if it's not already there.
  3. Copy item X from the program variable named X into its correct location in the buffer.
  4. Store the updated disk block from the buffer back to disk (either immediately or at some later point in time).
  • Hard Disk (disk block) → main memory (RAM) → program variable named X → Write buffer back to disk

Read and Write Sets

• Read set of a transaction: Set of all items read.
• Write set of a transaction: Set of all items written.

Commit and Rollback

• Commit:
  • Maintains integrity in the database.
  • Ensures that changes made by a transaction are permanently applied to the database.
  • Further operations of any other transaction are performed only after work of the current transaction is done, a commit operation is performed to the changes made by a transaction permanently to the database.
• Rollback:
  • Brings the database to the last saved state when a transaction is interrupted.
  • Undoes the operations of transactions that were performed before its interruption to achieve a safe state of the database and avoid any kind of ambiguity or inconsistency.

DBMS Buffers

• DBMS maintains several main memory data buffers in the database cache.
• When buffers are occupied, a buffer replacement policy is used to choose which buffer will be replaced (e.g., least recently used).

ACID Properties

• ACID properties ensure the reliability and consistency of data transactions.
• ACID stands for Atomicity, Consistency, Isolation, and Durability.

Isolation

• The operations of one transaction are invisible to other transactions until that transaction is complete.
• Each transaction behaves as if it were the only transaction running in the system, even when multiple transactions are happening simultaneously.

Example of Fund Transfer

• Transaction to transfer $50 from account A to account B:
  1. read(A)
  2. $A := A - 50$
  3. write(A)
  4. read(B)
  5. $B := B + 50$
  6. write(B)
• Atomicity requirement: If the transaction fails after step 3 and before step 6, money will be “lost,” leading to an inconsistent database state.
  • Failure could be due to software or hardware.
  • The system should ensure that updates of a partially executed transaction are not reflected in the database.
• Durability requirement: Once the user has been notified that the transaction has completed, the updates to the database by the transaction must persist even if there are software or hardware failures.

Durability

• Definition: Once a transaction is committed, it remains so even in the event of a system crash.
• Example: Ticket Booking
  • You book a flight and get confirmation.
  • The system crashes right after—but your booking stays in the system because it was committed.

Consistency

• Requirement in the fund transfer example: The sum of A and B is unchanged by the execution of the transaction.
• In general, consistency requirements include:
  • Explicitly specified integrity constraints such as primary keys and foreign keys.
  • Implicit integrity constraints (e.g., sum of balances of all accounts, minus sum of loan amounts must equal value of cash-in-hand).
• A transaction must see a consistent database.
• During transaction execution, the database may be temporarily inconsistent.
• When the transaction completes successfully, the database must be consistent.
• Erroneous transaction logic can lead to inconsistency.

Isolation (Continued)

• If between steps 3 and 6 of the fund transfer, another transaction T2 is allowed to access the partially updated database, it will see an inconsistent database (the sum A + B will be less than it should be).
• Example:
  • T1:
    1. read(A)
    2. $A := A - 50$
    3. write(A)
    4. read(B)
    5. $B := B + 50$
    6. write(B)
  • T2: read(A), read(B), print(A+B)
• Isolation can be ensured trivially by running transactions serially (i.e., one after the other).
• However, executing multiple transactions concurrently has significant benefits.

Isolation Example: Online Orders by Two Users

• Two customers try to buy the last available product at the same time.
• Isolation ensures:
  • Only one transaction will succeed.
  • The other will wait or fail, avoiding race conditions.

20.2 Transaction States

• BEGIN_TRANSACTION: Marks the beginning of transaction execution.
• READ or WRITE: Specify read or write operations on the database items that are executed as part of a transaction.
• END_TRANSACTION: Specifies that READ and WRITE transaction operations have ended and marks the end of transaction execution.
  • At this point, it may be necessary to check whether the changes introduced by the transaction can be permanently applied to the database (committed) or whether the transaction has to be aborted because it violates serializability or for some other reason.
• COMMIT_TRANSACTION: Signals a successful end of the transaction so that any changes (updates) executed by the transaction can be safely committed to the database and will not be undone.
• ROLLBACK (or ABORT): Signals that the transaction has ended unsuccessfully, so that any changes or effects that the transaction may have applied to the database must be undone.

Partially Committed State

• Once all the instructions of the transaction are successfully executed, the transaction enters the Partially Committed state.
• If the changes are made permanent from the buffer memory, then the transaction enters the Committed state (RAM → HardDisk).
• Otherwise, if there is any failure, it enters the failed state.
• The main reason for this state is that every time a database operation is performed, a transaction can involve a large number of changes to the database, and if a power failure or other technical problem occurs when the system goes down the transaction will result in Inconsistent changes to the database.

Failed and Terminated States

• Failed state: In case there is any failure in carrying out the instructions while the transaction is in the active state, or there are any issues while saving the changes permanently into the database (i.e., in the partially committed stage), then the transaction enters the failed state.
• Terminated state: If a transaction is aborted, then there are two ways of recovering the DBMS, one is by restarting the task, and the other is by terminating the task and making itself free for other transactions. The latter is known as the terminated state.

Example: Railway Ticket Booking

• When you initiate the booking process, the train details need to be retrieved from the database.
• Once these details are retrieved, the transaction of booking a ticket enters the active state.
• After the user has completed the entire process of booking a ticket from their end, the transaction enters the partially committed state. In case any error occurs during the process, then the transaction will enter the failed state.
• If the process was successful and the transaction entered the partially committed state, and the saving in the database is completed successfully, then the transaction enters the committed state. In case there is any error while saving in the database then it enters the failed state.
• Anything from the failed state enters the aborted state so that rollbacks can take place and the database consistency is maintained.
• If the booking is permanently saved in the database, or it has been aborted due to some unforeseen reasons then the transaction enters the terminated state.

What is Concurrency Control?

Concurrency control in a transactional Database Management System (DBMS) refers to the methods and mechanisms used to ensure that multiple transactions can occur simultaneously without causing inconsistencies in the database.

20.1.3 Why Concurrency Control Is Needed

• Transactions submitted by various users may execute concurrently, accessing and updating the same database items. Some form of concurrency control is needed.
• Concurrent execution of user programs is essential for good DBMS performance.
  • Disk access is frequent and slow.
  • Want to keep the CPU busy.
• A user’s program may carry out all sorts of operations on the data, but the DBMS is only concerned about what data is read from/written to the database.

Concurrency Control Problems

Several problems arise when numerous transactions execute simultaneously in a random manner. These are referred to as Concurrency Control Problems, including:

• Dirty Read Problem
• Lost Update Problem
• Incorrect Summary Problem
• Unrepeatable Read Problem
• Phantom Read Problem

Dirty Read Problem (Temporary Update Problem)

• The dirty read problem occurs when a transaction reads data that has been updated by another transaction that is still uncommitted. It arises due to multiple uncommitted transactions executing simultaneously.

• Example: Consider two transactions A and B performing read/write operations on a data DT in the database DB. The current value of DT is 1000:

  Time	A	B
  T1	READ(DT)
  T2	DT=DT+500
  T3	WRITE(DT)
  T4		READ(DT)
  T5		COMMIT
  T6	ROLLBACK

• Transaction A reads the value of data DT as 1000 and modifies it to 1500, which gets stored in the temporary buffer.

• Transaction B reads the data DT as 1500 and commits it, and the value of DT permanently gets changed to 1500 in the database DB.

• Then some server errors occur in transaction A, and it wants to get rollback to its initial value, i.e., 1000, and then the dirty read problem occurs.

• Temporary Update Problem Illustration:

  • Transaction T1:
    • read_item(X);
    • $X = X - N$
    • write_item(X);
  • Transaction T2:
    • read_item(X);
    • $X = X + M$
    • write_item(X);
    • read_item(Y);
  • Transaction T1 fails and must change the value of X back to its old value; meanwhile, T2 has read the temporary incorrect value of X.

The Lost Update Problem

• Arises when an update made by one transaction is overridden by another update by two different transactions.

• Example: Consider two transactions A and B performing read/write operations on a data DT in the database DB. The current value of DT is 1000:

  Time	A	B
  T1	READ(DT)
  T2	DT=DT+500
  T3	WRITE(DT)
  T4		DT=DT+300
  T5		WRITE(DT)
  T6	READ(DT)

• Transaction A initially reads the value of DT as 1000.

• Transaction A modifies the value of DT from 1000 to 1500, and then again transaction B modifies the value to 1800.

• Transaction A again reads DT and finds 1800 in DT; therefore, the update done by transaction A has been lost.

• Illustration:

  • Transaction A: DT = 1500 is lost/overridden by Transaction B: DT = 1800

• Graphical Illustration:

  • Transaction T1:
    • read_item(X);
    • $X = X - N$
  • Transaction T2:
    • read_item(X);
    • $X = X + M$
    • write_item(X);
    • read_item(Y);
    • $Y = Y + N$
    • write_item(Y);
  • Time write_item(X);
  • Item X has an incorrect value because its update by T1 is lost (overwritten).

Incorrect Summary Problem

• The Incorrect summary problem occurs when there is an incorrect sum of the two data. This happens when a transaction tries to sum two data using an aggregate function and the value of any one of the data get changed by another transaction.

• Example: Consider two transactions A and B performing read/write operations on two data DT1 and DT2 in the database DB. The current value of DT1 is 1000 and DT2 is 2000:

  Time	A	B
  T1	READ(DT1)
  T2	add=0
  T3	add=add+DT1
  T4		READ(DT2)
  T5		DT2=DT2+500
  T6	READ(DT2)
  T7	add=add+DT2

• Transaction A reads the value of DT1 as 1000.

• It uses an aggregate function SUM, which calculates the sum of two data DT1 and DT2 in variable add, but in between the value of DT2 get changed from 2000 to 2500 by transaction B.

• Variable add uses the modified value of DT2 and gives the resultant sum as 3500 instead of 3000.

• Illustration:

  • Figure 20.3 (c) The incorrect summary problem

Unrepeatable Read Problem

• The unrepeatable read problem occurs when two or more different values of the same data are read during the read operations in the same transaction.

• Example: Consider two transactions A and B performing read/write operations on a data DT in the database DB. The current value of DT is 1000:

  Time	A	B
  T1	READ(DT)
  T2		READ(DT)
  T3	DT=DT+500
  T4	WRITE(DT)
  T5		READ(DT)

• Transaction A and B initially read the value of DT as 1000.

• Transaction A modifies the value of DT from 1000 to 1500, and then again transaction B reads the value and finds it to be 1500.

• Transaction B finds two different values of DT in its two different read operations.

Phantom Read Problem

• In the phantom read problem, data is read through two different read operations in the same transaction. In the first read operation, a value of the data is obtained, but in the second operation, an error is obtained saying the data does not exist.

• Example: Consider two transactions A and B performing read/write operations on a data DT in the database DB. The current value of DT is 1000:

  Time	A	B
  T1	READ(DT)
  T2		READ(DT)
  T3	DELETE(DT)
  T4		READ(DT)

• Transaction B initially reads the value of DT as 1000.

• Transaction A deletes the data DT from the database DB, and then again transaction B reads the value and finds an error saying the data DT does not exist in the database DB.

Schedules

• Schedule: A sequence of instructions that specify the chronological order in which instructions of concurrent transactions are executed.
  • A schedule for a set of transactions must consist of all instructions of those transactions.
  • Must preserve the order in which the instructions appear in each individual transaction.
• The important read and write actions take place in the main-memory buffers, not the disk.
• The variables t and s are local variables of T1 and T2, respectively; they are not database elements.
• Multiple transactions are executed in order of sequence called schedule.
• Schedules are of two types: serial and parallel schedule
• Schedule (or history): When transactions are executing concurrently in an interleaved fashion, then the order of execution of operations from all the various transactions is known as a schedule (or history).
• 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.
• Example: Sa: r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y);

Conflicting Operations in a Schedule

Two operations in a schedule are said to conflict if they satisfy all three of the following conditions:

• (1) they belong to different transactions;
• (2) they access the same item X; and
• (3) at least one of the operations is a write_item(X).

20.5 Characterizing Schedules Based on Serializability

• A schedule S is serial if, for every transaction T participating in the schedule, all the operations of T are executed consecutively in the schedule; otherwise, the schedule is called non-serial.
• A schedule S of n transactions is serializable if it is equivalent to some serial schedule of the same n transactions.
• There are $n!$ possible serial schedules of n transactions and many more possible non serial schedules.
• A nonserial schedule S is serializable is equivalent to saying that it is correct, because it is equivalent to a serial schedule, which is considered correct.
  • nonserial schedule S is serializable when its = serial schedule

Serial Schedules

• A schedule is serial if its actions consist of all the actions of one transaction, then all the actions of another transaction, and SO on with no mixing of the actions.
• Precisely, a schedule S is serial if for any two transactions T and T1, if any action of T precedes any action of T1, then all actions of T precede all actions of T1.
• Serial schedule in which T1 precedes T2
• Serial schedule in which T2 precedes Tl
• We can represent a serial schedule as in listing each of the actions in the order they occur. However, since the order of actions in a serial schedule depends only on the order of the transactions themselves, we shall sometimes represent a serial schedule by the list of transactions. Thus, the schedule is represented $(\text{T i},\text{T 2})$, and that is $(\text{T2 } ,\text{Ti})$.

Serial vs. Non-Serial vs. Serializable Schedules

• Serial Schedule: A schedule where the operation of each transaction is executed consecutively without any interleaved operations from other transactions.
• NonSerial Schedule: A schedule where the operations from a set of concurrent transactions are interleaved.
• Serializable Schedule: The objective of serializability is to find non serial schedules that allow transactions to execute concurrently without interfering one another and thereby producing a database state that could be produced by serial execution. That means a non serial schedule is serializable and correct if it produces same result as some serial execution.
• There are two types of Serializability:
  • Conflict Serializability
  • View Serializability

Notation for Transaction and Schedules

T1: r1(A); w1(A); r1(B); w1(B);
T2: r2(A): w2(A); r2(B); w2(B);

Definition: Conflict-serializability

• Non-Conflict:
  • Different transaction + Different Data items.
  • Read on Same Data item.
• Conflict:
  • Write on Same data items + combination on Read operation.
  • R(A) R(A) – Non Conflict
  • R(A) W(A) – Conflict
  • W(A) R(A) – Conflict
  • W(A) W(A) - Conflict
  • R(B) R(A) – Non Conflict
  • W(B) R(A) – Non Conflict
  • R(B) W(A) – Non Conflict
  • W(A) W(B) – Non Conflict
• A schedule S1 is conflict-serializable iff:
• It can be transformed into a serial schedule by a sequence of non-conflicting swaps of adjacent actions.

Schedules in DBMS

Type of schedules in DBMS include:

• Serial Schedules
• Non-Serial Schedules
• Serializable
  • Conflict Serializable
  • View Serializable
• Non-Serializable
• Recoverable
• Non-Recoverable
• Cascading Schedule
• Cascadeless Schedule
• Strict Schedule

Serial Schedules VS Serializable Schedules

Conventions for Schedules

We can represent a schedule using a table with one column for each transaction, and operations are performed in the order given by reading from top to bottom.

We can also write a schedule on a single line using this notation:

rᵢ(A) = transaction Tᵢ reads A
wᵢ(A) = transaction Tᵢ writes A

example for the table above:
r1(A); r2(B); w1(A); r2(A); w2(A)

Example of a Conflict Serializable Schedule

r2(A); r1(A); r2(B); w1(A); w2(B); r1(B); w1(B)

r2(A); r2(B); r1(A); w1(A); w2(B); r1(B); w1(B)

r2(A); r2(B); r1(A); w2(B); w1(A); r1(B); w1(B)

r2(A); r2(B); w2(B); r1(A); w1(A); r1(B); w1(B)

The final schedule is referred to as an equivalent serial schedule.
serial - all of T2, followed by all of T1
equivalent - it produces the same results as the original schedule

Question 1

Convert the given schedule to serial schedule Thumb rule Adjacent operations from different transaction + different data items are Swapped as they are non-conflict pairs

Consider the following schedule: S₁ r₁ (A ) W₁ (A ) r₂ (A ) W₂ (A )r₁ (B ) w₁ (B )r₂(B ) W₂ (B )

We perform the following sequence of non-conflicting swaps:

S₁ r₁ (A ) W₁ (A ) r₂ (A ) W₂ (A )r₁ (B ) w₁ (B )r₂(B ) W₂ (B )
r₁ (A ) W₁ (A ) r₂ (A ) r₁ (B ) W₂ (A )w₁ (B )r₂ (B ) W₂ (B )
r₁ (A ) W₁ (A ) r₁ (B ) r₂ (A ) W₂ (A )w₁ (B )r₂ (B ) W₂ (B )
r₁ (A ) W₁ (A ) r₁ (B ) W₁ (B )r₂ (A ) W₂ (A )r₂ (B ) W₂ (B )
r₁ (A ) W₁ (A ) r₁ (B) w₁ (B )r₂ (A ) W₂ (A )r₂ (B ) W₂ (B )
and obtain a serial schedule !!!Conclusion:

The schedule:is a conflict-serializable schedule

Question 2: Testing for Conflict Serializability (cont.)

What about this schedule? r1(B); w1(B); r2(B); r2(A); w2(A); r1(A)

Which of the following pairs of actions from this schedule conflict?

A. r1(B); r2(B)
B. r1(B); W2(A)
C. W1(B); r2(B)
D. 2(B); 2(A)
E. W2(A); r1(A)

Fact:

Conflict-serializable schedule are always serializable

Reason: A conflict-serializable schedule is (always) a serializable schedule

Swapping two non-conflicting operations in a schedule will not change the effect of the execution of the operations in a schedule

Therefore: The effect of the execution of a conflict-serializable schedule is equivalent to the execution of a serial schedule of the transactions for every database state!!!

To check whether schedule is conflict serializablity:

• We need to do a precedence graph
• Number of vertex depends on number of transactions
• Check conflict pairs in other transactions and draw the edges
• Conflict pairs are R(X) W(X), W(X)R(X), W(X) W(X)
• Check in graph whether cycle is present.
• If no cycle then it is conflict serializable
• If it is conflict serializable then it is serial and consistent too.

Algorithm :

• Create a node T in the graph for each participating transaction in the schedule.
• 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.
• 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.
• 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.
• The Schedule S is serializable if there is no cycle in the precedence graph.

Equivalent Serial Schedule of Conflict Serializable Schedule

Conflict Serializable Schedule: A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations

Approach: Follow to below steps to find topological sorting of Precedence Graph:

• Find the indegree of all nodes for the given Precedence Graph and store it in an auxiliary array.
• Now For each node having indegree 0 perform the following:
  • Print the current node T as the order of the topological sort.
  • Let the node T be the node with in-degree 0.
  • Remove T and all edges connecting to T from the graph.
  • Update indegree of all nodes after the above steps.

Question 3: Precedence Graph

Check whether the given schedule S is conflict serializable or not-

S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)

Step-01: List all the conflicting operations and determine the dependency between the transactions

Step-02: Draw the precedence graph

Note – If RT(A) & WT(A) is in the same transaction then don’t add them in conflicting pairs

Solution 3: Precedence Graph

S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)

• Step1 : Conflicting pairs
• R2(A) → W1(A) ; T2→T1
• R1(B)→ W2(B) ; T1→T2
• R3(B) →W2(B) ; T3→T2
• Draw the precedence graph Clearly, there exists a cycle in the precedence graph.
• Therefore, the given schedule S is not conflict serializable.

Question 4: Precedence Graph

Check whether the given schedule S is conflict serializable

Step1 : Find all the Conflicting pairs between the transaction

Step-02: Draw the precedence graph

• List all the conflicting operations and determine the dependency between the transactions-
• R2(X) , W3(X) (T2 → T3)
• R2(X) , W1(X) (T2 → T1)
• W3(X) , W1(X) (T3 → T1)
• W3(X) , R4(X) (T3 → T4)
• W1(X) , R4(X) (T1 → T4)
• W2(Y) , R4(Y) (T2 → T4)
• Clearly, there exists no cycle in the precedence graph. Therefore, the given schedule S is conflict serializable.

Question 5 Precedence Graph

Check whether the given schedule S is conflict serializable or not. If yes, then determine all the possible serialized schedules

List all the conflicting operations and determine the dependency between the transactions-

• R4(A) , W2(A) (T4 → T2)

• R3(A) , W2(A) (T3 → T2)

• W1(B) , R3(B) (T1 → T3)

• W1(B) , W2(B) (T1 → T2)

• R3(B) , W2(B) (T3 → T2)

• Clearly, there exists no cycle in the precedence graph.

• Therefore, the given schedule S is conflict serializable

• After performing the topological sort, the possible serialized schedules are-

  1. T1 → T3 → T4 → T2
  2. T1 → T4 → T3 → T2
  3. T4 → T1 → T3 → T2

Question 6

Conflict Serial Schedule be: S: R2(A) W2(A) R3(C) W2(B) W3(A) W3(C) R1(A) R2(B) W1(A) W2(B) Equivalent Serial Schedule is : T2 T3 T1

• Here node T2 has indegree 0. So, select T2 and remove T2 and all edges connecting from it.
• Now T3 has indegree 0