=Paper=
{{Paper
|id=Vol-1644/paper39
|storemode=property
|title=SwarmGuide: Towards Multiple-Query Optimization in Graph Databases
|pdfUrl=https://ceur-ws.org/Vol-1644/paper39.pdf
|volume=Vol-1644
|authors=Zahid Abul-Basher,Nikolay Yakovets,Parke Godfrey,Mark Chignell
|dblpUrl=https://dblp.org/rec/conf/amw/Abul-BasherYGC16
}}
==SwarmGuide: Towards Multiple-Query Optimization in Graph Databases==
https://ceur-ws.org/Vol-1644/paper39.pdf
SWARMGUIDE: Towards Multiple-Query
Optimization in Graph Databases
Zahid Abul-Basher§ Nikolay Yakovets†
Parke Godfrey† Mark Chignell§
§
University of Toronto, Toronto, ON, Canada
{zahid,chignell}@mie.utoronto.ca
†
York University, Toronto, ON, Canada
{hush,godfrey}@cse.yorku.ca
1 Introduction
Analytic tasks over graph databases often require sequences of related queries to
be evaluated. While there are promising query optimization methods for graph
queries [6], these do not optimize globally for sets of queries. For relational, mul-
tiple query optimization (MQO) has been studied [5]. We propose Swarmguide,
a framework for MQO for graph databases.
2 Graph Databases & Queries
Preliminaries. A graph database G is a finite, directed, edge-labeled, multi-
graph defined by G = hN, Σ, Ei, where N is a finite set of nodes (vertices), Σ is
a set of labels, E is a set of directed, labeled edges, and E ⊆ N × Σ × N . A path
p in G is defined as a sequence of n0 a0 n1 · · · nk−1 ak−1 nk where ni ∈ N , ai ∈ Σ,
and hni , ai , ni+1 i ∈ E for 0 ≤ i ≤ k. We call the sequence of edge labels Σ ∗ of a
particular path p the word, ω(p) that p induces.
A regular path rp is a path in the graph where ω(rp) is a word in a given
regular language L(reg) (e.g., ω(rp) ∈ L(reg)). A regular path query (RPQ) [2]
is a triple hx, reg, yi in which x and y are free variables over the domain of
nodes, and reg is a regular expression. An answer of an RPQ is a node-pair hs, ti
(s, t ∈ N ) such that there is a path p in G between s and t and ω(p) ∈ L(reg).
The answer set of an RPQ is the set of all its answers. The RDF data model
and SPARQL query language instantiate these concepts. With the introduction
of property paths in SPARQL 1.1, the query language encompasses RPQs. For
our examples in this paper, we adopt SPARQL syntax.
Evaluation of RPQs. Evaluating an RPQ is a two-step procedure. Path recog-
nition determines whether the word of path p, ω(p), is recognized by the regular
expression reg (i.e., ω(p) ∈ L(reg)); path search finds pairs of nodes, s, t ∈ N
such that there exists such a path p from node s to node t. There has been
recent interest in how to evaluate RPQs efficiently in SPARQL over RDF stores.
Yakovets et al. [6] demonstrate in their Waveguide framework that there is a
rich plan space for such queries, and that different plans for a given query can
Fig. 1: Example movie graph
differ by orders of magnitude in evaluation cost. A simple cost model for such
a plan is how many edges traversals (edge-walks) in the graph are made during
the plan’s evaluation.
Consider Q1 = hx, director of /actor/born in, yi over the movie graph in
Figure 1. This query can be evaluated in different ways, with different edge-
walk costs. We can evaluate it in forward-direction by retrieving all node-pairs
connected by edge label director of then appending with those linked by actor
and then by born in. We can also evaluate it in the backward direction by
retrieving all node-pairs connected by edge label born in then prepending with
those connected by actor and then by director of . A third way is from the middle
by retrieving all node-pairs connected by edge label actor then appending with
those connected by born in and then prepending by director of . Note that, the
edge-walk cost for the first is 10, in the second is 9, and in the third is 7.
In Waveguide, path search is performed efficiently while simultaneously
recognizing the path expressions. Waveguide’s input is a graph database G and
a waveplan (WP) PQ which guides a number of search wavefronts that explore
the given graph. The term wavefront is introduced to refer to a part of the
plan that evaluates breadth-first during the evaluation. This graph exploration,
driven by an iterative search procedure, is inspired by the semi-naı̈ve bottom-up
strategy used in the evaluation of linear recursive expressions based on a fixpoint.
The key idea is to expand repeatedly the search wavefronts until no new
answers are produced; i.e., we reach a fixpoint. Each search wavefront is guided
by an automaton in the plan, a finite state machine based on an NFA.
Consider query plans for Q1 = hx, director of /actor/born in, yi as in Figure
2. Plan A employs a WP corresponding to a single FA that directly encodes
a recognizer for the query’s regular expression. This plan captures the notion
of “pipelining”. Whereas Plan B employs a WP that consists of two subplan
automata, the first subplan (SP) is used as a view for transition over states in
the second plan. This captures the notion of “materialization”. Note that in the
second subplan automaton, we used a prepend transition (·director of ) over the
previous state.
Fig. 2: A batch of two queries
Fig. 3: Swarmguide Framework
The Waveguide prototype implements guided graph search as procedu-
ral SQL on top of PostgreSQL. However, any type of back-end physical graph
database model (e.g., triple store or adjacency lists) can be used.
3 SWARMGUIDE: The Framework
Queries running in a batch may have common subexpressions among them. In-
stead of running each query individually, one could benefit from sharing the re-
sults of common subexpressions [5]. Consider two queries, Q1 = hx, director of /
actor/born in, yi and Q2 = hx, actor/born in/located in, yi as in Figure 2. Clearly,
the optimal automaton plans (Plan A) do not share any common subplan for
Q1 and Q2 . However, if we chose suboptimal plans (Plan B) then we could have
a common sub-plan automaton (actor/born in). This common subplan could be
shared among Q1 and Q2 without re-evaluating it.
Evaluation of MRPQs. The evaluation of multiple regular path queries (MR-
PQs) is two-step: identifying common subexpressions among queries; and search-
ing for a global optimal plan such that its cost is less than the summed cost of
the local optimal plans in the batch. We present our framework Swarmguide,
a generic framework for optimizing multiple regular path queries (MRPQs) in
graph databases. Figure 3 shows Swarmguide architecture.
Clustering Queries. Clustering queries is a preprocessing step to finding the
commonalities among the RPQs in the batch. These can be detected by finding
the isomorphic subgraphs of their corresponding finite automata (FAs). This
process is known to be NP-hard, in general [1]. Therefore, we use heuristics to
group only queries that can have common sub-automata, and then do the hard
task of identifying the common sub-automata within each group.
Finding Common Sub-automata. Finding common sub-automaton resem-
bles finding the maximum common subgraph among graphs. The problem be-
comes more difficult here as we need to find the largest common subgraphs
(sub-automata) for multiple graphs (FAs). Most existing solutions only consider
non-labeled edges and nodes in undirected graphs. We adopt the solution from
the maximal common-edge subgraph (MCES) problem [3] to detect common sub-
automata. This has three steps: transforming labeled-graphs into the equivalent
line-graphs; producing a product graph from the line-graphs; and detecting the
maximal cliques in the product graph, which corresponds to MCESs (therefore,
common sub-automata).
Query Rewriting. A regular expression reg can be recognized equivalently by
many FAs. For instance, the two FAs for two regular expressions reg1 = (ab)∗ ac
and reg2 = a(ba)∗ c are equivalent; however, the plan space may differ, depending
on the chosen FA. In this step, we rewrite FAs according to their shared common
sub-automata.
Global Optimization. A local optimal plan for a given query may not be the
best plan when optimizing a batch of queries. The goal of the global optimization
is then to search local plans of queries to find a global plan by choosing one local
plan per query in a cluster of RP Qs. The cost of this global plan should be less
than, or equal to, the total cost of local optimal plans of queries in the batch.
In [4], the authors propose cost-based heuristic algorithms for this; we likewise
adapt their algorithms for here.
Other Considerations. A single FA plan is often decomposed into several
subplans as views. When planning globally, one has to check if views from other
queries’ plans can be shared. Intermediate node-pairs—along with their states
in FA—are cached to avoid unbounded computation over cyclic graphs. When
evaluating a global plan in MRPQs, these local caches need to be maintained
globally so subplans shared among queries can be leveraged. The global cache
also can be used to obtain useful statistics about the graph to obtain a more ac-
curate global optimal plan and choosing the initial nodes for search exploration.
4 Conclusions
Graph database analytic applications are rapidly on the rise. These raise new
and arduous challenges. We can apply many of the lessons learned from the
relational domain—e.g., pipelining, materialized views, cost-based optimization,
query answering by views, and multiple query optimization—to these challenges
to great effect. However, these techniques have to be carefully re-imagined to be
effective for graph databases, their queries, and applications.
References
1. W. Le, A. Kementsietsidis, S. Duan, and F. Li. Scalable multi-query optimization for
SPARQL. In Data Engineering (ICDE), 2012 IEEE 28th International Conference
on, pages 666–677. IEEE, 2012.
2. A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph databases.
SIAM Journal on Computing, 24(6):1235–1258, 1995.
3. J. W. Raymond and P. Willett. Maximum common subgraph isomorphism algo-
rithms for the matching of chemical structures. Journal of computer-aided molecular
design, 16(7):521–533, 2002.
4. P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. Efficient and extensible algorithms
for multi query optimization. In ACM SIGMOD Record, volume 29, pages 249–260.
ACM, 2000.
5. T. K. Sellis. Multiple-query optimization. ACM Transactions on Database Systems
(TODS), 13(1):23–52, 1988.
6. N. Yakovets, P. Godfrey, and J. Gryz. Query planning for evaluating SPARQL
property paths. In Proceedings of the ACM SIGMOD International Conference on
Management of Data, pages 1–15, San Francisco, CA, USA, June 2016.