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

Questions about subsumption relationships for matchmaking

From: David Martin <martin@ai.sri.com>
Date: Tue, 29 Apr 2003 23:16:17 -0700
Message-ID: <3EAF6A31.39E7BCC3@ai.sri.com>
To: www-ws@w3.org, Lei Li <lil@cs.man.ac.uk>, Ian Horrocks <horrocks@cs.man.ac.uk>

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.)

Thanks,
David Martin
Received on Wednesday, 30 April 2003 02:16:24 GMT

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