Re: problem with blank nodes in EXISTS solution mappings

On 06/16/2016 03:44 PM, Gregory Williams wrote:
> On Jun 16, 2016, at 3:38 PM, Peter F. Patel-Schneider
<pfpschneider@gmail.com> wrote:
>>
>> The definition of EXISTS in SPARQL 1.1 Query uses the substitute function.
>> There are multiple problems with substitute already reported.  Here is
>> another one.
>>
>>
>> Consider
>>
>> SELECT ?x WHERE {
>>  :s :p ?x .
>>  FILTER EXISTS { ?x :p ?y . }
>> }
>>
>> on the graph
>>
>> :s :p _:x .
>>
>> The EXISTS gets { { (x,_:x) } } and then does a substitute which results in
>>  BGP( _:x :p ?y )
>> This has a solution of
>>  { { (y,:x) } }
>> because the blank node that is the mapping of x can itself be further mapped
>> to :s in the RDF instance mapping part of a pattern instance mapping.
>
> Peter,
>
> Can you expand on why you believe "the blank node that is the mapping of x
> can itself be further mapped to :s”? I’m not sure I follow.
>
> thanks,
> .greg


>From https://www.w3.org/TR/sparql11-query/#BasicGraphPattern

18.3.1 SPARQL Basic Graph Pattern Matching

A basic graph pattern is matched against the active graph for that part of
the query. Basic graph patterns can be instantiated by replacing both
variables and blank nodes by terms, giving two notions of instance. Blank
nodes are replaced using an RDF instance mapping, σ, from blank nodes to RDF
terms; variables are replaced by a solution mapping from query variables to
RDF terms.  Definition: Pattern Instance Mapping

A Pattern Instance Mapping, P, is the combination of an RDF instance
mapping, σ, and solution mapping, μ. P(x) = μ(σ(x))

For a BGP 'x', P(x) denotes the result of replacing blank nodes b in x for
which σ is defined with σ(b) and all variables v in x for which μ is defined
with μ(v).

Any pattern instance mapping defines a unique solution mapping and a unique
RDF instance mapping obtained by restricting it to query variables and blank
nodes respectively.  Definition: Basic Graph Pattern Matching

Let BGP be a basic graph pattern and let G be an RDF graph.

μ is a solution for BGP from G when there is a pattern instance mapping P
such that P(BGP) is a subgraph of G and μ is the restriction of P to the
query variables in BGP.


>From https://www.w3.org/TR/rdf11-mt/#notation-and-terminology

Suppose that M is a functional mapping from a set of blank nodes to some set
of literals, blank nodes and IRIs. Any graph obtained from a graph G by
replacing some or all of the blank nodes N in G by M(N) is an instance of
G. Any graph is an instance of itself, an instance of an instance of G is an
instance of G, and if H is an instance of G then every triple in H is an
instance of at least one triple in G.


So consider
  BGP( _:x :p ?y )
against the active graph G = { :s :p _:x . }

The RDF instance mapping is σ = { ( _:x, :s ) }.
The solution mapping is μ = { ( y, _:x ) }.
The pattern instance mapping is P = { ( _:x, :s ), ( y, _:x ) }.
This is a solution because P( _:x :p ?y ) = (:s :p _:x) which is a subgraph
of G.

The point is that the _:x that came from the EXISTS substitution is a blank
node and can be itself substituted for in the RDF instance mapping.  This is
counter to what I think is the desired meaning for EXISTS.

Note that this is all just a little bit sloppy.  To make it all precise
would require an extra injection from blank node names to real blank nodes
but this extra precision doesn't make any difference here.

Peter F. Patel-Schneider
Nuance Communications

Received on Thursday, 16 June 2016 23:32:56 UTC