Re: language subsets and complexity [was: Minutes of June 12 Telecon]

On Tue, 2003-06-17 at 09:55, Ian Horrocks wrote:
> > 
> > ---> OWL comment - language subsets and complexity (Fri, May 09 2003)
> >       [no reply received] - issue discussed, but not yet assigned
> > ??? to respond
> 
> I think that this was me. Here is a proposed response.

Well put; please send it.

> Ian
> 
> -------------------------
> 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))
> > 
-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/

Received on Tuesday, 17 June 2003 19:13:22 UTC