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

This message takes up a response to a thread started on 
public-webont-comments@w3.org -- see 
http://lists.w3.org/Archives/Public/public-webont-comments/2003May/0046.html
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 
now had been mostly research programs -- databases have replaced ad 
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>
>To: "'Jim Hendler'" <hendler@cs.umd.edu>, public-webont-comments@w3.org
>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
>>  consistent with your request
>>
>
>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.
>
>You add:
>
>>    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
>implementations; I've asked him to find out more information. However, in
>view of your earlier comments I assume that these implementations aren't
>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
>safely ignore any of these comments.  However, given your comments earlier I
>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]
>http://lists.w3.org/Archives/Public/public-webont-comments/2003Jun/0023.html
>>
>
-- 
Professor James Hendler				  hendler@cs.umd.edu
Director, Semantic Web and Agent Technologies	  301-405-2696
Maryland Information and Network Dynamics Lab.	  301-405-6707 (Fax)
Univ of Maryland, College Park, MD 20742	  *** 240-277-3388 (Cell)
http://www.cs.umd.edu/users/hendler      *** NOTE CHANGED CELL NUMBER ***