SPDL Algorithms

Abstract

This document describes the algorithms used to resolve SPARQL queries against SPDL patterns.

Status of this Document

This document is part of the documentation for the SPDL project.

This is the work of the author — it is not endorsed by the W3C members.

1 Goals

The process examples in this document will use a query:

PREFIX tns: <http://webservices.amazon.com/AWSECommerceService/2004-11-10>
SELECT ?asin ?title WHERE {
 ?X tns:id "0FWYBWB91M5S26YBE382" ;
    tns:keywords "Weaving" ;
    tns:index "Books" ;

    tns:asin ?asin ;
    tns:title ?title };

to invoke an Amazon Web Service annotated with SPDL.

The parsed web service gives you a set of invokers, each with an assocated set of input and output annotations. (Input and output names are designated from the perspective of the web service. This agent issues a request that comforms to some operation's input specification and parses a response conforming to the output specification.)

2 Exact

This rather naive approach involves an exact match between the submitted query and the input and output patterns of the matched web service.

• Interpret the query on an empty database.
• Reset the result set to a "fresh" state (one solution of zero bindings).
• Convert the pattern part of the query to assertions, encoding variables as var: URIs:

  assert(<var:?X> tns:id "0FWYBWB91M5S26YBE382" && 
         <var:?X> tns:keywords "Weaving" && 
         <var:?X> tns:index "Books" && 
         <var:?X> tns:asin <var:?asin> && 
         <var:?X> tns:title <var:?title>)
  

• Exectute the assertions, placing an assertion form of the the query into the previously empty database.
• Walk the list of invokers, testing:
  • Store input and output pattern as assertions (again, with var: URIs) in the invoker database.
  • Try the user's query against the invoker triple database (note additional verification needed). If matched:
    • Get the input and output components:

      pattern(?req this:id XPath(., 9880444))
      pattern(?req this:keywords XPath(tns:Keywords, 987b8a4) && 
              ?req this:index XPath(tns:SearchIndex, 987b8a4))
      pattern(?item this:asin XPath(tns:ASIN, 995d498))
      pattern(?item this:title XPath(tns:Title, 9994f94))
      

    • Change the first component's db from a simple one representing that pattern:

      <var:?req> <http://dev.w3.org/cvsweb/perl/modules/W3C/SPDL/descriptions/AWSECommerceService-SAWSDL-item-terms.ttl#id> <var:XPath(.,%209880444)> .

      to the user query database (the one with all the assertions mapped from the user's query).
    • Get that component to create a query pattern from itself and the other components:

      ask(?req this:id XPath(., 9880444) && 
          ?req this:keywords XPath(tns:Keywords, 987b8a4) && 
          ?req this:index XPath(tns:SearchIndex, 987b8a4) && 
          ?item this:asin XPath(tns:ASIN, 995d498) && 
          ?item this:title XPath(tns:Title, 9994f94))
      

      and evaluate that query.
    • Ask the input specification (in XML schema) to solve itself, given associations from annotation on the input to @@some mysterious array@.

additional verification needed

This should make sure that not only does the pattern match, but that all the IN variables correspond to ground values in the user query. For example, you may have access to bot a jpg2png and a png2jpg service and asking for the png of some jpg should invoke the correct one.

A. Resources

• SPDL Project Page

Change History

$Log: Algorithms.html,v $
Revision 1.1  2006/07/15 23:28:06  eric
+ started on a plane