TY - GEN

T1 - Heuristics-based Query Reordering for Federated Queries in SPARQL 1.1 and SPARQL-LD

AU - Yannakis, Thanos

AU - Fafalios, Pavlos

AU - Tzitzikas, Yannis

N1 - Funding Information: The work was partially funded by the European Commission for the ERC Advanced Grant ALEXANDRIA under grant No. 339233.

PY - 2018

Y1 - 2018

N2 - The federated query extension of SPARQL 1.1 allows executing queries distributed over different SPARQL endpoints. SPARQL-LD is a recent extension of SPARQL 1.1 which enables to directly query any HTTP web source containing RDF data, like web pages embedded with RDFa, JSON-LD or Microformats, without requiring the declaration of named graphs. This makes possible to query a large number of data sources (including SPARQL endpoints, online resources, or even Web APIs returning RDF data) through a single one concise query. However, not optimal formulation of SPARQL 1.1 and SPARQL-LD queries can lead to a large number of calls to remote resources which in turn can lead to extremely high query execution times. In this paper, we address this problem and propose a set of query reordering methods which make use of heuristics to reorder a set of service graph patterns based on their restrictiveness, without requiring the gathering and use of statistics from the remote sources. Such a query optimization approach is widely applicable since it can be exploited on top of existing SPARQL 1.1 and SPARQL-LD implementations. Evaluation results show that query reordering can highly decrease the query-execution time, while a method that considers the number and type of unbound variables and joins achieves the optimal query plan in 88% of the cases.

AB - The federated query extension of SPARQL 1.1 allows executing queries distributed over different SPARQL endpoints. SPARQL-LD is a recent extension of SPARQL 1.1 which enables to directly query any HTTP web source containing RDF data, like web pages embedded with RDFa, JSON-LD or Microformats, without requiring the declaration of named graphs. This makes possible to query a large number of data sources (including SPARQL endpoints, online resources, or even Web APIs returning RDF data) through a single one concise query. However, not optimal formulation of SPARQL 1.1 and SPARQL-LD queries can lead to a large number of calls to remote resources which in turn can lead to extremely high query execution times. In this paper, we address this problem and propose a set of query reordering methods which make use of heuristics to reorder a set of service graph patterns based on their restrictiveness, without requiring the gathering and use of statistics from the remote sources. Such a query optimization approach is widely applicable since it can be exploited on top of existing SPARQL 1.1 and SPARQL-LD implementations. Evaluation results show that query reordering can highly decrease the query-execution time, while a method that considers the number and type of unbound variables and joins achieves the optimal query plan in 88% of the cases.

KW - Linked data

KW - Query reordering

KW - SPARQL 1.1

KW - SPARQL-LD

UR - http://www.scopus.com/inward/record.url?scp=85049106183&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85049106183

T3 - CEUR Workshop Proceedings

SP - 74

EP - 88

BT - GeoLD-QuWeDa 2018 ESWC 2018 Workshops: GeoLD 2018 and QuWeDa 2018

T2 - 3rd International Workshop on Geospatial Linked Data and the 2nd Workshop on Querying the Web of Data, GeoLD-QuWeDa 2018

Y2 - 3 June 2018 through 4 June 2018

ER -