Efficient approximation in DL-Lite of OWL 2 ontologies

Abstract

Ontologies, as a conceptualization of a domain of interest, can be used for different objectives, such as for providing a formal description of the domain of interest for documentation purposes, or for providing a mechanism for reasoning upon the domain. For instance, they are the core element of the OntologyBased Data Access paradigm, in which the ontology is utilized as a conceptual view, allowing user access to the underlying data sources. With the aim to use an ontology as a formal description of the domain of interest, the use of expressive languages proves to be useful. If instead the goal is to use the ontology for reasoning tasks which require low computational complexity, the high expressivity of the language used to model the ontology may be of hindrance. In this scenario, the approximation of ontologies expressed in very expressive languages through ontologies expressed in languages which keep the computational complexity of the reasoning tasks low is pivotal. In this work we present our notion of ontology approximation and present an algorithm for computing the approximation of OWL 2 ontologies by means of DL-Lite TBoxes. Moreover, we provide optimization techniques for this computation, and discuss the results of the implementation of these techniques.

-

Ontologies, as a shared conceptualization of a domain of interest, are commonly recognized as powerful tools in support of the information systems of organizations [ 6,4,10 ]. On one hand, they can be used for providing a formal description of the domain of interest, and thus represent valuable documentation for an organization. On the other hand, they provide a mechanism for reasoning upon the domain with different objectives. For instance, they are the core element of the Ontology-Based Data Access (OBDA) [ 13,4 ] paradigm, in which the ontology is utilized as a conceptual view of the underlying data sources, granting the user the ability to retrieve information without specific knowledge on how this information is organized and where it is stored.

With the aim to use an ontology as a formal description of the domain of interest, the use of expressive languages, such as the OWL 2 Web Ontology Language [ 9 ], proves to be useful. The expressivity of such languages allows the ontology designer to obtain a precise formalization of the domain. If instead the goal is to use the ontology for reasoning tasks, the high expressivity of the language used to model the ontology may be of hindrance. In particular, when wishing to access large quantities of data through the ontology, as in OBDA, the computational cost of very expressive languages such as OWL 2 is prohibitive. In these cases, it is necessary to recur to less expressive languages, thus resigning to having less complete representations of the domain of interest.

One possible solution to this issue is to allow the ontology designer the use of expressive languages to define ontologies that model the domain in great detail for the purpose of documentation and of other tasks that do not require strong computational effort, while adopting, for all those reasoning tasks in which particular computational properties are required, such as OBDA, descriptions of the domain of interest obtained through less expressive languages.

Following this approach, the notion of approximation becomes pivotal. The goal of approximation is, given a ontology O in a language L, to compute an ontology O0 in a target language L0, in which as much as possible of the semantics of O is preserved. In general, various approaches can be adopted towards this goal [ 17,14,12,18,3 ]. Among these, the approaches in which we are most interested are those which aim to obtain the so-called semantic approximation [ 14,3,12 ]. Here, as opposed to those approaches which aim at a syntactic approximation [ 17,18 ], the computation of the ontology which is the approximation of the original one is obtained through the semantics of this original ontology, and not only through its syntactic representation.

In this paper, we focus on the semantic approximation of an ontology for OBDA applications. Thus, we study approaches for approximating ontologies in very expressive languages with ontologies in languages that, characterized by low reasoning complexity, are suitable for query answering purposes. The most significant works in which this problem is studied are [ 12 ] and [ 3 ], in which the proposed approaches can be traced back to the work of Selman and Kautz [ 14 ].

These approaches, as is ours, are based on the notion of entailment set. Given an ontology O in a language L, the entailment set of O in a target language L0 is the set of all the assertions expressible in L0 over that are entailed by O. The idea behind our approach is that an approximation in L0 of O is an ontology O0 whose entailment set minimally differs from the entailment set of O in L0.

Since OWL 2 is the W3C standard language for expressing ontologies, it is often used as the expressive language for formulating ontologies describing the domain of interest. On the other hand, in the context of OBDA, one naturally focuses on the logics of the DL-Lite family [ 5 ]. This is a family of DLs specifically designed to keep all reasoning tasks polynomially tractable in the size of the data, and is thus suitable for OBDA. For this reason, in this work we study the problem of approximating OWL 2 ontologies with ontologies in DL-Lite. To this aim we provide an algorithm for the computation of these approximations, and an optimized technique for the computation of the entailment set of an OWL 2 ontology in DL-Lite, which can be used efficiently in practice.

The rest of the paper is organized as follows. In Section 2, we provide some useful notions for the paper. In Section 3 we study the problem of ontology approximation, and introduce our notion of approximation. In Section 4 we focus on the approximation in DL-Lite of OWL 2 ontologies. In Section 5 we describe our technique for optimizing the computation of the entailment set of an OWL 2 ontology in DL-Lite, and present the results of our experimentation. Finally, in Section 6 we conclude the paper.

Preliminaries

Description Logics (DLs) [ 2 ] are logics that allow one to represent the domain of interests in terms of concepts, denoting sets of objects, value-domains, denoting sets of values, attributes, denoting binary relations between objects and values, and roles denoting binary relations over objects.

Let be a signature of symbols for individual (object and value) constants and atomic elements, i.e., concepts, value-domains, attributes, and roles. If L is a DL, then an ontology O in L (or L ontology) over is the set T [ A, where T , the TBox, is a finite set of intensional assertions over expressed in L, and A, the ABox, is a finite set of instance assertions, i.e, assertions on individuals, over . Different DLs allow for different kinds of TBox and/or ABox assertions and allow for different manners in which these can be combined for obtaining TBoxes and ABoxes in the specific DL.

The semantics of a DL ontology is given in terms of first-order (FOL) interpretations (cf. [ 2 ]). We denote with M od(O) the set of models of O, i.e., the set of FOL interpretations that satisfy all the assertions in T and A, where the definition of satisfaction depends on the kind of expressions and assertions in the specific DL language in which O is specified. As usual, a ontology O is said to be satisfiable if it admits at least one model, and O is said to entail a First-Order Logic (FOL) sentence , denoted O j= , if I = true for all I 2 M od(O). Moreover, given to ontology O and O0, we say that O and O0 are logically equivalent if M od(O) = M od(O0).

In this work we mainly focus on two specific languages, which are OWL 2, the official ontology language of the World Wide Web Consortium (W3C) [ 9 ], and DL-LiteA, a member of the DL-Lite family [ 5 ], which is a family of tractable DLs particularly suited for dealing with ontologies with very large ABoxes, and is at the basis of OWL 2 QL, one of the profiles of OWL 2.

The Web Ontology Language (version 2), or simply OWL 2, is an ontology language for the Semantic Web with formally defined meaning. OWL 2 provides for describing the domain of interest in terms of concepts, roles, attributes, individuals, and data values [ 9 ]. Due to the limitation of space, here we do not provide a complete description of OWL 2, but we refer the reader to the official W3C specification [ 11 ].

We now present the syntax of the DL DL-LiteA. As for the semantics, we apply the general definitions given above, and refer the reader to [ 13 ] for the precise description of the semantics of a DL-LiteA ontology.

In what follows we adopt the following notation: A, P , and U are symbols in denoting respectively an atomic concept, an atomic role and an atomic attribute; T1; : : : ; Tn are n pairwise disjoint unbounded value-domains; B denotes a basic concept; C a general concept; Q a basic role; R a general role; V a general attribute; E a basic value-domain; and F a value-domain expression.

Expressions in DL-LiteA are formed according to the following syntax: B C F ! A j 9Q j (U ) ! B j :B j 9Q:C j F (U ) ! T1 j j Tn

Q R ! P j P ! Q j :Q

V ! U j :U E ! (U ) where: P denotes the inverse of P , 9Q, or unqualified existential restriction denotes the objects related to some object by the role Q, : denotes negation, (U ) denotes the domain of U , i.e., the set of objects that U relates to values, and (U ) denotes the range of U , i.e., the set of values related to objects by U . The concept 9Q.C, or qualified existential restriction, denotes the qualified domain of Q with respect to C, i.e., the set of objects that Q relates to some instance of C. Similarly, F (U ) denotes the qualified domain of U with respect to a value-domain F , i.e., the set of objects that U relates to some value in F . We refer to the qualified existential restriction expression 9Q1. : : : .9Qn.C, where C is not a qualified existential restriction, as an existential role chain of depth n.

A DL-LiteA TBox assertion is an assertion of the form:

B v C

Q v R

E v F

U v V (funct Q) (funct U ) From left to right, the first four assertions denote inclusions between concepts, roles, value-domains, and attributes, respectively. The last two assertions denote functionality on roles and on attributes.

A DL-LiteA TBox is a finite set of assertions of the form above, where suitable limitations in the combination of such assertion are imposed. Given a TBox T and a role P (resp. an attribute U ), we say that P (resp. U ) is primitive in T if P does not appear in T positively in the right-hand side of any role (resp. attribute) inclusion assertion and in any qualified existential restriction. In a DL-LiteA TBox, a role P (resp, attribute U ) that is not primitive in T cannot appear either directly nr inversely in a functionality assertion.

A DL-LiteA ABox A is a finite set of assertions of the form A(a), P (a; b), and U (a; v), where A, P , and U are as above, a and b are object constants while v is a value constant. 3

Approximation of DL ontologies

In this section, we present our notion of approximation of an ontology expressed in a language L in a target language L0, and then we provide a comparison between our notion and others proposed in literature.

Ontology approximation. In what follows, O is a satisfiable L ontology, and L0 a language not necessarily different from L.

First of all, we need to introduce the notion of entailment set [ 12 ] of a satisfiable ontology with respect to a language.

Definition 1. Let O be a satisfiable ontology expressed in a language L over a signature , and let L’ be a language, not necessarily different from L. The entailment set of O with respect to L0, denoted as ES(O; L0), is the set which contains all L0 axioms over that are entailed by O.

In other words, we say that an axiom belongs to the entailment set of an ontology O with respect to a language L0, if is an L0 axiom built over the alphabet of O and for each interpretation I 2 M od(O) we have that I j= . Clearly, given an ontology O and a language L0, the entailment set of O with respect to L0 is unique.

With the notion of entailment set in place, we can define the notion of approximation in L0 of O0.

Definition 2. Let O be an ontology over a signature . A satisfiable L0 ontology O0 over is an approximation in L0 of O if both the following statements hold:

(i) ES(O0; L0) ES(O; L0); (ii) there is no satisfiable L0 ontology O00 such that ES(O0; L0)

ES(O; L0).

ES(O00; L0)

In other words, the above definition states that a satisfiable ontology O0 is an approximation in L0 of O , if O0 is an ontology in L0, and there is no a satisfiable ontology O00 in L0 whose entailment set in L0 is “nearer” to the entailment set of O in L0 than the entailment set in L0 of O, where the distance here is measured in terms of set inclusion.

Given an ontology O, it may be the case that the entailment set in a language L0 of O is infinite. If so, it may happen that the approximation in L0, in accordance with Definition 2, does not exist. For this reason, we follow the approach proposed in [ 3 ], where safeness restrictions on the target language are imposed, in order to guarantee the finiteness of the entailment set. For example, in DL-LiteA, which is the language we focus on in the following sections, the infiniteness of the entailment set arises from the possibility of inferring infinitely-long existential chains. In this case, the safeness restriction requires to allow, in the TBox, only existential chains of bounded length. Therefore, in what follows we denote versions of DL-LiteA in which such restriction is enforced as DL-Lite(Ak), where k is the bounded length of the existential chains.

Another characteristic of DL-LiteA, shared with other languages such as E L++ [ 1 ], is that syntactic restrictions are imposed on the manner in which assertions can be combined. In this case, there may exist more than one ontology which is an approximation in L0 of O. In what follows we denote with ApxMAX (O; L0) the set of L0 ontologies which are approximations in L0 of O in accordance with Definition 2. Example 1. Consider the OWL 2 ontology O = fA v 9R:B; A v 8R:B; (funct R)g. It is easy to see that, due to the syntactic restriction in DL-LiteA, which imposes that a non primitive role cannot be functional, we have that, up to logical equivalence, the set ApxMAX (O; DL-Lite(A1)) = ffA v 9R:Bg; fA v 9R; (funct R)gg. tu Comparison with related work. The problem of approximating ontologies for OBDA applications has recently been faced in [ 12 ] and [ 3 ].

In [ 12 ], the authors define the approximation in L0 of a satisfiable ontology O as the set of L0 axioms coinciding with the entailment set of O with respect to L0.

Definition 3. Let O be a satisfiable ontology expressed in a language L. The approximation in L0 of O is ApxES (O; L0) = ES(O; L0):

Therefore, in accordance with the above definition, the approximation in L0 of the ontology O is a set of L0 axioms, but not necessarily a valid ontology expressed in L0.

In [ 3 ], the authors provide a more sophisticated notion of approximation, in which it is required that the approximation in L0 of O be an ontology expressed in L0.

Definition 4. Let O be a satisfiable ontology expressed in a language L over a signa

ture . A satisfiable L0 ontology O0 over is an approximation in L0 of O if both the following statements hold: (i) ES(O0; L0) (ii) for each

ES(O; L0);

2 ES(O; L0) such that O0[f g is an L0 ontology, then

Example 2. Consider the following OWL 2 ontology: O = f9R 9R:B; (funct R)g. In accordance with Definitions 3, 4, 2, we have: v

B, A v ApxES (O; DL-Lite(A1)) = f9R v B; A v 9R; A v 9R:B; A v 9R:9R ; 9R v 9R:9R ; 9R v 9R :9R; (funct R) g ApxSC (O; DL-Lite(A1)) = fOs0c = f9R v B; A v 9R; A v 9R:B; A v 9R:9R ; 9R v 9R:9R ; 9R v 9R :9R g;

Os00c = f9R v B; A v 9R; (funct R) g g ApxM AX (O; DL-Lite(A1)) = fOmax = f9R v B; A v 9R; (funct R) g g tu

Due to the syntactic restrictions enforced in DL-Lite(A1), ontology O of Example 2 is not a DL-Lite(A1) ontology. However, it is logically equivalent to the DL-Lite(A1) ontology f9R v B, A v 9R; (funct R)g.

Regarding ApxES (O; DL-Lite(A1)) we only observe that it is not a valid DL-Lite(A1) ontology. Up to logical equivalence, we can see that the set ApxSC (O; DL-Lite(A1)) contains, along with ontology Os00c, which is logically equivalent to O, also the unexpected ontology Os0c, for which we have ES(Os0c; DL-Lite(A1)) ES(Os00c; DL-Lite(A1)). Finally, according to Definition 2, up to logical equivalence, the only approximation is a DL-Lite(A1) ontology that is logically equivalent to O.

Other significant differences between these three approaches arise when the goal is to compute the approximation of an ontology O expressed in a language L in which the UNA is not adopted into a target language L0 in which the UNA is adopted. In the example below, we highlight the different behavior of the three approaches in this circumstance.

Example 3. We recall that in OWL 2 the UNA is not adopted. This means, for instance, that given the following two ontologies O = fA v fo1g; B v fo2gg and O0 = fA v fo1g; B v fo2g; o1 6= o2g, we have that M od(O) 6= M od(O0). In fact, while O does not entail A v :B, O0 does. Differently, if we adopt the UNA in OWL 2, then we have that M od(O) = M od(O0), and both entail the assertion A v :B.

From the observations above, it follows that fA v fo1g; B v fo2gg ES(O; OWLUNA), and that A v :B 62 ES(O; OWLUNA). In what follows let us denote with OWLUNA the version of OWL 2 where the UNA is adopted.

In accordance with Definitions 3, 4, and 2, we have that, up to logical equivalence, the approximations in OWLUNA of O are: – ApxES (O; OWLUNA) = ES(O; OWLUNA). In this case, ApxES (O; OWLUNA) is a valid OWLUNA ontology. Let OES be such ontology. As shown above, since in OWLUNA the UNA is adopted, OES j= A v :B. This means that ES(OES ; OWLUNA) 6 ES(O; OWLUNA): – ApxSC (O; OWLUNA) = ;. Indeed, since ES(O; OWLUNA) is a valid OWLUNA ontology, any OWLUNA ontology O1 such that ES(O1; OWLUNA) ES(O; OWLUNA), does not satisfy condition (ii) of Definition 4. Moreover, since every OWLUNA ontology O2 that satisfies condition (ii) entails both fA v fo1g; B v fo2gg, then it also entails A v :B. Hence ES(O2; OWLUNA) 6 ES(O; OWLUNA), and so condition (i) of Definition 4 is not satisfied. – ApxMAX (O; OWLUNA) = fOm0ax = fA v fo1gg; Om00 ax = fB v fo2gg g. Indeed, it is easy to verify that both Om0ax and Om00 ax satisfy both conditions (i) and (ii) of Definition 2, and that there is no other ontology O000 in ApxMAX (O; OWLUNA) logically equivalent to neither Om0ax nor Om00 ax. tu As shown in the previous example, given an L ontology O and a target language L0, our approach, as the one in [ 3 ], but differently from the one given in [ 12 ], guarantees that an approximation in L0 of O is an L0 ontology, and that for each L0 ontology O0 that is an approximation in L0 of O, we have that ES(O0; L0) ES(O; L0). Finally, it can be shown that our approach always preserves the same or more inferences than those obtained by adopting the approach given in [ 3 ].

Theorem 1. For each Osc 2 ApxSC (O; L0), there is an Omax 2 ApxMAX (O; L0)

such that ES(Osc; L0) ES(Omax; L0). Furthermore, for each Omax 2

ApxMAX (O; L0), there is no Osc 2 ApxSC (O; L0) such that ES(Omax; L0)

ES(Osc; L0). 4

Approximation in DL-LiteA of OWL 2 ontologies

In this section, we study the problem of computing the approximation in DL-LiteA of a satisfiable OWL 2 ontology O. More specifically, we aim to approximate O with DL-LiteA TBox assertions. Therefore, in what follows we assume that ApxMAX (O; DL-LiteA) is a set of DL-LiteA TBoxes and that ES(O; DL-LiteA) is a set of DL-LiteA TBox assertions. To guarantee the finiteness of the entailment set, we refer to versions of DL-LiteA allowing only for TBox assertions with existential chains of bounded length k.

Given a set of DL-Lite(Ak) assertions S, and a functionality assertion ' over a role R (resp. attribute U ), we denote with clashes('; S) the set of all assertions involving R (resp. U ) that, together with ', violate the syntactic restriction imposed on DL-Lite(Ak) TBoxes. Hence, clashes('; S) is a set of role (resp. attribute) inclusion assertions and assertions with a qualified existential role (resp. attribute) on the right hand side.

Let O be an OWL 2 ontology, and let F be the set containing all the functionality assertions in ES(O; DL-Lite(Ak)) for which clashes('; ES(O; DL-Lite(Ak))) 6= ;. If F 6= ;, then ES(O; DL-Lite(Ak)) is not a valid DL-Lite(Ak) TBox, and there are at most 2jFj TBoxes Ti which are valid DL-Lite(Ak) TBoxes and minimally differ from ES(O; DL-Lite(Ak)). Let M axSubES (ES(O; DL-Lite(Ak))) be the set of such DL-Lite(Ak) TBoxes. One can compute these TBoxes in M axSubES (ES(O; DL-Lite(Ak))) by retracting, from ES(O; DL-Lite(Ak)), either ' 2 F or the assertions in clashes('; S), in order to resolve the violations of the syntactic restriction.

The lemma below guarantees that a TBox in M axSubES (ES(O; DL-Lite(Ak))) is a candidate for being one of the TBoxes in ApxMAX (O; DL-Lite(Ak)).

Lemma 1. Let O be a satisfiable OWL 2 ontology and let T be a DL-Lite(Ak) TBox. ES(T ; DL-Lite(Ak)) ES(O; DL-Lite(Ak)) if and only if T ES(O; DL-Lite(Ak)).

In other words, the above lemma guarantees that the first condition in Definition 2 is satisfied by every DL-Lite(Ak) TBox in M axSubES (ES(O; DL-Lite(Ak))), and that in computing all the TBoxes in ApxMAX (O; DL-Lite(Ak)), one can consider only the assertions in ES(O; DL-Lite(Ak)). Moreover, from the monotonicity of the DLs, it directly follows that for every TBox T in ApxMAX (O; DL-Lite(Ak)) there is a TBox in M axSubES (ES(O; DL-Lite(Ak))) which is logically equivalent to T .

However, in order for a TBox Ti in M axSubES (ES(O; DL-Lite(Ak))) to belong to ApxMAX (O; DL-Lite(Ak)), it must also satisfy the second condition of Definition 2, and thus that there is no other DL-Lite(Ak) TBox T 0 ES(T ; DL-Lite(Ak)) such that ES(Ti; DL-Lite(Ak))

ES(T 0; DL-Lite(Ak))

ES(O; DL-Lite(Ak)).

To explain why a TBox in M axSubES (ES(O; DL-Lite(Ak))) does not necessarily also satisfy the second condition in Definition 2, we refer to the ontology O = f9R v B; A v 9R:B; (funct R)g of Example 2. It is easy to see that ES(O; DL-Lite(A1)) = f9R v B, A v 9R:B, (funct R), 9R v 9R:9R , 9R v 9R:B, A v 9R:9R , 9R v 9R :9R, A v 9Rg, and that clashes((funct R); ES(O; DL-Lite(A1))) = fA v 9R:B, 9R v 9R:9R , 9R v 9R:B, A v 9R:9R , 9R v 9R :9Rg. Hence, by following the procedure described above, we have the following two TBoxes in M axSubES (ES(O; DL-Lite(A1))): T1 = f9R v B, A v 9R:B, 9R v 9R:9R , 9R v 9R:B, A v 9R:9R , 9R v 9R :9R, A v 9Rg, and T2 = f9R v B, (funct R), A v 9Rg. However, it is clear that only T2 2 ApxMAX (O; DL-Lite(A1)). In fact we have that ES(T1; DL-Lite(A1)) ES(T2; DL-Lite(A1)).

We provide the algorithm isApx which, given a TBox T and an ontology O, returns true if T 2 ApxMAX (O; DL-Lite(Ak)), false otherwise. The algorithm proceeds as fol

Algorithm 1: isApx(T ; O)

Input: a DL-Lite(Ak) TBox T , a satisfiable OWL 2 ontology O Output: true or false begin

E ES(T ; DL-Lite(Ak));

S ES(O; DL-Lite(Ak)) n E;

foreach 2 S

if T [ f g is a DL-Lite(Ak) TBox then return false; foreach functionality assertion 2 E

E E n clashes( ; E); foreach functionality assertion ' 2 S

if ES(E n clashes('; E); DL-Lite(Ak)) = ES(T ; DL-Lite(Ak)) then return false; return true; end lows. Given a satisfiable OWL 2 ontology O and a DL-Lite(Ak) TBox T , it first computes their entailment sets in DL-Lite(Ak) and then computes the set S containing all the assertions in the entailment set of O in DL-Lite(Ak) which are not in the entailment set of T in DL-Lite(Ak). Then, for every assertion in S, it attempts to add to T without violating any syntactic restriction. If such assertion exists, then T is not an approximation in DL-Lite(Ak) of O. If not, the algorithm continues, fixing E as the entailment set of T in DL-Lite(Ak), and resolving every violation of the syntactic restriction in E by removing clashes( ; E ) from E , for every functionality assertion in E . This operation guarantees that E is a DL-Lite(Ak) TBox. Then the algorithm checks, for every functionality assertion ' in S, if the set obtained from E by removing clashes('; E ) from E is logically equivalent to E . If this is the case, then it is possible to build a DL-Lite(Ak) TBox T 00 by adding ' to the set of assertions obtained in this fashion. T 00 is a DL-Lite(Ak) TBox that proves that T does not satisfy the second condition of Definition 2. Otherwise, the algorithm terminates by returning true.

The theorem below establishes termination and correctness of Algorithm 1. Theorem 2. Let O be a satisfiable OWL 2 ontology, and let T be a DL-Lite(Ak) TBox. isApx(T ; O) terminates, and returns true if and only if T 2 ApxMAX (O; DL-Lite(Ak)).

Given a satisfiable OWL 2 ontology O, Lemma 1 and Theorem 2 suggest Algorithm 2 for computing, up to logical equivalence, the set ApxMAX (O; DL-Lite(Ak)).

The following theorem establishes termination and correctness of Algorithm 2.

Theorem 3. Let O be a satisfiable OWL 2 ontology. Then computeApx(O) terminates

and computes, up to logical equivalence, ApxMAX (O; DL-Lite(Ak)).

As expected, Algorithm 2 does not return a single TBox, but instead a set of TBoxes. For application purposes, the approximation that shall be used must be chosen from this set. A pragmatic approach could be to choose one non-deterministically. Instead, one could think to leave this choice to the end user, according to the use he intends to make

Algorithm 2: computeApx(O)

Input: a satisfiable OWL 2 ontology O Output: a set of DL-Lite(Ak) TBoxes begin

S M axSubES(ES(O; DL-Lite(Ak))); foreach Ti 2 S

if isApx(Ti; O) = false then S return S; end

S n fTig; of it. A more interesting direction could be to achieve the identification of a unique TBox by applying some preference criteria to the set returned by Algorithm 2. 5

Efficient entailment set computation in DL-Lite

In the previous sections, we have provided an algorithm for computing the set ApxMAX (O; DL-Lite(Ak)) of TBoxes for an OWL 2 ontology O. This computation is clearly intractable. Indeed, it requires to compute the set ES(O; DL-Lite(Ak)), and moreover, due to the syntactic restriction enforced in DL-Lite(Ak), in the worst case, the cardinality of the set ApxMAX (O; DL-Lite(Ak)) is exponential in the number of functionality assertions in ES(O; DL-Lite(Ak)). In particular, the computation of ES(O; DL-Lite(Ak)) is in general very costly, as highlighted also in [ 3 ] and [ 12 ], since it requires the invocation of reasoning services over an OWL 2 ontology O. This task is performed by invoking an OWL 2 oracle which can be implemented by an OWL 2 reasoner.

A naive algorithm for computing ES(O; DL-Lite(Ak)) is the one described in [ 12 ], in which firstly one computes the set of DL-Lite(Ak) TBox assertions which can be built over the signature , and then, for each assertion 2 such that O j= , one adds to ES(O; DL-Lite(Ak)).

We now show how to optimize the computation of ES(O; DL-Lite(Ak)) through a technique which drastically reduces in practice the calls to the OWL 2 oracle.

In the computation of ES(O; DL-Lite(Ak)), a large portion of the invocations of the OWL 2 oracle involve assertions in which a general concept C9R1:::9Rn involving a non trivial existential role chain occurs. Empirical observation has brought to light the fact that this kind of general concept very often does not subsume any concept in O. Hence, all the invocations of the OWL 2 oracle involving these childless general concepts are useless. Therefore, at the base of our strategy is the identification of all these childless general concepts C9R1:::9Rn , without invoking the OWL 2 oracle.

We use the function subsumed(S1; O), where S1 is a general concept (resp. general role, general attribute) which returns the set of concepts (resp. roles, attributes) S2 such that O j= S2 v S1. This function is efficiently performed by the most commonly-used OWL 2 reasoners, such as Pellet [ 15 ], Racer [ 8 ], FACT++ [ 16 ], and HermiT [ 7 ].

Our technique calls, as the first step, for the computation of the classification of basic concepts, roles, and attributes, which is encoded into a directed graph, in which the nodes represent the predicates of the ontology, and the edges the inclusion assertions. Ontology DL Fragment Mouse Pathway Cognitive Mammalian Spatial

After this initial step, the remaining invocations, which we work to minimize, are those needed for computing the entailed inclusion assertions involving general concepts C9R1:::9Rn , and the entailed disjointness. Regarding the former, we exploit the graph encoding of concept, role, and attribute classification to invoke these subsumption checks in a manner which follows the hierarchical order of these general concepts C9R1:::9Rn , in order to avoid those checks which can be skipped. Consider, for example, an ontology O that entails the inclusions A1 v A2 and P1 v P2, where A1 and A2 are concepts and P1 and P2 are roles. Exploiting these inclusions we can deduce the hierarchical structure involving general concepts that can be built on these four predicates. For instance, we know that 9P2:A2 v 9P2, that 9P2:A1 v 9P2:A2, that 9P1:A1 v 9P2:A1, and so on. We begin by invoking the OWL 2 oracle, asking for the children of the general concepts which are in the highest position in the hierarchy. So, first we call subsumed(9P2; O). If subsumed(9P2; O) = ;, we avoid invoking the oracle asking for subsumed(9P2:A2; O), and so on. Regarding the latter we follow the same procedure, but beginning from the lowest positions in the hierarchy. The algorithm concludes by asking the OWL 2 oracle for all functionalities entailed by O.

In Table 1 we present a sample of the evaluation tests for this strategy, performed through a Java-based implementation of this technique. The table reports the number of invocations to the OWL 2 oracle performed with our optimization (#O.A.), and without (#N.A.), for computing the entailment set of the ontologies in DL-Lite(Ak), with 1 k 3. It also reports, for each ontology, the total computation time of ES(O; DL-Lite(Ak)). 6

Conclusion

In this paper we address the problem of ontology approximation. We illustrate our approach to this problem, and provide a comparison with other approaches provided in literature. We deeply investigate the approximation of OWL 2 ontologies with DL-Lite TBoxes for OBDA purposes, and provide an algorithm for its computation. Finally, we present a technique for the optimization of the core procedure of this computation, whose success we have shown with empirical evaluation. As future work, we plan to improve the performances in computing the approximation in DL-Lite of OWL 2 ontologies by adopting more sophisticated techniques. Moreover, we aim to study reasonable solutions for addressing the problem of multiple approximations of an ontology. In particular, for those settings in which the approximation is used in OBDA. Acknowledgments. This research has been partially supported by the EU under FP7 project Optique (grant n. FP7-318338), and by the EU under FP7-ICT project ACSI (grant no. 257593).

References

1. Franz Baader , Sebastian Brandt , and Carsten Lutz . Pushing the E L envelope further . In Proc. of OWLED 2008 DC , 2008 .

2. Franz Baader , Diego Calvanese, Deborah McGuinness , Daniele Nardi , and Peter F. PatelSchneider, editors. The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2003 .

3. Elena Botoeva , Diego Calvanese, and Mariano Rodriguez-Muro. Expressive approximations in DL-Lite ontologies . Proc. of AIMSA 2010 , pages 21 - 31 , 2010 .

4. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Antonella Poggi, Mariano Rodriguez-Muro, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. The Mastro system for ontology-based data access . Semantic Web J. , 2 ( 1 ): 43 - 53 , 2011 .

5. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati . Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. of Automated Reasoning , 39 ( 3 ): 385 - 429 , 2007 .

6. Balakrishnan Chandrasekaran , John R Josephson, and V Richard Benjamins . What are ontologies, and why do we need them? Intelligent Systems and Their Applications , IEEE, 14 ( 1 ): 20 - 26 , 1999 .

7. Birte Glimm , Ian Horrocks, Boris Motik, Rob Shearer, and Giorgos Stoilos . A novel approach to ontology classification . J. of Web Semantics , 10 ( 1 ), 2011 .

8. Volker Haarslev and Ralf Mo¨ ller. RACER system description . In Proc. of IJCAR 2001 , volume 2083 of LNAI , pages 701 - 705 . Springer, 2001 .

9. Pascal Hitzler , Markus Kro¨ tzsch, Bijan Parsia, Peter F. Patel-Schneider , and Sebastian Rudolph, editors. OWL 2 Web Ontology Language: Primer. W3C Recommendation , 11 december 2012. Available at http://www.w3.org/TR/2012/ REC-owl2 - primer-20121211/.

10. Maurizio Lenzerini . Ontoloogy-based data management . In Proc. of CIKM 2011 , pages 5 - 6 , 2011 .

11. Boris Motik , Bijan Parsia, and Peter F. Patel-Schneider, editors. OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax. W3C Recommendation , 11 december 2012. Available at http://www.w3.org/TR/2012/ REC-owl2 - syntax-20121211/.

12. Jeff Z Pan and Edward Thomas . Approximating OWL-DL ontologies . In Proc. of AAAI 2007 , page 1434 , 2007 .

13. Antonella Poggi , Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati . Linking data to ontologies . J. on Data Semantics , X: 133 - 173 , 2008 .

14. Bart Selman and Henry Kautz . Knowledge compilation and theory approximation . J. of the ACM , 43 ( 2 ): 193 - 224 , 1996 .

15. Evren Sirin , Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz . Pellet: a practical OWL-DL reasoner . Web Semantics: science, services and agents on the World Wide Web , 5 ( 2 ): 51 - 53 , 2007 .

16. Dmitry Tsarkov and Ian Horrocks . FaCT++ description logic reasoner: System description . In Proc. of IJCAR 2006 , pages 292 - 297 , 2006 .

17. Tuvshintur Tserendorj , Sebastian Rudolph , Markus Kro¨ tzsch, and Pascal Hitzler. Approximate OWL-reasoning with Screech . In Proc. of RR 2008 , pages 165 - 180 . Springer, 2008 .

18. Holger Wache , Perry Groot, and Heiner Stuckenschmidt . Scalable instance retrieval for the semantic web by approximation . In Proc. of WISE 2005 , pages 245 - 254 . Springer, 2005 .