Profiles

Editors

Boris Motik, University of Oxford

Bernardo Cuenca Grau, University of Oxford

Ian Horrocks, University of Oxford

Zhe Wu, Oracle

Achille Fokoue, IBM Corporation

Carsten Lutz, University of Bremen

Contributors (alphabetical order)

Diego Calvanese, Free University of Bozen-Bolzano

Jeremy Carroll, HP (now at TopQuadrant)

Giuseppe De Giacomo, Sapienza Università di Roma

Jim Hendler, Rensselaer Polytechnic Institute

Ivan Herman, W3C/ERCIM

Bijan Parsia, University of Manchester

Peter F. Patel-Schneider, Nuance Communications

Alan Ruttenberg, Science Commons (Creative Commons)

Uli Sattler, University of Manchester

Michael Schneider, FZI Research Center for Information Technology

1 Introduction

An OWL 2 profile (commonly called a fragment or a sublanguage in computational logic) is a trimmed down version of OWL 2 that trades some expressive power for the efficiency of reasoning. This document describes three profiles of OWL 2, each of which achieves efficiency in a different way and is useful in different application scenarios. The profiles are independent of each other, so (prospective) users can skip over the descriptions of profiles that are not of interest to them. The choice of which profile to use in practice will depend on the structure of the ontologies and the reasoning tasks at hand (see Section 10 of the OWL 2 Primer [OWL 2 Primer] for more help in understanding and selecting profiles).

• OWL 2 EL is particularly useful in applications employing ontologies that contain very large numbers of properties and/or classes. This profile captures the expressive power used by many such ontologies and is a subset of OWL 2 for which the basic reasoning problems can be performed in time that is polynomial with respect to the size of the ontology [EL++] (see Section 5 for more information on computational complexity). Dedicated reasoning algorithms for this profile are available and have been demonstrated to be implementable in a highly scalable way. The EL acronym reflects the profile's basis in the EL family of description logics [EL++], logics that provide only Existential quantification.
• OWL 2 QL is aimed at applications that use very large volumes of instance data, and where query answering is the most important reasoning task. In OWL 2 QL, conjunctive query answering can be implemented using conventional relational database systems. Using a suitable reasoning technique, sound and complete conjunctive query answering can be performed in LOGSPACE with respect to the size of the data (assertions). As in OWL 2 EL, polynomial time algorithms can be used to implement the ontology consistency and class expression subsumption reasoning problems. The expressive power of the profile is necessarily quite limited, although it does include most of the main features of conceptual models such as UML class diagrams and ER diagrams. The QL acronym reflects the fact that query answering in this profile can be implemented by rewriting queries into a standard relational Query Language.
• OWL 2 RL is aimed at applications that require scalable reasoning without sacrificing too much expressive power. It is designed to accommodate OWL 2 applications that can trade the full expressivity of the language for efficiency, as well as RDF(S) applications that need some added expressivity. OWL 2 RL reasoning systems can be implemented using rule-based reasoning engines. The ontology consistency, class expression satisfiability, class expression subsumption, instance checking, and conjunctive query answering problems can be solved in time that is polynomial with respect to the size of the ontology. The RL acronym reflects the fact that reasoning in this profile can be implemented using a standard Rule Language.

OWL 2 profiles are defined by placing restrictions on the structure of OWL 2 ontologies. Syntactic restrictions can be specified by modifying the grammar of the functional-style syntax [OWL 2 Specification] and possibly giving additional global restrictions. In this document, the modified grammars are specified in two ways. In each profile definition, only the difference with respect to the full grammar is given; that is, only the productions that differ from the functional-style syntax are presented, while the productions that are the same as in the functional-style syntax are not repeated. Furthermore, the full grammar for each of the profiles is given in the Appendix. Note that none of the profiles is a subset of another.

An ontology in any profile can be written into an ontology document by using any of the syntaxes of OWL 2.

Apart from the ones specified here, there are many other possible profiles of OWL 2 — there are, for example, a whole family of profiles that extend OWL 2 QL. This document does not list OWL Lite [OWL 1 Reference]; however, all OWL Lite ontologies are OWL 2 ontologies, so OWL Lite can be viewed as a profile of OWL 2. Similarly, OWL 1 DL can also be viewed as a profile of OWL 2.

The italicized keywords MUST, MUST NOT, SHOULD, SHOULD NOT, and MAY are used to specify normative features of OWL 2 documents and tools, and are interpreted as specified in RFC 2119 [RFC 2119].

2 OWL 2 EL

The OWL 2 EL profile [EL++,EL++ Update] is designed as a subset of OWL 2 that

• is particularly suitable for applications employing ontologies that define very large numbers of classes and/or properties,
• captures the expressive power used by many such ontologies, and
• for which ontology consistency, class expression subsumption, and instance checking can be decided in polynomial time.

For example, OWL 2 EL provides class constructors that are sufficient to express the very large biomedical ontology SNOMED CT [SNOMED CT].

2.1 Feature Overview

OWL 2 EL places restrictions on the type of class restrictions that can be used in axioms. In particular, the following types of class restrictions are supported:

• existential quantification to a class expression (ObjectSomeValuesFrom) or a data range (DataSomeValuesFrom)
• existential quantification to an individual (ObjectHasValue) or a literal (DataHasValue)
• self-restriction (ObjectHasSelf)
• enumerations involving a single individual (ObjectOneOf) or a single literal (DataOneOf)
• intersection of classes (ObjectIntersectionOf) and data ranges (DataIntersectionOf)

OWL 2 EL supports the following axioms, all of which are restricted to the allowed set of class expressions:

• class inclusion (SubClassOf)
• class equivalence (EquivalentClasses)
• class disjointness (DisjointClasses)
• object property inclusion (SubObjectPropertyOf) with or without property chains, and data property inclusion (SubDataPropertyOf)
• property equivalence (EquivalentObjectProperties and EquivalentDataProperties),
• transitive object properties (TransitiveObjectProperty)
• reflexive object properties (ReflexiveObjectProperty)
• domain restrictions (ObjectPropertyDomain and DataPropertyDomain)
• range restrictions (ObjectPropertyRange and DataPropertyRange)
• assertions (SameIndividual, DifferentIndividuals, ClassAssertion, ObjectPropertyAssertion, DataPropertyAssertion, NegativeObjectPropertyAssertion, and NegativeDataPropertyAssertion)
• functional data properties (FunctionalDataProperty)
• keys (HasKey)

The following constructs are not supported in OWL 2 EL:

• universal quantification to a class expression (ObjectAllValuesFrom) or a data range (DataAllValuesFrom)
• cardinality restrictions (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality, DataMaxCardinality, DataMinCardinality, and DataExactCardinality)
• disjunction (ObjectUnionOf, DisjointUnion, and DataUnionOf)
• class negation (ObjectComplementOf)
• enumerations involving more than one individual (ObjectOneOf and DataOneOf)
• disjoint properties (DisjointObjectProperties and DisjointDataProperties)
• irreflexive object properties (IrreflexiveObjectProperty)
• inverse object properties (InverseObjectProperties)
• functional and inverse-functional object properties (FunctionalObjectProperty and InverseFunctionalObjectProperty)
• symmetric object properties (SymmetricObjectProperty)
• asymmetric object properties (AsymmetricObjectProperty)

2.2 Profile Specification

The following sections specify the structure of OWL 2 EL ontologies.

2.2.1 Entities

Entities are defined in OWL 2 EL in the same way as in the structural specification [OWL 2 Specification], and OWL 2 EL supports all predefined classes and properties. Furthermore, OWL 2 EL supports the following datatypes:

• rdf:PlainLiteral
• rdf:XMLLiteral
• rdfs:Literal
• owl:real
• owl:rational
• xsd:decimal
• xsd:integer
• xsd:nonNegativeInteger
• xsd:string
• xsd:normalizedString
• xsd:token
• xsd:Name
• xsd:NCName
• xsd:NMTOKEN
• xsd:hexBinary
• xsd:base64Binary
• xsd:anyURI
• xsd:dateTime
• xsd:dateTimeStamp

The set of supported datatypes has been designed such that the intersection of the value spaces of any set of these datatypes is either empty or infinite, which is necessary to obtain the desired computational properties [EL++]. Consequently, the following datatypes MUST NOT be used in OWL 2 EL: xsd:double, xsd:float, xsd:nonPositiveInteger, xsd:positiveInteger, xsd:negativeInteger, xsd:long, xsd:int, xsd:short, xsd:byte, xsd:unsignedLong, xsd:unsignedInt, xsd:unsignedShort, xsd:unsignedByte, xsd:language, and xsd:boolean.

Finally, OWL 2 EL does not support anonymous individuals.

2.2.2 Property Expressions

Inverse properties are not supported in OWL 2 EL, so object property expressions are restricted to named properties. Data property expressions are defined in the same way as in the structural specification [OWL 2 Specification].

2.2.3 Class Expressions

In order to allow for efficient reasoning, OWL 2 EL restricts the set of supported class expressions to ObjectIntersectionOf, ObjectSomeValuesFrom, ObjectHasSelf, ObjectHasValue, DataSomeValuesFrom, DataHasValue, and ObjectOneOf containing a single individual.

2.2.4 Data Ranges

A data range expression is restricted in OWL 2 EL to the predefined datatypes admitted in OWL 2 EL, intersections of data ranges, and to enumerations of literals consisting of a single literal.

2.2.5 Axioms

The class axioms of OWL 2 EL are the same as in the structural specification [OWL 2 Specification], with the exception that DisjointUnion is disallowed. Different class axioms are defined in the same way as in the structural specification [OWL 2 Specification], with the difference that they use the new definition of ClassExpression.

OWL 2 EL supports the following object property axioms, which are defined in the same way as in the structural specification [OWL 2 Specification], with the difference that they use the new definition of ObjectPropertyExpression.

OWL 2 EL provides the same axioms about data properties as the structural specification [OWL 2 Specification] apart from DisjointDataProperties.

The assertions in OWL 2 EL, as well as all other axioms, are the same as in the structural specification [OWL 2 Specification], with the difference that class object property expressions are restricted as defined in the previous sections.

2.2.6 Global Restrictions

OWL 2 EL extends the global restrictions on axioms from Section 11 of the structural specification [OWL 2 Specification] with an additional condition [EL++ Update]. In order to define this condition, the following notion is used.

The set of axioms Ax imposes a range restriction to a class expression CE on an object property OP₁ if Ax contains the following axioms, where k ≥ 1 is an integer and OP_i are object properties:

The axiom closure Ax of an OWL 2 EL ontology MUST obey the restrictions described in Section 11 of the structural specification [OWL 2 Specification] and, in addition, if

• Ax contains SubObjectPropertyOf( ObjectPropertyChain( OP₁ ... OP_n ) OP ) and
• Ax imposes a range restriction to some class expression CE on OP

then Ax MUST impose a range restriction to CE on OP_n.

This additional restriction is vacuously true for each SubObjectPropertyOf axiom in which in the first item of the previous definition does not contain a property chain. There are no additional restrictions for range restrictions on reflexive and transitive roles — that is, a range restriction can be placed on a reflexive and/or transitive role provided that it satisfies the previously mentioned restriction.

3 OWL 2 QL

The OWL 2 QL profile is designed so that sound and complete query answering is in LOGSPACE (more precisely, in AC⁰) with respect to the size of the data (assertions), while providing many of the main features necessary to express conceptual models such as UML class diagrams and ER diagrams. In particular, this profile contains the intersection of RDFS and OWL 2 DL. It is designed so that data (assertions) that is stored in a standard relational database system can be queried through an ontology via a simple rewriting mechanism, i.e., by rewriting the query into an SQL query that is then answered by the RDBMS system, without any changes to the data.

OWL 2 QL is based on the DL-Lite family of description logics [DL-Lite]. Several variants of DL-Lite have been described in the literature, and DL-Lite_R provides the logical underpinning for OWL 2 QL. DL-Lite_R does not require the unique name assumption (UNA), since making this assumption would have no impact on the semantic consequences of a DL-Lite_R ontology. More expressive variants of DL-Lite, such as DL-Lite_A, extend DL-Lite_R with functional properties, and these can also be extended with keys; however, for query answering to remain in LOGSPACE, these extensions require UNA and need to impose certain global restrictions on the interaction between properties used in different types of axiom. Basing OWL 2 QL on DL-Lite_R avoids practical problems involved in the explicit axiomatization of UNA. Other variants of DL-Lite can also be supported on top of OWL 2 QL, but may require additional restrictions on the structure of ontologies.

3.1 Feature Overview

OWL 2 QL is defined not only in terms of the set of supported constructs, but it also restricts the places in which these constructs are allowed to occur. The allowed usage of constructs in class expressions is summarized in Table 1.

OWL 2 QL supports the following axioms, constrained so as to be compliant with the mentioned restrictions on class expressions:

• subclass axioms (SubClassOf)
• class expression equivalence (EquivalentClasses)
• class expression disjointness (DisjointClasses)
• inverse object properties (InverseObjectProperties)
• property inclusion (SubObjectPropertyOf not involving property chains and SubDataPropertyOf)
• property equivalence (EquivalentObjectProperties and EquivalentDataProperties)
• property domain (ObjectPropertyDomain and DataPropertyDomain)
• property range (ObjectPropertyRange and DataPropertyRange)
• disjoint properties (DisjointObjectProperties and DisjointDataProperties)
• symmetric properties (SymmetricObjectProperty)
• reflexive properties (ReflexiveObjectProperty)
• irreflexive properties (IrreflexiveObjectProperty)
• asymmetric properties (AsymmetricObjectProperty)
• assertions other than individual equality assertions and negative property assertions (DifferentIndividuals, ClassAssertion, ObjectPropertyAssertion, and DataPropertyAssertion)

The following constructs are not supported in OWL 2 QL:

• existential quantification to a class expression or a data range (ObjectSomeValuesFrom and DataSomeValuesFrom) in the subclass position
• self-restriction (ObjectHasSelf)
• existential quantification to an individual or a literal (ObjectHasValue, DataHasValue)
• enumeration of individuals and literals (ObjectOneOf, DataOneOf)
• universal quantification to a class expression or a data range (ObjectAllValuesFrom, DataAllValuesFrom)
• cardinality restrictions (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality, DataMaxCardinality, DataMinCardinality, DataExactCardinality)
• disjunction (ObjectUnionOf, DisjointUnion, and DataUnionOf)
• property inclusions (SubObjectPropertyOf) involving property chains
• functional and inverse-functional properties (FunctionalObjectProperty, InverseFunctionalObjectProperty, and FunctionalDataProperty)
• transitive properties (TransitiveObjectProperty)
• keys (HasKey)
• individual equality assertions and negative property assertions

OWL 2 QL does not support individual equality assertions (SameIndividual): adding such axioms to OWL 2 QL would increase the data complexity of query answering, so that it is no longer first order rewritable, which means that query answering could not be implemented directly using relational database technologies. However, an ontology O that includes individual equality assertions, but is otherwise OWL 2 QL, could be handled by computing the reflexive–symmetric–transitive closure of the equality (SameIndividual) relation in O (this requires answering recursive queries and can be implemented in LOGSPACE w.r.t. the size of data) [DL-Lite-bool], and then using this relation in query answering procedures to simulate individual equality reasoning [Automated Reasoning].

3.2 Profile Specification

The productions for OWL 2 QL are defined in the following sections. Note that each OWL 2 QL ontology must satisfy the global restrictions on axioms defined in Section 11 of the structural specification [OWL 2 Specification].

3.2.1 Entities

Entities are defined in OWL 2 QL in the same way as in the structural specification [OWL 2 Specification], and OWL 2 QL supports all predefined classes and properties. Furthermore, OWL 2 QL supports the following datatypes:

• rdf:PlainLiteral
• rdf:XMLLiteral
• rdfs:Literal
• owl:real
• owl:rational
• xsd:decimal
• xsd:integer
• xsd:nonNegativeInteger
• xsd:string
• xsd:normalizedString
• xsd:token
• xsd:Name
• xsd:NCName
• xsd:NMTOKEN
• xsd:hexBinary
• xsd:base64Binary
• xsd:anyURI
• xsd:dateTime
• xsd:dateTimeStamp

The set of supported datatypes has been designed such that the intersection of the value spaces of any set of these datatypes is either empty or infinite, which is necessary to obtain the desired computational properties. Consequently, the following datatypes MUST NOT be used in OWL 2 QL: xsd:double, xsd:float, xsd:nonPositiveInteger, xsd:positiveInteger, xsd:negativeInteger, xsd:long, xsd:int, xsd:short, xsd:byte, xsd:unsignedLong, xsd:unsignedInt, xsd:unsignedShort, xsd:unsignedByte, xsd:language, and xsd:boolean.

Finally, OWL 2 QL does not support anonymous individuals.

3.2.2 Property Expressions

OWL 2 QL object and data property expressions are the same as in the structural specification [OWL 2 Specification].

3.2.3 Class Expressions

In OWL 2 QL, there are two types of class expressions. The subClassExpression production defines the class expressions that can occur as subclass expressions in SubClassOf axioms, and the superClassExpression production defines the classes that can occur as superclass expressions in SubClassOf axioms.

3.2.4 Data Ranges

A data range expression is restricted in OWL 2 QL to the predefined datatypes and the intersection of data ranges.

3.2.5 Axioms

The class axioms of OWL 2 QL are the same as in the structural specification [OWL 2 Specification], with the exception that DisjointUnion is disallowed; however, all axioms that refer to the ClassExpression production are redefined so as to use subClassExpression and/or superClassExpression as appropriate.

OWL 2 QL disallows the use of property chains in property inclusion axioms; however, simple property inclusions are supported. Furthermore, OWL 2 QL disallows the use of functional and transitive object properties, and it restricts the class expressions in object property domain and range axioms to superClassExpression.

OWL 2 QL disallows functional data property axioms, and it restricts the class expressions in data property domain axioms to superClassExpression.

OWL 2 QL disallows negative object property assertions and individual equality axioms. Furthermore, class assertions in OWL 2 QL can involve only atomic classes. Inequality axioms and property assertions are the same as in the structural specification [OWL 2 Specification].

Finally, the axioms in OWL 2 QL are the same as those in the structural specification [OWL 2 Specification], with the exception that key axioms are not allowed.

4 OWL 2 RL

The OWL 2 RL profile is aimed at applications that require scalable reasoning without sacrificing too much expressive power. It is designed to accommodate both OWL 2 applications that can trade the full expressivity of the language for efficiency, and RDF(S) applications that need some added expressivity from OWL 2. This is achieved by defining a syntactic subset of OWL 2 which is amenable to implementation using rule-based technologies (see Section 4.2), and presenting a partial axiomatization of the OWL 2 RDF-Based Semantics [OWL 2 RDF-Based Semantics] in the form of first-order implications that can be used as the basis for such an implementation (see Section 4.3). The design of OWL 2 RL was inspired by Description Logic Programs [DLP] and pD* [pD*].

For ontologies satisfying the syntactic constraints described in Section 4.2, a suitable rule-based implementation (e.g., one based on the partial axiomatization presented in Section 4.3) will have desirable computational properties; for example, it can return all and only the correct answers to certain kinds of query (see Theorem PR1 and OWL 2 Conformance [OWL 2 Conformance]). Such an implementation can also be used with arbitrary RDF graphs. In this case, however, these properties no longer hold — in particular, it is no longer possible to guarantee that all correct answers can be returned, for example if the RDF graph uses the built-in vocabulary in unusual ways. Such an implementation will, however, still produce only correct entailments (see OWL 2 Conformance [OWL 2 Conformance]).

4.1 Feature Overview

Restricting the way in which constructs are used makes it possible to implement reasoning systems using rule-based reasoning engines, while still providing desirable computational guarantees. These restrictions are designed so as to avoid the need to infer the existence of individuals not explicitly present in the knowledge base, and to avoid the need for nondeterministic reasoning. This is achieved by restricting the use of constructs to certain syntactic positions. For example in SubClassOf axioms, the constructs in the subclass and superclass expressions must follow the usage patterns shown in Table 2.

All axioms in OWL 2 RL are constrained in a way that is compliant with these restrictions. Thus, OWL 2 RL supports all axioms of OWL 2 apart from disjoint unions of classes (DisjointUnion) and reflexive object property axioms (ReflexiveObjectProperty).

4.2 Profile Specification

The productions for OWL 2 RL are defined in the following sections. OWL 2 RL is defined not only in terms of the set of supported constructs, but it also restricts the places in which these constructs can be used. Note that each OWL 2 RL ontology must satisfy the global restrictions on axioms defined in Section 11 of the structural specification [OWL 2 Specification].

4.2.1 Entities

Entities are defined in OWL 2 RL in the same way as in the structural specification [OWL 2 Specification]. OWL 2 RL supports the predefined classes owl:Nothing and owl:Thing, but the usage of the latter class is restricted by the grammar of OWL 2 RL. Furthermore, OWL 2 RL does not support the predefined object and data properties owl:topObjectProperty, owl:bottomObjectProperty, owl:topDataProperty, and owl:bottomDataProperty. Finally, OWL 2 RL supports the following datatypes:

• rdf:PlainLiteral
• rdf:XMLLiteral
• rdfs:Literal
• xsd:decimal
• xsd:integer
• xsd:nonNegativeInteger
• xsd:nonPositiveInteger
• xsd:positiveInteger
• xsd:negativeInteger
• xsd:long
• xsd:int
• xsd:short
• xsd:byte
• xsd:unsignedLong
• xsd:unsignedInt
• xsd:unsignedShort
• xsd:unsignedByte
• xsd:float
• xsd:double
• xsd:string
• xsd:normalizedString
• xsd:token
• xsd:language
• xsd:Name
• xsd:NCName
• xsd:NMTOKEN
• xsd:boolean
• xsd:hexBinary
• xsd:base64Binary
• xsd:anyURI
• xsd:dateTime
• xsd:dateTimeStamp

The set of supported datatypes has been designed to allow for an implementation in rule systems. The owl:real and owl:rational datatypes MUST NOT be used in OWL 2 RL.

4.2.2 Property Expressions

Property expressions in OWL 2 RL are identical to the property expressions in the structural specification [OWL 2 Specification].

4.2.3 Class Expressions

There are three types of class expressions in OWL 2 RL. The subClassExpression production defines the class expressions that can occur as subclass expressions in SubClassOf axioms; the superClassExpression production defines the class expressions that can occur as superclass expressions in SubClassOf axioms; and the equivClassExpressions production defines the classes that can occur in EquivalentClasses axioms.

4.2.4 Data Ranges

A data range expression is restricted in OWL 2 RL to the predefined datatypes admitted in OWL 2 RL and the intersection of data ranges.

4.2.5 Axioms

OWL 2 RL redefines all axioms of the structural specification [OWL 2 Specification] that refer to class expressions. In particular, it restricts various class axioms to use the appropriate form of class expressions (i.e., one of subClassExpression, superClassExpression, or equivClassExpression), and it disallows the DisjointUnion axiom.

OWL 2 RL axioms about property expressions are as in the structural specification [OWL 2 Specification], the only differences being that class expressions in property domain and range axioms are restricted to superClassExpression, and that the use of reflexive properties is disallowed.

OWL 2 RL restricts class expressions in positive assertions to superClassExpression. All other assertions are the same as in the structural specification [OWL 2 Specification].

OWL 2 RL restricts class expressions in keys to subClassExpression.

All other axioms in OWL 2 RL are defined as in the structural specification [OWL 2 Specification].

4.3 Reasoning in OWL 2 RL and RDF Graphs using Rules

This section presents a partial axiomatization of the OWL 2 RDF-Based Semantics [OWL 2 RDF-Based Semantics] in the form of first-order implications; this axiomatization is called the OWL 2 RL/RDF rules. These rules provide a useful starting point for practical implementation using rule-based technologies such as logic programming [Logic Programming, Lloyd].

The rules are given as universally quantified first-order implications over a ternary predicate T. This predicate represents a generalization of RDF triples in which bnodes and literals are allowed in all positions (similar to the partial generalization in pD* [pD*] and to generalized RDF triples in RIF [RIF RDF & OWL]); thus, T(s, p, o) represents a generalized RDF triple with the subject s, predicate p, and the object o. Variables in the implications are preceded with a question mark. The rules that have empty "if" parts should be understood as being always applicable. The propositional symbol false is a special symbol denoting contradiction: if it is derived, then the initial RDF graph was inconsistent. The set of rules listed in this section is not minimal, as certain rules are implied by other ones; this was done to make the definition of the semantic consequences of each piece of OWL 2 vocabulary self-contained.

Many conditions contain atoms that match to the list construct of RDF. In order to simplify the presentation of the rules, LIST[h, e₁, ..., e_n] is used as an abbreviation for the conjunction of triples shown in Table 3, where z₂, ..., z_n are fresh variables that do not occur anywhere where the abbreviation is used.

The axiomatization is split into several tables for easier navigation. Each rule is given a short unique name. The rows of several tables specify rules that need to be instantiated for each combination of indices given in the right-most column.

Table 4 axiomatizes the semantics of equality. In particular, it defines the equality relation owl:sameAs as being reflexive, symmetric, and transitive, and it axiomatizes the standard replacement properties of equality for it.

Table 5 specifies the semantic conditions on axioms about properties.

Table 6 specifies the semantic conditions on classes.

Table 7 specifies the semantic conditions on class axioms.

Table 8 specifies the semantics of datatypes.

Table 9 specifies the semantic restrictions on the vocabulary used to define the schema.

In order to avoid potential performance problems in practice, OWL 2 RL/RDF rules do not include the axiomatic triples of RDF and RDFS (i.e., those triples that must be satisfied by, respectively, every RDF and RDFS interpretation) [RDF Semantics] and the relevant OWL vocabulary [OWL 2 RDF-Based Semantics]; moreover, OWL 2 RL/RDF rules include most, but not all of the entailment rules of RDFS [RDF Semantics]. An OWL 2 RL/RDF implementation MAY include these triples and entailment rules as necessary without invalidating the conformance requirements for OWL 2 RL [OWL 2 Conformance].

Theorem PR1. Let R be the OWL 2 RL/RDF rules as defined above. Furthermore, let O₁ and O₂ be OWL 2 RL ontologies satisfying the following properties:

• neither O₁ nor O₂ contains a IRI that is used for more than one type of entity (i.e., no IRIs is used both as, say, a class and an individual);
• O₁ does not contain SubAnnotationPropertyOf, AnnotationPropertyDomain, and AnnotationPropertyRange axioms; and
• each axiom in O₂ is an assertion of the form as specified below, for a, a₁, ..., a_n named individuals:
  • ClassAssertion( C a ) where C is a class,
  • ObjectPropertyAssertion( OP a₁ a₂ ) where OP is an object property,
  • DataPropertyAssertion( DP a v ) where DP is a data property, or
  • SameIndividual( a₁ ... a_n ).

Furthermore, let RDF(O₁) and RDF(O₂) be translations of O₁ and O₂, respectively, into RDF graphs as specified in the OWL 2 Mapping to RDF Graphs [OWL 2 RDF Mapping]; and let FO(RDF(O₁)) and FO(RDF(O₂)) be the translation of these graphs into first-order theories in which triples are represented using the T predicate — that is, T(s, p, o) represents an RDF triple with the subject s, predicate p, and the object o. Then, O₁ entails O₂ under the OWL 2 Direct Semantics [OWL 2 Direct Semantics] if and only if FO(RDF(O₁)) ∪ R entails FO(RDF(O₂)) under the standard first-order semantics.

Proof Sketch. Without loss of generality, it can be assumed that all axioms in O₁ are fully normalized — that is, that all class expressions in the axioms are of depth at most one. Let DLP(O₁) be the set of rules obtained by translating O₁ into a set of rules as in Description Logic Programs [DLP].

Consider now each assertion A ∈ O₂ that is entailed by DLP(O₁) (or, equivalently, by O₁). Let dt be a derivation tree for A from DLP(O₁). By examining the set of OWL 2 RL constructs, it is possible to see that each such tree can be transformed to a derivation tree dt' for FO(RDF(A)) from FO(RDF(O₁)) ∪ R. Each assertion B occurring in dt is of the form as specified in the theorem. The tree dt' can, roughly speaking, be obtained from dt by replacing each assertion B with FO(RDF(B)) and by replacing each rule from DLP(O₁) with a corresponding rule from Tables 3–8. Consequently, FO(RDF(O₁)) ∪ R entails FO(RDF(A)).

Since no IRI in O₁ is used as both an individual and a class or a property, FO(RDF(O₁)) ∪ R does not entail a triple of the form T(a:i1, owl:sameAs, a:i2) where either a:i1 or a:i2 is used in O₁ as a class or a property. This allows one to transform a derivation tree for FO(RDF(A)) from FO(RDF(O₁)) ∪ R to a derivation tree for A from DLP(O₁) in a way that is analogous to the previous case. QED

5 Computational Properties

This section describes the computational complexity of the most relevant reasoning problems of the languages defined in this document. For an introduction to computational complexity, please refer to a textbook on complexity such as [Papadimitriou]. The reasoning problems considered here are ontology consistency, class expression satisfiability, class expression subsumption, instance checking, and (Boolean) conjunctive query answering [OWL 2 Direct Semantics]. When evaluating complexity, the following complexity measures are considered:

• 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 (without assertions) in the ontology
• Query Complexity: the complexity measured with respect to the total size of the conjunctive query (defined only for conjunctive query answering)
• Combined Complexity: the complexity measured with respect to the total size of the axioms and the assertions in the ontology, the conjunctive query (in the case of conjunctive query answering), and the expression(s) being checked (in the case of class expression satisfiability, class expression subsumption, or instance checking)

Table 10 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 meaning of the entries is as follows:

• Decidability open means that it is not known whether this reasoning problem is decidable at all.
• Decidable, but complexity open means that decidability of this reasoning problem is known, but not its exact computational complexity. If available, known lower bounds are given in parenthesis; for example, (NP-Hard) means that this problem is at least as hard as any other problem in NP.
• X-complete for X one of the complexity classes explained below indicates that tight complexity bounds are known — that is, the problem is known to be both in the complexity class X (i.e., an algorithm is known that only uses time/space in X) and hard for X (i.e., it is at least as hard as any other problem in X). The following is a brief sketch of the classes used in this table, from the most complex one down to the simplest ones.
  • N2EXPTIME is the class of problems solvable by a nondeterministic algorithm in time that is at most double exponential in the size of the input (i.e., roughly 2²ⁿ, for n the size of the input).
  • NEXPTIME is the class of problems solvable by a nondeterministic algorithm in time that is at most exponential in the size of the input (i.e., roughly 2ⁿ, for n the size of the input).
  • PSPACE is the class of problems solvable by a deterministic algorithm using space that is at most polynomial in the size of the input (i.e., roughly n^c, for n the size of the input and c a constant).
  • NP is the class of problems solvable by a nondeterministic algorithm using time that is at most polynomial in the size of the input (i.e., roughly n^c, for n the size of the input and c a constant).
  • PTIME is the class of problems solvable by a deterministic algorithm using time that is at most polynomial in the size of the input (i.e., roughly n^c, for n the size of the input and c a constant). PTIME is often referred to as tractable, whereas the problems in the classes above are often referred to as intractable.
  • LOGSPACE is the class of problems solvable by a deterministic algorithm using space that is at most logarithmic in the size of the input (i.e., roughly log(n), for n the size of the input and c a constant). NLOGSPACE is the nondeterministic version of this class.
  • AC⁰ is a proper subclass of LOGSPACE and defined not via Turing Machines, but via circuits: AC⁰ is the class of problems definable using a family of circuits of constant depth and polynomial size, which can be generated by a deterministic Turing machine in logarithmic time (in the size of the input). Intuitively, AC⁰ allows us to use polynomially many processors but the run-time must be constant. A typical example of an AC⁰ problem is the evaluation of first-order queries over databases (or model checking of first-order sentences over finite models), where only the database (first-order model) is regarded as the input and the query (first-order sentence) is assumed to be fixed. The undirected graph reachability problem is known to be in LogSpace, but not in AC⁰.

The results below 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.

6 Appendix: Complete Grammars for Profiles

This appendix contains the grammars for all three profiles of OWL 2.

6.1 OWL 2 EL

The grammar of OWL 2 EL consists of the general definitions from Section 13.1 of the OWL 2 Specification [OWL 2 Specification], as well as the following productions.

6.2 OWL 2 QL

The grammar of OWL 2 QL consists of the general definitions from Section 13.1 of the OWL 2 Specification [OWL 2 Specification], as well as the following productions.

6.3 OWL 2 RL

The grammar of OWL 2 RL consists of the general definitions from Section 13.1 of the OWL 2 Specification [OWL 2 Specification], as well as the following productions.

8 Acknowledgments

The starting point for the development of OWL 2 was the OWL1.1 member submission, itself a result of user and developer feedback, and in particular of information gathered during the OWL Experiences and Directions (OWLED) Workshop series. The working group also considered postponed issues from the WebOnt Working Group.

This document has been produced by the OWL Working Group (see below), and its contents reflect extensive discussions within the Working Group as a whole. The editors extend special thanks to Jie Bao (RPI), Jim Hendler (RPI) and Jeff Pan (University of Aberdeen) for their thorough reviews.

The regular attendees at meetings of the OWL Working Group at the time of publication of this document were: Jie Bao (RPI), Diego Calvanese (Free University of Bozen-Bolzano), Bernardo Cuenca Grau (Oxford University Computing Laboratory), Martin Dzbor (Open University), Achille Fokoue (IBM Corporation), Christine Golbreich (Université de Versailles St-Quentin and LIRMM), Sandro Hawke (W3C/MIT), Ivan Herman (W3C/ERCIM), Rinke Hoekstra (University of Amsterdam), Ian Horrocks (Oxford University Computing Laboratory), Elisa Kendall (Sandpiper Software), Markus Krötzsch (FZI), Carsten Lutz (Universität Bremen), Deborah L. McGuinness (RPI), Boris Motik (Oxford University Computing Laboratory), Jeff Pan (University of Aberdeen), Bijan Parsia (University of Manchester), Peter F. Patel-Schneider (Bell Labs Research, Alcatel-Lucent), Sebastian Rudolph (FZI), Alan Ruttenberg (Science Commons), Uli Sattler (University of Manchester), Michael Schneider (FZI), Mike Smith (Clark & Parsia), Evan Wallace (NIST), Zhe Wu (Oracle Corporation), and Antoine Zimmermann (DERI Galway). We would also like to thank past members of the working group: Jeremy Carroll, Jim Hendler, and Vipul Kashyap.

9 References

9.1 Normative References

[OWL 2 Conformance]

OWL 2 Web Ontology Language: Conformance. Michael Smith, Ian Horrocks, Markus Krötzsch, and Birte Glimm, eds., 2009.

[OWL 2 Direct Semantics]

OWL 2 Web Ontology Language: Direct Semantics. Boris Motik, Peter F. Patel-Schneider, and Bernardo Cuenca Grau, eds., 2009.

[OWL 2 RDF Mapping]

OWL 2 Web Ontology Language: Mapping to RDF Graphs. Peter F. Patel-Schneider and Boris Motik, eds., 2009.

[OWL 2 RDF-Based Semantics]

OWL 2 Web Ontology Language: RDF-Based Semantics. Michael Schneider, ed., 2009.

[OWL 2 Specification]

OWL 2 Web Ontology Language: Structural Specification and Functional-Style Syntax. Boris Motik, Peter F. Patel-Schneider, and Bijan Parsia, eds., 2009.

[RFC 2119]

RFC 2119: Key words for use in RFCs to Indicate Requirement Levels. Network Working Group, S. Bradner. IETF, March 1997, http://www.ietf.org/rfc/rfc2119.txt

9.2 Nonnormative References

[Complexity]

Complexity Results and Practical Algorithms for Logics in Knowledge Representation. Stephan Tobies. Ph.D Dissertation, 2002

[DL-Lite]

Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Diego Calvanese, Giuseppe de Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati. J. of Automated Reasoning 39(3):385–429, 2007

[DL-Lite-bool]

The DL-Lite Family and Relatives. Alessandro Artale, Diego Calvanese, Roman Kontchakov, Michael Zakharyaschev, submitted.

[DLP]

Description Logic Programs: Combining Logic Programs with Description Logic. Benjamin N. Grosof, Ian Horrocks, Raphael Volz, and Stefan Decker. in Proc. of the 12th Int. World Wide Web Conference (WWW 2003), Budapest, Hungary, 2003. pp.: 48–57

[EL++]

Pushing the EL Envelope. Franz Baader, Sebastian Brandt, and Carsten Lutz. In Proc. of the 19th Joint Int. Conf. on Artificial Intelligence (IJCAI 2005), 2005

[EL++ Update]

Pushing the EL Envelope Further. Franz Baader, Sebastian Brandt, and Carsten Lutz. In Proc. of the Washington DC workshop on OWL: Experiences and Directions (OWLED08DC), 2008

[OWL 1 Reference]

OWL Web Ontology Language Reference. Mike Dean and Guus Screiber, eds., W3C Recommendation, 10 February 2004.

[OWL 2 Primer]

OWL 2 Web Ontology Language: Primer. Pascal Hitzler, Markus Krötzsch, Bijan Parsia, Peter F. Patel-Schneider, and Sebastian Rudolph, eds., 2009.

[Papadimitriou]

Christos H. Papadimitriou. Computational Complexity. Addison Wesley Publ. Co., Reading, Massachussetts, 1994.

[pD*]

Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary. Herman J. ter Horst. J. of Web Semantics 3(2–3):79–115, 2005

[RDF Semantics]

RDF Semantics. Patrick Hayes, ed., W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-mt-20040210/. Latest version available as http://www.w3.org/TR/rdf-mt/.

[RIF RDF & OWL]

RIF RDF and OWL Compatibility. Jos de Bruijn, ed., W3C Working Draft, 30 July 2008.

[SNOMED CT]

Systematized Nomenclature of Medicine – Clinical Terms. International Health Terminology Standards Development Organization (IHTSDO)

[Automated Reasoning]

Handbook of Automated Reasoning. A. Robinson and A. Voronkov, eds., Elsevier Science, 2001

[Logic Programming]

Logic programming and knowledge representation. Chitta Baral and Michael Gelfond. Journal of Logic Programming 19:73–148, 1994.

[Lloyd]

Foundations of Logic Programming, 2nd ed. John Wylie Lloyd. Springer-Verlag, Berlin, Germany, 1987.