Browse By

How to check for View Serializable and Conflict Serializable

This is a note for myself about how to check whether a schedule is view serializable, conflict serializable, or not.

There is various resources in the internet about how to do this, but the examples are a bit scattered, so in this post I just want to make a neat note on how to do it properly with several examples that can cover many possibilities as well.

Let’s get started!

For the sake of this tutorial, we will use this example:
R1(X),R2(Y),R2(Y),W2(X),W3(Y),R1(X)

or if we spread it to three different transactions, it will be:

T1 |  R1(X)                         R1(X)
T2 |        R2(Y) R2(Y) W2(X)
T3 |                          W3(Y)

How to check for Conflict Serializable?

To check for conflict serializability takes two steps.
Step #1 : Check for the conflicting actions.

(From Wikipedia)
——————————————————
Two or more actions are said to be in conflict if:

1. The actions belong to different transactions.
2. At least one of the actions is a write operation.
3. The actions access the same object (read or write).

The following set of actions is conflicting:

T1:R(X), T2:W(X), T3:W(X)

While the following sets of actions are not:

T1:R(X), T2:R(X), T3:R(X)
T1:R(X), T2:W(Y), T3:R(X)
—————————————————–

For our example, we have a conflict on X (T1 reads it and T2 writes it).
We also have a conflict on Y (T2 reads it and T3 writes it).

So it has a conflict property but is it serializable?

Step #2 : Check for a cycle in the Precedence Graph.

The easiest way to check for a cyclic transaction, is to paste the schedule to this web app.

But if you are like me, you won’t be satisfied getting answer from someone without understanding how exactly they come up with the the answer (though sometimes I don’t care either..). So let’s find out how to do exactly just that.

First, draw all the Transactions (Tx):

precedence graph - initial

Check if there is a Tx that reads an item after a different Tx writes it.

  • We have T1 that reads X after T2 writes it, so draw arrow from T2 -> T1

Check if there is a Tx that writes an item after a different Tx reads it.

  • We have T2 that writes X after T1 reads it, so draw arrow from T1 -> T2
  • We also have T3 that writes Y after T2 reads it, so draw arrow from T2 -> T3

Check if there is a Tx that writes an item after a different TX writes it.

  • not in this case

So, the final graph is :

example-1

We can see that there is a cycle between T1 and T2, so the graph is cyclic, and therefore it is not conflict serializable.

Need more example?
Graph for R1(X),R2(Y),W3(Z),W2(Y),W2(X),R1(Z),W3(Y),W2(X)
example-2-and-3

Graph for R1(X),R2(Y),R3(Z),W2(Y),W2(X),W1(Z),W3(Y),W2(X)

(same like the previous example)

How to check for View Serializable?

To check for view serializability of a schedule, you must create all possible combinations of the Transactions. So let’s say you have three transactions, then you need to check for these combinations:
< T1, T2, T3 >
< T1, T3, T2 >
< T2, T1, T3 >
< T2, T3, T1 >
< T3, T1, T2 >
< T3, T2, T1 >

Now the schedule is view serializable if:

A Tx reads an initial data in a Schedule, the same Tx also should read the initial data in one of the transaction combination.

  • For our example, at least T1 should occur before T2, because T1 reads initial value X. If T2 occurs before T1, then T1 reads X value after T2 writes. So remove these combinations:
    • < T2, T1, T3 >
    • < T2, T3, T1 >
    • < T3, T2, T1 >

A Tx reads a data after another Tx has written in a Schedule, the same Tx also should read the data after another Tx has written it in one of the transaction combination.

  • In our example, T1 reads X after T2 writes, so it means that T2 should occur before T1. But wait a minute, isn’t it we’ve just said that T1 should occur before T1 on the previous condition? That’s what a cycle in the graph also caused. We need T1 before T2 and at the same time we need T2 before T1. Because of this, none of the combinations can satisfy these two conditions, so it is not view serializable.

A Tx writes the final value for a data in a Schedule, the same Tx should also write the final data in one of the transaction combination.

  • Although we’ve said that our schedule is not view serializable, let’s just take a look which combination satisfy this condition. We know that T2 writes Y and X, but in our schedule the T3 writes the last value of Y. So the combination that satisfy these condition should have T2 occur before T3. If we are to choose the combinations, keep everything else but remove these:
    • < T1, T3, T2 >
    • < T3, T1, T2 >
    • < T3, T2, T1 >

View Serializable Example:

Now, let’s take a look an example that is view serializable
W3(Z), R2(X), W2(Y), R1(Z), W3(Y), W1(Y)

A Tx reads an initial data in a Schedule, the same Tx also should read the initial data in one of the transaction combination.

  • Here, at least T2 must occur first, though it actually doesn’t matter also because no one else writes X, so we still keep all our Tx combinations.

A Tx reads a data after another Tx has written in a Schedule, the same Tx also should read the data after another Tx has written it in one of the transaction combination.

  • Now, this means that T1 must occur after T3 because T1 reads Z after T3 writes it. So we remove
    • < T1, T2, T3 >
    • < T1, T3, T2 >
    • < T2, T1, T3 >

A Tx writes the final value for a data in a Schedule, the same Tx should also write the final data in one of the transaction combination.

  • Here, T1 must occur last after T3 or T2 because if not T3 or T2 will overwrites Y that T1 writes in our schedule. So we remove  < T3, T1, T2 >

So the two combinations left satisfy the view serializability this time, they are:

  • < T2, T3, T1 >
  • < T3, T2, T1 >

Conclusion

That’s all friends! Now you know how to check a database schedule for its view and conflict serializability. Questions, critics and comments are welcome. 😀


44 thoughts on “How to check for View Serializable and Conflict Serializable”

  1. Jeremy says:

    Your note is useful, thanks from Hong Kong.

    1. djitz says:

      You’re welcome Jeremy! 😀

  2. Varun says:

    Good Work.
    Can u pls explain view serializability example using R1(X), W1(X), R2(X), W2(X), R3(X), W3(X) instead of . Correct me if this cannot be applied for view serializability.

    1. djitz says:

      Hi Varun,

      Hmm.. I think for view serializability check, we really should test the transactions if they are executed in any of these six combinations:

      Because although in a schedule the transaction overlaps each other, if its result is equal to one or more of these combination, then it is view serializable. If not, then it is not view serializable. 😀

  3. Elie says:

    useful note
    thank you for spending the time making it . 🙂

    1. djitz says:

      You’re welcome Elie! 😀

  4. Ash says:

    We have T2 that reads X after T1 reads it, so draw arrow from T1 -> T2

    We have T2 that WRITE X after T1 reads it, so draw arrow from T1 -> T2

  5. djitz says:

    @Ash, thanks for catching the mistakes, I’ve fixed them.. 😀

  6. rajdeep says:

    Usefull notes.thanks.

  7. A.R.Kiran says:

    thanks yaar good explanation

  8. venkat says:

    usefull notes.
    but i want an example of View Serializable which is not Conflict Serializable..

  9. djitz says:

    hmm.. yeah, unfortunately I don’t have such example also.

    Anyway, I hope my explanation is clear enough to make people able to tell when such case occur. 😀

  10. sourav says:

    today is my DBMS exam… thanks for this note….

  11. neghah says:

    thank you so much you helped me to do my assignmet

  12. priyasmita says:

    thanks a lot,it has been extremely helpful.

  13. IT Man says:

    Thank you very much. My teacher taught is a bullshit. All thanks to you

  14. anuran says:

    beautifully done,good examples

  15. Saidah says:

    Many thanks for this summarize and easy explanation.

  16. Seda says:

    Thank you so much I will get the highest mark tomorrow 🙂

  17. Vasana says:

    Thanks a lot for your valuable lesson.

  18. nils says:

    thanks dude…..i was strugling for this from past 2 days. india

  19. nils says:

    Does every conflict serializable is view serializable ?

    1. djitz says:

      yes, it is (link to Wikipedia).

  20. Nilay says:

    Thanks a lot. . .

  21. sir42 says:

    gud work my friend..keep it up..

  22. indika says:

    nice one dude!!very useful.thanx alot!!

  23. Shashank Bhardwaj says:

    Good, Very Good. Really Useful, So much simple language. Excelent! With Real Examples, With Easy Steps. Good.

  24. saumya says:

    thanx zillions of times…..

  25. pavan says:

    Thanks sir…..

  26. nils says:

    Can you show how all conflict serializable schedules are view serializable ? Because as per Thomas’ write , there are some view serializable schedules which are not conflict serializable..

  27. shanu says:

    really a gud job!!

  28. Bhushan says:

    keep the good work up…. thanx buddy 🙂
    -from India

  29. LAst day exam study! says:

    You saved my a** in the final day of the exam. Thank you so much!!! You should put a paypal donation, i would do that ! THANKS MAN!!

  30. Somen dutta says:

    Good understanding

  31. chandan says:

    Thanks very very nice explanation

  32. kamal says:

    thaaaanks

  33. Dipak Panchasara says:

    Hey Dude.
    you really done nice job…….

    Thanks a lot……….

  34. Nikhil says:

    Pretty well explaind…
    Thanks a lot 🙂

  35. dinesh says:

    AMAZING WORK!!!KUDOS TO DJITZ…

  36. vijeta says:

    best notes ever very very thank u

  37. Tim says:

    Great write up save me big time

  38. Jonathan says:

    Many thanks! It’s very hard to find any information about VS-condition of view serializability even with the help of Google and Wikipedia. Finally found here

  39. Abdullah says:

    You are going to heaven man!
    Thank you so much for this article. Finally, I got a bit
    understanding about these bad boys.

Leave a Reply

Your email address will not be published. Required fields are marked *