How to check Conflict Serializability using Precedence Graph Algorithm

Precedence graph algorithm can be used to find out whether the given concurrent schedule is conflict serializable or not.

Algorithm:

  1. Create the number of node in the graph equal to the number of transactions in the given schedule.
  2. Starting with each and every transaction identify all the existing conflicting operations and represent them in the graph in the form of edges following the direction of the conflicting operation.
  3. Check if the precedence graph has either a cycle or a loop.
  4. If the cycle or loop does exist, then the given schedule is not conflict serializable.
  5. Else the schedule is conflict serializable.
  6. In case the schedule is conflict serializable then apply the Topological ordering in the graph to find out the equivalent serial schedule.

Before going to take the example, let us first understand what is the Topological ordering.

Topological Ordering: The process of selecting the nodes with in-degree zero always, is known as topological ordering.

while applying this process, after selecting the node with in-degree zero, we shall ignore that node further and also we should ignore the edges that were emerging from that selected node.

From the remaining graph we should continue finding the next node with in-degree zero until all the nodes of graph gets selected.

Example: (Topological Ordering)

IMG_20170415_214211.jpgTopological Ordering1

Topological Ordering2

Example (Check for Conflict Serializablity using Precedence Graph)

Precedence Graph.jpg

 

For now signing off until next post. In case you have any doubts, please do not hesitate to ask using the comment section below. I will be happy to clear them.

Also please give your feed back as comment and share your views.

Drive more traffic to your blog using performance based marketing.

You may connect with me on  LinkedIn

Thanks for reading.

Take care!

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s