ISSUE-75

Non tractable fragments

ACCEPTED: Tractable fragments that are not tractable

State:

CLOSED

Product:

Raised by:

Bijan Parsia

Opened on:

2007-11-28

Description:

(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.

Related Actions Items:

No related actions

Related emails:

1. Proposal to close ISSUE-75: OWL-Lite as EL++ (from alanruttenberg@gmail.com on 2008-03-16)
2. Proposal to close Issue-75 (from alanruttenberg@gmail.com on 2008-03-16)
3. Re: ISSUE-75 (Non tractable fragments): REPORTED: Tractable fragments that are not tractable (from ian.horrocks@comlab.ox.ac.uk on 2007-12-02)
4. Re: ISSUE-75 (Non tractable fragments): REPORTED: Tractable fragments that are not tractable (from hendler@cs.rpi.edu on 2007-11-28)
5. ISSUE-75 (Non tractable fragments): REPORTED: Tractable fragments that are not tractable (from sysbot+tracker@w3.org on 2007-11-28)

Related notes:

Display change log