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

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

From: Birte Glimm <birte.glimm@comlab.ox.ac.uk>
Date: Mon, 25 Apr 2011 01:30:01 +0100
Message-ID: <BANLkTi=vimf3N2xE_zTsbCqGAzMJgzZ4+w@mail.gmail.com>
To: Andy Seaborne <andy.seaborne@epimorphics.com>, Steve Harris <steve.harris@garlik.com>
Cc: SPARQL Working Group <public-rdf-dawg@w3.org>
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.

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 Translate Graph Patterns
If… NO Then
NO End
The next two blocks have If, NO Else, No End
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. Grouping and Aggregation
pseudo code for Step: Aggregates
End in first If clause is indented, but shouldn't be.  The if clause
has no Else although the next one has an Else.
The  End at the end of the third for loop belongs to the If clause
after the first For I assume since that If misses its End and The for
loops don't seem to use End or there would be several Ends missing. 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.
----------------------- Translate Basic Graph Patterns
After translating property paths, any adjacent triple patterns are
collectied together to form a basic graph pattern BGP(triples).
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 Translate
Pattens in Filters.
Section Translate Graph Patterns contains what should make up
the definition of Transform(.).
I am still not happy with the (NOT) EXISTS filters.
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
eval(D(G), Filter(…))
= Filter(exists(…), Eval(D(G),Bgp(…)))
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.
Definition: Evaluation of Group
eval(D(G), Group(exprlist, Ω)) = Group(exprlist, eval(D(G), Ω))
Using Ω here is confusing. In fact you have an algebra expression
there that has to be evaluated so that you can apply the Group
Definition: Evaluation of Group
eval(D(G), Group(exprlist, P)) = Group(exprlist, eval(D(G), P))

Definition: Evaluation of AggregateJoin
Write A = (A1, A2, ...) where Ai = Aggregation(exprListi, funci, scalarvarsi, P)
eval(D(G), AggregateJoin(A, P))
should be
eval(D(G), AggregateJoin(A)) P has been removed, is in each A_i

On 21 March 2011 10:50, Andy Seaborne <andy.seaborne@epimorphics.com> wrote:
> On 15/03/11 00:34, Birte Glimm wrote:
>> 18.6
>> The overall SPARQL design can be used for queries which assume a more
>> elaborate form of entailment than simple entailment, by re-writing the
>> matching conditions for basic graph patterns.
>> This is no longer true due to PPEs. I am not happy about this at all
>> and I assumed that PPEs are optional features. If they are not, it is
>> quite unfortunate that the so far existing extension point no longer
>> really is one and something has to be done at least to clarify this!
> Property paths are handled by maximising the rewrites to other SPARQL forms,
> including BGPs, and introducing new SPARQL algebra operators only where
> necessary.
> Therefore, evaluation of property paths does reduce to algebra+BGPs, just
> like any SPARQL query pattern.
> Would it be useful for the entailment document to discuss the issue that the
> property path syntax is compiled to SPARQL algebra forms.  It would be
> useful to discuss the relationship of applications-defined relationships
> (which is what property paths do - give the application writer a chance to
> express complex relationships such as transitivity) and the ontology-defined
> relationships that manifest via entailment. This might include limitations
> on the patterns in the syntax although that weakens the expressivity
> otherwise given to the application query writer.
>        Andy

Dr. Birte Glimm, Room 309
Computing Laboratory
Parks Road
United Kingdom
+44 (0)1865 283520
Received on Monday, 25 April 2011 00:30:29 GMT

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