In recent years the core of the semantic web has evolved into a conceptual layer built by a set of ontologies mapped onto data distributed in numerous data sources, interlinked, interpreted and processed in terms of semantics. One of the central issues in this context became the federated querying of such linked data. This paper presents the federated query engine ELITE that facilitates a complete and transparent integration and querying of distributed autonomous data sources. To achieve this aim a combination of existing approaches for Ontologybased Data Access (OBDA) and federated query processing on Linked Open Data (LOD) is applied. Consolidating technologies like entailment regimes, the DL-Lite formalism, query rewriting, mapping relational data to RDF and an improved implementation of R-Tree based indexing contributes to the unique features of this federation engine. ELITE thereby enables the integration of various kinds of data sources, for example as relational databases or triple stores, simplicity of query design, guaranteed completeness of query results and highly e cient query processing. The federation engine has been developed and evaluated in the domain of carbon reduction in urban planning.
Due to initiatives like Linking Open Data (LOD) [
Systems and methodologies for federation of linked data, that are basically
stored in RDF triple stores exposing a SPARQL service, belong to the rst
category. Federation is one of three main paradigms for the design of a linked data
infrastructure identi ed by Gorlitz & Staab [
The approaches of the second category aim at building a service tending to present a conceptual view of the domain of discourse formulated in terms of an ontology that is univocally mapped onto the data layer. Clients accessing the service don't have to know how the data layer is organized, formatted, and structured. They formulate semantic queries referring to the ontology and hence, to the native vocabulary of the domain of discourse. The conceptual view typically consists of the ontology TBox only. There is no need for storing ABox individuals since semantic queries are translated in runtime into the query language (usually SQL) and are comprehensible for the data sources comprising the data layer. Furthermore, application of formalisms designed especially for OBDA purposes facilitates e ective query rewriting e.g. from SPARQL into SQL, and therefore high e ciency of query evaluation ensuring sound and complete query results. However, since existing OBDA approaches focus on accessing (mostly non-RDF) data in relation to its semantics, they don't take into account sources that already provide RDF data via SPARQL interfaces like triple stores. [6{8]
The approach proposed in this paper consolidates the advantageous features of the two approaches described above and is free of their most signi cant disadvantages. It uses the conceptual view for the domain of discourse formally specied as ontology, in a way similar to the OBDA approach. The central ontology in turn is linked and mapped onto vocabularies of each single data source integrated into the federated infrastructure. However in contrast to OBDA systems our approach exploits query execution strategies described in federation approaches for linked data combined with reasoning applied centrally to each query launched by the client. Due to the described architecture the system guarantees completeness of query results and enables clients to operate on the vocabulary strongly related to the domain of discourse. Besides, the system supports highly e cient query processing by means of an improved implementation of R-Tree-based indexing. The proposed approach has been implemented and evaluated for the domain of carbon reduction in urban planning.
The document is structured as follows: After Section 2 containing a survey of related work we introduce the system architecture of our approach in Section 3. The implementation of entailment regimes through rewriting of SPARQL queries is described in Section 4. Subsequently, Section 5 presents an improved R-Treebased indexing. Before concluding this paper in Section 7 we discuss evaluation results in Section 6.
This paper is written for readers familiar with the paradigm of semantic web [
In order to achieve complete results on SPARQL queries not only the
explicitly speci ed data and its relations have to be taken into account but also
the knowledge that can be inferred by reasoning on the RDF graph. The de
nition of such extended interpretation on query evaluation is part of the proposed
recommendation of SPARQL 1.1 and is called entailment regimes. [
As stated in the introduction, ODBA is one of the approaches fundamental
to the work described in this paper. It enables a mapping of relational data to
ontologies and therefore access to this data by reference to its semantics. The
OBDA platforms {ontop{ [
Another approach strongly related to the present work focuses on facilitating
the infrastructure for linked data, and in particular on optimization of federated
SPARQL queries. One of the most complete surveys of this issue is given by
Gorlitz & Staab [
To our best knowledge at least six approaches exist that adopt various
techniques to overcome this limitation. For instance, the approach described by Vidal
et al. [
Despite our extensive studies and to the best of our knowledge none of the
existing approaches considers the complexity of reasoning and query answering.
Concerning this Calvanese et al. [
The proposed architecture has been developed with the goals mentioned in the introduction (Section 1). These are i) e cient query processing in particular complete evaluation of conjunctive federated queries, ii) ability for clients to formulate queries abstracted from the technological and structural characteristics of the data sources and iii) ability to federate data sources using di erent schemas, e.g. RDF triple stores and relational data base systems. One key feature of the proposed federative approach is the application of a single central ontology that on the one hand represents the vocabulary and knowledge structure of the domain of discourse and, on the other hand serves as a mediator for heterogeneous data sources. All queries formulated by a client and potentially targeting data distributed in single sources refer to this ontology. However the client is not constrained to use only the central vocabulary but is also able to use elements (e.g. concepts) of data source speci c vocabularies. The system architecture of ELITE is outlined in Fig. 1.
The central ontology (A in Fig. 1) is basically a TBox that comprises apart from own items, i.e. concepts, roles and axioms de ned in its own namespaces, items semantically related to the domain of discourse and speci ed in openly accessible vocabularies (B), e.g. those used in the LOD sources. The integration of such items into the central ontology is implemented by their linking through using RDFs or OWL properties. For instance by equating the concept ResidentialBuilding of the central ontology with the concept DwellingHouse of an external ontology (ResidentialBuilding DwellingHouse), or by subsumption of an external concept DwellingHouse (DwellingHouse v Building).
Such mapping and linking facilitate federated querying of related data sources
using their own vocabularies. Issues related to the design of the central ontology
are out of scope of this paper, we just would like to mention that the e cient
design of the central ontology is basically carried out manually, e.g. using a
dedicated process model, as it is described by Nemirovski et al. [
The proposed approach works for triple stores as well as for relational databases
under the condition that all integrated sources (C) provide a SPARQL-endpoint
to query data. For conversion of relational data to the RDF format RDB2RDF
tools like D2RQ and OBDA tools like {ontop{ are used. These tools are applied
locally for each source to map relational data to items of the central ontology as
it is shown for example by Poggi et al. [
The querying process starts when a query formulated by an external application or by a user is launched at the central SPARQL endpoint of ELITE (1). Elements of this query, e.g. basic graph patterns (BGP), refer to items of the central ontology and elements of other vocabularies linked to the central ontology as described above. In the rst step the initial query is rewritten (2) by means of entailment regimes, whereby the semantics of the central ontology as well as of the linked external ontologies are taken into account. The application of entailment regimes (described in Section 4) results in multiple queries re ecting all possible ways of expressing the same statement using the knowledge implicated by all considered vocabularies. The disjunction of evaluation results of these queries by each data source delivers the initial query result complete in terms of all considered vocabularies. Yet not all BGPs contained in these queries are relevant to all integrated sources. Therefore not all queries, more precisely its patterns generated through application of entailment regimes, can be answered by any sources. To avoid sending queries causing empty results, such queries are excluded from further processing by the index look-up procedure. In the next step (3) this procedure is applied for every single BGP in all queries to determine the sources which contain data related to each BGP. The index also delivers an estimated size of results that would be returned by each data source for each BGP (see Section 5 for a detailed description of indexing). Using estimated sizes and dependencies among patterns of each query, an optimized query execution plan is generated (4). After results to all pre-selected queries executed by preselected sources according to the previously generated plan are retrieved, the federated result is returned to the client that has launched the initial query (5). 4
In order to take knowledge inferred from persistently stored RDF triples in the
query execution process into account the implementation of such entailment
regimes can be done in three di erent ways. The rst technique is to
materialize all triples that are inferred according to the used entailment regimes e.g.
RDFS entailment regimes, that is also called forward-chaining. The alternative
technology is called backward-chaining. It operates by inferring of new triples
through query rewriting in runtime. The third option is a hybrid combination
of both approaches. These techniques (query rewriting and materialization of
inferred triples) are further described by Glimm [
Since in our approach the entailment is processed centrally, all inferable knowledge as well as all conceivable external concepts and properties referenced in the central ontology are taken into account in the patterns of the rewritten SPARQL queries. Therefore the federative system doesn't have to rely on the entailment of single data sources to guarantee the completeness of query results. Even if local SPARQL services of e.g. some RDB2RDF tools don't implement entailment regimes at all, the query results will be complete in terms of the central ontology. Yet the central query rewriting does not only help in cases when local SPARQL services are not (fully) support entailment. Furthermore, even though a SPARQL service of a single source implements the entailment regimes, it only can infer knowledge based on the vocabularies (ontologies) available at the corresponding source. If the central ontology that speci es the domain of discourse is not among these vocabularies, completeness of query results in terms of the central ontology can't be guaranteed based on local entailments only.
At this point we want to thank the developers of Quest who provided us with the source code of the system at our disposal. We extended it by implementing a translator to convert datalog programs, Quests internal rule representation of the rewritten queries into SPARQL queries by analyzing and inspecting the generated rules. As Quest contains various rewriting implementations we have chosen the Tree Witness Rewriter implemented by Kontchakov et al. [50{52] because the authors have shown that this rewriter produces better evaluation results than to other ones. Assuming for example that the TBox of the central ontology contains the following statements (namespace speci cations are omitted):
(1)
The distributed sources DSA(2) and DSB(3) contain the following data (ABox):
ResidentialFloorArea(Hundertwasserhaus3356) :Hundertwasserhaus :hasResBuildingFloorArea :Hundertwasserhaus3356 :Hundertwasserhaus3356 :hasValue 3356.0^^xsd:decimal :Casa_Mila :hasResBuildingFloorArea :Casa_Mila1000 :Casa_Mila1000 :hasValue 1000^^xsd:decimal q(building) :- hasResBuildingFloorArea(building, ) q(building) :- Building(building) q(building) :- CommercialBuilding(building) q(building) :- hasBuilding_Floor_Area(building, ) q(building) :- ResidentialBuilding(building)
These programs can be rewritten accordingly as SPARQL queries that have to be federated. To get all oor area values of all buildings the user only has to de ne the following query:
?building :hasBuilding_Floor_Area :bfa .
:bfa :hasValue ?buildingFloorArea . g
It is important to notice that in a case when entailment regimes are not implemented at SPARQL services, neither centrally nor locally, it is the task of the client to formulate the query in a way that makes sure that all related RDF graph patterns are taken into account. For this purpose the client has to be aware of all formal vocabulary structures her/his query refers to, and the semantics that can be applied to these vocabularies. Consequentially the complexity of queries and of client applications would increase signi cantly. For instance, the query for selecting all oor area values of all buildings (6) would look like this:
(3)
To get all buildings the user only has to de ne the following query:
After entailment by query rewriting we get the following datalog program:
f ?building :hasBuilding_Floor_Area :bfa . g
f ?building :hasResBuildingFloorArea :bfa . g :bfa :hasValue ?buildingFloorArea . g
Since a query may address complex relations across several data sources it is not unusual that a single source is only able to answer a part of the query. However the complete query can't be forwarded to a source that is not able to deliver results for each query pattern and hence would return an empty result set. Instead, the federation engine has to identify relations between data sources (4) (5) (6) (7) and query patterns, to generate, based on these relations, dedicated sub-queries and forward them to corresponding sources. To select all sources relevant to each single part of a query an index catalog implementing a look-up service and able to estimate the size of the sub-query results of each source is required.
A comparative analysis of currently available indexing methods for distributed
RDF data can't be provided in this paper due to space limitations. For a survey
of the state of the art we point out the work of Gorlitz & Staab [
Similar to PARTree our approach follows the strategy to index each single data source independently but in contrast to PARTree it uses more ne-grained partitioning of RDF triples. A systematical representation of the described index architecture is shown below in part (A) of Fig. 2. The index partitions are identi ed by the hash value of the predicate's URI (phash), the hash value of the pre x - more precisely the namespace - of the subject (s pre xhash) and object (o pre xhash) and additionally by the type of the subject (s typehash) and object (o typehash). In this context the type of a particular ABox individual is de ned as the URI of the TBox concept connected to the individual by the rdf:type relation. For the last triple of the assertion below the type of the subject Hundertwasserhaus would be ResidentialBuilding:
If no type of an individual can be derived the assigned hash value for s typehash or o typehash is 0. Since the rdf:type for TBox elements does not exist, this would be also the case for the objects in type assertions like the rst two statements of the example above. Using this ne-grained segmentation for triple partitions leads to more accurate results compared to QTree as well as PARTree and therefore to a more exact data source selection as well as more precise result estimations. For type assertions like e.g. the rst one shown in (8) the described segmentation results in an one-dimensional index structure, because the type URIs of the predicate and the object as well as the namespaces for the subject are unique in each partition.
Calling the index look-up service for a BGP results in selections of MBBs for each source containing triples tting to this pattern. For this purpose the corresponding hash values are calculated for all pattern elements de ned by an URI and all found MBBs of each source are returned. For instance two BGBs that are connected with the same subject variable, estimated results can be calculated by joining the spatial results (MBBs). A graphical representation of this example is given in part (B) of Fig. 2.
Besides the partitioning another main di erence to PARTree and QTree is that our index isn't held in main memory but instead stored in a spatial database. Due to this solution we bene t from the optimized features of spatial database systems to manage spatial objects, to perform spatial operations like joins and to achieve high scalability of the index. To ll the index with summarized data of each data source we crawl them through to SPARQL queries specially constructed for this purpose. 6
The goal of our evaluation was to prove the completeness of query results
generated by ELITE, and furthermore to demonstrate that conventional systems,
which neither use query rewriting techniques nor apply materialization of
inferred data aren't able to deliver comparable results. To evaluate ELITE we
have used part of an ontology developed for the SEMANCO project [
Since none of the six strongly related approaches mentioned in Section 2 are publicly accessible we have compared ELITE to available state of the art federation systems with respect to completeness of query results. For evaluation purposes several data sets containing data properties of individuals speci ed within the selected ontology have been distributed over two data sources. Utilizing D2RQ we mapped the relational data to the appropriated ontology elements.
Using this infrastructure a comparative evaluation with the FedX system for federation of distributed data has been carried out. As stated in Section 4, query results generated by D2RQ using FedX only take into account data de ned explicitly by the D2RQ mappings. This hypothesis has been con rmed by the evaluation results. Since inference has been carried out neither by local installations of D2RQ nor by FedX, no other matches to the query patterns originally submitted have been identi ed. In contrast to this, caused by the implemented entailment by query rewriting, ELITE has delivered complete results taking into account all implicit knowledge. As expected, evaluation results (Table 1) demonstrate that ELITE provides an e ective method for entailment-based federated query processing and delivers complete results when other systems fail. This paper introduced the federated query engine ELITE that enables querying of linked data distributed over a set of autonomous data sources. Application of entailment regimes by query rewriting facilitates completeness of query results in terms of a central ontology that represents a native vocabulary of the domain of discourse. By the ability to generate complete query results regardless of the SPARQL endpoint features supported by integrated data sources, ELITE has an outstanding position compared to other federation approaches. Beside that this paper elucidated an improved implementation of R-Tree based semantic indexing. This technology and application of the DL-Lite formalism for ontology design are crucial in relation to high e ciency.
Our next steps towards further improvement of ELITE characteristics will be the implementation of a query execution plan, optimization and identi cation of alternative techniques for federated querying. A further purpose is the proof of soundness of query results that are delivered by the rewritten queries. Since in this paper we only have described the evaluation results concerning completeness of query results, our future target will be the evaluation of e ciency. We will evaluate selected benchmarks and try to quantify the contributions of particular technologies to the e ciency of query processing. Acknowledgments. We thank Dr. Mariano Rodr guez-Muro for providing us the source code of Quest as well as for supporting. The main contribution of this work has been developed within the SEMANCO project, which is being carried out with the support of the Seventh Framework Programme \ICT for Energy Systems" 2011{2014, under the grant agreement no. 287534.