Re: Questions about subsumption relationships for matchmaking

> On May 7, Ian Horrocks <horrocks@cs.man.ac.uk> writes:
> 
> 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


I agree with Ian.

The point is that you can't do everything with subsumption. Matchmaking 
can be much more complex than that.

I think this is a good case for why more expressive languages might be
needed.  For instance, you might have to specify your policy for matching
using Prolog-style rules. And you very well might want to use
negation-as-failure type of stuff in those rules, so it won't be a simple
extension of a DL.


	regards
	  --michael

Received on Monday, 12 May 2003 02:36:05 UTC