- From: Adrian Walker <adrianw@snet.net>
- Date: Tue, 07 Oct 2003 10:26:21 -0400
- 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
"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.
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
www.reengineeringllc.com
Adrian Walker
Reengineering LLC
PO Box 1412
Bristol
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