A shortest path approach to SPARQL chain query optimisation
Tanvi Chawla, Girdhari Singh, Emmanuel S. Pilli · 2017
The Semantic Web paradigm has opened several doors for representing information on the web such that this information can be easily understood by both the humans and the machines. Resource Description Framework (RDF) is a popular format for representing information on the Semantic Web and queries on this RDF data are known as SPARQL queries. There are some popular and successful frameworks available for modeling and processing Semantic Web data such as Apache Jena, Sesame etc. The objective is to optimise SPARQL queries in order to reduce their execution time. Many execution plans may be possible for processing a single SPARQL query so, the challenge lies in choosing an optimal one that will be able to produce the results in minimum time and with minimal overhead. In this paper, we have modified the conventional All Pair Shortest Path (APSP) algorithms which take as input a pre-computed cost matrix of a graph-based SPARQL query. This matrix is obtained after computing join costs between triples patterns in a SPARQL query graph using heuristic based techniques.