W3C home > Mailing lists > Public > www-rdf-logic@w3.org > October 2003

Re: AW: Safe Execution of Recursive Axioms + English

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Tue, 7 Oct 2003 00:25:57 +0200
Cc: "Raphael Volz" <volz@aifb.uni-karlsruhe.de>
To: www-rdf-logic@w3.org
Message-Id: <0E4CF678-F84C-11D7-9E96-000A9575BDDE@inf.unibz.it>

On Thursday, Oct 2, 2003, Raphael Volz wrote:
> indeed Ian Horrocks, Benjamin Grosof, Stefan Decker and me
> have shown (in the Description Logic Program paper at WWW)
> that you can NOT implement SHIF (the DL below
> OWL Lite) via Datalog, but a (more or less - depending on your
> own perspective) fragment thereof.

Well, this can be proved by simple complexity arguments (poly vs  
EXPTIME-hard).

> One example is existential quantification, which you can
> only do in one directions of implication, since existentials
> in the head are generally unavailable in Datalog. Another
> example is negation, which has different semantics (incompatible
> with FOL negation).

Your work contains an obvious and trivial polynomial fragment of OWL,  
known since long time, whose impact in the real ontology world has to  
be empirically shown yet. Its impossibility to freely intermix  
universal and existential quantifiers makes it, to my opinion, quite  
useless.

> I believe that you - generally - can NOT implement OWL Lite
> with rule-based reasoners.

It is not only a belief, you can formally prove it! No sub-boolean DL  
(e.g., FL-) with full axioms, and no DL with full booleans (e.g. ALC)  
without axioms can be ever encoded in a polynomial language (e.g., a  
rule-based reasoner), as a matter of fact.

> What you seems to be possible
> is using Disjunctive Logic Programs, but our proof that an
> appropriate translation is indeed correct is not quite finished
> yet. Empirically, we pass all tests in the OWL Test Suite and
> other well-known DL tests.

Still, DLP in its full power is below PSPACE, so again no reasonable DL  
(with a complexity coming either from full axioms or from the booleans)  
can be ever be encoded in it. This is the case of OWL-lite which is  
EXPTIME-hard. So, again, I don't understand what are you really doing.

Passing the test in the OWL Test Suite does not seem to me anything  
like a soundness and completeness proof for any algorithm. I wonder  
which other tests did your system pass. Did you consider the standard  
DL test suite (e.g. see http://www.dis.uniroma1.it/~tancs/ or  
http://kogs-www.informatik.uni-hamburg.de/~moeller/dl-benchmark- 
suite.html)?

cheers
--e.

Enrico Franconi                  - franconi@inf.unibz.it
Free University of Bozen-Bolzano - http://www.inf.unibz.it/~franconi/
Faculty of Computer Science      - Phone: (+39) 0471-315-642
I-39100 Bozen-Bolzano BZ, Italy  - Fax:   (+39) 0471-315-649
Received on Monday, 6 October 2003 18:26:14 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:47 GMT