W3C home > Mailing lists > Public > public-owl-wg@w3.org > January 2009

Re: Requirements document?

From: Carsten Lutz <clu@informatik.uni-bremen.de>
Date: Tue, 20 Jan 2009 19:34:05 +0100
To: Bijan Parsia <bparsia@cs.man.ac.uk>
Cc: OWL 2 <public-owl-wg@w3.org>
Message-id: <4976191D.4070809@informatik.uni-bremen.de>

Bijan Parsia wrote:
> Some errors:
> """  OWL 2 EL is the maximal language for which reasoning, including 
> query answering, is known to be worst-case polynomial. It is related to 
> the theory of [EL++] [EL++ Update].
> OWL 2 QL is the maximal language for which reasoning, including query 
> answering, is known to be worst case logspace (same as DB). """
> Anything which says "THE maximal" followed by such general terms is 
> almost always wrong. It's extra wrong for OWL QL because, with the 
> removal of, e.g., sameAs it's not even maximal.

Indeed, these sentences are confusing. Some reasons:

- I agree that "the" should be "a"

- the complexity statements are *very* misleading: query answering in
   EL is polynomial only regarding *data complexity*, but not regarding
   combined complexity (NP complete). So the statement confuses by
   just saying "polynomial", which to me sounds like it refers to the
   more standard measure combined complexity. Moreover, other reasoning
   tasks do not have the distinction between data complexity and combined
   complexity (e.g., no data involved in subsumption, which is polynomial
   in OWL 2 EL regarding the only complexity measure that is considered
   in that case), and this mixture makes the statement all the more

- For OWL 2 QL, LogSpace also refers to *data* complexity and this is
   mixed in with standard reasoning. Moreover, the statement suggests
   that "reasoning" (say subsumption) is in LogSpace regarding the only
   complexity measure considered in that case. Is this a correct state-


*  Carsten Lutz, FB Mathematik und Informatik, Universitaet Bremen   *
* Office phone:++49 421 21864431 mailto:clu@informatik.uni-bremen.de *
Received on Tuesday, 20 January 2009 18:34:46 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:42:08 UTC