- From: Steve Harris <steve.harris@garlik.com>
- Date: Tue, 22 Nov 2011 20:37:47 +0000
- To: birte.glimm@uni-ulm.de
- Cc: Andy Seaborne <andy.seaborne@epimorphics.com>, SPARQL Working Group <public-rdf-dawg@w3.org>
On 22 Nov 2011, at 18:06, Birte Glimm wrote:
> On 22 November 2011 13:50, Steve Harris <steve.harris@garlik.com> wrote:
>> OK, I think I have a solution, which bridges the gap, and doesn't violate any scope rules:
>>
>> For each expression E in SELECT and each HAVING(E) in Q
>>
>> If E does not contain an aggregate
>> Replace E with Sample(E) in Q
>> End
>>
>> For each variable V appearing outside of an aggregate
>> Ai := Aggregation(V, Sample, {}, G)
>> Replace V with aggi in E
>> Q := Extend(Q, V, aggi)
>> i := i + 1
>> End
>>
>> 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
>>
>> End
>>
>> So, SELECT ?x {?x :p ?v } GROUP BY ?x
>>
>> Becomes
>>
>> A=AggregateJoin(Aggregation((?x), SAMPLE, {}, A))
>>
>> rewritten query:
>> SELECT ?agg1 {?x :p ?v } GROUP BY ?x
>>
>> The the result is
>> Extend(Project(A, {?agg1}), ?x, ?agg1)
>>
>> - Steve
>
> Wouldn't it be possible and cleaner to take the loop for the
> non-aggregated variables out of the outer loop? It is IMO not
> necessary to do the variable loop for each E. Then we would have:
>
> For each expression E in SELECT and each HAVING(E) in Q
> If E does not contain an aggregate
> Replace E with Sample(E) in Q
> End
> 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
> End
>
> For each variable V appearing outside of an aggregate
> Ai := Aggregation(V, Sample, {}, G)
> Replace V with aggi in E (I guess now I should use Q instead of E)
> Q := Extend(Q, V, aggi)
> i := i + 1
> End
…there's some other issues here, but it doesn't matter…
> It can also be that I am confused as to what is done where. As I see
> it, we have the following cases:
> 1. Select:
> a. aggregates, e.g., (AVG(?var1) AS ?var2)
> b. grouped unaggregated vars, e.g., just ?var
> 2. Having
> a. expressions with aggregates, e.g., AVG(?var1) > 5
> b. expressions with unaggregated but grouped vars: ?var1 + ?var2 > 5
> possibly
> 3. Order By
> a. expressions with aggregates, e.g., AVG(?var1)
> b. expressions with unaggregated but grouped vars: ?var1 + ?var2
3 is currently (LC1) not allowed, Andy wants to add it, but I've not looked at the implications.
> I don't see that 3.b is forbidden, but it is not taken care of at all
> in the evaluation. I believe 3.a. can be handled in exactly the same
> way as 2.b.
>
> For 2.b., we don't have to care about extending the solutions to
> assign a value to the original variable, but for both 1.b. and 2.b. we
> want to add sampling. For the having expressions, we can't sample the
> whole expression, we have to sample each variable occurence. I don't
> think the latter is taken into account yet.
Right.
> What I don't like is that we now have non-legal queries as they are
> intermixed with algebra objects. Before, one could think of the
> algebra transformation as just looking at the query while constructing
> the algebra object. This also leads to problems as I show below.
>
> I'll try the example again with a HAVING clause, which covers 2.a and 2.b:
>
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?x)) > 3 && COUNT(?x) > 2)
>
> We start with:
> G=Group((?x), Bgp(?x :p ?v))
> I have E=STRLEN(STR(?x)) > 3 && COUNT(?x) > 2, which I replace in Q
> (just the selected
> ?x is not an expression I assume):
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (SAMPLE(STRLEN(STR(?x)) > 3 && COUNT(?x) > 2))
> Then I get:
> Aggregation((STRLEN(STR(?x)) > 3 && COUNT(?x) > 2), SAMPLE, {}, A)
> This is not great as I will not do any expression evaluation in the
> aggregation step (STRLEN etc).
>
> To fix this, I can modify the IF clause, so that only the variables
> are replaced and not the whole expression:
> If E contains an unaggregated variable V
> Replace V in E with Sample(V)
> End
>
> After replacing I then get:
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(SAMPLE(?x))) > 3 && COUNT(?x) > 2)
> Then I handle the having expression, which contains 2 aggregates:
> A1=Aggregation((?x), SAMPLE, {}, G)
> A2=Aggregation((?x), COUNT, {}, G)
> and Q
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?agg1)) > 3 && ?agg2 > 2)
>
> I then handle the selected unaggregated variables:
> A3=Aggregation((?x), SAMPLE, {}, G)
> Q=SELECT ?agg3 WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?agg1)) > 3 && ?agg2 > 2)
> (not totally clever to sample x twice...)
> and Q:
> Extend(SELECT ?agg3 WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?agg1)) > 3 && ?agg2 > 2),
> ?x, ?agg3
> )
>
> Somehow it is not nice to directly mix algra objects into the query. I
> don't think the spec makes it very explicit that the transformation
> step by step replaces query parts with algebra objects. One would, for
> example, have to remove explicitly the WHERE keyword at some point. So
> far that wasn't necessary as the algebra transformation just looked at
> the query to guide the algebra construction. But, ok, lets assume for
> now that we really mix.
>
> I also have A=A1, A2, A3
> and P=AggregateJoin(A)
>
> Then I process HAVING:
> P=Filter(STRLEN(STR(?agg1)) > 3 && ?agg2 > 2, P)
>
> Now I come to select expressions (18.2.4.4)
> X=P (algebra from previous steps)
> VS=(?agg3, ?x) (visible vars, I believe ?y is not visible since it is
> not grouped, not sure about ?agg3/?x)
> P={} (projected vars)
> E=[] (list of expressions)
> I have no select expressions, so I simply get
> P={?agg3} (<- not good, I want to select ?x)
>
> Only solution modifiers are left:
> The spec says: Let M := ToList(Pattern), but I believe Pattern is in
> fact the algebra expression from the previous steps (this should be
> fixed), which was last named X:
> M := ToList(X)
> and then
> M := Project(ToList(X), {?agg3})
>
> All taken together that is:
> Project(
> ToList(
> Filter(STRLEN(STR(?agg1)) > 3 && ?agg2 > 2,
> AggregateJoin(
> Aggregation((?x), SAMPLE, {}, Group((?x), Bgp(?x :p ?v)))
> Aggregation((?x), COUNT, {}, Group((?x), Bgp(?x :p ?v)))
> Aggregation((?x), SAMPLE, {}, Group((?x), Bgp(?x :p ?v)))
> )
> )
> ), {?agg3}
> )
>
> The AggregateJoin(.) opertor will now assemble solutions with domain
> {agg1, agg2, agg3}, which map to a sample value for agg1 and agg3 and
> to the count for agg2.
>
> Filter should then work as expected. We lost, however, the Extend(.)
> since the algorithm in 18.2.4.4 for select expressions does just take
> the algebra from the previous steps and then looks at the select
> expressions to extend the algebra object.
>
> Since I also don't like the mix of SPARQL query with algebra objects,
> why not do the following: You initialise a list E of pairs of the form
> (variable, expression) in the aggregate translation algorithm. This
> list is then used (and extended) by the select expression algorithm in
> 18.2.4.4, so there you no longer start with an empty list E. This is
> pretty consistent with how the projected variable list is used later
> by the Project(.) operator. In this case, we don't have to rewrite the
> selected unaggregated variables with aggi. The complete algorithm
> would then be:
>
> ------------------------
> Let A := the empty sequence
> Let Q := the query level being evaluated
> Let P := the algebra translation of the GroupGraphPattern of the query level
> Let E := [], a list of pairs of the form (variable, expression)
>
> If Q contains GROUP BY exprlist
> Let G := Group(exprlist, P)
> Else
> Let G := Group((1), P)
> End
>
> Let i := 1
>
> For each expression E in SELECT and each HAVING(E) in Q
> If E does not contain an aggregate
> Replace E with Sample(E) in Q
> End
> 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
> End
>
> For each variable V appearing outside of an aggregate
> Ai := Aggregation(V, Sample, {}, G)
> E := E append (V, aggi)
> i := i + 1
> End
>
> A := Ai, ..., Ai-1
> P := AggregateJoin(A)
>
> For each HAVING(E) in Q
> P := Filter(E, P)
> End
>
> Note: E is then used in 18.2.4.4 for the processing of select
> expressions.
OK, that seems pretty reasonable, but "Expression E" etc. probably needs some other symbol to reduce confusion.
I think there's a problem with SELECT though:
SELECT ?x
WHERE { ?x a <Foo> }
GROUP BY ?x
"If E does not contain an aggregate" will be true, and that will become SELECT Sample(?x), but the extend E will not be modified.
"If E does not contain an aggregate, or group variable" may cover it?
> ---------------------------------
>
> Lets do the example again:
>
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?x)) > 3 && COUNT(?x) > 2)
>
> We start with:
> G=Group((?x), Bgp(?x :p ?v))
>
> I then have E=STRLEN(STR(?x)) > 3 && COUNT(?x) > 2.
> After replacing I get:
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(SAMPLE(?x))) > 3 && COUNT(?x) > 2)
>
> Then I handle the having expression, which contains 2 aggregates:
> A1=Aggregation((?x), SAMPLE, {}, G)
> A2=Aggregation((?x), COUNT, {}, G)
> and Q
> SELECT ?x WHERE {?x :p ?v }
> GROUP BY ?x
> HAVING (STRLEN(STR(?agg1)) > 3 && ?agg2 > 2)
>
> I then handle the selected unaggregated variables:
> A3=Aggregation((?x), SAMPLE, {}, G)
> Q no longer needs any rewriting
> and E: [(?x, ?agg3)]
>
> I get P=AggregateJoin(A1, A2, A3)
>
> Then I process HAVING:
> P=Filter(STRLEN(STR(?agg1)) > 3 && ?agg2 > 2, P)
>
> Now I come to select expressions (18.2.4.4)
> X=P (algebra from previous steps)
> VS=(?x) (visible vars)
> P={} (projected vars)
> E=[(?x, ?agg3)] (list of expressions, now initialised from aggregation
> algorithm)
> I now have select expressions, so I get
> X=Extend(X, ?x, ?agg3)
> P={?x}
>
> Now the solution modifiers:
> I again assume pattern is the algebra object, i.e., X:
> M := ToList(X)
> and then
> M := Project(ToList(X), {?x})
>
> All taken together that is:
> Project(
> ToList(
> Extend(
> Filter(STRLEN(STR(?agg1)) > 3 && ?agg2 > 2,
> AggregateJoin(
> Aggregation((?x), SAMPLE, {}, Group((?x), Bgp(?x :p ?v)))
> Aggregation((?x), COUNT, {}, Group((?x), Bgp(?x :p ?v)))
> Aggregation((?x), SAMPLE, {}, Group((?x), Bgp(?x :p ?v)))
> )
> ), ?x, ?agg3
> )
> ), {?x}
> )
>
> This looks good to me. We select only the variables that were in the
> select clause, but sampled them internally. We filter according to
> having conditions and that worked both with aggregated and
> unaggregated variables. We no longer mix algebra objects with the
> query, so we keep at all times a legal SPARQL query while we build the
> algebra object.
Yes, that seems a lot cleaner.
> Handling aggregates in the ORDER BY clause shouldn't be a
> problem. ORDER BY is also processed before projection, so we can
> without problems order based on some ?aggi.
OK, cool, I haven't been able to check that.
> Sorry for such a long mail, but we really get this sorted for 2LC…
No, thanks for putting in the time. I've been going over this again and again, but don't have time to get the whole algebra swapped in :(
I'll try the pseudocode you suggest above (replacing one occurrence of E with something else), and see ho that is.
Cheers,
Steve
>>
>> Becomes
>>
>> A=AggregateJoin(Aggregation((?x), SAMPLE, {}, A))
>>
>> rewritten query:
>> SELECT ?agg1 {?x :p ?v } GROUP BY ?x
>>
>> The the result is
>> Extend(Project(A, {?agg1}), ?x, ?agg1)
>
>
>
> 18.2
> ...
> The result of converting such an abstract syntax tree is a SPARQL
> query that uses the following symbols in the SPARQL algebra:
> The following table misses entries for Group, Aggregate and AggrateJoin.
>
>>
>> On 2011-11-21, at 21:26, Birte Glimm wrote:
>>
>>> On 21 November 2011 15:28, Andy Seaborne <andy.seaborne@epimorphics.com> wrote:
>>>> Steve,
>>>>
>>>> Could you walk through the translation of:
>>>>
>>>> SELECT ?x {?x :p ?v } GROUP BY ?x
>>>
>>> Up to aggregation you get:
>>> A=Group((?x), Bgp(?x :p ?v))
>>> rewritten query:
>>> SELECT SAMPLE(?x) {?x :p ?v } GROUP BY ?x
>>> Then
>>> A=AggregateJoin(Aggregation((?x), SAMPLE, {}, A))
>>> rewritten query:
>>> SELECT ?agg1 {?x :p ?v } GROUP BY ?x
>>> Finally:
>>> Project(A, {?agg1})
>>>
>>> Now you evaluate and get results where ?agg1 has some binding, but ?x
>>> is lost and Extend(...) is not used to extend the solutions so that ?x
>>> gets the values that ?agg1 has.
>>>
>>> Birte
>>>
>>>
>>>> This is the case where there is no AS because the variable is part of the
>>>> group key.
>>>>
>>>> Andy
>>>>
>>>> On 17/11/11 09:00, Birte Glimm wrote:
>>>>>
>>>>> On 16 November 2011 19:08, Steve Harris<steve.harris@garlik.com> wrote:
>>>>>>
>>>>>> On 2011-11-16, at 16:58, Birte Glimm wrote:
>>>>>>
>>>>>>> [snip]
>>>>>>>>>>
>>>>>>>>>> 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.
>>>>>>>
>>>>>>> That still does not solve the problem that you loose the original
>>>>>>> variable name, so results will contain agg_i and even worse, if you
>>>>>>> have a having clause, the variable used there might no longer exist
>>>>>>> since it was replaced by agg_i.
>>>>>>
>>>>>> I believe that's taken care of by AggregateJoin:
>>>>>>
>>>>>> Write A = (A1, A2, ...) where Ai = Aggregation(exprListi, funci,
>>>>>> scalarvarsi, P)
>>>>>>
>>>>>> eval(D(G), AggregateJoin(A)) = { (agg1, v1), ..., (aggn, vn) | vi such
>>>>>> that ( k, vi ) in eval(D(G), Ai)
>>>>>> for some k and each 1<= i<= n }
>>>>>>
>>>>>> vi is your var below, I think.
>>>>>
>>>>> I don't think. vi is the aggregated value, so you ( k, vi ) with k the
>>>>> key that was used to group the values and vi the aggregated value.
>>>>> I'll do one complete example to make clear where I think we have a
>>>>> problem:
>>>>>
>>>>> Assume data:
>>>>> ex:Birte ex:mark 4, 5 .
>>>>> ex:Steve ex:mark 3, 5 .
>>>>> and query:
>>>>> SELECT ?name (MAX(?mark) AS ?max) (AVG(?mark) AS ?avg)
>>>>> WHERE { ?name ex:mark ?mark } GROUP BY ?name
>>>>>
>>>>> Algebra translation up to group gives:
>>>>> A=Group((?name), Bgp(...))
>>>>> Replace ?name with SAMPLE(?name)
>>>>> SELECT SAMPLE(?name) (MAX(?mark) AS ?max) (AVG(?mark) AS ?avg)
>>>>> WHERE { ?name ex:mark ?mark } GROUP BY ?name
>>>>> continue transformation:
>>>>> A= AggregateJoin(
>>>>> Aggregation((?name), SAMPLE, {}, A),
>>>>> Aggregation((?mark), MAX, {}, A),
>>>>> Aggregation((?mark), AVG, {}, A)
>>>>> )
>>>>> plus we rewrite the aggregates with aggi:
>>>>> SELECT ?agg1 (?agg2 AS ?max) (?agg3 AS ?avg)
>>>>> WHERE { ?name ex:mark ?mark } GROUP BY ?name
>>>>> We then translate the expressions:
>>>>> A=Extend(A, ?max, ?agg2)
>>>>> A=Extend(A, ?avg, ?agg3)
>>>>> Finally projection:
>>>>> Projcet(A, {?agg1, ?max, ?avg})
>>>>>
>>>>> Evaluation the BGP gives 4 solutions:
>>>>> mu1 : ?name -> ex:Birte, ?mark -> 4
>>>>> mu2 : ?name -> ex:Birte, ?mark -> 5
>>>>> mu3 : ?name -> ex:Steve, ?mark -> 3
>>>>> mu4 : ?name -> ex:Steve ?mark -> 5
>>>>> After grouping we get:
>>>>> { ex:Birte -> {mu1, mu2}, ex:Steve -> {mu3, mu4} }
>>>>> The three aggregates give
>>>>> SAMPLE: { (ex:Birte)->ex:Birte, (ex:Steve)->ex:Steve }
>>>>> MAX: { (ex:Birte)->5, (ex:Steve)->5 }
>>>>> AVG: { (ex:Birte)->4.5, (ex:Steve)->4 }
>>>>> Joining the aggregates gives 2 new solutions:
>>>>> mu_a: ?agg1->ex:Birte, ?agg2->5, ?agg3->4.5
>>>>> mu_b : ?agg1->ex:Steve, ?agg2->5, ?agg3->4
>>>>> We extend the solutions:
>>>>> mu_a' = mu_a union ?max->5, ?avg->4.5
>>>>> mu_b' = mu_a union ?max->5, ?avg->4
>>>>> Project then throws out ?agg2 and ?agg3 and we are done.
>>>>>
>>>>> We have, however, ?agg1 instead of ?name and if we had used HAVING
>>>>> with some condition on ?name we would have a problem.
>>>>>
>>>>> Do I do something wrong here or do we indeed have ?agg1 in the result
>>>>> and ?name got lost?
>>>>>
>>>>> Birte
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> The way the document is structured moves these apart in an unfortunate
>>>>>> way.
>>>>>>
>>>>>> - Steve
>>>>>>
>>>>>>>
>>>>>>> How about having two loops
>>>>>>> For each aggregate (X(args ; scalarvals) AS var) 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
>>>>>>> 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(var; scalarvals) with (aggi AS var) in Q
>>>>>>> i := i + 1
>>>>>>> End
>>>>>>>
>>>>>>> This way, we never have an illegal syntax form, we guarantee that all
>>>>>>> variables are still available after the aggregation and since AS is
>>>>>>> only processed later all seems to be fine. One could of course think
>>>>>>> about handling both cases in one loop although for the spec having two
>>>>>>> loops seems fine to me.
>>>>>>>
>>>>>>> Birte
>>>>>>>
>>>>>>>> - 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
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> 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
>>
>>
>
>
>
> --
> 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 Tuesday, 22 November 2011 20:38:31 UTC