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

Re: AW: Datalog DEXPTIME Complexity + Safe Execution of Recursive Axioms + English

From: Adrian Walker <adrianw@snet.net>
Date: Tue, 07 Oct 2003 10:26:21 -0400
Message-Id: <>
To: "Enrico Franconi" <franconi@inf.unibz.it>
Cc: <www-rdf-logic@w3.org>, <www-rdf-interest@w3.org>, voronkov@cs.man.ac.uk

Enrico --

It's possible that an important point is overlooked when many of us say 
things like "datalog can only compute things of polynomial complexity"

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 

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.

Now it would seem that, if one is proposing a rule interpreter, then its 
inputs include variable datalog programs P.  So, the applicable complexity 
would appear to be "complete in DEXPTIME".

What do you think ?

                         Cheers --    Adrian

                                        INTERNET BUSINESS LOGIC

Business Rules in English + Semantic Data Integration + Your Oracle Databases


Adrian Walker
Reengineering LLC
PO Box 1412
CT 06011-1412 USA

Phone: USA 860 583 9677
Cell:    USA  860 830 2085
Fax:    USA  860 314 1029
Received on Tuesday, 7 October 2003 10:24:22 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:44:44 UTC