W3C home > Mailing lists > Public > public-webont-comments@w3.org > May 2003

OWL comment - language subsets and complexity

From: Dave Reynolds <der@hplb.hpl.hp.com>
Date: Fri, 09 May 2003 14:40:17 +0100
Message-ID: <3EBBAFC1.3C42AF05@hplb.hpl.hp.com>
To: public-webont-comments@w3.org

We wish to register a comment on the implementation complexity of the selected
subsets of OWL - Lite and DL - based on our implementation experience with Jena.

We understand that there is a tradeoff between complexity of reasoner
implementations and expresivity of the language for ontology authors. There are
applications of OWL that just involve the exchange of ontology documents and do
not require complete reasoning support. For this reason we do not object to
OWL-full being undecidable. 

However, we understand the purpose of the defined subsets (Lite, DL) as being to
provide interoperability points between implementations that *are* offering
reasoning support.

It has already been pointed out by working group members that OWL/DL reasoning
is NExpTime and that practical, tractable implementations of the complete subset
remains a research problem. It seems inappropriate to us to call out a language
subset which is not yet effectively implementable - we cover this point, and its
implications for CR stage, in more detail in a separate comment.

Turning to OWL/Lite, the inclusion of intersectionOf together with the ability
to define multiple complete definitions of a named class means that the language
is not very "light". In particular, it appears to be possible to define
equivalents to complementOf[1] and thus unionOf within OWL/Lite. Their exclusion
would have been useful in order to facilitate low complexity rule-based
implementations but does not seem to have been achieved.

One means to simplify OWL/Lite would be to restrict class definitions to only be
"partial". Our concern is that this would go too far - there is value in having
complete definitions in order to support classification of individuals based on
their properties. We wonder if a constraint of the form "each classId may only
participate in a single axiom of the form Class(classID complete ...)" would
remove this source of complexity. We ask those with greater knowledge of this
field to explore whether an approach along these lines would enable OWL/Lite to
better live up to its name.

Dave Reynolds for the Jena team

[1] An example construct, which Jeremy credits to Ian Horrocks, is as follows.

Given a definition of a class C:
   Class(C complete <expr1>)

The let P be a property which is not used elsewhere and define:
   Class(C complete restriction(minCardinality(P, 1))
   Class(C-co complete restriction(maxCardinality(P, 0))
Received on Friday, 9 May 2003 09:41:45 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:43:28 GMT