Profiles-v1

Authors

Bernardo Cuenca Grau, Oxford University

Boris Motik, Oxford University

Zhe Wu, Oracle

Achille Fokoue, IBM

Carsten Lutz, Dresden University of Technology

1 Introduction

The purpose of an OWL 2 profile is to provide a trimmed down version of OWL 2 that trades expressive power for efficiency of reasoning. In logic, a profile is usually called a fragment or a sublanguage. This document describes three important profiles of OWL 2, each of them achieving efficiency in a different way and useful in different application scenarios:

• The EL++ profile enables polynomial time algorithms for the reasoning tasks consistency, classification, and instance checking. Dedicated reasoning algorithms for this profile are available and have been demonstrated to be implementable in a highly scalable way.
• In the DL-Lite profile, conjunctive query answering can be implemented using conventional relational database systems (after rewriting the query). In particular, this requires that conjunctive query answering is in LogSpace regarding data complexity. As in EL++, there are polynomial time algorithms for consistency, classification, and instance checking.
• The OWL-R profile enables the implementation of reasoning algorithms by forward chaining rules applied to triples of the RDF serialization. In particular, such rule approaches can be used to compute consistency, classification, and instance checking in polynomial time. Conjunctive query answering in OWL-R can be implemented by extending a standard relational database system with rules. OWL-R comes in two varieties, OWL-R DL and OWL-R Full.

The profiles EL++, DL-Lite, and OWL-R DL are defined by placing restrictions on the syntax of OWL 2 DL. In contrast, OWL-R Full is defined by placing restrictions on the semantics of OWL 2 Full.

Syntactic restrictions can be specified by modifying the grammar of the functional-style syntax [OWL 2 Specification], and (possibly) giving additional non-structural restrictions. In this document, the modified grammars are specified in two ways. In each section defining a profile, only the difference to the full grammar is given; that is, only the productions that differ from [OWL 2 Specification] are presented and the productions that are the same as in [OWL 2 Specification] are not repeated. In order to make this document self-contained, the full grammar for each of the profiles is given in the Appendix.

The reasoning tasks mentioned in the description of the profiles are defined as follows.

• consistency: given an ontology, decide whether it is contradictory (i.e., has any models);
• classification: given an ontology, compute the subclass relation between all its classes;
• instance checking: given an individual a and a class C in an ontology, decide whether a is an instance of C;
• conjunctive query answering: given an ontology O and a conjunctive query q, return all tuples of individuals in O that match q.

Apart from the ones specified here, there are many other possible profiles of OWL 2. Although we don't specifically document OWL lite [OWL 1 Reference] in this document, it is the intention of the working group that all OWL Lite ontologies will be OWL 2 DL ontologies and so OWL Lite can be viewed as a profile of OWL 2. OWL 1 DL can also be viewed as a profile of OWL 2.

2 EL++

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

• captures the expressive power used by many large-scale ontologies and
• for which the following reasoning problems can be decided in polynomial time: satisfiability, subsumption, classification, and instance checking.

A main design principle of EL++ is to focus on the class constructors ObjectIntersectionOf and ObjectSomeValuesFrom, but to provide ObjectAllValuesFrom only in the form of range restrictions. Many biomedical ontologies, such as SNOMED CT, fall within this profile.

2.1 Feature Overview

EL++ provides the following features:

• existential quantification to a class expression (ObjectSomeValuesFrom) or a data range (DataSomeValuesFrom)
• existential quantification to an individual (ObjectHasValue) or a literal (DataHasValue)
• self-restriction (ObjectExistsSelf)
• enumerations involving a single individual (ObjectOneOf) or a single literal (DataOneOf)
• intersection of classes (ObjectIntersectionOf)
• class inclusion (SubClassOf)
• class equivalence (EquivalentClasses)
• class disjointness (DisjointClasses)
• object property inclusion (SubObjectPropertyOf), possibly involving 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 (KeyFor)
• a subset of the datatypes of OWL 2

The following features of OWL 2 are not supported in EL++:

• universal quantification to a class expression (ObjectAllValuesFrom) or a data range (DatAllaValuesFrom)
• cardinality restrictions (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality),DataMaxCardinality, DataMinCardinality, and DataExactCardinality))
• disjunction (ObjectUnionOf and DisjointUnion)
• 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 object properties (FunctionalObjectProperty)
• symmetric object properties (SymmetricObjectProperty)
• asymmetric object properties (AsymmetricObjectProperty)

2.2 Profile Specification

The following sections specify the structure of EL++ ontologies.

2.2.1 Entities

The entities of EL++ are exactly as in OWL 2. Furthermore, EL++ supports the owl:Thing and owl:Nothing predefined classes, as well as the predefined object and data properties owl:TopObjectProperty, owl:BottomObjectProperty, owl:TopDataProperty, and owl:BottomDataProperty. Finally, it supports the following datatypes:

• rdfs:Literal
• xsd:decimal
• xsd:integer
• xsd:nonNegativeInteger
• xsd:dateTime
• xsd:date
• xsd:string
• xsd:normalizedString
• xsd:anyURI
• xsd:token
• xsd:Name
• xsd:NCName
• xsd:hexBinary
• xsd:base64Binary
• owl:internationalizedString

The following predefined OWL 2 datatypes cannot be used in EL++: xsd:double, xsd:float, xsd:long, xsd:int, xsd:short, xsd:byte, xsd:nonPositiveInteger, xsd:positiveInteger, xsd:negativeInteger, xsd:unsignedLong, xsd:unsignedInt, xsd:unsignedShort, xsd:unsignedByte, xsd:time, xsd:gYear, xsd:gMonth, xsd:gDay, xsd:gYearMonth, and xsd:gMonthDay.

2.2.2 Property Expressions

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

2.2.3 Class Expressions

In order to allow for efficient reasoning, EL++ restricts the set of supported class expressions to ObjectIntersectionOf, ObjectSomeValuesFrom, ObjectExistsSelf, ObjectHasValue, DataSomeValuesFrom, DataHasValue, and objectOneOf containing a single individual.

The class expressions are as defined in the same way as in OWL 2 [OWL 2 Specification], with the exception of the objectOneOf class expression, which in EL++ admits only a single individual.

2.2.4 Data Ranges

A data range expression is restricted in EL++ to the predefined datatypes admitted in EL++ and to enumerated datatypes consisting of a single literal.

2.2.5 Axioms

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

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

EL++ provides the same axioms about data properties as OWL 2 apart from DisjointDataProperty. These axioms are defined in the same way as in [OWL 2 Specification].

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

2.2.6 Global Restrictions

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

Let CE be a class expression. We say that Ax imposes a range restriction to CE on an object property OP₁ if object properties OP_i, 2 ≤ i ≤ k, exist such that Ax contains all of the following axioms:

• SubPropertyOf( OP₁ OP₂)
• ...
• SubPropertyOf( OP_k-1 OP_k )
• PropertyRange( OP_k CE )

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

• Ax contains SubPropertyOf( PropertyChain( 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 SubPropertyOf axiom in which in the first item of the previous definition does not contain a property chain. Range restrictions on reflexive and transitive roles are generally allowed, unless they are used in axioms that are explicitly forbidden using the previous definition.

3 DL-Lite

DL-Lite is a syntactic profile of OWL 2 that admits sound and complete reasoning in LOGSPACE with respect to the size of the data (assertions). DL-Lite includes most of the main features of conceptual models such as UML class diagrams and ER diagrams.

Several variants of DL-Lite have been described in the literature. The variant presented here is called DL-Lite_A: it is one of the most expressive variants of DL-Lite, and it contains the intersection between RDFS and OWL 2. In order to achieve the desired complexity of query answering, certain restrictions are imposed on the interaction between subproperty and functionality axioms.

DL-Lite 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.

3.1 Feature Overview

The following constructs can be used to define subclass expressions in SubClassOf axioms:

• classes
• existential quantification (ObjectSomeValuesFrom) where the class is limited to owl:Thing

The following constructs can be used to define superclass expressions in SubClassOf axioms:

• classes
• existential quantification to a class (ObjectSomeValuesFrom)
• negation (ObjectComplementOf)
• intersection (ObjectIntersectionOf)

All axioms in DL-Lite are constrained in a way that is compliant with these restrictions. Thus, DL-Lite supports the following axioms:

• subclass axioms (SubClassOf)
• class expression equivalence (EquivalentClasses)
• class expression disjointness (DisjointClasses)
• functional object properties (FunctionalObjectProperty)
• 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)
• assertions other than the equality assertions (DifferentIndividuals, ClassAssertion, ObjectPropertyAssertion, and DataPropertyAssertion)
• keys (KeyFor)

The following features of OWL 2 are not supported in DL-Lite:

• existential quantification to a class expression or a data range (ObjectSomeValuesFrom and DataSomeValuesFrom in the subclass position)
• self-restriction (ObjectExistsSelf)
• existential quantification to an individual or a literal (ObjectHasValue, DataHasValue)
• nominals (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)
• property inclusions (SubObjectPropertyOf involving property chains)
• transitive properties (TransitiveObjectProperty)
• reflexive properties (ReflexiveObjectProperty)
• irreflexive properties (IrreflexiveObjectProperty)
• asymmetric properties (AsymmetricObjectProperty)
• inverse-functional properties (InverseFunctionalObjectProperty)

3.2 Profile Specification

The productions for DL-Lite are defined in the following sections. The expressive power of DL-Lite is such that the global restriction on axioms defined in Section 11 of [OWL 2 Specification] are vacuously satisfied in every DL-lite ontology.

3.2.1 Entities

DL-Lite supports all OWL 2 entities, including all predefined classesand properties. The following datatypes are supported in DL-Lite:

• rdfs:Literal
• xsd:decimal
• xsd:integer
• xsd:nonNegativeInteger
• xsd:positiveInteger
• xsd:dateTime
• xsd:date
• xsd:string
• xsd:normalizedString
• xsd:anyURI
• xsd:token
• xsd:Name
• xsd:NCName
• xsd:hexBinary
• xsd:base64Binary
• owl:internationalizedString

The following predefined OWL 2 datatypes cannot be used in DL-Lite: xsd:double, xsd:float, xsd:long, xsd:int, xsd:short, xsd:byte, xsd:nonPositiveInteger, xsd:negativeInteger, xsd:unsignedLong, xsd:unsignedInt, xsd:unsignedShort, xsd:unsignedByte, xsd:time, xsd:gYear, xsd:gMonth, xsd:gDay, xsd:gYearMonth, and xsd:gMonthDay.

3.2.2 Property Expressions

DL-Lite object and data property expressions are the same as in OWL 2.

3.2.3 Class Expressions

In DL-Lite, there are two types of class expressions. The subClassExpression production defines the class expressions that can occur in the antecedents of implications; such class expressions can, for example, occur as subclass expressions in SubClassOf axioms. The superClassExpression production defines the classes that can occur in the consequents of implications; such class expressions can, for example, can occur as superclass expressions in SubClassOf axioms.

3.2.4 Data Ranges

A data range expression is restricted in DL-Lite to the predefined datatypes.

3.2.5 Axioms

The class axioms of DL-Lite are the same as in OWL 2, with the exception that DisjointUnion is disallowed. Different OWL 2 class axioms from the structural specification [OWL 2 Specification] that refer to the ClassExpression production, however, are redefined and restricted them to appropriate forms of class expressions.

DL-Lite disallows the use of property chains in property inclusion axioms; however, simple property inclusions are supported. Furthermore, DL-Lite disallows the transitive, asymmetric, reflexive and irreflexive object properties, and it redefines the object property domain and range axioms to use the appropriate class expressions. Finally, DL-Lite allows for functional object properties.

DL-Lite provides the same axioms about data properties as OWL 2 [OWL 2 Specification], with the exception that the object property domain axioms are redefined to use the appropriate class expressions.

DL-Lite disallows negative object property assertions and equality axioms. Furthermore, class assertions in DL-Lite can involve only atomic classes. Equality and inequality axioms and property assertions are the same as in OWL 2.

Finally, the axioms in DL-Lite are the same as in OWL 2, with the difference that the new productions are used for various types of axioms.

3.2.6 Global Restrictions

The global restrictions on axioms from Section 11 of the structural specification [OWL 2 Specification] are not relevant in DL-Lite because DL-Lite allows for neither number restrictions nor property chains. DL-Lite, however, introduces a different set of global restrictions that the axiom closure Ax of a DL-Lite ontology O must satisfy.

• Ax must axiomatize the Unique Name Assumption (UNA): each pair of individuals i₁ and i₂ occurring in some axiom in Ax must also occur in Ax in an axiom of the form DifferentIndividuals( ... i₁ ... i₂ ... ).
• No object property OP is allowed to occur in Ax in both a FunctionalProperty or a KeyFor axiom and in a superproperty expression in SubPropertyOf axiom.
• No data property DP is allowed to occur in Ax in both a FunctionalProperty or a KeyFor axiom and in a superproperty expression in SubPropertyOf axiom.

4 OWL-R

OWL-R is a profile of OWL 2 that allows for scalable reasoning using rule-based technologies. The profile has been designed so as to avoid the need to infer the existence of individuals not explicitly present in the knowledge base. This design goal enables a straightforward translation of OWL’s semantic conditions into rules, on which most rule-based reasoning engines terminate in a finite amount of time.

Another design goal for OWL-R is flexibility. On the one hand, OWL-R can accommodate OWL 2 DL applications that can trade the full expressivity of the language for efficiency; on the other hand, OWL-R can also accommodate RDF(S) applications that need some added expressivity from OWL. For this purpose, this document provides two variants of OWL-R.

The first variant of OWL-R, called OWL-R DL, is intended to be used by OWL 2 users who can trade some expressivity for being able to implement reasoning using rule-based systems. OWL-R DL is defined as a syntactic subset of OWL 2 — that is, it places syntactic restrictions on OWL 2 axioms. For example, in this definition, one cannot declare a class C1 to be a subclass of the union of two classes C2 and C3. The definition of OWL-R DL is presented completely in Section 4.2.

The second variant OWL-R, called OWL-R Full, is intended to be used by RDF(S) users who want to augment RDF(S) with additional contructs. OWL-R Full ontologies are thus RDF graphs that are interpreted under a weakened version of the extensional semantic conditions of OWL 2 Full. An axiomatization of the weakened semantics using first-order implications is provided in the form of entailment rules that operate directly on RDF triples. This set of entailment rules provides a useful starting point for practical inference implementation using rule-based technologies. The definition of OWL-R Full is presented completely in Section 4.3. Readers who are familiar with RDF(S) triple-oriented technology and are interested mainly in the semantic axiomatization of OWL-R Full using first-order implication may skip directly to Section 4.3.2.

The definitions of OWL-R DL and OWL-R Full are independent in the sense that it is not necessary to understand one variant in order to be able to understand the other. Thus, the readers interested in the DL version of OWL-R can skip to Section 4.2, whereas the readers interested in the Full version of OWL-R can skip to Section 4.3.

The relationship between OWL-R DL and OWL-R Full is specified precisely in Section 4.4. This clear relationship allows users to switch between the two versions of OWL-R if necessary.

4.1 Feature Overview

OWL-R is a fairly expressive profile of OWL 2 that has been designed such that reasoning can be implemented with relatively simple technology. It allows for most constructs of OWL 2. To achieve tractability, these constructs are restricted in a way that depends on the variant of OWL-R one is using.

In OWL-R DL, tractability is achieved by disallowing the usage of certain constraints of OWL 2 in certain syntactic positions. For example, in SubClassOf axioms, the constructs of OWL 2 in the subclass and superclass expressions must be used according to the patterns shown in Table 1.

In OWL-R Full, tractability is achieved in a different way. There are no syntactic restrictions on the way language constructs can be used: any RDF graph constitutes a valid OWL-R Full ontology. The semantics of language constructs, however, is weakened in OWL-R Full to mimic the usage patterns of OWL-R DL. For example, in OWL 2 Full (or DL), an OWL class C1 is a subclass of C2 if and only if the extension of C1 is a subset of the extension of C2. In OWL-R Full, this "if and only if" condition is weakened to "only if." The principles according to which this weakening has been derived are presented in Section 4.3.1. An equivalent characterization of the weakened semantics by means of first-order implications is given in Section 4.3.2. Table 2 lists the language constructs that are supported in OWL-R Full.

4.2 OWL-R DL

OWL-R DL is a syntactic profile of OWL 2. The profile is defined not only in terms of a set of supported constructs, but it also restricts the places in which these constructs can be used. It is based on Description Logic Programs [DLP] — a logic obtained by intersecting description logics with rule-based languages.

4.2.1 Entities

OWL-R DL does not impose any restrictions on OWL 2 entities; hence, all entities from [OWL 2 Specification] are supported. OWL-R also supports all well-known entities of OWL 2, apart from owl:TopObjectProperty, owl:BottomObjectProperty, owl:TopDataProperty, and owl:BottomDataProperty built-in properties.

4.2.2 Property Expressions

Property expressions in OWL-R DL are identical to the property expressions in OWL 2 [OWL 2 Specification].

4.2.3 Class Expressions

There are three types of class expressions in OWL-R DL. The subClassExpression production defines the class expressions that can occur in the antecedents of implications; such class expressions can, for example, occur as subclass expressions in a SubClassOf axiom. The superClassExpressions production defines the classes that can occur in the consequents of implications; such class expressions can, for example, occur as superclass expressions in a SubClassOf axiom. Finally, the equivClassExpressions production defines the classes that can occur in an EquivalentClasses axiom.

4.2.4 Data Ranges

In OWL-R DL, data ranges are restricted to supported datatypes.

4.2.5 Axioms

OWL-R DL redefines all of [OWL 2 Specification] that refer to ClassExpression. 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-R DL axioms about property expressions are as in OWL 2, the only difference being that property domain and range axioms are restricted to the appropriate form of class expressions.

OWL-R DL restricts the positive assertions to a particular type of classes, and it disallows negative property assertions. Equality and inequality between individuals and positive assertions are the same as in OWL 2.

Keys are redefined in OWL-R DL to allow for correct type of class expression in the axiom.

All other axioms in OWL-R DL are defined as in OWL 2.

4.3 OWL-R Full

OWL-R Full is defined by weakening the semantic conditions on an interpretation from OWL 2 Full. Section 4.3.1 illustrates the principles according to which this weakening has been derived; these have strongly been inspired by [pD*]. The language is then formally defined in Section 4.3.2 by axiomatizing the weakened semantic conditions using first-order implications. The latter section provides a useful starting point for practical implementation using rule-based technologies.

4.3.1 Weakening the Semantic Conditions of OWL 2 Full

This section presents the principles according to which the [OWL 2 Full Semantics] is weakened in OWL-R Full. To make discussion easier to understand, the following paragraph first summarizes the basic definitions used in [OWL 2 Full Semantics].

A datatype map D is a partial mapping from URI references to datatypes that maps datatype URIs to the appropriate [XML Schema Datatypes]. Given a datatype map, an interpretation in OWL 2 Full is defined as follows. For V a set of URI references and literals containing the reserved vocabulary of RDF, RDFS, and OWL, and for D a datatype map, a D-interpretation of V is a tuple I = ( R_I , P_I , EXT_I , S_I , L_I , LV_I ). R_I is the domain of discourse or universe — that is, a nonempty set that contains the denotations of URI references and literals in V. P_I is a subset of R_I consisting of the properties of I. EXT_I is used to give meaning to properties, and is a mapping from P_I to P(R_I × R_I). S_I is a mapping from URI references in V to their denotations in R_I. L_I is a mapping from typed literals in V to their denotations in R_I. LV_I is a subset of R_I that contains at least the set of all Unicode strings, the set of pairs of Unicode strings and language tags, and the value spaces for each datatype in D. The set of all classes in R_I is C_I, and the mapping CEXT_I from C_I to P(R_I) is defined as CEXT_I(c) = { x ∈ R_I | < x , c > ∈ EXT_I(S_I(rdf:type)) }. CEXT_I(c) maps a class c to its extension. A D-interpretations must meet several other conditions, as detailed in the OWL 2 Full semantics. Finally, the following important sets are used in the definitions of the semantic conditions of OWL 2 Full. IOOP denotes the set of OWL object properties and IODP denotes the set of OWL datatype properties; both are subsets of P_I. IOC, a subset of C_I, denotes the set of OWL classes, and IDC is the set of OWL datatypes. IOR represents the set of OWL restrictions. IOT is the set of OWL individuals.

In OWL-R Full, the weakening of the OWL 2 Full semantic conditions on an interpretation is mainly done by weakening some equivalences in the OWL Full semantics to implications. For example, the semantics of the owl:someValuesFrom restriction is defined in OWL 2 Full using the following restrictions on the RDF interpretation:

In a simplified form, these conditions can be understood as the following two implications:

The first implication captures the notion of existential restrictions occurring in the antecedents of implications, while the second implication captures the notion of existential restrictions occurring in the consequents of implications. In OWL-R Full, the second implication is discarded. Note the parallel with OWL-R DL, where syntactic restrictions prevent existential restrictions occurring in the consequents of implications.

Next, the restrictions that define OWL-R Full are listed. Instead of repeating all the intricate definitions of OWL Full, this section just specifies the difference to the definitions in the OWL Full document. For readers less familiar with OWL Full semantics, the next section provides a more self-contained axiomatization of OWL-R.

• The conditions in the table defining the characteristics of OWL classes, datatypes, and properties are changed as follows:
  • The conditions defining the sets IOT, LV_I, and IX are dropped.
  • The if-and-only-if in the definition of the semantics of owl:FunctionalProperty, owl:InverseFunctionalProperty, owl:SymmetricProperty, and owl:TransitiveProperty is changed into only-if.
• In the table defining the semantics of rdfs:subClassOf, rdfs:subPropertyOf, rdfs:domain, and rdfs:range, the if-and-only-if condition in the third column of the table header is changed into only-if.
• In the table defining the characteristics of OWL vocabulary related to equivalence, the if-and-only-if condition in the second column of the table header is changed into only-if.
• In the table defining the conditions on OWL vocabulary related to boolean combinations and sets, the conditions for owl:complementOf is dropped, and the conditions for owl:oneOf and owl:unionOf are changed into only-if. The condition for owl:intersectionOf is left unchanged.
• The table defining the conditions on OWL restrictions is modified as follows.
  • The condifion for owl:allValuesFrom is changed into CEXT_I(x) ⊆ { u ∈ IOT | < u , v > ∈ EXT_I(p) implies v ∈ CEXT_I(y) }.
  • The condifion for owl:someValuesFrom is changed into CEXT_I(x) ⊇ {u ∈ IOT | < u , v > ∈ EXT_I(p) implies v ∈ CEXT_I(y) }.
  • The condition for owl:hasValue is let unchanged.
  • The conditions for cardinality restrictions are changed such that y must be 1, and CEXT_I(x) = [...] is changed into CEXT_I(x) ⊆ [...].
• The comprehension principles are dropped.

4.3.2 Axiomatization Using First-Order Implications

This section defines OWL-R Full in terms of first-order (material) implications. This definition is intended to be equivalent to the one from the previous section. This definition provides a useful starting point for the practical implementation using rule-based technologies.

The implications are given as universally quantified first-order implications over a ternary predicate T. This predicate represents RDF triples; thus, T(s, p, o) represents a RDF triple with the subject s, predicate p, and the object o. Variables in the implications are preceded with the question mark. The propositional symbol false is a special symbol denoting contradiction: if it derived, then the RDF graph is inconsistent.

Many conditions contain atoms that must 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 following conjunction of triples, where z₂, ..., z_n are fresh variables that do not occur anywhere where the abbreviation is used.

The semantic conditions are split into several tables for easier navigation. These tables are exhaustive: they specify exactly all the semantic conditions that must hold.

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

Table 4 specifies the semantic conditions on axioms about properties.

Table 5 specifies the semantic conditions on classes.

Table 6 specifies the semantic conditions on class axioms.

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

4.4 Relationship between OWL-R DL and OWL-R Full

Let AXIOMS be a set containing all the implications listed in Section 4.3.2; let O be an OWL-R DL ontology in which no URI is used more than one type of entity (i.e., no URIs is used both as, say, a class and an individual); and let F be a set of assertions of the following form:

• ClassAssertion( C a ) where C is a class
• PropertyAssertion( P a₁ a₂ ) where P is an object property
• PropertyAssertion( P a v ) where P is a data property
• SameIndividual( a₁ ... a_n )
• DifferentIndividuals( a₁ ... a_n )

Furthermore, let RDF(O) and RDF(F) be the translations of O and F into RDF graphs as specified in [OWL 2 RDF Mapping], in which triples are represented using the T predicate. Then, the following relationship between consequences in OWL-R DL and OWL-R Full holds:

5 Computational Properties

This section describes the computational complexity of important reasoning problems in the described profiles.

Note that in languages that are propositionally closed (i.e., that provide, either implicitly or explicitly, conjunction, union and negation of class descriptions), such as OWL 2, the problems of ontology consistency, class expression satisfiability, class expression subsumption and instance checking can be reduced to each other in polynomial time. However, none of the described profiles is propositionally closed, and these reasoning problems may thus have different complexity and require different algorithmic solutions.

This section describes the computational complexity of the most relevant reasoning problems of the languages defined in this document. The reasoning problems considered here are the following:

• Ontology Consistency: Check whether a given ontology has at least one model.
• Class Expression Satisfiability: Given an ontology O and a class expression CE, verify whether there is a model of O in which the interpretation of CE is not empty.
• Class Expression Subsumption: Given an ontology O and class expressions CE₁ and CE₂, verify whether the interpretation of CE₁ is a subset of the interpretation of CE₂ in every model of O
• Instance Checking: Given an ontology, an individual a and a class expression CE, verify whether a is an instance of CE in every model of the ontology.
• Conjunctive Query Answering: Given an ontology O and a Boolean conjunctive query Q (that is, a closed, existentially quantified conjunction of atoms in which class and property expressions occur as unary and binary atoms), check whether Q is true in every model of O

When evaluating the complexity, the following parameters will be 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 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 and the facts. In the case of conjunctive query answering, the combined complexity also includes the size of the query.

Table 8 summarizes the known complexity results for OWL 2, OWL 1 DL, EL++, DL-Lite, and OWL-R. Whenever the complexity for a given problem is described as "Open", * denotes that the problem's decidability is still an open question; if * is omitted, then the problem is known to be decidable but precise complexity bounds have not yet been established.

6 References

[OWL 2 Specification]

OWL 2 Web Ontology Language: Structural Specification and Functional-Style Syntax. Peter F. Patel-Schneider, Ian Horrocks, and Boris Motik, eds., 2008.

[OWL 2 Semantics]

OWL 2 Web Ontology Language: Model-Theoretic Semantics. Bernardo Cuenca Grau and Boris Motik, eds., 2008.

[OWL 2 RDF Mapping]

OWL 2 Web Ontology Language: Mapping to RDF Graphs. Bernardo Cuenca Grau and Boris Motik, eds., 2008.

[OWL 2 Full Semantics]

OWL 2 Web Ontology Language: Semantics of OWL 2 Full. Document in preparation

[OWL 1 Reference]

OWL Web Ontology Language Reference. Mike Dean and Guus Screiber, eds., 2004.

[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.

[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.

[Complexity]

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

[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

[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.

[XML Schema Datatypes]

XML Schema Part 2: Datatypes Second Edition. Paul V. Biron and Ashok Malhotra, eds. W3C Recommendation 28 October 2004.

7 Appendix: Complete Grammars for Profiles

7.1 EL++

7.2 DL-Lite

7.3 OWL-R