W3C home > Mailing lists > Public > public-owl-wg@w3.org > December 2007

Re: ISSUE-75 (Non tractable fragments): REPORTED: Tractable fragments that are not tractable

From: Ian Horrocks <ian.horrocks@comlab.ox.ac.uk>
Date: Sun, 2 Dec 2007 15:17:22 +0000
Message-Id: <772C45FA-F246-4252-8370-EB186152A9CB@comlab.ox.ac.uk>
Cc: OWL Working Group WG <public-owl-wg@w3.org>
To: Jim Hendler <hendler@cs.rpi.edu>
I don't know how to change the URL either, but I updated the link  
from the Work In Progress page to read "Fragment Proposal(s)".  
Hopefully this will be a little less confusing.


On 28 Nov 2007, at 17:34, Jim Hendler wrote:

> I think the whole issue of what the fragments document should  
> report on will eventually need discussing (I mentioned that in my  
> intro message, so I'm being consistent) - I definitely think some  
> non-tractibility must be considered in that document - not just the  
> ones mentioned below, but also what the OWL Full equivalents of  
> some of these fragments are (i.e. same vocabulary restrictions, but  
> not DL restrictions) and how to discuss these - I also remind folks  
> that I started a page in the wiki for discussion of this at http:// 
> www.w3.org/2007/OWL/wiki/Fragments which is not to be confused with  
> the fragments draft (maybe I should have used a different name for  
> the wiki page - I don't know how to change it - but something like  
> "fragment suggestions" or such might make it easier for people to  
> find)
>  -JH
> On Nov 28, 2007, at 12:15 PM, OWL Working Group Issue Tracker wrote:
>> ISSUE-75 (Non tractable fragments): REPORTED: Tractable fragments  
>> that are not tractable
>> http://www.w3.org/2007/OWL/tracker/issues/
>> Raised by: Bijan Parsia
>> On product:
>> (On behalf of Carsten Lutz.)
>> We have a document called "tractable" fragments, but in fact several
>> fragments listed are not tractable or unknown to be tractable. In
>> particular, these are DLP and Horn-SHIQ. I think that
>> - these fragments (well, at least Horn-SHIQ) are interesting (because
>>   Hornness is very likely to make practical reasoning more feasible),
>>   and should be in the document;
>> - the current motivation via tractability of data complexity misses
>>   the point and is very likely to mislead the reader (it is based
>>   on the assumption that the ontology is very small -- length 20
>>   symbols or so -- which does not seem very realistic for most OWL
>>   use cases; moreover, (in contrast to Hornness) it has never been
>>   shown that polytime data complexity can be really be exploited for
>>   efficient reasoning
>> - the distinction taxonomic complexity/data complexity/query  
>> complexity/
>>   combined complexity are much too technical for our purposes and  
>> should
>>   not be in the document.
>> My proposal is to call the document simply "Fragments of OWL". Since
>> the fragments that we list in the document are of a very different
>> nature, we should then make an effort to explain for each fragment
>> separately why it is interesting and what it is good for. The huge
>> complexity table should go away. Instead, we should simply point out
>> whenever a fragment is tractable (in the standard sense, *not* data
>> complexity) and when it is not. There are still sufficiently many
>> good things left that can be said about Horn-SHIQ.
> "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 Sunday, 2 December 2007 15:17:42 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 16:41:41 UTC