Re: OWL comment - language subsets and complexity

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