W3C home > Mailing lists > Public > www-ws@w3.org > May 2003

Re: Questions about subsumption relationships for matchmaking

From: Ian Horrocks <horrocks@cs.man.ac.uk>
Date: Wed, 7 May 2003 00:23:14 +0100
Message-ID: <16056.17378.732353.179292@merlin.horrocks.net>
To: David Martin <martin@ai.sri.com>
Cc: www-ws@w3.org, Lei Li <lil@cs.man.ac.uk>

On April 29, David Martin writes:
> Hello Lei and Ian -
> 
> As you know, we had some brief discussion at the SWSI F2F meeting in
> Miami, having to do with effective matchmaking using advertisements and
> queries expressed in description logic (in particular, expressed using
> the DAML-S Profile Ontology).  Some concerns have been raised about
> possible cases where an advertisement contains too much information, so
> that it precludes a DL reasoner from finding a subsumption relationship.
> 
> This is a very central topic, it seems to me, for the successful use of
> DAML-S (and the soon to be released OWL-S) profiles.  The DAML-S
> coalition members are very keen to understand this issue.  So I'd like
> to get the ball rolling with a brief request for clarification.
> 
> I've read your recent paper, "A software framework for matchmaking based
> on Semantic Web technology", available here:
> 
> http://www.cs.man.ac.uk/~horrocks/Publications/download/2003/p815-li.pdf
> 
> The point is made there that there may be "too much information inside
> the service profile, and this makes it difficult to use automated
> reasoning techniques to compute Semantic matches between service
> descriptions".  (For those who haven't seen the paper, I should say this
> is just one relatively minor point in a broad and interesting paper.)
> 
> Anyway, I'm afraid I'm not convinced of the difficulty yet.  This may be
> because I've never studied DL subsumption thoroughly.  So the purpose
> here is just to get clarification of the problem.
> 
> Here is a simplified version of your example:
> 
> Advert1 =
>   ServiceProfile ^
>   (Sales ^
>    forall[providedBy].(Actor ^ forall[hasName].Georgia) ^
>    ...)
> 
> Query1 =
>   ServiceProfile ^
>   (Sales ^
>    forall[providedBy].(Actor ^ hasCreditLevel >= 5) ^
>    ...)
> 
> Now, it seems clear to me, as the paper states, that Query1 is *not*
> subsumed by Advert1, because the {set of actors with credit level >= 5},
> specified in Query1, may certainly include actors that aren't named
> Georgia.  And thus, Query1 may well have values of providedBy that
> Advert1 doesn't have, and so Advert1 can't subsume Query1.
> 
> But, it seems to me that simply by modifying Query1 as follows, it would
> then be subsumed by Advert1:
> 
> Query1A =
>   ServiceProfile ^
>   (Sales ^ forall[providedBy].(Actor ^ forall[hasName].BOTTOM ^
>                                        hasCreditLevel >= 5) ^
>    ...)
> 
> It seems to me that adding forall[hasName].BOTTOM means that Query1A is
> subsumed by Advert1.  (If you'd like me to justify this statement before
> you respond, just let me know, but in the interest of brevity I won't do
> so now.)
> 
> If it's true that Query1A is subsumed by Advert1, that suggests to me
> that it could be quite easy in practice to avoid the problem that's been
> raised.  I could explain further, but I'd rather not get ahead of
> myself.  Could I first just ask you to confirm whether or not Query1A is
> subsumed by Advert1?  (And of course feel free to make any other
> clarifying remarks you'd like.)

It is certainly true that forall[hasName].BOTTOM is subsumed by
forall[hasName].C for any class C (including Georgia, which is this
context probably should have been written {Georgia}, meaning "the
class whose only instance is Georgia"). This isn't really a general
solution to the problem though:

1. Adding forall[hasName].BOTTOM would rule out subsumption
relationships that might otherwise have held w.r.t. advertisements
that simply do not specify the name of the provider.

2. There may be lots of additional information, as in the case of
Advert1, (more specific forms of) which would also need to be added to
the query. In some cases this may not be appropriate (you may end up
getting spurious matches).

Regarding this 2nd point, I have to say that the example is not well
chosen as an illustration of the point about "providedBy", because
Advert1 and Query1 specify 2 different PC features (memory and
processor) which mean that they would not be in a subsumption
relationship even if neither mentioned the provider. If, however, the
PC specification in a query was identical or more general than that in
an advertisement, then one would like to find an exact or subsume
match respectively. This would not happen if forall[hasName].BOTTOM
were added to the query.

Our "solution" was to separate parts of the service profile that are
almost certainly not of interest in the matching phase so they could
be ignored by the subsumption based matcher. This does not, however,
address the wider problem that is illustrated by the example - the
fact that it may very often be the case that, even after discarding
these "irrelevant" parts of the descriptions", advertisements and
queries will not be in subsumption relationships, but satisfy only the
very weak "intersection" matching condition (i.e., their intersection
is not a contradiction). This is because advertisers and queriers may
choose to be more specific about different aspects of the description
(memory and processor in this example).

Regards, Ian


> 
> Thanks,
> David Martin
Received on Tuesday, 6 May 2003 19:23:19 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 3 July 2007 12:25:42 GMT