Simplification step in the algebra translation

The text:

[[
A group pattern is mapped into the SPARQL algebra as follows: first, convert 
all elements making up the group into algebra expressions using *this* 
transformation process recursively, then apply the following transformation:
]]
(my emphasis)
is unclear as to what "this" is referring to.

It affects when the simplification rule is applied.  A query with double 
nesting in the OPTIONAL is affected.  I think this is the only case.  There 
are no tests in the test suite.

Example:

PREFIX : <http://example/>
SELECT *
{
   ?x :q ?v
     OPTIONAL
   { { ?x :p ?p . FILTER(?p < 4) } }
}

The key feature is the (at least) double {{}} in the optional.

What is not clear is whether the recursion is the whole process applied to the 
sub-expression, or whether each step is applied to the whole query 
exhaustively before moving on to the next step.  The test in step 1 says to 
apply it to the whole query but the quoted text from step 4 ("this 
transformation") can be taken to mean step 4 or the whole process.

Applying step 5 during a recursion of step 4 means that

{ ?x :p ?p . FILTER(?p < 4) }
   becomes
(filter (< ?q 34)
       (BGP (triple ?x :p ?q)))

then the { { ... } } becomes

(Join Z
     (filter (< ?q 34)
       (BGP (triple ?x :p ?q))))

but simplification (step 5) removes the "(Join Z ", where Z is the empty 
pattern (the join identity), leaving:

   (filter (< ?q 34)
     (BGP (triple ?x :p ?q)))

which is the same as if there were only one level of {}.  The filter is going 
to be lifted into the LeftJoin as it it were without the extra {}

The overall translation this way round is:

   (leftjoin
     (BGP (triple ?x :r ?y))
     (BGP (triple ?x :p ?q))
     (< ?q 34)))


Applying step 5 after the whole query means that

{ ?x :p ?p . FILTER(?p < 4) }

is remains
    (Join Z
         (filter (< ?q 34)
            (BGP (triple ?x :r ?y))
when step 4 is applied for the OPTIONAL and the filter is not lifted into the 
LeftJoin.

The overall translation is now

   (leftjoin
     (BGP (triple ?x :r ?y))
     (filter (< ?q 34)
       (BGP (triple ?x :p ?q))
     true))

with the filter being strictly on the basic graph pattern inside the LeftJoins 
second argument which is the right hand side of the LeftJoin.

I produced versions of ARQ that did the transformation in either order and all 
tests pass in either way round - there is no use of OPTIONAL {{ }}.

(Use of prefix notation because I semi-mechanically produced the examples)

 Andy

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

Received on Wednesday, 26 September 2007 17:01:53 UTC