Constructing Precedence Graph to Check Conflict Serializability

Constructing Precedence Graph to Check Conflict Serializability



hello everyone welcome to tech comm in this lecture we will understand how we can test whether a given schedule is conflict serializable okay so we have already studied how to test the conflict serializability in last lecture so in that lecture what did we do we basically compared all the conflicting operations with some serial schedule but that's not the correct way of doing this because that procedure is very very much time-consuming so Google we have a nice algorithm to test whether the given schedule is conflict serializable okay so to start with let's take a you'll so we have this schedule which we worked on in the last lecture okay and now we will use the algorithm of constructing precedence graph to test whether this given schedule is conflict serializable okay so the first step of constructing this precedence graph is you construct the graph or you start with nodes number of nodes equal to number of transaction okay so here as I have two transaction how do I know this that I have two transactions you can see as I have already explained that in a transaction or in a schedule given like this you can identify this number this number is transaction number okay this is variable okay or database item on which this particular operation which is read operation okay is walking so you know that you have transaction 1 T 1 and 2 you don't have any operation from 3 right as we have only 1 2 1 2 here ok so we have only two transactions here so what we will do we will construct two nodes we will call it 1 okay and we will call it – great now what is the second thing we have to do we have to construct directed ages okay and what is the procedure for that the procedure is that we construct directed age I – J for each conflicting operation oh I – Oh J okay I am denoting Oh as operation okay so for each conflicting operations set I mean when it is conflicting it will be pair of operations okay so for each conflicting operation we will take one edge from I to J where I is the first operation in the series and J is the second operation in the series okay so we will understand it in better manner just now so now let's use this second point so we already know what is conflicting operation right what is conflicting operation a conflicting operation is set of operations okay which are walking on same data base item belonging to two different transactions and at least one of the operation is right operation okay so let's see whether for this first operation this first operation we have any conflicting operation so the idea is that start looking for X with the right operation why I am saying this as this is read it will have conflict with right only okay so do we have write X here we have write X okay now here we have write X now as this transaction is T 1 it will be conflicting with some other than one transaction T one transaction okay so here as it is right X but from the same transaction 1 so it will not be conflicting but this will be conflicting ok so these two transactions are 1 X and W 2 X are conflicting ok so we have got one conflicting operation ok as we got this conflicting operation we will draw an edge here so it will be one to two edge fine now let's check for other conflicting operation so now this r1 is not conflicting with any other operation we have to check for or all other operation not just the first operation with which this operation is conflicting okay even if we have something here let's say I am assuming so if we have w3x then this will also be conflicting with this operation right and we should have here another node 3 and then we have to draw an edge but here this is not the case so we will not have another edge and another node I just took it to explain the situation that you don't have to stop where you get first conflicting operation you have to check thoroughly that whether this first operation conflicts with any other operation ok fine so ok now the second operation are to X ok so this is first I am writing this is first conflict now second operation are two X it will have a conflict with something which is working on X but right operation from different transaction right so if we look for right we have one right here and on X variable yes so this is again our two these two are conflicting right ok so the edge will be from 2 to 1 by 2 to 1 because 2 is occurring first and then 1 as I am saying I 2 J you have to draw a edge because we have gotten conflicting operation I and J ok I followed followed by J right ok so here you will draw an edge 2 2 1 2 2 1 ok now let's go for another conflicting operation with Aitu so with our two now I do not have any conflicting operation okay now start with W 2 W 1 X ok so W 1 X does not have here we have this W and X this operation and this operation is conflicting right right you can see right ok as these are on same variable different transaction one of the operation is right okay so this is conflicting now what will be the age direction of phase 1 to 2 okay 1 to 2 so 1 to 2 we already have is an edge ok fine now similarly you can keep on drawing so after R 1 R 1 by from R 1 why I do not have any conflicting operation because on Y variable I have only this right and which is from the same transaction similarly this doesn't have any conflicting operation further and mine will when I am checking conflicting operation I am checking after this operation of it so when this operation occurs after this in this direction not previous one previous we have already checked ok so in this direction we keep on checking and would do next operation right ok now third point is if this graph has a cycle then it is not conflict serializable so if the graph has a cycle in it then the shedule given schedule is not conflict serializable okay not conflict serializable fine so if graph has cycle then not conflict serializable and if graph doesn't have any cycle then it will be conflict serializable so here you can see that the graph has this graph has you can see that this graph has cycle so this cycle 1 2 2 1 ok so it has some cycle so this schedule here given schedule s is not conflict serializable so this is not conflict serializable okay so this is the simple processor now we will solve many problems to understand it in better manner so see you in the next lecture thanks for watching

28 thoughts on “Constructing Precedence Graph to Check Conflict Serializability”

  1. What if we have commit in between? should we just ignore those commits and do the same thing as you explaine?
    Imagine the schedule is as follow :
    r3(x), r3(y), w3(p), w4(q), r2(p), w3(x), commit 3, r1(x), w1(y), commit 1, r4(y), w4(y), commit 4, commit 2.
    How we should treat it?

  2. I've watched so many other videos, some in half hindi half english, some in english but dont explain well. Yours was clear and very helpful explanation. Thank you!

  3. Before reading data item X by T2, T1 has already written data Item X.
    i think these are the conflicting operations here
    R2(X)–W1(X) and W1(X)–W2(X)

    please clear my confusion..
    Thanks.

  4. sir,firstly thank you very much for the videos they are soo helpful and they explain all the concepts one needs to know before solving the problems. now i have a question regarding one of your video,is it necessary to check for all the possible serial schedules for checking conflict serializability?

  5. awesome sir
    sir plz make a list of all solved example of transaction in the youtube playlist channel .There is no list,Thanks

Leave a Reply

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

Tags: , , , , , , ,