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

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.

Received on Wednesday, 28 November 2007 17:15:32 UTC