Enrico -

Good point.

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 ?

                        Thanks in advance,   -- Adrian

                           INTERNET BUSINESS LOGIC

Semantic Integration + Business Rules in English + 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 06:44 PM 10/1/03 +0200, you wrote:
On Wednesday, October 1, 2003, at 04:46 PM, Adrian Walker wrote:
We have some of the same concerns about RDF and OWL, and I have occasionally questioned some of the folks preparing the W3C RDF document about this.

One thing that we have found that makes it easier to explore these questions, is to have a mechanism that executes recursive axioms safely and efficiently.  In addition, we assign an English meaning to each predicate, to keep track of what we are doing.

I'd be interested please in getting your set of axioms so far, plus English comments where needed.

If you can kindly send these, I will try rephrasing them in our Internet Business Logic system.  Then, we can run them over deliberately chosen tricky test examples to see what happens.  You and your students will also be able to run them by pointing a browser to our site if you wish.

BTW, the system implements a model theory of stratified datalog programs augmented with negation as failure, plus aggregation predicates that support "bag", "set' and so forth.

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.


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