1 Introduction
Recently, graph data models have attracted increasing research interest, because many data in various applications can be represented by graphs, such as chemical compounds [1], social networks [2], road networks [3], and Semantic Web [4]. The growing popularity of graph data requires efficient graph data management techniques. Thus, many queries have been investigated, such as shortest path query [5], [6], reachability query [7], [8], [9], and (sub)graph query [10], [11], [12]. Among these, (sub)graph query (i.e., given a query graph \$q\$, finding all graphs \$g\$ in a graph database \$D\$ , such that \$q\$ is (sub)graph isomorphic to \$g\$) has been well studied.