constructing the abstract structure from an OPTIONAL

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.

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?

Fred

Received on Friday, 23 June 2006 00:51:32 UTC