Difference between revisions of "Profiles"
(→Feature Overview) |
(→Axiomatization Using First-Order Implications) |
||
Line 703: | Line 703: | ||
| class="name" | T(?x, owl:maxCardinality, "1"^^xsd:nonNegativeInteger)<br /> T(?x, owl:onProperty, ?p)<br /> T(?u, ?p, ?y<sub>1</sub>)<br /> T(?u, ?p, ?y<sub>2</sub>)<br/> T(?u, rdf:type, ?x) | | class="name" | T(?x, owl:maxCardinality, "1"^^xsd:nonNegativeInteger)<br /> T(?x, owl:onProperty, ?p)<br /> T(?u, ?p, ?y<sub>1</sub>)<br /> T(?u, ?p, ?y<sub>2</sub>)<br/> T(?u, rdf:type, ?x) | ||
| class="name" colspan="2" | T(?y<sub>1</sub>, owl:sameAs, ?y<sub>2</sub>) | | class="name" colspan="2" | T(?y<sub>1</sub>, owl:sameAs, ?y<sub>2</sub>) | ||
+ | |- | ||
+ | | class="name" | T(?c, owl:oneOf, ?x)<br /> LIST[?x, ?y<sub>1</sub>, ..., ?y<sub>n</sub>] | ||
+ | | class="name" | T(?y<sub>i</sub>, rdf:type, ?c) | ||
+ | | for each 1 ≤ i ≤ n | ||
+ | |- | ||
|} | |} | ||
</div> | </div> |
Revision as of 16:36, 26 April 2008
__NUMBEREDHEADINGS__
- Document title:
- OWL 2 Web Ontology Language
Profiles (Second Edition)
- Authors
- Bernardo Cuenca Grau, Oxford University
- Boris Motik, Oxford University
- Zhe Wu, Oracle
- Achille Fokoue, IBM
- Carsten Lutz, Dresden University of Technology
- Abstract
Abstract needs total rewrite
- The OWL 2 Web Ontology Language, informally OWL 2, is an ontology language for the Semantic Web with formally defined meaning. OWL 2 ontologies provide classes, properties, individuals, and data values and are stored as Semantic Web documents. OWL 2 ontologies can be used along with information written in RDF, and OWL 2 ontologies themselves are primarily exchanged as RDF documents. The OWL 2 Document Overview describes the overall state of OWL 2, and should be read before other OWL 2 documents.
This document provides a specification of several profiles of OWL 2 which can be more simply and/or efficiently implemented. In logic, profiles are often called fragments. Most profiles are defined by placing restrictions on the syntax of OWL 2. These restrictions have been specified by modifying the productions of the functional-style syntax. - Status of this Document
- This document is an evolution of the OWL 1.1 Web Ontology Language: Tractable Fragments document that forms part of the OWL 1.1 Web Ontology Language W3C Member Submission.
Copyright © 2008-2009 W3C^{®} (MIT, ERCIM, Keio), All Rights Reserved. W3C liability, trademark and document use rules apply.
Contents
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.
It will be worth having a larger introduction. It's worth mentioning that there are many possible profiles that might usefully be the focus of a community, as well as that implementations of the profiles might support profile *families* (DL-Lite really comes to mind there).
Longer intro should mention each of the three profiles and a one-liner rationale for each in language that is as non-technical as possible. Could also mention: OWL DL as another sensible implementation profile; that users/implementators MAY use any other profile that they find helpful; deprecate OWL Lite, see ISSUE-107
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 constant (DataHasValue)
- self-restriction (ObjectExistsSelf)
- enumerations involving a single individual (ObjectOneOf) or a single constant (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)
- 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. Finally, it supports the following datatypes:
- 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 EL++: 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.
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.
ObjectPropertyExpression := ObjectProperty
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.
ClassExpression :=
Class | ObjectIntersectionOf | ObjectOneOf |
ObjectSomeValuesFrom | ObjectExistsSelf | ObjectHasValue |
DataSomeValuesFrom | DataHasValue
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.
ObjectOneOf := 'OneOf' '(' 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 constant.
DataRange := Datatype | DataOneOf
DataOneOf := 'OneOf' '(' Constant ')'
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.
ClassAxiom := SubClassOf | EquivalentClasses | DisjointClasses
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.
ObjectPropertyAxiom :=
EquivalentObjectProperties | SubObjectPropertyOf |
ObjectPropertyDomain | ObjectPropertyRange |
TransitiveObjectProperty| ReflexiveObjectProperty
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].
DataPropertyAxiom :=
SubDataPropertyOf |
EquivalentDataProperties |
DataPropertyDomain |
DataPropertyRange |
FunctionalDataProperty
The assertions in EL++ are the same as in OWL 2, with the difference that class object property expressions are restricted as defined in the previous sections. Finally, the axioms of EL++ are the same as in OWL 2, with the difference that each axiom type is restricted as specified previously.
2.2.6 Global Restrictions
EL++ extends the global restrictions on axioms from Section 10 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_{1} if object properties OP_{i}, 2 ≤ i ≤ k, exist such that Ax contains all of the following axioms:
- SubPropertyOf( OP_{1} OP_{2})
- ...
- 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 10 of the structural specification [OWL 2 Specification] and, in addition, if
- Ax contains SubPropertyOf( PropertyChain( OP_{1} ... 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_{R} since it allows for property inclusion axioms; it therefore contains the intersection between RDFS and OWL 2. Other variants trade property inclusion axioms for functionality and inverse-functionality of object properties.
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 except for owl:Thing
- 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)
- inverse object properties (InverseObjectProperties)
- property inclusion (SubObjectPropertyOf) not involving property chains
- property equivalence (EquivalentObjectProperties)
- property domain (ObjectPropertyDomain)
- property range (ObjectPropertyRange)
- disjoint properties (DisjointObjectProperties)
- symmetric properties (SymmetricObjectProperty)
- assertions (SameIndividual, DifferentIndividuals, ClassAssertion, and ObjectPropertyAssertion)
The following features of OWL 2 are not supported in DL-Lite:
- existential quantification to a class expression (ObjectSomeValuesFrom) in the subclass position
- self-restriction (ObjectExistsSelf)
- existential quantification to an individual (ObjectHasValue)
- nominals (ObjectOneOf)
- universal quantification to a class expression (ObjectAllValuesFrom)
- cardinality restrictions (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality)
- disjunction (ObjectUnionOf, DisjointUnion)
- property inclusions (SubObjectPropertyOf) involving property chains
- transitive properties (TransitiveObjectProperty)
- reflexive properties (ReflexiveObjectProperty)
- irreflexive properties (IrreflexiveObjectProperty)
- asymmetric properties (AsymmetricObjectProperty)
- functional properties (FunctionalObjectProperty)
- 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 10 of [OWL 2 Specification] are vacuously satisfied in every DL-lite ontology.
3.2.1 Entities
DL-Lite supports all OWL 2 entities apart from data properties. The only well-known entity available in DL-Lite is the predefined class owl:Thing.
3.2.2 Property Expressions
DL-Lite object 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.
subClassExpression :=
Class other than owl:Thing |
'SomeValuesFrom' '(' ObjectPropertyExpression owl:Thing ')'
superClassExpression :=
Class |
'SomeValuesFrom' '(' ObjectPropertyExpression Class ')'
'ComplementOf' '(' subClassExpression ')' |
'IntersectionOf' '(' superClassExpression superClassExpression { superClassExpression } ')'
3.2.4 Axioms
DL-Lite does not provide for any axioms about data properties.
Axiom := Declaration | ClassAxiom | ObjectPropertyAxiom | Assertion | EntityAnnotation
Furthermore, DL-Lite redefines all OWL 2 axioms from the structural specification [OWL 2 Specification] that refer to the ClassExpression production and restricts them to appropriate forms of class expressions. DL-Lite also disallows DisjointUnion.
SubClassOf := 'SubClassOf' '(' subClassExpression superClassExpression ')'
EquivalentClasses := 'EquivalentClasses' '(' subClassExpression subClassExpression { subClassExpression } ')'
DisjointClasses := 'DisjointClasses' '(' subClassExpression subClassExpression { subClassExpression } ')'
ClassAxiom := SubClassOf | EquivalentClasses | DisjointClasses
DL-Lite disallows the use of property chains in property inclusion axioms; however, simple property inclusions are supported just. Furthermore, DL-Lite disallows the transitive, asymmetric, reflexive and irreflexive properties, and it redefines the domain and range axioms to use the appropriate class expressions.
ObjectPropertyDomain := 'PropertyDomain' '(' ObjectPropertyExpression superClass ')'
ObjectPropertyRange := 'PropertyRange' '(' ObjectPropertyExpression superClass ')'
SubObjectPropertyOf := 'SubPropertyOf' '(' ObjectPropertyExpression ObjectPropertyExpression ')'
ObjectPropertyAxiom :=
SubObjectPropertyOf | EquivalentObjectProperties |
DisjointObjectProperties | InverseObjectProperties |
ObjectPropertyDomain | ObjectPropertyRange |
SymmetricObjectProperty
DL-Lite disallows axioms about data properties and negative object property assertions. 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.
ClassAssertion := 'ClassAssertion' '(' Class Individual ')'
Assertion := SameIndividual | DifferentIndividuals | ClassAssertion | ObjectPropertyAssertion
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.
Subclass Expressions | Superclass Expressions |
---|---|
a class a nominal class (OneOf) intersection of class expressions (ObjectIntersectionOf) union of class expressions (ObjectUnionOf) existential quantification to a class expressions (ObjectSomeValuesFrom) existential quantification to an individual (ObjectHasValue) |
a class intersection of classes (ObjectIntersectionOf) universal quantification to a class expressions (ObjectAllValuesFrom) at-most 1 cardinality restrictions (ObjectMaxCardinality 1) existential quantification to an individual (ObjectHasValue) |
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.
Equality | owl:sameAs owl:differentFrom |
Property Expressions | owl:inverseObjectPropertyExpression |
Property Axioms | rdfs:domain rdfs:range owl:FunctionalProperty owl:InverseFunctionalProperty owl:ReflexiveProperty owl:IrreflexiveProperty owl:SymmetricProperty owl:AsymmetricProperty owl:TransitiveProperty rdfs:subPropertyOf owl:propertyChain owl:equivalentProperty owl:propertyDisjointWith owl:inverseOf |
Class Constructs | owl:intersectionOf owl:unionOf owl:someValuesFrom owl:allValuesFrom owl:hasValue owl:maxCardinality 1 |
Class Axioms | rdfs:subClassOf owl:equivalentClass owl:disjointClasses |
At some point it should be clear that OWL-R implementations are free to implement any consequences of the OWL Full semantics, and this section specifies a minimal semantics, not a maximal
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.
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.
zeroOrOne := '0' | '1'
subClassExpression :=
Class other than owl:Thing |
'OneOf' '(' Individual { Individual } ')'
'IntersectionOf' '(' subClassExpression subClassExpression { subClassExpression } ')' |
'UnionOf' '(' subClassExpression subClassExpression { subClassExpression } ')' |
'SomeValuesFrom' '(' ObjectPropertyExpression subClassExpression ')' |
'SomeValuesFrom' '(' DataPropertyExpression { DataPropertyExpression } DataRange ')' |
'HasValue' '(' ObjectPropertyExpression Individual ')' |
'HasValue' '(' DataPropertyExpression Constant ')'
superClassExpression :=
Class |
'IntersectionOf' '(' subClassExpression superClassExpression { superClassExpression } ')' |
'AllValuesFrom' '(' ObjectPropertyExpression superClassExpression ')' |
'AllValuesFrom' '(' DataPropertyExpression { DataPropertyExpression } DataRange ')' |
'MaxCardinality' '(' zeroOrOne ObjectPropertyExpression [ subClassExpression ] ')' |
'MaxCardinality' '(' zeroOrOne DataPropertyExpression [ DataRange ] ')' |
'HasValue' '(' ObjectPropertyExpression Individual ')' |
'HasValue' '(' DataPropertyExpression Constant ')'
equivClassExpression :=
Class other than owl:Thing |
'IntersectionOf' '(' equivClassExpression equivClassExpression { equivClassExpression } ')' |
'HasValue' '(' ObjectPropertyExpression Individual ')' |
'HasValue' '(' DataPropertyExpression Constant ')'
4.2.4 Data Ranges
In OWL-R DL, data ranges are restricted to supported datatypes or a datatype restriction of a preexisting datatype by means of facets. All facets from Section 7.3 of [OWL 2 Specification] are supported.
DataRange := Datatype | DatatypeRestriction
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.
ClassAxiom := SubClassOf | EquivalentClasses | DisjointClasses
SubClassOf := 'SubClassOf' '(' subClassExpression superClassExpression ')'
EquivalentClasses := 'EquivalentClasses' '(' equivClassExpression equivClassExpression { equivClassExpression } ')'
DisjointClasses := 'DisjointClasses' '(' subClassExpression subClassExpression { subClassExpression } ')'
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.
ObjectPropertyDomain := 'PropertyDomain' '(' ObjectPropertyExpression superClassExpression ')'
ObjectPropertyRange := 'PropertyRange' '(' ObjectPropertyExpression superClassExpression ')'
DataPropertyDomain := 'PropertyDomain' '(' DataPropertyExpression superClassExpression ')'
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.
ClassAssertion := 'ClassAssertion' '(' Individual superClassExpression ')'
Assertion :=
SameIndividual | DifferentIndividuals | ClassAssertion |
ObjectPropertyAssertion | DataPropertyAssertion
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 should provide a useful starting point for practical implementation using rule-based technologies.
HP notes the following design choice concerning expressivity vs ease-of-implementation with respect to: (a) equality and (b) b-node introduction. We have found both of these features add to expressivity and usefulness of a rule based approach to OWL Full reasoning, and both lead to performance issues. We note that the OWL-R definition includes (a) and not (b). That trade-off seems appropriate to us but this is a choice that should be highlighted during public review.
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:
If | < x , y > ∈ EXT_{I}(S_{I}(owl:someValuesFrom)) ∧ < x , p > ∈ EXT_{I}(S_{I}(owl:onProperty)) | then | x ∈ IOR, y ∈ IOC ∪ IDC, p ∈ IOOP ∪ IODP, and CEXT_{I}(x) = { u ∈ IOT | ∃ < u , v > ∈ EXT_{I}(p) such that v ∈ CEXT_{I}(y) } |
---|
In a simplified form, these conditions can be understood as the following two implications:
If | < x , y > ∈ EXT_{I}(S_{I}(owl:someValuesFrom)) ∧ < x , p > ∈ EXT_{I}(S_{I}(owl:onProperty)) ∧ < u , v > ∈ EXT_{I}(p) ∧ < v , y > ∈ EXT_{I}(S_{I}(rdf:type)) |
then | < u , x > ∈ EXT_{I}(S_{I}(rdf:type)). |
---|---|---|---|
If | < x , y > ∈ EXT_{I}(S_{I}(owl:someValuesFrom)) ∧ < x , p > ∈ EXT_{I}(S_{I}(owl:onProperty)) ∧ < u , x > ∈ EXT_{I}(S_{I}(rdf:type)) |
then | ∃ v such that < u , v > ∈ EXT_{I}(p) ∧ < v , y > ∈ EXT_{I}(S_{I}(rdf:type)). |
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.
It would be good if tables in the OWL Full semantics document were numbered so that we can refer to them easily from this document.
Similarly, I think numbering all the rows would be helpful too, even if it's only in the markup. Consider trying to discuss a particular mapping rule in the RDF mapping.
- 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 and owl:oneOf are dropped, and the condition for owl:unionOf is changed into only-if. The condition for owl:intersectionOf is left unchanged.
I do not understand why conditions on owl:oneOf are dropped whereas owl:oneOf was allowed in antecedents in OWL-R DL. Does it mean that we cannot write "subClassOf(ObjectOneOf(a1, a2), A) in OWL-R Full?
- 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
I have deleted the untrue words "It is easy to see that" and added the weasel words "intended to be"
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 should provide 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_{1}, ..., e_{n}] is used as an abbreviation for the following conjunction of triples, where z_{2}, ..., 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.
T(h, rdf:first, e_{1}) | T(h, rdf:rest, z_{2}) |
T(z_{2}, rdf:first, e_{2}) | T(z_{2}, rdf:rest, z_{3}) |
... | ... |
T(z_{n}, rdf:first, e_{n}) | T(z_{n}, rdf:rest, rdf:nil) |
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.
Please add real names (not consequtive numbers, which are hostages to fortune) for each rule, and add HTML anchors
If | then |
---|---|
T(?s, ?p, ?o) |
T(?s, owl:sameAs, ?s) T(?p, owl:sameAs, ?p) T(?o, owl:sameAs, ?o) |
T(?x, owl:sameAs, ?y) | T(?y, owl:sameAs, ?x) |
T(?x, owl:sameAs, ?y) T(?y, owl:sameAs, ?z) |
T(?x, owl:sameAs, ?z) |
T(?s, owl:sameAs, ?s') T(?s, ?p, ?o) |
T(?s', ?p, ?o) |
T(?p, owl:sameAs, ?p') T(?s, ?p, ?o) |
T(?s, ?p', ?o) |
T(?o, owl:sameAs, ?o') T(?s, ?p, ?o) |
T(?s, ?p, ?o') |
T(?x, owl:sameAs, ?y) T(?x, owl:differentFrom, ?y) |
false |
Table 4 specifies the semantic conditions on axioms about properties.
If | then |
---|---|
T(?p, rdfs:domain, ?c) T(?x, ?p, ?y) |
T(?x, rdf:type, ?c) |
T(?p, rdfs:range, ?c) T(?x, ?p, ?y) |
T(?y, rdf:type, ?c) |
T(?p, rdf:type, owl:FunctionalProperty) T(?x, ?p, ?y_{1}) T(?x, ?p, ?y_{2}) |
T(?y_{1}, owl:sameAs, ?y_{2}) |
T(?p, rdf:type, owl:InverseFunctionalProperty) T(?x_{1}, ?p, ?y) T(?x_{2}, ?p, ?y) |
T(?x_{1}, owl:sameAs, ?x_{2}) |
T(?p, rdf:type, owl:ReflexiveProperty) T(?x, ?y, ?z) |
T(?x, ?p, ?x) T(?y, ?p, ?y) T(?z, ?p, ?z) |
T(?p, rdf:type, owl:IrreflexiveProperty) T(?x, ?p, ?x) |
false |
T(?p, rdf:type, owl:SymmetricProperty) T(?x, ?p, ?y) |
T(?y, ?p, ?x) |
T(?p, rdf:type, owl:AsymmetricProperty) T(?x, ?p, ?y) T(?y, ?p, ?x) |
false |
T(?p, rdf:type, owl:TransitiveProperty) T(?x, ?p, ?y) T(?y, ?p, ?z) |
T(?x, ?p, ?z) |
T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) T(?x, ?p_{1}, ?y) |
T(?x, ?p_{2}, ?y) |
T(?sc, owl:propertyChain, ?x) LIST[?x, ?p_{1}, ..., ?p_{n}] T(?sc, rdfs:subPropertyOf, ?p) T(?u_{1}, ?p_{1}, ?u_{2}) T(?u_{2}, ?p_{2}, ?u_{3}) ... T(?u_{n}, ?p_{n}, ?u_{n+1}) |
T(?u_{1}, ?p, ?u_{n+1}) |
T(?p_{1}, owl:equivalentProperty, ?p_{2}) T(?x, ?p_{1}, ?y) |
T(?x, ?p_{2}, ?y) |
T(?p_{1}, owl:equivalentProperty, ?p_{2}) T(?x, ?p_{2}, ?y) |
T(?x, ?p_{1}, ?y) |
T(?p_{1}, owl:propertyDisjointWith, ?p_{2}) T(?x, ?p_{1}, ?y) T(?x, ?p_{2}, ?y) |
false |
T(?p_{1}, owl:inverseOf, ?p_{2}) T(?x, ?p_{1}, ?y) |
T(?y, ?p_{2}, ?x) |
T(?p_{1}, owl:inverseOf, ?p_{2}) T(?x, ?p_{2}, ?y) |
T(?y, ?p_{1}, ?x) |
Table 5 specifies the semantic conditions on classes.
If | then | |
---|---|---|
T(?c, owl:intersectionOf, ?x) LIST[?x, ?c_{1}, ..., ?c_{n}] T(?y, rdf:type, ?c_{1}) T(?y, rdf:type, ?c_{2}) ... T(?y, rdf:type, ?c_{n}) |
T(?y, rdf:type, ?c) | |
T(?c, owl:intersectionOf, ?x) LIST[?x, ?c_{1}, ..., ?c_{n}] T(?y, rdf:type, ?c) |
T(?y, rdf:type, ?c_{1}) T(?y, rdf:type, ?c_{2}) ... T(?y, rdf:type, ?c_{n}) | |
T(?c, owl:unionOf, ?x) LIST[?x, ?c_{1}, ..., ?c_{n}] T(?y, rdf:type, ?c_{i}) |
T(?y, rdf:type, ?c) | for each 1 ≤ i ≤ n |
T(?x, owl:someValuesFrom, ?y) T(?x, owl:onProperty, ?p) T(?u, ?p, ?v) T(?v, rdf:type, ?y) |
T(?u, rdf:type, ?x) | |
T(?x, owl:allValuesFrom, ?y) T(?x, owl:onProperty, ?p) T(?u, rdf:type, ?x) T(?u, ?p, ?v) |
T(?v, rdf:type, ?y) | |
T(?x, owl:hasValue, ?y) T(?x, owl:onProperty, ?p) T(?u, rdf:type, ?x) |
T(?u, ?p, ?y) | |
T(?x, owl:hasValue, ?y) T(?x, owl:onProperty, ?p) T(?u, ?p, ?y) |
T(?u, rdf:type, ?x) | |
T(?x, owl:maxCardinality, "0"^^xsd:nonNegativeInteger) T(?x, owl:onProperty, ?p) T(?u, ?p, ?y) T(?u, rdf:type, ?x) |
false | |
T(?x, owl:maxCardinality, "1"^^xsd:nonNegativeInteger) T(?x, owl:onProperty, ?p) T(?u, ?p, ?y_{1}) T(?u, ?p, ?y_{2}) T(?u, rdf:type, ?x) |
T(?y_{1}, owl:sameAs, ?y_{2}) | |
T(?c, owl:oneOf, ?x) LIST[?x, ?y_{1}, ..., ?y_{n}] |
T(?y_{i}, rdf:type, ?c) | for each 1 ≤ i ≤ n |
Table 6 specifies the semantic conditions on class axioms.
If | then |
---|---|
T(?c_{1}, rdfs:subClassOf, ?c_{2}) T(?x, rdf:type, ?c_{1}) |
T(?x, rdf:type, ?c_{2}) |
T(?c_{1}, owl:equivalentClass, ?c_{2}) T(?x, rdf:type, ?c_{1}) |
T(?x, rdf:type, ?c_{2}) |
T(?c_{1}, owl:equivalentClass, ?c_{2}) T(?x, rdf:type, ?c_{2}) |
T(?x, rdf:type, ?c_{1}) |
T(?c_{1}, owl:disjointClasses, ?c_{2}) T(?x, rdf:type, ?c_{1}) T(?x, rdf:type, ?c_{2}) |
false |
Table 7 specifies the semantic restrictions on the vocabulary used to define the schema.
If | then |
---|---|
T(?c, rdf:type, owl:Class) | T(?c, rdfs:subClassOf, ?c) T(?c, owl:equivalentClasses, ?c) |
T(?c_{1}, rdfs:subClassOf, ?c_{2}) T(?c_{2}, rdfs:subClassOf, ?c_{3}) |
T(?c_{1}, rdfs:subClassOf, ?c_{3}) |
T(?c_{1}, owl:equivalentClass, ?c_{2}) | T(?c_{1}, rdfs:subClassOf, ?c_{2}) T(?c_{2}, rdfs:subClassOf, ?c_{1}) |
T(?p, rdf:type, owl:ObjectProperty) | T(?p, rdfs:subPropertyOf, ?p) T(?p, owl:equivalentProperty, ?p) |
T(?p, rdf:type, owl:DatatypeProperty) | T(?p, rdfs:subPropertyOf, ?p) T(?p, owl:equivalentProperty, ?p) |
T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) T(?p_{2}, rdfs:subPropertyOf, ?p_{3}) |
T(?p_{1}, rdfs:subPropertyOf, ?p_{3}) |
T(?p_{1}, owl:equivalentProperty, ?p_{2}) | T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) T(?p_{2}, rdfs:subPropertyOf, ?p_{1}) |
T(?p, rdfs:domain, ?c_{1}) T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?p, rdfs:domain, ?c_{2}) |
T(?p_{2}, rdfs:domain, ?c) T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) |
T(?p_{1}, rdfs:domain, ?c) |
T(?p, rdfs:range, ?c_{1}) T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?p, rdfs:range, ?c_{2}) |
T(?p_{2}, rdfs:range, ?c) T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) |
T(?p_{1}, rdfs:range, ?c) |
T(?c_{1}, owl:hasValue, ?i) T(?c_{1}, owl:onProperty, ?p_{1}) T(?c_{2}, owl:hasValue, ?i) T(?c_{2}, owl:onProperty, ?p_{2}) T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) |
T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?c_{1}, owl:someValuesFrom, ?y_{1}) T(?c_{1}, owl:onProperty, ?p) T(?c_{2}, owl:someValuesFrom, ?y_{2}) T(?c_{2}, owl:onProperty, ?p) T(?y_{1}, rdfs:subClassOf, ?y_{2}) |
T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?c_{1}, owl:someValuesFrom, ?y) T(?c_{1}, owl:onProperty, ?p_{1}) T(?c_{2}, owl:someValuesFrom, ?y) T(?c_{2}, owl:onProperty, ?p_{2}) T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) |
T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?c_{1}, owl:allValuesFrom, ?y_{1}) T(?c_{1}, owl:onProperty, ?p) T(?c_{2}, owl:allValuesFrom, ?y_{2}) T(?c_{2}, owl:onProperty, ?p) T(?y_{1}, rdfs:subClassOf, ?y_{2}) |
T(?c_{1}, rdfs:subClassOf, ?c_{2}) |
T(?c_{1}, owl:allValuesFrom, ?y) T(?c_{1}, owl:onProperty, ?p_{1}) T(?c_{2}, owl:allValuesFrom, ?y) T(?c_{2}, owl:onProperty, ?p_{2}) T(?p_{1}, rdfs:subPropertyOf, ?p_{2}) |
T(?c_{2}, rdfs:subClassOf, ?c_{1}) |
T(?c, owl:intersectionOf, ?x) LIST[?x, ?c_{1}, ..., ?c_{n}] |
T(?c, rdfs:subClassOf, ?c_{1}) T(?c, rdfs:subClassOf, ?c_{2}) ... T(?c, rdfs:subClassOf, ?c_{n}) |
T(?c, owl:unionOf, ?x) LIST[?x, ?c_{1}, ..., ?c_{n}] |
T(?c_{1}, rdfs:subClassOf, ?c) T(?c_{2}, rdfs:subClassOf, ?c) ... T(?c_{n}, rdfs:subClassOf, ?c) |
Should soemthing be specified about literals
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 both as an object and a data property; and let F be a set of assertions of the following form:
- ClassAssertion( C a ) where C is a class
- ObjectPropertyAssertion( P a_{1} a_{2} ) where P is an object property
- DataPropertyAssertion( P a v ) where P is a data property
- SameIndividual( a_{1} ... a_{n} )
- DifferentIndividuals( a_{1} ... 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:
F is a consequence of O under the OWL 2 DL semantics if and only if RDF(F) is a consequence of RDF(O) ∪ AXIOMS under the standard first-order semantics.
The main result of this section seems intuitive, but do we have a formal proof?
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_{1} and CE_{2}, verify whether the interpretation of CE_{1} is a subset of the interpretation of CE_{2} 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.
Language | Reasoning Problems | Taxonomic Complexity | Data Complexity | Query Complexity | Combined Complexity |
---|---|---|---|---|---|
OWL 2 DL | Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking |
2NEXPTIME-complete | Open (NP-Hard) |
Not Applicable | 2NEXPTIME-complete |
Conjunctive Query Answering | Open* | Open* | Open* | Open* | |
OWL 1 DL | Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking |
NEXPTIME-complete | Open (NP-Hard) |
Not Applicable | NEXPTIME-complete |
Conjunctive Query Answering | Open* | Open* | Open* | Open* | |
Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking |
PTIME-complete | PTIME-complete | Not Applicable | PTIME-complete | |
Conjunctive Query Answering | PTIME-complete | PTIME-complete | NP-complete | PSPACE-complete | |
Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking, |
In PTIME | In LOGSPACE | Not Applicable | In PTIME | |
Conjunctive Query Answering | In PTIME | In LOGSPACE | NP-complete | NP-complete | |
Ontology Consistency, Class Expression Satisfiability, Class Expression Subsumption, Instance Checking |
PTIME-complete | PTIME-complete | Not Applicable | PTIME-complete | |
Conjunctive Query Answering | PTIME-complete | PTIME-complete | NP-complete | NP-complete |
In Table 6, I wonder if we should add references to papers establishing complexity results for various profiles.
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.