Re: Suggestions for implementing a "document matches" program?

At 20:03 20/04/2003 -0400, Roger L. Costello wrote:

>Hi Folks,
>
>Suppose that you want to create a PROGRAM which, when handed *any* XML
>instance document, decides whether or not it meets this desire:
>
>"I am interested in purchasing a camera with a 75-300mm zoom lens, that
>has an aperture of 4.5-5.6, and a shutter speed that ranges from 1/500
>sec. to 1.0 sec."

Assuming that we're talking here about RDF rather than any old XML...

The matching you ask for seems to be just like the subsumption calculation 
of Description Logic ideas that underpin (some flavours of) 
OWL.  Essentially, given two descriptions, find a new minimal description 
that subsumes both of the given descriptions.  If that description is not 
an empty collection, then you have a match.  I found Alex Borgida's 
introduction to description logics [1] to be illuminating.

Another variation of these ideas which could be mapped into RDF is in some 
IETF work I did on content negotiation, documented in RFC2533 [2], and 
updated in a private note [3].

Note that there are restrictions on the kinds of expression that these 
algorithms handle.  A fully-general matching algorithm is computationally hard.

#g
--

[1] ftp://ftp.cs.rutgers.edu/pub/borgida/dldb.survey.TKDE.ps.gz
(Originally published in IEEE Transactions on Knowledge and Data 
Engineering, 1995).

[2] http://www.ietf.org/rfc/rfc2533.txt

[3] 
http://www.ninebynine.org/IETF/Conneg/draft-klyne-conneg-feature-match-02a.txt


At 20:03 20/04/2003 -0400, Roger L. Costello wrote:

>Hi Folks,
>
>Suppose that you want to create a PROGRAM which, when handed *any* XML
>instance document, decides whether or not it meets this desire:
>
>"I am interested in purchasing a camera with a 75-300mm zoom lens, that
>has an aperture of 4.5-5.6, and a shutter speed that ranges from 1/500
>sec. to 1.0 sec."
>
>To recap, here's the scenario:
>
>XML instance document --> PROGRAM ---> "Yes! It's a match!"
>                                        (or, "No match")
>
>[The idea is that PROGRAM will "consult" the Camera Ontology whenever it
>encounters XML elements that it does not "understand"]
>
>What are your recommendations for implementing PROGRAM?
>
>Would you recommend using a query language, such as DQL (DAML Query
>Language) combined with some Java code?  Or would you recommend using
>something else?  Has someone already done something like this?  /Roger

-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E

Received on Tuesday, 22 April 2003 16:44:13 UTC