Database Reference
In-Depth Information
Figure 1. Graph database querying
SUBGRAPH QUERY PROCESSING
There are many graph indexing techniques that have been recently proposed to deal with the problem of
subgraph query processing (Sakr, 2009; Yan et al., 2004; Zhang et al., 2007; Zhao et al., 2007). Subgraph
query processing techniques can be divided into the following two approaches:
•
Non Mining-Based Graph Indexing Techniques:
The techniques of this approach focus on in-
dexing the whole constructs of the graph database instead of indexing only some selected features
(Giugno & Shasha, 2002; He & Singh, 2006; Jiang et al., 2007; Sakr, 2009; Williams et al., 2007).
The main criticisms of these approaches are that: 1) they can be less effective in their pruning
power; 2) they may need to conduct expensive structure comparisons in the filtering process and
thus degrades the filtering efficiency. Therefore, these techniques need to employ efficient filter-
ing and pruning mechanisms to overcome these limitations. However, The techniques of this ap-
proach have a clear advantage in that they can handle the graph updates with less cost as they do
not rely on the effectiveness of the selected features and they do not need to rebuild their whole
indexes.
•
Mining-Based Graph Indexing Techniques:
The techniques of this approach apply graph-min-
ing methods (Kuramochi & Karypis, 2001, 2004; Wang et al., 2004; Washio & Motoda, 2003; Yan
& Han, 2002, 2003) to extract some features (sub-structures) from the graph database members
(Cheng et al., 2007; Yan et al., 2004; Zhang et al., 2007; Zhao et al., 2007). An inverted index is
created for each feature. Answering a subgraph query
q
is achieved through two steps:
