Question

Which of the following is a conflict-serializable schedule?

• A. One that is equivalent to some serial schedule.
• B. One that uses only shared locks.
• C. One that results in a deadlock.
• D. One where all write operations occur at the end.

Hint:

Conflict serializability is a sufficient condition for consistency. If a schedule is conflict serializable, it is guaranteed not to have any concurrency anomalies like lost updates or dirty reads.

Answer 1

The Correct Option is A

Concept:
A "Serial Schedule" is one where transactions are executed one after another without any interleaving. While safe, serial schedules are slow. DBMSs use "Concurrent Schedules" for speed. A concurrent schedule is considered "Conflict Serializable" if it can be transformed into a serial schedule by swapping non-conflicting operations.

Step 1: Defining Conflict Operations.
Two operations in a schedule are said to conflict if:
• They belong to different transactions.
• They operate on the same data item.
• At least one of them is a Write operation.

Step 2: The Logic of Swapping.
If two adjacent operations in a schedule do not conflict, their order does not matter. By repeatedly swapping non-conflicting adjacent operations, we try to "un-interleave" the transactions. If we successfully reach a state where all operations of $T_1$ happen before $T_2$ (or vice versa), the schedule is conflict serializable.

Step 3: Precedence Graphs.
The standard way to check for this is to draw a "Precedence Graph."
• Create a node for each transaction.
• Draw an arrow from $T_i$ to $T_j$ if an operation in $T_i$ conflicts with a later operation in $T_j$.
• If the graph contains no cycles, the schedule is conflict serializable and thus equivalent to a serial schedule.