1 Introduction
Listing 1.1: Running example (LD3 from FedBench)
SELECT ? p r e s i d e n t ? p a r t y ? p a g e
WHERE f
? p r e s i d e n t r d f : t y p e d b p e d i a : P r e s i d e n t .
? p r e s i d e n t d b p e d i a : n a t i o n a l i t y d b p e d i a : U n i t e d S t a t e s .
? p r e s i d e n t d b p e d i a : p a r t y ? p a r t y .
? x n y t : t o p i c P a g e ? p a g e .
? x owl : sameAs ? p r e s i d e n t .
g
While several types of federated queries exist, we focus on federated SPARQL
queries herein. An example of such a query is shown in Listing 1.1. This query retrieves
the political party and the NYT website of presidents who are nationals of the United
States. The generic architecture of a federated SPARQL query engine is as shown in
Figure 1. The input query q is first sent to a parser/rewriter, which reads and checks the
query for whether it is a valid SPARQL query as well as rewrites it if necessary. The
query is then forwarded to a source selection approach, which determines the subset of
the knowledge bases S1; : : : ; Sn that must be queried to compute the result set of the
input query. This is most commonly carried out by a triple-pattern-wise source selection,
where the sources necessary to retrieve result sets for each triple pattern T1; : : : ; Tm of q
are detected. After the computation and optimization of a query plan, the sources for each
of the triple patterns are queried by means of a federator. The results are subsequently
merged by means of the integrator and the query results are returned. Improving the
performance of federated SPARQL query processing engines is equivalent to improving
the performance of each of these components.
Result
Query
Parsing/Rewriting
Source Selection
Federation/Optimization
Integration
S1
S2
: : :
Sn
This section addresses four of the most pressing challenges in the area of federated
SPARQL query processing. We derive these challenges from [
12,13
]. In [
12
], we
gathered query logs from SPARQL endpoints on the Web and performed an analysis of their
structure and runtime. The queries from which the insights presented herein were derived
can be found in LSQ’s SPARQL endpoint.1 Our other source, [
13
], presents a survey2
and fine-grained evaluation of state-of-the-query federated query processing engines.
2.1
Source Selection
Source selection aims to map each of the triple patterns in the input query q to a set of
data sources. Most SPARQL query federation approaches [
4,5,11,19,20,16,15
] perform
a triple-pattern-wise source selection (TPWSS). Here, the goal is to identify the set of
relevant (also called capable) sources for each individual triple patterns Tj of a query q,
i.e., the set of sources Si that return a non-empty result set when queried with this triple
pattern. However, it is possible that a relevant source does not contribute to the final result
set of a query. This is because the results from a particular data source can be excluded
after performing joins with the results of other triple patterns contained in the same
query. An overestimation of such sources increases the network traffic, the number of
intermediate results and thus can significantly increase the overall query processing time
[
15
]. Join-aware TPWSS strategies have been shown to yield great improvement potential
[
1,15
]. For example, [
15
] can reduce the number of sources selection by approximately
47%. Still, there is a gap being between the optimal number of sources to select and the
number of sources selected by current approaches. In particular, join-aware approaches
based on authorities still fail to perform well on datasets where the same authorities are
distributed across a large number of data sources. The development of better approaches
for the characterization of data contained in single knowledge bases would further reduce
both the network traffic and the source selection time.
In addition, our survey suggest that desirable features of federation systems are still to
be addressed in literature. While approaches such as [
16
] allow approximating the recall
of incomplete query results, source selection approaches dedicated to the computation
of queries with LIMIT (approximately 17% of the queries in real query logs) remains
work in progress. Such approaches could however improve the runtime of federated
query processing further, as they would allow discarding sources that are capable but
unnecessary to compute k results to the query. Similar insights can be derived for other
SPARQL features.
2.2
Planning and Optimization
One of the most interesting results of the survey underlying [
13
] is that none of the
systems surveyed combined cardinality estimations with join-aware source selection
for planning. Devising an approach for computing more accurate join orderings can
potentially yield improvements of several orders of magnitude on queries with large
intermediate results. In addition, providing optimization of join implementations
depending on the query can also lead to improved runtimes. Furthermore none of the current
systems supports top-k queries according to the same study. However, approximately
1 http://lsq.aksw.org/sparql
2 The survey results are at https://goo.gl/bAfJJM.
17% of the queries available in the LSQ dumps use LIMIT. The provision of better
planners that make use of information contained in SPARQL features is hence yet another
opportunity for the development of more efficient federation systems. Static planning
approaches could derive more efficient plans by having to deal with less sources.
An area of research which has been paid little attention to within the setting of
federated queries is dynamic planning [
1
]. During the execution of federated queries, the
planner most commonly generates a plan, which is executed as is. Therewith, current
federation engines fail to make use of intermediary information they receive while
executing portions of the queries. For example, receiving small intermediary results
where large intermediary results were expected is a potent hint towards the subsequent
steps of the plan needing readjustment. New results on dynamic planning in other areas
of research such as link discovery [
9
] suggest that runtimes can be reduced by more than
80%. Approaches which can update their cost functions and therewith also their query
processing plan should lead to a new generation of SPARQL federation engines.
2.3 Integration
The role of the integration module is to gather result sets from the previous step and to
merge these result sets to the final result of the engine. Caching seems to be an obvious
solution to improving the runtime of federated queries. In particular, tailored caching
solutions have been shown to outperform generic caching approaches significantly (see,
e.g., [
7,10
]). However, non of the systems we surveyed rely on caching the intermediate
results when processing federated SPARQL queries. Thus, they were unable to reuse
information on highly recurrent queries. Providing novel caching methods for the
aggregation of results is thus one low-hanging fruit for future research. Another improvement
would be in the development of polymorphic implementation of joins. Being able to
choose the correct join implementation for merging the results gathered from a set of
SPARQL endpoints can potentially lead to further improvements of the overall runtime
of federated queries or even of triple stores.
2.4
Benchmarking
The main question that remains after composing a federated system is “how well does
the new approach perform”? A large number of benchmarks for SPARQL have been
devised over the last years [
2,3,6,8,17,18,14
]. However, only a few tackle federated query
processing. While LargeRDFBench3 is being used in a growing number of experiments,
the most popular federated benchmark is FedBench [
17
]. This benchmark consists of 9
datasets and 25 queries. A deeper look into this benchmark however suggests that the
queries it provised do not reflect real queries as found in query logs. For example, none
of FedBench queries uses ORDER BY, DISTINCT, REGEX or LIMIT. However, these
features are common in real queries. In addition, the average runtime of these queries
(approx. 2 s for [
15
]) makes the evaluation of the significance of runtime differences
between systems tedious to evaluate. We thus suggest that the queries in this benchmark
are not sufficient to carry out a thorough evaluation of the performance of existing
3 https://github.com/AKSW/LargeRDFBench
systems, especially when aiming to have an idea of their performance in real settings.
A look at the size of the datasets included also suggest that the benchmark has stopped
reflecting the complexity of the Data Web in which we currently live. The results of the
evaluation in [
13
] suggest that benchmarks for federated queries must:
1. SPARQL features. While FedBench queries do not use a large number of SPARQL
features (e.g.., LIMIT), LSQ clearly show that most SPARQL features are often
used in Web queries (e.g., LIMIT is used in approximately 17% of the LSQ queries).
We’d suggest including more queries into existing benchmarks that allow evaluating
the performance of existing systems for all SPARQL features.
2. Large data sources. A large number of the current data sources dispatch billions of
RDF triples. According to LodStats,4 144 SPARQL endpoints contain an average
of 1.03 billion triples. Reflecting these ever growing dataset sizes is of central
importance to implement the vision of realistic benchmarks that allow selecting the
right solution for a given problem.
3. Duplicated data. The distributed and decentral architecture of the Linked Data Web
leads to (1) data sources being duplicated or replicated (e.g., DBLP) and (2) portions
of datasets being duplicated across different endpoints (e.g., copies of DBpedia).
Modern federated benchmark must contain this characteristic of the Linked Data
Web to allow evaluating the performance of existing systems. That the presence of
duplicates can lead to different rankings in performance is shown in [
13
].
4. Complex queries. The largest query available in the LSQ dataset encompasses 37
triple patters. While the distribution of the number of triple patterns is a long-tailed
distribution, this piece of information suggests that modern federation engines can
be confronted with very large SPARQL queries. Including such queries into existing
benchmarks would ensure a better and more realistic assessement of SPARQL
federation systems. With this requirement also comes the needs for the inclusion of
queries with large intermediary results and large result sets.
3