W3C home > Mailing lists > Public > public-owl-wg@w3.org > February 2008

Re: completeness

From: Jim Hendler <hendler@cs.rpi.edu>
Date: Thu, 21 Feb 2008 15:04:49 -0500
Cc: Alan Ruttenberg <alanruttenberg@gmail.com>, Ulrike Sattler <sattler@cs.man.ac.uk>, public-owl-wg@w3.org
Message-Id: <4C9E6AC8-AB0E-4ECD-89D3-FBF29831E841@cs.rpi.edu>
To: Bijan Parsia <bparsia@cs.man.ac.uk>

Hmm, I hoped the answer was responsive - let me try responding another  
way - how would you compare two Java implementations?  There is no  
formal model, and there is no way that you can prove them formally  
compatible (actually that's not true, if Turing, Church and Godel were  
wrong, then you maybe could) -- anyway, we compare these by examples,  
tests, descriptions, etc.  We test interoperability by providing  
programs that have to be run through both and get same answers -- in  
fact, just the way OWL 1.0 defined what it meant to be a conforming  
OWL DL implementation (to show interop, we did not analyze the  
internals of  implemenations, we ran them against a test set).
  I'm not against formal properties when they exist, but not  
everything can be expressed in the same way, and not everything can be  
formalized against the same model.  We used one particular way to  
formalize OWL DL, which is fine, but it doesn't mean every  
Recommendation needs a model theory -- in fact, very few of them have  
it (I bet you the majority of W3C specs don't have formal models, even  
if a few you cite below do) - because it's appropriate in some cases,  
not in others.
  So I would argue we must define carefully, and that we need  
interoperability.  But if you insist completeness is the only thing we  
can evaluate against, then we can never have a spec you will consider  
interoperable for any undecidable (w/respect to various properties)  
fragment.  But then we could also never have interoperable programming  
languages, or interoperable collaborative  data systems, or  
interoperable web servers (unless someone has developed an HTTP  
semantics that I missed)
  As we've said often on this WG, there are people coming at OWL from  
disparate approaches, and we all must live in one WG, so we cannot  
assume everyone's favorite way of doing things will be the only way  
something can be done.  Formal models are fine where they work, but  
they don't work for many things, and I believe RDFS 3.0/OWL Prime   
could be one of these...
  Is that more responsive?  If not, you will have to tell me how to  
address a completeness argument for things like programming languages  
(or web apps) and I will try my best to develop one for this.
  -JH



On Feb 21, 2008, at 12:29 PM, Bijan Parsia wrote:

>
> I think this isn't a responsive answer, but perhaps the question  
> isn't clearly enough stated.
>
> One important point of having a standard is to support as much  
> interoperability as possible, reasonable, and helpful. It's  
> particularly important that the standard be clear on what's required  
> so that if a system deviates, customers and competitors have a  
> reasonably objective basis for discussion. I refer everyone to the  
> excellent and amusing essay "Why specs matter?" by Mark Pilgrim:
> 	http://diveintomark.org/archives/2004/08/16/specs
>
> This is why grammars are generally preferred to a pile of prose and  
> why, at the W3C, formal methods have gotten a lot of purchase (e.g.,  
> there are formal semantics for XQuery and XPath, for example).  
> (HTML5 is an interesting non-formal method based spec, but there the  
> spec is given in terms of canonical algorithms exhaustively reversed  
> engineered from existing browser behavior. Also, each particular  
> algorithm admits of relatively few necessary degrees of freedom,  
> unlike, say, for a query language.) Yes there will be bugs  
> throughout any system at all levels, but no one claims or believes  
> otherwise: No formality or exhaustiveness of the spec will change  
> this fact. But just considering the experience of RDF model & syntax  
> should make us all very interested in getting as precise a spec as  
> we possibly can.
>
> In this case, there have been claims of trading completeness for  
> scalability. Let's grant that this is what has been done for the  
> sake of argument. After all, with a bit of work, one can make e.g.,  
> a DL Lite implementation incomplete (but scalable) for OWL DL (you  
> have to explain how you ignore the non-DL Lite bits, of course). But  
> in this case, the incompleteness is very clearly specified and  
> specified in a neutral manner with regard to implementation. (Which  
> is another important point: The W3C, at least some of the time,  
> tries to be fair between big vendors and small vendors and everyone  
> else, although you can read complaints about it being in the thrall  
> of the big vendors. Requiring people to reverse engineer *anyone's*  
> in order to be compatible defeats the point of specification.)
>
> Finally, it's easy to be (formally) incomplete and *not* scalable or  
> not robustly scalable or not easily robustly scalable. After all,  
> this is basically what happened with OWL Lite. For OWL Lite, to  
> program reasonably interoperable systems *independently* pretty much  
> requires implementing SHIF which is not easy to make scalable. Of  
> course, I could through out parts of SHIF and you could through out  
> parts of SHIF but unless we through out the *same bits* we won't be  
> reasonable interoperable and users will have difficulty assessing  
> the systems.
>
> Note, I'm not saying that having formal properties shown provides  
> total certainty. But I think it's reasonable for the working group  
> to ask for more than mere assertion. And people *do* spend a lot of  
> time and money on interop (e.g., WS-I, RDF Core, HTML5 etc. etc.).
>
> OWL processors are *components* of other systems, including web  
> apps. So it's a bit apples and oranges too point out that people  
> don't make completeness or correctness demands on web apps. They do  
> on databases. (And XSLT processors...imagine if saxon gave a  
> *different* result than libxslt!) While we can't get perfection, we  
> should strive to do well.
>
> Cheers,
> Bijan.
>
>
>

"If we knew what we were doing, it wouldn't be called research, would  
it?." - Albert Einstein

Prof James Hendler				http://www.cs.rpi.edu/~hendler
Tetherless World Constellation Chair
Computer Science Dept
Rensselaer Polytechnic Institute, Troy NY 12180
Received on Thursday, 21 February 2008 20:05:18 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 21 February 2008 20:05:20 GMT