Define schedule and serializability. How can you test the serializability?

A schedule is the order in which the operations (read, write, commit) of several concurrent transactions are executed. Within a schedule, the operations of each transaction keep their own order.

• In a serial schedule the transactions run one after another with no interleaving. It is always correct, but slow.
• In a non-serial (concurrent) schedule the operations are interleaved to improve throughput.

Serializability is the property that a concurrent schedule produces the same result as some serial schedule. A serializable schedule is therefore correct even though it interleaves operations.

There are two kinds:

• Conflict serializability: the schedule can be turned into a serial one by swapping adjacent non-conflicting operations.
• View serializability: the schedule reads the same initial values, reads the same writes, and does the same final writes as a serial schedule. Every conflict serializable schedule is view serializable, but not the other way round.

Testing serializability: the precedence graph

1. Create a node for each transaction.
2. Two operations conflict if they are from different transactions, use the same data item, and at least one is a write.
3. For each conflicting pair where Ti's operation comes before Tj's, add an edge Ti → Tj.
4. If the graph has no cycle, the schedule is conflict serializable. A topological order of the graph gives the equivalent serial schedule.

Example: S: R1(X), W2(X), W1(X).

• R1(X) before W2(X) gives T1 → T2.
• W2(X) before W1(X) gives T2 → T1.

The graph has a cycle (T1 → T2 → T1), so S is not conflict serializable.