Querying Graph Databases - Advanced Database Query Systems - page 316

Table 1. Summary of the graph indexing and querying techniques

Indexing Technique Supported Query Types Indexing Unit Indexing Mechanism

CIndex (Chen et al., 2007) Supergraph queries Subgraph structure Rarely occurring features

Closure-Tree (He & Singh, 2006) Subgraph and similarity Closure Tree Enumeration of graph closures

FG-Index (Cheng et al., 2007 Subgraph queries Subgraph structure Frequent features

GDIndex (Williams et al., 2007) Subgraph queries Decomposed subgraph Full enumeration

GIndex (Yan et al., 2004) Similarity queries Subgraph structure Frequent features

GPTree (Zhang et al., 2009) Supergraph queries Subgraph structure Full enumeration

Grafil (Yan et al., 2005) Similarity queries Any Full enumeration

GraphGrep (Guigno & Shasha, 2002) Subgraph queries Path structure Full enumeration

GraphREL (Sakr, 2009) Subgraph queries Nodes and Edges Full enumeration

GString (Jiang et al., 2007) Subgraph queries Subgraph structure Full enumeration

SAGA (Tian et al., 2007) Similarity queries Subgraph structure Full enumeration

TreeDelta (Zhao et al., 2007) Subgraph queries Tree structure Frequent features

TreePi (Zhang et al., 2007) Subgraph queries Tree structure Frequent features

graph if and only if two query fragments share zero or more nodes, and the corresponding database
fragments in the hit-compatible graph also share the same corresponding nodes. An edge between
two nodes tells us that the corresponding two hits can be merged to form a larger match which is
then a candidate match.
3. Each candidate is examined to produce the query results. For each candidate, the percentage of the
gap nodes is checked. If it exceeds a user-defined threshold P g , then the candidate match is ignored
otherwise, the DistanceIndex is probed to calculate the real subgraph matching distance. If two
matches have the same matching distance and one is a submatch of the other, only the supermatch
is considered.

Table 1 provides a comparison between the different graph indexing techniques in terms of their
supported query types, indexing unit and indexing strategy.

GRAPH QUERY LANGUAGES

With the prevalence of graph data in a variety of application domains, there is an increasing need for
a suitable language to query and manipulate graph data structure (Angles & Guti•errez, 2008). In this
section, we give an overview of representative proposals for graph query languages in the literature.
In (Leser, 2005) Leser has proposed a special-purpose graph query language for biological networks
called PQL ( P athway Q uery L language PQL is a declarative language whose syntax is similar to SQL.
The language targets retrieving specific parts of large, complex networks. It is based on a simple graph
data model with extensions reflecting properties of biological objects. PQL queries match arbitrary
subgraphs in the database based on node properties and paths between nodes. The general syntax of
PQL is as follows: