Unit 8: Introduction to Transaction Processing - ACID, States, and Serializability

Introduction to Transaction Processing

In a Database Management System (DBMS), a transaction is a logical unit of database processing that includes one or more database access operations. These operations typically include insertion, deletion, modification, or retrieval of data.

From the perspective of the DBMS, a transaction is a sequence of operations that must be treated as a single, indivisible unit. A transaction starts with a "Begin Transaction" statement and ends with either a "Commit" (successful completion) or a "Rollback" (unsuccessful completion where changes are undone).

Single-user vs. Multi-user Systems

• Single-user System: Only one user can access the database at a time. There is no need for complex concurrency control.
• Multi-user System: Multiple users can access the database simultaneously. This requires sophisticated mechanisms to ensure that concurrent operations do not interfere with each other, leading to data inconsistency.

Desirable Properties of Transactions (ACID Properties)

To ensure the integrity of the database, every transaction must follow the ACID properties. This is a core topic for TU/PU exams.

1. Atomicity

Atomicity follows the "all or nothing" rule. A transaction is a single unit of work; either all its operations are performed, or none are. If a transaction fails halfway through (e.g., due to a power failure), the DBMS must undo (rollback) any changes made by that transaction to restore the database to its previous consistent state.

2. Consistency

A transaction must transform the database from one consistent state to another consistent state. It is the responsibility of the programmer and the DBMS to ensure that the transaction does not violate any integrity constraints (like primary key uniqueness or foreign key relationships).

3. Isolation

Even though multiple transactions may execute concurrently, the system should guarantee that each transaction is unaware of other transactions executing simultaneously. The intermediate effects of a transaction should not be visible to others until it is committed.

4. Durability

Once a transaction has been committed, its changes must be permanent and survive any subsequent system failures (like a crash or power loss). This is usually achieved by recording the changes in a non-volatile transaction log.

---

Transaction States and State Transitions

A transaction does not jump directly from start to finish. It passes through several states during its lifetime.

       +-----------+           +-------------------+           +-----------+
       |  Active   |---------->| Partially Committed|---------->| Committed |
       +-----------+           +-------------------+           +-----------+
             |                         |                             ^
             |                         |                             |
             v                         v                             |
       +-----------+           +-----------+                         |
       |  Failed   |---------->|  Aborted  |-------------------------+
       +-----------+           +-----------+

1. Active: The initial state. The transaction stays in this state while it is executing its read and write operations.
2. Partially Committed: This state is reached after the final statement of the transaction has been executed. However, the changes are still in the main memory (buffers) and not yet permanently saved on the disk.
3. Committed: After the DBMS ensures that all operations are successful and the log records are written to the disk, the transaction enters the committed state. The changes are now permanent.
4. Failed: If a transaction cannot proceed due to internal errors (like division by zero) or system errors, it enters the failed state.
5. Aborted: Once a transaction fails, the DBMS performs a "Rollback" to undo any changes made by the transaction. After the rollback, the transaction is in the aborted state. The system can then either restart the transaction or kill it.

---

Concurrency Control: Why do we need it?

When multiple transactions run concurrently, several problems can arise if they are not controlled.

1. The Lost Update Problem

This occurs when two transactions that access the same data item have their operations interleaved in a way that makes the value of some data item incorrect. Example: T1 reads balance (1000), T2 reads balance (1000). T1 adds 100 and writes (1100). T2 adds 200 and writes (1200). The update by T1 is "lost".

2. The Temporary Update (Dirty Read) Problem

This occurs when one transaction updates a data item and then the transaction fails for some reason. Meanwhile, the updated item is read by another transaction before it is changed back to its original value. Example: T1 updates balance to 2000. T2 reads balance as 2000. T1 fails and rolls back balance to 1000. T2 is now working with "dirty" (incorrect) data.

3. The Incorrect Summary Problem

If one transaction is calculating an aggregate summary function (like SUM) on a number of records while other transactions are updating those same records, the aggregate function may calculate some values before they are updated and others after they are updated.

---

Schedules and Serializability

A Schedule is a sequence of operations (Read, Write, Commit, Abort) from a set of concurrent transactions that preserves the order of operations within each individual transaction.

Types of Schedules

1. Serial Schedule: A schedule where transactions are executed one after another. If T1 and T2 are two transactions, a serial schedule is either (T1 followed by T2) or (T2 followed by T1). Serial schedules always leave the database in a consistent state but result in poor performance.
2. Non-serial Schedule: A schedule where the operations of T1 and T2 are interleaved. This improves throughput but can lead to inconsistency.
3. Serializable Schedule: A non-serial schedule that produces the same result as some serial execution of the same transactions. Serializability is the criterion for correctness in concurrency control.

Conflict Serializability

Two operations are said to be in conflict if:

1. They belong to different transactions.
2. They access the same data item.
3. At least one of them is a Write operation.

A schedule is Conflict Serializable if it is conflict-equivalent to some serial schedule. We can check this using a Precedence Graph.

Worked Example: Precedence Graph

Consider a schedule S with transactions T1 and T2:

• T1: Read(X), Write(X)
• T2: Read(X), Write(X)

Steps to draw Precedence Graph:

1. Create a node for each transaction (T1, T2).
2. Draw an edge from $T_i$ to $T_j$ if an operation in $T_i$ conflicts with an operation in $T_j$ and $T_i$ occurs earlier in the schedule.
3. If the graph contains a cycle, the schedule is NOT conflict serializable. If there is no cycle, it is serializable.

---

Transaction Deadlocks

A Deadlock occurs when two or more transactions are in a simultaneous wait state, each waiting for one of the others to release a resource (lock).

Example of Deadlock

• T1 holds a lock on Data Item A and requests a lock on Data Item B.
• T2 holds a lock on Data Item B and requests a lock on Data Item A.
• Both transactions will wait forever.

Deadlock Handling Techniques

1. Deadlock Prevention:
   • Wait-Die Scheme: If a transaction requests a resource held by another, the requesting transaction is allowed to wait only if it is older than the holding transaction. If it is younger, it is aborted (dies).
   • Wound-Wait Scheme: If an older transaction requests a resource held by a younger one, the older transaction "wounds" (aborts) the younger one. If the requester is younger, it waits.
2. Deadlock Detection and Recovery:
   • The system maintains a Wait-for Graph. Nodes represent transactions. An edge $T_1\to T_2$ exists if $T_1$ is waiting for a resource held by $T_2$.
   • If a cycle is detected in the graph, a deadlock exists.
   • Recovery: Select a "victim" transaction to abort and rollback to break the cycle.

---

Comparison: File System vs. DBMS Approach

This is a frequent question in TU exams, often asked in the context of why we need transaction management.

---

Summary of Transaction Operations

• Read_item(X): Reads a database item named X into a program variable.
• Write_item(X): Writes the value of a program variable into the database item X.
• Commit: Signals that the transaction has ended successfully and changes should be permanent.
• Rollback (Abort): Signals that the transaction has ended unsuccessfully and changes should be undone.

---

Exam Tip

• ACID Properties: This is the most important question. Always define each letter (A, C, I, D) and give a small example (like a bank transfer) to illustrate.
• Transaction States: Be prepared to draw the state transition diagram. Label the arrows correctly.
• Serializability: Practice drawing precedence graphs. Remember: Cycle = Not Serializable.
• Deadlock: Differentiate between "Wait-Die" and "Wound-Wait". Students often confuse these two.
• Short Notes: "Transaction Log" and "Conflict Serializability" are common short-note topics.
• Past Question Note: If asked to differentiate between File System and DBMS, use a table format as shown above for better marks.