edited by
28,060 views
61 votes
61 votes

Consider the following schedule S of transactions $T1, T2, T3, T4:$
$${\begin{array}{|l|l|l|l|}\hline
\textbf{T1}&    \textbf{T2}&  \textbf{T3}& \textbf{T4} \\\hline
&     \text{Reads(X)}       \\ 
&&     \text{Writes(X)}   \\     
&&     \text{Commit}          \\     \text{Writes(X)}      \\
    \text{Commit}&     \\
&     \text{Writes(Y) }   \\   
&     \text{Reads(Z)}    \\ 
&     \text{Commit} \\
&&&    \text{Reads(X)}   \\
&&&     \text{Reads(Y)} \\ &  &&\text{Commit} \\\hline 
\end{array}}$$
Which one of the following statements is CORRECT?

  1. S is conflict-serializable but not recoverable
  2. S is not conflict-serializable but is recoverable
  3. S is both conflict-serializable and recoverable
  4. S is neither conflict-serializable not is it recoverable
edited by

3 Answers

Best answer
64 votes
64 votes
Answer: S is both conflict serializable and recoverable.
           
Recoverable? Look if there are any dirty reads? Since there are no dirty read, it simply implies schedule is recoverable( if there were dirty read, then we would have taken into consideration the order in which transactions commit)

Conflict serializable? Draw the precedence graph( make edges if there is a conflict instruction among Ti and Tj. But for the given schedule, no cycle exists in precedence graph, thus it's conflict serializable.

Hope this helps.
edited by
87 votes
87 votes

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 :

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. 

edited by
5 votes
5 votes
To check for conflict-serializable, we need to make a precedence graph, if the graph contains a cycle, then it's not conflict serializable, else it is. Here, for the precedence graph there will be only two directed edges, one from T2 -> T3 ( Read- Write Conflict), and another from T2 -> T1( Read- Write Conflict), hence no cycle, so the schedule is conflict serializable. Now to check for Recoverable, we need to check for a dirty-read operation( Write by Transaction Ti, followed by Read by Transaction Tj but before Ti commits) between any pair of operations. If no dirty-read then recoverable schedule, if a dirty read is there then we need to check for commit operations. Here no dirty read operation ( as T3 and T1 commits before T4 reads the Write(X) of T3 and T1 , and T2 commits before T4 reads the Write(Y) of T2 ). Therefore the schedule is recoverable. Hence, Option C.
Answer:

Related questions