Fwd: RE: OWL Comment: have long CR period for OWL, or move owl:oneOf, owl: have Value to OWL Full

From: Jim Hendler <hendler@cs.umd.edu>
Date: Wed, 25 Jun 2003 16:56:39 -0400
Message-Id: <p05200f0ebb1fb490a096@[10.0.0.229]>

```This message takes up a response to a thread started on
for the start...

(and I see there is already discussion on this - sorry about lack of
sequentiality)

Martin - I think a lot of the problem is confusion about what
"complete" means -- in fact, in my opinion the reason some people
were willing to  remove the clause about a complete OWL DL
Consistency Checker was they didn't want to have to add a whole lot
of explanation about what it really means.

Let's start with this - there is virtually no such thing as an
implemented program that is provably complete and sound for any
interesting langauge (Including OWL Lite, by the way).  What is
complete is the ALGORITHM (or, more technically for a logic, the
decision procedure that an algorithm uses).  This is because there
are resource constraints on any algorithm that means it will
eventually fail -- because the problem being encoded can grow beyond
the resource bounds of the system.  The real issue, which is the one
you are asking about below for OWL DL, is how much of a resource hog
is it -- that is, will it take arbitrarily long or arbitrarily much
memory for relatively simple problems.

The first thing to note is that virtually anything that can do
interesting reasoning is likely to be NP-hard (or else P = NP, but we
won't go there) -- so we're talking exponential -- add more to the
problem and the time/space goes up as k^^n -- n being the size of the
problem, k being some constant (usually 2, but not necessarily so).
That's worst case complexity - some recent results have shown that
for some algorithms the average case is very different - and that has
usually used logic algorithms (based on 3-SAT problems) as an example
- their distributions are not "normal"

without getting into a logic discourse, this means the following --
the difference between Lite and DL is not as much as you might think
-- Lite is ExpTime, DL is NexpTime -- i.e. if Lite is 2^^n, DL is
n2^^n -- so the extra n, even in worst case, isn't necessarily that
bad -- for small to medium problems it is likely not to be a big deal
-- in practice, for example, we're finding very little difference in
tests my group is running on Owl Lite v. DL - except in some corner
cases.

So it really gets down to what time is practical, how hard are these
things to optimize, etc.  What I do know is that since OWL has become
"real" several companies have started engineering things that till
hoc stores, new optimizations have been developed, and new techniques
pioneered, and these are performing orders of magnitude better than
earlier problems -- there's now an incentive to engineer this stuff.

So, from HP's point of view, I think there is a business decision to
be made, but I'd suggest not writing off DL -- if you are building a
practical system, sound and complete "When it terminates" can be an
awfully nice thing -- that is, you can run problems through OWL DL
with some time or memory limit (based on use) and it will sometimes
say "cannot be determined w/in limits, should I continue" -- However,
if it does return an answer, it is guaranteed to be correct (that's
the real sound/complete guarantee in practice)

So, bottom line, we have reason to believe that the size of the
problems it can handle NOW, plus the things being engineered, will
hold us for a while to come.

Thus, IMHO, I think DL will prove itself for a certain class of
reasoning tasks for which there is nothing else.  However both Lite
and Full have other markets, so I think we'll just have to see

-Jim H.
p.s. Above is my own opinion, and does not necessarily reflect that
of the Web Ont WG or any of its members.

>From: "Merry, Martin" <Martin_Merry@hplb.hpl.hp.com>
>Subject: RE: OWL Comment: have long CR period for OWL, or move owl:oneOf,
>	owl:	have Value to OWL Full
>Date: Wed, 25 Jun 2003 11:16:17 +0100
>X-MailScanner: Found to be clean
>X-MailScanner-SpamCheck: not spam (whitelisted), SpamAssassin (score=-1.6,
>	required 5, BAYES_10 -4.70, QUOTED_EMAIL_TEXT -0.38,
>	SUBJ_HAS_SPACES 3.53)
>X-Spam-Status: No, hits=-7.5 required=5.0
>	tests=BAYES_01,QUOTED_EMAIL_TEXT,SUBJ_HAS_SPACES
>	version=2.53
>X-Spam-Level:
>X-Spam-Checker-Version: SpamAssassin 2.53 (1.174.2.15-2003-03-30-exp)
>
>Hi Jim
>
>Thank you for your response [1].  From the point of view of the formal
>process I accept your response and don't want to pursue this point any
>further.
>
>However, I would just like to check my understanding of the situation.
>
>You say:
>
>>  First, we have dropped the discussion of a "Complete OWL DL
>>  Consistency Checker" from the Test document.  We believe this is
>>
>
>My interpretation of this is that you do not expect a complete consistency
>checker for OWL DL to exist; in particular, you do not require such a
>complete implementation in order to advance the proposal.
>
>
>>    The WG has been made aware of implementations of OWL DL
>>  that include
>>  both inverseOf and oneOf and which seem to be performing well in
>>  practice.  The working group will definitely consider their status
>>  and usability before deciding on our schedule with respect to
>>  Candidate Recommendation and Proposed Recommendation.
>
>The HP representative on the working group (Jeremy) isn't aware of such
>complete i.e. there are other OWL DL features which aren't supported in
>these implementations.
>
>If it is the case that there are complete implementations of OWL DL that
>have acceptable performance and are available on terms compatible with the
>W3C patent policy then I would be very pleased to hear it, and you can
>assume that the intended status of OWL DL is
>
>* it is decidable
>* there are implementations of a number of different proper subsets.
>
>
>
>>From a purely HP-centric point of view (concerned with developing practical
>tools and applications of and for the semantic web) this isn't particularly
>interesting to us.
>
>OWL Full is interesting: we would expect a number of implementations to
>support proper subsets of OWL Full and agree on the correctness of any
>reachable entailments. We expect to be able to share OWL Full documents
>amongst different users and for them to have common understanding of the
>semantics of these documents. We would expect special-purpose reasoners to
>be able to provide proofs for ontologies developed in particular (proper)
>subsets of OWL full - we would eventually hope to be able to share these
>proofs amongst different users.
>
>OWL Lite is interesting: we would expect a number of implementations of
>reasoners for OWL Lite. We would expect to be able to share OWL lite
>documents amongst different users and for them to reach the same conclusions
>about the consequences of these documents.
>
>But OWL DL is "merely" a subset of OWL Full for which one would not expect
>to get full reasoning support, comparable in usability terms to any other
>fragment of OWL Full.  It does have the property that any ontology written
>in a proper subset of OWL DL has a fighting chance of having reasoning
>support, and so could therefore be described, roughly speaking, as the
>minimal unimplementable subset of OWL Full.
>
>I would therefore expect us (again, this is an HP-centric comment) to
>concentrate on OWL FUll and OWL lite, and largely ignore OWL DL.
>
>I'd welcome any (informal) comments on this
>
>Martin Merry
>
>
>[1]