A Novel Graph Containment Query Algorithm on Graph Databases
Xiantong Li, Wei Zhang, Jianzhong Li
Journal of Digital Information Management, Vol. 7, No. 3, 2009.
DOI: 
Link: http://www.dirf.org/jdim/v7n3a3.asp
Abstract:
Nowadays, efficient graph query processing method is coming more and more important along with the structured data accumalating. Given a graphs from the    database that are subgraphs of the query graph. In this  paper, an algorithm is processed,which is founded on a CFG(closed frequent subgraph) based index, to   answer graph contaiment 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 theritical analysis and experimental evaluation result   shows that the proposed method not only efficiently prunes the search branches in the feature index, but also efficiently reduces the subgrapg  isomorphism test   between the query graph and the indexed features.