Database Reference
In-Depth Information
Figure 5. Sample GraphREL encoding of graph databases
GraphREL
Sakr (2009) has presented a purely relational framework for processing graph queries named GraphREL.
In this approach, the graph data set is encoded using an intuitive Vertex-Edge relational mapping scheme
((Figure 5) and the graph query is translated into a sequence of SQL evaluation steps over the defined
storage scheme. An obvious problem in the relational-based evaluation approach of graph queries is the
huge cost which may result from the large number of join operations which are required to be performed
between the encoding relations. Several relational query optimization techniques have been exploited
to speed up the search efficiency in the context of graph queries. The main optimization technique of
GraphREL is based on the observation that the size of the intermediate results dramatically affects the
overall evaluation performance of SQL scripts (Teubner et al., 2008). Therefore, GraphREL keeps sta-
tistical information about the less frequently existing nodes and edges in the graph database in the form
of simple Markov Tables.
For a graph query
q
, the maintained statistical information is used to identify the highest pruning
point on its structure (nodes or edges with very low frequency) to firstly filter out, as many as possible,
of the false positives graphs that are guaranteed to not exist in the final results first before passing the
candidate result set to an optional verification process. This statistical information is also used to influ-
ence the decision of relational query optimizers by selectivity annotations of the translated query
predicates to make the right decision regarding the selection of most efficient join order and the cheap-
est execution plan (Bruno et al., 2009).
Based on the fact that the number of distinct vertices and edges labels are usually far less than the
number of vertices and edges in graph databases, GraphREL utilizes the powerful partitioned B-trees
indexing mechanism of the relational databases to reduce the access costs of the secondary storage to a
minimum. GraphREL applies an optional verification process only if more than one vertex of the set of
query vertices has the same label. For large graph queries, GraphREL applies a decomposition mecha-
nism to divide the large and complex SQL translation query into a sequence of intermediate queries
(using temporary tables) before evaluating the final results. This decomposition mechanism reuses the
