On the selection of SPARQL endpoints to efficiently execute federated SPARQL queries

Maria Esther Vidal*, Simón Castillo, Maribel Acosta, Gabriela Montoya, Guillermo Palma

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

9 Citations (Scopus)

Abstract

We consider the problem of source selection and query decomposition in federations of SPARQL endpoints, where query decompositions of a SPARQL query should reduce execution time and maximize answer completeness. This problem is in general intractable, and performance and answer completeness of SPARQL queries can be considerably affected when the number of SPARQL endpoints in a federation increases. We devise a formalization of this problem as the Vertex Coloring Problem and propose an approximate algorithm named Fed- DSATUR. We rely on existing results from graph theory to characterize the family of SPARQL queries for which Fed-DSATUR can produce optimal decompositions in polynomial time on the size of the query, i.e., on the number of SPARQL triple patterns in the query. Fed-DSATUR scales up much better to SPARQL queries with a large number of triple patterns, and may exhibit significant improvements in performance while answer completeness remains close to 100%. More importantly, we put our results in perspective, and provide evidence of SPARQL queries that are hard to decompose and constitute new challenges for data management.

Original languageEnglish
Title of host publicationTransactions on Large-Scale Data- and Knowledge-Centered Systems XXV
EditorsAbdelkader Hameurlain, Josef Küng, Roland Wagner
Number of pages41
PublisherSpringer
Publication date1 Jan 2016
Pages109-149
ISBN (Print)9783662495339
ISBN (Electronic)978-3-662-49534-6
DOIs
Publication statusPublished - 1 Jan 2016
EventInternational Conference on Transactions on Large-Scale Data- and Knowledge-Centered Systems, TLDKS 2016 - Porto, Portugal
Duration: 1 Jan 2016 → …

Conference

ConferenceInternational Conference on Transactions on Large-Scale Data- and Knowledge-Centered Systems, TLDKS 2016
Country/TerritoryPortugal
CityPorto
Period01/01/2016 → …
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9620
ISSN0302-9743

Fingerprint

Dive into the research topics of 'On the selection of SPARQL endpoints to efficiently execute federated SPARQL queries'. Together they form a unique fingerprint.

Cite this