An Efficient Indexing Mechanism for Graph Queries in Graph Databases

Abstract

In recent years, graph has become a powerful tool for representing and modeling objects and their relationships in various application domains such as protein interactions, chemical compounds, social networks, XML documents and so on. The volume of graph data increases rapidly and the graph database becomes an essential role to store graph data. However, the performance of query processing on graph databases is still inadequate due to the high complexity of processing graph data. As a result, it is important to develop efficient indexing structure for query processing on the graph databases. In this paper, we propose both algorithms for graph indexing and subgraph isomorphism query for subgraph query processing in the graph database. We also propose a proficient index structure (AdE) to support both algorithms to quickly index and identify the isomorphic graphs for the given query graph. Like canonical code, AdE checks whether the query graph is a subgraph isomorphic to the database graph. Our proposed index structure significantly reduces the computational time complexity compared to the DGIndex structure.