The canonical standard description logic reasoning service is classi cation, that is, the generation of the set of atomic subsumptions which are entailed by some ontology. While this consequence relation is well de ned and nite, there is signi cant variance in the composition of that set. For example, it is common (in tools and in discussion) to exclude some tautologies (e.g., A v >, A v A). While for many purposes such divergences are harmless, there are many for which precision about what appears in the classi cation is essential, for example, estimating di erences in logical content. In this paper, we propose de nitions for di erent types of nite entailment sets of an OWL ontology based on the transitive closure and transitive reduction of its asserted and inferred class graphs. The purpose of this work is to introduce a exible and extensible speci cation for selecting a particular set of entailments, with the aim of ensuring the correctness and replicability of OWL-based applications.
The Web Ontology Language OWL 2 DL is based on the expressive description
logic SROIQ [
The ontology editor Protege 42 for instance comes with a `selected entailments' tab which shows a list of atomic SubClassOf, SubPropertyOf and Type (class assertion) axioms. The tool also o ers the option to `Save inferred axioms as ontology' which saves asserted and inferred axioms as a new OWL ontology. Similarly, Top Braid Composer3 o ers to `Save [the] inference graph' as a new le. In all cases, it is not clear how the entailments are generated, what the selection criteria is for entailments (inferences), and how the user can modify the ontology to a ect these entailments. For example, given an ontology containing only subsumptions and equivalences between named classes, Protege 4 exports all direct and strict subsumptions between the classes, but o ers no options to export the indirect or non-strict subsumptions explicitly. Top Braid Composer, however, does not include (direct or indirect) atomic subsumptions at all in the exported `inference graph'.
Ontologies that are available on the web may be published as `compiled' versions, which include the ontology and its entailments of some description. The OWL version of the National Cancer Institute (NCI) Thesaurus, for example, `includes inferred relationships'.4 There is, however, no de nition of what is regarded as an inferred relationship, how these relationships are determined, and what the selection criteria is. This may leave users wondering what kinds of information they are dealing with, and what implications this has for their understanding of the ontology.
Analytical applications that are based on justi cations (minimal subsets of
the ontology that are su cient for the entailment to hold) extract the entailed
atomic subsumptions of an ontology and compute the justi cations therefore
[
The above examples demonstrate how the notion of entailments is widely used in OWL applications, however without a clear understanding of how the entailment relation relates to the set of axioms that is obtained from an ontology. In order to ensure the correctness and replicability of data based on the entailments of an ontology, it is necessary to explicitly specify which ( nite) subset of the set of all entailments should be extracted from the ontology. In this paper, we discuss the di erent aspects of extracting entailments of OWL ontologies and 2 http://protege.stanford.edu 3 http://topquadrant.com/products/TB Composer.html 4 http://evs.nci.nih.gov/ftp1/NCI Thesaurus/ReadMe.txt provide de nitions for practical entailment sets. We propose ways of dealing with imported entailments based on the justi cations for the entailment. Rather than providing an exhaustive de nition for all possible entailment sets of a SROIQ ontology, the focus of this paper is to encourage clarity when using the term `entailments' in the context of OWL ontology applications. 2 2.1
The OWL API5 provides the convenience class InferredOntologyGenerator, which allows users to ` ll' a new ontology with the desired type of entailments, such as inferred atomic SubClass axioms and ClassAssertions. By default, this method only retrieves the direct superclasses of a named class when using InferredSubClassOfAxiomGenerator. For each class that does not have any direct superclasses other than OWL:Thing, the reasoner returns a node labelled OWL:Thing. While this method provides a common basis for computing the inferred ontology, it does not o er any exibility for the user to specify which relationships should be included in the output. We propose the implementation of more speci c and exible entailment generation methods in the OWL API as an addition to or extension of existing methods, in order to allow users to conveniently extract clearly de ned nite entailment sets from an OWL ontology. 2.2
The OWL ontology editor Protege 4 provides a view of `selected entailments' of the ontology. As the editor o ers no further explanation to how these entailments were extracted in the classi cation process, this view does not support understanding of the ontology. It may even seem surprising to the end-user that some trivial axioms, such as A v OWL:Thing, are displayed in the panel while others are missing. A more detailed and modi able view could support users in exploring the class hierarchy when attempting to understand entailment relations in the ontology. 2.3
Explanation of entailments for the purpose of debugging a description logic
ontology has been the focus of research since the early applications of description
logics for modelling domain knowledge [
2.4
Analytical applications that consider the number and type of entailments in order to infer semantic ontology metrics bene t from clearly de ned entailment sets in two ways: rst, the basis of the measurements, i.e. what exactly is measured, is well de ned and transparent, therefore ensuring consistent measurements which are independent from a particular implementation or individual modi cations of the results provided by the OWL API. Second, greater exibility allows to extract entailments that are t for a speci c purpose. For instance, when describing the inferential power of an ontology, it is not necessary to consider the asserted entailments as they hold no information value. On the other hand, to explore the justi catory structure of an OWL ontology, we need to consider that there may be non-obvious and possibly complex reasons for entailments that are asserted in the ontology; this makes it necessary to compute the justi cations for both inferred and asserted entailments in order to capture these `hidden' justi cations. 3
In this section we present di erent criteria for de ning the set of entailments of an OWL ontology. We provide four de nitions for nite entailment sets based on the class graph of the ontology, which we then illustrate with examples. In each case, we expect the input to be an OWL 2 DL ontology O, with the output being a set of OWL 2 DL axioms . Please note that for the purpose of demonstrating our approach, we only focus on atomic entailments, i.e. relations between named atomic classes in the ontology. 3.1
In the remainder of this paper the letters A, B denote class names, C, D (possibly complex) concepts, a an individual, O = (T ,A) a description logic ontology which is the union of a TBox T and an ABox A, an axiom in O, and I = ( I ; I ) an interpretation of an ontology O. The notations for > and OWL:Thing, and ? and OWL:Nothing are used interchangeably.
The term nding entailments of a DL ontology summarises di erent reasoning tasks, such as the subsumption problem, equivalence and satis ability checking with respect to a TBox T , and instance checking with respect to an ABox A.
Entailment relations in SROIQ are de ned based on the formal semantics
given by an interpretation I [
Cat {Puma, MountainLion, Cougar}
Mammal
Cat
Animal {Puma, MountainLion, Cougar} NorthAmericanCougar
NorthAmericanCougar (a) Asserted Class Graph (b) Inferred Class Graph a is an instance of a concept C (O j= C(a)) if aI 2 CI for every model I of O. The set of entailments of an ontology is therefore the set of all axioms such that O j= . The asserted class graph of an ontology O is a labelled directed acyclic graph G = (V; E; L) with nodes labelled with (a non-empty set of) class names, including > and ?, from the signature of O. The graph is initialised by creating a node u for each class name in the signature of O, with the class name being in the label L(u) of the node. An edge (u; v) is added if it is asserted in O that A v B for some A 2 L(u), B 2 L(v), where A and B are class names, >, or ?. For any two nodes u, v in the graph with L(u) = fAg, L(v) = fBg, the nodes are collapsed into a single node w if the ontology contains the two subsumption axioms A v B and B v A, or the equivalence class axiom A B. This leads to existing edges (u; x), (v; y) for some node x, y in the graph, being replaced by the corresponding edges (w; x), (w; y).
The inferred class graph G0 = (V 0; E0; L0) of the ontology contains an edge (u; v) if O j= A v B for some A 2 L(u), B 2 L(v). A class name A is in the label L(u) of a node u in the inferred class graph if O j= A Bi for all Bi in L(u).
The asserted and inferred class graphs in Figure 1 are based on the following toy ontology:
NorthAmericanCougar v Cougar The inferred and asserted class graphs of an ontology are uniquely de ned. Retrieving these class graphs may be su cient for counting entailments, as every subsumption relationship between nodes is represented by a single edge, and the arity of a node label (i.e. the number of distinct class names in the node) is equal to the number of equivalent classes. OWL applications however generally present the asserted and inferred class hierarchy as sets of OWL axioms, which need to be generated from the relationships in the respective class graphs.
Generating axioms from the transitive closure of the inferred class graph is straightforward: a SubClassOf axiom is created for each pair of class names in the label of the sub- and superclass node respectively, and an EquivalentClasses axiom for each pair of class names in the label of a node. Example 2 demonstrates how this method can quickly lead to a large set of entailments. In some situations however it is su cient and more economical to use a subset of these relations based on the transitive reduction of the graph.
The transitive reduction of a directed acyclic graph is a canonical
representation for the paths in the graph [
For the purpose of expressing subsumptions in the transitive reduction, a function Rep(u) is introduced which selects a single class name from the label of a node u to act as a representative for the node. This function is intended to be user-de ned and may retrieve a randomly selected element, the rst element in a lexicographical ordering, or even a freshly generated class name (such as the concatenation of the class names in the node), to name a few examples.
In order to generate EquivalentClasses axioms from a node with arity n, where n > 2, we apply a function P airwise(u) to the node label. This introduces an ordering < on the class names in the label of the node (such as a lexicographical order) and returns a set of pairs of class names (Ai; Ai+1) where Ai < Ai+1. While OWL 2 allows EquivalentClasses axioms with an arity greater than two, we choose to express equivalences in binary axioms, which corresponds to the description logic notation of Ai Ai+1. While an unsatis able class is generally referred to as being a subclass of Bottom, the class is in fact equivalent to the bottom node OWL:Nothing, as discussed above. We consider this in our de nitions and treat an unsatis able named class not as a subsumption, but as an atomic equivalence. Likewise, a universal class, i.e. a class that is equivalent to OWL:Thing, is not treated as superclasses of Top, but as an equivalent class.
Furthermore, tautologies such as A v >, ? v A and A v A for all named classes A are not included in the entailment set, as they do not hold any information value. We de ne the set of inferred atomic entailments of an ontology O as the union of the inferred atomic subsumptions Sub and the inferred atomic equivalences Equiv for the asserted and inferred class graphs G = (V; E; L) and G0 = (V 0; E0; L0) respectively. The following de nitions are ordered by two aspects: whether they are based on the transitive closure T c(E0) or transitive reduction T r(E0) of the inferred class graph, and whether they include (A+) or exclude (A ) asserted subsumptions and equivalences respectively.
SubTcA+(O) :=fA v B j there is (u; v) 2 E0; A 2 L0(u); B 2 L0(v);
A 6= B; A 6= ?; B 6= >g EquivTcA+(O) :=fA
B j there is u 2 V 0; A; B 2 L0(u); A 6= Bg
SubTcA (O) :=fA v B j there is (u; v) 2 E0; A 2 L0(u); B 2 L0(v) (u; v) 62 E; A 6= B; A 6= ?; B 6= >g EquivTcA (O) :=fA there is no v 2 V s:t: A; B 2 L(v)g
B j there is u 2 V 0; A; B 2 L0(u); A 6= B;
SubTrA+(O) :=fA v B j there is (u; v) 2 T R(E0);
A = Rep(u); B = Rep(v); A 6= B; A 6= ?; B 6= >g EquivTrA+(O) :=fA
B j there is u 2 V 0; (A; B) 2 P airwise(u); A 6= Bg
SubTrA (O) :=fA v B j there is (u; v) 2 T R(E0);
A = Rep(u); B = Rep(v); (u; v) 62 E; A 6= B; A 6= ?; B 6= >g EquivTrA (O) :=fA
B j there is u 2 V 0; (A; B) 2 P airwise(u); A 6= B; there is no v 2 V s:t: A; B 2 L(v)g 3.6
The properties of di erent entailment sets are demonstrated using the above toy ontology as an example.
Cougar
MountainLion MountainLion
Puma Puma v Mammal MountainLion v Cat MountainLion v Animal Cougar v Mammal The transitive closure, including asserted, makes explicit the relationships between every single class in the ontology. It is the largest nite entailment set to be extracted from the class graph. The alternative variant of this set excluding asserted entailments simply discards the axioms that occur in the original ontology, yielding a set of 12 axioms.
NorthAmericanCougar v Cougar MountainLion Cat v Mammal
Puma
Cougar The entailment set based on the transitive reduction of the class graph uses representative elements from each node to produce a minimal representation of the class hierarchy. In this example, the function selects the class names that are asserted to be in SubClassOf relationships in the ontology, otherwise it selects a random class name from the node. The function P airwise(u) applies a lexicographical ordering on the class names in each node, as described above. Having translated the class graph into a set of OWL axioms based on the above de nitions, the number of entailments can be computed in an unambiguous way. By choosing a representative class name for each node in the transitive reduction, the number of entailed atomic subsumptions is equal to the number of edges in the graph, i.e. one edge in the graph is represented by one axiom.
For the transitive closure of the class graph, the number of entailed subsumption axioms is the sum of all n(u) n(v) for each edge (u; v) in the graph, with n(u) the number of class names in a node u. The number of entailed binary equivalence class axioms is n(u) (n(u) 1)=2 for each node u in the graph. We have implemented the entailment extractor methods using the OWL API.6 The code is intended to be used with any OWL reasoner that is compatible with the current version of the OWL API. Preliminary tests with large ontologies such as the NCI Thesaurus show that all types of entailment sets can be extracted in practical time. 4
Another issue that needs to be dealt with when extracting and counting entailments from an ontology is its import structure. An OWL ontology O (the `root' ontology) that imports another OWL ontology O' can have di erent kinds of entailments: those that hold in O n O' (native entailments), those that are entirely from the imported ontology, i.e. they hold in O' n O (imported entailments), and those that hold in O [ O' but not in O n O' (mixed entailments). When performing analytical tasks on the root ontology such as analysing its inferential power, it may be considered misleading to include the number of imported entailments. Furthermore, if the imported ontology itself imports another ontology (and so on), we will almost certainly obtain data that is not relevant to our original root ontology. While this may not be problematic for some tasks, the origin of entailments needs to be at least made obvious in a way such that the user can make their own judgements on how to handle them. 4.1
We propose a classi cation of these three types of entailments in an ontology
which is based on the notion of justi cations for an entailment. A justi cation is
a minimal subset of the ontology that is su cient for the entailment to hold [
http://code.google.com/p/owl-entailment-extractor. and modi cation at Type 1: Native entailments We may want to restrict the entailment extraction to the root ontology and discard all entailments that originate partly or entirely from the imported ontologies. In this case, the class graph construction and reasoning process is limited to the root ontology axioms only. Computing justi cations is not necessary for this type of entailments.
Type 2: Imported entailments While the entailments that originate purely from the imported ontology may not be relevant to application, an analysis of the type and numbers provides information about the computational overhead they may cause when not excluding them from the entailment set. Type 2 entailments are extracted by computing the inferred class graph for axioms that are contained in the imported ontology only. Computing justi cations is not necessary for this type of entailments.
Type 3: Mixed entailments In this type, we gather all entailments that are considered `mixed' for at least one of the following reasons: rst, an entailment that has at least one justi cation which contains axioms from both O and O' is considered mixed. Second, an entailment that has some justi cation that comprises axioms from O, and some justi cation that comprises axioms from O'.7 Type 3 entailments are computed by extracting all entailments from the union of the imports closure of the root ontology, then sequentially generating justications for these entailments. If the set of justi cations contains axioms from both the root and the import ontologies, the entailment is marked as `mixed' and no further justi cations need to be found. 5
Due to the ambiguous use of the term `entailments' in the OWL community, it is necessary to explicitly specify the selection criteria for entailments in both analytical and user-oriented applications. The methods for extracting entailments from OWL ontologies currently provided by the OWL API and ontology development tools provide little exibility and do not support understanding of the entailment relationships in the ontology. We have presented well-founded and extensible de nitions for di erent types of entailment sets of an OWL ontology, based on its class graph. Depending on the purpose, users can extract entailments from the transitive reduction or the transitive closure of the ontology, and decide whether the asserted entailments should be included. We have also introduced di erent ways of dealing with entailments that are partly or entirely caused by imported ontologies. The proposed methods o er exibility and transparency when handling entailments, which may support ontology understanding as well as clarify analytical tasks.
matter in the context of analysing the structure of justi cations in an ontology.
Thus far, we have discussed de nitions and examples for entailed subsumptions between atomic classes. In order to capture the wide range of entailments from an expressive description logic such as SROIQ and to provide extensive information about an ontology, these de nitions can be extended in two directions: rst, to cover the expressivity of OWL 2 DL ontologies beyond subsumptions between named classes, such as class assertions, object property hierarchies and data property hierarchies. Second, we may also want to capture non-atomic entailments, such as literals (disjointness of classes) and subsumptions and equivalences between complex class expressions (e.g. existential and universal restrictions on atomic class names). In the case of complex class expressions, it will be necessary to identify which complex entailments are of interest to users, depending on the needs of a particular application.