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

Re: Questions about subsumption relationships for matchmaking

From: David Martin <martin@AI.SRI.COM>
Date: Mon, 12 May 2003 18:34:22 -0700
Message-ID: <3EC04B9E.6C504CA3@ai.sri.com>
To: Ian Horrocks <horrocks@cs.man.ac.uk>
CC: www-ws@w3.org, Lei Li <lil@cs.man.ac.uk>

Hi Ian -

Thanks for your response.  My comments are all the way at the bottom - and I
do solicit further discussion on this important topic.

Ian Horrocks wrote:

> 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

Yes, this is a good restatement of the point you brought up in Miami.

But it still doesn't seem clear to me that this is a significant problem.
That is, it seems to me there's a perfectly reasonable, natural way of using
DL to perform matchmaking that avoids this problem.  I think it just requires
the following conventions:

(1) An advertiser expresses a class of services using an expression that's as
*general* as possible.

(2) A requester expresses a query for a service desired using an expression
that's as *specific* as possible.

(3) When a requester doesn't care about how a particular property is
restricted, his query expresses "don't care" for that property, using
    forall[property].BOTTOM
as in my proposed reformulation of the example query.

It seems to me these conventions add up to a very natural approach to
knowledge representation for service matchmaking -- at least for the most
normal, familiar kind of matchmaking.  That is, an advertiser normally
advertises his services in the most general way possible (think of the Yellow
Pages), and a service-seeker normally describes what he wants to accomplish,
in a particular use of a service, in the most specific way possible.  A
matchmaker that's tailored to answer whether queries meeting convention (2)
above are subsumed by advertisements meeting convention (1) may not support
every conceivable kind of matchmaking, but it seems to me an extremely useful
approach that supports the most mainstream kind.

Under these conventions, one is primarily interested in identifying the set of
advertisements that subsumes a given query.  Those are the advertisements that
most effectively identify the candidate service providers.   But one can still
test for cases in which an advertisement and query are merely compatible, and
for cases in which the query subsumes the advertisement - and if such cases
are identified, one can use that knowledge to make reasonable choices about
whether and how to use those cases.

I've been going around telling people that service matchmaking *is*, in fact,
a very natural application of DL subsumption, so I'm very keen to know if I've
been lying or not :-).  I'd certainly like to get your comments (as well as
others') about whether the use of DL under conventions (1) - (3) will work
well for (what seems to me) the most normal, mainstream kind of matchmaking.
At the moment I don't see why it wouldn't!

Regards,
David
Received on Monday, 12 May 2003 21:33:31 GMT

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