Enrico --

Thanks for your reply, below.

Actually, there may be something else going on here.

If I remember correctly, the view that datalog can only compute things of polynomial complexity depends on using the "well-founded" semantics.  But that semantics has a strong tendency to assign the value "unknown" to many otherwise intuitively OK computations.
It may indeed be the case that datalog (or datalog + negation) can compute things of exponential complexity if you assign instead the Apt-Blair-Walker [1] stratified semantics.

Could this be correct ?        Cheers, -- Adrian

[1]  Towards a Theory of Declarative Knowledge, (with K. Apt and H. Blair).  In: Foundations of Deductive Databases and Logic Programming, J. Minker (Ed.), Morgan Kaufman 1988.

                           INTERNET BUSINESS LOGIC

Business Rules in English + Semantic 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

At 12:19 AM 10/2/03 +0200, you wrote:

On Wednesday, Oct 1, 2003, at 20:14 Europe/Rome, Adrian Walker wrote:
The Internet Business Logic engine capabilities mentioned below are stratified datalog with negation, plus some aggregation operations (SDA).  It's possible that this goes beyond polynomial complexity.
For the purposes of exploring Tamel's questions, it may turn out that SDA is enough.
But for more general purposes, can you point me to the proof that OWL is EXPTIME-hard please?

I don't think that aggregation has been used in this context capture, for example, even the complexity of the propositional content of OWL (which is obviously a NP-hard component).
The EXPTIME-hardness complexity comes from the fact that it is possible to encode in OWL-dl and OWL-lite the simplest propositionally complete description logic (i.e., ALC) which is EXPTIME-complete.


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

On Wednesday, Oct 1, 2003, at 18:44 Europe/Rome, Enrico Franconi wrote:
This is soemthing I always wanted to ask: how comes that reasoning for a language like OWL (starting from OWL-lite itself) -- whose complexity has been proved to be EXPTIME-hard -- is going to be implemented with a polynomial language such as the datalog variant you're talking about? I've seen many implementations based on this idea (e.g., based on ECA rules), and I wonder whether there is something I'm missing.