WAVEGUIDE: Evaluating SPARQL Property Path Queries

Abstract

The extension of SPARQL 1.1 of property paths now o↵ers a type of regular path query for RDF graph databases. While eminently useful, these queries are dicult to optimize to evaluate eciently. We have embarked on a project we call Waveguide to build a cost-based optimizer for SPARQL queries with property paths. Waveguide maps the property path to a waveguide plan (WGP )c omposed ofwavefront automata (WFAs) modeled by (non-deterministic) finite automata. The waveguide plan guides the graph search during evaluation. Our Waveguide prototype illustrates the types of optimizations this approach a↵ords and the performance gains that can be obtained.