Database Reference
In-Depth Information
Table 2. Summary graph query languages
Query Language
Target Domain
Query Units
Query Style
BPMN-Q (Awad, 2007)
Business Process Models
Subgraphs
Graphical
GOOD (Gyssens et al., 1994)
General
nodes/edges
Declarative (OQL-Like)
GOQL (Sheng et al., 1999)
General
nodes/edges
Declarative (OQL-Like)
GraphLog (Consens & Mendelzon, 1990)
General
nodes/edges
Graphical
GraphQL (He & Singh, 2008)
General
Subgraphs
Declarative (XQuery-Like)
PQL (Leser, 2005)
Biological networks
Subgraphs
Declarative (SQL-Like)
SPARQL (Prud'hommeaux & Seaborne, 2008)
Semantic Web
Subgraphs
Declarative (SQL-Like)
whatever nodes could be in between in the matching process model while Negative Path used to express
that two nodes must have no connection between them.
There are some other proposal for graph query languages that have been proposed in the literature
such as: GOQL (Sheng et al., 1999), GOOD (Gyssens et al., 1994) and SPARQL (Prud'hommeaux &
Seaborne, 2008). For example, GOQL and GOOD are designed based on an extension of OQL (Object-
Oriented Query Language) and rely on an object-oriented graph data model. SPARQL query language
is a W3C recommendation for querying RDF graph data. It describes a directed labeled graph by a set
of triples, each of which describes a (attribute, value) pair or an interconnection between two nodes.
The SPARQL query language works primarily through a primitive triple pattern matching techniques
with simple constraints on query nodes and edges.
Table 2 provides a comparison between the graph query languages in terms of their target domain,
query unit and query style.
DISCUSSION AND CONCLUSION
In this chapter, we give an overview of the problem of graph indexing and querying techniques. The
problem is motivated by the continued emergence and increase of massive and complex structural data.
Due to the very expensive cost of pair-wise comparison of graph data structures, recently proposed graph
query processing techniques rely on a strategy which consists of two steps: filtering and verification .
For a given graph database D and a graph query q , the main objective of the filtering and verification
methodology is to avoid comparing the query graph q with each graph database member g i that belongs
to D to check whether gi satisfies the conditions of q or not. Therefore, most of the proposed graph index-
ing strategies shift the high online graph query processing cost to the off-line index construction phase.
Index construction is thus, always computationally expensive because it requires the use of high quality
indexing features with great pruning power from the graph database. However, the number of indexing
features should be as small as possible to keep the whole index structure compact so that it is possible
to be held in the main memory for efficient access and retrieval. Hence, a high quality graph indexing
mechanism should be time-efficient in index construction and indexing features should be compact and
powerful for pruning purposes. Moreover, candidate verification can be still very expensive as the size
of the candidate answer set is at least equal to that of the exact answer set in the optimal case but it is
Search WWH ::




Custom Search