A Survey on Subgraph Matching Algorithm for Graph Database

Subgraph matching is a technique to retrieve subgraphs which are isomorphic to query graph. A graph S (VS, ES) is subgraph of graph G (VG, EG) if VS ⊆ VG and ES ⊆ EG. Subgraph matching is a process to fetch all subgraphs S (VS, ES) from graph G (VG, EG) which are structurally isomorphic to input graph I(VI, EI) using subgraph matching algorithm. Subgraph matching is a NP-hard. In real-world graphs such as semantic web, social networks, protein interaction and biological networks, subgraph matching will retrieve subgraphs which are isomorphic to query graph from data graph. Many subgraph matching algorithms have proposed in recent years, these algorithms aims to find desired results in less time for real datasets using information like join orders, pruning techniques and vertex neighbour information. Subgraph matching algorithms can be classified into two clases: exact and approximate matching algorithms. These two approaches are being described in survey.