Anonymous user menu

Conflict and View Serializability and Polygraph Test

We already discussed how to check whether the given schedules are conflict serializable or not. It was fun doing that. We need to make a transition graph and check if there is a cycle or not?

If we get

Cycle then   -----> NO conflict

No cycle       -----> Conflict.


Polygraph Test:-

Checking View Serializability is a little bit tricky thing. 

  1. If a transaction is a Conflict Serializable then it is definitely View Serializable but the reverse may not be true. 
  2. If a  transaction is not conflict serializable then check for Blind Write.
  3. If there is no blind write then NOT View Serializable​.
  4. If Blind Write then Polygraph Test.
  5. Polygraph Test pass then View Serializable

We already know the theory what is View Serializable, So let's talk about how to solve questions in the exam. Basically, in Exam, they will ask you to find to out which one is  View Serializable.

The trick for the Polygraph Test:

Consider every given transaction as a node in the graph.

Step 1: for every data item first see which one is the first transaction to read it. let' say some transaction t is the first one to read it. then you draw outgoing edges from this node to all other transaction except tx.

Step 2: If ty is the transaction which is the last one to perform write operations on that data item, then towards ty you draw incoming edges from all the others transitions. 

Step3: Now you check dependency between the transaction and draw edges accordingly like you did while checking for Conflict Serializable​.

Now if you see any cycle the no view and

no cycle means View.





shashank @shashankjoshi
6 Apr 2020 12:43 pm
first example should be vs
Ambikesh Kumar Singh @ambikeshkumarsingh
12 Apr 2020 12:22 am
Can you please explain Why??
chinmay badjatya @chinmaybadjatya
26 Nov 2020 08:03 pm
I think it's because you have also considered w-w conflicts in the graph, we're supposed to preserve only w-r conflicts, this is what I read on GFG. Please correct me if I'm wrong.