The aim of the Semantic Web and Linked Data principles is to create a web of data that can be processed by machines. The web of data is seen as a single globally distributed dataset. During the years, an increasing amount of data was published on the Web. In particular, large knowledge bases such as Wikidata, DBPedia, LinkedGeoData, and others are freely available as Linked Data and SPARQL endpoints. Exploring and performing reasoning tasks on such huge knowledge graphs is practically impossible. Moreover, triples involving an entity can be distributed among di erent datasets hosted by di erent SPARQL endpoints. Given an entity of interest and a task, we are interested into extracting a fragment of knowledge relevant to that entity, such that the results of the given task performed on the fragment are the same as if the task was performed on the whole web of data. Here we propose a system, called KRaider (\Knowledge Raider"), for extracting the relevant fragment from di erent SPARQL endpoints, without the user knowing their location. The extracted triples are then converted into an OWL ontology, in order to allow inference tasks. The system is part of a - still under development - framework called SRL-Frame (\Statistical Relational Learning Framework").
The aim of the Semantic Web and Linked Data principles [
Published data is generally available as data dumps, Linked Data documents, Triple Pattern Fragments or SPARQL Endpoints. Moreover, according to the Linked Data principles, triples involving an entity can be distributed among di erent datasets. All this data constitutes the web of data, that can be seen as a single globally distributed dataset.
Due to its sheer size, it is di cult to explore or perform complex tasks such
inference tasks (e.g. inconsistency checks) on the whole Web of data. Reasoners
like Pellet [17], Hermit [16] and BUNDLE [
In this paper we propose a system, called KRaider (\Knowledge Raider"), for extracting the relevant fragment from di erent SPARQL endpoints, without the user knowing their location. The extracted triples are then converted into an OWL ontology, in order to allow inference tasks. The system is part of a still under development - framework called SRL-Frame (\Statistical Relational Learning Framework").
The paper is organized as follows. Section 2 provides an overview of the main interfaces used to obtain knowledge from the Web of data. Section 3 illustrates the problem of the extraction of the knowledge fragment relevant to an entity. Section 4 presents the system KRaider and the framework SRL-Frame. An evaluation of KRaider used in SRL-Frame is provided in Section 5. Finally, Section 6 draws conclusions. 2
In this section we provide a brief overview of the main paradigms and interfaces for publishing and querying Linked Data based on RDF triples:(i) data dumps, (ii) Linked Data Documents, (iii) SPARQL endpoints, and (iv) Triple Pattern Fragments.
In particular, for each interface, we illustrate how queries can be performed by clients and/or servers using the SPARQL language, which is the standard language de ned by the W3C for expressing queries on RDF triples.
Queryable by client data dump
Linked Data Documents (RDFa, JSON-LD)
Triple Pattern Fragments
Queryable by server SPARQL Endpoint generic request / restricted queries simple server / complex client high availability / high bandwidth specific request / unrestricted queries complex server / simple client low availability / low bandwidth on RDF triples, whereas a server that publishes data dumps or Linked Data Documents does not provide a way for executing queries, which is, instead, delegated to clients. Moreover, there exist hybrid approaches like Triple Pattern Fragments [20] that divide the query workload between servers and clients. 2.1
The easiest way to publish Linked Data is to upload to a server an archive (data dump) containing one or more les in an RDF syntax such as Turtle or N-Triples. The client downloads the data dump, extracts the contained les and processes them for performing queries.
The main advantage is that the server is easy to maintain and the requests received from clients can be easily handled, i.e. the complexity of the server is low.
However, this approach has several disadvantages. First of all, even if only few triples are needed, the client has to download the whole dump and a high bandwidth may be necessary. Second, if part of the data becomes outdated, the client has to download again the archive. Moreover, the cost for managing data can be very high for clients. For huge RDF graphs, the client is required to perform data-intensive tasks in order to answer queries.
Data centralization approaches aim at providing support for query execution
over a collection of RDF data harvested from several sources. LOD
Laundromat [
If a query service is provided, a data centralization system can provide fast responses. However, if the central repository server is not available, all the clients that rely on it are unable to function. Therefore, in order to avoid unavailability (and latency), clients still have to download the needed data dumps. Furthermore, even without any query service, the cost of maintaining a centralized repository can be very high. Finally, given the dynamic nature of Linked Data, the collected dumps may be outdated. 2.2
RDF triples are divided into several Linked Data documents organized by entity. Typically, each document de consists of triples related to the entity e identi ed by an URI, where the subject of the triples is that entity, i.e. de contains triples of the form (e, p, o).
These approaches follow the Linked Data principles by Tim Berners-Lee [
Linked Data documents can be represented in any RDF syntax. In particular, due to the popularization of REST architectures for web applications, an RDF format based on JSON, called JSON-LD was developed. Moreover, in order to reduce the e ort for producing documents, RDFa was proposed, which allows publishing Linked Data in HTML5 documents.
From the viewpoint of the server, the required cost to generate each document is low and the performances for responses can be high. Moreover, the same document can be reused by many clients, allowing the sever to apply cache reuse policies to reduce the response time.
In [8], Hartig surveyed the approaches to execute queries over Linked Data
documents. These approaches can be split into two main categories. One category
uses pre-populated index structures [19]. The other one performs link traversal to
dynamically discover data for answering the query [9]. Link traversal approaches
have usually long query execution times. However, they require less bandwidth
than data dumps and, unlike data dumps, the data used to answer the query
is up-to-date. The major drawback of these methods is that the completeness
of the answers with respect to a knowledge graph cannot be guaranteed [
The most straightforward way for a client to execute a SPARQL query is to send the query to the server and delegate the entire execution to the server, which sends the answer back to the client. A SPARQL endpoint enables the clients to execute queries on a dataset through HTTP.
Although allowing clients to submit arbitrary SPARQL queries leads to low bandwidth consumption and low client cost, the cost of processing the whole query server-side may be really high, for the server, in terms of CPU time and memory consumption. In fact, evaluating a SPARQL query is PSPACEcomplete [14]. Another disadvantage of SPARQL endpoints is that client queries are highly individualized. Therefore, caching the results does not lead to significant improvements.
In order to reduce the computational cost of evaluating SPARQL queries, many endpoints use fragments of SPARQL with less expressive power (and hence lower complexity), reduce the allowed query execution time and limit the number of rows that can be returned (for instance, the SPARQL endpoint of DBPedia [12] has a limit of 10,000 rows).
The idea of query federation is to answer queries based on information from many di erent sources. SPARQL 1.1 from the SPARQL W3C working group added the SERVICE operator to the language speci cation, which can be used for querying another remote SPARQL endpoint during query execution. 2.4
The Triple Pattern Fragment [20] (TPF) interface aims at reducing query execution costs by moving part of the execution workload from servers to clients.
A fragment consists of all triples that match a speci c triple pattern (plus metadata and controls). SPARQL queries are decomposed by clients into triple pattern queries, i.e. queries composed of a single triple pattern. The server is only responsible for providing solutions to triple patterns, i.e. providing the fragment of a given triple pattern query. The client is responsible of combining the obtained fragments by processing operators such as join, union and optional.
An example of a triple pattern is: dbpedia:Donald_Duck ?p ?o. The formal de nition of triple pattern is reported below.
De nition 1. Let V be the in nite set of variables, which is disjoint from the set U of all URIs and the set L of all literals. Any triple tp 2 (V [ U [ L) (V [ U ) (V [ U [ L) is a triple pattern.
Since queries received by a server are less speci c, it is more probable that the same fragment may be reused by multiple clients. Therefore Triple Pattern Fragments can exploit caching. This interface allows servers to maintain high availability and to scale to a much larger number of clients. However, it is not awless. First of all, this interface requires the maintenance of dedicated servers and clients. Moreover, the required bandwidth is much higher. In fact, a query is decomposed into multiple triple pattern queries leading to a large amount of data transferred between servers and clients. In order to overcome this issue, Hartig and Buil Aranda [10] proposed an extension of TPF that allows clients to send to the server bindings in the queries in addition to triple patterns. There exist hybrid approaches that combine SPARQL endpoints and Triple Pattern Fragments, in order to exploit the advantages of both paradigms [13]. 3
In [11], the authors de ned an approach to extract a knowledge fragment relevant
to an entity in order to perform a learning task. This approach is integrated into
DL-Learner [
In this paper, in order to enable the users to perform complex tasks such as inference on Linked Data, we propose KRaider, a system for discovering relevant knowledge fragments. The approach is similar to the one proposed in [11], but, unlike [11], it can extract knowledge from multiple SPARQL endpoints by using an approach inspired by Link Traversal methods [9].
Below we provide the de nition of desired knowledge fragment relevant to an entity.
De nition 2. The desired knowledge fragment Fe relevant to an entity e is the smallest fragment of the Web of data W (Fe W), such that a task involving entity e and performed on Fe, provides the same results as if the task was performed on W.
In other words, we want to extract a fragment that holds enough information and that is small enough to allow the e cient execution of various tasks.
The relevant fragment is extracted by recursively traversing the RDF graphs starting from an entity. The recursion depth is a parameter that can be set by the user and a ects the size of the extracted fragment.
The extraction algorithm starts from an entity e identi ed by an URI Ue, then extracts the triples that have e as subject, i.e. triples of the form (e, p, o). The recursion depth is decremented and the objects o of the obtained triples are used to extract additional knowledge until the user-de ned recursion depth is reached. In case p is equal to owl:sameAs, the recursion depth is not decremented. Moreover, if the object's URI Uo has a domain Do which is di erent from the domain of subject's URI, in the next recursive step, the SPARQL endpoint hosted by Do is also queried.
The object of the obtained triples are used to extract additional knowledge until the user-de ned recursion depth is reached. The fragment extraction process is shown in Figure 2.
owl:sameAs/owl:equivalentClass/ owl:equivalentProperty property DBPedia data.europa.eu
Wikidata entity starting entity In this section we provide the conceptual and some technical details about the framework used to extract the relevant knowledge fragment. The system that takes care of extraction of the knowledge fragment from SPARQL endpoints is KRaider, which is integrated into SRL-Frame, a framework under development written in Java and based on the OSGi technology. In particular, it uses Apache Felix as the OSGi implementation.
The architecture of SRL-Frame is shown in Figure 3. The framework provides some common libraries like SLF4J and Log4j for logging and OWL API for manipulating ontologies. KRaider is a bundle3 and a service of this framework. When SRL-Frame is launched, an instance of (an implementation of) KRaider is registered into the OSGi Service Register. Therefore, if another bundle wants to use a KRaider instance, it should check if there is one in the Service Register. The OSGi technology is useful to enable or disable services on the y. In fact, if for some reason the KRaider service was disabled (e.g. maintenance, replacement of the service with a better implementation), the client bundle does not nd KRaider in the Service Register and it simply does nothing.
The implementation of KRaider provides a factory for building new extractors (SPARQLEndpointExtractorFactory). An extractor is a component that extracts new triples from the Web of data. In particular, a SPARQL endpoint extractor is a component that can nd new triples by exploiting SPARQL 3 In the OSGi jargon a bundle is a module. endpoints. When an extractor is created, it is assigned to a new thread by a component called ExtractionManager, which manages the created extractors. In particular, it is responsible for the creation of new extractors, handles the extracted triples and assigns jobs to extractors (see subsection 4.2 for further details).
The ultimate goal of KRaider is to be able to use several types of extractors, each exploiting a di erent Linked Data interface. The service oriented philosophy of OSGi comes in handy to realize this. In fact, KRaider can check, at run-time, which extraction services are available and then choose the ones to use. However, at the moment, KRaider only contains a single type of extractor which is able to exploit SPARQL endpoints to obtain triples. No other kinds of extractors have been implemented yet. 4.2
Algorithm 1 shows the algorithm of ExtractionManager. Its interactions with the extractors are graphically summarized in Figure 4.
Given a recursion depth, an URI that represents an entity e, a list of available SPARQL endpoints and a triple queue as input, ExtractionManager extracts the domain from the given URI4 (line 7), creates the rst job, where a job is a quadruple of the form hUe; Oe; Se; Dei, where Ue is the URI of entity e, Oe is its domain, Se is the status, and De the recursion depth (line 8). The status can have four possible values: Available, Running, NotAnswerable and Complete. Then it checks if new extractor threads can be launched and listens for extractor requests.
When an extractor requests a new job (line 11), it also send the set of extracted triples and the job j that has just been completed (in the rst request the list will be empty and the completed job will be null). The extracted triples will be all those triples that have as subject the entity represented by the URI in job j.
If the extractor was able to extract new triples, it sends a requests where the computed job's status is Complete, otherwise it sends an empty set of triples and the computed job's status is NotAnswerable. Then the manager takes the rst available job, i.e. a job with status equal to Available, sends it to the extractor (lines 12-14) and sets the job status to Running . If there are no available jobs at the moment, the manager stops the extractor that performed the request.
When the manager receives a request from the extractor together with a nonempty set of newly extracted triples and the computed job is hUs; Os; Ss; Dsi, for each new triple of the form (s; p; o), if o is a named resource, it extracts the domain Oo from Uo and adds the following job to the job queue: hUo; Oo; Available; Doi In addition, if the domain Os is di erent from Oo, then it means that another SPARQL endpoint should be taken into account and the manager adds the 4 We assume that each domain corresponds to a SPARQL endpoint.
Algorithm 1 KRaider's ExtractionManager 1: function ExtractionManager(Ue, D, E, T ) 2: Input: URI representing an entity Ue 3: Input: max recursion depth D 4: Input: list of available SPARQL endpoints E 5: Input: triple queue T 6: Create job queue J 7: Oe ExtractDomain(Ue) 8: Enqueue job hUe; Oe; Available; Dei into J 9: do 10:
StartExtractors(J , E) . Start extractor threads according to available 11: jobs
T; j WaitRequests() . Listen to requests and receive from each extractor the set of triples T and the computed job j l DequeueAvailable(J ) Update l status to Running Send l to extractor Enqueue triples T into T for all (s; p; o) 2 T do if o is a named resource then
Oo ExtractDomain(Uo) if p 6= owl:sameAs then
Do = Ds 1 3. Dequeue available job 1. Create
Extraction
Manager 2. Request job Extractor 1 (a) First operations of KRaider.
4. Return job 3. Enqueue new jobs
Dequeue available job 5. Assign job 1. Request job
Send triples 4. Return
job Extraction Manager 5. Assign job 2. Enqueue new triples 6. Create Extractor 1
Extractor 2 (b) Dynamic creation of new extractors when new jobs are available.
Triple Queue (e, p1, o1) (e, p2, o2) 3. Return null Job Queue <Ue, Oe, Complete, De> <Uo1, Oo1, Available, Do1> <Uo2, Oo2, Available, Do2> 2. Dequeue available job 1. Request job
Send null
Extraction Manager
4. Stop Extractor 1
Extractor 2 (c) Termination of an extractor caused by the lack of available jobs.
Fig. 4: KRaider's fragment extraction process. following job (where Oo 6= Os):
hUo; Os; Available; Dsi Moreover, if p is di erent from owl:sameAs, the recursion depth is decreased Do = Ds 1, otherwise it is left unchanged (lines 16-29).
Finally, if there are no available jobs the algorithm terminates.
The algorithm SPARQLEndpointExtractor which extracts triples from a SPARQL endpoint is shown in Algorithm 2. The extractor gets as input a list of the SPARQL endpoints E and a job hUs; Os; Ss; Dsi. It checks if there is a SPARQL endpoint hosted by domain Os (line 5) In the list of the available endpoints E. If no such endpoint exists, it updates the job status to NotAnswerable (line 24) and request a new job to ExtractionManager (line 26). Otherwise, it queries the endpoint 3 times in order to obtain the list of URIs Uei (with i = 1 : : : n) of the entities which are the same as (owl:sameAs) or equivalent (owl:equivalentClass, owl:equivalentProperty) to Us (lines 8-19). Then it sends the following query to the endpoint (line 20: SELECT DISTINCT * WHERE { { <Us> ?p ?o . } UNION { <Ue1 > ?p ?o . } UNION ... { <Uen > ?p ?o . } } The triples that bind with the union of the triple patterns of the query are extracted. 4.3
Each extracted triple is added by ExtractorManager to a triple queue
(TripleQueue). Many reasoners like Pellet [17], Hermit [16] and BUNDLE [
The triples in TripleQueue are repeatedly dequeued by a converter (Triple2OWLAxiomConverter), which converts each triple into an OWL axiom and then enqueues the axiom into another queue called OWLAxiomQueue. This queue is consumed by OntologyManager, which annotates the OWL axioms with their origins, i.e. with the dataset from which an axiom was extracted, and enqueues them to an OWL ontology. Finally, if a timeout was reached or the triple queue doesn't contain any triples (that means that KRaider stopped), the converter and the ontology manager stop.
The conversion from RDF to OWL is performed by following the mapping
de ned by the W3C in [
. get from E the SPARQL endpoint that is KRaider OWL Axiom Queue Dequeue
Enqueue
Ontology Manager One of the main limitations of KRaider is that, at the moment, it cannot handle blank nodes: KRaider just ignores the triples that contain them. These nodes are important in order to convert RDF triples into complex OWL class expression or properties.
For instance, the OWL class expression 9hasChild:P erson corresponds to the following RDF triples: _:x rdf:type owl:Restriction . _:x owl:onProperty hasChild .
_:x owl:someValuesFrom Person . where :x is a blank node. These triples are ignored by KRaider. In the future we plan to make KRaider handle blank nodes.
After multiple executions, it could happen that triples about an entity were already been extracted. Therefore, in order to improve the performances, KRaider should exploit caching. This is also future work. Moreover, we plan to allow the user to de ne lters that should be used during extractions. 5
We evaluated KRaider used inside SRL-Frame by performing several knowledge fragment extraction tasks on three di erent entities and an increasing recursion depth. The tests were performed on GNU/Linux machine equipped with Intel Core i7-5500U CPU @ 2.40GHz with 6 extractor threads.
Table 1 reports the number of extracted axioms and the running time in seconds averaged over 5 executions of KRaider (inside SRL-Frame) for di erent entities and recursion depth settings. 6
In this paper we proposed KRaider, a system that extract triples from di erent SPARQL Endpoints. The extracted triples are then converted into OWL axioms by another component. All these systems are integrated into a framework called SRL-Frame, which is still under development. SRL-Frame is based on OSGi technologies, which allows the system to dynamically install and start new services, hence making the framework exible to changes.
KRaider's code is available as git repository at https://bitbucket.org/ machinelearningunife/kraider/, whereas the code of SRL-Frame is available at https://bitbucket.org/machinelearningunife/srl-frame/.
In addition to the directions for future work presented in subsection 4.4,
we plan to develop new type of extractors that exploit the other Linked Data
interfaces. In particular, in the immediate future, we plan to integrate
SPARQLLD [