W3C home > Mailing lists > Public > www-rdf-logic@w3.org > April 2004

Re: Expressiveness of OWL

From: Varga Péter <pvarga@mit.bme.hu>
Date: Thu, 29 Apr 2004 14:53:30 +0200
To: Graham Klyne <gk@ninebynine.org>, Jeremy Carroll <jjc@hplb.hpl.hp.com>
Cc: www-rdf-logic@w3.org
Message-Id: <200404291453.31086.pvarga@mit.bme.hu>

Graham Klyne wrote:

> Generally, I think it would be very helpful if there were some notes that
> indicated clearly what were the capabilities and limitations of OWL in this
> regard, particularly compared with Horn Clauses. (Maybe there is one that I
> don't know about?)  It's not always clear to me how to best use OWL's
> class-based reasoning.

I think that the following article is quite illuminating about these issues:
B. N. Grosof- I. Horrocks-R. Volz-S. Decker: Description Logic Programs: 
Combining Logic Programs with Description Logic. In: Proceedings of the 
twelfth international conference on World Wide Web (WWW'2003)
http://portal.acm.org/citation.cfm?doid=775152.775160
I think Section 2 is esp. relevant for your questions.

Graham Klyne wrote:
>>(1) No "role composition" in OWL
>>The Description Logic literature makes mention of a "role constructor" 
>>called 'compose'.  I find no equivalent property in OWL;  I don't think 

Jeremy Caroll wrote:
>> Also excluded were unions and intersections of properties.
>>  (...)
> >Note procedurally what happened was not that these things were considered
> >and rejected but that our charter said start with DAML+OIL, D+O did not
> >have these things and noone suggested adding them.
Although it might have happened this way, I can see a rationale behind these 
decisions
OWL (or, more precisely speaking, OWL DL, since reasoning services are not 
guaranteed for OWL Full, see OWL Language Overview Sec. 1.3) can be mapped to 
the DL language-familiy called SHOIN (see I. Horrocks-P.F. Patel-Schneider: 
Reducing OWL Entailment to DL Satisfiability, ISWC 2003, Published in LNCS 
2870, online at http://www.cs.man.ac.uk/~horrocks/Publications/download/2003/
HoPa03b.pdf).
Unfortanately most reasoning algorithms in SHOIN are NExpTime-complete, and 
there are no optimized algorithm known for these language class (see S. 
Tobies: Complexity Results and Practical Algorithms for Logics in KR, http://
lat.inf.tu-dresden.de/research/phd/Tobies-PhD-2001.pdf).
On the other hand, by omitting some rarely used constructs (which results to 
so-called nominals) OWL DL can be reduced to the well-known DL language, 
SHOIN(D), and there exist an optimized algorithm and several reasoners 
(RACER, Pellet, FACT and so on).
So far, so good. 
But there are DL language classes emanded by role-expressions (role 
composition, unions and so on), for example ALCIreg, ALCQIreg, ALCFIreg, and 
they are also in ExpTime. (See Chapter 5 in the Description Logics Handbook).
Here is the point to ask why role expressions are not included in OWL DL. It 
seems, that they could be included (and this is, what J. Caroll suggests).
The problem, I think, is that these "reg"-langauges still lack the numerical 
restrictions on roles, which is considered by the modeling community to be an 
important feature. (Numerical restriction are present in SHOIN(D).) But when 
adding numerical restrictions, these "reg"-languages become indecidabile (see 
the same Chapter).

This is the rationale I see behind excluding role expressions from OWL. And 
this is why I think that -- allowing that it might have happened from mere 
continguence (which, personally speaking, I do not believe:) -- it is a good 
decisions (although I also suffer from it in my modeling practice:)

All the bests,
 Peter
-- 
Peter Varga
Phd-Student
Budapest University of Technology and Economics
Department of Measurement and Information Systems
www.mit.bme.hu/~pvarga/ (+36)-1-463-2066
Builidng I., Room E.336.
Received on Thursday, 29 April 2004 17:46:33 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:48 GMT