Transaction Schedules and Serializability

A transaction in DBMS is a sequence of operations performed as a single logical unit of work. When multiple transactions run simultaneously, their operations may interleave.
To maintain correctness, DBMS uses schedules and checks their serializability.

1. Transaction Schedules

A schedule is an order in which operations (read/write) of concurrent transactions are executed.

Schedules ensure the DBMS can allow concurrency while still keeping the database consistent.

Types of Schedules

1️⃣ Serial Schedule

• Only one transaction executes at a time.

• No interleaving of operations.

• Always consistent and correct.

Example:

T1: R(A), W(A), R(B), W(B)
T2: R(A), W(A)

Execution:
T1 → T2 or T2 → T1

✔ Always safe
❌ Low concurrency

2️⃣ Non-Serial Schedule

• Operations of transactions are interleaved.

• Provides higher concurrency.

• May or may not be correct → so we test for serializability.

Example:

T1: R(A) W(A)
T2: R(B) W(B)

Interleaving allowed.

2. Serializability

A non-serial schedule is serializable if its result is equivalent to a serial schedule.

It ensures that concurrent transaction execution is correct and consistent.

There are two main types:

A. Conflict Serializability

A schedule is conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

✔ Conflicting operations

Two operations conflict if:

1. They belong to different transactions

2. They access the same data item

3. At least one is a write

Conflicts:

• R–W

• W–R

• W–W

Non-conflicts:

• R–R

✔ Precedence Graph (Serialization Graph)

Steps:

1. Nodes = Transactions

2. Draw edge Ti → Tj if Ti’s operation conflicts and occurs before Tj

3. If the graph has no cycle → Conflict Serializable

4. If cycle exists → NOT serializable

B. View Serializability

A schedule is view serializable if it is view equivalent to a serial schedule.

View equivalence checks:

1. Read-from rule – both schedules read initial or same transaction-written value

2. Final write rule – same transaction does final write

3. Update rule – same dependencies

✔ More general than conflict serializability
✔ Every conflict-serializable schedule is view-serializable
❌ But reverse is not always true

3. Types of Non-Serial Schedules

Recoverable Schedule

A schedule is recoverable if:

• A transaction Tj reads a value written by Ti

• Tj commits only after Ti commits

Ensures no cascading errors.

Cascadeless Schedule

• A transaction can read a data item only if the writing transaction has committed.

• Prevents cascading rollbacks.

Strict Schedule

• A data item written by a transaction cannot be read or written by another transaction until after commit.

✔ Strictest
✔ Ensures highest safety
✔ Used in most modern DBMS (Strict 2PL)

4. Importance of Serializability

• Ensures correctness of concurrent transactions

• Prevents anomalies like:

  • Lost updates

  • Dirty read

  • Inconsistent retrieval

• Maintains ACID properties

• Ensures database consistency

Conclusion

Transaction schedules define the order of execution of concurrent transactions in DBMS. To ensure correctness, DBMS checks if a non-serial schedule is equivalent to a serial schedule using serializability tests like conflict serializability and view serializability. Schedules may also be evaluated based on safety properties such as recoverable, cascadeless, and strict schedules. These mechanisms help achieve high concurrency while preserving data integrity and consistency.