W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > October to December 2011

Re: Order of evaluation for aggregates

From: Steve Harris <steve.harris@garlik.com>
Date: Wed, 16 Nov 2011 12:29:36 +0000
Cc: Andy Seaborne <andy.seaborne@epimorphics.com>, SPARQL Working Group <public-rdf-dawg@w3.org>
Message-Id: <65B5E4FD-6AA7-437A-9CED-9A9B8DAF8012@garlik.com>
To: birte.glimm@uni-ulm.de
On 2011-11-15, at 19:22, Birte Glimm wrote:

> On 15 November 2011 18:12, Andy Seaborne <andy.seaborne@epimorphics.com> wrote:
>> 
>> 
>> On 15/11/11 12:44, Steve Harris wrote:
>>> 
>>> Many thanks Birte.
>>> 
>>> OK, of these I suspect that changing the substitution to (SAMPLE(?x) AS
>>> ?x) will mean the least changes.
>> 
>> As syntax, (SAMPLE(?x) AS ?x) isn't legal because AS has to introduce a new
>> variable. This happens in SELECT expression processing a few subsections.
> 
> Yes, that occured to me as well. Unless it is made legal for
> intermediate queries, which I don't like, there seems no way around
> creating solutions in the aggregate join that also contain the grouped
> variables.

Yes, that why I ended up with the messy agg_i thing, to avoid conflating aggregate results with variable names.

Reading through this again, I think that the text as written is correct:

    For each variable V appearing outside of an aggregate
        Replace V with Sample(V) in Q
        End

ensures that there's only aggregates being projected, then

    For each aggregate X(args ; scalarvals) now in E
        # note scalarvals may be omitted, then it's equivalent to the empty set
        Ai := Aggregation(args, X, scalarvals, G)
        Replace X(...) with aggi in Q
        i := i + 1
        End

Defines A_i/agg_i for the Sample(V) above. I could well have spec blindness though.

- Steve

>> There is no definition of "Aggregation".  It's mentioned in 11.2 but the
>> link goes to "Definition: Evaluation of Aggregation".  There should a
>> definition (just after group?) in 18.4.
> 
> Yes, I also wondered about that. It is somehow clear how to evaluate,
> but it would be much more consistent if there were a definition.
> 
>> I looked because I wondered if we could just have an "?x" as the
>> "aggregate".
> 
> Not sure I understand this.
> 
>> But I think, as Birte shows, as because it's done by syntactic
>> rewriting, just leaving it as "?x" would work.
> 
> As I don't understand the sentence above. I just want to make my point
> again that we need a binding for ?x if ?x is grouped but not in an
> aggregate as it can be used in the HAVING clause. If, at the point of
> evaluating HAVING, we only have agg_1, we can't filter on ?x.
> 
>>> I wanted to convert the plain ?x projection to an aggregate so it was
>>> consistent with the rest of the projections, but expressing it explicitly
>>> would be equivalent I think.
>>> 
>>> I will have a run through the aggregation text and see if I can make that
>>> change with a relatively small change to the document.
>>> 
>>> Cheers,
>>>    Steve
>> 
>> I also noticed;
>> 
>> [[
>> Definition: Evaluation of AggregateJoin
>> ...
>> Note that if eval(D(G), Ai) is an error, it is ignored.
>> ]]
>> 
>>  An error causes an error doesn't it?  (AS causes it to be unbound)
> 
> AS is transformed into Extend(), which is evaluated:
> Extend(μ, var, expr) = μ ∪ { (var,value) | var not in dom(μ) and value
> = eval(expr) }
> Extend(μ, var, expr) = μ if var not in dom(μ) and eval(expr) is an error
> 
> The latter makes the solution just not contain a mapping for the
> variable as I understand it.
> 
> But while we are at it, there is a lowercase extend in the Definition of Extend:
> Extend(Ω , var, term) = { extend(μ, var, term) | μ in Ω }
> 
> It is also lowercase in the evaluation semantics:
> Definition: Evaluation of Extend
> eval(D(G), extend(var, expr, P)) = extend(var, expr , eval(D(G), P))
> Furthermore, here we swap the order. It should be
> eval(D(G), Extend(P, var, expr)) = Extend(eval(D(G), P), var, expr)
> or the algorithm for translating queries into the algrebra is wrong
> and has to be changed.
> 
> Birte
>>        Andy
>> 
> 
> 
> 
> -- 
> Jun. Prof. Dr. Birte Glimm            Tel.:    +49 731 50 24125
> Inst. of Artificial Intelligence         Secr:  +49 731 50 24258
> University of Ulm                         Fax:   +49 731 50 24188
> D-89069 Ulm                               birte.glimm@uni-ulm.de
> Germany
> 

-- 
Steve Harris, CTO, Garlik Limited
1-3 Halford Road, Richmond, TW10 6AW, UK
+44 20 8439 8203  http://www.garlik.com/
Registered in England and Wales 535 7233 VAT # 849 0517 11
Registered office: Thames House, Portsmouth Road, Esher, Surrey, KT10 9AD
Received on Wednesday, 16 November 2011 12:31:04 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:47 GMT