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

That is exactly what we have been saying.

Raphael

> -----Ursprungliche Nachricht-----
> Von: www-rdf-logic-request@w3.org 
> [mailto:www-rdf-logic-request@w3.org] Im Auftrag von Enrico Franconi
> Gesendet: Montag, 20. Oktober 2003 04:22
> An: www-rdf-logic@w3.org; www-rdf-interest@w3.org
> Cc: Adrian Walker; Andrei Voronkov; Raphael Volz; Boris Motik
> Betreff: 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
>

Received on Monday, 20 October 2003 18:11:51 UTC