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

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