Skip to main content
Engineering LibreTexts

5.3: OWL 2

  • Page ID
    6423
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Over the past 16 years, OWL has been used across subject domains, but in the early years mostly by the health care and life sciences disciplines. Experimentation with the standard revealed expected as well as unexpected shortcomings in addition

    OWL Axiom DL Example
    SubClassOf \(C_{1}\sqsubseteq C_{2}\) \(\texttt{Human}\sqsubseteq\texttt{Animal}\sqcap\texttt{Biped}\)
    EquivalentClasses \(C_{1}\:\equiv\: ...\:\equiv\: C_{2}\) \(\texttt{Man}\equiv\texttt{Human}\sqcap\texttt{Male}\)
    SubPropertyOf \(P_{1}\sqsubseteq P_{2}\) \(\texttt{hasDaughter}\sqsubseteq\texttt{hasChild}\)
    EquivalentProperties \(P_{1}\:\equiv\: ...\:\equiv\: P_{2}\) \(\texttt{cost}\equiv\texttt{price}\)
    SameIndividual \(o_{1}\:\equiv\: ...\:\equiv\: o_{2}\) \(\texttt{President_Zuma}=\texttt{J_Zuma}\)
    DisjointClasses \(C_{i}\:\sqsubseteq\:\neg C_{j}\) \(\texttt{Male}\sqsubseteq\neg\texttt{Female}\)
    DifferentIndividuals \(o_{i}\neq o_{j}\) \(\texttt{Thabo}\neq\texttt{Andile}\)
    inverseOf \(P_{1}\:\equiv\:P^{-}_{2}\) \(\texttt{hasChild}\equiv\texttt{hasParent}^{-}\)
    transitiveProperty \(P^{+}\:\sqsubseteq\: P\)

    \(\texttt{ancestor}^{+}\:\sqsubseteq\:\texttt{ancestor,}\)

    denoted also as \(\texttt{Trans(ancestor)}\)

    symmetricProperty \(P\:\equiv\: P^{-}\) \(\texttt{Sym(connectedTo)}\)
    functionalProperty \(\top\sqsubseteq\leq 1P\) \(\top\sqsubseteq\leq\texttt{1hasPresident}\)
    inverseFunctionalProperty \(\top\sqsubseteq\leq 1P^{-}\) \(\top\sqsubseteq\leq\texttt{1hasIDNo}^{-}\)

    Table 4.2.1: Some examples of OWL’s axioms, the same in DL notation, and an example.

    to the ideas mentioned in the “Future extensions” section of [HPSvH03], so that a successor to OWL was deemed to be of value. Work towards a standardisation of an OWL 2 took shape after the OWL Experiences and Directions workshop in 2007 and a final draft was ready by late 2008. On October 27 2009 it became the official OWL 2 W3C recommendation4. What does OWL 2 consists of—new and improved!—and what does it fix with respect to the OWL standard of 2004? Let’s consider the answers to these questions in the remainder of this section.

    Limitations of OWL—As Experienced By The Practitioners

    OWL 2 aims to address the issues described in section 2 of [CGHM+08] to a greater or lesser extent, which is neither a superset nor subset of [HPSvH03]’s ideas for possible extensions. For instance, an OWL 1 possible future feature was catering for the Unique Name Assumption, but that did not make it into OWL 2, despite that it has quite an effect on the complexity of a language [ACKZ09]. We briefly summarize the interesting issues; refer to [CGHM+08] for details.

    Expressivity limitations. First, it is not possible to express qualified cardinality restrictions in OWL. For instance, one can state \(\texttt{Bicycle}\sqsubseteq\texttt{2 hasComponent.}\top\) or \(\texttt{Bicycle}\sqsubseteq\exists\texttt{hasComponent.Wheel}\), but not \(\texttt{Bicycle}\sqsubseteq\geq\texttt{2 hasComponent.Wheel}\). This was deemed an important shortcoming in OWL DL by its modelers. Second, some relational properties were perceived to be missing, notably reflexivity and irreflexivity, so one could not represent the class Narcissist (someone who loves him/herself), and not state that proper parthood is irreflexive, yet an irreflexive partOf relation is import in medicine and biology. Third, there were also limitations on data types; e.g., one cannot express restrictions to a subset of datatype values (ranges) and relationships between values of data properties on one object. Last, there were also some ‘housekeeping’ features missing, such as annotations, imports, versioning, and species validation (see p315 of [CGHM+08] for details).

    Syntax problems. OWL has both a frame-based legacy (Abstract syntax) and axioms (DL), which was deemed too confusing. For instance, take the following axiom:

    \(texttt{Class(A partial restriction(hasB someValuesFrom(C))}\)

    What type of ontology elements do we have? Is hasB is data property and C a datatype, or is hasB an object property and C a class? OWL-DL has a strict separation of the vocabulary, but the specification does not precisely specify how to enforce this separation at the syntactic level. In addition, RDF’s triple notation is difficult to read and process.

    Problems with the semantics. We shall not cover this issue. (For the curious: this has to do with RDF’s blank nodes, but unnamed individuals not directly available in \(\mathcal{SHOIN (D)}\), and frames and axioms).

    Overview of OWL 2

    Complex systems have a tendency to become more, rather than less, complex, and so it is for OWL 2, mainly regarding new features and more new languages. First, have a look at the ‘orchestration’ of the various aspects of OWL 2 in Figure 4.2.1. The top section indicates several syntaxes that can be used to serialize the ontology, where RDF/XML is required and the other four are optional. There are mappings between an OWL ontology and RDF graph in the middle, and the lower half depicts that there is both a direct semantics, for OWL 2 DL-based species, and an RDFbased one, for OWL 2 full. Note that while that “mapping” between “ontology structure” and “RDF Graph” and that “correspondence theorem” between “Direct semantics” and “RDF-based semantics” exist, this does not mean they’re all the same thing. The DL-based OWL 2 species have a mapping into RDF for the serialization, but they do not have an RDF-based semantics.

    Second, the OWL 2 DL species is based on the DL \(\mathcal{SROIQ(D)}\) [HKS06]. It is more expressive than the underlying DL of OWL DL \(\mathcal{(SHOIN (D)) }\)and therewith meeting some of the modellers’ requests, such as more properties of properties and qualified number restrictions (see below). There is cleaner support for annotations, debatable (from an ontological perspective, that is) punning for metamodeling, and a ‘key’ that is not a key in the common sense of keys in conceptual data models and databases. Also, it irons out some difficulties that tool implementers had with the syntaxes of OWL and makes importing ontologies more transparent.

    Third, there are three OWL 2 profiles, which are sub-languages of (syntactic restrictions on) OWL 2 DL so as to cater for different purposes of ontology usage in applications. At the time of standardization, they already enjoyed a considerable user base. This choice has its consequences that very well can, but may not necessarily, turn out to be a positive one in praxis; this will be explored further in the block on ontology engineering. The three profiles are:

    • OWL 2 EL which is based on the \(\mathcal{EL}^{++}\) language [BBL05], intended for use with large relatively simple type-level ontologies;
    • OWL 2 QL, which is is based on the \(DL-Lite_{R}\) language [CGL+07], intended for handling and querying large amounts of instances through the ontology;

    Screenshot (69).png

    Figure 4.2.1: Orchestration of syntax and semantics of OWL 2. (Source: http://www.w3.org/TR/2009/REC-owl2-overview-20091027/).

    • OWL 2 RL, which is inspired by Description Logic Programs and pD, intended for ontologies with rules and data in the form of RDF triples.

    Like with OWL 2 DL, each of these languages has automated reasoners tailored to the language so as to achieve the best performance for the application scenario. Indirectly, the notion of the profiles and automated reasoners says you cannot have both many modeling features together in one language and expect to have good performance with the ontology and ontology-driven information system. Such is life with the limitations of computers, but one can achieve quite impressive results with the languages and its tools that are practically not really doable with paper-based manual efforts.

    New OWL 2 Features

    OWL 2 DL is based on \(\mathcal{SROIQ(D)}\) [HKS06], which we have seen in Chapter 3, which is 2NExpTime-complete in taxonomic complexity [Kaz08]; hence, it is a more expressive language than OWL-DL (\(\mathcal{SHOIN}\), which is NExpTime-complete [Tob01]). Compared to OWL DL, it has fancier metamodeling and annotations, improved ontology publishing, imports and versioning control. In addition to all the OWL-DL features (recall Section 4.1: Standardizing an Ontology Lanugage "The OWL 1 Family of Languages"), one can use the following ones in OWL 2 DL as well, which are illustrated afterwards:

    • Qualified cardinality restrictions, \(\geq nR.C\) and \(\leq nR.C\) (the \(\mathcal{Q}\) in \(\mathcal{SROIQ}\)):

    – \((\geq nR.C)^{\mathcal{I}}= \{x |\sharp \{ y | (x, y)\in R^{\mathcal{I}}\cap y\in C^{\mathcal{I}}\}\geq n\}\)

    In OWL 2: ObjectMinCardinality(n OPE CE); an example in DL notation: \(\geq\texttt{3 hasPart.Door}\)

    – \((\leq nR.C)^{\mathcal{I}} = \{x |\sharp\{y | (x, y)\in R^{\mathcal{I}}\cap y\in C^{\mathcal{I}}\}\leq n\}\)

    In OWL 2: ObjectMaxCardinality(n OPE CE), an example in DL notation: \(\leq\texttt{2 enrolledIn.UGDegree}\)

    – The difference between the unqualified cardinality constraint (the \(\mathcal{N}\) in OWL DL’s \(\mathcal{SHOIN}\)) and qualified cardinality constraint (the \(\mathcal{Q}\) in OWL 2 DL’s \(\mathcal{SROIQ}\)) is the difference between aforementioned \(\texttt{Bicycle}\sqsubseteq\geq\texttt{2 hasComponent.}\top\) and \(\texttt{Bicycle}\sqsubseteq\geq\texttt{2 hasComponent.Wheel}\), respectively.

    • Properties of roles (the \(\mathcal{R}\) in \(\mathcal{SROIQ}\)):

    – Reflexive (globally): \(\texttt{Ref}(R)\), with semantics:

    \(\forall x : x\in\Delta^{\mathcal{I}}\) implies \((x, x)\in (R)^{\mathcal{I}}\)

    Example: the connection relation (everything is connected to itself).

    – Reflexive (locally):

    \(\exists R.\texttt{Self}\), with semantics:

    \(\{x | (x, x)\in R\}\)

    In OWL 2: ObjectHasSelf (OPE); e.g., \(\exists\texttt{knows.Self}\) to state you know yourself.

    – Irreflexive: \(\texttt{Irr}(R)\), with semantics:

    \(\forall x : x\in\Delta^{\mathcal{I}}\) implies \((x, x)\notin (R)^{\mathcal{I}}\)

    For instance, proper parthood is irreflexive: something cannot be proper part of itself.

    – Asymmetric: \(\texttt{Asym}(R)\), with semantics:

    \(\forall x, y : (x, y)\in (R)^{\mathcal{I}}\) implies \((y, x)\notin (R)^{\mathcal{I}}\)

    For instance, Asym(parentOf): if John is the parent of Divesh, then Divesh cannot be the parent of John.

    • Limited role chaining (also covered with the \(\mathcal{R}\) in \(\mathcal{SROIQ}\)): e.g., \(R\circ S\sqsubseteq R\), with semantics: \(\forall y_{1}, . . . , y_{4} : (y_{1}, y_{2})\in (R)^{\mathcal{I}}\) and \((y_{3}, y_{4})\in (S)^{\mathcal{I}}\) imply \((y_{1}, y_{4})\in (R)^{\mathcal{I}}\), and regularity restriction (strict linear order (“\(<\)”) on the properties). For instance: \(\texttt{childOf}\circ\texttt{childOf}\sqsubseteq\texttt{grandchildOf}\) so that one can deduce that the child of a child is that person’s grandchild, and the uncle example in Chapter 3.

    The tricky part especially in practical ontology development is that some object property features and axioms work only on simple object properties, ‘simple’ meaning that it has no direct or indirect subproperties that are either transitive or are defined by means of property chains; see section 11.1 of the OWL Structural Specification and Functional-Style Syntax for the exact specification of this limitation. Practically, this means that the following features can be used only on simple object properties: ObjectMinCardinality, ObjectMaxCardinality, ObjectExactCardinality, ObjectHasSelf, FunctionalObjectProperty, InverseFunctionalObjectProperty, IrreflexiveObjectProperty, AsymmetricObjectProperty, and DisjointObjectProperties. Two examples of what this concretely means when you’re trying to develop an ontology are illustrated next.

    Example \(\PageIndex{1}\):

    In the first example, the ontologist has to choose between transitivity or qualified number restrictions, but cannot have both. This gives a modeler options within OWL 2 DL, using cake with its ingredients as example:

    1. Cake has ingredient any number of Edible substances and one would be able to infer that if Milk is an ingredient of Butter that is an ingredient of Cake, then Milk is an ingredient of Cake; i.e., hasIngredient and its inverse, ingredientOf is transitive; or
    2. a (standard) Cake has ingredients at least four Edible substances, but it cannot be inferred that the Milk is an ingredient of the Cake; i.e., hasIngredient participates in a qualified number restriction.

    Another modelling trade-off is the following one. Alike the uncle example in Chapter 3, one can specify a role chain for aunts, e.g.: \(\texttt{hasMother}\circ\texttt{hasSister}\sqsubseteq\texttt{hasAunt}\). It certainly holds that hasMother is asymmetric (your mother cannot be your child), i.e., Asym(hasMother). Each axiom can be represented in an OWL 2 DL ontology, yet, one cannot assert both the property chain and antisymmetry in the same OWL 2 DL ontology.

    The ontology development environment probably will warn you about such syntax violations, and will prevent you from running the reasoner. It may say something cryptic like “internal reasoner error” and the log file will have an entry returned by the OWL API with the offending axioms, along the line of:

    \(\texttt{An error occurred during reasoning: Non-simple property ’<ex#hasIngredient>’ or its inverse appears in the cardinality restriction 'ObjectMax}\)

    \(\texttt{ Cardinality(4 <ex#hasIngredient> <ex# EdibleSubstance>)' }\)

    where the ex is the ontology’s URI. If it happens, you will have to decide which of the two axioms is the more important one to keep, or choose another, more expressive, logic beyond OWL 2 DL. One ‘way out’ to this problem will pass the revue in Section 4.3:OWL in Context "The Distributed ontology, model, and specification language DOL".

    OWL 2 Profiles

    The main rationale for the profiles are computational complexity considerations and robustness of implementations with respect to scalable applications. Their features are summarized here. Note that you are not expected to learn the following lists of features by heart (it can be used as a quick ‘cheat sheet’), but you do need to know, at least, their intended purpose. The more you practice developing ontologies, the easier it becomes to remember them. To assist with grasping language features actually used in a particular ontology—be it the three OWL 1 species or the five OWL 2 species—the OWL Classifier can be used. It lists in which OWL species one’s OWL ontology is and why it violates the other species (i.e., creates a justification of the reported expressivity)5 , and therewith provides features that are not available in currently popular ontology editors such as Protégé.

    OWL 2 EL

    OWL 2 EL is intended for large ‘simple’ ontologies and focuses on type-level knowledge (TBox). It has a better computational behavior than OWL 2 DL . It is based on the DL language \(\mathcal{EL}^{++}\) (PTime complete), and it is used for the large medical terminology SNOMED CT [SNO12], among others. The listing of OWL 2 EL features is included in Appendix B.

    OWL 2 QL

    OWL 2 QL aims at scenarios for query answering over a large amount of instances with the same kind of performance as relational databases (Ontology-Based Data Access; see Chapter 8). Its expressive features cover several used features of UML Class diagrams and ER models. It is based on \(DL-Lite_{\mathcal{R}}\) (though more is possible with the Unique Name Assumption and in some implementations).

    The supported axioms in OWL 2 QL take into account what one can use on the left-hand side of the inclusion operator (\(\sqsubseteq\), SubClassOf) and what can be asserted on the right-hand side, which turns it into a fairly long list due to the intricate exclusions. The listing of OWL 2 QL features is included in Appendix B.

    OWL 2 RL

    OWL 2 RL’s development was motivated by what fraction of OWL 2 DL can be expressed by rules (with equality) and scalable reasoning in the context of RDF(S) application. It uses rule-based technologies (forward chaining rule system, over instances) and is inspired by Description Logic Programs and pD\(^{*}\). Reasoning in PTime.

    The list of features supported in OWL 2 RL is easily specified:

    – More restrictions on class expressions (see table 2 of [MGH+09]; e.g., no SomeValuesFrom on the right-hand side of a subclass axiom)

    – All axioms in OWL 2 RL are constrained in a way that is compliant with the restrictions in Table 4.2.1.

    – Thus, OWL 2 RL supports all axioms of OWL 2 apart from disjoint unions of classes and reflexive object property axioms.

    A quick one-liner of the difference with OWL 2 DL is: No \(\forall\) and \(\neg\) on the left-hand side, and \(\exists\) and \(\sqcup\) on right-hand side of \(\sqsubseteq\).

    OWL 2 Syntaxes

    There are more syntaxes for OWL 2 than for OWL, as we have see in Figure 4.2.1. Consider the DL axiom

    \(\texttt{FirstYearCourse}\sqsubseteq\forall\texttt{isTaughtBy.Professor}\)

    Rendering this in RDF/XML yields:

    <!–– http://www.semanticweb.org/ontologies/2017/6/exOKB17.owl#FirstYearCourse −−>
    <owl:Class rdf:about=”&exOKB17;FirstYearCourse”>
        <rdfs:subClassOf rdf:resource=”&owl;Thing”/>
        <rdfs:subClassOf>
            <owl:Restriction>
                <owl:onProperty rdf:resource=”&exOKB17;isTaughtBy”/>
                <owl:allValuesFrom rdf:resource=”&exOKB17;Professor”/>
            </owl:Restriction>
        </rdfs:subClassOf>
    </owl:Class>
    

    This RDF/XML fragment tells us that the ontology is called exOKB17 (abbreviated name for the full URI), FirstYearCourse is a subClassOf the root-class Thing, and a subclass of the restriction on FirstYearCourse, being that the restriction is owl:onProperty object property isTaughtBy and the ‘filler’, i.e., to which the restriction applies, is allValuesFrom (i.e., \(\forall\)) Professor.

    In OWL/XML (also not intended for human consumption), we have the same as follows:

    <SubClassOf>
        <Class IRI=”#FirstYearCourse”/>
        <Class abbreviatedIRI=”owl:Thing”/>
    </SubClassOf>
    <SubClassOf>
        <Class IRI=”#FirstYearCourse”/>
        <ObjectAllValuesFrom>
            <ObjectProperty IRI=”#isTaughtBy”/>
            <Class IRI=”#Professor”/>
        </ObjectAllValuesFrom>
    </SubClassOf>
    

    The functional syntax equivalent is as follows:

    Declaration(Class(:FirstYearCourse))
    SubClassOf(:FirstYearCourse owl:Thing)
    SubClassOf(:FirstYearCourse ObjectAllValuesFrom(:isTaughtBy :Professor))
    

    The Manchester syntax rendering is intended exceedingly for human reading, for non-logicians, and for ease of communication in, say, emails that do not render mathematical symbols well. On the one hand, there is a Prot´eg´e-generated Manchester syntax rendering:

    Class: <http://www.semanticweb.org/ontologies/2017/6/exOKB17.owl#FirstYearCourse>
    
        SubClassOf: 
            owl:Thing,
            <http://www.semanticweb.org/ontologies/2017/6/exOKB17.owl#isTaughtBy> only
                <http://www.semanticweb.org/ontologies/2017/6/exOKB17.owl#Professor>
    

    But this usually gets abbreviated as follows:

    Class: FirstYearCourse
    SubClassOf:
        owl:Thing, 
        isTaughtBy only Professor
    

    or, even shorter:

    FirstYearCourse SubClassOf isTaughtBy only Professor
    

    There are several really non-standard representations of OWL ontologies for various reasons, such as interface design and making it easier for non-logicians to contribute to ontology development. For instance, in pseudo-natural language (which is a topic of Chapter 9), and graphical renderings, like with Ontograf and depicted in Figure 4.2.2, where the axiom shows when hovering over the coloured line representing the object property. These informal variants are all ‘syntactic sugar’ renderings of the ontology.

    Screenshot (70).png

    Figure 4.2.2: Screenshot of the \(\texttt{FirstYearCourse}\sqsubseteq\forall\texttt{isTaughtBy.Professor}\) in the Ontograf plugin for the Protégé ontology development environment; the axiom appears when hovering over the coloured dashed line representing the object property.

    Complexity Considerations for OWL

    We have seen different ‘species’ of OWL, which have more or less language features, and that this was motivated principally by scalability issues of the very expressive languages. Different languages/problems have different complexity (NP-complete, PSPACE, EXPTIME etc.). Appendix C contains a very brief recap on computational complexity, whereas here we jump straight to the specifics for OWL.

    In this setting of ontologies, we are interested in the following reasoning problems: ontology consistency, class expression satisfiability, class expression subsumption, instance checking, and (Boolean) conjunctive query answering (recall Section 3.3: Reasoning Services). When evaluating complexity, the following parameters are considered (copied from a section in the OWL 2 Profiles standard [MGH+09]):

    • Data Complexity: the complexity measured with respect to the total size of the assertions in the ontology.
    • Taxonomic Complexity: the complexity measured with respect to the total size of the axioms in the ontology.
    • Query Complexity: the complexity measured with respect to the total size of the query.
    • Combined Complexity: the complexity measured with respect to both the size of the axioms, the size of the assertions, and, in the case of conjunctive query answering, the size of the query as well.
    Language Reasoning Problems Taxonomic Complexity Data Complexity Query Complexity Combined Complexity
    OWL 2 RDF-Based Semantics Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking, Conjunctive Query Answering Undecidable Undecidable Undecidable Undecidable
    OWL 2 Direct Semantics
    • Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking
    • Conjunctive Query Answering
    • 2NEXPTIME-complete (NEXPTIME if property hierarchies are bounded)
    • Decidability open
    • Decidable, but complexity open (NP-Hard)
    • Decidability open
    • Not Applicable
    • Decidability open
    • 2NEXPTIMEcomplete (NEXPTIME if property hierarchies are bounded)
    • Decidability open
    OWL 2 EL
    • Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking
    • Conjunctive Query Answering
    • PTIME-complete
    • PTIME-complete
    • PTIME-complete
    • PTIME-complete
    • Not Applicable
    • NP-Complete
    • PTIME-complete
    • PSPACE-Complete
    OWL 2 QL
    • Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking,
    • Conjunctive Query Answering
    • NLogSpace-complete
    • NLogSpace-complete
    • in AC0
    • in AC0
    • Not Applicable
    • NP-complete
    • NLogSpace-complete
    • NP-complete
    OWL 2 RL
    • Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking,
    • Conjunctive Query Answering
    • PTIME-complete
    • PTIME-complete
    • PTIME-complete
    • PTIME-complete
    • Not Applicable
    • NP-complete
    • PTIME-complete
    • NP-complete
    OWL DL
    • Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking,
    • Conjunctive Query Answering
    • NEXPTIME-complete
    • Decidability open
    • Decidable, but complexity open (NP-Hard)
    • Decidability open
    • Not Applicable
    • Decidability open
    • NEXPTIME-complete
    • Decidability open

    Table 4.2.3: Complexity of OWL species (Source: [MGH +09]).

    Table 4.2.3 summarizes the known complexity results for OWL 2 under both RDF and the direct semantics, OWL 2 EL, OWL 2 QL, OWL 2 RL, and OWL 1 DL. The results refer to the worst-case complexity of these reasoning problems and, as such, do not say that implemented algorithms necessarily run in this class on all input problems, or what space/time they use on some/typical/certain kind of problems.

    For X-complete problems, these results only say that a reasoning algorithm cannot use less time/space than indicated by this class on all input problems, where “X” is one of the complexity classes listed in the previous section.


    This page titled 5.3: OWL 2 is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Maria Keet via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?