Decentralized infrastructure for knowledge discovery in the Semantic Web

2.1 RDF data access

RDF data is distributed across the Web, thus making it difficult to seek, query and consume. Triples are freely available via standard HTTP GET mechanism or stored in datasets equipped with SPARQL endpoint. These sources are frequently disconnected, leading to the so-called data islands. There are four general approaches to this problem. Navigational [1, 37] mimics the way we browse the Web exploiting graph nature of RDF and cross-linking RDF graphs. Navigating does not require any additional structures supporting data collection; however, the collected data is heavily dependent on a starting point selection. This technique is implemented in semantic browsers, Tabulator [4], Disco [5], DBpedia Mobile [2]. Warehousing [9, 39] is another approach originating from database theory, where heterogenous data needs standarization and schema unification prior to being queried. It assumes collecting and loading entire datasets into central repository, thus enabling efficient query evaluation. This approach, however, suffers from data redundancy which raises problems with scalability and data becoming obsolete. Semantic Web search engines SWOOGLE [13], Sindice [29], SWSE [18], Falcons [8] crawl the Web and index RDF documents much like traditional search engines. They collect RDF documents, create centralized indexing structure and enable keyword-based search exploiting classic information retrieval methods. Since they are not resource-oriented, the support for structural or semantic querying is limited only to metadata and search results refer to RDF documents rather than RDF resources. Federation [16, 17] is oriented towards structural query evaluation across multiple data sources on the Web. It derives from database researches on distributed query processing [21] and assumes a role of a mediator which splits the query into subqueries which are then delegated to different endpoints. Mediator collects and merge intermediate results to obtain final result set for the query. SPARQL 1.1 [31] has built-in support for federation implemented as a SERVICE clause. Two examples of federated SPARQL system are DARQ [32] and SemiWIQ [22].

2.2 Semantic integration

Web ontologies determine terminological layer for RDF triples, so they constitute the semantics both for datasets and for query. Ontologies, even if shared and reused, introduce heterogeneity on a semantic level. Fruitful knowledge discovery in the Semantic Web requires alignment of miscellaneous ontologies used to describe RDF data. Ontology matching is a wide topic including a variety of methods that can be split into categories regarding matching objective and human involvement. Ontology merging and integration produce new ontology which may be significantly altered in a deep reengineering process requiring extensive human involvement. Mapping and alignment of ontologies are considered more lightweight and better fitting Web’s reality. A potentially incomplete mapping between Web ontologies, (semi-)automatically computed and represented without affecting their autonomy is believed to be particularly suitable to aid semantic alignment. [10, 35] provide a comprehensive survey on ontology matching. Another important aspect is the representation formalism that determines mappings’ expresiveness and ways they can be exploited. Formal and logic-oriented approaches [14, 28] consider the interpretation of logic concepts across different ontologies, first-order formulas for cross-ontological translations and upper ontologies for schema mediation. Query language level approaches [11, 34] propose various extensions for SPARQL to evaluate queries in one ontology over data expressed in another. A great deal of attention is dedicated to query rewriting strategies and algorithms. Lightweight mapping representation tools are represented by Alignment API [12], R2R [6], BLOOMS [19].

3.1 Architectural extensions

We follow common distinction between terminological data (TBox), namely ontologies, and assertional data (ABox) stored in RDF datasets, usually of much higher volume. Dereferenceability of ontology IRI and availability of ontology document including its metadata, is not only stipulated by Linked Data design recommendations but also required by OWL2 specification [27]. It renders a basis for additional annotation of owl : Ontology concept (owl, rdfs and rdf are abbreviations for standard namespaces of those vocabularies) regarding new services necessary to facilitate query federation. Two annotations are defined and illustrated in Figure 1.

Definition 1. (IndexingServiceAnnotation). Annotation is defined as a set of axioms:

IndexingService : owl:Class

hasIndexingService : owl:AnnotationProperty

⊤ ⊑   ∀ hasIndexingService.IndexingService

∃ hasIndexingService.Thing ⊑ owl:Ontology

Definition 2. (MappingServiceAnnotation). Annotation is defined as a set of axioms:

MappingService : owl:Class

hasMappingService : owl:AnnotationProperty

⊤ ⊑   ∀ hasMappingService.MappingService

∃ hasMappingService.Thing  ⊑ owl:Ontology

OPEN IN VIEWER

Fig.1

Indexing and Mapping annotations.

Conceptually, five separate logical nodes in the network infrastructure can be denoted. Each of them exposes a service which, along with ontology annotation, facilitates discovery protocol.

Ontology Repository Node. ORN node is responsible for hosting ontologies and serving ontology documents via HTTP GET mechanism. The ORN implementation is based on standard HTTP server, since terminological datasets are small in comparison to assertional data. Every hosted ontology has at least one IndexingService annotation and one MappingService annotation, pointing at ISN node and MSN node, respectively.

Indexing Service Node. ISN node stores index entries linking ontologies with RDF datasets and providing additional metadata information to improve the process. The basic index entry takes form of a couple (IRI _TBox , URL _SEndpoint ), where IRI _TBox is an identifier of ontological concept and URL _SEndpoint is an address to the SPARQL Endpoint which provides triples containing IRI _TBox . The actual index entry is more elaborate, but it is of less importance at this point. The ISN node provides information about index entries for TBox concepts in terms of getDataSources(IRI _TBox ) service.

Mapping Service Node. MSN node stores mapping entries between TBox elements in different Web ontologies. The expresiveness of mappings regards named concepts, both classes and properties, which can be related by means of standard description logics equivalence and inclusion. ( class equivalence ) C 1 ≡ C 2(1) ( class inclusion ) C 1 ⊏ C 2(2) ( property equivalence ) R 1 ≡ R 2(3) ( property inclusion ) R 1 ⊏ R 2(4) The basic getMappings(IRI _TBox ) service returns URIs of all concepts TBox _i , both classes and properties, which satisfy ∀i TBox _i  ⊑ TBox.

Data Repository Node. DRN node is merely an RDF dataset repository equipped with standard SPARQL endpoint. The service can be implemented with any existing SPARQL server and is supposed to handle large volumes of RDF data.

Querying Service Node. QSN node orchestrates all other services to accomplish the scenario according to the discovery protocol. It does not store any data itself, but calls on other nodes, thus playing the role of mediator in federation system.

These elements form the infrastructural basis for looking up the data sources necessary for query rewrite and execution.

Following the distinction between TBox and ABox data, the evaluated query is considered to be an ABox query according to definition 3. Let V be the set of variables, L be the set of literals, I _TBox be the set of terminological IRIs of any ontology excluding common vocabularies for OWL, RDFS and RDF, I _ABox be the set of any assertional IRIs.

Definition 3. (ABox Query). SPARQL query Q _ABox is an ABox query ⇔ ∀ tp ∈ BGP : tp ∈ V × ({rdf : type}) × (I _TBox ) ∪ (I _ABox  ∪ V)  × (I _TBox  ∪ {owl : sameAs, owl : differentFrom})  × (I _ABox  ∪ V ∪ L) where tp and BGP stand for triple pattern and Basic Graph Pattern of the query, respectively.

Definition 3 entails five types of a triple pattern. TP _i is a shorthand for triple pattern of type i.

Type 1 (V, rdf : type, I _TBox ): tp = (s, p, o), where s ∈ V, p ∈ {rdf : type}, o ∈ I _TBox .

Type 2 (V ∪ I _ABox  ∪ L, I _TBox , V ∪ I _ABox  ∪ L): tp = (s, p, o), where p ∈ I _TBox , (s ∈ V ∧ o ∈ I _ABox  ∪ L) ∨ (s ∈ I _ABox  ∪ L ∧ o ∈ V).

Type 3 (V, I _TBox , V): tp = (s, p, o), where p ∈ I _TBox , s, o ∈ V.

Type 4 (V ∪ I _ABox  ∪ L, I _OWL , V ∪ I _ABox  ∪ L): tp = (s, p, o), where p ∈ {owl : sameAs, owl : differentFrom}, (s ∈ V ∧ o ∈ I _ABox  ∪ L) ∨ (s ∈ I _ABox  ∪ L ∧ o ∈ V).

Type 5 (V, I _OWL , V): tp = (s, p, o), where p ∈ {owl : sameAs, owl : differentFrom}, s, o ∈ V.

An immediate consequence is that there is at most one element of I _TBox in each triple pattern in Q _ABox and at least one element of I _ABox . Any variable is bounded by elements of I _ABox . According to the primary proposition, the initial ABox query carries no addressing elements, in terms of FROM or SERVICE clauses, and no background dataset or default graph is assumed either.

Having introduced architecture components and the input query defined, the scenario of ontology-based ABox query evaluation can be described. An overall protocol is presented in Fig. 2. The sequence diagram illustrates message passing between nodes depicting pieces of intermediary data collected in the evaluation process. An entry point for the querying agent is Query Service Node, which receives the input SPARQL query and starts the procedure in Algorithm 1 listing. Data sources discovery and query rewriting interleave in course of algorithm execution. First, the query’s BGP is extracted and a new one is initialized (lines 1-2). Next, all triple patterns are subsequently analyzed (lines 3-27). We are interested in TPs having a TBox element on predicate or object position, so only TP₁, TP₂ and TP₃ are further processed (line 4). TP₄ and TP₅ are appended to the new BGP untouched (line 24). From each triple pattern TBox IRI is extracted (line 6) and respective ontology is dereferenced by issuing HTTP GET request to this location. Then ontology hasMappingService annotation is consulted (line 7) and, after the respective Mapping Service Node is contacted, the set of mappings for TP TBox element is acquired (line 8). The new TBoxes extracted from mappings, along with source TBox form the basis for data sources search (lines 9-13). For each TBox set element, by dereferencing its IRI, the indicated ontology is loaded from respective Ontology Repository Node and hasIndexingService annotation is referred to (line 15). The IndexingService pointer enables a remote invocation to Indexing Service Node which returns data sources for a given TBox (line 16). At this point all addressing information required for query rewrite is in place. For each data source new SERVICE clause for a given endpoint and rewritten triple pattern is appended, thus creating a part of compound UNION clause which in turn forms a new expanded triple pattern (lines 17-20), appended to the new BGP in the target query. When all triple patterns are transformed the rewriting procedure stops. There is some important pre-and-postprocessing for the query with optimization in mind, elaborated in the next section.

The rewritten (and optimized) query is then executed by SPARQL engine being part of QSN implementation. Subqueries from SERVICE clauses are delegated to respective sources, intermediate results are joined on QSN and sent back to the querying agent.

Algorithm 1 An algorithm for ontology-based ABox query rewriting

Require: Non-addressing ontology-based ABox query

Ensure: Adressing ontology-based ABox query

1:  BGP← extractBGP (Q _ABox ) ;

2:  newBGP← initEmptySet () ;

3: for all (TP tp: BGP)do

4:  if (tp . getTpKind () in (1, 2, 3))then

5:   nTP← initNewTP () ;

6:   tbox← tp . getTBoxIRI () ;

7:   mServ← getMappingService (tbox) ;

8:   mappings← mServ . getMappings (tbox) ;

9:   tboxSet← initEmptySet () ;

10:     tboxSet . add (tbox) ;

11:   for all (Map map: mappings) do

12:     tboxSet . add (map . getTBox ()) ;

13:   end for

14:   for all (TBox tbox: tboxSet) do

15:     iServ← getIndexingService (tbox) ;

16:     DSs← iServ . getDataSources (tbox) ;

17:     for all (DataSource ds: DSs) do

18:       nTP . appendSERVICE (tp, ds, tbox) ;

19:       nTP . append (′UNION′) ;

20:     end for

21:   end for

22:   newBGP . append (nTP) ;

23:  else

24:  newBGP . append (tp) ;

25: end if

26:  newBGP . append (′ . ′) ;

27: end for

OPEN IN VIEWER

Fig.2

Query evaluation protocol

The already mentioned query preprocessing and postprocessing parts in Fig. 2 regard various optimization efforts undertaken to prepare the target query for efficient evaluation in distributed environment. In federation architecture the most expensive operation is connected with subquery execution on remote nodes, transmission the intermediate results over the network and join them on mediator. Therefore, it is crucial for performance reasons to ensure the intermediate results are as limited as possible and query planner on mediator supports smallest-first join order. The key factor is the selectivity of a triple pattern, Definition 4.

Definition 4. (Triple pattern selectivity). Let tp _x  = (s _x , p _x , o _x ) ∈ (I ∪ V) ³ be a triple pattern x and tp = (s, p, o) ∈ V³, where I is a set of IRIs, V is a set of variables. Selectivity S (tp _x ) is then S ( tp x ) = | eval ( tp ) | | eval ( tp x ) | where eval(tp) is a set of results of evaluation tp.

Roughly speaking, selectivity represents a capability of a triple pattern to restrict results. It can be estimated based on the triple pattern itself or it may take into account additional metadata carried by index entries. Both possibilities are considered in ActiveDiscovery query evaluation.

In preprocessing phase the FILTER expression is analyzed in the first place. The filter pushing strategy is applied by converting the filtering formula into conjunctive form. Any conjunct having its variables set contained in the TP’s variables set, is glued to the respective TPs as separate FILTER, so that they later can be pushed into one SERVICE call. Afterwards, initial reordering of the triple pattern is performed. TPs containing URI _ABox , namely TP₂ and TP₄, as well as TPs with glued FILTER clause are moved to the beginning of the BGP according to obvious heuristics. They become a seed of BGP. Next in line are TPs with variables shared with seeders, which narrows possible bindings for those TPs.

In postprocessing phase the reordering is augmented with the information about the cardinality of TBoxes. Basic index entry couple is extended to the triple (IRI _TBox , URL _SEndpoint , n), where n is a number of occurrences of IRI _TBox in data source exposed by URL _SEndpoint . The total number of occurences of IRI _TBox in all data sources URL _{SEndpoint i} discovered for this element is denoted as card ( IRI TBox ) = ∑ ( IRI TBox , URL SEndpoint i , n i ) n i(5) Cardinality supports an estimation of selectivity of triple pattern containing IRI _TBox . Lower cardinality implies fewer bindings on average, therefore relevant TPs take precedence in BGP order. However, a rule requiring TPs with bounded variables to occur prior to those with unbounded variables must be satisfied at all times. One way of subquery’s selectivity improvement is filter pushing. Another one is raising a number of triple patterns with shared variables to be pushed to remote endpoint within one subquery. This is possible whenever there are triple patterns addressed to the same endpoint which are not elements of any UNION clause at the same time.

To summarize optimization strategies applied, filter pushing and aggregating as many TPs as possible within one SPARQL SERVICE invocation improve selectivity and reduce network transmission by cutting off useless intermediary results. Reordering triple patterns based on heuristics and source statistics tend to significantly reduce resource consumption spent on mediator joins.

4.1 Validation example

Two ontologies are used to express the source query, presented in Listing 1, Schema.org¹ and Geonames² ontology. The query declares all cities in Poland with their names (labels) and population. It may be trivial, but still worth mentioning, that source query cannot be successfully executed unless it is explicitly submitted to the specific endpoint. First of all, a querying agent must know the address. If there are multiple endpoints it needs to make a decision which one to query, which leads to different results. Moreover, the data necessary to form the results may be split into various sources, which makes the task even harder.

For the purpose of the experiment, the ontologies’ namespaces need to be altered and ontologies themselves hosted accordingly. The reason for this is that they had to be augmented with relevant annotations regarding Mapping and Indexing Service. However, it does not affect the principles so original namespaces are used.

The annotation property has Mapping Service of Schema ontology points at node returning the following mappings dbpedia : City  ≡  schema : City

dbpedia : country  ⊑  schema : location

which extend the query in a way that DBpedia ontology³ is used in a query as well. Index entries for all TBoxes in question are collected in Table 1 as they were returned by Indexing Service Nodes for three ontologies. Two endpoints are available (ff.net is a shorthand for factforge.net). Cardinality measures reflect real world numbers for TBoxes occurrences in both sources.

The source query submission to either DBpedia endpoint or Factforge.net endpoint returns no bindings. Translation of the query and optimization-oriented transformation produce target query presented in Listing 2. The target query executed on Query Service Node returns 39 bindings of which 31 bindings are distinct due to the fact that Factforge aggregates data from multiple sources, DBpedia included.

The scalability of the ActiveDiscovery architecture is measured in terms of execution time of a rewritten query Q as a function of database size, for different Q, varying in size (triple patterns number) and selectivity. T = f Q ( S )(6) where T is execution time in ms of already rewritten ABox query Q and S is a total number of triples in all sources contributing to the result set of the query. Duration time of translation process itself can be neglected due to its low time cost in comparison to execution time.

The goal of the experiment is to figure out a shape of f _Q for increasing size of RDF datasets. Four different queries have been examined:

Q₁ consisting of 7 triple patterns of low selectivity,

OPEN IN VIEWER

Fig.3

Execution time of test queries.

RDF triples generator was used to produce twelve datasets of different size for measurement, starting from 38 triples in the smallest dataset it doubled each time reaching 77824 triples in the largest. Each dataset was uniformly distributed on four separate DRN nodes. Evaluation methodology was to take 100 samples for each setting of dataset size and query type, cut off 10 highest and 10 lowest results and take an average of others. The results for each query are presented in Fig. 3. Logarithmic scale for both axes has been used to clearly show all average measures.

The first and most significant observation is the linear growth of f _Q for all queries. The difference in execution time between queries is constant and depends on the query type. The much smaller Q₄ outperforms the biggest Q₁ by factor cca 24 while Q₂, equal in size to Q₁ but more selective, performs 4 times faster. It is important to note that these results cannot be meaningfully compared to the performance of a single query engine which provides measure of central query execution rather than distributed execution against multiple endpoints.