Re: Improving EXISTS

On 06/30/2016 04:50 AM, Axel Polleres wrote:
> Dear Andy,
> 
> sure, happy to join. I have to admit that I am still unsure whether there is really a *bug* in the specification (in the sense that it would be something that could be fixed by an erratum), or whether just what 
> the spec describes something in an unambiguous way, but it is just not what people would expect (which indeed would need if we wanted to propose an alternative to change/re-spec). 
> 
> I have to admit I couldn't follow the whole discussion but is there a mail/link which summarizes the issues (I am aware of the bnode injection issue, which more there are?) 
> 
> Thanks & best regards,
> Axel

Hi Axel:

I don't think that there is an email that is exactly what you asked for so I
have tried to put together a simple list of problems with EXISTS.  The first
two problems are directly problems with the spec.  The last three are cases
where the spec produces what can be considered to be counterintuitive results
and some implementations diverge from the spec.


Problem 1: Some uses of EXISTS are undefined

exists is only defined for graph patterns, but in
  SELECT ?x WHERE {
    ?x :p :c .
    FILTER EXISTS { SELECT ?y { ?y :q :c . } } }
the argument to exists ends up being a ToMultiSet, which is not listed under
"Graph Pattern" in the table of SPARQL algebra symbols.


Problem 2: Substitution happens where definitions are only for variables

In
  SELECT ?x WHERE {
    BIND ( :d AS ?x )
    FILTER EXISTS { SELECT ?x { :b :p :c } } }
the substitute ends up producing
  ToMultiSet(Project(ToList(BGP( :b :p :c )),{:d}))
However Project is only defined for variables in its second argument.

This also affects Extend, multisets, BOUND, and maybe other constructs.


Problem 3: Blank nodes substituted into BGPs act as variables

In
  SELECT ?x WHERE {
    ?x :p :d .
    FILTER EXISTS { ?x :q :b . } }
against the graph { _:c :p :d , :e :q :b }
the substitute ends up producing
  BGP(_:c :q :b)
when then matches against :e :q :b.

This is counterintuitive.  Some implementations diverge from the spec here.


Problem 4: Substitution can flip MINUS to its disjoint case

In
  SELECT ?x WHERE {
    ?x :p :c .
    FILTER EXISTS { ?x :p :c . MINUS { ?x :p :c . } } }
against the graph { :d :p :c } the substitute ends up producing
  Minus( BGP( :d :p :c ), BGP( :d :p :c ) )
which produces a non-empty result.

This is counterintuitive.  Some implementations diverge from the spec here.


Problem 5: Substitution affects disconnected variables

In
  SELECT ?x WHERE {
    BIND ( :d AS ?x )
    FILTER EXISTS { BIND ( :e AS ?z )
                    SELECT ?y WHERE { ?x :p :c } } }
the substitute ends up producing
  Join ( Extend( Z, ?z :e ),
         ToMultiSet( Project( ToList( BGP( :d :p :c ) ), {?y} ) ) )

This may be counterintuitive.  Some, but not all, implementations diverge
from the spec here.

Received on Thursday, 30 June 2016 13:06:02 UTC