Re: OWL comment - language subsets and complexity

Ian,

Thank you for your response.

It is a shame that it is not possible to close these "loopholes", and reduce the
complexity levels for the two subsets, without unacceptable restrictions.
However, I accept that the proposed tradeoff is the best that the working group
can achieve and accept your response as satisfactory.

Dave Reynolds

Ian Horrocks wrote:
> 
> Thank you for your comments.
> 
> As you point out, the issue of OWL DL implementability is dealt with
> in a separate comment, so here I will restrict my attention to your
> comment regarding the complexity of reasoning in OWL Lite.
> 
> On May 9, Dave Reynolds writes:
> >
> > 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.
> 
> The design of OWL Lite is intended to maximise utility while providing
> easier implementability (not just of reasoners, but also of tools such
> as editors). As you point out, it is possible through "abuse" of the
> syntax to express, e.g., negation, even though it is not directly
> supported in the syntax.
> 
> The working group did consider trying to close such "loopholes" via
> the mechanisms you suggest (amongst others), but concluded that this
> would be difficult to achieve without an unacceptable reduction in the
> power/utility of the language. E.g., see the thread beginning with [1]
> for a discussion on how the complexity of reasoning in Lite might be
> reduced and [2] for an argument as to why eliminating complete
> definitions from Lite would be unacceptable.
> 
> As far as your suggestion to have "each classId may only participate
> in a single axiom of the form Class(classID complete ...)" is
> concerned, this would not work as we can easily assert (or even infer)
> the equivalence of classes, allowing different classIds to be used to
> be used in different axioms in order to achieve the same result.
> 
> Please reply to this message as to whether this response is satisfactory,
> copying public-webont-wg@w3.org. Again, thank you for your comments.
> 
> Ian Horrocks
> 
> [1] http://lists.w3.org/Archives/Public/www-webont-wg/2002Dec/0054.html
> 
> [2] http://lists.w3.org/Archives/Public/www-webont-wg/2002Dec/0088.html
> 
> >
> > 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, 20 June 2003 12:10:51 UTC