60.701 Transaction Processing in Relational Databases

Objectives

Upon completion of this lesson, you will be able to:

explain the need for transactions
describe the ACID properties for transactions
define isolation levels
draw precedence graphs for serializability

Overview

Concurrency and transactions are essential concepts in relational databases, ensuring data integrity and consistency, especially in environments with multiple users or processes accessing the database simultaneously. Concurrency refers to the ability of the database to allow multiple users or processes to access and modify the data at the same time. When multiple accesses from different users or applications try to access the same data concurrently, there’s a risk of conflicts, leading to data inconsistencies. Transactions can help address this problem by ensuring that the database modifications are done in such a way that the database remains consistent.

Transactions

In the context of database management systems (DBMS), a transaction is a sequence of operations performed as a single logical unit of work that accesses and possibly modifies various data items. A transaction must adhere to the ACID properties, which are:

Atomicity: This property ensures that all operations within the transaction are completed successfully. If any operation in the transaction fails, the entire transaction is aborted, and the database state is left unchanged as if the transaction was never initiated. Essentially, a transaction is “all or nothing.”
Consistency: This property ensures that a transaction changes the database from one consistent state to another consistent state. Consistency rules are defined by the constraints, triggers, and schema definitions in the database. The transaction does not violate any integrity constraints during its execution.
Isolation: This property ensures that the intermediate state of a transaction is invisible to other transactions. Transactions appear to be executed in isolation from each other, even if they are executed concurrently. This property prevents transactions from interfering with each other.
Durability: Once a transaction has been committed, its changes are permanent in the database, even in the event of system failures. This property ensures that the results of the transaction are preserved despite any subsequent system crashes or errors.

Transactions are essential for maintaining the integrity and consistency of the database, especially in systems that support concurrent access by multiple users or applications. They allow complex operations to be executed safely and reliably, ensuring that the database remains in a valid state even in the face of errors or failures.

Motivating Example

Transactions are required in scenarios where multiple operations on a database must be executed as a single, atomic unit to maintain data integrity and consistency. Any other user of a database will only see the state of the database before the transaction started and then see the revised state when the transaction completed successfully. No intermediary states are visible to anyone except the program executing the transaction. If other users were to be able to see the database states during a transaction, they would see that the database might have inconsistent values or foreign key references.

A classic motivating example involves a banking system, specifically during a fund transfer operation between two accounts. This example highlights the necessity of transactions to ensure atomicity, consistency, isolation, and durability (ACID properties) in database operations.

Example Scenario: Bank Fund Transfer

Imagine a simple operation where a bank customer wants to transfer $100 from their savings account to their checking account. This operation involves two main steps:

Debit (withdraw) $100 from the savings account.
Credit (deposit) $100 to the checking account.

Without Transactions

Without using a transaction, if the system fails (due to power failure, system crash, etc.) after completing the first step (debiting the savings account) but before the second step (crediting the checking account), the money would be withdrawn from the savings account without being deposited into the checking account. This would result in lost funds for the customer, violating the integrity of the bank’s data.

With Transactions

Using a transaction ensures that both steps are treated as a single, atomic operation. The process would look like this:

Begin Transaction: Start the transaction to group the following operations.
Debit $100 from the savings account: Check if the savings account has enough funds. If yes, proceed; otherwise, abort the transaction.
Credit $100 to the checking account: Add the money to the checking account.
Commit Transaction: If both steps are successful, commit the transaction to make the changes permanent.
Rollback if Necessary: If there’s a failure at any point before the commit, rollback the transaction to undo any changes made since the transaction began, ensuring no incomplete operation affects the database.

Why Transactions Are Necessary

Atomicity: Guarantees that all steps in the fund transfer are completed successfully as a single unit of work. If any step fails, the entire transaction is aborted, and the accounts are left unchanged.
Consistency: Ensures the transaction moves the database from one consistent state (correct total funds across accounts) to another, maintaining all balance invariants.
Isolation: Protects the transaction from interference by other operations, ensuring that intermediate states are not visible to other transactions and that transactions appear to be executed in sequence.
Durability: Once the transaction is committed, the changes (the fund transfer) are guaranteed to be permanent, even in the case of a system failure.

This example underscores the importance of transactions in maintaining the integrity and consistency of data, especially in systems where accurate and reliable operations on data are critical, such as in financial systems.

ACID vs BASE vs CAP

Note that many non-relational (NoSQL) database management systems do not support ACID, but may support the BASE properties. NoSQL databases generally adhere to Brewer’s CAP Theorem.

The concepts of ACID, BASE, and the CAP Theorem are fundamental in the context of database systems, each providing a different perspective on data consistency, availability, and the handling of transactions, especially in distributed systems. BASE and CAP are intended for distributed databases where achieving ACID may be extremely difficult.

BASE Model

BASE stands for Basically Available, Soft state, and Eventual consistency. It is a model designed for distributed systems, emphasizing availability and partition tolerance, often at the expense of immediate consistency.

Basically Available indicates that the system guarantees availability.
Soft state means that the state of the system may change over time, even without input.
Eventual Consistency ensures that if the system does not receive any new updates for a certain period, all replicas will gradually become consistent.

BASE is more flexible than ACID in terms of consistency to achieve higher availability and scalability in distributed systems, such as NoSQL databases. However, this is at the expense of occasional inconsistencies, so it is only useful when such temporary inconsistencies can be tolerated.

CAP Theorem

The CAP Theorem, proposed by Eric Brewer in a keynote speech at the Symposium on Principles of Distributed Computing (PODC) in 2000 and formalized by Seth Gilbert and Nancy Lynch ([2]), states that a distributed system can only simultaneously achieve two out of the following three guarantees:

Consistency (all nodes see the same data at the same time),
Availability (every request receives a response about whether it was successful or failed),
Partition Tolerance (the system continues to operate despite physical network partitions).

This theorem outlines the trade-offs involved in distributed system design, forcing a choice between consistency and availability when network partitions occur.

Comparison of ACID and BASE within the Context of CAP

ACID vs. BASE: ACID focuses on transaction reliability and consistency within single database systems, making it more aligned with the “Consistency” aspect of the CAP Theorem. On the other hand, BASE accepts that “Consistency” can be relaxed and opts for a more flexible approach, aligning with “Availability” and “Partition Tolerance” of CAP. BASE is suitable for distributed systems where immediate consistency is less critical than availability.
Applicability: ACID properties are often applied in traditional relational databases where transaction integrity is crucial, such as financial systems. BASE is applied in distributed databases, where the system must scale and remain highly available, such as social networks or e-commerce platforms with distributed data stores.

Overall, ACID and BASE represent two ends of the spectrum in database design, with ACID prioritizing consistency and reliability and BASE emphasizing availability and scalability. The CAP Theorem highlights the inherent trade-offs in distributed systems, showing that design choices depend on the application’s specific requirements for consistency, availability, and tolerance to network partitions.

The remainder of this lesson concerns itself with ACID Transaction and use cases where complete consistency is required

Programming Transactions

Databases initiate transactions using specific commands or APIs provided by the database management system (DBMS). The exact method can vary depending on the DBMS being used (such as MySQL, PostgreSQL, Oracle, SQL Server, etc.), but the core concept remains consistent. Here’s a general overview of how transactions are initiated in databases:

SQL-Based Databases

In SQL-based databases, a transaction is typically initiated with the BEGIN TRANSACTION or simply BEGIN command. This command signals the start of a transaction block, within which all subsequent operations are part of the same transaction until it is explicitly committed or rolled back. Here’s a basic flow:

Start the Transaction: The transaction begins with the BEGIN TRANSACTION command.
```
BEGIN TRANSACTION;
```
Perform Operations: After initiating the transaction, you can execute multiple SQL operations such as INSERT, UPDATE, DELETE, etc., that form the transaction’s body.
Commit or Rollback: Depending on the success of the operations within the transaction, it can be either committed using the COMMIT command, which saves all changes to the database, or rolled back using the ROLLBACK command, which undoes all changes made in the transaction.
```
COMMIT; -- or ROLLBACK;
```

APIs in Application Code

When interacting with a database through application code (e.g., using object-relational mapping (ORM) libraries or database drivers in languages like Python, R, Java, C#, etc.), transactions are often initiated through method or function calls defined by the library, package, or driver. For example:

Python (with SQLAlchemy ORM):

from sqlalchemy import create_engine
from sqlalchemy.orm import sessionmaker

engine = create_engine('database_url')
Session = sessionmaker(bind=engine)
session = Session()

session.begin() # Start the transaction
try:
    # Perform database operations...
    session.commit() # Commit if successful
except:
    session.rollback() # Rollback in case of error
    raise
finally:
    session.close() # Close the session

Java (with JDBC):

Connection conn = DriverManager.getConnection("jdbc:database_url", "username", "password");

try {
    conn.setAutoCommit(false); // Disable auto-commit to start the transaction
    // Perform SQL operations...
    conn.commit(); // Commit the transaction
} catch (SQLException e) {
    conn.rollback(); // Rollback the transaction on error
} finally {
    conn.close(); // Close the connection
}

The initiation of a transaction marks the beginning of a sequence of operations to be treated as a single logical unit. The ability to explicitly manage transactions allows developers and database administrators to ensure data integrity and consistency, especially in complex operations or in environments with concurrent data access.

State Machine for a Transaction

Whenever a transaction is initiated in a database, it either completes successfully or it fails (for some reason). Throughout its execution process, the transaction transitions through several distinct states: active, partially committed, committed, failed, and aborted. The state transition diagram, depicted below, illustrates the progression of a transaction through these various stages during its execution.

The initial (or start) state of a transaction is the active state, entered into with the BEGIN_TRANSACTION operation; it signals the start of its execution. In this phase, two or more read or write operations are performed on the database as part of the transaction. The READ operation moves a data item from the database to the transaction’s local buffer, while the WRITE operation transfers the data item from the local buffer back to the database.

Upon completing its final operation, the application signifies the end of the transaction with an END_TRANSACTION operation, transitioning the transaction into a partially committed state. At this stage, the outcome might still reside in main memory, vulnerable to hardware failures that could impede completion, potentially necessitating an abortion of the transaction.

Before updating the database on the disk, the database engine logs the transaction’s updates in a log file, ensuring that any updates can be reconstructed following a system restart after a failure or crash; of course, the log must be committed to disk – the transaction log is generally stored outside the database store. The transaction ends with the COMMIT_TRANSACTION operation but only once the log is successfully written. That indicates its successful conclusion and at that time all modifications are permanently committed to the database and other users can now see all changes.

Should the transaction need to be aborted during its active phase or if logging the changes fails, it shifts to a failed state. That triggers a rollback to the state before the transaction was started; this will undo any and all database changes to preserve consistency.

Aborted transactions may restart automatically by the system for recoverable errors like hardware or software issues, but not for internal logical or transaction programming errors. Transactions aborted due to internal logic issues or missing database data must be terminated explicitly by the programmer. Users must correct any transaction errors before resubmitting it as a new transaction for execution.

Compensating Transactions

In some (rare) cases, a transaction may need to conduct write operations to an external system or device, such as a partner’s system in an integrated B2B supply chain, or perhaps to a printer. These operations, termed “observable external writes”, are irreversible once executed on these devices. Consequently, the database system permits such operations exclusively after the transaction has achieved a committed status.

It is important to note that the effects of a committed transaction are irreversible through aborting. The sole method to counteract the effects of a committed transaction is by implementing a compensating transaction, which negates the original transaction’s effects. For instance, to counterbalance a transaction that deposited $100 into an account, a compensating transaction would withdraw $100 from the same account.

Nonetheless, crafting a compensating transaction isn’t always feasible. Hence, the onus lies on the programmer, rather than the database system, to develop and execute any necessary compensating transactions.

Concurrent Transactions

Different applications connected to the same database may all need to execute transactions and the database allows those transactions to execute at the same time in order to improve performance. Of course, this requires careful coordination to ensure that the database is not corrupted.

The transaction-processing subsystem within the database management system (DBMS) facilitates the concurrent execution of multiple transactions to enhance overall system performance. Remember that transactions are initiated by the client application but are actually executed within the database server. During concurrent execution, the database management system orchestrates the simultaneous execution of two or more transactions, ensuring that only one operation from any given transaction is executed at a time. This process is commonly referred to as interleaved execution. The rationale behind allowing concurrent transaction execution is twofold.

Firstly, transactions that engage in read or write operations involving I/O devices may not utilize the CPU at that time and thus allow another process to use the CPU for data processing. Therefore, when one transaction is occupied with I/O operations, the CPU can efficiently allocate its resources to another transaction. The parallel use of CPU and I/O systems enables the overlapping of I/O and CPU activities, significantly reducing idle times for storage devices and processors. Consequently, this overlap boosts the system’s throughput, which is generally taken as the number of transactions processed within a specified time frame, such as transactions per minute (TPM).

Secondly, interleaving the execution of transactions of varying lengths — particularly short and long transactions — facilitates quicker completion of shorter transactions. In a serial execution model, where transactions are processed one after another, shorter transactions might experience substantial delays if queued behind longer transactions. By allowing transactions to execute concurrently, the system minimizes these avoidable delays, thereby lowering the average response time for transactions.

However, it is important to acknowledge that while individual transactions may be correct in isolation, improper interleaving of operations from multiple transactions can lead to inconsistencies within the database. To prevent such issues, the DBMS must ensure that the outcome of concurrently executed transactions is equivalent to some serial execution of the same transactions. To manage the interactions among concurrently executing transactions and maintain database integrity, the DBMS employs various concurrency control techniques. These techniques include locking mechanisms, timestamp ordering, and multiversion concurrency control (MVCC), among others. Each technique has its approach to ensuring that concurrent transactions do not interfere destructively, thereby preserving the ACID properties (Atomicity, Consistency, Isolation, Durability) essential for reliable database operation.

Interleaving Anomalies

When transactions are interleaved without careful consideration, it may cause several types of anomalies, including lost updates, dirty reads, and unrepeatable reads, which can compromise database integrity. To illustrate the impact of these anomalies, let’s consider two transactions, T₁ and T₂. Transaction T₁ is responsible for transferring $100 from account A to account B, while T₂ applies a 2% interest rate to account A’s balance. Initially, account A has a balance of $2000, and account B has $1500. After executing T₁ followed by T₂ in sequence, the expected final balances should be $1938 for account A and $1600 for account B.

However, complications arise when the operations of T₁ and T₂ are improperly interleaved. For example, if T₂ reads the balance of account A before T₁ has the chance to update it, and then T₂ applies its update based on this outdated information, the update made by T₁ can be overwritten. This scenario, known as the lost update anomaly, results in an incorrect final balance of $2040 for account A, diverging from the expected $1938, thus leading to data inconsistency.

Another issue, the dirty read anomaly, occurs if T₁ fails after debiting $100 from account A but before it can credit account B. If the system does not revert account A’s balance before another transaction, say T₂, reads it, T₂ may operate on this incorrect balance. This premature access to uncommitted data, termed a dirty read, leaves the database in an inconsistent state when T₁ is eventually rolled back.

The third anomaly, unrepeatable reads, takes place when a transaction, let’s call it T₃, reads the same data item twice, and another transaction, say T₄, updates that data item in the meantime. As a result, T₃ encounters different values for the same data item across its reads, leading to inconsistencies within its execution context.

These anomalies are fundamentally caused by conflicts in the actions of concurrent transactions. Specifically, the lost update reflects a write-write (WW) conflict, where two transactions attempt to update the same data item. The dirty read represents a write-read (WR) conflict, where one transaction reads another transaction’s uncommitted changes. Lastly, the unrepeatable read scenario illustrates a read-write (RW) conflict, where an update conflicts with an earlier read, making it impossible to repeat the read with the same result.

To mitigate these issues, database systems implement concurrency control mechanisms, such as locking protocols, timestamp-based methods, or multiversion concurrency control (MVCC). These mechanisms aim to sequence transaction operations in a way that preserves data consistency, ensuring that the results of concurrent transaction execution are equivalent to some serial order of the same transactions, thereby maintaining the integrity and reliability of the database system.

Transaction Schedules

A schedule, or history, in this context, refers to a sequence of operations – such as read, write, abort, or commit – carried out by a set of transactions. This sequence must include all operations from the involved transactions while maintaining the order of these operations as they are defined within each transaction. The purpose of a schedule is to document the execution sequence of multiple transactions, ensuring that the integrity and logic of each transaction are preserved throughout the process.

To elaborate, let’s examine an example involving two transactions, T₁ and T₅. Transaction T₁ is tasked with transferring $100 from account A to account B, whereas T₅ handles the transfer of $50 from account B to account C. Let’s assume that, initially, the balances in accounts A, B, and C are $2000, $1500, and $500, respectively, totaling $4000 across the three accounts.

Executing these transactions in a serial manner – first T₁ and then T₅ – results in what is known as a serial schedule. A serial schedule is a type of schedule where the operations from a single transaction are executed consecutively without intermixing with operations from other transactions. Consequently, for a group of $n$ transactions, there are $n!$ (factorial of $n$) possible valid serial schedules, each representing a different order of transaction execution.

In the given example, the execution sequence is organized chronologically. The operations of T₁ are done first, followed by those of T₅. This ordering results in the updated balances of accounts A, B, and C being $1900, $1550, and $550, respectively, after both transactions are completed. Notably, the total sum of $4000 across accounts A, B, and C remains unchanged, preserving the overall financial integrity.

Alternatively, executing T₅ before T₁ represents another valid serial schedule. This sequence would also maintain the total sum across accounts A, B, and C, demonstrating the flexibility of serial schedules in ensuring data consistency regardless of the execution order. Such serial execution guarantees the absence of concurrency-related anomalies, ensuring that each transaction’s effects are isolated from others and that the database remains in a consistent state throughout the transactional processes.

A schedule, which outlines the sequence of operations performed by transactions in a database, can be efficiently represented using shorthand notation. This notation employs specific symbols to denote the fundamental operations critical to transaction processing, recovery, and concurrency control. These symbols are:

r for read operations, which retrieve data from the database,
w for write operations, which modify data in the database,
c for commit operations, signaling the successful completion of a transaction, and
a for abort operations, indicating the termination of a transaction without applying its changes due to an error or a specific condition not being met.

To distinguish between transactions when they perform these operations, the transaction identifier (ID) is attached as a subscript to each operation symbol in the schedule. For instance, if transaction 1 reads from a data item, it would be denoted as $r_1$, and if transaction 2 writes to a data item, this would be represented as $w_2$.

For example, a sample schedule $S_1$ for two transactions $T_1$ and $T_2$ is shown below:

$S_1: r_1(A); w_1(A); r_1(B); w_1(B); r_5(B); w_5(B); r_5(C); w_5(C);$

where A, B, and C are the database objects being operated on (accounts A, B, and C in this example). What the actual operations are does not matter from a scheduling perspective; only knowing what kind of operation it is, is sufficient.

This shorthand notation simplifies the depiction of schedules, making it easier to analyze the sequence of operations and their interactions. It’s particularly useful for illustrating and understanding the concepts of recovery and concurrency control in database systems. By examining these notations, database engineers can identify potential conflicts between transactions, assess the need for rollback or commit actions, and implement appropriate concurrency control mechanisms to ensure database integrity and consistency.

In a serial schedule, each transaction is executed sequentially, ensuring that it runs in isolation without any overlap with the operations of other transactions. This isolation guarantees that as long as each transaction is allowed to proceed from start to finish without interruption, the final outcome on the database will be accurate and consistent. Consequently, serial schedules are inherently considered correct and reliable, as they prevent the complexities and potential anomalies associated with concurrent transaction executions.

Despite their correctness, serial schedules operate under the constraint that only one transaction can be active at any given moment. The completion of one transaction, marked by either a commit or an abort operation, triggers the commencement of the next transaction in the queue. This strict sequential order means that transactions are not executed concurrently, leading to certain inefficiencies. For example, if the currently active transaction requires a prolonged I/O operation, the CPU resources remain underutilized, as no other transaction can proceed during this time to make use of the CPU. This results in unnecessary CPU idle time, diminishing the overall throughput of the system.

Furthermore, the sequential nature of serial schedules introduces another significant drawback: if any transaction in the sequence is particularly lengthy, subsequent transactions are forced to wait until it completes. This wait time can be substantial, leading to delays in processing other transactions and, ultimately, to reduced system responsiveness and efficiency.

Therefore, while serial schedules ensure correctness and consistency in the outcomes of transactions, their limitations in terms of resource utilization and system throughput render them impractical for environments requiring high performance and concurrency. These drawbacks underscore the need for more sophisticated scheduling techniques that can balance correctness with efficiency, such as those enabling concurrent execution while managing the challenges of data consistency and isolation. This requires schedules that can be interleaved but behave as if they were serialized, i.e., serializable schedules.

Serializable Schedules

In multi-user database systems, the concurrent execution of multiple transactions is a common practice aimed at optimizing system resource utilization. This concurrency involves the operating system allocating CPU time to a transaction for a certain period before switching context to another transaction. This cycle of allocation and context switching continues, allowing multiple transactions to share CPU resources simultaneously. The resulting interleaved execution pattern forms what is known as a non-serial schedule, where operations from different transactions are intermixed rather than executed in a strict sequential order.

However, entrusting the operating system with the sole responsibility for managing the concurrent execution of transactions could lead to the generation of schedules that compromise the database’s consistency. It is, therefore, incumbent upon the database system’s concurrency control component to oversee the execution process. This component’s role is to guarantee that only those schedules that maintain the database’s consistent state are allowed to proceed. This involves implementing sophisticated algorithms and mechanisms that can intelligently orchestrate the interleaving of transactions while safeguarding against data anomalies and inconsistencies.

Predicting the exact sequence and extent of operations for each transaction before a CPU switch occurs is inherently unpredictable. Given $n$ transactions, the sheer number of potential non-serial schedules exponentially exceeds $n!$, illustrating the complexity and variability of possible execution paths. However, it’s crucial to note that not all these non-serial schedules are viable; many can lead to incorrect database states. The challenge lies in identifying and executing only those non-serial schedules that ensure data integrity and consistency, a task that requires meticulous control and sophisticated concurrency management strategies.

This complexity underscores the importance of the concurrency control component within database systems, particularly in environments with high levels of parallel transaction processing. By carefully managing transaction interleaving, database systems can achieve high throughput and efficiency without sacrificing the correctness and consistency of the database.

Maintaining database consistency during concurrent transaction execution involves carefully interleaving the operations of multiple transactions. The goal is to ensure that the end result mirrors that of a sequence where these transactions are executed one after the other, without any overlap—a concept known as a serial schedule. When a schedule achieves this level of consistency and predictability, it is termed a serializable schedule. Essentially, a serializable schedule for a set of $n$ transactions $T1, T2, T3, \ldots, Tn$ is one that is equivalent in outcome to a serial schedule of the same $n$ transactions, despite the interleaved execution of their operations.

Example of Serializable Schedule

Consider two transactions, $T1$ and $T2$, operating on a database with two accounts, Account A and Account B, initially holding $1000 each.

Transaction $T1$: Transfers $100 from Account A to Account B.
Transaction $T2$: Applies a 10% interest rate to both accounts.

A serial execution might process $T1$ first and then $T2$, resulting in the following steps:

$T1$ reduces Account A to $900 and increases Account B to $1100.
$T2$ then applies a 10% interest, making Account A $990 and Account B $1210.

Alternatively, executing $T2$ first and then $T1$ would result in:

$T2$ increases Account A to $1100 and Account B to $1100 due to the interest rate.
$T1$ then transfers $100, making Account A $1000 and Account B $1200.

Both sequences are serial schedules, leading to different outcomes due to the nature of the transactions.

A serializable schedule might interleave these operations but still produce an outcome equivalent to one of these serial schedules. For instance:

$T1$ starts by deducting $100 from Account A (Account A = $900).
Then, $T2$ applies a 10% interest rate to Account A ($900 + 10% = $990) and Account B ($1100 + 10% = $1210).
Finally, $T1$ completes by adding $100 to Account B (but since $T2$ has already applied the interest, this step is conceptually merged with the interest application).

This interleaved execution results in Account A having $990 and Account B $1210, equivalent to executing $T1$ followed by $T2$ serially. Thus, this schedule is serializable because it achieves an end state that matches one of the possible serial executions, maintaining database consistency despite the concurrent execution of transactions.

Schedule Equivalence

In the realm of database systems, particularly under the context of concurrent transaction execution, it’s possible for distinct schedules to lead to identical final states of the database. These schedules are termed “result equivalent” because, despite potentially differing sequences of operations, their effects on the database are indistinguishable, culminating in the same final data configuration. Result equivalence underscores the idea that the order of certain operations can vary without altering the outcome, highlighting the flexibility and complexity of managing transaction executions in a concurrent environment.

Example of Result Equivalent Schedules

Consider a database with two records: Record X and Record Y, initially both set to 10.

Transaction $T1$: Increments the value of Record X by 5.
Transaction $T2$: Doubles the value of Record Y.

Schedule 1:

$T1$ increments Record X (X = 15).
$T2$ doubles Record Y (Y = 20).

Schedule 2:

$T2$ doubles Record Y (Y = 20).
$T1$ increments Record X (X = 15).

Both Schedule 1 and Schedule 2 are result equivalent since they independently achieve the same end state: Record X at 15 and Record Y at 20, despite the different order of operations. This equivalence demonstrates that the specific sequence of these transactions does not impact the final state of these particular records.

Accidental Result Equivalence

However, there are scenarios where two schedules might unexpectedly lead to the same database state, not through the inherent design of the transactions but rather by coincidence. For instance:

Transaction $T3$: Sets Record X to the current value of Record Y plus 5.
Transaction $T4$: Sets Record Y to the current value of Record X plus 5.

Accidental Schedule 1:

$T3$ sets Record X to 15 (X = Y + 5, with Y initially 10).
$T4$ sets Record Y to 20 (Y = X + 5, with X now 15).

Accidental Schedule 2:

$T4$ sets Record Y to 15 (Y = X + 5, with X initially 10).
$T3$ sets Record X to 20 (X = Y + 5, with Y now 15).

In this case, both schedules achieve a state where Record X is 20 and Record Y is 15, but the paths taken are not inherently predictable or designed to be equivalent. Instead, the particular initial values and the operations’ nature accidentally lead to the same outcome. This accidental result equivalence highlights the nuanced challenge of managing and predicting the outcomes of concurrent transactions in database systems, necessitating robust concurrency control mechanisms to ensure consistency and integrity.

Conflict Equivalence and Conflict Serializability

In a schedule, operations are considered to conflict when they originate from separate transactions, target the same data item, and at least one of the operations involves updating ($w$ operation) that data item. Conversely, operations from different transactions do not conflict if they are both read operations or if they target different data items. To illustrate the notion of conflicting operations, let’s examine transactions $T_3$ and $T_4$, which modify data items Q and R in the database.

Consider a hypothetical schedule $S_2$, where write(Q) of $T_3$ conflicts with read(Q) of $T_4$. This conflict arises because both operations interact with the same data item, Q, and one of these is a write operation. However, the write(Q) operation of $T_4$does not conflict with the read(R) operation of $T_3$, as they involve different data items, Q and R, respectively.

The sequencing of conflicting operations is critical, as altering their order can impact the database’s state or affect other transactions within the schedule. For instance, if the write(Q) operation of $T_3$ precedes the read(Q) operation of $T_4$, the data read by $T_4$ could differ. In contrast, the execution order of non-conflicting operations is inconsequential. This means swapping $T_4$’s write(Q) operation with $T_3$’s read(Q) operation results in a new schedule that retains the same impact on the database as Schedule $S_2$. This example underscores the importance of understanding and managing conflicting operations within transaction schedules to ensure database consistency and integrity.

A schedule $S$ can be deemed conflict equivalent to another schedule $S'$ if it’s possible to convert $S$ into $S'$ through a sequence of swaps involving only non-conflicting operations. This concept hinges on the principle that the relative order of any pair of conflicting operations remains unchanged between the two schedules. In essence, conflict equivalence between two schedules asserts that, despite potential rearrangements of operations that do not interfere with one another, the core sequence of operations that could affect the outcome—those that are in conflict due to accessing the same data item with at least one write operation—preserves their original order across both schedules.

To further elaborate, consider that operations within a schedule involve reading, writing, or other manipulations of data items by transactions. When operations from different transactions access the same data item and at least one operation is a write, they directly influence the data’s integrity and must occur in a specific sequence to maintain consistency.

Example:

Let’s assume we have two schedules involving transactions $T_1$ and $T_2$, working with data items $X$ and $Y$.

Schedule $S$: $r_1(X), w_2(X), r_1(Y), w_2(Y)$
Schedule $S'$: $r_1(X), r_1(Y), w_2(X), w_2(Y)$

In these schedules, $r_1(X)$ and $r_1(Y)$ are read operations by $T_1$ on data items $X$ and $Y$, respectively, and $w_2(X)$ and $w_2(Y)$ are write operations by $T_2$ on the same data items. The operations $r_1(Y)$ and $w_2(X)$ do not conflict since they involve different data items, allowing their positions to be swapped without affecting the outcome.

Thus, moving $r_1(Y)$ before $w_2(X)$ in schedule $S$ to match $S'$ does not alter the fundamental conflict structure between $T_1$ and $T_2$’s operations on $X$ and $Y$. Since the relative order of the conflicting operations ($r_1(X)$ with $w_2(X)$ and $r_1(Y)$ with $w_2(Y)$) remains consistent between $S$ and $S'$, these schedules are conflict equivalent. They preserve the integrity of the operations’ impact on data items $X$ and $Y$, underscoring that the specific order of non-conflicting operations can be adjusted without compromising the database’s consistent state as determined by the conflicting operations. This demonstrates how conflict equivalence focuses on the preservation of critical operation sequences to ensure consistent transaction outcomes.

Serializability of Schedules

The concept of conflict serializability in schedules can be effectively analyzed using a structured approach known as the precedence graph (or serialization graph) method. This technique specifically examines the read and write operations within a schedule to determine if the schedule can be serialized without conflicts, meaning it can be rearranged into an equivalent serial schedule without altering the outcome of the transactions.

Precedence Graph Explained

A precedence graph is a directed graph, denoted as $G = (N, E)$, where: - $N$ represents the set of nodes, each corresponding to a transaction ($T1, T2, \ldots, Tn$), - $E$ signifies the set of directed edges ($e1, e2, \ldots, en$), indicating a precedence relationship between transactions.

In this graph, an edge $e_i = (T_i \rightarrow T_j)$ is drawn from node $T_i$ to node $T_j$ if the transaction $T_i$ must precede $T_j$ due to a conflict in their operations on the same data item.

The short tutorial video below can help you in understanding precedence graphs for determining if transactions are serializable.

Steps to Test Conflict Serializability

To assess a schedule $S$’s conflict serializability using the precedence graph, follow these detailed steps:

Node Creation: For each transaction $T_i$ in schedule $S$, create a corresponding node labeled $T_i$ in the graph.
Edge for Write-Read Conflict: If a transaction $T_j$ performs a read operation on a data item $Q$ after $T_i$ has performed a write operation on $Q$, draw a directed edge from $T_i$ to $T_j$.
Edge for Read-Write Conflict: If $T_j$ executes a write operation on $Q$ after $T_i$ has read $Q$, also draw an edge from $T_i$ to $T_j$.
Edge for Write-Write Conflict: Similarly, if $T_j$ writes to $Q$ after $T_i$ has also written to $Q$, draw an edge from $T_i$ to $T_j$.
Determining Serializability: After constructing the graph with all relevant edges, examine it for cycles. If the graph is acyclic (contains no cycles), then schedule $S$ is conflict serializable, meaning it can be rearranged into a serial schedule without changing the transactions’ outcome. However, if any cycle is detected, $S$ is not conflict serializable, indicating that there is no way to rearrange $S$ into a serial schedule without altering the outcome.

Example

Consider a simple schedule involving two transactions, $T1$ and $T2$, where $T1$ writes to data item $Q$ and $T2$ subsequently reads $Q$ and then writes to it. The steps would lead to a precedence graph with nodes $T1$ and $T2$ and directed edges indicating the order of operations due to the conflicts between their read and write operations. The absence of cycles in this graph would imply that the schedule is conflict serializable, offering a visual representation of the transactions’ dependencies and their ability to be serialized without conflict.

View Equivalence

View equivalence offers a broader framework for evaluating the similarity between two schedules, $S$ and $S'$, by focusing on how transactions view and interact with the data, rather than strictly on the order of operations. Two schedules are considered view equivalent if they meet specific criteria regarding the operations performed by their transactions and the visibility of data changes. This approach to equivalence emphasizes the consistency of data as seen by transactions, rather than the exact sequence of read and write operations.

Detailed Criteria for View Equivalence

To determine view equivalence between schedules $S$ and $S'$, the following conditions must be satisfied:

Identical Transaction Participation: Both $S$ and $S'$ must involve the same set of transactions, and each schedule must include an identical set of operations performed by these transactions.
Consistent Initial Reads: If a transaction $T_i$ reads the initial value of a data item, say $Q$, in schedule $S$, then $T_i$ must also read the initial value of $Q$ in schedule $S'$. This ensures that transactions in both schedules start with the same understanding of the data.
Order of Read After Write: For any data item $Q$, if a transaction $T_i$ performs a read operation on $Q$ following a write operation on $Q$ by another transaction $T_j$ in schedule $S$, the same precedence must be maintained in $S'$. This rule guarantees that the dependencies between reading and writing operations on the same data item are preserved across both schedules.
Matching Final Writes: If a transaction $T_i$ executes the last write operation on a data item $Q$ in schedule $S$, it must also perform the last write operation on $Q$ in schedule $S'$. This condition ensures that the final state of the database, with respect to any data item, is identical in both schedules.

Implications of the Criteria

Conditions 2 and 3 make sure that transactions in both schedules read the same values, ensuring that their computations based on these values remain consistent.
Condition 4, in conjunction with conditions 2 and 3, guarantees that the ultimate modifications to each data item lead to the same final database state in both schedules.

View Serializability

Building on the concept of view equivalence, a schedule $S$ is deemed view serializable if it is view equivalent to some serial schedule. This form of serializability allows for greater flexibility in the concurrent execution of transactions, focusing on the outcome and the perceived state of the database by the transactions, rather than the strict ordering of operations. View serializability ensures that despite the potential interleaving of operations in concurrent transactions, the end result mirrors that of a sequence where transactions are executed one after another, maintaining data consistency and integrity from the perspective of each transaction.

Constrained Write Assumption

The concepts of conflict serializability and view serializability share similarities under a specific condition known as the constrained write assumption. This assumption applies to the behavior of transactions within a schedule and plays a pivotal role in determining the equivalence of these serializability forms.

Constrained Write Assumption Explained

The constrained write assumption mandates that for any transaction $T_i$, if a write operation on a data item $P$ occurs, it must be preceded by a read operation on $P$ within the same transaction $T_i$. Furthermore, the value that $T_i$ writes to $P$ should be directly derived from the value it previously read from $P$. This implies that the new value of $P$ being written is a function of its initially read value, ensuring that the write operation is not arbitrary but based on the transaction’s earlier interaction with $P$.

Implications for Serializability

Under this assumption, the distinction between conflict serializability and view serializability becomes more nuanced:

Conflict Serializable Schedules: A schedule is conflict serializable if it can be rearranged (through swaps of non-conflicting operations) into a serial schedule without changing the outcome of the transactions. This form of serializability is strict about the order of conflicting operations (reads and writes on the same data item where at least one operation is a write) and ensures that the database remains consistent.
View Serializable Schedules: A schedule is view serializable if it results in the same final state of the database as some serial schedule, taking into account the initial reads, the order of dependent reads and writes, and the final writes on data items. View serializability is more concerned with the end-state consistency from the transactions’ viewpoint rather than the exact sequence of operations.

Relationship Between Conflict and View Serializability

With the constrained write assumption in place, every conflict serializable schedule naturally satisfies the criteria for view serializability. This is because the assumption guarantees that write operations are dependent on preceding read operations within the same transaction, thereby preserving the logical flow and outcome of transactions as if they were executed serially.

However, the converse is not always true: not all view serializable schedules are conflict serializable. Some schedules might achieve the same final database state as a serial schedule (thus being view serializable) without necessarily adhering to the strict ordering of operations required for conflict serializability. This discrepancy arises because view serializability allows for more flexibility in operation ordering as long as the transactions’ view of the database state remains consistent.

In short, while every conflict serializable schedule under the constrained write assumption is also view serializable, the reverse does not hold. This distinction underscores the nuanced criteria that differentiate these two forms of serializability, with the constrained write assumption serving as a critical link in understanding their relationship.

Recoverability of Schedules

Computer systems (which includes their hardware and software) are inherently susceptible to failures, making it essential to address the impact of transaction failures during their concurrent execution. To uphold the atomicity property of transactions, which dictates that transactions should either be completed fully or not at all, the effects of any failed transaction $T_i$ must be reversed. This reversal process is essential to maintain the integrity and consistency of the database even when hardware or software failures (crashes, deadlocks, etc.) occur.

In the context of concurrent transaction execution, special attention must be given to transactions $T_j$ that are dependent on the outcome of another transaction $T_i$. Dependency occurs when $T_j$ reads a data item that has been modified by $T_i$. If $T_i$ fails and its effects are undone, then $T_j$, and potentially other transactions that have interacted with the affected data, must also be rolled back to prevent inconsistency. This requirement introduces the need for careful control over the scheduling of transactions to allow for efficient and reliable recovery from failures.

To manage this, two specific types of schedules are considered suitable:

Recoverable Schedules: These schedules ensure that if a transaction $T_j$ reads a data item modified by another transaction $T_i$, the commit operation of $T_i$ must precede the commit operation of $T_j$. This sequencing guarantees that no transaction commits to changes based on uncommitted, and thus potentially rollback-able, modifications of another transaction. A recoverable schedule prevents scenarios where a transaction might commit to changes that are later undone due to another transaction’s failure, ensuring that the database can always be returned to a consistent state.
Cascadeless (or Strict) Schedules: While not explicitly defined in the initial statement, it’s worth noting that cascadeless schedules go a step further by ensuring that transactions only read data items that have been committed. This approach significantly reduces the complexity and overhead associated with rolling back transactions since it eliminates the “cascading” effect of rollbacks where multiple dependent transactions need to be undone.

By adhering to these scheduling principles, database systems can better manage the complexities associated with transaction failures during concurrent execution. Recoverable schedules ensure that the system can recover from failures without violating the integrity of the database, while cascadeless schedules offer an even stronger guarantee by minimizing the potential for cascading rollbacks, thus simplifying recovery processes and enhancing system reliability.

Isolation Levels in SQL Transactions

In SQL, each transaction is defined by specific attributes including its access mode, the size of its diagnostic area, and its isolation level. These characteristics are crucial for managing how transactions interact with the database and with each other. The SET TRANSACTION command in SQL:92 allows for the explicit setting of these characteristics at the beginning of a transaction.

Access Modes

READ ONLY: This mode restricts the transaction to only fetching data from the database, prohibiting any operations that modify the database.
READ WRITE: This mode enables the transaction to perform modifications to the database, including UPDATE, INSERT, DELETE, and CREATE operations.

Diagnostic Area Size

Specified with the DIAGNOSTIC SIZE n DIAGNOSTIC LIMIT n or clause, this option sets the maximum number of error or exception conditions that can be captured and stored in the diagnostic area for the current transaction. This area is updated with details from each SQL statement executed within the transaction. Should the number of conditions exceed the defined size, only the conditions deemed most severe will be retained and reported. For instance, if the diagnostic size is set to 5 and an SQL statement triggers 10 conditions, only the 5 most critical conditions will be recorded.

Isolation Levels

SQL:92 defines four isolation levels to manage the degree of visibility transactions have to each other’s changes:

SERIALIZABLE: The highest level of isolation, where transactions are completely isolated from one another, preventing all forms of data anomalies such as dirty reads, non-repeatable reads, and phantom reads.
REPEATABLE READ: Transactions are shielded from updates that could cause non-repeatable reads, but phantom rows can still appear.
READ COMMITTED: This level prevents dirty reads by ensuring transactions can only read data that has been committed. However, it does not prevent non-repeatable reads or phantom rows.
READ UNCOMMITTED: The lowest level of isolation, where transactions may see uncommitted changes from other transactions. This level allows for dirty reads, non-repeatable reads, and phantom reads.

Dirty Read: Occurs when a transaction reads data that has been modified but not yet committed by another transaction.
Non-repeatable Read: Happens when a transaction reads the same row twice and finds different data due to updates by another transaction.
Phantom Read: Arises when a transaction re-executes a query matching a set of rows and discovers new rows that were added (and committed) by another transaction since the initial query.

These isolation levels offer a trade-off between performance and the strictness of data integrity and consistency. Higher isolation levels like SERIALIZABLE provide more stringent data protection at the potential cost of performance due to increased locking and reduced concurrency. Lower levels, such as READ UNCOMMITTED, maximize performance and concurrency but at the risk of encountering data anomalies. The choice of isolation level depends on the specific requirements of the application, including its tolerance for temporary inconsistencies and its performance needs.

Below is a table summarizing the possible violations or anomalies that can occur at different transaction isolation levels in SQL databases. The isolation levels are listed from the least strict (READ UNCOMMITTED) to the most strict (SERIALIZABLE), along with the types of anomalies they are susceptible to:

Isolation Level	Dirty Read	Non-repeatable Read	Phantom Read
READ UNCOMMITTED	Possible	Possible	Possible
READ COMMITTED	Not Possible	Possible	Possible
REPEATABLE READ	Not Possible	Not Possible	Possible
SERIALIZABLE	Not Possible	Not Possible	Not Possible

Explanation:

Dirty Read: Occurs when a transaction reads data that another transaction has not yet committed. This anomaly is only possible under the READ UNCOMMITTED level.
Non-repeatable Read: Happens when a transaction reads the same row twice and gets different data each time because another transaction updated the row in the meantime. This is prevented in the REPEATABLE READ and SERIALIZABLE levels.
Phantom Read: Arises when a transaction re-executes a query matching a set of rows and discovers new rows that were added by another transaction after the initial read. Phantom reads are prevented only at the SERIALIZABLE isolation level.

This table illustrates the trade-offs between the degree of isolation and the potential for concurrency-related anomalies. Higher isolation levels (e.g., SERIALIZABLE) offer greater data integrity at the cost of potential performance penalties due to locking and decreased concurrency. Lower levels (e.g., READ UNCOMMITTED) increase concurrency and performance but at the risk of encountering these anomalies.

Setting Isolation Levels in Databases

Isolation levels can generally be configured through SQL or PRAGMA commands, although the support for different isolation levels varies from database to database. Following are mechanisms supported by SQLite and MySQL. Consult vendor documentation for other databases.

SQLite Isolation Levels

SQLite operates differently from many other database systems in terms of transaction isolation because it uses a file-based database. It doesn’t support the full range of isolation levels in the same way as client-server SQL database systems like MySQL. Instead, SQLite uses locking mechanisms at the database or table level to manage concurrency, which can be broadly mapped to isolation concepts.

Isolation Levels: SQLite essentially operates in a mode that is somewhat analogous to SERIALIZABLE isolation, in that it prevents other transactions from accessing the database in ways that would violate consistency. SQLite achieves this through database locks, including shared locks for reading and exclusive locks for writing.
Configuration: Isolation in SQLite is managed through its locking mechanism rather than explicitly settable isolation levels. When you begin a transaction with BEGIN TRANSACTION, SQLite uses a shared lock for read operations and a reserved lock when a transaction intends to write. The lock is escalated to an exclusive lock when the transaction writes.

MySQL Isolation Levels

MySQL supports all four standard SQL isolation levels, and they can be configured both globally and per-session.

Supported Isolation Levels:
- READ UNCOMMITTED
- READ COMMITTED
- REPEATABLE READ (the default isolation level for InnoDB)
- SERIALIZABLE
Configuration:
- Globally: To set the isolation level for all new connections to the database, you can set the global variable using the following SQL command:
```
SET GLOBAL transaction_isolation = 'isolation_level';
```
  Replace 'isolation_level' with your chosen level, e.g., 'READ COMMITTED'.
- Per-Session: To set the isolation level for the current session only, use:
```
SET SESSION transaction_isolation = 'isolation_level';
```
  This change affects only the current connection and reverts to the default upon disconnection.

Example

For MySQL, if you want to set the isolation level to READ COMMITTED globally, you would use:

SET GLOBAL transaction_isolation = 'READ COMMITTED';

And for a single session:

SET SESSION transaction_isolation = 'READ COMMITTED';

In SQLite, direct control over isolation levels through SQL commands is not applicable. Instead, concurrency and isolation are managed through its transaction and locking mechanisms, ensuring data consistency by controlling concurrent access to the database file.

Nested Transactions

Nested transactions are a set of transactions organized in a hierarchical manner, where each transaction, except the top-level one, is nested within another. Databases supporting nested transactions allow a transaction to contain subtransactions that can independently commit or abort, providing finer-grained control over transaction execution. This structure helps in better managing complex operations and dependencies within a large transaction.

As an example of the need for nested transactions, consider booking a flight on an airline; let’s call the airline Bird Air. So, imagine that you log on to Bird Air’s website to book a flight from Boston to Vancouver. So, the booking is obviously done within a transaction. But let’s say that Bird Air doesn’t fly directly to Vancouver, but flies only to Seattle. However, Bird Air has a code share agreement with Pacific Airlines, so the leg from Seattle to Vancouver is handled by them, so Bird Air’s booking system must now start a transaction within Pacific’s booking system – a nested transaction. Let’s take this a step further: you want to book your flight with “miles” or “points” rather than paying cash, but you do not have enough points – you are a couple thousand points short, so Bird Air suggests you purchase “miles” to top up your account so you can pay with miles. The transaction of buying the points (credit card payment and credit to your mileage account) is another transaction – that runs subordinate and within your flight booking transaction. The mileage purchase transaction might fail but that would not necessitate a rollback of the booking transaction. So, you can see why nested transactions are often necessary. This scenario illustrates the utility of nested transactions in handling complex, interdependent operations.

Concurrency Control

Concurrency control in databases refers to the mechanisms that ensure data consistency and transaction integrity in a database system when multiple transactions are executed concurrently. These mechanisms are crucial in multi-user database environments, where several transactions may try to read from and write to the same data simultaneously. Without effective concurrency control, concurrent transactions can lead to several problems, including lost updates, temporary inconsistency, uncommitted data being read (dirty reads), and phantom reads. The goal of concurrency control is to manage these issues while maximizing database performance and ensuring the ACID properties (Atomicity, Consistency, Isolation, Durability) of transactions:

Atomicity guarantees that each transaction is treated as a single unit, which either completes fully or not at all.
Consistency ensures that each transaction moves the database from one consistent state to another consistent state, maintaining all database rules.
Isolation ensures that transactions are securely isolated from one another, providing each transaction with a clear and consistent view of the data.
Durability guarantees that once a transaction has been committed, it remains so, even in the event of a system failure.

Concurrency control strategies can be broadly classified into two categories:

pessimistic concurrency control, and
optimistic concurrency control.

Pessimistic Concurrency Control

Pessimistic concurrency control assumes that conflicts among transactions are likely and implements controls to lock data and prevent conflicts before they happen. This approach uses locks to ensure that no other transaction can access the same data simultaneously in a conflicting manner. Locking mechanisms can be granular, ranging from locking an entire database to locking a table, page, or even a single row.

Lock-Based Protocols: These include shared locks (for reading data) and exclusive locks (for writing data). Lock-based protocols prevent other transactions from accessing the locked data in a conflicting way.

Optimistic Concurrency Control

Optimistic concurrency control assumes that conflicts among transactions are rare and allows transactions to proceed without locking resources. Instead, it checks for conflicts before committing. If a conflict is detected, one of the conflicting transactions is rolled back and may be retried.

Validation or Commit-Time Checking: This approach involves executing transactions without restrictions but validating them at commit time. If a transaction is found to have conflicting operations with other transactions, it is rolled back.

Other Techniques

Timestamp Ordering: Each transaction is given a unique timestamp, ensuring that transactions proceed in timestamp order. This can prevent conflicts by ordering transactions in a way that respects their temporal sequence.
Multiversion Concurrency Control (MVCC): This approach keeps multiple versions of data objects, allowing readers to access a version of the data that was current at the start of their transaction, thus avoiding write-read conflicts.

Concurrency control is a fundamental aspect of database management systems, ensuring that the database remains consistent and reliable even in highly concurrent environments. Different DBMS may implement different concurrency control strategies based on their underlying architecture and the specific requirements of the applications they support.

Distributed Transactions and 2PC

So far, we have only considered transactions in a single database containing all data. The Two-Phase Commit Protocol (2PC) is a critical algorithm used in distributed database systems to ensure the atomicity of transactions across multiple databases or nodes. Atomicity, one of the ACID properties, guarantees that a series of operations within a transaction are completed successfully as a single unit. If any operation fails, the entire transaction is rolled back, leaving the system in a consistent state. 2PC is designed to handle the challenges of maintaining atomicity across distributed systems, where transactions may span multiple, independently managed databases or resources.

How Two-Phase Commit Works

The two-phase commit protocol operates in two distinct phases: the prepare phase and the commit phase.

Phase 1: Prepare Phase

Transaction Initiation: The transaction manager (coordinator) initiates the transaction across all participating nodes (participants) in the distributed system.
Voting: After executing the transaction’s operations, each participant votes on whether the transaction should be committed or aborted. This vote is based on whether the participant successfully executed its part of the transaction without encountering any errors or constraints.
Ready to Commit: Each participant sends its vote to the coordinator. If all participants vote “Yes” (indicating success), the system moves to the commit phase. If any participant votes “No,” indicating an inability to complete the transaction successfully, the system moves to abort the transaction.

Phase 2: Commit Phase

Commit or Abort Decision: Based on the votes received from all participants, the coordinator decides whether to commit or abort the transaction.
- Commit: If all participants voted “Yes,” the coordinator sends a commit message to all participants.
- Abort: If any participant voted “No,” or if the coordinator did not receive votes from all participants within a certain timeout period, it decides to abort the transaction.
Commit or Abort Execution: Upon receiving the coordinator’s decision, each participant either commits or aborts the transaction on its end and acknowledges this action to the coordinator.
Completion: Once the coordinator receives acknowledgments from all participants, the transaction is considered complete.

Example of Two-Phase Commit

Consider an online retail system where a customer’s order involves updating inventory databases located in different geographical locations and processing payment through a separate payment gateway.

Prepare Phase:
- The order management system (coordinator) sends a prepare-to-commit message to the inventory databases (participants) and the payment gateway, asking if they can commit the order transaction.
- The inventory databases reduce the stock for the ordered items and vote “Yes” if sufficient stock is available or “No” if stock is insufficient. Simultaneously, the payment gateway attempts to authorize the payment and votes “Yes” if the payment can be processed or “No” if the payment fails.
Commit Phase:
- If all participants vote “Yes,” the coordinator sends a commit message to all participants, finalizing the stock reduction and payment processing.
- If any participant votes “No” (e.g., insufficient stock or payment failure), the coordinator sends an abort message to all participants. The inventory databases would then roll back any stock adjustments, and the payment gateway would cancel the payment authorization.

This example illustrates how 2PC ensures that either all parts of a distributed transaction are successfully committed, maintaining consistency across the system, or the entire transaction is rolled back, leaving the system in its initial state. The protocol is essential for applications requiring strong consistency guarantees across distributed components but can introduce challenges related to performance and the potential for blocking if the coordinator fails during the process.

Summary

Concurrency and transactions are fundamental in relational databases to manage multiple accesses and modifications, ensuring data integrity, consistency, and reliability. Proper implementation of concurrency control and transaction management mechanisms is vital for the efficient and safe operation of database systems.

In this lesson, we explored several key concepts related to transactions, concurrency control, serializability, and the conditions that influence the consistency and integrity of databases in concurrent execution environments.

Transactions and Atomicity: We discussed the nature of transactions in DBMS, highlighting their atomic character and the ACID properties (Atomicity, Consistency, Isolation, Durability) that ensure database transactions are processed reliably.
Concurrency Control: The importance of concurrency control in managing simultaneous transactions was addressed. We explored how it prevents issues like lost updates, dirty reads, and phantom reads, ensuring that databases maintain integrity and consistency even when multiple transactions are executed concurrently.
Serializability: The concept of serializability, specifically conflict serializability and view serializability, was examined. We discussed how these concepts ensure that concurrent transactions result in a database state that could be achieved by executing transactions serially, thus preserving data consistency.
Conflict and View Serializability: We delved into the specifics of conflict serializability and view serializability, including the conditions under which schedules are considered equivalent under these criteria. The discussion included the constrained write assumption, which when satisfied, aligns the definitions of conflict serializability and view serializability by ensuring that write operations depend only on previously read values within the same transaction.

Files & Resources

All Files for Lesson 60.701

References

[1] Chapple, M. (2020). “Abandoning ACID in Favor of BASE in Database Engineering”. Lifewire. July 25, 2020.

[2] Gilbert, Seth, and Nancy Lynch. “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.” ACM SIGACT News 33.2 (2002): 51-59.

This paper provides a formal analysis of the CAP Theorem and discusses the trade-offs between consistency, availability, and partition tolerance in distributed systems. It’s an essential reference for understanding the theoretical foundations of the CAP Theorem as proposed by Eric Brewer.

Resources

LudicChart Diagrams

Glossary of Key Terms

ACID (Atomicity, Consistency, Isolation, Durability): A set of properties that guarantee database transactions are processed reliably, ensuring data integrity and error recovery.
Atomicity: The property that ensures a transaction is treated as a single unit of work, which either completes entirely or not at all.
Consistency: Ensures that a transaction can only bring the database from one valid state to another, maintaining all predefined rules.
Isolation: The property that ensures transactions are executed in isolation from each other, preventing concurrent transactions from interfering.
Durability: Guarantees that once a transaction has been committed, it will remain so, even in the event of a system failure.
BASE (Basically Available, Soft state, Eventual consistency): A set of principles for distributed systems that prioritize availability, allowing for more flexibility in terms of consistency.
CAP Theorem (Consistency, Availability, Partition tolerance): A principle that states a distributed system cannot simultaneously guarantee consistency, availability, and partition tolerance beyond a certain level.
Serializable: The highest isolation level in SQL, where transactions are completely isolated from one another, preventing anomalies like dirty reads, non-repeatable reads, and phantom reads.
Read Uncommitted: The lowest isolation level, allowing transactions to read uncommitted changes made by other transactions, leading to potential data anomalies.
Read Committed: An isolation level that prevents dirty reads by ensuring transactions can only read data that has been committed.
Repeatable Read: An isolation level that prevents dirty reads and non-repeatable reads but might still allow phantom reads.
Dirty Read: An anomaly where a transaction reads data that has been modified but not yet committed by another transaction.
Non-repeatable Read: Occurs when a transaction reads the same row twice and gets different data each time because another transaction updated the row in the meantime.
Phantom Read: Happens when a transaction re-executes a query matching a set of rows and discovers new rows that were added by another transaction after the initial read.
Result Equivalence: When two schedules lead to the same final state of the database, regardless of the order of operations.
Recoverable Schedule: A schedule where, if a transaction reads a data item modified by another transaction, the commit of the modifying transaction occurs before the commit of the reading transaction.
Cascadeless Schedule: A type of schedule where transactions only read data items that have been committed, preventing cascading rollbacks.
Constrained Write Assumption: An assumption that a write operation in a transaction depends solely on data read earlier in the same transaction.

Errata

Let us know.

60.701Transaction Processing in Relational Databases

Martin Schedlbauer, PhD

2024-04-04

Objectives

Overview

Transactions

Motivating Example

Example Scenario: Bank Fund Transfer

Without Transactions

With Transactions

Why Transactions Are Necessary

ACID vs BASE vs CAP

BASE Model

CAP Theorem

Comparison of ACID and BASE within the Context of CAP

Programming Transactions

SQL-Based Databases

APIs in Application Code

State Machine for a Transaction

Compensating Transactions

Concurrent Transactions

Interleaving Anomalies

Transaction Schedules

Serializable Schedules

Example of Serializable Schedule

Schedule Equivalence

Example of Result Equivalent Schedules

Schedule 1:

Schedule 2:

Accidental Result Equivalence

Accidental Schedule 1:

Accidental Schedule 2:

Conflict Equivalence and Conflict Serializability

Example:

Serializability of Schedules

Precedence Graph Explained

Steps to Test Conflict Serializability

Example

View Equivalence

Detailed Criteria for View Equivalence

Implications of the Criteria

View Serializability

Constrained Write Assumption

Constrained Write Assumption Explained

Implications for Serializability

Relationship Between Conflict and View Serializability

Recoverability of Schedules

Isolation Levels in SQL Transactions

Access Modes

Diagnostic Area Size

Isolation Levels

Setting Isolation Levels in Databases

SQLite Isolation Levels

MySQL Isolation Levels

Example

Nested Transactions

Concurrency Control

Pessimistic Concurrency Control

Optimistic Concurrency Control

Other Techniques

Distributed Transactions and 2PC

How Two-Phase Commit Works

Phase 1: Prepare Phase

Phase 2: Commit Phase

Example of Two-Phase Commit

Summary

Files & Resources

See Also

References

Resources

Glossary of Key Terms

Errata

60.701
Transaction Processing in Relational Databases