Re: constructing the abstract structure from an OPTIONAL

Fred Zemke wrote:
> In my paper attached to 
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0170.html
> on page 15, I posed the question of how to interpret queries of the form
> { P1 } UNION {P2} OPTIONAL {P3}.
> I maintained that the first operand of OPTIONAL must be an
> empty pattern, based on BNF rule [20] GraphPattern, which
> shows that an OptionalGraphPattern is necessarily preceded by
> a FilteredBasicGraphPattern, which I took to be the first operand.
> In private communication Andy Seaborne pointed me to the SPARQLer validator
> at http://www.sparql.org/validator.html .
> Since Andy pointed me at it, I assume the group regards it as a guide for
> interpreting the draft.  So I played around with it.  My observation of
> its behavior is as follows:
> 
> 1. If an OPTIONAL is the very first token within a GroupGraphPattern,
> then an implicit empty FilteredBasicGraphPattern is taken as its
> first operand.

This is in rq23 as { {} OPTIONAL { P } }.  (and there is an editorial action 
to put in that {} is one result of no bindings.)

> 
> 2. Otherwise the GroupGraphPattern is of the form { GraphPattern }
> where the GraphPattern, according to rule [20], expands recursively
> into something of the form
> 
> Filtered1 NotTriples1 Filtered2 NotTriples2 ... Filteredn NotTriplesn
> 
> where Filteredi is a FilteredBasicGraphPattern and NotTriplesi is a
> GraphPatternNotTriples.  Let j be the subscript of the particular
> NotTriplesj that is the OptionalGraphPattern whose first operand is sought.
> There are two subcases:
> 
> a) Possibly Filteredj is not an empty pattern.  In that case, Filteredj
> is taken as the first operand of the OPTIONAL.
> 
> b) If Filteredj is the empty pattern, then note that j cannot be 1
> (otherwise rule 1 above would apply).
> Therefore NotTriples(j-1) exists, and if we examine the BNF
> for NotTriples, we see that it can never be an empty pattern. 
> So we take NotTriples(j-1) as the first operand of OPTIONAL.
> 
> Examples:
> 
> 1. WHERE { OPTIONAL { P1 } }
> 
> In this example, OPTIONAL is the first keyword within a GroupGraphPattern
> so rule 1 applies.
> 
> 2. WHERE { ?x ?y ?z OPTIONAL { P2 } }
> 
> In this example, the OPTIONAL is preceded by a non-empty
> FilteredBasicGraphPattern, which is the operand of the OPTIONAL
> by rule 2)a)
> 
> 3. WHERE { ?x ?y ?z { OPTIONAL { P2 } } }
> 
> This example nests the OPTIONAL inside of braces, making it the
> first token within a GroupGraphPattern.  Therefore its first operand
> is an implicit empty pattern.
> 
> 4. WHERE { {P1} UNION {P2} OPTIONAL {P3} }
> 
> In this example, the OPTIONAL is preceded by a NotTriples, the UNION.
> Therefore {P1} UNION {P2} is the first operand of OPTIONAL
> 
> 5. WHERE { {P1} UNION { {P2} OPTIONAL {P3} } }
> 
> This example shows how to use {} to regroup example 4, forcing
> {P2} as the operand of OPTIONAL, rather than the UNION.
> 
> Examples 4 and 5 show tricky cases.  Note that in 4, the use of
> rule 2)b) does not make {P2} the operand of OPTIONAL,
> because {P2} is nested within the NotTriple that is the UNION.
> 
> 6. WHERE { ?x ?y ?z OPTIONAL {P2} OPTIONAL {P3} }
> 
> The first operand of the first OPTIONAL is "?x ?y ?z".
> For the first operand of the second OPTIONAL, it is preceded
> by a NotTriple which is the first OPTIONAL.  So the
> first OPTIONAL is the first operand of the second OPTIONAL.
> 
> Can other people confirm or deny that I have correctly stated
> the intention?

It looks right.

I experimented by shuffling the grammar around and moving Optional into 
GraphPattern to see if that is clearer.

GroupGraphPattern ::=
   <LBRACE>
     GraphPattern
     (
       (  OptionalGraphPattern (<DOT>)?
       )+
       GraphPattern
     )?
   <RBRACE>

and taking Optional out of GraphPatternNotTriples.  Parses the same language 
(I reran the syntax tests on this variant).

It would make a slightly different abstract syntax tree but the same 
conceptual query because
   (Group A (Optional B C) )   # Prefix notation
has the same results as
   (Group (Optional {A B} C) )
by expanding out the definition of optional.  A and B not both 
FilteredGraphPatterns.  Which is a group of one item:
   (Optional {A B} C)
so implementations have choices in how they split parsing from internal 
representation of a query.

There are some other ways to express the binary nature of OPTIONAL that I'd 
like to try out including what I believe will give exactly the same AST at the 
expense of a slightly more complicated grammar.

	Andy

> 
> Fred
> 
> 
>

Received on Friday, 23 June 2006 14:10:34 UTC