Re: another problem with Proposal B

My understanding of the translation to the SPARQL algebra of
SELECT ?this WHERE {
  ?this a ex:good .
  FILTER EXISTS { { SELECT * WHERE { } }
                  BIND ( ?this AS ?that )
                  ?that a ex:bad } }
is as follows.

This is a SELECT expression, so look at 18.2.4.4 which (implicitly) says to
first translate the pattern.

  So translate
  { ?this a ex:good .
    FILTER EXISTS { { SELECT * WHERE { } }
                  BIND ( ?this AS ?that )
                  ?that a ex:bad } }

  This is a group graph pattern with a triple pattern and a filter.

  From 18.2.2.2 the filter is extracted and translated, with the EXISTS
  construct inside the filter translated.

    So translate
    { { SELECT * WHERE { } }
                  BIND ( ?this AS ?that )
                  ?that a ex:bad } }

    This is a group graph pattern with a group graph pattern, a bind, and a
    triple pattern.

    From the part of 18.2.2.6 on group graph patterns the translation
    proceeds by first setting G = Z

    Then the group graph pattern is "any other form" so translate it.

      Translate { SELECT * WHERE { } }
      This gets to the part of 18.2.2.6 on group graph patterns, setting G = Z
      Then translate SELECT * WHERE { }
      ends up as Project(Z,{}))
      and then ToMultiset(Project(Z,{}))

    So G = Join(Z,ToMultiset(Project(Z,{})))
    Now 18.2.2.8 simplifies this to G = ToMultiset(Project(Z,{}))

    Then the BIND is processed resulting in
    G = Extend(ToMultiset(Project(Z,{})),that,?this)

    Then the triple pattern is processed.
    From 18.2.2.5 the triple pattern is translated into a BGP, becoming
    something like BGP ( ?that rdf:type ex:bad . ) which is then added,
    resulting in
    G = Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that rdf:type
ex:bad .))

    [Maybe simplification happens now but the result is the same.]

  So the filter becomes
    exists(Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that
rdf:type ex:bad .)))
  and is remembered for later.

  Then the group graph pattern portion of 18.2.2.6 proceeds by first setting G = Z

  Then the triple pattern is procesed, first from 18.2.2.5 being is
  translated into a BGP, becoming something like BGP( ?this rdf:type ex:good . )
  and then G = Join(Z,BGP( ?this rdf:type ex:good . ))

  Filter addition from 18.2.2.7 results in
  Filter( exists(Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that
rdf:type ex:bad .))),
     Join(Z,BGP( ?this rdf:type ex:good . )) )

  Simplification from 18.2.28 results in
  Filter( exists(Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that
rdf:type ex:bad .)))
     BGP( ?this rdf:type ex:good . ) )

Finally back to 18.2.4.4 for the outer SELECT to get PV = { this }

Then on to 18.2.5 and 18.2.5.2 to get the final result of translation

Project(
  ToList(
    Filter( exists(Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that
rdf:type ex:bad .))) ,
         BGP( ?this rdf:type ex:good . ) ) ),
  {this} )

This is then evaluated.  The evaluation of the exists does a
Replace(PrjMap(
    Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that rdf:type
ex:bad .))),
  { (this, ex:i) } )
which becomes
Replace(Join(Extend(ToMultiset(Project(Z,{})),that,?this),BGP(?that rdf:type
ex:bad .)),
        { (this, ex:i) } )
and then
Join(Extend(ToMultiset(Project(Join(Z,{{(this,ex:i)}},{}))),that,?this),
     Join(BGP(?that rdf:type ex:bad .),{{(this,ex:i)}}))
and then
Join(Extend({{}},that,?this),
     Join(BGP(?that rdf:type ex:bad .),{{(this,ex:i)}}))
and then
Join(BGP(?that rdf:type ex:bad .),{{(this,ex:i)}}))
so the connection between ?this and ?that is broken.


So simplification happened in two places, removing a Join(Z,...) just
outside of the ToMultiSet and another around the outer BGP.  The latter
simplification is benign for Proposal B as the outer BGP is still there.
However, the former simplification ends up with the Extend not seeing any
value for the variable this which is a problem.

peter




On 04/21/2017 12:55 PM, Andy Seaborne wrote:
> 
> 
> On 18/04/17 19:24, Peter F. Patel-Schneider wrote:
>> [Second half only.]
>>
>>>> SELECT ?this WHERE {
>>>>   ?this a ex:good .
>>>>   FILTER EXISTS { { SELECT * WHERE { } }
>>>>                   BIND ( ?this AS ?that )
>>>>                   ?that a ex:bad } }
>>>>
>>>> peter
>>>>
>>>
>>> Simplification applies after syntax parsing, before evaluation.
>>>
>>> Inner "SELECT * {}" is a project of no variables of the unit table which is
>>> left as-is.  So no simplification.
>>>
>>> 18.2.4.4
>>> "The set PV is used later for projection."
>>>
>>> 18.2.5.2 Projection
>>> """
>>> The set of projection variables, PV, was calculated in the processing of
>>> SELECT expressions.
>>>
>>>     M := Project(M, PV)
>>> """
>>>
>>> There is something to account for in SELECT * but it's not simplification.
>>>
>>>     Andy
>>
>>
>> As far as I can tell the inner select is translated (see last example in
>> 18.2.3) as
>>   ToMultiSet(Project(Z,{}))
>>
>> The argument to EXISTS is translated (19.2.2.6) as
>>   Join( Extend(Join(Z,ToMultiSet(Project(Z,{}))),?that,?this),
>>         BGP(?that rdf:type ex:bad )
>>
>> Simplification (18.2.2.8) then results in
>>   Join( Extend(ToMultiSet(Project(Z,{})),?that,?this),
>>         BGP(?that rdf:type ex:bad) )
> 
> and the Z is not in a join.
> 
>>
>> So the EXISTS is translated to
>>   exists(
>>     Join( Extend(ToMultiSet(Project(Z,{})),?that,?this),
>>           BGP(?that rdf:type ex:bad) ) )
>>
>> Evaluation of the EXISTS with ?this mapped to ex:i proceeds by first doing
>> the replacement, which ends up with something like
>>   Join( Extend(ToMultiSet(Project(Join(Z,{{?this,ex:i}}),{})),?that,?this),
>                                         ^^^
> Simplification happened after the query was parsed, as the algebra was created
> and does not apply again during evaluation.
> 
> It should be that
> 
> project -> {{?this,ex:i}}
> 
> except for the issue noted about "SELECT *"
> 
> then BIND ( ?this AS ?that ) happens.
> then join with BGP(?that rdf:type ex:bad)
> 
>>         Join(BGP(?that rdf:type ex:bad),{{?this,ex:i}}) )
>> This is evaluated to
>>   Join( Extend({{}},?that,?this),
>>         Join(BGP(?that rdf:type ex:bad),{{?this,ex:i}}) )
>> and then to
>>   Join( {{}},
>>         Join(BGP(?that rdf:type ex:bad),{{?this,ex:i}}) )
>>
>> The BIND then ends up not having any effect because ?this doesn't have a
>> binding when it is evaluated, due simplification removing the place where
>> the FILTER variables might have been joined in.
> 
> I don't see where such a simplification is happening.
> It's the fact SELECT * is calculated without regard to the current row.
> 
> When "SELECT *" includes ?this, the inner BGP has the current row added.
> 
> "SELECT * {}" does not have a join.
> 
>>
>> peter
>>
> 
> (prefix ((: <http://example/>)
>          (rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>))
>   (project (?this)
>     (filter (exists
>                (join
>                  (extend ((?that ?this))
>                    (project {}
>                      (table unit)))
>                  (bgp (triple ?that rdf:type <::ex:bad>))))
>       (bgp (triple ?this rdf:type <::ex:good>)))))
> 
> for the EXISTS part:
> 
> (join
>   (extend ((?that ?this))
>     (project {}
>       (table unit))
>   (bgp (triple ?that rdf:type <::ex:bad>))
> )
> 
> BIND extends the graph pattern (syntactically - it's gathered up in
> syntax->algebra) before it.

Received on Friday, 21 April 2017 23:22:56 UTC