- From: Seaborne, Andy <andy.seaborne@hp.com>
- Date: Fri, 23 Jun 2006 15:10:17 +0100
- To: Fred Zemke <fred.zemke@oracle.com>
- CC: public-rdf-dawg@w3.org

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