# Simplification step in the algebra translation

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Wed, 26 Sep 2007 18:01:32 +0100
Message-ID: <46FA906C.90709@hp.com>
To: RDF Data Access Working Group <public-rdf-dawg@w3.org>
```
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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 17:00:51 UTC