To answer queries over a federation of multiple data sources, a preliminary task is source selection; i.e., identify the federation members that can answer each part of the query and decompose the query into subqueries assigned to each federation member. Existing source selection approaches for federations of RDF data sources have been developed based on the assumption that the federation member are SPARQL endpoints. This paper presents an analytical study that investigates whether these approaches are still efective in the context of federations that are heterogeneous in terms of the types of data access interface. In particular, we identify what information about the data of the federation members is required by the approaches and analyze the possibilities and the efort of obtaining this information via the different types of data access interfaces. We find that almost all existing source selection approaches can be adopted for heterogeneous federations but obtaining the required information may not be practical.
Processing queries that cannot be answered by a single data source requires combining data from multiple data sources in a federation. For such federated queries, it is significant to identify relevant federation members for executing particular parts of a given query, since requesting data from irrelevant federation members is an unnecessary overhead or may result in high costs on subsequent query processing. The task of source selection is to identify relevant federation members that may answer parts of the query and to determine the subqueries to be executed at each federation member. Existing source selection approaches have, by and large, focused only on the source selection problem in federations that are homogeneous in terms of the interfaces provided by the federation members; that is, the federation members have typically be assumed to be SPARQL endpoints. For federations that are heterogeneous in terms of interface types (i.e., each federation member may support a diferent type of interface to access its RDF dataset), the source selection problem has yet to be studied.
As a first step in this direction, this paper focuses on the existing source selection approaches for homogeneous federations and investigates whether these approaches are still applicable in the context of heterogeneous federations. The main question that we aim to answer is whether the information that the approaches assume to have about the federation members can still be obtained even if the federation members provide interfaces diferent from the SPARQL endpoint interface. Additionally, we aim to achieve a general understanding of the efort of obtaining this information when relying on the diferent types of interfaces.
As a preliminary for the analysis, we first provide an overview of the types of interfaces that we consider in this study; cf. Section 2. Thereafter, we present our analysis in Section 3 and summarize our findings in Section 4.
This section provides an overview of the diferent types of interfaces for accessing RDF datasets that have been proposed in the literature. For each interface, we focus on the types of requests that clients can send to the server and the possible metadata that the server needs to include in its responses (if any).
SPARQL endpoints [
SaGe [
?book rdf:type dbo:Book . }
SELECT * WHERE {
?book rdf:type dbo:Book .
} LIMIT 1 (a) (b) we examine what information about the datasets of federation members is required for each approach, and then analyze whether and how it is possible to collect that information based on the diferent types of data access interfaces. We first focus on source selection approaches that do not require any prior information about the datasets of the federation members (Sections 3.1– 3.3). Thereafter, we examine source selection approaches that use a data summary or index for federation members together with runtime requests (Sections 3.4–3.6). In addition, we also investigate source selection approaches that rely solely on a pre-computed data catalog or index for federation members (Sections 3.7 and 3.8). Finally, we consider approaches that require federation members to compute and share statistics (Sections 3.9 and 3.10) and discuss alternative options if the required information is not provided by federation members.
FedX [13] uses a source selection approach that does not require any prior information about the data of the federation members before performing any query. Instead, FedX obtains the information it needs for its source selection approach from each federation member at query runtime. The particular information that FedX requires for each federation member is: Info1: For each triple pattern of the given query, determine whether the federation member contains at least one triple that matches the triple pattern.
To obtain this information for SPARQL endpoints (for which FedX was designed), FedX iterates over the triple patterns of the given query and, for each triple pattern, issues a SPARQL ASK query with that triple pattern. Every federation member that returns TRUE in response to such a query is identified as a federation member containing triples that match the triple pattern.
For federation members using the SaGe interface, checking whether such federation
members contain matching triples for a triple pattern can be done by requesting partial results using
SPARQL SELECT queries with a LIMIT clause [
For federation members with a TPF interface, a brTPF interface, or an SPF interface, using ASK queries or LIMIT clauses is not possible. The required information (Info1) can instead be obtained by requesting the first page of matching triples for each triple pattern of the query. The count metadata in the retrieved pages indicates whether the federation member has matching triples for the corresponding triple pattern.
Finally, considering federation members that use a smart-KG interface, recall that smart-KG clients are provided with a catalog that contains metadata about the structure of the compressed dataset partitions available at the smart-KG server. This catalog can be leveraged to obtain the source selection information (Info1) required by the FedX approach. That is, for every triple pattern in which the predicate is bound, and subject and object are not, the corresponding predicate set of this catalog can be checked to determine whether the smart-KG server contains triples that match the triple pattern. This check does not even require contacting the smart-KG server. For any other triple pattern, a TPF first-page request can be used as suggested above for the TPF interface (because the smart-KG interface is an extension of the TPF interface).
Lusail [14] applies another source selection approach that does not rely on prior information of the federation members and their datasets. The particular information that Lusail requires for each federation member is the same as required by FedX:
Additionally, Lusail aims to determine whether two or more triple patterns can be grouped as a subquery. To this end, Lusail requires the following information for each federation member. Info2: For each pair of triple patterns in the query that share a variable, information whether the set diference is empty between (i) the set of all RDF terms at the position of the shared variable within triples that match the first triple pattern and (ii) the set of all RDF terms at the position of the shared variable within triples that match the second triple pattern.
Since the options to obtain Info1 via the diferent types of interfaces have been discussed already in Section 3.1, the following discussion focuses on Info2.
For federation members that provide a SPARQL endpoint, the set diference check can be performed by issuing a SPARQL SELECT query with FILTER NOT EXISTS and LIMIT 1 [14] (e.g., Figure 2), since it is only essential to know if the result is an empty set. Another option would be to use ASK instead of SELECT, in which case LIMIT 1 can be omitted.
For federation members with a SaGe interface, the set diferences cannot be checked directly based on preemptable SPARQL queries because SaGe servers can only process filter conditions with pure logical expressions but no NOT EXISTS filters. As an alternative, the set diference may be computed within the federation engine, for which the relevant sets of RDF terms (i.e., Info2(i) and Info2(ii)) have to be retrieved via preemptable SPARQL queries that contain the corresponding triple patterns. The drawback of this alternative option is that large amounts of data may end up being shipped from the server to the federation engine.
If federation members ofer a TPF interface or a smart-KG interface, the same alternative as for SaGe servers can be applied, just with using TPF requests instead of SPARQL queries, which also has the same drawback as in the case of SaGe (potentially large amounts of data might need to be transferred from the federation members to the federation engine). For smart-KG SELECT ?book WHERE { ?book rdf:type dbo:Book .
FILTER NOT EXISTS {
SELECT ?book WHERE {
?book dbo:author ?author .
} } . } LIMIT 1
SELECT ?book WHERE { ?book dbo:author ?author .
FILTER NOT EXISTS {
SELECT ?book WHERE {
?book rdf:type dbo:Book .
} } . } LIMIT 1 (b) servers it is additionally possible to fetch the corresponding partitions from the server and, then, extract the required sets of RDF terms locally, instead of via TPF requests.
If federation members use a brTPF interface, the option outlined for TPF and smart-KG can be simplified as follows. For each pair of triple patterns with a shared variable, first retrieve the set of triples matching one of the triple patterns (i.e., either Info2(i) or Info2(ii)) by using a TPF requests (as are supported by brTPF servers). Thereafter, attach a set of solution mappings (variable bindings for the shared variable) to a brTPF request for the other triple pattern, and obtain a second set of triples. If the number of distinct RDF terms bound to the shared variable in the second set of triples is less than the number of distinct RDF terms bound to the shared variable in the first set of triples, it indicates the set diference is not empty.
For federation members providing the SPF interface, the option outlined for brTPF can be used (and so can the option outlined for TPF and smart-KG). Additionally, for pairs of triple patterns that both have the shared variable in the subject position, another option exists: a star pattern request can be constructed and issued for retrieving matching triples for the pair of triple patterns. If the number of distinct RDF terms bound to the shared variable in matching triples for the star pattern is less than the number of distinct RDF terms bound to the shared variable in matching triples of any one of the single triple pattern requests, it indicates that the set diference is not empty. Fed-DSATUR [15] is another source selection approach that does not rely on statistics, indices, or any kind of estimates of the federation members and their datasets. Fed-DSATUR uses a greedy iterative strategy to get optimal query decomposition by considering properties of the SPARQL queries (e.g., the number of subqueries, and the triple patterns assigned to the subqueries as well as the federation members selected for each subquery). The particular information that Fed-DSATUR requires for each federation member is the same as FedX: SELECT DISTINCT ?p WHERE {
?s ?p ?o . }
SELECT DISTINCT ?s WHERE { ?s <predicate> ?o .
FILTER isIRI(?s) } } (b)
SELECT DISTINCT ?o WHERE { ?s <predicate> ?o .
FILTER isIRI(?o) } (c) SELECT DISTINCT ?p ?s WHERE {
VALUES ?p { <pred1> <pred2> <pred3> } ?s ?p ?o .
FILTER isIRI(?s)
SELECT DISTINCT ?p ?o WHERE {
VALUES ?p { <pred1> <pred2> <pred3> } ?s ?p ?o .
FILTER isIRI(?o) } (d) (e)
The HiBISCuS approach [16] relies on a combination of runtime requests and a summary of the dataset in each federation member. In order to build such a data summary for a federation member the following information needs to be available about the dataset.
Info3: All the URIs that are used as predicates in triples of the dataset.
Info4: For each of these predicate URIs, all the URIs that are used as subjects in triples with the predicate URI.
Info5: For each of these predicate URIs, all the URIs that are used as objects in triples with the predicate URI.
For federation members that provide a SPARQL endpoint, the SPARQL query in Figure 3a may be used for retrieving the predicate URIs (Info3). Thereafter, for each of the predicate URIs, two queries with DISTINCT together with an isIRI() filter can be used to get the set of URIs that are used as subjects (Info4) and as objects (Info5) in triples with the predicate URI. Figures 3b and 3c illustrate these two queries. As a more eficient alternative, instead of issuing these pairs of queries separately for each predicate URI, the requests can be batched by including multiple predicate URIs via a VALUES clause (or UNION or FILTER [17]), as illustrated in Figures 3d–3e.
For federation members with a SaGe interface, the same approach as for SPARQL endpoints can be applied. Notice, however, that the preemptable operator for DISTINCT has a client-side component, which means that the federation engine would need to do some processing itself for the queries that retrieve the relevant information (Figures 3a–3c) and that potentially some irrelevant intermediate solutions would be retrieved from the SaGe server.
If federation members expose data through a TPF interface, a brTPF interface or an SPF interface, the set of predicate URIs (Info3) can be obtained by a request with a triple pattern of the form (?s, ?p, ?o), which retrieves the complete dataset of the federation member. The removal of duplicate (predicate) URIs has to be taken care of by the federation engine. After retrieving the entire dataset in order to obtain all the predicate URIs, the required information about subject URIs (Info4) and object URIs (Info5) can then also be extracted from the retrieved data.
For federation members using a smart-KG interface, the set of distinct predicate URIs (Info3) can be obtained from the smart-KG catalog provided to the federation engine by the smart-KG server. Thereafter, for each of the predicate URIs, the set of subject URIs (Info4) and object URIs (Info5) can be obtained by fetching the relevant partitions from the smart-KG server or by issuing TPF requests with triple patterns of the form (?s, <predicate>, ?o). Since this would be done for every predicate URI, the federation engine would also end up retrieving the complete dataset from the smart-KG server. Similar to TPF-like interfaces, removing duplicate URIs and ifltering subjects/objects that are not URIs can only be done within the federation engine.
CostFed [18] also relies on a combination of runtime requests and a summary of the dataset in each federation member. The information that CostFed needs to build its type of data summary for a federation member is exactly the same information as is needed by HiBISCuS. Info3 (same as in Section 3.4): All the URIs that are used as predicates in triples of the dataset. Info4 (same as in Section 3.4): For each of these predicate URIs, all the URIs that are used as subjects in triples with the predicate URI.
Info5 (same as in Section 3.4): For each of these predicate URIs, all the URIs that are used as objects in triples with the predicate URI.
As already described in Section 3.4, Info3, Info4 and Info5 can be obtained in diferent ways depending on the interface of the federation member, where for several types of interfaces (TPF, brTPF, SPF, and smart-KG), this would mean retrieving the complete dataset from the corresponding federation member.
ANAPSID [21] makes use of service descriptions and runtime request to determine whether SPARQL endpoints can answer a triple pattern or not. The particular information that the source selection of ANAPSID requires from these service descriptions is a list of predicate URIs, which is the same as Info3 (cf. Section 3.4).
ADERIS [19] requires specific information about the data contained in each federation member before performing any query. The particular information that the source selection of ADERIS requires for each federation member is: Info3 (same as in Section 3.4): All the URIs that are used as predicates in triples of the dataset. Info6: For each of these predicate URIs, the number of triples with that predicate URI.
As already described in Section 3.4, the set of distinct predicates URIs (Info3) can be obtained in diferent ways depending on the interface of the federation member.
SELECT DISTINCT ?s WHERE {
?s ?p ?o . }
SELECT DISTINCT ?p WHERE {
<subject> ?p ?o . }
SELECT DISTINCT ?o1 WHERE { ?s dbo:birthDate ?o1 . ?s dbo:activeYearsStartYear ?o2 . ?s foaf:name ?o3 .
FILTER isIRI(?o1) } (a) (b) (c)
Once the predicate URIs are known to the federation engine, for federation members that provide a SPARQL endpoint or a SaGe interface, the number of triples with the same predicate URI (Info6) can be obtained via queries using the COUNT function.
For federation members with a smart-KG interface, a request with a triple pattern of the form (?s, <predicate>, ?o) can be issued for each predicate URI to obtain the first page of matching triples with that predicate, and estimates of the count metadata (Info6) can be obtained from the retrieved pages.
For federation members supporting TPF, brTPF, or SPF, since obtaining the set of predicates URIs (Info3) required retrieving the complete dataset from the federation member (cf. Section 3.4), the counting of triples per predicate URI (Info6) can then be done in the federation engine.
DARQ [20] relies on a so-called service description (represented in RDF), which describes the data available from a federation member in form of capabilities. The particular information that DARQ requires each federation member to provide includes Info3 (cf. Section 3.4) and hand-crafted constraints on subjects and objects. These constraints are represented using SPARQL filter expressions.
Odyssey [22] relies on statistics computed by federation members and shared with the federation
engine. The particular information that Odyssey requires from each federation member is the
following:
Info7: For each URI that appears in the subject of some triple, the characteristic set [
If the federation members do not provide such information, the federation engine may obtain the information via requests to the data access interfaces of the federation members.
For SPARQL endpoints and SaGe servers, to get all predicates of each subject URI (Info7), a set of all subject URIs needs to be retrieved first, which can be achieved via a query with DISTINCT (shown in Figure 4a). Then, for each subject URI, the predicate URIs that belong to the characteristic set of that subject URI (Info7) can be retrieved by a SPARQL query of the form in Figure 4b. These requests may also be batched for multiple subject URIs by using a VALUES clause (similar to the batching outlined in Figure 3d in Section 3.4, but with having subject URIs in the VALUES clause, instead of predicate URIs). Once the characteristic sets for all subject URIs have been obtained, all subject URIs that share the same characteristic set (Info8) can be determined within the federation engine. Thereafter, the set of object URIs for each predicate within a characteristic set (Info9) can be obtained by queries such as the one in Figure 4c. Notice that all these queries use the DISTINCT keyword which, in the case of SaGe, as already discussed in Section 3.4, requires some processing within the federation engine and potential retrieval of some irrelevant intermediate solutions.
For federation members with a TPF interface, a brTPF interface, a SPF interface, or a smart-KG interface, obtaining the set of predicates per subject URI requires retrieving the whole RDF dataset to the federation engine. After retrieving the entire dataset, all required information can be determined within the federation engine.
To identify and exclude federation members that have no matching triples for some of the triple patterns of a given query, some engines such as SPLENDID [23], Semagrow [24] and LHD [25] rely on external metadata that is shared by federation members and described using the Vocabulary of Interlinked Datasets (VoID) [26]. For source selection, these engines mainly make use of predicate information in the VoID descriptions, which allows them to identify whether federation members are relevant or irrelevant for any triple pattern with a bound predicate. For triple patterns with an unbound predicate, the engines use ASK queries as done by FedX. Hence, in general, the information that the source selection approaches of these engines use is the same as Info1 (Section 3.1) and Info3 (Section 3.4).
When taking into account the capabilities of diferent interfaces for providing access to RDF data, we observe that all existing source selection approaches can be adopted for heterogeneous federations by making some interface-specific modifications to the processes they use to collect the information they rely on. However, for many cases, these modifications would result in processes that are of limited suitability from a practical perspective.
In particular, for all approaches that rely on some form of data summary, index, or statistics about the data of each federation member—which includes the DARQ approach [20], ADERIS [19], HiBISCuS [16], CostFed [18], Odyssey [22], as well as VoID-based approaches as used in SPLENDID [23], LHD [25], Semagrow [24]—if federation members provide certain types of interfaces, obtaining the information required for building the corresponding data summary or index would result in retrieving the complete dataset from these federation members. As a consequence, the retrieved datasets may then also be stored locally, making the use of a federation engine obsolete.
Even for the approach of Lusail [14], potentially large amounts of data would need to be transferred from the federation members to the query engine for the purpose of deciding about combining triple patterns into subqueries.
The only approaches for which obtaining the relevant information is practical are the approach of FedX [13] and the Fed-DSATUR approach [15]. For these approaches, all required information can be obtained by issuing only a few requests to the federation members, where these requests are guaranteed not to result in retrieving large portions of the datasets.
This work was funded by CUGS (the National Graduate School in Computer Science, Sweden), by Vetenskapsrådet (the Swedish Research Council, project reg. no. 2019-05655), and by the CENIIT program at Linköping University (project no. 17.05). [11] J. Aimonier-Davat, H. Skaf-Molli, P. Molli, Processing SPARQL Property Path Queries Online with Web Preemption, in: Proceedings of the 18th Extended Semantic Web Conference (ESWC), 2021. [12] J. Aimonier-Davat, H. Skaf-Molli, P. Molli, A. Grall, T. Minier, Online Approximative SPARQL Query Processing for COUNT-DISTINCT Queries with Web Preemption, Semantic Web (2022). [13] A. Schwarte, P. Haase, K. Hose, R. Schenkel, M. Schmidt, FedX: Optimization Techniques for Federated Query Processing on Linked Data, in: Proceedings of the 10th International Semantic Web Conference (ISWC), 2011. [14] I. Abdelaziz, E. Mansour, M. Ouzzani, A. Aboulnaga, P. Kalnis, Lusail: A System for
Querying Linked Data at Scale, Proc. of the VLDB Endowment (2017). [15] M.-E. Vidal, S. Castillo, M. Acosta, G. Montoya, G. Palma, On the Selection of SPARQL Endpoints to Eficiently Execute Federated SPARQL Queries, in: Transactions on LargeScale Data- and Knowledge-Centered Systems XXV, Springer, 2016, pp. 109–149. [16] M. Saleem, A.-C. Ngonga Ngomo, HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation, in: Proceeding of the European Semantic Web Conference (ESWC), 2014. [17] C. B. Aranda, A. Polleres, J. Umbrich, Strategies for Executing Federated Queries in SPARQL1.1, in: Proceedings of the 13th International Semantic Web Conference (ISWC), 2014. [18] M. Saleem, A. Potocki, T. Soru, O. Hartig, A.-C. N. Ngomo, CostFed: Cost-Based Query Optimization for SPARQL Endpoint Federation, in: Proceedings of the SEMANTiCS Conference, 2018. [19] S. Lynden, I. Kojima, A. Matono, Y. Tanimura, ADERIS: An Adaptive Query Processor for Joining Federated SPARQL Endpoints, in: Proceedings of the Int. Conf. on Ontologies, Databases, and Applications of Semantics (ODBASE), 2011. [20] B. Quilitz, U. Leser, Querying Distributed RDF Data Sources with SPARQL, in: Proceedings of the European Semantic Web Conference (ESWC), 2008. [21] M. Acosta, M.-E. Vidal, T. Lampo, J. Castillo, E. Ruckhaus, ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints, in: Proceedings of the International Semantic Web Conference (ISWC), 2011. [22] G. Montoya, H. Skaf-Molli, K. Hose, The Odyssey Approach for Optimizing Federated SPARQL Queries, in: Proceedings of the International Semantic Web Conference (ISWC), 2017. [23] O. Görlitz, S. Staab, SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions, in: Proc. of the 2nd Int. Workshop on Consuming Linked Data (COLD), 2011. [24] A. Charalambidis, A. Troumpoukis, S. Konstantopoulos, SemaGrow: Optimizing Federated
SPARQL Queries, in: Proc. of the 11th Int. Conf. on Semantic Systems (SEMANTiCS), 2015. [25] X. Wang, T. Tiropanis, H. C. Davis, LHD: Optimising Linked Data Query Processing Using
Parallelisation, in: Proceedings of the Linked Data on the Web Workshop (LDOW), 2013. [26] K. Alexander, R. Cyganiak, M. Hausenblas, J. Zhao, Describing Linked Datasets with the VoID Vocabulary, W3C Interest Group Note, Online at http://www.w3.org/TR/void/, 2011.