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

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