3.1 Metadata catalogs

The existing query federation engines use three types of metadata catalogs: (i) service descriptions (Quilitz & Leser, Reference Quilitz and Leser2008), (ii) VoID (Vocabulary of Interlinked Datasets) descriptions (Alexander & Hausenblas, Reference Alexander and Hausenblas2009) and (iii) list of predicates. Before we begin, we want to remark that data set and data source are used interchangeably.

• ∙ Service description: provides metadata about the RDF data and cover some statistics about this data. It states the potential capacity of a data source by containing statistics; such as number of triples with a predicate and total triples. In other saying, a service description takes into account the information about the data set, which means a set of RDF triples which is published by a single provider.

• ∙ VoID description: provides metadata about the RDF data and cover some statistics about this data like service descriptions. In addition to the information about data sets, there is another concept in VoID which is called linkset. A linkset describes a set of RDF triples where all subjects refer to one data set and all objects belong to another data set (Alexander & Hausenblas, Reference Alexander and Hausenblas2009). Thus, VoID can be used to describe the metadata of RDF data sets with the interlinking to other data sets. In addition to these, statistics about the data sets can be defined in VoID descriptions as service descriptions. Number of triples and number of instances of a class or property are some examples of the statistics here. Cyganiak et al. (Reference Cyganiak, Zhao, Alexander and Hausenblas2011) proposed a VoID guide to data publishers or consumers.

• ∙ List of predicates: list of predicates is also used as a metadata catalog.

3.2 Data source selection methods

As indicated in the beginning of this section, according to our classification there are four data source selection methods of query federation engines as follows:

• ∙ Predicate-based selection: selects the relevant data sources of a triple pattern by matching its predicate with the covered predicates in the metadata catalog.

• ∙ Type-based selection: selects the relevant data sources according to the type definitions (rdf:type) in the metadata catalog.

• ∙ Rule-based selection: selects the relevant data sources according to the defined rules which are generated by analyzing the relations between the triple patterns of a query.

• ∙ SPARQL ASK queries: selects the relevant data sources by sending SPARQL ASK queries to the endpoints. If the result of the query is TRUE, this data source is selected as a relevant data source.

DARQ uses service descriptions for its metadata catalog and these descriptions must be created before using the query engine. It employs predicate-based data source selection. Therefore, the engine cannot support unbound predicate triple patterns.

SPLENDID uses VoID descriptions in data source selection. Data sources are indexed for every predicate and type by using VoID statistics. However, the statistics in VoID descriptions can be insufficient to select a triple pattern’s relevant data source or data sources. This situation exists especially for the triples with common predicates such as rdfs:label. Almost all data sets use this predicate, thus SPLENDID sends SPARQL ASK queries for the triples with bound variables which are not covered in VoID descriptions. All data sources are selected for the triple patterns which have unbound predicates.

LHD (Wang et al., Reference Wang, Tiropanis and Davis2013) is another federated query engine that uses VoID descriptions together with SPARQL ASK queries in data source selection. It first uses VoID descriptions and then sends SPARQL ASK queries to refine the selected data sources. Its data source selection is based on predicates as DARQ. However, it can support unbound predicates without eliminating irrelevant data sources such as SPLENDID.

WoDQA, which was first proposed by Akar et al. (Reference Akar, Halaç, Ekinci and Dikenelli2012) and then was enhanced by Yönyül (Reference Yönyül2014), also uses VoID descriptions and SPARQL ASK queries in data source selection. Akar et al. (Reference Akar, Halaç, Ekinci and Dikenelli2012) stated that predicate-based and type-based selection is not enough to eliminate all irrelevant data sources due to having common predicates or types. Hence, Akar et al. (Reference Akar, Halaç, Ekinci and Dikenelli2012) proposed different rules based on query pattern analysis. These rules are proposed with three perspectives; IRI-based analysis, linking analysis and shared variable analysis. IRI-based analysis selects the relevant data sources by matching the IRIs in the triple pattern with the void:uriSpace and void:vocabulary properties of VoID descriptions. Furthermore, IRI-based analysis includes the predicate-based selection and type-based selection methods as well. By this means, WoDQA does not only select the data sources according to the predicate or type of a query, it considers all the IRIs in a query. In linking analysis, WoDQA takes into consideration the linkset definitions in the VoID descriptions. Lastly, in the shared variables analysis, WoDQA considers that triple patterns with shared variables can affect their related data sources. In other words, shared variables analysis aims to eliminate the irrelevant data sources.

As stated previously, list of predicates can also be used as a metadata catalog. ANAPSID (Acosta et al., Reference Acosta, Vidal, Lampo, Castillo and Ruckhaus2011) keeps a list of predicates, the execution timeout properties of the endpoints and the statistics as metadata catalog. The endpoints’ execution timeouts and statistics are collected by an adaptive sampling technique (Vidal et al., Reference Vidal, Ruckhaus, Lampo, Martnez, Sierra and Polleres2010; Blanco et al., Reference Blanco, Cardinale and Vidal2012) or during the query execution. It also updates the statistics on the fly. ANAPSID uses predicate-based selection and chooses the endpoints whose timeout is longer than the triple patterns estimated execution time. However, the details are not given in their publication so it is not clear how ANAPSID estimates the triple patterns’ execution times. ADERIS (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2010, Reference Lynden, Kojima, Matono and Tanimura2011) also uses list of predicates as metadata catalog and predicate-based selection for data source selection. It sends SPARQL SELECT queries with DISTINCT keyword to each endpoint to find out the unique predicates. Besides, ADERIS adds data sources manually when it is impossible to do that automaticallyFootnote ¹.

FedX (Schwarte et al., Reference Schwarte, Haase, Hose, Schenkel and Schmidt2011) sends SPARQL ASK queries for each triple pattern in order to decide if the intended query can be answered by the endpoint or not and it also caches the relevance of each triple with each data source.

Table 1 shows the data source selection methods in the existing query federation engines. As seen from the table, predicate-based selection and sending SPARQL ASK queries are the common methods. FedX just sends SPARQL ASK queries to select the data sources. Although SPLENDID uses VoID descriptions to select the data sources based on predicates and types, it sends SPARQL ASK queries when the descriptions cannot help to select the relevant data sources. DARQ selects the data sources based on predicates via service descriptions. However, it does not send SPARQL ASK queries when its metadata catalog fails to select the data sources. LHD employs predicate-based selection via VoID descriptions and sends SPARQL ASK queries in order to eliminate the irrelevant data sources. ANAPSID and ADERIS use predicate-based selection as DARQ. However, ANAPSID also considers the execution timeout information of endpoints as well. Different from other engines, WoDQA uses rule-based selection by query pattern analysis and considers the linksets in VoID descriptions. Hence, it eliminates all the irrelevant data sources before the query execution by considering the relations between triple patterns. It also uses SPARQL ASK queries.

Table 1

Data source selection methods in query federation

The data source selection methods in query federation show that using a metadata catalog is a need. Without a metadata catalog, data source selection becomes quite difficult and time consuming due to the need of preprocessing for each query. This time-consuming task usually is done by SPARQL ASK queries. However, first employing a metadata catalog and then when the selection cannot be done through the catalog, using SPARQL ASK queries seems a better strategy for data source selection in federated query processing.

In addition to the mentioned data source selection methods, Saleem and Ngomo (Reference Saleem and Ngomo2014) proposed an approach for data source selection as well. We have not included them to our classification because it is a data source selection approach, not a query federation engine.

4.1 Bind join

Bind join was introduced by Haas et al. (Reference Haas, Kossmann, Wimmers and Yang1997). The method passes the bindings of the intermediate results of the outer objects to the inner object in order to filter the result set. Its execution is similar to the nested loop join and substantially efficient when the intermediate results are small (Haas et al., Reference Haas, Kossmann, Wimmers and Yang1997).

Bind join, also called bound join, is commonly used in federated query processing. Schwarte et al. (Reference Schwarte, Haase, Hose, Schenkel and Schmidt2011) proposed a bound join technique for FedX which uses SPARQL UNIONFootnote ² constructs to group a set of mappings in a subquery to be sent to the relevant data sources in a single remote request. The original mapping is kept in order to retain correctness of the final results. WoDQA (Yönyül, Reference Yönyül2014) uses bound join method as well. However, FedX uses SPARQL UNION constructs whereas WoDQA prefers SPARQL FILTERFootnote ³ expression for bound join. In addition, SPARQL 1.1 Query LanguageFootnote ⁴ (March 2013) proposes SERVICEFootnote ⁵ keyword to explicitly execute certain subqueries on different SPARQL endpoints and WoDQA takes the advantage of SERVICE keyword in its bound join.

DARQ (Quilitz & Leser, Reference Quilitz and Leser2008), ANAPSID (Acosta et al., Reference Acosta, Vidal, Lampo, Castillo and Ruckhaus2011), ADERIS (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2011), LHD (Wang et al., Reference Wang, Tiropanis and Davis2013) and SPLENDID (Görlitz & Staab, Reference Görlitz and Staab2011b) employ bound join as well. We will talk about their usage later. Different from other engines, DARQ employs bound join when the data sources have limitations on access patterns. For this reason, DARQ keeps the definition of limitations on access patterns in service descriptions.

4.2 Nested loop join and hash join

Nested loop join method is used by Quilitz and Leser (Reference Quilitz and Leser2008) for query execution in DARQ when there is no limitation on access patterns. The inner relation is scanned for every binding in the outer relation and the bindings which provide the join condition are included in the result. ADERIS applies index nested loop join method in query execution which uses an index on join attributes.

Hash join is another join method used in federated query processing. Görlitz and Staab (Reference Görlitz and Staab2011a) implemented a hash join method for SPLENDID which requests the results of the join argument in parallel and joins them locally. Wilschut and Apers (Reference Wilschut and Apers1991) stated that although hash join method is symmetric conceptually, it is asymmetric in it operands.

4.3 Symmetric join

Symmetric hash join (Wilschut & Apers, Reference Wilschut and Apers1991) is a non-blocking hash-based join which supports pipelining in parallel database systems. It maintains a hash table for each relation. In other words, symmetric hash join creates two hash tables instead of generating a single hash table as in hash join method. Thus, symmetric hash join is a non-blocking join method which produces the output of tuples as early as possible. However, it requires more memory due to keeping the hash tables in memory.

The double pipelined hash join (Ives et al., Reference Ives, Florescu, Friedman, Levy and Weld1999) and the XJoin (Urhan & Franklin, Reference Urhan and Franklin2000) are the extended versions of symmetric hash join. Different from the symmetric hash join, double pipelined hash join adapts its execution when the memory is insufficient and XJoin moves some parts of hash tables to the secondary storage when the memory is full.

Acosta et al. (Reference Acosta, Vidal, Lampo, Castillo and Ruckhaus2011) proposed a non-blocking join method, called adaptive group join (agjoin), which is based on symmetric hash join and XJoin. This join method produces incremental results by presenting a data structure called resource join tuple (RJT), which records the join values and the tuples that are matched. By this means, ANAPSID can produce results even when an endpoint becomes blocked and can hide delays from users. Adaptive dependent join (adjoin) is the extended version of dependent join (Florescu et al., Reference Florescu, Levy, Manolescu and Suciu1999). It sends requests to the data sources in an asynchronous fashion and hides delays from the user. Specifically, it sends the request to the second data source when tuples from the first source are received. Actually, adjoin can be accepted as a bound join because it needs the bindings. Both agjoin and adjoin flush to the secondary memory when the memory is full as XJoin does. In addition, when the both endpoints become blocked, the RJTs in the first and second memory are joined.

4.4 Multiple hash join

The execution system of LHD (Wang et al., Reference Wang, Tiropanis and Davis2013) is similar to double pipelined hash join (Ives et al., Reference Ives, Florescu, Friedman, Levy and Weld1999) and XJoin (Urhan & Franklin, Reference Urhan and Franklin2000). It uses multiple hash tables at a node. Wang et al. (Reference Wang, Tiropanis and Davis2013) stated that a node can be a subject or an object, while an edge refers to triple patterns. Also a data stream was defined as the results of triple patterns of an edge. LHD uses multiple hash tables in order to join more than one data stream at the same time. The result of a stream is stored in its hash table and it is probed against the hash tables of other streams simultaneously. On the other hand, LHD employs bound join when pre-computed bindings are used. Wang et al. (Reference Wang, Tiropanis and Davis2013) proposed a join operator that separates the input bindings via a hash table on the dependent variable or variables. If there is only one binding in the query, the variables in the query is replaced by the values of the binding. Otherwise, the bindings are specified with VALUESFootnote ⁶ syntax.

Table 2 shows the join methods in federated query processing on linked data. All the engines employ bound join. DARQ, SPLENDID, ANAPSID, ADERIS and LHD provide two different join methods whereas FedX and WoDQA implement one join method. Different from others, ANAPSID uses a non-blocking join method which is an extended version of symmetric hash join and XJoin. However, it uses its own data structure instead of hash tables. For this reason, we name this method as symmetric join.

Table 2

Join methods in query federation

NLJ=nested loop join.

As the final remark of this section, we would like to mention three papers which are related to the efficiencies of query federation engines. Buil-Aranda et al. (Reference Buil-Aranda, Arenas, Corcho and Polleres2013) described and formalized the syntax of federation extension for SPARQL 1.1, whereas Buil-Aranda et al. (Reference Buil-Aranda, Polleres and Umbrich2014) focused on the limitations of SPARQL servers when using SPARQL 1.1. They showed that SPARQL servers can limit the amount of result sizes and these limitation can be overcome by using SERVICE patterns in queries. They also discussed different evaluation strategies and showed that results of all queries in all systems under test are returned by using only FILTER and ‘symmetrical hash join with pagination of the remote results’ strategies. Saleem et al. (Reference Saleem, Ngomo, Parreira, Deus and Hauswirth2013) proposed a duplicate-aware approach, namely DAW, which can be adapted to query federation engines. They extended DARQ, SPLENDID and FedX with this approach, and compared the engines with their extended versions. They showed that query execution times are reduced in most cases by extending the engines with the proposed approach. The engines should consider the limitations mentioned by Buil-Aranda et al. (Reference Buil-Aranda, Polleres and Umbrich2014) and can use a duplicate-aware approach like DAW (Saleem et al., Reference Saleem, Ngomo, Parreira, Deus and Hauswirth2013) to increase their efficiencies.

5.1 Subquery building

A SPARQL query is comprised of triple patterns. A subquery can be composed of a triple pattern or a set of triple patterns. Therefore, subquery building refers to grouping the triple patterns of a query in order to decrease the number of HTTP requests and intermediate results. We classify the subquery building methods used in query federation engines as follows: (i) exclusive grouping (EG), (ii) exclusive grouping considering shared variables (EGSV) and (iii) owl:sameAs grouping (SAG). We first define these methods and then explain their roles in the existing query federation engines.

• ∙ EG: a heuristic which groups the triple patterns that refer to the same data source with a provision that there must be one and only one relevant data source (Schwarte et al., Reference Schwarte, Haase, Hose, Schenkel and Schmidt2011). The grouped triple patterns are called exclusive groups. In other words, the triple patterns in an exclusive group must refer to a single data source. This heuristic aims to reduce both HTTP requests and intermediate results.

• ∙ EGSV: extended version of the EG heuristic which creates different exclusive groups for the triple patterns without shared variables. EG method can group triple patterns which do not have shared variables and it causes redundant intermediate results.

• ∙ SAG: creates a subquery for the triple pattern which has owl:sameAs predicate with an unbound subject variable and the triple pattern which has the same unbound variable. This method is used when there is an assumption that this predicate is used in order to indicate the internal resources of a data set.

The idea behind the EG was proposed by Quilitz and Leser (Reference Quilitz and Leser2008) for DARQ. However, the method was titled as exclusive grouping by Schwarte et al. (Reference Schwarte, Haase, Hose, Schenkel and Schmidt2011) for FedX. Although ANAPSID (Acosta et al., Reference Acosta, Vidal, Lampo, Castillo and Ruckhaus2011) does not use the name of EG, it groups the triple patterns which refer to the same endpoint. SPLENDID (Görlitz & Staab, Reference Görlitz and Staab2011b) uses both EG and SAG. The assumption about the SAG here is that all data sources describe owl:sameAs links for their data. This grouping can be realized manually when third-party data sets with external owl:sameAs links do not exist in the federation. WoDQA is the only engine which uses EGSV.

After data source selection, ADERIS (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2010, Reference Lynden, Kojima, Matono and Tanimura2011) generates predicate tables which include subject and object of triples associated with each unique predicate in the intended query. In order to create these tables, the engine sends triple patterns to data sources by considering the predicates contained in each data source. In other words, ADERIS groups and sends triple patterns to the relevant endpoint together if their predicates are covered in the same data source. Actually, the main idea of this grouping is the same with EG.

To conclude this subsection, there are three methods for subquery building in query federation engines which are EG, EGSV and SAG. Although some engines group the triple patterns which refer to the same data source, they do not name this method as EG. On the other hand, SAG is used when there is an assumption that this predicate is used for the resources of one data set. Each triple pattern of a query is accepted as a subquery without using these methods.

5.2 Join method selection

The second decision in query optimization is join method selection. In this decision, the join method is selected if more than one exists. As stated in Section 4, DARQ, SPLENDID, ANAPSID, ADERIS and LHD implement two different join methods. We classify the methods for join method selection as follows: (i) binding limitation-based (BLB), (ii) cost-based (CB) and (iii) time constrained-based (TCB).

ANAPSID employs bound join when a binding is required by a data source. We refer to this selection method as BLB. DARQ employs bound join when the data sources have limitations on access patterns. Actually, it can be accepted as a binding limitation. However, when there is no binding limitation, DARQ employs cost models for join method selection as well. We refer to this selection method as CB.

After data source selection, for each predicate, ADERIS generates a predicate table with two columns (subject, object) by sending queries to the selected sources. Using these predicate tables, the join could be done with index nested loop join method. However, some endpoints may refuse to answer the queries for building predicate tables, if the estimated execution time is longer than a given threshold. If a predicate table is missing, the engine sends a subquery with bindings for the subject/object values to the corresponding endpoint, meaning that the join method becomes bound join. We refer to this selection method as TCB method.

SPLENDID and LHD use cost models for join method selection as DARQ. Equation (1) (Quilitz & Leser, Reference Quilitz and Leser2008) and Equation (2) (Quilitz & Leser, Reference Quilitz and Leser2008) are the cost functions of DARQ for nested loop join and bound join, respectively, where q and p are the relations, R(q) the result size of q, c _t the transfer cost for one tuple and c _r the transfer cost for one query. p′ is the relation with the bindings of q. We see that DARQ considers the transfer cost for each tuple and the transfer cost for each query in its cost functions. The transfer cost for one query is multiplied by two in nested loop join, whereas it is multiplied with the result size of the first relation in bound join. Besides, even though the transfer cost for one tuple is multiplied by result size for both two relations, the result size of the second relation is reduced by the bindings of the first join argument in bound join. SPLENDID uses the same cost functions. It uses Equation (1) for hash join and Equation (2) for bound join:

(1) $$cost(q \,\raster="rg1" \,_{H}\,p)=R(q) \cdot c_{t} {\plus}R(p) \cdot c_{t} {\plus}2 \cdot c_{r} $$

(2) $$cost(q \,\raster="rg1" \, _{B} \,p)=R(q) \cdot c_{t} {\plus}R(q) \cdot c_{r} {\plus}R(p') \cdot c_{t} $$

LHD (Wang et al., Reference Wang, Tiropanis and Davis2013) proposes a cost function assuming that response time of a query is proportional to the number of bindings. It first estimates the cardinalities of each operation by using statistics in VoID descriptions and then estimates the response time of query plans. It proposes two different plans according to the usage of bindings in query execution. The plan is named as plain access plan when a triple pattern is executed directly whereas the plan is called as dependent access plan when intermediate bindings are used to execute the triple pattern.

Equations (3–6) (Wang et al., Reference Wang, Tiropanis and Davis2013) show the cost functions where a plain access plan of triple pattern t is denoted as acc(t) and dependent access plan with bindings of q is represented as acc(q, t). Also rt _q is the time of sending a triple pattern or a pre-computed result to a data source, and rt _t is the time of receiving a result. Actually, these functions are quite similar to the cost models of DARQ and SPLENDID:

(3) $$cost(q \,\,\raster="rg1" \,_{H}\, p)=maximum(cost(q),\,cost(p))$$

(4) $$cost(q \,\raster="rg1" \,_{B} \,p)=cost(q){\plus}cost(acc(card(q),\,t))$$

(5) $$cost(acc(t))=rt_{q} {\plus}card(t) \cdot rt_{t} $$

(6) $$cost(acc(q,t))=card(q) \cdot rt_{q} {\plus}card(q \,\,\raster="rg1" \,\, t) \cdot rt_{t} $$

5.3 Join ordering

Ibaraki and Kameda (Reference Ibaraki and Kameda1984) stated that finding an optimization cost for a query is admitted as computationally intractable. Starting from this point of view, Gardarin and Valduriez (Reference Gardarin and Valduriez1990) specified that heuristics are necessary for optimizing the cost functions. Due to huge and distributed data space, query processing with SPARQL endpoints is a difficult task. Thus, using heuristic methods for join order optimization in federated query processing is an expected case.

FedX and WoDQA employ various heuristics for join ordering. We name these heuristics as follows:

• ∙ Free variables heuristic (FVH): considers the number of free and bound variables. The number of free variables of triple patterns and groups are counted with considering the already bound variables from the earlier iterations. In other words, the free variables which have become bound from the earlier iterations are accepted as bound variables.

• ∙ Exclusive group priority heuristic (EGPH): gives priority to exclusive groups.

• ∙ Position and type-based selectivity heuristic (PTSH): calculates the heuristic selectivity value of each triple pattern as multiplying the coefficients of each node according to their positions with the coefficients of each node according to their types.

• ∙ Shared variables heuristic (SVH): reorders the join order by considering the shared variables between triple patterns.

FedX orders both the triple patterns and groups of triple patterns by using FVH. The triple patterns and groups are chosen with the lowest cost iteratively.

WoDQA orders the triple patterns of each query by using PTSH after creating the exclusive groups of each query. The coefficient of position and types are assigned according to their selectivities. It considers that subjects are more selective than objects and objects are more selective than predicates. A similar strategy is used by Stocker et al. (Reference Stocker, Seaborne, Bernstein, Kiefer and Reynolds2008) for the Jena ARQ optimizer in which they categorize this estimation as heuristics without pre-computed statistics and state that there are more triples matching with a predicate than a subject or an object in a typical data source. But at the same time Stocker et al. (Reference Stocker, Seaborne, Bernstein, Kiefer and Reynolds2008) specify that making a distinction between subject and object is more difficult. On the other hand, WoDQA orders the selectivities of types as URIs, literals and variables.

After ordering the triple patterns in an exclusive group by employing PTSH, WoDQA uses SVH in order to order exclusive groups. The triple patterns which do not have shared variables are changed with the next triple pattern to process the related joins as early as possible. After finishing the ordering of triple patterns of each exclusive group, WoDQA orders the exclusive groups. It calculates the mean selectivity of each group by using PTSH. Lastly, this order is changed by employing SVH for exclusive groups. There is a difference between the usage of SVH for triple patterns and exclusive groups. The exclusive group which has more shared variables than the consequent group moves up in the order of exclusive groups. The aim of ordering the exclusive groups is to decrease the intermediate results as well.

Different from the above engines, DARQ, SPLENDID, LHD and ADERIS use cost-based (CB) methods for join ordering. DARQ, SPLENDID and LHD use dynamic programming (DP) whereas ADERIS employs greedy algorithm (GA) for the search strategy. The cost functions of DARQ and SPLENDID (Equations (1 and 2)), and LHD (Equations (3–6)) are explained in the previous subsection. Both of these engines consider the cardinality estimations, cost for sending a triple pattern and cost for receiving a result. Query result size estimation in DARQ is done by using the statistics in the service descriptions. On the other hand, SPLENDID and LHD use VoID statistics for the cardinality estimations in their cost functions.

As mentioned in the previous section, LHD classifies the execution of joins as follows: (i) joins which do not require input bindings (plain access plan) and (ii) joins which require pre-computed bindings (dependent access plan). The joins in the first class can be executed in a parallel fashion whereas the second one should be executed in a sequence due to the need of bindings. LHD uses plain access plans for the triple patterns which have concrete subject or object. We refer to that heuristic as concrete subject or object heuristic (CSOH). Therefore, it first executes these triple patterns and then uses DP to find the query plan with the minimum response time. Thus, we can say that LHD uses both heuristics and DP in query planning. Second, it determines the actual order of triple patterns to execute them in a parallel way by taking into consideration the type of access plans, bound variables and the already bound variables from the previous iterations. For example, it executes the triple patterns with plain access plan concurrently and the triple patterns with the dependent access are executed as soon as its bindings are ready. In addition, it proposes a concurrent control system to use the bandwidth and data sources efficiently by separating the execution of plans from communication from data sources.

Different from above engines, ADERIS supports adaptive query processing. The first version of ADERIS (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2010) builds predicate tables for federated query processing and adaptively joins two tables as they become complete while the other predicate tables are being generated. In the second version (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2011), the engine can employ non-materialized predicate tables and it uses an adaptive cost model for query optimization. Equation (7) (Lynden et al., Reference Lynden, Kojima, Matono and Tanimura2011) shows the cost model of ADERIS where incard is the estimated input cardinality for each iteration, lookupTime refers to the average time taken to probe a given table t and R is the remaining set of tables that need to be joined to the current plan. Furthermore, join ordering is based on a GA. Most importantly, the engine estimates cardinality at each stage for join ordering.

(7) $$cost(t)=incard \cdot lookupTime(t) \cdot \mathop{\sum}\limits_{i \in R} {lookupTime(i) \cdot cardEst(t)} $$

Table 3 shows the query optimization methods used in each decision in query federation engines. In order to decrease the HTTP requests, DARQ, FedX, SPLENDID, ANAPSID and ADERIS use EG. WoDQA employs EGSV. Thus, it aims to decrease the redundant intermediate results as well. SPLENDID employs SAG together with EG. However, this method cannot be used when other data sets use owl:sameAs predicate to define that the resource in their data sets indicates to the same resource in other data sets. Although LHD does not group the triple patterns, it sends them in a parallel fashion. The second decision and the third decision are the join method selection and the join ordering. Actually, they are substantially related with each other in query federation. FedX and WoDQA use some heuristics whereas DARQ, SPLENDID, ADERIS and LHD propose cost functions for join ordering. FedX orders the joins by using FVH and EGPH. WoDQA first orders the triple patterns by using PTSH and SVH. Second, it orders the exclusive groups by SVH. The different usages of SVH for the triple patterns and the exclusive groups are explained in the beginning of this subsection. DARQ and SPLENDID use CB method and DP for join method selection and join ordering. DARQ also uses BLB method for join method selection. ANAPSID selects the join method by employing BLB method as well. LHD first uses CSOH and then employs DP for join method selection and join ordering according to the proposed cost function. ADERIS employs TCB method for join method selection and uses GA for join ordering.

Table 3

Query optimization methods in query federation

EG=exclusive grouping; EGSV=exclusive grouping shared variables; SAG=owl:sameAs grouping; BLB=binding limitation-based; TCB=time constrained-based; CB=cost-based; FVH=free variables heuristic; EGPH=exclusive grouping priority heuristic; PTSH=position and type-based selectivity heuristic; SVH=shared variables heuristic; CSOH=concrete subject or object heuristic; DP=dynamic programming; GA=greedy algorithm.

6.1 Discussion on query federation on linked data

We provide a qualitative comparison of query federation engines according to the following criteria:

• ∙ No preprocessing per query: data source selection without using a metadata catalog might cause some performance problems due to the need of preprocessing per query.

• ∙ Unbound predicate queries: predicates are less selective than subjects and objects in a typical data source (Stocker et al., Reference Stocker, Seaborne, Bernstein, Kiefer and Reynolds2008). Therefore, selecting the data source for a query with an unbound predicate is a difficult task. However, the data source selection methods of some engines are based on predicates. These query federation engines might have some problems to handle queries with unbound predicates.

• ∙ Parallelization: parallelization is another fact which improves the performances of engines due to the concurrent query processing. Parallelism can be achieved in two forms which are inter-operator parallelism and intra-operator parallelism. In inter-operator parallelism, more than one operation of a query are executed concurrently whereas a single operator is executed by multiple processors in intra-operator parallelism.

• ∙ Adaptive query processing: adaptive query processing (Deshpande et al., Reference Deshpande, Ives and Raman2007) is a form of dynamic query processing which reacts to the unforeseen variations of run-time environment (Ozsu & Valduriez, Reference Ozsu and Valduriez2011). As the federated query processing is done on the Web, adaptive query processing is required in order to manage the changing conditions such as endpoint unavailability and timeouts.

Table 4 shows the qualitative comparison of engines with the mentioned criteria. All except FedX do not need preprocessing per query before query processing due to metadata catalogs. FedX sends SPARQL ASK queries to data sources for each query. Other engines primarily employ metadata catalogs. Actually, ADERIS sends SELECT DISTINCT queries to decide which predicates are covered by each data source. However, it does not send individual SPARQL ASK queries for each triple pattern in the query.

Table 4

Comparison of query federation engines

DARQ and ANAPSID cannot manage unbound predicate queries due to their predicate-based data source selections. SPLENDID, ADERIS and LHD handle queries with unbound predicates, although the data source selection methods of ADERIS and LHD are based on predicates. LHD and SPLENDID support unbound predicates without eliminating irrelevant data sources and ADERIS defines data sources manually when it cannot do that automatically. They might cause some performance problems but the queries with unbound predicates can be supported by this way.

FedX, ANAPSID and LHD execute the triple patterns in a parallel fashion. FedX integrates a parallelization infrastructure to execute subqueries at different endpoints concurrently. And also it uses a pipelining approach to send intermediate results to the next operator as they are ready. ANAPSID executes the triple patterns in parallel by proposing a join method based on symmetric hash join and XJoin. LHD separates the query plans and communication with data sources for parallelization. Several threads are used for sending triple patterns to a data source and for receiving results from a data source. It also considers the type of access plans, bound variables and the already bound variables from the previous iterations to adopt parallelization. Furthermore, it uses multiple hash joins. FedX provides inter-operator parallelism whereas ANAPSID employs intra-operator parallelism. LHD affords both inter-operator and intra-operator parallelism.

Only ANAPSID and ADERIS enable adaptive query processing. ANAPSID proposes adaptive join methods which produce new results when one of the endpoints becomes blocked. On the other hand, ADERIS provides adaptive query processing by changing the join order.

Table 5 shows the common measured metrics of the query federation engines. We think that these metrics are important as they show the main focus of query federation engines. The first three metrics are about the data source selection, the fourth and fifth one are about query optimization, and the sixth and seventh one are about the general performances of the engines. First tuple time and comparison with other engines are other measured metrics. Looking at these metrics, we can say that the studies in query federation mainly focus on the data source selection part so far. In order to make efficient query processing in this global and distributed data space, the first requirement is to select only the relevant data sources. As we have mentioned in the previous parts, SPARQL ASK queries can be used in data source selection. As the number of SPARQL ASK queries and the selected data sources increase, the network communication increases as well. Furthermore, data source selection time certainly gives idea about the performance of data source selection. For this reason, we can say that the first two metrics show the performances of engines in data source selection step. The number of HTTP requests is about query optimization. This number changes according to the number of subqueries, join methods and join ordering. Query planning and optimization time is another measured metric which is certainly related to query optimization step. The next two metrics are the number of queries executed per second and the response time. The main objective of query federation engines is to minimize the response time. For this reason, the response time is the most common metric. Different from other engines, ANAPSID evaluated the first tuple time to show the advantages of non-blocking join methods. The last measured metric in the table is comparison with other engines. In addition to these metrics, LHD evaluated the size of outcoming and incoming data, the CPU usage per query and the memory usage per query.

Table 5

Measured metrics of query federation engines

A=number of SPARQL ASK queries; B=number of selected data sources; C=data source selection time; D=number of HTTP requests; E=query planning and optimization time; F=number of queries executed per second; G=response time; H=first tuple time; I=comparison with other engines.

6.2 Challenges

During surveying the studies in query federation on linked data, we have realized that there are some challenges and open research issues in this field, namely, metadata management, caching results and adaptive query processing. In this subsection, we state these challenges and suggest some ideas to handle them. Distributed query processing has been studied in database research for a long time. Therefore, we believe that some approaches in database field can be adapted to query federation on linked data to overcome the caching and adaptive query processing challenges.