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

Encoding of OWL in a rule system (such as Datalog)

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Mon, 20 Oct 2003 11:22:24 +0200
Cc: Adrian Walker <adrianw@snet.net>, Andrei Voronkov <voronkov@cs.man.ac.uk>, "Raphael Volz" <rvo@aifb.uni-karlsruhe.de>, "Boris Motik" <motik@fzi.de>
To: <www-rdf-logic@w3.org>, <www-rdf-interest@w3.org>
Message-Id: <EA98F0C3-02DE-11D8-9D22-000A9575BDDE@inf.unibz.it>

On Tuesday, Oct 7, 2003, at 16:26 Europe/Rome, Adrian Walker wrote:
> Andrei Voronkov kindly sent me a pointer to the excellent paper 
> "Complexity and the Expressive Power of Logic Programming", that he 
> wrote with Dantsin, Eiter and Gottlob. In the paper, they point out 
> that "complexity" can be "data complexity" or "program complexity".   
> The two are very different. Data complexity  is the complexity of 
> checking whether Din U P |= A for a fixed datalog program P and 
> variable input databases Din and ground atoms A.  It is "polynomial". 
> Program complexity is the complexity of checking whether Din U P |= A 
> for variable datalog programs P and ground atoms A over a fixed input 
> database Din.  It is complete in DEXPTIME.

Of course I know very well those results and that paper.

The proof of the statement that query answering with OWL-lite (or any 
richer ontology language) can not be polynomially encoded in a rule 
system such as Datalog derives from the fact that the problem of 
instance checking in OWL-lite is coNP-hard in DATA complexity. Full 
stop.

On Tuesday, Oct 7, 2003, at 14:50 Europe/Rome, Raphael Volz wrote:
> We a working on a reduction of SHIQ to Disj. Datalog with equality, 
> (w/o closed world negation!) which will for some knowledge base 
> generate a set of rules (whose number is worst-case exponential in the 
> size of the knowledge base), which preserves satisfiabilty and 
> entailment.

If there is an EXPONENTIAL blow up in the number of the target rules 
with respect to the number of the axioms in the original knowledge base 
everything is possible.

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, 20 October 2003 05:23:23 GMT

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