[ogsa-rss-wg] Candidate Ordering Language

[Andreas Savva]

Donal,
After a quick glance this looks a bit like MathML. One thought is that
this 'simple' language could be a profiled subset of MathML, picking out
those terms which must be supported by all implementations. More
sophisticated implementations could support other features (and there
would not be a need to worry about definining extensions).

Andreas

Donal K. Fellows wrote:
> Hi everyone!
> 
> I've previously proposed that we should be returning ordered sets of
> candidates from the CSG. But it's been (rightly) pointed out that this
> means the caller needs some control over the ordering. In general, this
> is a difficult thing to do - valuation policies might need to be very
> flexible indeed, forcing the use of a general programming language with
> all the attendant security trickinesses - but we can probably do a
> cut-down version that captures most of what is needed with much less
> effort. Furthermore, if we define this through appropriate extensibility
> tricks, we can still allow the more general solutions to be there in the
> complex cases.
> 
> Therefore, this is a simple function language that operates (given some
> context offer) and provides a single floating-point value that indicates
> the ranking. (Open question: should small or large values be "good"?)
> 
>   Language consists of a term (possibly with subterms) yielding a value.
>   There are different kinds of terms:
> 
>   Combination Terms:
> 
>      <sum> term+ </sum>
>      <product> term+ </product>
> 
>      Sum adds its terms together, product multiplies them together.
>      Subtraction and division can be constructed using these and the
>      right monadic terms.
> 
>   Monadic Terms:
> 
>      <power exponent="xsd:double"> term </power>
>      <negate> term </negate>
>      <log> term </log>
>      <exp> term </exp>
>      <abs> term </abs>
> 
>      Log and exp use natural logarithms. Power isn't strictly necessary
>      with log and exp, but it'll simplify things for most common cases.
>      Abs returns the absolute value of the term (chopping any sign).
> 
>   Atomic Terms:
> 
>      <constant> xsd:double </constant>
>      <value base="xsd:dateTime|now"? > XPath </value>
>      <exists> XPath </exists>
> 
>      Constant allows the embedding of literals, value allows the use of
>      a value picked out of the context offer (strictly, it uses the
>      value of the first node in the nodeSet returned by evaluating the
>      XPath expression) and exists allows the checking of whether a
>      particular XPath expression refers to anything within the context
>      offer (it's value is 1 if the nodeSet is non-empty, and 0
>      otherwise).
> 
>      In order to deal with values that are expressed as xsd:dateTime
>      instead of numerics, value has an optional base attribute and the
>      result is the difference between the base time and the "value" time
>      in *seconds*.
> 
> Example:
> 
> The value is the sum of the price times a constant factor, and the
> inverse square root of the number of CPUs allocated (using some schema
> for offers that I've picked out of the air)...
> 
>    <sum>
>      <product>
>        <value> //price/@value </value>
>        <constant> 42 </constant>
>      </product>
>      <power exponent="-0.5">
>        <!-- Assume that somewhere there's some JSDL -->
>        <value> //JobDescription/Resources/IndividualCPUCount </value>
>      </power>
>    </sum>
> 
> Or something like that. And this very simple structure has the advantage
> of being both pretty easy to implement (once you have XPath) and free of
> programming language nasties.
> 
> Is this sufficient? Or too complicated? Have I missed anything obvious?
> 
> (The other major alternative is to define a language that can compare
> two terms, but that's likely to be more difficult to do, and it can
> easily lead to ill-defined orderings, i.e. where there is no partial
> order on the offers at all. A scoring function doesn't have those
> problems.)
> 
> Donal.
> 

-- 
Andreas Savva
Fujitsu Laboratories Ltd