SPARQL property path optimizer

μSPARQL

Introduction

μ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.

μSPARQl manual

Project schematic

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.

Running instruction

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"

Compiling instruction

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.

muSPARQL benchmark


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.