Difference between revisions of "Profiles"
IanHorrocks (Talk | contribs) m (→Introduction) |
(Action-120) |
||
Line 53: | Line 53: | ||
{{Review|[[User:JeremyCarroll|JeremyCarroll]] 11:41, 28 March 2008 (EDT)|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}} | {{Review|[[User:JeremyCarroll|JeremyCarroll]] 11:41, 28 March 2008 (EDT)|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. | + | Apart from the ones specified here, there are many other possible profiles of OWL 2. Although we don't specifically document OWL lite [<cite>[[#owl-1-reference|OWL 1 Reference]]</cite>] 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. |
{{EdNote|[[User:Bmotik2|Boris Motik]] 10:37, 03 April 2008 (EDT)|See [http://www.w3.org/2007/OWL/tracker/issues/108 ISSUE-108] The Working Group has not yet comitted itself to the names of different profiles. The names used in this document are likely to change in future.}} | {{EdNote|[[User:Bmotik2|Boris Motik]] 10:37, 03 April 2008 (EDT)|See [http://www.w3.org/2007/OWL/tracker/issues/108 ISSUE-108] The Working Group has not yet comitted itself to the names of different profiles. The names used in this document are likely to change in future.}} |
Revision as of 03:52, 23 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 DL 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 (ObjectSomeValuesFrom) or a data range (DataSomeValuesFrom) ,
- existential quantification to a nominal (ObjectHasValue) or a constant (DataHasValue) ,
- self quantification (ObjectExistsSelf),
- enumerations involving a single element (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),
- facts (SameIndividual, DifferentIndividuals, ClassAssertion, ObjectPropertyAssertion, DataPropertyAssertion, NegativeObjectPropertyAssertion, and NegativeDataPropertyAssertion),
- functional data properties (FunctionalDataProperty),
- a limited range of datatypes.
The following features of OWL 2 are missing in EL++:
- universal quantification to a class (ObjectAllValuesFrom) or a data range(DatAllaValuesFrom) ,
- counting quantification (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality),DataMaxCardinality, DataMinCardinality, and DataExactCardinality))
- disjunction (ObjectUnionOf, DisjointUnion),
- negation (ObjectComplementOf),
- enumerations involving multiple elements (ObjectOneOf, DataOneOf),
- disjoint properties (DisjointObjectProperties and DisjointDataProperties),
- irreflexive object properties (IrreflexiveObjectProperty),
- inverse object properties (InverseObjectProperties),
- functional object properties (FunctionalObjectProperty),
- symmetric object properties (SymmetricObjectProperty),
- asymmetric object property (AsymmetricObjectProperty).
2.2 Profile Specification
The productions for EL++ are defined in the following sections. All global restrictions on axioms from the [OWL 2 Specification] apply. An additional such restriction is imposed, as detailed below.
2.2.1 Entities
The entities of EL++ are exactly as in the entire OWL 2 language. Furthermore, EL++ supports the owl:Thing and owl:Nothing predefined classes that are interpreted as specified in [OWL 2 Specification].
EL++ supports the following datatypes:
- The unary datatype with URI 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
Furthermore, the following predefined datatypes of full OWL 2 are not available 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 Class Expressions
The design principle of EL++ is to focus on the class constructors ObjectIntersectionOf and ObjectSomeValuesFrom, which are used extensively in many large-scale ontologies. It additionally provides for objectExistsSelf, objectHasValue, dataSomeValuesFrom, dataHasValue, and objectOneOf enumerations that contain a single individual (called nominals in the DL literature). Thus, EL++ class descriptions are defined according to the following production:
objectSomeValuesFrom | objectExistsSelf | objectHasValue |
dataSomeValuesFrom | dataHasValue
The productions for class constructors are as defined in [OWL 2 Specification], with the exception of objectOneOf which admits only a single individual:
EL++ disallows ObjectUnionOf, ObjectComplementOf, ObjectAllValuesFrom, DataAllValuesFrom, ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality, DataMaxCardinality, DataMinCardinality, and DataExactCardinality.
2.2.3 Property Expressions
Inverse properties are not supported in EL++, and thus object property expressions are restricted to named properties. Data property expressions are as in OWL 2.
objectPropertyExpression := objectPropertyURI
2.2.4 Data Range Expressions
A data range expression is restricted in EL++ to the predefined datatypes admitted in EL++ and enumerated datatypes consisting of a single constant.
dataRange := datatypeURI | dataOneOf
dataOneOf := 'DataOneOf' '(' constant')'
EL++ does not support DataComplementOf and DatatypeRestriction (i.e., no facet is admitted).
2.2.5 Axioms
The class axioms of EL++ are the same as in full OWL 2, except that DisjointUnion is not allowed.
classAxiom := subClassOf | equivalentClasses | disjointClasses
The productions for all supported kinds class axioms are as in the [OWL 2 Specification], with the difference that they use the new description production. We refer to that document for details.
EL++ supports the following object property axioms.
objectPropertyAxiom :=
equivalentObjectProperties | subObjectPropertyOf |
objectPropertyDomain | objectPropertyRange |
transitiveObjectProperty|
reflexiveObjectProperty
The productions for all supported kinds of object property axioms are as in the [OWL 2 Specification]. EL++ disallows DisjointObjectProperties, IrreflexiveObjectProperty, InverseObjectProperties, FunctionalObjectProperty, SymmetricObjectProperty, and AsymmetricObjectProperty axioms.
Regarding data property axioms, EL++ provides the same facilities as OWL 2, except DisjointDataProperty. Therefore, data property axioms in EL++ are defined as follows.
dataPropertyAxiom :=
subDataPropertyOf |
equivalentDataProperties |
dataPropertyDomain |
dataPropertyRange |
functionalDataProperty
Again, the productions for all supported kinds of property axioms are as in the [OWL 2 Specification].
The facts in EL++ are the same as in OWL 2, with the diffence that descriptions and object property expressions are restricted as specified previously. 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 Restriction
The axiom closure Ax of an EL++ ontology must obey the restrictions described in Section 10 of the structural specification [OWL 2 Specification]. To obtain polytime reasoning problems, one additional restriction is imposed.
Let CE be a class expression. We say that Ax imposes a range restriction to CE on an object property PE_{1} if it contains axioms
- SubObjectPropertyOf(PE_{1} PE_{2}),...,SubObjectPropertyOf(PE_{k-1} PE_{k})
- ObjectPropertyRange(PE_{k} CE)
We require that if
- Ax contains SubObjectPropertyOf(SubObjectPropertyChain(PE_{1} ... PE_{n}) PE) and
- Ax imposes a range restriction to CE on PE
then Ax imposes a range restriction to CE on PE_{n}.
Remarks: (1) The restriction is vacuously true if the SubObjectPropertyOf in the first item is a role inclusion statement -- that is, if it does not contain SubObjectPropertyChain. (2) Range restrictions on reflexive and transitive roles are generally allowed, unless they are used in axioms following the forbidden pattern above.
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 (facts). 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 DL. Other variants trade property inclusion axioms for functionality and inverse-functionality of object properties.
I suggest that the following sentence should start "This profile is defined not only ...". The Note constuct is unnecessarily verbose, the word 'asymmetric' sounds technical but isn't and is confusing.
Note that the profile presented here is asymmetric: it 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 subclasses in SubClassOf axioms:
- OWL classes, except for owl:Thing
- existential quantification to a class ( ObjectSomeValuesFrom ) where the class is limited to owl:Thing,
The following constructs can be used to define superclasses in SubClassOf axioms:
- OWL classes
- existential quantification to a class ( ObjectSomeValuesFrom ) where the class is limited to owl:Thing,
- negation (ObjectComplementOf)
All class axioms in DL-Lite are constrained in a way that is compliant with these restrictions. For example, the property domain and range axioms are allowed to refer only to the superclasses mentioned above:
- class inclusion (SubClassOf),
- class equivalence (EquivalentClasses),
- class disjointness (DisjointClasses),
Moreover, DL-Lite allows for the following property axioms and facts:
- 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),
- facts (SameIndividual, DifferentIndividuals, ClassAssertion, ObjectPropertyAssertion)
The following features of OWL 2 are missing in DL-Lite:
- existential quantification to a class (ObjectSomeValuesFrom),
- self quantification (ObjectExistsSelf),
- existential quantification to a nominal (ObjectHasValue),
- nominals (ObjectOneOf),
- universal quantification to a class (ObjectAllValuesFrom),
- counting quantification (ObjectMaxCardinality, ObjectMinCardinality, ObjectExactCardinality),
- disjunction (ObjectUnionOf, DisjointUnion),
- property inclusion (SubObjectPropertyOf) involving property chains,
- transitivity (TransitiveObjectProperty),
- reflexivity (ReflexiveObjectProperty),
- irreflexivity (IrreflexiveObjectProperty),
- asymmetric properties (AsymmetricObjectProperty),
- (inverse)functional properties (FunctionalObjectProperty and InverseFunctionalObjectProperty)
3.2 Profile Specification
I fear the the second sentence may be misread as "the non-structural restrictions of the structural specification are dropped". Thus, I propose to rephrase it to "The expressive power of DL-Lite is such that the global restriction on axioms defined in the structural specification are vacuously satisfied".
The productions for DL-Lite are defined in the following sections. The global restricitons on axioms defined in the structural specification [OWL 2 Specification] are not enforced in DL-Lite.
3.2.1 Entities
DL-Lite supports all OWL 2 entities apart from data properties. The entities in DL-Lite are defined as follows.
entity := owlClass | objectProperty | annotationProperty | individual
The only well-known entity defined in DL-Lite is the class with URI owl:Thing, which is interpreted as specified in [OWL 2 Semantics].
3.2.2 Class Expressions
In DL-Lite, there are two types of class expressions. The subClass production defines the classes that can occur in the antecedents of implications; for example, such classes can occur as subclasses in a SubClassOf axiom. The superClass production defines the classes that can occur in the consequents of implications; for example, such classes can occur as superclasses in a SubClassOf axiom.
subClass :=
owlClassURI other than owl:Thing |
'ObjectSomeValuesFrom' '(' objectPropertyExpression owl:Thing ')'
superClass :=
subClass |
'ObjectComplementOf' '(' subClass ')'
Adding "objectIntersectionOf" in the production of "superClass" should be harmless.
3.2.3 Property Expressions
DL-Lite object property expressions are the same as in OWL 2 DL.
3.2.4 Axioms
DL-Lite axioms are defined to exclude membership assertions on data properties.
axiom := classAxiom | objectPropertyAxiom | fact | declaration | entityAnnotation
Furthermore, DL-Lite redefines all axioms from the functional-style syntax [OWL 2 Specification] that refer to the description production. In particular, it restricts various class axioms to appropriate forms of classes, and it disallows DisjointUnion. The production for axioms about classes in DL-Lite are defined as follows.
subClassOf := 'SubClassOf' '(' subClass superClass ')'
equivalentClasses := 'EquivalentClasses' '(' subClass subClass { subClass } ')'
disjointClasses := 'DisjointClasses' '(' subClass subClass { subClass } ')'
classAxiom := subClassOf | equivalentClasses | disjointClasses
DL-Lite disallows the use of property chains in property inclusion axioms (simple property inclusions are just like in OWL 2), it disallows the use of transitive, asymmetric, reflexive and irreflexive properties, and it redefines the domain and range axioms to use the new class productions.
objectPropertyDomain := 'ObjectPropertyDomain' '(' objectPropertyExpression superClass ')'
objectPropertyRange := 'ObjectPropertyRange' '(' objectPropertyExpression superClass ')'
objectPropertyAxiom :=
subObjectPropertyOf | equivalentObjectProperties |
disjointObjectProperties | inverseObjectProperties |
objectPropertyDomain | objectPropertyRange |
symmetricObjectProperty
DL-Lite disallows axioms about data properties and negative object property assertion. Furthermore, class membership assertions in DL-Lite are restricted to only atomic classes. Equality and inequality axioms and property membership assertions are the same as in OWL 2. Therefore, the fact axioms of DL-Lite are defined as follows.
classAssertion := 'ClassAssertion' '(' individualURI classURI ')'
fact := 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 DL 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 DL -- that is, it places syntactic restrictions on OWL 2 DL axioms. For example, in this definition, one cannot declare an OWL 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
first para could perhaps introduce features of OWL-R, not OWL-R DL: e.g.
OWL-R is a fairly expressive profile of OWL 2 designed to be implementable with relatively simple technology. The restrictions on the complexity are expressed in two different ways: OWL-R DL restricts the syntax of the documents to not use features which are harder to implement; whereas OWL-R Full provides a conformance point for reasoners which acts as a partial implementation of the OWL Full semantics.
OWL-R, although just a profile of OWL 2, is quite expressive. An OWL-R DL ontology can use, in a nutshell, most OWL 2 language constructs except owl:cardinality, owl:minCardinality, owl2:NegativeObjectPropertyAssertion, owl2:NegativeDataPropertyAssertion, and owl:complementOf.
Not all constructs of OWL-R DL can be used freely in all places in the axioms. For example, in SubClassOf axioms, the usage of the constructs on the left- and right-hand side of the implication must follow the patterns shown in Table 4.1.
Left-Hand Side | Right-Hand Side |
---|---|
an OWL class a nominal class (OneOf) intersection of classes (ObjectIntersectionOf) union of classes (ObjectUnionOf) existential quantification to an OWL class (ObjectSomeValuesFrom) existential quantification to a nominal (ObjectHasValue) |
an OWL class intersection of classes (ObjectIntersectionOf) universal quantification to a class (ObjectAllValuesFrom) at-most 1 cardinality restrictions (ObjectMaxCardinality 1) existential quantification to a nominal (ObjectHasValue) |
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
Unlike OWL-R DL, in OWL-R Full 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, that "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 owl2:ReflexiveProperty owl2:IrreflexiveProperty owl:SymmetricProperty owl2:AsymmetricProperty owl:TransitiveProperty rdfs:subPropertyOf owl2:propertyChain owl:equivalentProperty owl2:propertyDisjointWith owl2:disjointDataProperties 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 |
4.2 OWL-R DL
OWL-R DL is a syntactic profile of OWL 2 DL. 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. Therefore, entities defined here are the same as in [OWL 2 Specification]. Furthermore, OWL-R defines the same set of well-known entities as the entire OWL 2 language:
- The class with URI owl:Thing is the set of all objects. (In DL literature this is often called the top concept.)
- The class with URI owl:Nothing is the empty set of objects. (In DL literature this is often called the bottom concept.)
- The unary datatype with URI rdfs:Literal is the set of all concrete objects.
- The datatypes with URIs as mentioned in [OWL 2 Semantics].
4.2.2 Data Ranges
A data range expression defines a range over data values. In OWL-R DL, a data range expression is restricted to either a named atomic datatype (the list of datatypes supported by OWL-R DL is identical to the one in [OWL 2 Semantics]) or a datatype restriction, specified by applying some facets to limit the value space of an pre-existing datatype.
dataRange := datatypeURI | datatypeRestriction
4.2.3 Classes
There are three types of classes in OWL-R. The subClass production defines the classes that can occur in the antecedents of implications; for example, such classes can occur as subclasses in a SubClassOf axiom. The superClass production defines the classes that can occur in the consequents of implications; for example, such classes can occur as superclasses in a SubClassOf axiom. Finally, the equivClass production defines the classes that can occur in an EquivalentClasses axiom.
zeroOrOne := '0' | '1'
subClass :=
owlClassURI other than owl:Thing |
'ObjectOneOf' '(' individualURI { individualURI } ')'
'ObjectIntersectionOf' '(' subClass subClass { subClass } ')' |
'ObjectUnionOf' '(' subClass subClass { subClass } ')' |
'ObjectSomeValuesFrom' '(' objectPropertyExpression subClass ')' |
'DataSomeValuesFrom' '(' dataPropertyExpression { dataPropertyExpression } dataRange ')' |
'ObjectHasValue' '(' objectPropertyExpression individualURI ')' |
'DataHasValue' '(' dataPropertyExpression constant ')'
superClass :=
owlClassURI |
'ObjectIntersectionOf' '(' subClass superClass { superClass } ')' |
'ObjectAllValuesFrom' '(' objectPropertyExpression superClass ')' |
'DataAllValuesFrom' '(' dataPropertyExpression { dataPropertyExpression } dataRange ')' |
'ObjectMaxCardinality' '(' zeroOrOne objectPropertyExpression [ subClass ] ')' |
'DataMaxCardinality' '(' zeroOrOne dataPropertyExpression [ dataRange ] ')' |
'ObjectHasValue' '(' objectPropertyExpression individualURI ')' |
'DataHasValue' '(' dataPropertyExpression constant ')'
equivClass :=
owlClassURI other than owl:Thing |
'ObjectIntersectionOf' '(' equivClass equivClass { equivClass } ')' |
'ObjectHasValue' '(' objectPropertyExpression individualURI ')' |
'DataHasValue' '(' dataPropertyExpression constant ')'
4.2.4 Properties
OWL-R constructs used to build more complex properties from existing ones are identical to the ones defined in [OWL 2 Specification].
4.2.5 Axioms
OWL-R redefines all axioms from the functional-style syntax OWL 2 Specification that refer to the description production. In particular, it restricts various class axioms to use the appropriate form of class expressions (i.e. one of subClass , superClass, or equivClass), and it disallows the DisjointUnion axiom.
classAxiom := subClassOf | equivalentClasses | disjointClasses
subClassOf := 'SubClassOf' '(' subClass superClass ')'
equivalentClasses := 'EquivalentClasses' '(' equivClass equivClass { equivClass } ')'
disjointClasses := 'DisjointClasses' '(' subClass subClass { subClass } ')'
OWL-R property expression language is very similar to OWL 2. The only difference is that OWL-R restricts property domain and range axioms to the appropriate form of class expressions as follows:
objectPropertyDomain := 'ObjectPropertyDomain' '(' objectPropertyExpression superClass ')'
objectPropertyRange := 'ObjectPropertyRange' '(' objectPropertyExpression superClass ')'
dataPropertyDomain := 'DataPropertyDomain' '(' dataPropertyExpression superClass ')'
Therefore, axioms about object and data properties in OWL-R are defined as follows.
objectPropertyAxiom :=
objectPropertyDomain | objectPropertyRange |
subObjectPropertyOf | equivalentObjectProperties |
disjointObjectProperties | inverseObjectProperties |
functionalObjectProperty | inverseFunctionalObjectProperty |
reflexiveObjectProperty | irreflexiveObjectProperty |
symmetricObjectProperty | asymmetricObjectProperty |
transitiveObjectProperty
dataPropertyAxiom :=
dataPropertyDomain | dataPropertyRange |
subDataPropertyOf | equivalentDataProperties | disjointDataProperties |
functionalDataProperty
OWL-R restricts the positive facts to a particular type of classes, and it disallows negative property assertions. Equality and inequality between individuals and positive facts are the same as in the entire OWL 2. Therefore, facts in OWL-R are defined as follows.
classAssertion := 'ClassAssertion' '(' individualURI superClass ')'
fact :=
sameIndividual | differentIndividuals | classAssertion |
objectPropertyAssertion | dataPropertyAssertion
Finally, the axioms in OWL-R are defined as follows.
axiom := classAxiom | objectPropertyAxiom | dataPropertyAxiom | fact | declaration | entityAnnotation
4.3 OWL-R Full
OWL-R Full is defined by weakening the semantic conditions on an interpretation from OWL 2 Full. An equivalent definition is also provided in terms of an "axiomatization" using first order implications. The latter definition should provide a useful starting point for practical implementation using rule-based technologies. It is based on [pD*].
Sections 4.3.1 and 4.3.2 are claimed to be equivalent, which seems intuitive, but do we have a formal proof?
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 tradeoff seems appropriate to us but this is a choice that should be highlighted during public review.
4.3.1 Weakened OWL 2 Full Semantic Conditions
I find this section a bit difficult to read probably because I am not as familiar with OWL Full semantics as the authors. I had to go back and reread OWL Full semantics before having a better grasp on this section. I think readability could be significantly improved by very briefly reminding the definitions of IOT, LVi , IX, EXTi, Si, IOR, IOC, IDC, IOOP, IODP, CEXTi. Those reminders don’t have to be formal definitions (e.g. IOT could be defined as "the set of OWL individuals", LVi as "the set of literal values", etc).----Achille 10:16, 26 March 2008 (EDT): Issue addressed by the addition of a brief subsection definition the main elements of OWL 2 Full Semantics
Since the axiomatic first order semantics given in section 4.3.2 is much straightforward, self-contanined (at least in the sense that it does not require a deep familiarity with OWL Full semantics), and equivalent to the weakened OWL 2 Full semantic given in section 4.3.1, I would suggest to move section 4.3.1 to an appendix.----Achille 10:16, 26 March 2008 (EDT): Addressed by the addition of a brief subsection definition the main elements of OWL 2 Full Semantics, and by a sentence pointing section 4.3.2 as being self-contained.
This section defines OWL-R Full by weakening the OWL 2 Full semantic conditions on an interpretation.
I suggest a reference with 'in preparation' and a link to editor's draft
4.3.1.1 Main elements of OWL 2 Full Semantics
Before specifying in more details how the semantic weakining is performed for various features of OWL-R Full, we briefly present here the main elements of OWL 2 Full semantics.
First, a datatype map D is a partial mapping from URI references to datatypes that maps xsd:string and xsd:integer to the appropriate XML Schema datatypes.
Next, the OWL 2 Full model-theoretic semantics defines an interpretation as follows.
next sentence: 'RDF, RDFS and OWL vocabulary'?
From OWL 2 Full Semantics, for V a set of URI references and literals containing the RDF, RDFS and OWL vocabulary and 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, i.e., 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 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∈RI | <x,c>∈EXT_{I}(S_{I}(rdf:type)) }. CEXT_{I}(c) maps a class c to its extension. 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 OWL 2 Full semantic conditions. IOOP denotes the set of OWL object properties, and IODP 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.
4.3.1.2 Restrictions defining OWL-R Full
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 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 preceeded with the question mark. 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 1 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
Rule name | If | then |
---|---|---|
RE1 | T(?s, ?p, ?o) |
T(?s, owl:sameAs, ?s) T(?p, owl:sameAs, ?p) T(?o, owl:sameAs, ?o) |
RE2 | T(?x, owl:sameAs, ?y) | T(?y, owl:sameAs, ?x) |
RE3 | T(?x, owl:sameAs, ?y) T(?y, owl:sameAs, ?z) |
T(?x, owl:sameAs, ?z) |
RE4 | T(?s, owl:sameAs, ?s') T(?s, ?p, ?o) |
T(?s', ?p, ?o) |
RE5 | T(?p, owl:sameAs, ?p') T(?s, ?p, ?o) |
T(?s, ?p', ?o) |
RE6 | T(?o, owl:sameAs, ?o') T(?s, ?p, ?o) |
T(?s, ?p, ?o') |
RE7 | T(?x, owl:sameAs, ?y) T(?x, owl:differentFrom, ?y) |
false |
Defining something instead of ... for the list syntax would be an improvement. Maybe some explicit foralls.
Table 2 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, owl2:ReflexiveProperty) T(?x, ?y, ?z) |
T(?x, ?p, ?x) T(?y, ?p, ?y) T(?z, ?p, ?z) |
T(?p, rdf:type, owl2:IrreflexiveProperty) T(?x, ?p, ?x) |
false |
T(?p, rdf:type, owl:SymmetricProperty) T(?x, ?p, ?y) |
T(?y, ?p, ?x) |
T(?p, rdf:type, owl2: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(?x_{1}, rdf:first, ?p_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?p_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?p_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?sc, owl2:propertyChain, ?x_{1}) 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}, owl2:propertyDisjointWith, ?p_{2}) T(?x, ?p_{1}, ?y) T(?x, ?p_{2}, ?y) |
false |
T(?p_{1}, owl2:disjointDataProperties, ?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) |
T(?p_{1}, owl2:inverseObjectPropertyExpression, ?p_{2}) T(?x, ?p_{1}, ?y) |
T(?y, ?p_{2}, ?x) |
T(?p_{1}, owl2:inverseObjectPropertyExpression, ?p_{2}) T(?x, ?p_{2}, ?y) |
T(?y, ?p_{1}, ?x) |
Table 3 specifies the semantic conditions on classes.
Preumably the line ... to ... is an error.
Answer by Boris Motik: This is not an error. I wanted to show here that the rule has to be instantiated fro any i between 1 and n. I agree that this is not all that nice and/or clear, so we can think of how to make it nicer; however, this needs to be reflected.
If | then |
---|---|
T(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:intersectionOf, ?x_{1}) T(?y, rdf:type, ?c_{1}) T(?y, rdf:type, ?c_{2}) ... T(?y, rdf:type, ?c_{n}) |
T(?y, rdf:type, ?c) |
T(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:intersectionOf, ?x_{1}) T(?y, rdf:type, ?c) |
T(?y, rdf:type, ?c_{1}) T(?y, rdf:type, ?c_{2}) ... T(?y, rdf:type, ?c_{n}) |
T(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:unionOf, ?x_{1}) T(?y, rdf:type, ?c_{1}) |
T(?y, rdf:type, ?c) |
... | ... |
T(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:unionOf, ?x_{1}) T(?y, rdf:type, ?c_{n}) |
T(?y, rdf:type, ?c) |
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}) |
Table 4 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 5 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(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:intersectionOf, ?x_{1}) |
T(?c, rdfs:subClassOf, ?c_{1}) T(?c, rdfs:subClassOf, ?c_{2}) ... T(?c, rdfs:subClassOf, ?c_{n}) |
T(?x_{1}, rdf:first, ?c_{1}) T(?x_{1}, rdf:rest, ?x_{2}) T(?x_{2}, rdf:first, ?c_{2}) T(?x_{2}, rdf:rest, ?x_{3}) ... T(?x_{n}, rdf:first, ?c_{n}) T(?x_{n}, rdf:rest, rdf:nil) T(?c, owl:unionOf, ?x_{1}) |
T(?c_{1}, rdfs:subClassOf, ?c) T(?c_{2}, rdfs:subClassOf, ?c) ... T(?c_{n}, rdfs:subClassOf, ?c) |
Should soemthing be specified about literals
Should the expected behaviour on false be specified
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; let F be a set of assertions of the following form:
- ClassAssertion( i C ) where C is an OWL class
- ObjectPropertyAssertion( P i_{1} i_{2} ) where P is an object property
- DataPropertyAssertion( P i v ) where P is a data property
- SameIndividual( i_{1} ... i_{n} )
- DifferentIndividuals( i_{1} ... i_{n} )
Furthermore, let RDF(O) and RDF(F) be the translations of O and F into RDF graphs as specified in the RDF mapping [ 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 DL and OWL 2 Full, the problems of ontology consistency, concept satisfiability, concept 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 diferent algorithmic solutions.
This section describes the computational complexity of the most relevant reasoning problems in the languages introduced so far. The reasoning problems considered here are the following:
- Ontology Consistency: Check whether a given ontology has at least one model.
- Concept Satisfiability: Given an ontology O and a class A, verify whether there is a model of O in which the interpretation of A is a nonempty set.
- Concept Subsumption: Given an ontology O and two classes A, B, verify whether the interpretation of A is a subset of the interpretation of B in every model of O
- Instance Checking: Given an ontology, an individual a and a class A, verify whether a is an instance of A in every model of the ontology.
- Conjunctive Query Answering: Given an ontology O and a conjunctive query q, return the answers of the query with respect to O.
When evaluating the complexity, the following parameters will be considered:
- Data Complexity: the complexity measured with respect to the total size of the facts 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.
I think we should define more precisely what we mean by conjunctive query. Some people might consider that, for pragmatic reasons, all variables are distinguished, which will make query answering less expensive in some cases.
Table 6 summarizes the known complexity results for OWL 2 DL, OWL 1 DL, EL++, DL-Lite, and OWL-R. Whenever the complexity for a given problem is described as Open, with a star, (*), it is meant that its decidability is still an open question; if the star (*) is omitted, then the problem is known to be decidable but precise complexity bounds have not yet been established.
In Table 6, I wonder if we should add references to papers establishing complexity results for various profiles.
Language | Reasoning Problems | Taxonomic Complexity | Data Complexity | Query Complexity | Combined Complexity |
---|---|---|---|---|---|
OWL 2 DL | Ontology Consistency, Concept Satisfiability, Concept Subsumption, Instance Checking |
2NEXPTIME-complete | Open (NP-Hard) |
Not Applicable | 2NEXPTIME-complete |
Conjunctive Query Answering | Open* | Open* | Open* | Open* | |
OWL 1 DL | Ontology Consistency, Concept Satisfiability, Concept Subsumption, Instance Checking |
NEXPTIME-complete | Open (NP-Hard) |
Not Applicable | NEXPTIME-complete |
Conjunctive Query Answering | Open* | Open* | Open* | Open* | |
Ontology Consistency, Concept Satisfiability, Concept Subsumption, Instance Checking |
PTIME-complete | PTIME-complete | Not Applicable | PTIME-complete | |
Conjunctive Query Answering | PTIME-complete | PTIME-complete | NP-complete | PSPACE-complete | |
Ontology Consistency, Concept Satisfiability, Concept Subsumption, Instance Checking, |
In PTIME | In LOGSPACE | Not Applicable | In PTIME | |
Conjunctive Query Answering | In PTIME | In LOGSPACE | NP-complete | NP-complete | |
Ontology Consistency, Concept Satisfiability, Concept Subsumption, Instance Checking |
PTIME-complete | PTIME-complete | Not Applicable | PTIME-complete | |
Conjunctive Query Answering | PTIME-complete | PTIME-complete | NP-complete | NP-complete |
In DL-Lite, instance checking and conjunctive query evaluation can be performed by exploiting relational database technology, i.e., through a translation to SQL queries. The fact that data complexity goes beyond LOGSPACE means that query answering and instance checking require more powerful engines than the ones provided by relational database technologies. PTIME-hardness essentially requires Datalog technologies. For the CoNP cases, Disjunctive Datalog technologies could be adopted.
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., 2006.
- [OWL 2 Semantics]
- OWL 2 Web Ontology Language: Model-Theoretic Semantics. Bernardo Cuenca Grau and Boris Motik, eds., 2006.
- [OWL 2 RDF Mapping]
- OWL 2 Web Ontology Language: Mapping to RDF Graphs. Bernardo Cuenca Grau and Boris Motik, eds., 2006.
- [OWL 1 Reference]
- OWL Web Ontology Language Reference. Sean Bechhofer, Frank van Harmelen, Jim Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, Lynn Andrea Stein, 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 2008), 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.