# SPARQL Algebra Translation Bug

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Wed, 26 Sep 2007 18:00:45 +0100
Message-ID: <46FA903D.3050508@hp.com>
To: RDF Data Access Working Group <public-rdf-dawg@w3.org>

The translation from SPARQL syntax to SPARQL algebra:
http://www.w3.org/2001/sw/DataAccess/rq23/rq25.html#convertGraphPattern

has a bug in it : the tests and the doc (rq25) do not agree.  The test are right.

[[
If SA is of the form OPTIONAL(Filter(F, A))
G := LeftJoin(G, A, F)
]]

is the way that filters get into thte conditional part of the LeftJoin.

But the section
[[
If F is not empty:
If G = empty pattern then G := Filter(F, Z)
If G = LeftJoin(A1, A2, true) then G := LeftJoin(A1, A2, F)
If G = Join(A1, A2) then G := Filter(F, Join(A1, A2))
If G = Union(A1, A2) then G := Filter(F, Union(A1, A2))
If G = Graph(x, A) then G := Filter(F, Graph(x, A))
where x is a variable or IRI.
]]
has the error.  This gives a second way for filters to get into the condition
part of the LeftJoin.  This extra way shouldn't be there; it should be:

[[
If F is not empty:
G := Filter(F, G)
]]

7 tests that cover this:

optional/q-opt-complex-1.rq
optional-filter/expr-2.rq
optional-filter/expr-3.rq
open-world/open-eq-12.rq
boolean-effective-value/query-bev-5.rq
boolean-effective-value/query-bev-6.rq
bound/bound1.rq

(I got these by grep'ing the test suite and looing at the tests.  I double
checked by building modified versions of ARQ each way round to seeing the sam
7 test as failures when done the way the text is.)

To work through one in detail:
http://www.w3.org/2001/sw/DataAccess/tests/data-r2/optional-filter/expr-2.rq

==== expr-2.rq

PREFIX  dc: <http://purl.org/dc/elements/1.1/>
PREFIX  x: <http://example.org/ns#>
SELECT  ?title ?price
WHERE
{ ?book dc:title ?title .
OPTIONAL
{ ?book x:price ?price } .
FILTER (?price < 15)  .
}

==== expr-1.rq

PREFIX  dc: <http://purl.org/dc/elements/1.1/>
PREFIX  x: <http://example.org/ns#>
SELECT  ?title ?price
WHERE
{ ?book dc:title ?title .
OPTIONAL
{ ?book x:price ?price .
FILTER (?price < 15) .
} .
}

with the bug, the translation will produce the same algebra for expr-1 and
expr-2 because there are two different ways filters get into the 3rd argument
of the LeftJoin.

But the test results are not the same and the results for expr-2 agree with
the algebra expression:

(filter (< ?price 15)
(leftjoin
(BGP (triple ?book dc:title ?title))
(BGP (triple ?book x:price ?price))
))

and not that of expr-1:

(leftjoin
(BGP (triple ?book dc:title ?title))
(BGP (triple ?book x:price ?price))
(< ?price 15))

(Use of prefix notation here 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:09 UTC

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