The Deep Web is constituted by data accessible through dynamic Web pages requested through a Web interface. While Deep Web data sources have been usually modelled as relational in the literature, in many cases it is useful to export Deep Web data as Linked Data sets. In this context, processing queries poses some algorithmic challenges due to the inherent limitations of Deep Web sources which, requiring some inputs to be queried, function as services. In this paper we present a framework and a system to export Deep Web data as Linked Data sets. Further, we characterise a class of SPARQL queries that are executable directly, in spite of the limitations.
The Deep Web (also known as Hidden Web) [
New ways of exposing structured data have recently emerged, which allow the
composition of services for the creation of new integrated applications
(mashups [
On the other hand, the Linked Data approach is based on the idea that data can be delivered on the Web together with their explicit semantics, expressed by means of common vocabularies. Following the Linked Data principles, datasets should be made accessible through a SPARQL endpoint. Moreover, by using federated queries an agent is able to automatically integrate data coming from di erent sources thus creating a data space at a Web scale. Unfortunately, also the Linked Data approach comes with its drawbacks, among which we may mention: { The e ort in setting up a SPARQL endpoint is bigger than that of adopting a RESTful approach from service providers. Normally it is much easier to nd a JSON-based service than a LD-based one. { Programmers are usually more familiar with JSON services than with
SPARQL endpoints. { Service providers are usually not interested in exposing all the data they have; instead, they normally want to expose only a small portion of their data.
Based on the above points we can see that, while from the practical point of view the RESTful approach is the most e cient, if we look at the knowledge point of view the Linked Data paradigm represents a more suitable solution.
Actually, with JSON-LD this issue could be solved but this format is not widely adopted yet. https://www.w3.org/DesignIssues/LinkedData.html https://www.w3.org/TR/sparql11-federated-query/
Following the above observations, we built the PoLDo prototype system, which is able to export existing RESTful services, even third-party ones, as a SPARQL endpoint, thus making the underlying Deep Data sources part of the Linked Data cloud. Thanks to a con gurable query planner, PoLDo is able to break down a SPARQL query into a sequence of RESTful service invocations and to orchestrate di erent services to provide a correct answer to the posed query. Starting from the data it retrieves from services, PoLDo builds a temporary RDF dataset used to compute the result set for the original SPARQL query.
In PoLDo, we expose Deep Web sources as services according to the aforementioned intrinsic restrictions. Rather than limiting ourselves to relational Deep Web sources, we model sources as Linked Data with access limitations, that is, SPARQL access points that are only accessible with queries that contain a certain xed, ground (variable-free) pattern. This poses the problem of determining whether a query can be evaluated over a set of sources (in the form of SPARQL endpoints), while returning the complete answers, in the presence of the access limitations. For other queries, we can only expect to get partial answers. 2
In this section we present a model for Linked Data sources that expose Deep Web data, with their inherent limitations. We characterise a class of queries that can be evaluated non-recursively on the data, while returning the complete set of answers (as if they were evaluated in the absence of limitations).
We rst show how Deep Web sources are represented as relational data.
When dealing with databases with access limitations the relations can be
expressed using the proper access modes. In the case of RESTful services we
have the two access mode i and o (for input and output respectively) stating
that for all the tuples r(c1; : : : ; cn) 2 DB we have some of the arguments of
r mapped to the inputs of the service and some to its outputs. Following [
r1oio(Y; a2; X); r2ioo(X; a4; Z)
. This query can be processed by executing the services corresponding to the
relations r1 and r2 from left to right. Indeed, by invoking the rst service with input
c1 we obtain as output a set of pairs of constants of the type hc1; c3i, each
instantiating Y and X respectively, as a consequence of the fact that r1(c1; a2; c3) 2 DB
. For each such pair, the second value c3 is then used as input to invoke the
service corresponding to r2, thus obtaining as output a new set of pairs of the form
hc4; c5i. Among these pairs, due to the selection with a4 on the second atom of
the query, we are interested only in those such that c4 = a4. So this kind of query
is executable and retrieves a complete answer that contains all solutions to the
query over DB. Notice that if the query is not executable, in some cases it can
be executed from left to right by reordering the subgoals (atoms) [
r1oio(Y; a2; X); r2ioo(X; a4; Z); r3oio(Z; U; W ); we may not be able to compute all the answers. For example, the instance fr1(d1; d2; d3); r2(d3; d4; d5); r3(d5; d04; d6)g will provide the answer hd3i for q2, but such answer cannot be retrieved due to the limitations. In general, the answers q(D) to a query q on a database D (as computed if the data sources had no access limitations) is a superset of the answers ans(q; I; D) that can be actually retrieved through the access patterns, that is ans(q; I; D) q(D), where I is a set of initial constants available to start the extraction of data from the sources.
When considering Linked Data sets, the limitations of the HTML forms (or
others beyond the relational formalism) are re ected naturally as we explain
below. We refer to the formalisation of SPARQL in [
Data are in the form of triple patterns of the form hs; p; oi 2 (I [ B) I (I [ B [ L), where B is the set of blank nodes. We assume to have a partial relation on predicates, where (p1; p2) means that p1 and p2 have compatible domains; this can be speci ed by the rdfs:domain of an rdf:Property, but we are not going to expose this in detail in this preliminary paper. The fact that two predicates have compatible domains re ects the notion of abstract domain in Deep Web.
Basic graph patterns (BGPs) are sets of triple graph patterns of the form t 2 (I [ L [ V) (I [ V) (I [ L [ V) where I, V and L are the sets of IRIs, variables and labels, respectively.
In the context of integrating set of Deep Web data sources and answering
queries posed on a set of such sources as if it was a single database, we assume
to have a schema S = fS1; : : : ; Sng of Deep Web sources. Each source Si, with
1 6 i 6 n, is an access point that has associated a set i of triple patterns that
are called input triple patterns (ITPs). Intuitively, in order to query a source,
we need to use a SPARQL query that provides constants for the object (the
Analogously to [
To start our exposition, we assume that queries are of the form q = P1 and P2 and : : : and Pn, where, for all i s.t. 1 6 i 6 n, each Pi is a graph pattern query to be evaluated on Si. We do not di erentiate here between SELECT and CONSTRUCT query types. Now, we formalise the limitations on sources and we establish a criterion for determining queries that can be evaluated so that all answers are computed.
We consider a schema S = fS1; : : : ; Sng of Deep Web sources with access limitations = f 1; : : : ; ng. For each Si, 1 6 i 6 n, i is a set of input triple patterns (ITPs) of the form = hVs; p; Voi 2 V I V. Let D = fD1; : : : ; Dng be an instance for the schema S, where Di is the instance of Si, , for all i s.t. 1 6 i 6 n.
De nition 1.
(a) A triple pattern t instantiates an ITP = hVs; p Voi if = ( ) such that is a mapping and (Vo) 2 I L. Notice that in this case (p) = p. (b) A source S with a set of input triple patterns can be accessed with a BGP P if for each 2 , there is 2 P such that instantiates . 3
We now focus on queries that can be executed on an instance D according to the access patterns De nition 2. Let t1; t2 be triple graph patterns de ned as t1 = hW1; p1; V i; t2 = hW2; p1; V i, with fW1; W2g I [ L [ V and V 2 V.
(a) We say that t1 feeds t2 if (p1; p2), that is, p1 and p2 are compatible (notice that both triple graph patterns have the same variable as third element). (b) We say that t1 and t2 match if p1 = p2.
We now identify a class of queries of the form q = P1 and P2 and : : : and Pn that are executable from left to right, after ordering the graph patternss Pi, on an instance D for a schema S; we call such queries orderable in accordance with the relational terminology for queries under access limitations.
De nition 3. Let q be a query of the form q = P1 and P2 and : : : and Pn, posed on a schema S as previously de ned. q is said to be orderable if P1; : : : ; Pn can be ordered as Pi1 ; : : : ; Pin such that: (a) For every ITP 2 i1 , there is 2 Pi1 such that instantiates ; (b) For all j such that 1 6 j 6 n, for every ITP 2 ij , either (i) there is 2 Pij such that instantiates ; (ii) there are feeds ; (2) 2 Pij and 2 Pi` , witha 1 6 ` 6 ij and match.
1, such that (1)
Notice that this de nition is analogous to the same one in the context of relational data under access limitations.
Proposition 1. Every orderable query on a schema S of the form q = P1 and P2 and : : : and Pn can be executed on an instance D, after suitably ordering P1; : : : ; Pn, from left to right so that all answers q(D) are retrieved.
Proof (sketch). We know q can be ordered as in De nition 3; let us assume w.l.o.g. then that it is already ordered. It is easily seen that P1 can be immediately evaluated on D1. Then, for each j such that 2 6 j 6 n, Pj can be evaluated on Dj according to j because every ITPs of j is either (1) instantiated by some BGP in Pj or (2) instantiated by a triple pattern 0, obtained from 2 P`, 1 6 ` 6 j 1 (as per De nition 3) by replacing its third element with the values of the third element of ( ), where 2 P`, for every mapping resulting from the evaluation of P` on D`.
P1
P2 1 2 p2 ?X p1 ?W a p3 ?Z
Y p2
?X Example 1. Consider the query P1 and P2, where P1; P2 are as in Figure 1 (we omit variables that appear only once), on a schema S = fS1; S2g with 1 = f 1g, 2 = f 2g, where 1; 2 are again as in Figure 1. The query q is processed by evaluating P1 on S1 directly and then, for all values v obtained by mapping ?X in the evaluation of P1, by evaluating P20 (see gure), obtained by replacing ?X with v in P2. 4
PoLDo In this section we brie y present the architecture of PoLDo, a prototype that processes queries over distributed Deep Web sources that are exposed as Linked Data sets.
The high level architecture of PoLDo is shown in Figure 2. The engine is responsible of getting the SPARQL query and breaking it down to a sequence of RESTful calls to a remote service. The transformation is made possible thanks to a mapping le that maps Linked Data URIs to the elements of the signature of the remote call. While querying the remote service, PoLDo feeds an RDF local triple store (Jena Fuseki, in its current implementation) which is in charge of processing the actual SPARQL query. More speci cally, in our system we have the following components and models.
PoLDo engine The engine accepts the SPARQL query and extracts all the constants from the graph template in the WHERE clause. Then, by using the algorithm sketched in Section 3 , it uses the constants to query the external service and to get the data that will be used to create a local RDF representation of the data space. Thanks to the information encoded in the PoLDo mapping le, the engine is able to feed a local repository of RDF triples. The engine is also capable to exploit external services to get extracted resources' URI from mapped API services, that often return data related to the resource but not the URI.
Jena The Jena Model is used to save a Linked Data version of the data which are incrementally retrieved from the RESTful service. The availability of a third-party RDF model makes PoLDo able to support the full speci cation of SPARQL query language. Furthermore, it is able to return the data in all the formats supported by the query engine Jena ARQ.
PoLDo Mapping Generator The Mapping Generator is responsible for the generation of the mapping le. Given a RESTful service, it works in four steps. It analyzes request (HTTP GET) and response (JSON or XML) given to and by a web service, then extracts all the inputs and outputs. The user is then allowed to manually assign a class of membership to resources. The Mapping Generator queries the ontologies (DBpedia and LOV, in our rst experimentation) and recommend how to link resources. After user con rmation, the nal mapping le is generated and can to be used by the engine. PoLDo mapping le This le contains information about how to map the URIs of the SPARQL query to inputs and outputs of the services. It also describes the access patterns as represented in Section 2 as well as their mutual relations (that is which triple graph patterns feed each other).