- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Thu, 14 Apr 2005 16:28:13 +0200
- To: Bijan Parsia <bparsia@isr.umd.edu>
- Cc: www-rdf-logic@w3.org, Paul Gearon <gearon@itee.uq.edu.au>
On 10 Apr 2005, at 06:02, Bijan Parsia wrote: > Remember that datalog's decision procedure is polynominal whereas OWL > DL's is NEXPTIME and OWL Full is doesn't *have* a decision procedure > (i.e., it's only semi-decidable). You ain't going to shoehorn the > latter into the former without a trim...with a sledgehammer :) I like to be pedantic :-) Query answering in datalog is polynomial in data complexity (i.e., wrt the dimension of the extensional DB), but it is EXPTIME-complete in combined complexity (i.e., wrt the dimension of the whole knowledge base). Instance checking in OWL-Lite is NP-complete (recent result by Boris Motik) in data compexity, while it is EXPTIME-complete in combined complexity. Instance checking in OWL-DL is NEXPTIME-complete in combined complexity, but as far as I know, the data complexity is still unknown. As a matter of fact, Boris just proposes to reduce SHIQ to deterministic disjunctive datalog. cheers --e.
Received on Thursday, 14 April 2005 14:28:19 UTC