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

On June 17, Dan Connolly writes:
> 
> 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.

Done.

Ian


> 
> > 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 Wednesday, 18 June 2003 12:07:43 UTC