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 

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.


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 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:38:26 UTC