# Precedence Graph | DBMS

**DBMS precedence graph**: In this tutorial, we are going to learn about the **precedence graph** and **the algorithm for testing conflict serializability of a schedule** in the database management system.

Submitted by Anushree Goswami, on September 06, 2019

## Precedence graph

A **precedence graph**, also known as **serialization graph or conflict graph**, is used for testing Conflict Serializability of a schedule in the condition that forms the setting of concurrency control in databases.

It is also known as a **directed Graph G = (V, E)**, which consists of a pair of a set of nodes **V = {V1, V2, V3, ..., Vn}** and a set of directed edges **E = {E1, E2, E3, ..., Em}**. Where the set of nodes **V** are testing to retrieve identical data attribute through the transactions of a schedule and the set of edges **E** is regulated connectivity between a set of two nodes.

**Nodes:** In the graph, for each transaction **Tp** the graph contains a single node. So, In a schedule of a **precedence graph**, The total number of transactions will be similar to the total number of nodes.

**Edges:** An edge is regulated connectivity between a set of two distinct transactions **Tq** and **Tr** and it shows in the format **Tq –>Tr**, where **Tq** is the beginning of the edge and **Tr** is the ending.

### The Algorithm for testing Conflict Serializability of a schedule

- Create a node
**T**, for each transaction participating in schedule**S**in the**precedence graph**. - For every condition in schedule
**S**create an edge**Tp → Tq**in the**precedence graph**if a Transaction**Tq**implements a**read_item (Z)**after**Tp**implements a**write_item (Z)**. It's a Read-Write conflict. - For every condition in schedule
**S**create an edge**Tp → Tq**in the precedence graph if a Transaction**Tq**implements a**write_item (Z)**after**Ti**implements a**read_item (Z)**. It's a Write-Read conflict. - For every condition in schedule
**S**create an edge**Tp → Tq**in the precedence graph If a Transaction**Tq**implements a**write_item (Z)**after**Tp**implements a**write_item (Z)**. It's a Write-Write conflict. - If and only if there is no cycle in the
**precedence graph**, then the schedule**S**is Serializable.

**Example:**

**Q1) Find the following Schedule S is conflict Serializable or not?**

**Solution:**

Let's make a precedence graph,

In the above **precedence graph**, by following accordingly to the Algorithm, Transaction **Tp** implements reads **A** before Transaction **Tq** implements writes **A**, therefore the first arrow directed from Transaction **Tp** towards Transaction **Tq** and Transaction **Tq** reads **B** before Transaction **Tp** writes **B**, therefore the second arrow directed from Transaction **Tq** towards Transaction **Tp**.

Since from the above precedence graph it's clearly visible that the graph is cyclic, therefore the schedule **S** is not conflicted Serializable.

**Q2) Find the following Schedule S is conflict Serializable or not?**

**Solution:**

Let's make a precedence graph,

In the above **precedence graph**, by following accordingly to the Algorithm, Transaction **Tp** implements reads **A** before Transaction **Tq** implements writes **A**, therefore the first arrow directed.

from Transaction **Tp** towards Transaction **Tq** and Transaction **Tq** reads **B** before Transaction **Tr** writes **B**, therefore the second arrow directed from Transaction **Tq** towards Transaction **Tr** and then the Transaction **Tp** reads **C** before Transaction **Tr** writes **C**, therefore the third arrow directed from Transaction **Tp** towards **Tr**.

Since from the above precedence graph it's clearly visible that the graph is acyclic, **therefore the schedule S is conflict Serializable**.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.