Re: Intersection of properties?

Hi all,
Yevgeny and I recently worked on this (see
http://web.comlab.ox.ac.uk//files/361/RoleConjunctions.pdf for a
technical report). The complexity of OWL or fragments thereof extended
with role conjunctions was not very well understood, in particular
when you have transitive roles. We showed that for OWL Lite adding
role conjunctions (even without functional roles/number restrictions)
causes an exponential jump from ExpTime-complete to 2ExpTime-complete.
If you do not have inverse roles the complexity remains ExpTime even
with (qualified) number restrictions (SHQ). For OWL DL (even for the
DL SHOIF) we have shown N2ExpTime hardness, so adding role
conjunctions to OWL DL makes reasoning at least exponentially harder
and we didn't show an upper bound so even decidability is an open
question. So far I believe OWL DL & OWL2 plus role conjunctions would
result in decidable logics, but this has not been proven to the best
of my knowledge.
I hope that helps a little.
Best regards,
Birte

2008/8/3 Bijan Parsia <bparsia@cs.man.ac.uk>:
>
> On Aug 3, 2008, at 8:57 PM, Jeff Thompson wrote:
>
>> Bijan Parsia wrote:
>>>
>>> On Aug 3, 2008, at 7:58 PM, Jeff Thompson wrote:
>>> [snip]
>>>>
>>>> I sounds like many implementors
>>>
>>> No, it doesn't sound like that. Those were all theory papers.
>>>>
>>>> see that even OWL 2 is not expressive
>>>> enough to solve their data processing needs, and so everyone has
>>>> their own extensions in Pellet, etc.
>>>
>>> ? No. The implementation of ALBO is not, by any means, production quality
>>> (or would purport to be even vaguely scalable to realistic kbs). There's
>>> only one, sorta implementation of PDL (Peter's DLP, which is sorta defunct).
>>> So, I don't know where you're getting this from :)
>>>>
>>>> And yet, the argument against
>>>> adding more expressiveness to OWL 2 (still decidable) is the fear
>>>> that not enough people will implement it and so that "OWL 2 compliant"
>>>> won't mean much.
>>>
>>> What? The argument against boolean role boxes, in general, is that it's
>>> relatively hard to do and there's been relatively little demand for it. ALBO
>>> is *very* expressive but, you know, doesn't have cardinality restrictions.
>>> I personally don't feel a burning desire for role conjunction. Perhaps
>>> you could list use cases?
>>
>> I already implemented SWRL in Browlser.
>> http://browlser.sourceforge.net/
>
> Actually, you haven't (at least I'm very skeptical that you have). At least
> not how it is properly understood. See:
>        http://clarkparsia.com/weblog/category/semweb/rules/swrl/
>
> You may have implemented some sort of DL Safe variant.
>
>> And so I'm trying to understand which of the implicit rules
>> in the OWL 2 axioms can be used instead of SWRL rules.
>
> There is some good recent work on this. Which I'm having trouble finding at
> the moment ;) I ping Uli and Markus for the pointers.
>
>> The "uncle" rule with role chains is a good example of where OWL 2 on
>> its own is good enough without having to spell out the rule in SWRL.
>> There are many SWRL rules I use which are of the form of role conjunction.
>
> If you are happy with the DL Safe version (as I suspect you are), then there
> are several implementations and you can have all these.
>
>> I also use the equivalent of role chains that end in a datatype but the
>> OWL working group has already rejected these.
>> http://www.w3.org/2007/OWL/tracker/issues/8
>
> Sufficient feedback could change things. It's hard to act with out data.
>
>> So I'm trying to understand what's "in" and what's "out" and why.
>
> For the role chains and datatype, this is key:
>        http://lists.w3.org/Archives/Public/public-owl-wg/2007Dec/0174.html
>
> Sensible implementation of path based concrete domains is a open challenge.
> DL Safe rules with data properties have some challenges but are much more
> likely to be robustly implemented in the near term (say, year).
>
>>>> I know it's a difficult political task to balance.
>>>> Is the general assumption that there will need to be several more
>>>> revision cycles to OWL before a large number of people will use it
>>>> as specified without needing to add their own incompatible extensions?
>>>
>>> I think you're confused. OWL already is used by a large number of people
>>> without needing to add their own incompatible extensions. If you have a
>>> strong need for very expressive role boxes, I suggest you submit a paper to
>>> OWLED detailing your needs.
>>
>> Thanks for the quick feedback.  There's a lot of work going on which is
>> exciting.
>
> Yep. Please make your needs known!
>
> Cheers,
> Bijan.
>
>

Received on Monday, 4 August 2008 13:31:19 UTC