Abstract:
Graph has become a powerful tool for representing
and modeling objects and their relationships in various
application domains such as protein interaction, social networks
and chemical informatics. With the emergence of these
applications, developments of graph databases are very useful to
store graph data. However, performance query processing on
graph database (GDB) is still inadequate due to the high
complexity of processing graph data. As a result, effective graph
structures to store graphs are the current research area to
complete efficient query processing on the graph databases. In
this paper, a new compact graph representative structure(CGRS)
is proposed to perform efficient graph query processing. In
CGRS, a graph is represented holistically via its edge code using
edge dictionary. The idea of graph decomposition is used to
specify all connected, induced subgraphs of a given graph
without changing the structure of the original graphs. Using
CGRS, two types of graph queries can be processed: graph
isomorphism query and subgraph isomorphism query. Chemical
compound dataset is applied to test the effectiveness of our
proposed CGRS. The analysis of storage space, graph
construction time and query response time offers a positive
response to our newly proposed CGRS structure.
