\
Question #2: CS245 Final Exam -- Winter 1996

To solve this problem, we first add our imaginary initial
transaction that "writes"  the initial state of the
database, and we add our imaginary final transaction
that "reads" the final database state.

S= Wb(A)Wb(B)W3(B)W3(A)W1(B)R2(B)R2(A)W1(A)Rf(A)Rf(B)

Our immediate write/read pairs are:

a1: W1(B) => R2(B)
a2: W3(A) => R2(A)
a3: W1(A) => Rf(A)
a4: W1(B) => Rf(B)

These pairs result in the arcs in figure 1.  Note that
                                           0
pairs a3 and a4 both result in the arc T1 ---> Tf.

Figure 1:
			
                    0
                T1 ---> Tf
     Tb        /
            0 /
            |/_  0
           T2 <----- T3

Now, we will consider *each* pair with respect to *each*
write.

W3(B):	* This write could appear to either the left or
        right of pair a1 in the schedule, but not in 
        between W1(B) and R2(B).  Hence, either T3 must
        appear before T1 in an equivalent schedule OR
        T2 must appear before T3.  We denote this by
                         1           1
        the arc pair T3 ---> T1, T2 ---> T3

        * Pairs a2 and a3 are on A, so we don't need
        to consider them.

        * This write must appear to the left of W1(B)
        since it can't appear in between W1(B) and Rf(B),
        and it can't appear after Rf(B).  Hence, we 
                                 0
        must include the arc T3 ---> T1

W3(A):  * Pairs a1 and a4 deal with B, so we don't need
        to consider them.
       
        * This write participates in pair a2, so we don't
        need to consider a2.

        * This write must appear before W1(A) since, 
        because of pair a3, it can't appear in between
        W1(A) and Rf(A), and it can't appear after Rf(A).
                                           0
        Hence, we must include the arc T3 ---> T1

W1(B):  * This write participates in both pairs a1 and
        a4, so we need not consider them.
  
        * Pairs a2 and a3 are both on A, so we need not
        consider them.

W1(A):  * Pairs a1 and a4 are both on B, so we need not
        consider them.

        * This write could appear to either the left or
        right of pair a2, but not in between.  Hence,
        either T1 must appear before T3 OR T2 must
        appear before T1.  We denote this by the arc
                 2           2
        pair T1 ---> T3, T2 ---> T1

All of the arcs determined above give the following
labeled precedence graph:



                            /------\
                            |  Tf  |
                            \------/
                              /|\
                               |0
                               |
                    --------/------\<---------\
                    |       |  T1  |<-----\   |
                    |    /->\------/---|  |   |
          Tb       0|    |             |  |1  |0   
                    |    |2           2|  |   | 
                   \|/   |            \|/ |   |
                   /------\     1      /------\
                   |  T2  |----------->|  T3  |
                   \------/<-----------\------/
                                0

We must now decide which of the arc pairs labeled "1" and
"2" to include to attempt to obtain an acyclic precedence
graph.

We first note that we cannot include the "1" arc from T2
to T3 without creating a cycle.  So, choose the "1" arc
from T3 to T1.  (This also makes sense since we must
include the "0" arc from T3 to T1 anyway.)

Having made the choice for labal "1", we must now choose
one of the arcs labelled "2."  Unfortunately, regardless
of which arc we choos, it will result in a cycle in the
graph.  Hence, the schedule is NOT view serializable.