Although the amount of RDF data has been steadily increasing over the years, the majority of information on the Web is still residing in other formats, and is often not accessible to Semantic Web services. A lot of this data is available through APIs serving JSON documents. In this work we propose a way of extending SPARQL with the option to consume JSON APIs and integrate the obtained information into SPARQL query answers. Looking to evaluate these queries as e ciently as possible we present an algorithm that produces \worst-case optimal" query plans that reduce the number of requests as much as possible. We also do a set of experiments that empirically con rm the optimality of our approach.
We extended the SERVICE operator to allow SPARQL to query Web APIs. We
call a query that uses this extended SERVICE a SERVICE-to-API query. We
assume the reader is familiar with the syntax and semantics of SPARQL 1.1 query
language [
The API responds with a JSON document containing weather information, say of the form {"timestamp": "24/10/2017 11:59:07", "temperature": 3, "description": "clear sky", "coord": {"lat": 56.79, "long": -5.02}} Therefore, to obtain all Scottish mountains with a favourable weather all we need to do is call the API for each mountain on our list, keeping only those records where the weather condition is "clear sky". One can do this manually, but this quickly become cumbersome, particularly when the number of API calls is large. Instead, we propose to extend the functionality of SPARQL SERVICE, allowing it to communicate with JSON APIs such as the weather service above. For our example we can use the following (extended) query: SELECT ?x ?l WHERE { ?x wdt:instanceOf wd:mountain . ?x wdt:locatedIn wd:Scotland . ?x rdfs:label ?l .
SERVICE <http://weather.api/request?q={?l}>{(["description"]) AS (?d)} FILTER (?d = "clear sky") }
The rst part of our query is meant to retrieve the IRI and label of the mountain in WikiData. The extended SERVICE operator then takes the (instantiated) URI template where the variable ?l is replaced with the label of the mountain, and upon executing the API call processes the received JSON document using an expression ["description"], which extracts from this document the value under the key description, and binds it to the variable ?d. Finally, we lter out those locations with undesirable weather conditions. tu
We proposed a way to implement the overloaded SERVICE operation on top
of any existing SPARQL engine. To do so, we partition each query using this
operator into smaller pieces, and evaluate these using the original engine
whenever possible. The answers given by the engine are extended with the results
provided by the APIs. A full speci cation can be found in [
But can we optimize this queries? We discover that for SERVICE-to-API queries the bottleneck are the API calls. This is mostly because HTTP requests are slower that disk access and its something that we cannot control. So if we want to evaluate queries as e ciently as possible we need to do the least amount of API calls as possible. Then, can we reformulate query plans to make sure we are making as few calls as possible?
What we did is to propose an algorithm that is optimal in the worst case. This
algorithm does not make more calls than the number we would need in the worst
case over all graphs and APIs of a given size. For matters of space we will not
explain all the algorithm and the proofs. The details can be found in [
Our algorithm is inspired by the optimal plan exhibited in [
Then we can think that a SERVICE-to-API query has the form Q = R1 |><| R2 |><| : : : |><| Rm. For the sake of presentation we consider that Rj (1 j m) can represent a basic graph pattern or a SERVICE-to-API pattern where its attributes are the variables of the basic graph pattern or the input and output variables of the API. Then, let A1; : : : ; An be an enumeration of all attributes (variables of SPARQL) involved in Q, in order of their appearance. Starting from Q, we construct a query Q = n, where the sequence 1; : : : ; n is de ned as: 1 =
A1 (R1) |><| : : : |><| A1 (Rm): i =
i 1 |><| A1;:::;Ai (R1) |><| : : : |><| A1;:::;Ai (Rm):
The idea is to process the query variable by variable. First we obtain the result of the intersection of all A1 from the BGPs, and then we extend such BGPs with the values obtained from APIs where their input is the attribute A1. Then we resolve the join for BGPs with variables A1 and A2 (considering the results of the previous iteration) and we extend the results with the output of the APIs with inputs A1 and A2. We continue this process until answer the query.
Our main result is the following. Take any SERVICE-to-API query Q, and
a database D. Denote by MQ;D the maximum size of the projection of any
relation appearing in Q over a single attribute in the database D. Furthermore,
let 2 (Q;D) be the AGM bound [
O(MQ;D 2 (Q;D)): 4
We wanted to give empirical evidence that the worst-case optimal algorithm of
Section 3 is indeed a superior evaluation strategy for executing queries that use
API calls. To construct a benchmark for SERVICE-to-API patterns we
reformulate the queries from the Berlin benchmark [
Results. The number of API calls done for each of the three versions of our algorithm are shown in Table 1. As we see, avoiding duplicate calls reduces the number of calls to some extent, but the best results are obtained when we use the worst-case optimal algorithm. We also measured the total time taken for the evaluation of these queries. Query times range from over 8000 seconds to just 0.7 seconds for the Vanilla version, and in average the use of WCO reduces by 40% the running times of the queries.
Q1 Q2 Q3 Q4 Q5 Q7 Q8 Q10 Q12 AVG
Vanilla 5332 77 5000 5066 2254 15 1 7 1 0% W/O Duplicates 4990 3 4990 4990 608 15 1 7 1 20%
WCO 2971 0 3284 4571 608 13 0 0 1 53% Table 1. The number of API call per query for each algorithm. WCO plans average 53% reduction in API calls. 5
In this paper we propose a way to allow SPARQL queries to connect to HTTP APIs returning JSON. We give an intuition of the syntax and the semantics of this extension, discuss how it can be implemented on top of existing SPARQL engines, show an sketch of a worst-case optimal algorithm for processing these queries, and show the usefulness of this algorithm in practice. In future work, we plan to support formats other than JSON, and explore how to support it in public endpoints.