A novel graph containment query algorithm on graph databases

Nowadays, efficient graph query processing method is coming more and more important along with the structured data accumulating. Given a graph database, a graph containment query retrieves the graphs from the database that are subgraphs of the query graph. In this paper, an algorithm is proposed, which is founded on a CFG (Closed Frequent subgraph) based index, to answer graph containment query. CFG is a set of special frequent subgraph of a graph database. When query processes through this index, it gets back a smaller candidate answer set than other methods which means much less subgraph isomorphism calculation. Both theoretical analysis and experimental evaluation result shows that the proposed method not only efficiently prunes the search branches in the feature index, but also effectively reduces the subgraph isomorphism test between the query graph and the indexed features.