Schedule and Serializability

Schedule

A schedule (also called a history) is an ordering of the operations from a set of concurrent transactions, where the operations of each individual transaction appear in the same order as they do in that transaction. A schedule defines the interleaved execution sequence of operations (read, write, commit, abort) from multiple transactions.

Types of Schedules:

• Serial Schedule: Transactions execute one after another with no interleaving. If there are n transactions, there are n! possible serial schedules.
• Non-Serial (Concurrent) Schedule: Operations from multiple transactions are interleaved.

---

Serializability

A concurrent schedule is said to be serializable if its final result (effect on the database) is totally the same as the final result produced by some serial schedule of the same transactions. In other words, even though transactions execute concurrently with interleaved operations, the outcome must be equivalent to some sequential (serial) execution.

Serializability ensures correctness of concurrent execution while maximizing resource utilization and efficiency.

Types of Serializability

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

2. View Serializability: A schedule is view serializable if its view equals that of a serial schedule (no overlapping transactions). Every conflict serializable schedule is view serializable, but if a schedule contains blind writes, it may be view serializable without being conflict serializable.

---

Testing for Serializability (Precedence Graph Method)

The standard method to test conflict serializability uses a Precedence Graph (also called a Serialization Graph):

Algorithm:

1. Consider only read_Item(X) and write_Item(X) operations from the schedule.

2. Construct a Precedence Graph:

   • Nodes represent each transaction T1, T2, ..., Tn.
   • A directed edge is drawn from Ti → Tj if an operation in Ti appears before a conflicting operation in Tj.

3. Conflicting operations occur when:

   • Two transactions access the same data item X, AND
   • At least one of them is a write operation.
   • Cases: read(X) then write(X), write(X) then read(X), write(X) then write(X).

4. Check for cycles:

   • If the precedence graph has no cycle → the schedule is conflict serializable.
   • If the precedence graph has a cycle → the schedule is NOT serializable.

Example:

• T1 writes X before T2 writes X → edge T1 → T2
• T1 reads X before T2 writes X → edge T1 → T2
• T2 reads X before T1 writes X → edge T2 → T1

This creates a cycle (T1 → T2 → T1), so the schedule is NOT serializable.

---

Summary: Serializability is the key correctness criterion for concurrent transaction execution in DBMS. The precedence graph (no cycle = serializable) is the standard test for conflict serializability.