Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item X, denoted by r(X) and w(X) respectively. Which one of them is conflict serializable ? S 1 : r 1(X); r 2(X); w 1(X); r 3(X); w 2(X) S2: r 2(X); r 1(X); w 2(X); r 3(X); w 1(X) S 3 : r 3(X); r 2(X); r 1(X); w 2(X); w 1(X) S4 : r 2(X); w 2(X); r 3(X); r 1(X); w 1(X)
S 4
Understanding Database Schedule Serializability
In a database system, concurrency control allows multiple transactions to execute seemingly simultaneously. A schedule represents the order in which operations from different transactions are interleaved. A key property for ensuring correctness in concurrent execution is serializability. A schedule is considered serializable if its result is equivalent to the result of some serial schedule (a schedule where transactions run one after another without interleaving).
Conflict serializability is a common type of serializability. A schedule is conflict serializable if it is conflict equivalent to a serial schedule. Two schedules are conflict equivalent if the relative order of any two conflicting operations is the same in both schedules.
Conflicting operations are operations from different transactions on the same data item where at least one of the operations is a write operation. There are three types of conflicts:
- Read-Write (RW) conflict: $r_i(X)$ and $w_j(X)$ where $i \neq j$.
- Write-Read (WR) conflict: $w_i(X)$ and $r_j(X)$ where $i \neq j$.
- Write-Write (WW) conflict: $w_i(X)$ and $w_j(X)$ where $i \neq j$.
The Precedence Graph Method for Conflict Serializability
To determine if a schedule is conflict serializable, we can construct a precedence graph (also called a serializability graph). The steps are as follows:
- Create a node in the graph for each transaction involved in the schedule.
- For every pair of conflicting operations on the same data item by different transactions, say operation $Op_i$ by transaction $T_i$ and operation $Op_j$ by transaction $T_j$:
- If $Op_i$ occurs before $Op_j$ in the schedule, draw a directed edge from node $T_i$ to node $T_j$.
- The schedule is conflict serializable if and only if the precedence graph is acyclic (contains no cycles).
If the graph is acyclic, any topological sort of the graph nodes represents a valid serial order that is conflict equivalent to the given schedule.
Analyzing Schedule S1 for Conflict Serializability
Schedule S1: $r_1(X); r_2(X); w_1(X); r_3(X); w_2(X)$
Transactions involved: $T_1, T_2, T_3$. Data item: $X$.
Let's identify conflicting operations and the corresponding edges:
- $r_2(X)$ (T2) before $w_1(X)$ (T1) on X (RW conflict) $\implies$ Edge $T_2 \to T_1$
- $w_1(X)$ (T1) before $r_3(X)$ (T3) on X (WR conflict) $\implies$ Edge $T_1 \to T_3$
- $w_1(X)$ (T1) before $w_2(X)$ (T2) on X (WW conflict) $\implies$ Edge $T_1 \to T_2$
- $r_3(X)$ (T3) before $w_2(X)$ (T2) on X (RW conflict) $\implies$ Edge $T_3 \to T_2$
Precedence Graph for S1:
- Nodes: $T_1, T_2, T_3$
- Edges: $T_2 \to T_1, T_1 \to T_3, T_1 \to T_2, T_3 \to T_2$
Cycle Check: The graph contains the edges $T_1 \to T_2$ and $T_2 \to T_1$. This forms a cycle $T_1 \to T_2 \to T_1$.
Conclusion for S1: Since the precedence graph contains a cycle, Schedule S1 is not conflict serializable.
Analyzing Schedule S2 for Conflict Serializability
Schedule S2: $r_2(X); r_1(X); w_2(X); r_3(X); w_1(X)$
Transactions involved: $T_1, T_2, T_3$. Data item: $X$.
Let's identify conflicting operations and the corresponding edges:
- $r_1(X)$ (T1) before $w_2(X)$ (T2) on X (RW conflict) $\implies$ Edge $T_1 \to T_2$
- $w_2(X)$ (T2) before $r_3(X)$ (T3) on X (WR conflict) $\implies$ Edge $T_2 \to T_3$
- $w_2(X)$ (T2) before $w_1(X)$ (T1) on X (WW conflict) $\implies$ Edge $T_2 \to T_1$
- $r_3(X)$ (T3) before $w_1(X)$ (T1) on X (RW conflict) $\implies$ Edge $T_3 \to T_1$
Precedence Graph for S2:
- Nodes: $T_1, T_2, T_3$
- Edges: $T_1 \to T_2, T_2 \to T_3, T_2 \to T_1, T_3 \to T_1$
Cycle Check: The graph contains the edges $T_1 \to T_2$ and $T_2 \to T_1$. This forms a cycle $T_1 \to T_2 \to T_1$.
Conclusion for S2: Since the precedence graph contains a cycle, Schedule S2 is not conflict serializable.
Analyzing Schedule S3 for Conflict Serializability
Schedule S3: $r_3(X); r_2(X); r_1(X); w_2(X); w_1(X)$
Transactions involved: $T_1, T_2, T_3$. Data item: $X$.
Let's identify conflicting operations and the corresponding edges:
- $r_3(X)$ (T3) before $w_2(X)$ (T2) on X (RW conflict) $\implies$ Edge $T_3 \to T_2$
- $r_2(X)$ (T2) before $w_1(X)$ (T1) on X (RW conflict) $\implies$ Edge $T_2 \to T_1$
- $r_1(X)$ (T1) before $w_2(X)$ (T2) on X (RW conflict) $\implies$ Edge $T_1 \to T_2$
- $r_3(X)$ (T3) before $w_1(X)$ (T1) on X (RW conflict) $\implies$ Edge $T_3 \to T_1$
- $w_2(X)$ (T2) before $w_1(X)$ (T1) on X (WW conflict) $\implies$ Edge $T_2 \to T_1$ (Already added)
Precedence Graph for S3:
- Nodes: $T_1, T_2, T_3$
- Edges: $T_3 \to T_2, T_2 \to T_1, T_1 \to T_2, T_3 \to T_1$
Cycle Check: The graph contains the edges $T_1 \to T_2$ and $T_2 \to T_1$. This forms a cycle $T_1 \to T_2 \to T_1$.
Conclusion for S3: Since the precedence graph contains a cycle, Schedule S3 is not conflict serializable.
Analyzing Schedule S4 for Conflict Serializability
Schedule S4: $r_2(X); w_2(X); r_3(X); r_1(X); w_1(X)$
Transactions involved: $T_1, T_2, T_3$. Data item: $X$.
Let's identify conflicting operations and the corresponding edges:
- $w_2(X)$ (T2) before $r_3(X)$ (T3) on X (WR conflict) $\implies$ Edge $T_2 \to T_3$
- $w_2(X)$ (T2) before $r_1(X)$ (T1) on X (WR conflict) $\implies$ Edge $T_2 \to T_1$
- $w_2(X)$ (T2) before $w_1(X)$ (T1) on X (WW conflict) $\implies$ Edge $T_2 \to T_1$ (Already added)
- $r_3(X)$ (T3) before $w_1(X)$ (T1) on X (RW conflict) $\implies$ Edge $T_3 \to T_1$
- $r_1(X)$ (T1) before $w_1(X)$ (T1): These operations are within the same transaction $T_1$, so they do not create a conflict edge for the precedence graph.
Precedence Graph for S4:
- Nodes: $T_1, T_2, T_3$
- Edges: $T_2 \to T_3, T_2 \to T_1, T_3 \to T_1$
Cycle Check: The graph has edges $T_2 \to T_3$ and $T_3 \to T_1$, forming a path $T_2 \to T_3 \to T_1$. It also has an edge $T_2 \to T_1$. There is no path starting and ending at the same node. The graph is acyclic.
Conclusion for S4: Since the precedence graph is acyclic, Schedule S4 is conflict serializable. A possible equivalent serial schedule is $T_2 \to T_3 \to T_1$, which respects all dependencies.
Conclusion: Identifying the Conflict Serializable Schedule
Based on the precedence graph analysis, schedules S1, S2, and S3 contain cycles in their precedence graphs, meaning they are not conflict serializable. Schedule S4 has an acyclic precedence graph, indicating that it is conflict serializable.
Revision Table: Schedule Analysis Summary
| Schedule | Operations | Conflict Edges | Precedence Graph Edges | Cycle? | Conflict Serializable? |
|---|---|---|---|---|---|
| S1 | $r_1(X); r_2(X); w_1(X); r_3(X); w_2(X)$ | RW($T_2, T_1, X$), WR($T_1, T_3, X$), WW($T_1, T_2, X$), RW($T_3, T_2, X$) | $T_2 \to T_1$, $T_1 \to T_3$, $T_1 \to T_2$, $T_3 \to T_2$ | Yes ($T_1 \to T_2 \to T_1$) | No |
| S2 | $r_2(X); r_1(X); w_2(X); r_3(X); w_1(X)$ | RW($T_1, T_2, X$), WR($T_2, T_3, X$), WW($T_2, T_1, X$), RW($T_3, T_1, X$) | $T_1 \to T_2$, $T_2 \to T_3$, $T_2 \to T_1$, $T_3 \to T_1$ | Yes ($T_1 \to T_2 \to T_1$) | No |
| S3 | $r_3(X); r_2(X); r_1(X); w_2(X); w_1(X)$ | RW($T_3, T_2, X$), RW($T_2, T_1, X$), RW($T_1, T_2, X$), RW($T_3, T_1, X$), WW($T_2, T_1, X$) | $T_3 \to T_2$, $T_2 \to T_1$, $T_1 \to T_2$, $T_3 \to T_1$ | Yes ($T_1 \to T_2 \to T_1$) | No |
| S4 | $r_2(X); w_2(X); r_3(X); r_1(X); w_1(X)$ | WR($T_2, T_3, X$), WR($T_2, T_1, X$), WW($T_2, T_1, X$), RW($T_3, T_1, X$) | $T_2 \to T_3$, $T_2 \to T_1$, $T_3 \to T_1$ | No | Yes |
Additional Information: Related Concepts
Understanding serializability is crucial in database concurrency control. Conflict serializability is a sufficient, but not necessary, condition for serializability. Another type is view serializability.
- Serial Schedule: A schedule where transactions execute completely one after another. The simplest way to ensure correctness, but severely limits concurrency.
- Serializable Schedule: A schedule whose effect on the database is the same as that of some serial schedule.
- Conflict Equivalence: Two schedules are conflict equivalent if they involve the same set of transactions and the relative order of conflicting operations is the same in both.
- View Serializability: A schedule is view serializable if it is view equivalent to a serial schedule. View equivalence considers the initial read of each transaction, the final write of each data item, and blinded writes. View serializability is a more general concept than conflict serializability (conflict serializable schedules are always view serializable), but checking for view serializability is NP-complete.
- Concurrency Control Protocols: Mechanisms like two-phase locking (2PL) or timestamp ordering are used to ensure that schedules produced are serializable (often specifically conflict serializable) to maintain database consistency.
Important Questions from Serializability of Schedules - Teaching
Consider the following statements:
Statement I: Conservative 2 PL is a deadlock-free protocol.
Statement II: Thomas's write rule enforces conflict serializability.
Statement III: Timestamp ordering protocol ensures serializability based on the order of transaction timestamps.
Which of the following is correct?
Consider the following schedules involving two transactions.
S 1: r 1(X) ; r 1(Y) ; r 2(X) ; r 2(Y) ; w 2(Y) ; w 1(X)
S2 : r 1(X) ; r 2(X) ; r 2(Y) ; w 2(Y) ; r 1(Y) ; w 1(X)
Which one of the following statements is correct with respect to above?Suppose a database schedule 5 involves transactions T 1, T 2, .............T nConsider the precedence graph of S with vertices representing the transactions and edges representing the conflicts. If S is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule ?
