Even though @Ramandeep Singh has answered this question, I'd like to add some additional points because in the comments and discussion on this question, many students are having incorrect arguments which they think are correct.
The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence Graph because they are not making conflict edges in the Precedence graph "from a committed transaction to a newly started transaction"....which is completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??
Following all the definitions and concepts are directly (without modification) picked mostly from Navathe and some from the following link : http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html
Refer Navathe if you still have some doubt.
Transactions :
A transaction is effectively a sequence of read and write operations on atomic database items. A transaction may be incomplete because the (database) system crashes, or because it is aborted by either the system or the user (or application). Complete transactions are committed. Transactions must terminate by either aborting or committing.
Complete Schedule :
A schedule $S$ of $n$ transactions $T1, T2, \ldots, Tn$ is said to be a complete schedule if the following conditions hold:
1. The operations in $S$ are exactly those operations in $T1, T2, \ldots, Tn$, including a commit or abort operation as the last operation for each transaction in the schedule.
2. For any pair of operations from the same transaction $Ti$ , their relative order of appearance in $S$ is the same as their order of appearance in $Ti$ . (i.e Operation order in/of every transaction must preserve.)
3. For any two conflicting operations, one of the two must occur before the other in the schedule.
Condition 1 simply states that all operations in the transactions must appear in the complete schedule. Since every transaction has either committed or aborted, a complete schedule will not contain any active transactions at the end of the schedule.
In general, it is difficult to encounter complete schedules in a transaction processing system because new transactions are continually being submitted to the system. Hence, it is useful to define the concept of the committed projection $C(S)$ of a schedule $S$.
Committed Projection of a schedule :
Committed Projection $C(S)$ of a schedule $S$ includes only the operations in $S$ that belong to committed transactions—that is, transactions $Ti$ whose commit operation $Ci$ is in $S$.
Given a schedule S, the committed projection $C(S)$ is the subset of $S$ consisting of operations $(r1(X), w2(Y), \;\text{etc})$ that are part of transactions that have committed $($that is, $r1(X)$ would be part of $C(S)$ only if transaction $1$'s commit, $c1,$ were also part of $S).$ This is sometimes useful in analyzing schedules when transactions are continuously being added.
A committed projection $C(S)$ of a schedule $S$ includes the operations in $S$ only from the committed transactions. Let's take an example :
Transactions:
- $T1: r1(X); w1(X); r1(Y); w1(Y); c1;$
- $T2: r2(Y); w2(Y); a2;$
- $T3: r3(X); w3(X);$
- $S1: r1(X); r2(Y); w1(X); w2(Y); r1(Y); a2; w1(Y); c1; r3(X); w3(X);$
Then $C(S1) = ??$
Well, $C(S1)$ will be the same as $T1$ because $T3$ has No Commit/Abort operation as the last operation of the transaction and $T2$ is Not committed. So, by the definition of Committed Transaction, $C(S1) = T1.$
Now, as according to Navathe,
We can theoretically define a schedule $S$ to be serializable if its committed projection $C(S)$ is equivalent to some serial schedule, since only committed transactions are guaranteed by the DBMS.
And It applies to both Conflict and View Serializability.
A schedule is serialisable if the effect of its committed projection (the restriction to its committed transactions) on any consistent database is identical to that of some serial schedule of its committed transactions.
(Conflict) Serialisability theorem :
Given a schedule $S$, define the serialisation graph(Precedence Graph) $SG(S)$ to have the committed transactions of S as its nodes, and a directed edge from $T1$ to $T2$ if $T1$ and $T2$ contain conflicting operations $O1$ and $O2$ such that $O1$ precedes $O2$ in $S.$ Then $S$ is serialisable if and only if $SG(S)$ is acyclic.
http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html
Now, coming to the given question :
The given schedule is Complete Schedule as all the transactions in the schedule are committed(or aborted). Moreover, the given schedule is Committed Projection of itself as well because all the Transactions are committed. Now, as the above definition of Conflict serializability suggests, we make Precedence graph for this schedule and in the precedence graph, the Nodes will be the Transactions participating in the committed projection of the schedule(which is same as the given schedule ) ..
The precedence graph will be as following :
From the precedence graph we can see that Only One serial schedule is conflict equivalent to the given schedule which is $T2,T3,T1,T4,\ldots $ No other schedule is conflict equivalent to the given schedule.
Only One serial schedule is conflict equivalent to the given schedule which is $T2,T3,T1,T4,\ldots $ This makes sense because $T2$ is reading the initial value of data item $X$ (directly from the database) But if we run either of $T3 $ or $T1$ before $T2$ then they will write the data item $X$ and $T2$ will have to read the modified value of $X.$ Hence, Only one Serial Schedule can be equivalent to the given schedule and that is $T2,T3,T1,T4.$
The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence Graph because they are not making conflict edges from a committed transaction to a new started transaction....which is completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??
Serial Schedule (Definition as it is given in Navathe) : Formally, a schedule S is serial if, for every transaction T participating in the schedule, all the operations of T are executed consecutively in the schedule; otherwise, the schedule is called nonserial. Therefore, in a serial schedule, only one transaction at a time is active—the commit (or abort) of the active transaction initiates execution of the next transaction. No interleaving occurs in a serial schedule.
$S = R_1(X) \,\, W_1(X) \,\,C1 \,\,R_2(X)\,\, W_2(X)\,\, C2\,\, R_3(X)\,\, W_3(X)\,\, C3$
If you make precedence graph for this schedule, then you must get a acyclic precedence graph But those students who are not putting conflict edges in the precedence graph "from a committed transaction to a newly started transaction" then you won't get any edges in this graph and the graph will be empty graph, which you know is not correct.
Consider this schedule : $$\begin{array}{c|c|c} \hline T1 & T2 & T3 \\\hline & \text{Write(X)} & \\\hline \text{Writes(Z)} & & \\\hline \text{Writes(X)} & & \\\hline \textbf{Commit} & & \\\hline & \text{Writes(Y)} & \\\hline & \text{Reads(Y)} & \\\hline & & \text{Writes(Z)} \\\hline & & \text{Writes(M)} \\\hline & &\textbf{Commit} \\\hline & \text{Reads(M)} & \\\hline & \textbf{Commit} & \\\hline \end{array}$$ Try to find whether this schedule is Conflict Serializable Or Not??
If you do it correctly, It is Not conflict serializable because there is Cycle in the precedence graph of this schedule. But If you don't put conflict edges in the precedence graph "from a committed transaction $(T1)$ to a newly started transaction $(T3)$" then you won't get edge $T1 \rightarrow T3$ in the precedence graph and hence, you will incorrectly get the answer as Conflict serializable.