Re: Review SPARQL Query 1.1, Section 18 (algebra)

On 28 April 2011 12:52, Andy Seaborne <andy.seaborne@epimorphics.com> wrote:
> On 25/04/11 01:30, Birte Glimm wrote:
>>
>> Hi Andy, Steve, others,
>> I was asked to check whether the comments in my review have been
>> addressed. This seems mostly to be the case in particular for
>> aggregates I just found some minor typos or leftover from changes, but
>> I still have some problems outlined below. I didn't check the grammar
>> for PP expressions yet due to lack of time.
>> Birte
>>
>> Can we please have unified pseudo code?
>
>> If seems to be followed by Then, but not always. If mostly has an End,
>> but not always. Indentation (often for End is messed up and in some
>> cases the End appears in the wrong place.
>> E.g., pseudo code 18.2.2.5 Translate Graph Patterns
>> If… NO Then
>>   …
>> Else
>>   …
>> NO End
>> The next two blocks have If, NO Else, No End
>
> The forms should be If (Else)? End; the isea is to be cleare.  There may be
> variations.

"isea is to be cleare" ?

> The "If the form is" is following the style of text just above it which I
> think is clearer.
>
>> Next block has several version:
>> First If has no Then no End
>> Next If has Then on the next line, but has End
>> The If inside the above has no Then, lowercase else and an End.
>> The next Ifs are without Then, but with End
>> The for loop has an End, which possibly belongs to the first If.
>> The last If has no Then, but an End that is indented, but it shouldn't
>> be indented.
>>
> ...
>
>> 18.2.4.3 SELECT Expressions
>> pseudo code for Step: Select expressions
>>      E := E append (variable, expr)
>> is not indented enough, should have same level as
>>        P := P  union { variable }
>>
>> I can't/won't list everything, but think it would be good to decide on
>> a style and go once through the doc to unify everything.
>
> I have tried to clean up the algorithms - is there anywhere you thin is
> unclear?

I guess it's clear, I don't have the time to look over all the code
again. I did it twice already...

>> -----------------------
>> 18.2.2.3 Translate Basic Graph Patterns
>> After translating property paths, any adjacent triple patterns are
>> collectied together to form a basic graph pattern BGP(triples).
>> s/collectied/collected/
>
> Done
>
>> --------------------
>> There no longer is a definition of transform(.), before there was
>> Transform(syntax form), which was defined for most basic things
>> (GroupGraphPattern, GroupOrUnionGraphPattern, TriplesBlock).
>>
>> Transform(.) now falls from the sky first in 18.2.2.4 Translate
>> Pattens in Filters.
>
> Henny Penny is saved.

?

> I have added it back in at the start of 18.2.2
>
>> Section 18.2.2.5 Translate Graph Patterns contains what should make up
>> the definition of Transform(.).
>
>> --------------------
>> I am still not happy with the (NOT) EXISTS filters.
>
> I'm a bit lost as to which text you are referring to. 18.2.2.4? 18.5? Other?

I mean 18.5.

> I've changed 18.2.2.4 to:
>
> ...
> Replace EXISTS{P} by eval(D(G), exists(A))
> Replace NOT EXISTS{P} by fn:not(eval(D(G), exists(A))

Yes, I don't think that's a good solution. It kind of addresses the
problem, but eval really is a method that is called recursively. Here
you cannot really call it or I misunderstand the definition. You have
eval(D(G), exists(P)) = true if and only if eval(D(G),
substitute(pattern, μ)) is a non-empty sequence.
What is pattern there? Where does μ come from? As I understand the
basic idea of exists is that you first have to evaluate the pattern to
which the filter applies (?s :p ?o in my example below). From that you
get μ and only then you can evaluate the filter.

> Is that what you are suggesting?

Not really. I don't have a solution, but what is there doesn't really work IMO.

>> Here an example: query pattern is
>> { ?s :p ?o FILTER EXISTS { ?s p' ?o } }
>> I replace the EXISTS
>> { ?s :p ?o FILTER exists(Bgp(?s p' ?o)) }
>> and continue
>> Filter(exists(Bgp(?s :p' ?o)), Bgp(?s :p ?o)) (simplified already)
>> then evaluate

here comes the problem. I have to evaluate
>> eval(D(G), Filter(…))
so I go to the definition of filter evaluation (18.5), which tells me

eval(D(G), Filter(F, P)) = Filter(F, eval(D(G),P))

in my example that is:
>> = Filter(exists(…), Eval(D(G),Bgp(…)))

Now Filter(.) is define in 18.4
Filter(expr, Ω) = { μ | μ in Ω and expr(μ) is an expression that has an
          effective boolean value of true }

but in my example expr is actually exists(Bgp(?s :p' ?o)), and just
proceeding here as told doesn't really work.

I would rather need something like
Filter(expr, Ω) = { μ | μ in Ω and either
    (a) expr is exists(...) and eval(D(G), substitute(pattern, μ)) is
a non-empty sequence, or
    (b) expr(μ) is an expression that has an effective boolean value of true }

but even here, D(G) would normally have to be handed through and here
I don't have D(G) anymore. Maybe:
eval(D(G), Filter(F, P)) = Filter(F, eval(D(G),P), D(G))? (not so nice)
further, expr could be complex e.g., a conjunction of filters only one
of which is exists(...) then the above again doesn't work.

As I said already several weeks ago. I don't have a solution to this,
but I also don't see that the current spec handles the case properly.
Did I at least make the problem clearer?

Birte

>> assume the active graph has
>> :a :p :c .
>> :a :p' :c .
>> :b :p :c .
>> we get Sigma = { {?s->:a, ?o->:c}, {?s->b, ?o->:c} } for Bgp(?s :p' ?o)
>> Now we have
>> Filter(exists(Bgp(?s :p' ?o)), Sigma)
>> which apparently is as follows
>> Filter(expire, Sigma) = { mu | mu in Sigma and expr(mu) is an
>> expression that has an effective boolean value of true }
>> For exists I rather want mu(exists(…)) or exists(mu(Bgp(…))).
>> Even further, I would want
>> exists(eval(D(g), mu(Bgp(…))))
>> since there might be variables in Bgp(…) or whatever we have inside
>> the exists(…) that are not yet bound and we actually want to work with
>> the graph again here.
>
> ...
>
>        Thanks
>        Andy
>
>



-- 
Dr. Birte Glimm, Room 309
Computing Laboratory
Parks Road
Oxford
OX1 3QD
United Kingdom
+44 (0)1865 283520

Received on Thursday, 28 April 2011 21:59:06 UTC