Re: Tests: data-r2/algebra

Jeen Broekstra wrote:
 > Seaborne, Andy wrote:
 >
 >> Checked in:
 >>
 >> http://www.w3.org/2001/sw/DataAccess/tests/data-r2/algebra/
 >>
 >> 12 tests.
 >>
 >> These tests cover various issues to do with the SPARQL algebra, such as
 >> filter scopes, nested optionals, repeated optionals using the same
 >> variable.
 >>
 >> There may well be duplication with tests elsewhere but it's probably
 >> useful to have a set focused on algebra matters all in one place.
 >>
 >> This is not intended to be a complete coverage. If there are specific
 >> other areas for the algebra that people would like covered, please say
 >> so.  Or supply additional tests!
 >
 > I'm having difficulties with the first test, Nested Optionals 1.

http://www.w3.org/2001/sw/DataAccess/tests/data-r2/algebra/two-nested-opt.rq

 > Perhaps
 > I'm out of touch with how the behaviour of nested optionals is defined, but:
 >
 > data:
 >
 > :x1 :p 1 .
 > :x2 :p 2 .
 > :x3 :q 3 .
 > :x3 :q 4 .
 >
 > query:
 >
 > SELECT *
 > {
 >     :x1 :p ?v .
 >     OPTIONAL
 >     {
 >       :x3 :q ?w .
 >       OPTIONAL { :x2 :p ?v }
 >     }
 > }
 >
 > I would intuitively expect the result to be:
 >
 >  ?v ?w
 >   1  3
 >   1  4
 >
 > According to this test, however, the result is:
 >
 >  ?v ?w
 >   1  -
 >
 > I guess this has something to do with the pattern in the second optional
 > not matching due to ?v being bound to value 1. However, given that this
 > is an optional pattern I do not quite understand why it makes the
 > _first_ optional clause fail as well.
 >
 >
 > Jeen

Jeen Broekstra wrote:
> Jeen Broekstra wrote:
>> I'm having difficulties with the first test, Nested Optionals 1.
> 
> [snip]
> 
> Following up on myself here, I think that this has to do with the fact
> that the test query's graph pattern is not "well designed" (see Perez et
> al., section 4.2).
> 
> This leads to a difference in evaluation results between Sesame's query
> evaluation approach (which is depth-first) and the compositional
> approach (which is presumably what the algebra advocates).
> 
> It might be useful to document this somehow as there are bound to be
> other depth-first implementations out there that will fail these kinds
> of patterns.
> 
> Jeen

Yes - the query illustrates the difference between top-down and bottom-up 
evaluation.  It's the not "well designed" case.

The answers you got:

 > I would intuitively expect the result to be:
 >
 >  ?v ?w
 >   1  3
 >   1  4
 >
 > According to this test, however, the result is:
 >
 >  ?v ?w
 >   1  -

are the two sets for different evaluation approaches.

(The latter because ?v gets bound to 2 in the inner OPTIONAL which blocks the 
matching with ?v/1 from the outer basic graph pattern, hence blockign the 
OPTIONAL with ?w being matched.)

I had checked in something that approximates the top-down evaluation by 
rewriting the query:
http://www.w3.org/2001/sw/DataAccess/tests/data-r2/algebra/two-nested-opt-alt.rq

This isn't in the manifest.


How/where do you suggest documenting this?  It would be useful to record the 
fact that the test is specific to cover this case but, for implementers coming 
to SPARQL now, it's a merely historical detail and may even be confusing 
because it refers to something that isn't in the spec.

 Andy

-- 
Hewlett-Packard Limited
Registered Office: Cain Road, Bracknell, Berks RG12 1HN
Registered No: 690597 England

Received on Thursday, 14 June 2007 13:24:44 UTC