Re: Translation to Algebra

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


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:
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 })

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)


Received on Monday, 17 January 2011 21:54:19 UTC