Querying Graph Databases - Advanced Database Query Systems - page 308

Figure 2. An example graph database and graph queries
1. Identifying the set of features of the subgraph query.
2. Using the inverted index to retrieve all graphs that contain the same features of q .
The rationale behind this type of query processing techniques is that if some features of graph q do
not exist in a data graph G , then G cannot contain q as its subgraph (inclusion logic). Formally, Clearly,
the effectiveness of these filtering methods depends on the quality of mining techniques to effectively
identify the set of features . Therefore, important decisions need to be made about: the indexing feature,
the number and the size of indexing features. These decisions crucially affect the cost of the mining
process and the pruning power of the indexing mechanism. A main limitation of these approaches is
that the quality of the selected features may degrade over time after lots of insertions and deletions. In
this case, the set of features in the whole updated graph database need to be re-identified and the index
needs to be re-build from scratch. It should be noted that, achieving these tasks is quite time consuming.
Non Mining-Based Graph Indexing Techniques
GraphGrep
The GraphGrep (Giugno & Shasha, 2002) index structure uses enumerated paths as index features to filter
unmatched graphs. For each graph database member, it enumerates all paths up to a certain maximum