- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Tue, 22 Apr 2003 17:39:56 +0200
- To: Ian Horrocks <horrocks@cs.man.ac.uk>, Bob MacGregor <macgregor@ISI.EDU>
- CC: <www-rdf-logic@w3.org>
On 22/4/03 3:55 pm, Ian Horrocks wrote: > The good news is that it is possible to add keys to these langauges > without loosing decidability for key inference problems. The bad news > is that computational complexity is rather high: it is easy to see > that keys are at least as expressive as nominals (oneOf), as integer > keys can be used to simulate an arbitrary number of nominals. This is not true in general. As the paper cited by Ian says, it is only true under the (expensive) assumption that the keys operate over a concrete domain. If you want to reason with keys that operate over the abstract domain (which to me makes more sense in an abstract conceptual modelling context), then the algorithmic complexity is definitely lighter, and easily encodable in the available implemented DL systems (without nominals). The problem reduces to the efficiency of implemented systems with cardinality and inverses. ciao -- e. 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
Received on Tuesday, 22 April 2003 11:40:30 UTC