μSPARQL is a tool based on the works described in Louis
Jachiet PhD thesis. It optimizes SPARQL property path by
translating them into an internal algebra (called μ-algebra)
and optimizes the resulting terms.
This tool translates SPARQL queries into an internal algebra called
"μ-ALGEBRA". Once in this from we produce multiple equivalent queries
using rewrite rules. The tool chooses one of the form using heuristics
and then run it.
The invocation is:
./compil query [parse] [debug] [stats] [showmu] [execute] [verbose] [timing]
The file query
is read and processed according to
the arguments passed to compil
- parse stops the compilation after the parsing phase
- debug activate a verbose mode
- stats prints the number of AST considered
- showmu pretty prints the AST selected
- execute runs the query against the vertically partionned data in "pred"
The compilation is done in several steps. Main.ml orchestrates the
several stages of compilation :
- the compilation options are parsed by the main
- the file is read by the lexer (lexer.mll)
- the lexed stream goes to the parser (parser.mly)
- the parsed sparql is sent to sparql_to_ast (sparqlToAst.ml)
- regexp are compiled to conditionnals
- the ast is cleaned (string variables to int, renaming of variables is done)
- we generate multiple plans for an ast.
We experimented our prototype against other SPARQL
tools. Here are the results.
In the figure below, we recapture the theoretical results
that, even on simple queries, there are graphs on which
our tool has a linear complexity while other approaches
have a quadratical complexity.