Heuristic Optimization of SPARQL queries over Column-Store DBMS
Author: Petros Anagnostopoulos – Tsialiamanis, University of Crete, Greece
Affiliation: Data StoresNoSQL
Abstract: In this thesis we describe a new Heuristic SPARQL Planner (HSP) that is capable of exploiting the syntactic and the structural variations of the triple patterns in a SPARQL query in order to choose an execution plan without the need of any cost model. For this, we define the variable graph and we show a reduction of the SPARQL query optimization problem to the maximum weight independent set problem. We implemented our planner on top of the MonetDB open source column-store and evaluated its effectiveness against the state-of-the-art RDF-3X engine as well as comparing the plan quality with a relational (SQL) equivalent of the benchmarks.
Type of work: Master
No of Pages: 92
Year of completion: 2011
Name of supervisor: Vassilis Christophides