Challenges of Source Selection in the WoD

Grubenmann, Tobias; Bernstein, Abraham; Moor, Dmitry; Seuken, Sven

Abstract

Federated querying, the idea to execute queries over several distributed knowledge bases, lies at the core of the semantic web vision. To accommodate this vision, SPARQL provides the SERVICE keyword that allows one to allocate sub-queries to servers. In many cases, however, data may be available from multiple sources resulting in a combinatorially growing number of alternative allocations of subqueries to sources. Running a federated query on all possible sources might not be very lucrative from a user’s point of view if extensive execution times or fees are involved in accessing the sources’ data. To address this shortcoming, federated join-cardinality approximation techniques have been proposed to narrow down the number of possible allocations to a few most promising (or results-yielding) ones.

In this paper, we analyze the usefulness of cardinality approximation for source selection. We compare both the runtime and accuracy of Bloom Filters empirically and elaborate on their suitability and limitations for different kind of queries. As we show, the performance of cardinality approximations of federated SPARQL queries degenerates when applied to queries with multiple joins of low selectivity. We generalize our results analytically to any estimation technique exhibiting false positives. These findings argue for a renewed effort to find novel join-cardinality approximation techniques or a change of paradigm in query execution to settings, where such estimations play a less important role.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: ISWC 2017
• Start Date: Oct 21, 2017
• End Date: Oct 25, 2017
• Online Publication Date: Oct 4, 2017
• Publication Date: 2017
• Deposit Date: Jun 3, 2023
• Publisher: Springer
• Pages: 313-328
• Series Title: Lecture Notes in Computer Science
• Series Number: 10587
• Book Title: The Semantic Web – ISWC 2017 16th International Semantic Web Conference, Vienna, Austria, October 21–25, 2017, Proceedings, Part I
• ISBN: 9783319682877
• DOI: https://doi.org/10.1007/978-3-319-68288-4_19
• Keywords: Approximate query processing, Bloom Filter, Federated SPARQL, Source selection, Web of Data