Re: Issue: Add hasValue to OWL Lite

On December 11, Jim Hendler writes:
> 
> Ian -The  IJCAI paper about SHOQ(D) which might somehow connote what 
> you are asserting, but I am afraid I don't see the connection.  The 
> argument you make in
> [1]  is the argument that the worst case computational complexity of 
> reasoning goes up from absurd (EXPtime) to ridiculous (NEXPtime) with 
> the addition of oneOf (or hasValue).  However, exptime already means 
> you are limitied to relatively small domains or to incompleteness, 
> and thus I don't find Nexptime compellingly bad.

So what is your point - that you don't understand the argument about
computational complexity, that you dispute the argument or that you
just don't care about the argument?

As far as the argument itself is concerned:

1. As I mentioned in the email, the IJCAI paper is just the starting
point and you should explore the bibliography it contains in order to
get a better understanding of research in this area.

2. It is easy to show (e.g., see [1]) that that DAML+OIL/OWL without
nominals is logically equivalent to SHIQ(D) and that adding nominals
gives SHOIQ(D). The literature I pointed to proves the satisfiability
problem for these logics to be in ExpTime and NExpTime respectively.

3. For ExpTime logics, it is possible to devise relatively simple
algorithms that are goal directed and know when they are done. It has
also been demonstrated that these algorithms can be optimised so as to
give good performance in realistic applications.

4. For NExpTime logics, no such algorithm is known. This is
illustrative of just how significant the jump from ExpTime to NExpTime
is from both a theoretical and a practical perspective.


> In short, you are arguing that adding hasValue makes the worst case 
> computational complexity of OWL Lite to be the same as that of OWL 
> DL.  OK, I'm willing to admit that.  However, the working group never 
> agreed that we were limiting Owl lite based on worst case complexity 
> -- in fact, you yourself argued that the only argument in favor of 
> Lite is ease of implementation -- okay, I throw that back to you -- 
> Jos and I have argued this is not hard to implement.  In my case, it 
> is naturally implemented by databases, which are often optimized for 
> these sorts of tasks.

As I mentioned in my earlier email, this depends on your definition of
"implement", and on just what it is you want to implement. To me, a
prerequisite for implementation is having an algorithm.

Also, as far as OWL Lite -v- OWL DL is concerned, if what you are
saying about "implementation" is true, then OWL DL is equally easy to
implement and there is no requirement whatsoever for OWL Lite. If it
makes you feel better, you could "re-badge" OWL DL as OWL Lite.

Ian

[1] http://www.cs.man.ac.uk/~horrocks/Publications/download/2002/AAAI02IHorrocks.pdf

Received on Thursday, 12 December 2002 04:22:50 UTC