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

Re: Translation to Algebra

From: Andy Seaborne <andy.seaborne@epimorphics.com>
Date: Mon, 17 Jan 2011 21:53:42 +0000
Message-ID: <4D34BA66.8040101@epimorphics.com>
To: Birte Glimm <birte.glimm@comlab.ox.ac.uk>
CC: SPARQL Working Group <public-rdf-dawg@w3.org>
On 17/01/11 18:44, Birte Glimm wrote:
> Hi all,
> I am just wondering how to interpret the not yet fully complete
> definition of the translation to the SPARQL algebra, but going back to
> the 1.0 spec also doesn't really help :-(
>
> I assume the query pattern
> { triple1 OPTIONAL { BGP } triple 2 }
> is ok according to the grammar.
>
> Now the question is whether optional applies to both triples or only
> to the first one. In the former case I would get:
> Join(LeftJoin(Bgp(triple1), Bgp(BGP), true), Bgp(triple2))
> whereas in the latter case it would be:
> LeftJoin(Join(Bgp(triple1), Bgp(triple2)), Bgp(BGP), true),
> both already with Z simplified away.
> I tend to assume the former since my understanding is that I work from
> left to right, but I couldn't see that from the spec (also the 1.0
> spec since this is not even 1.1 stuff and this bits in 1.1 are still
> not finalized at least according to the @@ marks in the relevant
> places)
>
> Similarly, I wonder how { triple1 {} triple2 } would be translated.
> triple1 {} triple2 is not a BGP/triples block (is it?), so I guess I
> would have use the description for GroupGraphPattern to translate the
> three elements. For the first element (triple1) that gives Join(Z,
> Bgp(triple1)), where I got Bgp(triple1) from Translate(triple1) where
> I treat triple1 as TriplesBlock. The next element is, however, the
> empty group, for which I also would have to obtain Translate({}), but
> now {} is not a TriplesBlock but a group, so I go back into the
> algorithm for GroupGraphPatterns, which again requires me to compute
> translate({}), etc. I think it is assumed that I implicitly take the
> elements out of the group to translate them, but then I have to
> explicitly do that for groups whereas I don't have to do it from
> things that are already just blocks of triples. Furthermore, it is not
> said AFAICT that in this case TriplesBlock translates into Z.
>
> I have to say that the triples that are not in a group give me a bit
> of a headache :-(
>
> Thanks for any clarification,
> Birte
>

Birte,

At
http://www.w3.org/TR/rdf-sparql-query/#convertGraphPattern
there isa a tranlsation step that goes:

"For each element E in the GroupGraphPattern"

GroupGraphPattern is the syntactic element between {} so

{ triple1 OPTIONAL { BGP } triple 2 }

is iterating over

triple1 OPTIONAL triple 2

(in syntax terms OPTIONAL is just a word followed by a {} in the 
abstract syntax tree - it hasn't become a binary operator yet).

Let G := the empty pattern Z

First time round loop:
E = triple1
G := Join(G, A)
=> we have join(Z , triple1)

Second time round loop:
E = OPTIONAL { BGP }
G := LeftJoin(G, A2, F)

=> we have LeftJoin(join(Z , triple1), OPTIONAL { BGP })

Third time round loop:
E = triple2
G := Join(G, A)
=> join(
       LeftJoin(join(Z , triple1), OPTIONAL { BGP })
       triple2)

Now for { triple1 {} triple2 }

3 syntax elements, only immediately adjacent triples become a BGP and so 
{} splits. {} is Z by recursion (it is a GroupGraphPattern of zero 
elements so it's Z and no time round the "E in the GroupGraphPattern" loop.

join( join( join(Z,triple1) , {}), triple2)

	Andy
Received on Monday, 17 January 2011 21:54:19 GMT

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