The extension of SPARQL in version 1.1 with property paths o ers a type of regular path query for RDF graph databases. Such queries are di cult to optimize and evaluate e ciently, however. We have embarked on a project, Waveguide, to build a cost-based optimizer for SPARQL queries with property paths. Waveguide builds a query plan| which we call a waveplan (WP)|which guides the query evaluation. There are numerous choices in the construction of a plan, and a number of optimization methods, so the space of plans for a query can be quite large. Execution costs of plans for the same query can vary by orders of magnitude. A WP's costs can be estimated, which opens the way to costbased optimization. We demonstrate that the plan space of Waveguide properly subsumes existing techniques and that the new plans it adds are relevant.
Graph data is becoming rapidly prevalent with the rise of the Semantic Web,
social networks, and data-driven exploration in life sciences. There is a need
for natural, expressive ways to query over these graphs. Standards are coming
into place for this. The Resource Description Framework (RDF) [
In its latest version, 1.1, SPARQL's expressiveness is extended with property
paths [
While SPARQL provides the expressiveness we desire, such queries are more challenging to optimize well. Query Q1 could be evaluated just by extracting the triples with \r = :friendOf" and \o = Charles". For even a slightly more complicated query, however, it may not be straightforward to nd a plan to evaluate it e ciently. Q2 is more challenging in requiring transitive closure over \:friendOf" with respect to the graph.
Property path evaluation is a tale of two methods: two quite di erent
approaches appear in the literature. For RPQs, the seminal work [
SPARQL with property paths is much more recent. Systems for SPARQL
query evaluation have followed the second approach, based primarily on the
seminal work of [
Which approach is better? We shall show that the e ective \plan spaces" that result from FA and -RA are incomparable. Sometimes, for a given query and graph, an FA plan will be the better choice. Other times, an -RA plan will be. Our goal is to formalize the notion of plan space for both, to be able to choose the best plan. We shall show that a richer plan space can be had that properly subsumes FA and -RA, and o ers more plans existing in neither (\mixed" plans), which sometimes are the best plans.
We have designed a system called Waveguide [
In [
(a) Summarize the state of the art for evaluation of RPQs and SPARQL property paths. (b) Establish why none su ces. (c) Devise Waveguide's plan space, and demonstrate that it subsumes the state of the art, and extends beyond it. (d) Model the cost factors that determine the e ciency of plans, and present the powerful optimizations o ered by Waveguide plans. 2. performance study.
(a) Provide a microbenchmark over a pertinent RPQ template with realistic queries over real RDF stores / graphs. (b) Substantiate the optimizations of our approach.
(c) Justify the necessity of the richer plan space. 2
Work on property-path evaluation has been remiss in not drawing the connection to RPQs. How do the FA and -RA approaches compare? Does one subsume the other? Or are they incomparable? If so, a combined approach might be superior. A generalized approach might o er new plans that neither FA nor -RA can produce with superior performance.
Both the FA and -RA approaches e ectively provide evaluation plans for property-path queries. However, the plan spaces that are implicit in these approaches have not been considered. In FA, choosing a di erent (but still correct) automaton for the plan might o er a signi cantly more e cient plan. In systems taking the -RA approach, planning is done over the -RA expression tree that results from the property path's translation, but no planning speci c to the semantics of property paths takes place.
In [
Waveguide's evaluation strategy is based on an iterative search algorithm, and variations thereof. In Waveguide, we perform path search e ciently while simultaneously recognizing the path expressions. Waveguide's input is a graph database G and a waveplan PQ which guides a number of search wavefronts that explore the given graph. We introduce the term wavefront to refer to a part of the plan that evaluates breadth- rst during the evaluation. This graph exploration, driven by an iterative search procedure, is inspired by the semi-nave bottom-up strategy used in the evaluation of linear recursive expressions based on xpoint, as is done for the operator for -RA.
The key idea is, given a seed |a set of nodes in the graph from which this wavefront begins its search|as a start, to expand repeatedly the search wavefronts until no new answers are produced; i.e., we reach a xpoint. Each search wavefront is guided by an automaton in the plan, a nite state machine based on an NFA. This is akin to the FA approach. Di erent, though, from NFAs which are used as recognizers of regular expressions on strings, wavefront automata have features directed to the evaluation of regular expressions over graphs.
In [
We prototype a system [
We test our implementation of Waveguide by running a collection of
realistic path queries over real-world datasets YAGO2s [