Ontology classi cation is the reasoning service that computes all subsumption relationships inferred in an ontology between concept, role, and attribute names in the ontology signature. OWL 2 QL is a tractable pro le of OWL 2 for which ontology classi cation is polynomial in the size of the ontology TBox. However, to date, no e cient methods and implementations speci cally tailored to OWL 2 QL ontologies have been developed. In this paper, we provide a new algorithm for ontology classi cation in OWL 2 QL, which is based on the idea of encoding the ontology TBox into a directed graph and reducing core reasoning to computation of the transitive closure of the graph. We have implemented the algorithm in the QuOnto reasoner and extensively evaluated it over very large ontologies. Our experiments show that QuOnto outperforms various popular reasoners in classi cation of OWL 2 QL ontologies.
Ontology classi cation is the problem of computing all subsumption relationships inferred in an ontology between predicate names in the ontology signature, i.e., named concepts (a.k.a. classes), roles (a.k.a. object-properties), and attributes (a.k.a. data-properties). It is considered a core service for ontology reasoning, which can be exploited for various tasks, at both design-time and run-time, ranging from ontology navigation and visualization to query answering.
Devising e cient ontology classi cation methods and implementations is a
challenging issue, since classi cation is in general a costly operation. Most
popular reasoners for Description Logic (DL) ontologies, i.e., OWL ontologies, such
as Pellet [23], Racer [
Whereas the above tools use algorithms based on model construction through
tableau (or hyper-tableau [
Other recently developed tools, such as Snorocket [
Instead, to the best of our knowledge, ontology classi cation in the other
OWL 2 pro les has received so far little attention. In particular, classi cation in
OWL 2 RL has been investigated only in [
In this paper, we thus provide a new method for ontology classi cation in the OWL 2 QL pro le. In our technique, we encode the ontology terminology (TBox) into a graph, and compute the transitive closure of the graph to then obtain the ontology classi cation. The analogy between simple inference rules in DLs and graph reachability is indeed very natural: consider, for example, an ontology containing the subsumptions A1 v A2 and A2 v A3, where A1, A2, and A3 are class names in the ontology signature. We can then associate to this ontology a graph having three nodes labeled with A1, A2, and A3, respectively, an edge from A1 to A2 and an edge from A2 to A3. It is straightforward to see that A3 is reachable from A1, and therefore an edge from A1 to A3 is contained in the transitive closure of the graph. This corresponds to the inferred subsumption A1 v A3. On the other hand, things become soon much more complicated when complex (OWL) axioms come into play.
In this respect, we will show that for an OWL 2 QL ontology it is possible
to easily construct a graph whose closure constitutes the major sub-task in
ontology classi cation, because it allows us to obtain all subsumptions inferred by
the \positive knowledge" speci ed by the TBox. We will show that the
computed classi cation misses only \trivial" subsumptions inferred by unsatis able
predicates, i.e., named classes (resp. properties) that always have an empty
interpretation in every model of the ontology, and that are therefore subsumed
by every class (resp. property) in the ontology signature. We therefore provide
an algorithm that, exploiting the transitive closure of the graph, computes all
unsatis able predicates, thus allowing us to obtain a complete ontology
classi1 Not to be confused with the set of DLs studied in [
cation. We notice that the presence of unsatis able predicates in an ontology
is mainly due to errors in the design. However, it is not rare to nd such
predicates, especially in very large ontologies or in ontologies that are still \under
construction". In particular, we could nd unsatis able concepts even in some
benchmark ontologies we used in our experiments (cf. Section 4). Of course,
already debugged ontologies might not present such predicates [
We have implemented our technique in a new module of QuOnto [
QuOnto showed better performances, in some cases corresponding to enormous gains, with respect to tableau-based reasoners (in particular, Pellet, Fact++, and HermiT). We also obtained comparable or better results with respect to the CB reasoner, for almost all ontologies considered, but, di erently from CB reasoner, we were always able to compute a complete classi cation. We nally compared QuOnto with ELK, one of the most performing reasoner for E L, for those approximated ontologies that turned out to be both in OWL 2 QL and OWL 2 EL, obtaining similar performances in almost all cases.
We conclude by noticing that, even though we refer here to OWL 2 QL, our
algorithms and implementations can be easily adapted to deal with all logics
of the DL-Lite family mentioned in [
The rest of the paper is organized as follows. In Section 2, we provide some preliminaries. In Section 3, we describe our technique for ontology classi cation in OWL 2 QL. In Section 4, we describe our experimentation, and nally, in Section 5, we conclude the paper. 2
In this section, we present some basic notions on DL ontologies, the formal underpinning of the OWL 2 language, and on OWL 2 QL. We also recall some notions of graph theory needed later on.
Description Logic Ontologies. We consider a signature , partitioned in two disjoint signatures, namely, P , containing symbols for predicates, i.e., atomic concepts, atomic roles, atomic attributes, and value-domains, and C , containing symbols for individual (object and value) constants. Complex concept, role, and attribute expressions are constructed starting from predicates of P by applying suitable constructs, which vary in di erent DL languages. Given a DL language L, an L-TBox (or simply a TBox, when L is clear) over contains universally quanti ed rst-order (FOL) assertions, i.e., axioms specifying general properties of concepts, roles, and attributes. Again, di erent DLs allow for di erent axioms. An L-ABox (or simply an ABox, when L is clear) is a set of assertions on individual constants, which specify extensional knowledge. An L-ontology O is constituted by both an L-TBox T and an L-ABox A, denoted as O = hT ; Ai.
The semantics of a DL ontology O is given in terms of FOL interpretations
(cf. [
Traditional intensional reasoning tasks with respect to a given TBox are
veri cation of subsumption and satis ability of concepts, roles, and attributes [
Strictly related to the previous reasoning tasks is the classi cation inference service, which we focus on in this paper. Given a signature P and a TBox T over P , such a service allows to determine subsumption relationships in T between concepts, roles, and attributes in P . Therefore, classi cation allows to structure the terminology of T in the form of a subsumption hierarchy that provides useful information on the connection between di erent terms, and can be used to speed up other inference services. Here we de ne it more formally. De nition 1. Let T be a satis able L-TBox over P . We de ne the T classi cation of P (or simply T -classi cation when P is clear from the context) as the set of inclusion assertions de ned as follows:
Let S1 and S2 be either two concepts, roles, or attributes in P . If
T j= S1 v S2 then S1 v S2 belongs to the T -classi cation of P .
The OWL 2 QL Language. The OWL 2 QL language is based on DL-LiteR,
a DL of the DL-Lite family [
Expressions in OWL 2 QL are formed according to the following syntax: B C ! A j 9Q ! B j :B j 9Q:A
Q R ! P j P ! Q j :Q where: A and P are symbols in P denoting respectively an atomic concept and an atomic role; P denotes the inverse of P ; 9Q, also called unquali ed existential role, denotes the set of objects related to some object by the role Q; the concept 9Q.A, or quali ed existential role, denotes the quali ed domain of Q with respect to A, i.e., the set of objects that Q relates to some instance of A. In the following, we call B a basic concept, and Q a basic role.
An OWL 2 QL TBox T is a nite set of axioms of the form B v C and Q v R, where the former denote subsumptions between concepts, and the latter subsumptions between roles. We call positive inclusions axioms of the form B1 v B2, B1 v 9Q:A, and Q1 v Q2, and negative inclusions axioms of the form B1 v :B2 and Q1 v :Q2.
The semantics of OWL 2 QL ontologies and TBoxes is given in the standard
way [
As for OWL 2 QL ABoxes, we do not present them here, since we concentrate on intensional reasoning, and refer the interested reader to [21]. Graph Theory Notions. In this paper we use the term digraph to refer to a directed graph. We assume that a digraph G is a pair (N ; E ), where N is a set of elements called nodes, and E is a set of ordered pairs (s; t) of nodes in N , called arcs, where s is denoted the source of the arc, and t the target of the arc.
The transitive closure G = (N ; E ) of a digraph G = (N ; E ) is a digraph
such that there is an arc in E having a node s as source and a node t as target
if and only if there is a path from s to t in G [
In this section we describe our approach to computing, given a signature P and an OWL 2 QL TBox T over P , the T -classi cation of P .
In OWL 2 QL, a subsumption relation between two concepts or roles in P , can be inferred by a TBox T if and only if (i) T contains such subsumption; (ii) T contains a set of positive inclusion assertions that together entail the subsumption; or (iii), trivially, the subsumed concept or role is unsatis able in T . The above observation is formalized as follows.
Theorem 1. Let T be an OWL 2 QL TBox containing only positive inclusions, and let S1 and S2 be two atomic concepts or two atomic roles. S1 v S2 is entailed by T if and only if at least one of the following conditions holds: 1. a set P of positive inclusions exists in T , such that P j= S1 v S2; 2. T j= S1 v :S1.
Given a OWL 2 QL TBox T over a signature P , we use T and T to denote two sets of positive inclusions of the form S1 v S2, with S1; S2 2 P , such that T contains only positive inclusions for which statement 1 holds, and
T contains only positive inclusions for which statement 2 holds. It is easy to see that T and T are not disjoint. From De nition 1 and Theorem 1 it follows that the T -classi cation coincides with the union of the sets T and T .
In the following, we describe our approach to the computation of the T classi cation by rstly computing the set T , and then computing the set T . Computation of T . Given an OWL 2 QL TBox T , in order to compute T , we encode the set of positive inclusions in T into a digraph GT and compute the transitive closure of GT in such a way that each subsumption S1 v S2 in
T corresponds to an arc (S1; S2) in such transitive closure, and vice versa. The following constructive de nition describes the appropriate fashion to obtain the digraph TBox representation for our aims.
De nition 2. Let T be an OWL 2 QL TBox over a signature P . We call the digraph representation of T the digraph GT = (N ; E ) built as follows: 1. for each atomic concept A in P , N contains the node A; 2. for each atomic role P in P , N contains the nodes P , P , 9P , 9P ; 3. for each concept inclusion B1 v B2 2 T , E contains the arc (B1; B2); 4. for each role inclusion Q1 v Q2 2 T , E contains the arcs (Q1; Q2), (Q1 ; Q2 ), (9Q1 ,9Q2), and (9Q1 ; 9Q2 ); 5. for each concept inclusion B1 v 9Q:A 2 T , E contains the arc (B1; 9Q);
The idea is that each node in the digraph GT represents a basic concept or a basic role, and each arc models a positive inclusion, i.e., a subsumption, contained in T , where the source node of the arc represents the left-hand side of the subsumption and the target node of the arc represents the right-hand side of the subsumption. Observe that for each role inclusion assertion P1 v P2 in the TBox T , we also represent as nodes and arcs in the digraph GT the entailed positive inclusions P1 v P2 , 9P1 v 9P2, and 9P1 v 9P2 .
Let T be an OWL 2 QL TBox and let GT = (N ; E ) be its digraph representation. We denote with GT = (N ; E ) the transitive closure of GT . Note that by de nition of digraph transitive closure, for each node n 2 N there exists in E an arc (n; n). Moreover, in what follows, we denote with (E ) the set of arcs (S1; S2) 2 E such that both terms S1 and S2 denote in T either two atomic concepts or two atomic roles. Then, the following property holds. Theorem 2. Let T be an OWL 2 QL TBox and let GT = (N ; E ) be its digraph representation. Let S1 and S2 be two atomic concepts or two atomic roles. An inclusion assertion S1 v S2 belongs to T if and only if there exists in (E ) an arc (S1; S2).
We can then easily construct an algorithm, called Compute , that, taken as input an OWL 2 QL TBox T , rst builds the digraph GT = (N ; E ) according Algorithm: computeUnsat Input: an OWL 2 QL TBox T Output: a set of concept and role expressions Emp ;; foreach negative inclusion S1 v :S2 2 T do foreach n1 2 predecessors(S1; GT ) do foreach n2 2 predecessors(S2; GT ) do if n1 = n2 then Emp if (n1 = 9Q then Emp
Emp [ fn1g; and n2 = A) or (n2 = 9Q
Emp [ f9Q:Ag; Emp0 ;; while Emp 6= Emp0 do
Emp0 Emp; foreach S 2 Emp0 do foreach n 2 predecessors(S; GT ) do
Emp Emp [ fng; if n = P or n = P or n = 9P or n = 9P then Emp Emp [ fP; P ; 9P; 9P g; if there exists B v 9Q:n 2 T then Emp Emp [ f9Q:ng; return Emp. and n1 = A) /* step 1 */ /* step 2 */ to De nition 2, then computes its transitive closure, and nally returns the set T , which contains an inclusion assertion S1 v S2 for each arc (S1; S2) 2 (E ).
According to Theorem 2, Compute is sound and complete with respect to the problem of computing T for any OWL 2 QL TBox T containing only positive inclusions.
Computation of T . We rst observe that, according De nition 2, no node corresponding to a quali ed existential role is created in the TBox digraph representation. This kind of node is indeed not useful for computing T . Di erently, if one aims to identify every cause of unsatis ability, the creation of nodes corresponding to a quali ed existential role is needed. This is due to the fact that a TBox may entail that a quali ed existential role 9P:A is unsatis able, even in case of satis ability of 9P . Speci cally, this may occur in two instances: (i) if the TBox T entails the assertion 9P v :A, and (ii), the TBox T entails A v :A. Clearly, in both cases the concept 9P:A is unsatis able. We therefore modify here De nition 2 by substituting Rule 5 with the following one: 5 . for each concept inclusion B1 v 9Q:A 2 T , N contains the node 9Q:A, and E contains the arcs (B1; 9Q:A) and (9Q:A; 9Q);
From now on, we adopt the digraph representation built according to De nition 2, where rule 5 replaces rule 5. Given one such TBox T over a signature P , the algorithm computeUnsat given in Figure 1 returns all unsatis able concepts and roles in P , by exploiting the transitive closure of the digraph representation of T .
Before describing the algorithm, we recall that, given a digraph G = (N ; E ) and a node n 2 N , the set predecessors(n; G ) contains all those nodes n0 in N such that G contains the arc (n0; n), which means that there exists a path from n0 to n in G. Also, it can be shown that GT allows in fact to obtain all subsumptions between satis able basic concepts or roles, in the sense that the TBox T infers one such subsumption S1 v S2 if and only if there is an arc (S1; S2) in E . Then, the two steps that compose the algorithm proceed as follows: Step 1 Let S be either a concept expression or a role expression. We have that for each Si 2 predecessors(S; GT ) the TBox T entails Si v S. p:HrSeend2jc.eecT,eshgseoivrrsee(fnoSr1ea;,GnTfoe)rgaaetniavdcehfoinnrecgleuaastciihovneS2iajnscs2leurstpiirooenndeSSce11ssvovrs(::SSS2;22G,T2f)o,rTTe,atcj=hhe SSa11iilgov2rithm computes the set predecessors(S1; GT ) and predecessors(S2; GT ) and is able to: (i) recognize as unsatis able all those concepts and roles whose corresponding nodes occur in both the set predecessors(S1; GT ) and predecessors(S2; GT ), and (ii) identify those unsatis able quali ed existential roles 9Q:A whose inverse existential role node 9Q occurs in predecessors(S1; GT ) (resp. predecessors(S2; GT )) and whose concept node A occurs in predecessors(S2; GT ) (resp. predecessors(S1; GT )), which indeed implies 9Q v :A and therefore unsatis ability of 9Q:A.
Step 2 Further unsatis able concepts and roles are identi ed by the algorithm through a cycle in which: (i) if a concept or role S is in Emp, then all the expressions corresponding to the nodes in predecessors(S; GT ) are in Emp. This captures propagation of unsatis ability through chains of positive inclusions; (ii) if at least one of the expressions P; P ; 9P; 9P is in Emp, then all four expressions are in Emp; (iii) for each expression 9Q:A in N , if A 2 Emp, then 9Q:A 2 Emp. We notice that the algorithm stops cycling when no new expressions of the form 9Q or 9Q:A are added to Emp (indeed, in this case only a single further iteration may be needed).
It easy to see that, by virtue of the fact that the size of the set N of the digraph representation of the TBox T is nite, computeUnsat(T ) terminates, and that the number of executions of the while cycle is less than or equal to jN j.
The following theorem shows that algorithm computeUnsat can be used for computing the set containing all the unsatis able concepts and roles in T . Theorem 3. Let T be an OWL 2 QL TBox and let S be either an atomic concept or an atomic role in P . T j= S v :S if and only if S 2 computeUnsat(T ).
We call Compute the algorithm that, taken T as input, returns T by making use of computeUnsat.
The following theorem, which is a direct consequence of Theorem 2 and of Theorem 3, states that our technique is sound and complete with respect to the problem of classifying an OWL 2 QL TBox.
Theorem 4. Let T be an OWL 2 QL TBox and let S1 and S2 be either two
atomic predicates. T j= S1 v S2 if and only if S1 v S2 2 Compute (T ) [
Compute (T ).
By exploiting the results presented in Section 3, we have developed a Java-based
OWL 2 QL classi cation module for the QuOnto reasoner [
This module computes the classi cation of an OWL 2 QL TBox T by adopting the technique described in Section 3. In this implementation the transitive closure of the digraph GT is based on a breadth rst search through GT . In the implementation we have considered all aspects of OWL 2 QL which were ignored in the theoretical discussion presented in the previous sections (see Section 2).
We have performed comparative experiments, where QuOnto was tested
against several popular ontology reasoners. Speci cally, during our test we
compared ourselves with the Fact++ [24], Hermit [
The ontology suite used during testing includes twenty OWL ontologies, assembled from the TONES Ontology Repository3 and from other independent sources. The six reasoners exhibited negligible di erences in performance for the majority of the smaller tested ontologies, so we will only discuss the ontologies which o ered interesting results, meaning those on which reasoning times are signi cantly di erent for at least a subset of the reasoners.
These ontologies include: the Mouse ontology; the Transportation
ontology4; the Descriptive Ontology for Linguistic and Cognitive Engineering
(DOLCE) [19]; the Athletic Events Ontology (AEO)5; the Gene Ontology
(GO) [
Because QuOnto is an OWL 2 QL reasoner, each benchmark ontology not in OWL 2 QL was preprocessed prior to classi cation in order to t OWL 2 QL expressivity. Therefore, every OWL expression which cannot be expressed 3 http://owl.cs.manchester.ac.uk/repository/ 4 http://www.daml.org/ontologies/409 5 http://www.boemie.org/deliverable d 3 5 by OWL 2 QL axioms was approximated from the ontology speci cations. This approximation follows this procedure: each axiom in the ontology is fed to an external reasoner, speci cally Hermit, and every OWL 2 QL-compliant axiom that is implied from that axiom, between the ontology symbols that appear in it, is added to the OWL 2 QL-approximated ontology. For instance, the OWL assertion EquivalentClasses(ObjectUnionOf(:Male :Female) :Person) is approximated by the two assertions SubClassOf(:Male :Person) and SubClassOf(:Female :Person). Note that, as is the case in this example, the OWL 2 QL-approximated ontology may contain a greater number of axioms than the original ontology. Table 1 shows that the Mouse, Transportation, Gene, and FMA-OBO ontologies are in OWL 2 QL, and thus do not need approximation, while AEO and FMA 1.4 are subject to minimal changes by the approximation procedure.
During the tests for each reasoner, classi cation was performed on the OWL 2 QL-compliant versions of the ontologies resulting from the above described preprocessing. Metrics about the ontologies are reported in Table 1.
All tests were performed on a DELL Latitude E6320 notebook with Intel Core i7-2640M 2.8Ghz CPU and 4GB of RAM, running Microsoft Windows 7 Premium operating system, and Java 1.6 with 2GB of heap space. Classi cation timeout was set at one hour, and aborting if maximum available memory was exhausted. All gures reported in Table 2 are in seconds, and, because classi cation results are subject to minor uctuation, particularly when dealing with large ontologies, are the average of 3 classi cations of the respective ontologies with each reasoner. The following versions of the OWL reasoners were tested: Fact++ v.1.5.3, HermiT v.1.3.6, Pellet v.2.3.0, CB v.12, and ELK v.0.3.2.
In our test con guration, the classi cations of the FMA 2.0 ontology by the
Hermit and FaCT++ reasoners terminate due to an out-of-memory error. In [
The results of the experiments are summarized in Table 2. These results con rm that the performance o ered by QuOnto compares favorably to other reasoners for almost all tested ontologies. Classi cation for even the largest of the tested ontologies, i.e., the FMA-OBO and FMA 3.2.1 ontologies, is performed in under 5 seconds, and memory space issues were never experienced during our tests with QuOnto. For some test cases, the gap in performance between QuOnto and other reasoners is sizeable: for instance, classi cation by Pellet of the Galen and FMA (1.4 and 2.0) and by FaCT++ of the FMA (1.4 and OBO) ontologies exceeds the predetermined timeout limit of one hour.
Detailed analysis of the results provided in Table 2 shows that only the CB and ELK reasoners consistently display comparable performances to QuOnto, which is fastest for all ontologies which feature only positive inclusions, with the exception of the EL-Galen, Galen, and FMA-OBO ontologies. The CB reasoner, which is the best-performing reasoner for the Galen ontology, does not however always perform complete classi cation. For instance, it does not compute property hierarchies. The ELK reasoner instead is slower than QuOnto for three out of the ve ontologies also in OWL 2 EL, showing instead markedly better performance for EL-Galen.
Furthermore, if, as it is usually the case, an ontology does not present unsatis able predicates, the computation of such predicates through the exploration of all negative inclusions can be avoided. This is the case for ontologies such as DOLCE and AEO, for which computation of the set T of positive inclusion assertions resulting from the transitive closure of GT is performed respectively in 0.347 and 0.384 seconds, fastest among tested reasoners. Instead, for ontologies such as Pizza and Transportation, which feature respectively 2 and 62 unsatisable atomic concepts, the identi cation of all such predicates is unavoidable, and the resulting set of trivial inclusion assertions must be added to T . 5
The research presented in this paper can be extended in various directions. First of all, in the implementation of our technique we have adopted a naive algorithm for computing the digraph transitive closure. We are currently experimenting more sophisticated and e cient techniques for this task. We are also working to optimize the procedure through which we identify unsatis able predicates. Finally, we are working to extend our technique to compute all inclusions that are inferred by the TBox (which, in OWL 2 QL, are a nite number). In this respect, we notice that through GT it is already possible to obtain the classi cation of all basic concepts, basic roles, and attributes, and not only that of predicates in the signature, and that, with slight modi cations of computeUnsat, we can actually obtain the set of all negative inclusions inferred by an OWL 2 QL TBox. The remaining challenge is to devise an e cient mechanism to obtain all inferred positive inclusions involving quali ed existential roles and attribute domains. Acknowledgments. This research has been partially supported by the EU under FP7 project Optique (grant n. FP7-318338), and by the EU under FP7ICT project ACSI (grant no. 257593). 18. D. Lembo, V. Santarelli, and D. F. Savo. Graph-based Ontology Classi cation in
OWL 2 QL. In Proc. of ESWC 2013, 2013. (to appear). 19. C. Masolo, S. Borgo, A. Gangemi, N. Guarino, A. Oltramari, and L. Schneider. The wonderweb library of foundational ontologies and the DOLCE ontology. Technical Report D17, WonderWeb, 2002. 20. J. Mendez, A. Ecke, and A. Turhan. Implementing completion-based inferences for the EL-family. In Proc. of DL 2011, volume 745 of CEUR, ceur-ws.org, 2011. 21. B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz.
OWL 2 Web Ontology Language { Pro les (2nd edition). W3C Recommendation, World Wide Web Consortium, Dec. 2012. Available at http://www.w3.org/ TR/owl2-profiles/. 22. J. Rogers and A. Rector. The GALEN ontology. Medical Informatics Europe (MIE 96), pages 174{178, 1996. 23. E. Sirin, B. Parsia, B. C. Grau, A. Kalyanpur, and Y. Katz. Pellet: A practical
OWL-DL reasoner. J. of Web Semantics, 5(2):51{53, 2007. 24. D. Tsarkov and I. Horrocks. FaCT++ description dogic reasoner: System description. In U. Furbach and N. Shankar, editors, Proc. of IJCAR 2006, volume 4130 of LNCS, pages 292{297. Springer, 2006.