Database Reference
In-Depth Information
SELECT subgraph-specification FROM node-variables
WHERE node-condition-set
During query evaluation node variables are bound to nodes of the database graph such that all node-
conditions in the WHERE clause evaluate to TRUE. The query result is constructed from these variable
bindings according to the subgraph-specification of the SELECT clause. Query evaluation considers each
node variable in the FROM clause. For each of these variables, all possible assignments of the variable
to nodes of the graph are determined for which the conditions of the WHERE clause mentioning only
this variable evaluates to TRUE. Node variables are equally assigned to molecules and interactions.
Once all possible bindings are computed for each node variable, the Cartesian product of these sets is
computed. From this set, all instances are removed for which the entire WHERE clause evaluates to
FALSE and all distinct assignments from the remaining elements of the Cartesian product are combined
to form the match graph. In general, SQL query operates on tables and produces a table (a set of rows),
in the same manner as a PQL query operates on a graph and produces a graph (a set of nodes) and not a
set of graphs. In the result of the SQL query the rows from the Cartesian product are preserved, columns
might be removed, added, or changed in their value. In PQL, the concrete combinations of bindings of
different node variables that together fulfill the WHERE clause are not preserved in the match graph of
a PQL query. The match graph simply consists of all bindings present in the filtered Cartesian product
into a flat, duplicate-free list of nodes.
In (He & Singh, 2008) He and Singh have proposed a general graph query and manipulation lan-
guages called GraphQL. In this language, graphs are considered as the basic unit of information and
each query manipulates one or more collections of graphs. It also targets graph databases that supports
arbitrary attributes on nodes, edges, and graphs. The core of GraphQL is its data model and its graph
algebra. In the GraphQL data model, a graph pattern is represented as a graph structure and a predicate
on attributes of the graph. Each node, edge, or graph can have arbitrary attributes. A tuple with a list of
name and value pairs is used to denote these attributes. In GraphQL algebra, graphs are the basic unit
of information. Each operator takes one or more collections of graphs as input and generates a collec-
tion of graphs as output. For example, the selection operator takes a collection of graphs as input and
produces a collection of graphs that match the graph pattern as an output. A graph pattern can match a
specific graph database member many times. Therefore, an exhaustive option is used to specify whether
it should return one or all possible matches. A Cartesian product operator takes two collections of graphs
C
and
D
and produces a collection of graphs as output where each output graph is composed of a graph
from
C
and another from
D
. The join operator is defined as a Cartesian product operator followed by
a selection operator. The composition operator generates new graphs by combining information from
matched graphs based on graph templates that specify the output structure of the graphs.
Consens & Mendelzon (1990) have proposed a graphical query language for graph databases called
GraphLog. Graphlog queries ask for patterns that must be present or absent in the database graph. In
GraphLog, the query graph can define a set of new edges that are added to the graph whenever the search
pattern is found. Awad has followed a similar approach in (Awad, 2007) where he presented a visual
query language for business process definitions called BPMN-Q. BPMN-Q allows expressing structural
queries and specifies proceedings of determining whether a given process model graph is structurally
similar to a query graph. BPMN-Q relies on the notations of BPMN languages as its concrete syntax
and provides a set of new visual constructs that can be seen as abstractions over the existing modeling
constructs. For example a Path construct connecting two nodes in a query represents an abstraction over
