what is the serializability graph of this?

Question

I try to figure out a question, however I do not how to solve it, I am unannounced most of the terms in the question. Here is the question:

Three transactions; T1, T2 and T3 and schedule program s1 are given below. Please draw the precedence or serializability graph of the s1 and specify the serializability of the schedule S1. If possible, write at least one serial schedule. r ==> read, w ==> write

T1: r1(X);r1(Z);w1(X);

T2: r2(Z);r2(Y);w2(Z);w2(Y);

T3: r3(X);r3(Y);w3(Y);

S1: r1(X);r2(Z);r1(Z);r3(Y);r3(Y);w1(X);w3(Y);r2(Y);w2(Z);w2(Y);

I do not have any idea about how to solve this question, I need a detailed description. In which resource should I look for? Thank in advance.

Answer 1

There are various ways to test for serializability. The Objective of serializability is to find nonserial schedules that allow transactions to execute concurrently without interfering with one another.

First we do a Conflict-Equivalent Test. This will tell us whether the schedule is serializable.

To do this, we must define some rules (i & j are 2 transactions, R=Read, W=Write).

We cannot Swap the order of actions if equivalent to:

1. Ri(x), Wi(y) - Conflicts 
2. Wi(x), Wj(x) - Conflicts
3. Ri(x), Wj(x) - Conflicts 
4. Wi(x), Rj(x) - Conflicts

But these are perfectly valid:

R1(x), Rj(y) - No conflict (2 reads never conflict)
Ri(x), Wj(y) - No conflict (working on different items)
Wi(x), Rj(y) - No conflict (same as above)
Wi(x), Wj(y) - No conflict (same as above)

So applying the rules above we can derive this (using excel for simplicity):

From the result, we can clearly see with managed to derive a serial-relation (i.e. The schedule you have above, can be split into S(T1, T3, T2).

Now that we have a serializable schedule and we have the serial schedule, we now do the Conflict-Serialazabile test:

Simplest way to do this, using the same rules as the conflict-equivalent test, look for any combinations which would conflict.

r1(x); r2(z); r1(z); r3(y); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y);
----------------------------------------------------------------------
              r1(z)                                     w2(z)
                            r3(y)                              w2(y)
                                          w3(y)  r2(y)
                                          w3(y)                w2(y)

Using the rules above, we end up with a table like above (e.g. we know reading z from one transaction and then writing z from another transaction will cause a conflict (look at rule 3).

Given the table, from left to right, we can create a precedence graph with these conditions:

T1 -> T2
T3 -> T2 (only 1 arrow per combination)

Thus we end up with a graph looking like this:

From the graph, since there it's acyclic (no cycle) we can conclude the schedule is conflict-serializable. Furthermore, since its also view-serializable (since every schedule that's conflict-s is also view-s). We could test the view-s to prove this, but it's rather complicated.

Regarding sources to learn this material, I recommend:

"Database Systems: A practical Approach To design, implementation and management: International Edition" by Thomas Connolly; Carolyn Begg - (It is rather expensive so I suggest looking for a cheaper, pdf copy)

Good luck!

Update I've developed a little tool which will do all of the above for you (including graph). It's pretty simple to use, I've also added some examples.