Horje
Equivalent Serial Schedule of Conflict Serializable Schedule in DBMS

Prerequisite: Conflict Serializability, Precedence Graph

Conflict Serializable Schedule: A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. The serial schedule of the Conflict Serializable Schedule can be found by applying topological Sorting on the Precedence Graph of the Conflict Serializable Schedule.

Note: Precedence Graph of Conflict Serial Schedule is always directed acyclic graph.

Approach: Follow to below steps to find topological sorting of Precedence Graph:

  • Find the indegree of all nodes for the given Precedence Graph and store it in an auxiliary array.
  • Now For each node having indegree 0 perform the following:
    • Print the current node T as the order of the topological sort.
    • Let the node T be the node with in-degree 0.
    • Remove T and all edges connecting to T from the graph.
    • Update indegree of all nodes after the above steps.
  • After the above steps, the topological sort of the given precedence graph can be calculated.

Below is the illustration of the above approach:

Let, the Conflict Serial Schedule be S: R2(A) W2(A) R3(C) W2(B) W3(A) W3(C) R1(A) R2(B) W1(A) W2(B)

  • Here node T2 has indegree 0.
  • So, select T2 and remove T2 and all edges connecting from it.
  • Now T3 has indegree 0. So, select T3 and remove the edge T3→T1.
  • At the end select T3. So the topological Sorting is T2, T3, T1.
  • Hence, the equivalent serial schedule of given conflict serializable schedule is T2→T3→T1, i.e., S2: R2(A) W2(A) W2(B) R3(C) W3(A) W3(C) R1(A) R2(B) W1(A) W1(B).

There may be more than one equivalent serial schedule of the conflict serializable schedule.

Below is the implementation to get the Serial Schedule of CSS using Topological Sorting:

C++

// C++ program to print serial schedule
// of CSS using Topological sorting
#include <bits/stdc++.h>
using namespace std;
 
class PrecedenceGraph {
 
    // No. of vertices
    int V;
 
    // Pointer to an array containing
    // adjacency vector
    vector<int>* adj;
 
    // Vector to store SerialSchedule
    vector<int> serialSchedule;
 
    // Function  declarations
    void computeIndegree(int* indegree);
    int findZeroIndegree(int* indegree,
                         bool* visited);
 
public:
    // Constructor
    PrecedenceGraph(int V);
 
    // Function declarations
    void addEdge(int v, int w);
    void topologicalSort();
    void printSchedule();
};
 
// Function to create the precedence
// graph
PrecedenceGraph::PrecedenceGraph(int V)
{
    this->V = V;
    adj = new vector<int>[V];
}
 
// Function to add the edge to the
// precedence graph
void PrecedenceGraph::addEdge(int v,
                              int w)
{
    adj[v].push_back(w);
}
 
// Function to compute indegree of nodes
void PrecedenceGraph::computeIndegree(
    int* indegree)
{
    for (int i = 1; i < V; i++) {
 
        // Traverse the adjacency list
        // of node i
        for (int j = 0;
             j < adj[i].size(); j++) {
            int node = adj[i][j];
 
            // Update the indegree
            // of node
            indegree[node]++;
        }
    }
}
 
// Function to find node with
// zero indegree
int PrecedenceGraph::findZeroIndegree(
    int* indegree, bool* visited)
{
    for (int i = 1; i < V; i++) {
 
        // If node is not visited
        // and have indegree 0
        if (!visited[i]
            && indegree[i] == 0) {
 
            // Mark node visited
            visited[i] = true;
 
            // Return node
            return i;
        }
    }
 
    // All nodes are visited
    return -1;
}
 
// Function to find the topological
// Sorting of the given graph
void PrecedenceGraph::topologicalSort()
{
    // Create and initialize
    // visited array
    bool* visited = new bool[V]();
 
    // Create and initialize
    // indegree array
    int* indegree = new int[V]();
 
    computeIndegree(indegree);
 
    // Check if the node with
    // indegree 0 is available
    int node = findZeroIndegree(
        indegree, visited);
 
    bool nodeAvailable = false;
 
    if (node != -1) {
        nodeAvailable = true;
    }
    while (nodeAvailable) {
 
        // Add node to serial schedule
        serialSchedule.push_back(node);
 
        for (int i = 0;
             i < adj[node].size(); i++) {
 
            // Delete all edges of current
            // node and update indegree
            indegree[adj[node][i]]--;
        }
 
        // Find next node with indegree 0
        node = findZeroIndegree(indegree,
                                visited);
 
        if (node == -1) {
 
            // Node with zero indegree
            // not available
            nodeAvailable = false;
        }
    }
}
 
// Function to print the serial schedule
void PrecedenceGraph::printSchedule()
{
    for (int i : serialSchedule) {
        cout << "T" << i << " ";
    }
}
 
// Driver Code
int main()
{
    // Create a precedence graph
    // given in the above diagram
    PrecedenceGraph graph(4);
    graph.addEdge(2, 1);
    graph.addEdge(2, 3);
    graph.addEdge(3, 1);
 
    // Find topological ordereing
    graph.topologicalSort();
 
    // Print Schedule
    cout << "Equivalent Serial"
         << " Schedule is :";
    graph.printSchedule();
}

Java

// Java program to print serial schedule
// of CSS using Topological sorting
 
import java.util.*;
 
class PrecedenceGraph {
    // No. of vertices
private int V;
 
// Pointer to an array containing
// adjacency vector
private ArrayList<Integer>[] adj;
 
// Vector to store SerialSchedule
private ArrayList<Integer> serialSchedule;
 
// Function to create the precedence
// graph
PrecedenceGraph(int V) {
    this.V = V;
    adj = new ArrayList[V];
    for (int i = 0; i < V; i++) {
        adj[i] = new ArrayList<>();
    }
    serialSchedule = new ArrayList<>();
}
 
// Function to add the edge to the
// precedence graph
void addEdge(int v, int w) {
    adj[v].add(w);
}
 
// Function to compute indegree of nodes
void computeIndegree(int[] indegree) {
    for (int i = 1; i < V; i++) {
        // Traverse the adjacency list
        // of node i
        for (int j = 0; j < adj[i].size(); j++) {
            int node = adj[i].get(j);
 
            // Update the indegree
            // of node
            indegree[node]++;
        }
    }
}
 
// Function to find node with
// zero indegree
int findZeroIndegree(int[] indegree, boolean[] visited) {
    for (int i = 1; i < V; i++) {
        // If node is not visited
        // and have indegree 0
        if (!visited[i] && indegree[i] == 0) {
            // Mark node visited
            visited[i] = true;
            // Return node
            return i;
        }
    }
    // All nodes are visited
    return -1;
}
 
// Function to find the topological
// Sorting of the given graph
void topologicalSort() {
    // Create and initialize
    // visited array
    boolean[] visited = new boolean[V];
 
    // Create and initialize
    // indegree array
    int[] indegree = new int[V];
 
    computeIndegree(indegree);
 
    // Check if the node with indegree 0 is available
    int node = findZeroIndegree(indegree, visited);
 
    boolean nodeAvailable = false;
 
    if (node != -1) {
        nodeAvailable = true;
    }
    while (nodeAvailable) {
        // Add node to serial schedule
        serialSchedule.add(node);
 
        for (int i = 0; i < adj[node].size(); i++) {
            // Delete all edges of current
            // node and update indegree
            indegree[adj[node].get(i)]--;
        }
 
        // Find next node with indegree 0
        node = findZeroIndegree(indegree, visited);
 
        if (node == -1) {
            // Node with zero indegree
            // not available
            nodeAvailable = false;
        }
    }
}
 
// Function to print the serial schedule
void printSchedule() {
    for (int i : serialSchedule) {
        System.out.print("T" + i + " ");
    }
    System.out.println();
}
}
 
// Driver Code
class Main {
public static void main(String[] args) {
// Create a precedence graph
// given in the above diagram
PrecedenceGraph graph = new PrecedenceGraph(4);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
  
    // Find topological ordereing
    graph.topologicalSort();
  
    // Print Schedule
    System.out.print("Equivalent Serial Schedule is :");
    graph.printSchedule();
     
}
}
 
// This code is contributed by Pushpesh Raj.

Python3

# Python program to print serial schedule of CSS using Topological sorting
from collections import defaultdict
 
class PrecedenceGraph:
    # Constructor
    def __init__(self, V):
        self.V = V
        self.adj = defaultdict(list)
        self.serialSchedule = []
 
    # Function to add the edge to the precedence graph
    def addEdge(self, v, w):
        self.adj[v].append(w)
 
    # Function to compute indegree of nodes
    def computeIndegree(self, indegree):
        for i in range(1, self.V):
            for node in self.adj[i]:
                # Update the indegree of node
                indegree[node] += 1
 
    # Function to find node with zero indegree
    def findZeroIndegree(self, indegree, visited):
        for i in range(1, self.V):
            # If node is not visited and have indegree 0
            if not visited[i] and indegree[i] == 0:
                # Mark node visited
                visited[i] = True
                # Return node
                return i
        # All nodes are visited
        return -1
 
    # Function to find the topological Sorting of the given graph
    def topologicalSort(self):
        # Create and initialize visited array
        visited = [False for i in range(self.V)]
 
        # Create and initialize indegree array
        indegree = [0 for i in range(self.V)]
 
        self.computeIndegree(indegree)
 
        # Check if the node with indegree 0 is available
        node = self.findZeroIndegree(indegree, visited)
        nodeAvailable = False
        if node != -1:
            nodeAvailable = True
 
        while nodeAvailable:
            # Add node to serial schedule
            self.serialSchedule.append(node)
            for next_node in self.adj[node]:
                # Delete all edges of current node and update indegree
                indegree[next_node] -= 1
 
            # Find next node with indegree 0
            node = self.findZeroIndegree(indegree, visited)
 
            if node == -1:
                # Node with zero indegree not available
                nodeAvailable = False
 
    # Function to print the serial schedule
    def printSchedule(self):
        print("Equivalent Serial Schedule is: ", end="")
        for i in self.serialSchedule:
            print("T{} ".format(i), end="")
 
# Driver Code
if __name__ == "__main__":
    # Create a precedence graph given in the above diagram
    graph = PrecedenceGraph(4)
    graph.addEdge(2, 1)
    graph.addEdge(2, 3)
    graph.addEdge(3, 1)
 
    # Find topological ordereing
    graph.topologicalSort()
 
    # Print Schedule
    graph.printSchedule()

C#

using System;
using System.Collections.Generic;
 
public class PrecedenceGraph
{
   
    // No. of vertices
    private int V;
 
    // Pointer to an array containing
    // adjacency vector
    private List<int>[] adj;
 
    // Vector to store SerialSchedule
    private List<int> serialSchedule = new List<int>();
 
    // Constructor
    public PrecedenceGraph(int V)
    {
        this.V = V;
        adj = new List<int>[ V ];
        for (int i = 0; i < V; i++) {
            adj[i] = new List<int>();
        }
    }
 
    // Function to add the edge to the
    // precedence graph
    public void addEdge(int v, int w) { adj[v].Add(w); }
 
    // Function to compute indegree of nodes
    private void computeIndegree(int[] indegree)
    {
        for (int i = 1; i < V; i++) {
            // Traverse the adjacency list
            // of node i
            foreach(int node in adj[i])
            {
                // Update the indegree
                // of node
                indegree[node]++;
            }
        }
    }
 
    // Function to find node with
    // zero indegree
    private int findZeroIndegree(int[] indegree,
                                 bool[] visited)
    {
        for (int i = 1; i < V; i++) {
            // If node is not visited
            // and have indegree 0
            if (!visited[i] && indegree[i] == 0) {
                // Mark node visited
                visited[i] = true;
 
                // Return node
                return i;
            }
        }
 
        // All nodes are visited
        return -1;
    }
 
    // Function to find the topological
    // Sorting of the given graph
    public void topologicalSort()
    {
        // Create and initialize
        // visited array
        bool[] visited = new bool[V];
 
        // Create and initialize
        // indegree array
        int[] indegree = new int[V];
 
        computeIndegree(indegree);
 
        // Check if the node with
        // indegree 0 is available
        int node = findZeroIndegree(indegree, visited);
 
        bool nodeAvailable = false;
 
        if (node != -1) {
            nodeAvailable = true;
        }
 
        while (nodeAvailable) {
            // Add node to serial schedule
            serialSchedule.Add(node);
 
            foreach(int i in adj[node])
            {
                // Delete all edges of current
                // node and update indegree
                indegree[i]--;
            }
 
            // Find next node with indegree 0
            node = findZeroIndegree(indegree, visited);
 
            if (node == -1) {
                // Node with zero indegree
                // not available
                nodeAvailable = false;
            }
        }
    }
 
    // Function to print the serial schedule
    public void printSchedule()
    {
        foreach(int i in serialSchedule)
        {
            Console.Write("T" + i + " ");
        }
    }
}
 
public class Program {
    public static void Main(string[] args)
    {
        // Create a precedence graph
        // given in the above diagram
        PrecedenceGraph graph = new PrecedenceGraph(4);
        graph.addEdge(2, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
 
        // Find topological ordering
        graph.topologicalSort();
 
        // Print Schedule
        Console.Write("Equivalent Serial Schedule is: ");
        graph.printSchedule();
    }
}

Javascript

class PrecedenceGraph {
  // Constructor
  constructor(V) {
    this.V = V;
    this.adj = new Map();
    this.serialSchedule = [];
  }
 
  // Function to add the edge to the precedence graph
  addEdge(v, w) {
    if (!this.adj.has(v)) {
      this.adj.set(v, []);
    }
    this.adj.get(v).push(w);
  }
 
  // Function to compute indegree of nodes
  computeIndegree(indegree) {
    for (let i = 1; i < this.V; i++) {
      // Check if the current node exists in the adjacency list
      if (!this.adj.has(i)) {
        continue;
      }
      // Update the indegree of all adjacent nodes
      for (const node of this.adj.get(i)) {
        indegree[node] += 1;
      }
    }
  }
 
  // Function to find node with zero indegree
  findZeroIndegree(indegree, visited) {
    for (let i = 1; i < this.V; i++) {
      // If node is not visited and have indegree 0
      if (!visited[i] && indegree[i] === 0) {
        // Mark node visited
        visited[i] = true;
        // Return node
        return i;
      }
    }
    // All nodes are visited
    return -1;
  }
 
  // Function to find the topological Sorting of the given graph
  topologicalSort() {
    // Create and initialize visited array
    const visited = new Array(this.V).fill(false);
 
    // Create and initialize indegree array
    const indegree = new Array(this.V).fill(0);
 
    // Compute indegree of nodes
    this.computeIndegree(indegree);
 
    // Check if the node with indegree 0 is available
    let node = this.findZeroIndegree(indegree, visited);
    let nodeAvailable = false;
    if (node !== -1) {
      nodeAvailable = true;
    }
 
    while (nodeAvailable) {
      // Add node to serial schedule
      this.serialSchedule.push(node);
      // Delete all edges of current node and update indegree
      if (this.adj.has(node)) {
        for (const nextNode of this.adj.get(node)) {
          indegree[nextNode] -= 1;
        }
      }
      // Find next node with indegree 0
      node = this.findZeroIndegree(indegree, visited);
      if (node === -1) {
        // Node with zero indegree not available
        nodeAvailable = false;
      }
    }
  }
 
  // Function to print the serial schedule
  printSchedule() {
    let result = "Equivalent Serial Schedule is: ";
    for (const i of this.serialSchedule) {
      result += `T${i} `;
    }
    console.log(result);
  }
}
 
// Driver Code
const graph = new PrecedenceGraph(4);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
graph.topologicalSort();
graph.printSchedule();

Output: 

Equivalent Serial Schedule is :T2 T3 T1

 

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
Find a set of at most N/2 nodes from a Graph such that all remaining nodes are directly connected to one of the chosen nodes Find a set of at most N/2 nodes from a Graph such that all remaining nodes are directly connected to one of the chosen nodes
Observations on graph Observations on graph
Maximum GCD of all nodes in a connected component of an Undirected Graph Maximum GCD of all nodes in a connected component of an Undirected Graph
Check for transitive property in a given Undirected Graph Check for transitive property in a given Undirected Graph
Minimize count of connections required to be rearranged to make all the computers connected Minimize count of connections required to be rearranged to make all the computers connected

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje