Heuristic Optimization of SPARQL queries over Column-Store DBMS

Language: English

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


You may also like...