W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > July to September 2007

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 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:37 GMT