Copyright © 2008 W3C® (MIT, ERCIM, Keio), All Rights Reserved. W3C liability, trademark and document use rules apply.
This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.
This document is being published as one of a set of 6 documents:
The OWL Working Group seeks public feedback on these Working Drafts. Please send your comments to public-owl-comments@w3.org (public archive). If possible, please offer specific changes to the text that would address your concern.
Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.
This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.
Contents |
This document describes three important fragments of OWL 1.1. Most fragments are defined by placing restrictions on the syntax of OWL 1.1. These restrictions have been specified by modifying some of the productions of the functional-style syntax [OWL 1.1 Specification].
From a specification perspective, most OWL fragments differ from each other in three important ways:
However, OWL fragments share important features that are presented in this section.
As in [OWL 1.1 Specification], the grammar of an OWL fragment is presented in the standard BNF notation. Nonterminal symbols are written in bold (e.g., owlClassURI), terminal symbols are written in single quotes (e.g. 'ObjectPropertyRange'), zero or more instances of a symbol is denoted with curly braces (e.g., { description }), alternative productions are denoted with the vertical bar (e.g., fact | declaration), and zero or one instances of a symbol are denoted with square brackets (e.g., [ description ]).
Regardless of the considered fragment, an ontology consists of a set of axioms and may include axioms from other, imported, ontologies. The following basic syntax of an ontology is shared by all three fragments of OWL 1.1:
ontologyFile:= { namespace } ontology
namespace:= 'Namespace' '(' [ prefix ] '=' Full-IRI ')'
ontology:= 'Ontology' '(' [ ontologyURI ] { import } { annotation } { axiom } ')'
ontologyURI:= URI
import:= 'Import' '(' URI ')'
The namespace production defines an abbreviation for namespaces in a document. The details of the Full-IRI and URI, used to uniquely identified a resource, and of annotation, which has no effects on the semantics, are given in section 2.2 of [OWL 1.1 Specification].
All fragments support two types of axioms with no effects on their semantics: declaration and entityAnnotation.
A declaration declares the existence of an entity. It can be used to check the structural consistency of an ontology (e.g. check that all entity URIs used in an ontology corresponds to an declared entity). The grammar for declarations is as follows:
declaration:= 'Declaration' '(' { annotation } entity ')'
An entityAnnotation provides a mechanism to annotate an entity:
annotationForAxiom:= annotation
annotationForEntity:= annotation
entityAnnotation:= 'EntityAnnotation' '(' { annotationForAxiom } entity annotationForEntity { annotationForEntity } ')'
Editor's Note: The version of EL++ defined in this document is known to have minor open issues that can make reasoning intractable.
EL++ [EL++] is a syntactic fragment of OWL 1.1 that admits sound and complete reasoning in polynomial time with respect to the size of the ontology. Many large-scale biomedical ontologies, such as SNOMED CT, fall within this fragment.
EL++ provides the following features:
The following features of OWL 1.1 are missing in EL++:
The productions for EL++ are defined in the following sections. All the nonstructural restrictions on axioms are exactly as in Section 10 of the structural specification [OWL 1.1 Specification].
EL++ does not impose any restrictions on OWL 1.1 Entities. Therefore, entities defined here are the same as in [OWL 1.1 Specification]
All entities may have an associated URI. The syntax for writing entity URIs in EL++ is as follows:
datatypeURI:= URI
owlClassURI:= URI
objectPropertyURI:= URI
dataPropertyURI:= URI
annotationPropertyURI:= URI
individualURI:= URI
Entities are written in the following way:
entity:= datatype | owlClass | objectProperty | dataProperty | annotationProperty | individual
datatype:= 'Datatype' '(' datatypeURI ')'
owlClass:= 'OWLClass' '(' owlClassURI ')'
objectProperty:= 'ObjectProperty' '(' objectPropertyURI ')'
dataProperty:= 'DataProperty' '(' dataPropertyURI ')'
annotationProperty:= 'AnnotationProperty' '(' annotationPropertyURI ')'
individual:= 'Individual' '(' individualURI ')'
EL++ defines the same set of well-known entities as the whole OWL 1.1 language. These entities are identified by the following predefined URIs:
Class expressions can be thought of as descriptions of sets of individuals, or as descriptions which are true (or false) of particular individuals. The language for defining class expressions in EL++ is much restricted compared to OWL 1.1 DL. EL++ disallows ObjectAllValuesFrom, DataAllValuesFrom, ObjectMaxCardinality, ObjectMinCardinality, and ObjectExactCardinality restrictions, ObjectComplementOf, DataMaxCardinality, DataMinCardinality and DataExactCardinality. Moreover, ObjectOneOf enumerations in EL++ can contain only one element. Therefore, EL++ descriptions are defined as follows.
description:= owlClassURI | objectIntersectionOf | objectOneOf |
objectSomeValuesFrom | objectExistsSelf | objectHasValue |
dataSomeValuesFrom | dataHasValue
Of all class expressions in EL++, only objectOneOf is different from the one defined in [OWL 1.1 Specification]. EL++ objectOneOf enumeration contains a single individual:
objectOneOf:= 'ObjectOneOf' '(' individualURI')'
objectIntersectionOf, which is a conjunction of a set of descriptions, objectSomeValuesFrom (resp. dataSomeValuesFrom), which denotes the set of objects that are connected via the given object (resp. data) property to at least one instance of the given description (resp. at least one literal of the given data range), objectExistsSelf, which denotes the set of objects that are connected to themselves via the given object property, objectHasValue (resp. dataHasValue), which denotes the set of objects that are connected via the given object (resp. data) property to the object denoted by the given individual (resp. to the given constant), are unchanged:
objectIntersectionOf:= 'ObjectIntersectionOf' '(' description description { description } ')'
objectSomeValuesFrom:= 'ObjectSomeValuesFrom' '(' objectPropertyExpression description ')'
objectExistsSelf:= 'ObjectExistsSelf' '(' objectPropertyExpression ')'
objectHasValue:= 'ObjectHasValue' '(' objectPropertyExpression individualURI ')'
dataSomeValuesFrom:= 'DataSomeValuesFrom' '(' dataPropertyExpression { dataPropertyExpression } dataRange ')'
dataHasValue:= 'DataHasValue' '(' dataPropertyExpression constant ')'
EL++ object and data property expressions are restricted to named properties. Inverse properties are not supported in EL++. Therefore, property expressions are defined as follows:
objectPropertyExpression:= objectPropertyURI
dataPropertyExpression:= dataPropertyURI
A data range expression defines a range over data values. In EL++, a data range expression is restricted to named atomic datatypes (e.g. the list of datatypes supported by EL++ is the same as the one in [OWL 1.1 Semantics]), enumerated datatypes consisting of a single constant, and datatype restrictions, specified by applying some facets to limit the value space of an pre-existing datatype.
dataRange:= datatypeURI | dataOneOf | datatypeRestriction
dataOneOf:= 'DataOneOf' '(' constant')'
datatypeRestriction:= 'DatatypeRestriction' '(' datatypeURI datatypeFacet restrictionValue { datatypeFacet restrictionValue } ')'
datatypeFacet:=
'length' | 'minLength' | 'maxLength' | 'pattern' |
'minInclusive' | 'minExclusive' | 'maxInclusive' | 'maxExclusive' |
'totalDigits' | 'fractionDigits'
restrictionValue:= constant
EL++ axioms are as follows:
axiom:= classAxiom | objectPropertyAxiom | dataPropertyAxiom | fact | declaration | entityAnnotation
EL++ disallows DisjointUnion. All other class axioms are the same as in OWL 1.1, with the difference that they use the new description production.
classAxiom:= subClassOf | equivalentClasses | disjointClasses
subClass:= description
superClass:= description
subClassOf:= 'SubClassOf' '(' { annotation } subClass superClass ')'
equivalentClasses:= 'EquivalentClasses' '(' { annotation } description description { description } ')'
disjointClasses:= 'DisjointClasses' '(' { annotation } description description { description } ')'
EL++ disallows DisjointObjectProperties, IrreflexiveObjectProperty, InverseObjectProperties, FunctionalObjectProperty, SymmetricObjectProperty, and AsymmetricObjectProperty axioms. Therefore, object property axioms in EL++ are defined as follows.
objectPropertyAxiom:=
equivalentObjectProperties | subObjectPropertyOf |
objectPropertyDomain | objectPropertyRange |
transitiveObjectProperty|
reflexiveObjectProperty
All object property axioms supported by EL++ are the same as in OWL 1.1, with the difference that they use the new description production. For your convenience, their definition is provided below:
subObjectPropertyOf:= 'SubObjectPropertyOf' '(' { annotation } subObjectPropertyExpression objectPropertyExpression ')'
subObjectPropertyExpression:= objectPropertyExpression | 'SubObjectPropertyChain' '(' objectPropertyExpression objectPropertyExpression { objectPropertyExpression } ')'
equivalentObjectProperties:= 'EquivalentObjectProperties' '(' { annotation } objectPropertyExpression objectPropertyExpression { objectPropertyExpression } ')'
objectPropertyDomain:= 'ObjectPropertyDomain' '(' { annotation } objectPropertyExpression description ')'
objectPropertyRange:= 'ObjectPropertyRange' '(' { annotation } objectPropertyExpression description ')'
reflexiveObjectProperty:= 'ReflexiveObjectProperty' '(' { annotation } objectPropertyExpression ')'
transitiveObjectProperty:= 'TransitiveObjectProperty' '(' { annotation } objectPropertyExpression ')'
EL++ disallows the FunctionalDataProperty axioms. Therefore, data property axioms in EL++ are defined as follows.
dataPropertyAxiom:=
subDataPropertyOf |
equivalentDataProperties |
disjointDataProperties |
dataPropertyDomain |
dataPropertyRange
All data property axioms supported by EL++ are the same as in OWL 1.1, with the difference that they use the new description production. For your convenience, their definition is provided below:
subDataPropertyOf:= 'SubDataPropertyOf' '(' { annotation } dataPropertyExpression dataPropertyExpression ')'
equivalentDataProperties:= 'EquivalentDataProperties' '(' { annotation } dataPropertyExpression dataPropertyExpression { dataPropertyExpression } ')'
disjointDataProperties:= 'DisjointDataProperties' '(' { annotation } dataPropertyExpression dataPropertyExpression { dataPropertyExpression } ')'
dataPropertyDomain:= 'DataPropertyDomain' '(' { annotation } dataPropertyExpression description ')'
dataPropertyRange:= 'DataPropertyRange' '(' { annotation } dataPropertyExpression dataRange ')'
EL++ fact axioms are almost the same as in OWL 1.1, with the difference that they use the new description and dataRange productions.
fact:= sameIndividual | differentIndividuals | classAssertion |
objectPropertyAssertion |
dataPropertyAssertion|
NegativeObjectPropertyAssertion | NegativeDataPropertyAssertion
sameIndividual:= 'SameIndividual' '(' { annotation } individualURI individualURI { individualURI } ')'
differentIndividuals:= 'DifferentIndividuals' '(' { annotation } individualURI individualURI { individualURI } ')'
classAssertion:= 'ClassAssertion' '(' { annotation } individualURI description ')'
objectPropertyAssertion:= 'ObjectPropertyAssertion' '(' { annotation } objectPropertyExpression sourceIndividualURI targetIndividualURI ')'
dataPropertyAssertion:= 'DataPropertyAssertion' '(' { annotation } dataPropertyExpression sourceIndividualURI targetValue ')'
negativeObjectPropertyAssertion:= 'NegativeObjectPropertyAssertion' '(' { annotation } objectPropertyExpression sourceIndividualURI targetIndividualURI ')'
negativeDataPropertyAssertion:= 'NegativeDataPropertyAssertion' '(' { annotation } dataPropertyExpression sourceIndividualURI targetValue ')'
targetValue:= constant
sourceIndividualURI:= individualURI
targetIndividualURI:= individualURI
DL-Lite is a syntactic fragment of OWL 1.1 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-LiteR since it allows for property inclusion axioms; it therefore contains the intersection between RDFS and OWL 1.1 DL. Other variants trade property inclusion axioms for functionality and inverse-functionality of object properties.
Note that the fragment 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.
Editor's Note: Please note that Data Properties are not yet incorporated into DL-Lite in this draft, pending consultation with some DL-Lite experts.
Editor's Note: See ISSUE-80 (DL-Lite) This document currently contains the DL-liteR version of DL-lite. In future versions of this document, however, this language is likely to be extended with additional constructs that preserve its computational properties, such as Data Properties and suitably restricted Functional Properties.
The following constructs can be used to define subclasses in SubClassOf axioms:
The following constructs can be used to define superclasses in SubClassOf axioms:
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:
Moreover, DL-Lite allows for the following property axioms and facts:
The following features of OWL 1.1 are missing in DL-Lite:
The productions for DL-Lite are defined in the following sections. No nonstructural restricitons on axioms defined in the structural specification [OWL 1.1 Specification] apply to DL-Lite.
Editor's Note: Please note that Data Properties are not yet incorporated into DL-Lite in this draft, pending consultation with some DL-Lite experts.
DL Lite supports all OWL 1.1 Entities except datatype and dataProperty. All entities may have an associated URI. The syntax for writing entity URIs in EL++ is as follows:
owlClassURI:= URI
objectPropertyURI:= URI
annotationPropertyURI:= URI
individualURI:= URI
Entities are written in the following way:
entity:= owlClass | objectProperty | annotationProperty | individual
owlClass:= 'OWLClass' '(' owlClassURI ')'
objectProperty:= 'ObjectProperty' '(' objectPropertyURI ')'
annotationProperty:= 'AnnotationProperty' '(' annotationPropertyURI ')'
individual:= 'Individual' '(' individualURI ')'
The only well-known entity defined in DL Lite us the class with URI owl:Thing, which corresponds to the set of all objects. (In DL literature this is often called the top concept.)
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 ')'
A DL Lite property expression is either named object property or inverse of an property exxpression:
objectPropertyExpression:= objectPropertyURI | inverseObjectProperty
inverseObjectProperty:= 'InverseObjectProperty' '(' objectPropertyExpression ')'
DL Lite axioms are as follows (dataPropertyAxiom is not supported):
axiom:= classAxiom | objectPropertyAxiom | fact | declaration | entityAnnotation
Furthermore, DL-Lite redefines all axioms from the functional-style syntax [OWL 1.1 Specification] that refer to the description production. In particular, it restricts various class axioms to appropriate forms of classes, and it disallows DisjointUnion. DL Lite classAxiom production is as follows:
classAxiom:= subClassOf | equivalentClasses | disjointClasses
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; moreover, it disallows the use of transitive, asymmetric, reflexive and irreflexive properties. Finally, it redefines the domain and range axioms to use the new class productions.
objectPropertyAxiom:=
subObjectPropertyOf | equivalentObjectProperties |
disjointObjectProperties | inverseObjectProperties |
objectPropertyDomain | objectPropertyRange |
symmetricObjectProperty
subObjectPropertyOf:= 'SubObjectPropertyOf' '(' objectPropertyExpression objectPropertyExpression ')'
objectPropertyDomain:= 'ObjectPropertyDomain' '(' objectPropertyExpression superClass ')'
objectPropertyRange:= 'ObjectPropertyRange' '(' objectPropertyExpression superClass ')'
Editor's Note: I assume that negativeObjectPropertyAssertion is not supported by DL-Lite
Finally, DL-Lite disallows axioms about data properties and negative object property assertion, and class membership assertions in DL-Lite are restricted to only atomic classes. Therefore, the fact axioms of DL-Lite are defined as follows:
fact:= sameIndividual | differentIndividuals | classAssertion |
objectPropertyAssertion
classAssertion:= 'ClassAssertion' '(' individualURI classURI ')'
sameIndividual:= 'SameIndividual' '(' { annotation } individualURI individualURI { individualURI } ')'
differentIndividuals:= 'DifferentIndividuals' '(' { annotation } individualURI individualURI { individualURI } ')'
objectPropertyAssertion:= 'ObjectPropertyAssertion' '(' { annotation } objectPropertyExpression sourceIndividualURI targetIndividualURI ')'
sourceIndividualURI:= individualURI
targetIndividualURI:= individualURI
OWL-R is a fragment of OWL 1.1 that allows for scalable reasoning using rule-based technologies. The fragment 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 1.1 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 one, OWL-R DL, is a syntactic fragment of OWL 1.1 DL, specifying syntactic restrictions on OWL 1.1 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 second variant, OWL-R Full, does not place any restrictions on the syntax; rather, it weakens the extensional semantic conditions that are used for OWL 1.1 Full interpretations. 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.
OWL-R is a fairly expressive fragment of OWL 1.1 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 fragment of OWL 1.1, is quite expressive. An OWL-R DL ontology can use, in a nutshell, most OWL 1.1 language constructs except owl:cardinality, owl:minCardinality, owl11:NegativeObjectPropertyAssertion, owl11: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) |
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 1.1 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 owl11:ReflexiveProperty owl11:IrreflexiveProperty owl:SymmetricProperty owl11:AsymmetricProperty owl:TransitiveProperty rdfs:subPropertyOf owl11:propertyChain owl:equivalentProperties owl11:disjointObjectProperties owl11: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 |
OWL-R DL is a syntactic fragment of OWL 1.1 DL. The fragment 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.
OWL-R DL does not impose any restrictions on OWL 1.1 Entities. Therefore, entities defined here are the same as in [OWL 1.1 Specification]
All entities may have an associated URI. The syntax for writing entity URIs in OWL-R DL is as follows:
datatypeURI:= URI
owlClassURI:= URI
objectPropertyURI:= URI
dataPropertyURI:= URI
annotationPropertyURI:= URI
individualURI:= URI
Entities are written in the following way:
entity:= datatype | owlClass | objectProperty | dataProperty | annotationProperty | individual
datatype:= 'Datatype' '(' datatypeURI ')'
owlClass:= 'OWLClass' '(' owlClassURI ')'
objectProperty:= 'ObjectProperty' '(' objectPropertyURI ')'
dataProperty:= 'DataProperty' '(' dataPropertyURI ')'
annotationProperty:= 'AnnotationProperty' '(' annotationPropertyURI ')'
individual:= 'Individual' '(' individualURI ')'
OWL-R defines the same set of well-known entities as the whole OWL 1.1 language. These entities are identified by the following predefined URIs:
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 1.1 Semantics]) or a datatype restriction, specified by applying some facets to limit the value space of an pre-existing datatype.
dataRange:= datatypeURI | datatypeRestriction
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 ')'
OWL-R constructs used to build more complex properties from existing ones are identical to the ones defined in [OWL 1.1 Specification]:
objectPropertyExpression:= objectPropertyURI | inverseObjectProperty
inverseObjectProperty:= 'InverseObjectProperty' '(' objectPropertyExpression ')'
dataPropertyExpression:= dataPropertyURI
OWL-R axioms are as follows:
axiom:= classAxiom | objectPropertyAxiom | dataPropertyAxiom | fact | declaration | entityAnnotation
OWL-R redefines all axioms from the functional-style syntax OWL 1.1 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 1.1. 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, the OWL-R objectPropertyAxiom and dataPropertyAxiom 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
Besides objectPropertyDomain, objectPropertyRange, dataPropertyDomain, and dataPropertyRange, all the other non-terminals appearing in the definitions of dataPropertyAxiom and objectPropertyAxiom are identical to those defined in OWL 1.1 Specification. For reader's convenience, we provide here their definition:
subObjectPropertyExpression:= objectPropertyExpression | 'SubObjectPropertyChain' '(' objectPropertyExpression objectPropertyExpression { objectPropertyExpression } ')'
subObjectPropertyOf:= 'SubObjectPropertyOf' '(' { annotation } subObjectPropertyExpression objectPropertyExpression ')'
equivalentObjectProperties:= 'EquivalentObjectProperties' '(' { annotation } objectPropertyExpression objectPropertyExpression { objectPropertyExpression } ')'
disjointObjectProperties:= 'DisjointObjectProperties' '(' { annotation } objectPropertyExpression objectPropertyExpression { objectPropertyExpression } ')'
objectPropertyDomain:= 'ObjectPropertyDomain' '(' { annotation } objectPropertyExpression description ')'
objectPropertyRange:= 'ObjectPropertyRange' '(' { annotation } objectPropertyExpression description ')'
inverseObjectProperties:= 'InverseObjectProperties' '(' { annotation } objectPropertyExpression objectPropertyExpression ')'
functionalObjectProperty:= 'FunctionalObjectProperty' '(' { annotation } objectPropertyExpression ')'
inverseFunctionalObjectProperty:= 'InverseFunctionalObjectProperty' '(' { annotation } objectPropertyExpression ')'
reflexiveObjectProperty:= 'ReflexiveObjectProperty' '(' { annotation } objectPropertyExpression ')'
irreflexiveObjectProperty:= 'IrreflexiveObjectProperty' '(' { annotation } objectPropertyExpression ')'
symmetricObjectProperty:= 'SymmetricObjectProperty' '(' { annotation } objectPropertyExpression ')'
asymmetricObjectProperty:= 'AsymmetricObjectProperty' '(' { annotation } objectPropertyExpression ')'
transitiveObjectProperty:= 'TransitiveObjectProperty' '(' { annotation } objectPropertyExpression ')'
subDataPropertyOf:= 'SubDataPropertyOf' '(' { annotation } dataPropertyExpression dataPropertyExpression ')'
equivalentDataProperties:= 'EquivalentDataProperties' '(' { annotation } dataPropertyExpression dataPropertyExpression { dataPropertyExpression } ')'
disjointDataProperties:= 'DisjointDataProperties' '(' { annotation } dataPropertyExpression dataPropertyExpression { dataPropertyExpression } ')'
functionalDataProperty:= 'FunctionalDataProperty' '(' { annotation } dataPropertyExpression ')'
OWL-R restricts the facts to a particular type of classes:
classAssertion:= 'ClassAssertion' '(' individualURI superClass ')'
Furthermore, it disallows negative property assertions. Therefore, OWL-R fact production is as follows:
fact:= sameIndividual | differentIndividuals | classAssertion |
objectPropertyAssertion | dataPropertyAssertion
Besides classAssertion, which has previously been redefined, the other types of facts are identical to those defined in OWL 1.1 Specification. For your convenience, their definition is presented below:
sameIndividual:= 'SameIndividual' '(' { annotation } individualURI individualURI { individualURI } ')'
differentIndividuals:= 'DifferentIndividuals' '(' { annotation } individualURI individualURI { individualURI } ')'
classAssertion:= 'ClassAssertion' '(' { annotation } individualURI description ')'
sourceIndividualURI:= individualURI
targetIndividualURI:= individualURI
objectPropertyAssertion:= 'ObjectPropertyAssertion' '(' { annotation } objectPropertyExpression sourceIndividualURI targetIndividualURI ')'
negativeObjectPropertyAssertion:= 'NegativeObjectPropertyAssertion' '(' { annotation } objectPropertyExpression sourceIndividualURI targetIndividualURI ')'
targetValue:= constant
dataPropertyAssertion:= 'DataPropertyAssertion' '(' { annotation } dataPropertyExpression sourceIndividualURI targetValue ')'
negativeDataPropertyAssertion:= 'NegativeDataPropertyAssertion' '(' { annotation } dataPropertyExpression sourceIndividualURI targetValue ')'
OWL-R Full is defined by weakening the semantic conditions on an interpretation from OWL 1.1 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*].
This section defines OWL-R Full by weakening the OWL 1.1 Full semantic conditions on an interpretation.
Editor's Note: We need to add a reference of OWL 1.1 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 1.1 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 1.1 Full model-theoretic semantics defines an interpretation as follows.
From OWL 1.1 Full Semantics, for V a set of URI references and literals containing the RDF and RDFS vocabulary and D a datatype map, a D-interpretation of V is a tuple I = < RI, PI, EXTI, SI, LI, LVI >. RI is the domain of discourse or universe, i.e., a nonempty set that contains the denotations of URI references and literals in V. PI is a subset of RI consisting of the properties of I. EXTI is used to give meaning to properties, and is a mapping from PI to P(RI × RI). SI is a mapping from URI references in V to their denotations in RI. LI is a mapping from typed literals in V to their denotations in RI. LVI is a subset of RI 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 RI is CI, and the mapping CEXTI from CI to P(RI) is defined as CEXTI(c) = { x∈RI | <x,c>∈EXTI(SI(rdf:type)) }. CEXTI(c) maps a class c to its extension. D-interpretations must meet several other conditions, as detailed in the OWL 1.1 Full semantics.
Finally, the following important sets are used in the definitions of OWL 1.1 Full semantic conditions. IOOP denotes the set of OWL object properties, and IODP the set of OWL datatype properties. Both are subsets of PI. IOC, a subset of CI, 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 1.1 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 > EXTI(SI(owl:someValuesFrom)) < x,p > EXTI(SI(owl:onProperty)) | then | x IOR, y IOC IDC, p IOOP IODP, and CEXTI(x) = { u IOT | < u,v > EXTI(p) such that v CEXTI(y) } |
---|
In a simplified form, these conditions can be understood as the following two implications:
If | < x,y > EXTI(SI(owl:someValuesFrom)) < x,p > EXTI(SI(owl:onProperty)) < u,v > EXTI(p) < v,y > EXTI(SI(rdf:type)) | then | < u,x > EXTI(SI(rdf:type)). |
---|---|---|---|
If | < x,y > EXTI(SI(owl:someValuesFrom)) < x,p > EXTI(SI(owl:onProperty)) < u,x > EXTI(SI(rdf:type)) | then | v such that < u,v > EXTI(p) < v,y > EXTI(SI(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.
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.
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 |
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,?y1) T(?x,?p,?y2) | T(?y1, owl:sameAs,?y2) |
T(?p, rdf:type, owl:InverseFunctionalProperty) T(?x1,?p,?y) T(?x2,?p,?y) | T(?x1, owl:sameAs,?x2) |
T(?p, rdf:type, owl11:ReflexiveProperty) T(?x,?y,?z) | T(?x,?p,?x) T(?y,?p,?y) T(?z,?p,?z) |
T(?p, rdf:type, owl11:IrreflexiveProperty) T(?x,?p,?x) | false |
T(?p, rdf:type, owl:SymmetricProperty) T(?x,?p,?y) | T(?y,?p,?x) |
T(?p, rdf:type, owl11: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(?p1, rdfs:subPropertyOf,?p2) T(?x,?p1,?y) | T(?x,?p2,?y) |
T(?x1, rdf:first,?p1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?p2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?pn) T(?xn, rdf:rest, rdf:nil) T(?sc, owl11:propertyChain,?x1) T(?sc, rdfs:subPropertyOf,?p) T(?u1,?p1,?u2) T(?u2,?p2,?u3) ... T(?un,?pn,?un+1) | T(?u1,?p,?un+1) |
T(?p1, owl:equivalentProperties,?p2) T(?x,?p1,?y) | T(?x,?p2,?y) |
T(?p1, owl:equivalentProperties,?p2) T(?x,?p2,?y) | T(?x,?p1,?y) |
T(?p1, owl11:disjointObjectProperties,?p2) T(?x,?p1,?y) T(?x,?p2,?y) | false |
T(?p1, owl11:disjointDataProperties,?p2) T(?x,?p1,?y) T(?x,?p2,?y) | false |
T(?p1, owl:inverseOf,?p2) T(?x,?p1,?y) | T(?y,?p2,?x) |
T(?p1, owl:inverseOf,?p2) T(?x,?p2,?y) | T(?y,?p1,?x) |
T(?p1, owl11:inverseObjectPropertyExpression,?p2) T(?x,?p1,?y) | T(?y,?p2,?x) |
T(?p1, owl11:inverseObjectPropertyExpression,?p2) T(?x,?p2,?y) | T(?y,?p1,?x) |
Table 3 specifies the semantic conditions on classes.
If | then |
---|---|
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:intersectionOf,?x1) T(?y, rdf:type,?c1) T(?y, rdf:type,?c2) ... T(?y, rdf:type,?cn) | T(?y, rdf:type,?c) |
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:intersectionOf,?x1) T(?y, rdf:type,?c) | T(?y, rdf:type,?c1) T(?y, rdf:type,?c2) ... T(?y, rdf:type,?cn) |
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:unionOf,?x1) T(?y, rdf:type,?c1) | T(?y, rdf:type,?c) |
... | ... |
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:unionOf,?x1) T(?y, rdf:type,?cn) | 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) | false |
T(?x, owl:maxCardinality, "1"^^xsd:nonNegativeInteger) T(?x, owl:onProperty,?p) T(?u,?p,?y1) T(?u,?p,?y2) | T(?y1, owl:sameAs,?y2) |
Table 4 specifies the semantic conditions on class axioms.
If | then |
---|---|
T(?c1, rdfs:subClassOf,?c2) T(?x, rdf:type,?c1) | T(?x, rdf:type,?c2) |
T(?c1, owl:equivalentClass,?c2) T(?x, rdf:type,?c1) | T(?x, rdf:type,?c2) |
T(?c1, owl:equivalentClass,?c2) T(?x, rdf:type,?c2) | T(?x, rdf:type,?c1) |
T(?c1, owl:disjointClasses,?c2) T(?x, rdf:type,?c1) T(?x, rdf:type,?c2) | 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(?c1, rdfs:subClassOf,?c2) T(?c2, rdfs:subClassOf,?c3) | T(?c1, rdfs:subClassOf,?c3) |
T(?c1, owl:equivalentClass,?c2) | T(?c1, rdfs:subClassOf,?c2) T(?c2, rdfs:subClassOf,?c1) |
T(?p, rdf:type, owl:ObjectProperty) | T(?p, rdfs:subPropertyOf,?p) T(?p, owl:equivalentProperties,?p) |
T(?p, rdf:type, owl:DatatypeProperty) | T(?p, rdfs:subPropertyOf,?p) T(?p, owl:equivalentProperties,?p) |
T(?p1, rdfs:subPropertyOf,?p2) T(?p2, rdfs:subPropertyOf,?p3) | T(?p1, rdfs:subPropertyOf,?p3) |
T(?p1, owl:equivalentProperties,?p2) | T(?p1, rdfs:subPropertyOf,?p2) T(?p2, rdfs:subPropertyOf,?p1) |
T(?p, rdfs:domain,?c1) T(?c1, rdfs:subClassOf,?c2) | T(?p, rdfs:domain,?c2) |
T(?p2, rdfs:domain,?c) T(?p1, rdfs:subPropertyOf,?p2) | T(?p1, rdfs:domain,?c) |
T(?p, rdfs:range,?c1) T(?c1, rdfs:subClassOf,?c2) | T(?p, rdfs:range,?c2) |
T(?p2, rdfs:range,?c) T(?p1, rdfs:subPropertyOf,?p2) | T(?p1, rdfs:range,?c) |
T(?c1, owl:hasValue,?i) T(?c1, owl:onProperty,?p1) T(?c2, owl:hasValue,?i) T(?c2, owl:onProperty,?p2) T(?p1, rdfs:subPropertyOf,?p2) | T(?c1, rdfs:subClassOf,?c2) |
T(?c1, owl:someValuesFrom,?y1) T(?c1, owl:onProperty,?p) T(?c2, owl:someValuesFrom,?y2) T(?c2, owl:onProperty,?p) T(?y1, rdfs:subClassOf,?y2) | T(?c1, rdfs:subClassOf,?c2) |
T(?c1, owl:someValuesFrom,?y) T(?c1, owl:onProperty,?p1) T(?c2, owl:someValuesFrom,?y) T(?c2, owl:onProperty,?p2) T(?p1, rdfs:subPropertyOf,?p2) | T(?c1, rdfs:subClassOf,?c2) |
T(?c1, owl:allValuesFrom,?y1) T(?c1, owl:onProperty,?p) T(?c2, owl:allValuesFrom,?y2) T(?c2, owl:onProperty,?p) T(?y1, rdfs:subClassOf,?y2) | T(?c1, rdfs:subClassOf,?c2) |
T(?c1, owl:allValuesFrom,?y) T(?c1, owl:onProperty,?p1) T(?c2, owl:allValuesFrom,?y) T(?c2, owl:onProperty,?p2) T(?p1, rdfs:subPropertyOf,?p2) | T(?c2, rdfs:subClassOf,?c1) |
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:intersectionOf,?x1) | T(?c, rdfs:subClassOf,?c1) T(?c, rdfs:subClassOf,?c2) ... T(?c, rdfs:subClassOf,?cn) |
T(?x1, rdf:first,?c1) T(?x1, rdf:rest,?x2) T(?x2, rdf:first,?c2) T(?x2, rdf:rest,?x3) ... T(?xn, rdf:first,?cn) T(?xn, rdf:rest, rdf:nil) T(?c, owl:unionOf,?x1) | T(?c1, rdfs:subClassOf,?c) T(?c2, rdfs:subClassOf,?c) ... T(?cn, rdfs:subClassOf,?c) |
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:
Furthermore, let RDF(O) and RDF(F) be the translations of O and F into RDF graphs as specified in the RDF mapping [ OWL 1.1 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 1.1 DL semantics if and only if RDF(F) is a consequence of RDF(O) AXIOMS under the standard first-order semantics.
This section describes the computational complexity of important reasoning problems in the described fragments.
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 1.1 DL and OWL 1.1 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 fragments 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:
When evaluating the complexity, the following parameters will be considered:
Table 6 summarizes the known complexity results for OWL 1.1 DL, OWL 1.0 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.
Language | Reasoning Problems | Taxonomic Complexity | Data Complexity | Query Complexity | Combined Complexity |
---|---|---|---|---|---|
OWL 1.1 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.0 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.