Interpretation of BNODE under subquery

[jitsedesmet]

I was recently playing around with the BNODE function and I think the SPARQL spec is not very clear on the behaviour of the BNODE function (1.2)wrapped in subqueries.
It states that every solution mapping will generate distinct blanknodes, similar to the behaviour of blanknodes within the construct template.

Constructs a blank node that is distinct from all blank nodes in the dataset being queried and distinct from all blank nodes created by calls to this constructor for other query solutions.

The following query, however, is interesting:

SELECT * WHERE {
  {SELECT ?x1 ?x2 WHERE { ?x1 ?p ?o BIND(BNODE("a") AS ?x2) } LIMIT 2}
  {SELECT ?x1 ?x3 WHERE { ?x1 ?p ?o BIND(BNODE("a") AS ?x3) } LIMIT 2}
}

The interpretation of the spec is quite special looking at some common query engines qlever Comunica
Both generate distinct blank nodes but only in the context of a single subquery, the generated blank nodes are however 'accidentally' the same for both subqueries and therefore you get the result:

?x2	?x3
_:a1	_:a1
_:a1	_:a2
_:a2	_:a1
_:a2	_:a2

Blazegraph, on the other hand, generates the same blank node constantly (which is definitely wrong?)

I think the spec would benefit on adding something allowing the lines of:

Constructs a blank node that is distinct from all blank nodes in the dataset being queried and distinct from all blank nodes created by calls to this constructor for other query solutions, even accross subqueries.

Since I assume this is the correct interpretation, as the spec really tries to make you generate distinct blanknodes?
For the other interpretation, I had a conversation with @rubensworks, but he will be able to explain it best.

[rubensworks]

To add to @jitsedesmet's findings, I think the issue here is this part of the text in the spec:

every call results in distinct blank nodes for different simple literals

This "every call" part implicitly refers to a certain context, but what context this is, is not precisely defined.
It could mean:

1. every call that's ever done across the lifetime of a query engine,
2. every call across all possible query engines in the world,
3. every call within the current query (from a top-down query perspective = scope of the top-level query when there are sub-queries), or
4. every call within the current query (from a bottom-up query perspective = scope of leaves when there are sub-queries).

It looks like QLever and Comunica both went for option 4, while the other options seem equally valid, but produce different results.

[afs]

BNODE::

If the form with a simple literal is used, every call results in distinct blank nodes for different simple literals, and the same blank node for calls with the same simple literal within expressions for one solution mapping.

A "solution mapping" here is the context (current row) in which the BNODE("a") is called. (I thought there was an errata about his wording but I can't find it.)

I think the spec would benefit on adding something allowing the lines of:

Constructs a blank node that is distinct from all blank nodes in the dataset being queried and distinct from all blank nodes created by calls to this constructor for other query solutions, even accross subqueries.

Since I assume this is the correct interpretation, as the spec really tries to make you generate distinct blanknodes?

Something along those lines would be good. "sub-queries" exist in syntax. The nearest name at evaluation time is "query level"
https://www.w3.org/TR/sparql12-query/#idp2427544 which is for discussing and has no representation in the algebra.

In the algebra, there is no mark for a "subquery" or a "level", just operations.

A query is a tree of "query levels", where each subquery forms one query level in the tree.

(sub-query link to the description of the syntax)

What about

SELECT * WHERE {
  { BIND(BNODE("a") AS ?x) }
  UNION
  { BIND(BNODE("a") AS ?y) }
}

or

SELECT * WHERE {
  { SELECT * { BIND(BNODE("a") AS ?x) } } # No-op SELECT *
  UNION
  { BIND(BNODE("a") AS ?y) }
}

which have the same algebra.

[hartig]

I think the first two sentence of the paragraph can be rewritten as follows:

The BNODE function constructs a blank node that is distinct from all blank nodes in the dataset being queried.
If the no argument form is used, every call to this constructor within the context of executing a query (including potential subqueries) results in a distinct blank node, distinct not only from the blank nodes in the dataset being queried but also from the blank nodes created by other calls to this constructor within the context of the query.

The third sentence (about the form with a string literal) is a bit more tricky. Just to clarify, that sentence ends with: "... within expressions for one solution mapping." Does this really mean that, for different solution mappings, BNODE("a") is supposed to produce different blank nodes? For instance, given the data

:s :p :o1 .
:s :p :o2 .

the query

SELECT ?b1 ?b2 WHERE {
  :s :p ?v
  BIND(BNODE("a") AS ?b1)
  BIND(BNODE("a") AS ?b2)
}

is supposed to result in something like

?b1	?b2
_:x	_:x
_:y	_:y

?

[afs]

Does this really mean that, for different solution mappings, BNODE("a") is supposed to produce different blank nodes? For instance, given the data

:s :p :o1 .
:s :p :o2 .
the query

SELECT ?b1 ?b2 WHERE {
:s :p ?v
BIND(BNODE("a") AS ?b1)
BIND(BNODE("a") AS ?b2)
}
is supposed to result in something like

?b1 ?b2
_:x _:x
_:y _:y
?

Yes. Like CONSTRUCT.

[jitsedesmet]

From @hartig 's reply:

distinct not only from the blank nodes in the dataset being queried but also from the blank nodes created by other calls to this constructor within the context of the query.

I think just specifying 'the query' leaves interpretations open between cases 3 and 4 of #292 (comment) ?

[kasei]

I also remember this coming up as (I thought) an erratum, but not sure what happened with that. I think the language around identity of solution mappings could be improved here, because it's clear different people understand "one solution mapping" (or "same solution mapping") differently.

Yes. Like CONSTRUCT.

The spec text uses union syntax for both Extend and Join (via merge):

Extend(μ, var, expr) = μ ∪ { (var,value) | var not in dom(μ) and value = expr(μ) }
Extend(μ, var, expr) = μ if var not in dom(μ) and expr(μ) is an error

If μ1 and μ2 are compatible then μ1 ∪ μ2 is also a mapping. Write merge(μ1, μ2) for μ1 ∪ μ2

I would have thought the "one solution mapping" becomes a different mapping after a join, but it's not clear to me how to reconcile that with the idea that Extend doesn't cause an identity change to that "one solution mapping".

[hartig]

From @hartig 's reply:

distinct not only from the blank nodes in the dataset being queried but also from the blank nodes created by other calls to this constructor within the context of the query.

I think just specifying 'the query' leaves interpretations open between cases 3 and 4 of #292 (comment) ?

We can add

".. (including potential subqueries)."

at the end of the sentence. I was assuming that this is implicit because that's already mentioned in the first part of that sentence (which you have excluded from your quote).

[jitsedesmet]

Oh sorry @hartig , seems like that sentence was already too long for me to read correctly 😅 .

I will give another try, only modifying the first sentence:

The BNODE function constructs a blank node that is distinct not only from the blank nodes in the dataset being queried but also distinct from blank nodes created during the evaluation of the query (including potential subqueries) in another solution mappings.

Unchanged:

If the no argument form is used, every call results in a distinct blank node.
If the form with a simple literal is used, every call results in distinct blank nodes for different simple literals, and the same blank node for calls with the same simple literal within expressions for one solution mapping.

However, @afs , can we understand from your comment that the use of the term 'subquery' is not preferable?

[hartig]

@jitsedesmet that rephrasing of the first sentence is good. But I would still integrate: "... created by other calls to this constructor during ..."

So, the sentence as a whole becomes:

The BNODE function constructs a blank node that is distinct not only from the blank nodes in the dataset being queried but also distinct from blank nodes created by other calls to this constructor during the evaluation of the query (including potential subqueries).

---

However, @afs , can we understand from your comment that the use of the term 'subquery' is not preferable?

I didn't read it that way. I think it is okay to use the term in this context here.

[jitsedesmet]

@hartig Using your latest proposal would not cover the case of the bnode function where a literal would be provided (Unless I am mistaken?). If you would still want to clarify the complete uniqueness of the case with no arguments, maybe we can do:

The BNODE function constructs a blank node that is distinct not only from the blank nodes in the dataset being queried, but also distinct from blank nodes created during the evaluation of the query (including potential subqueries) in other solution mappings. If the no argument form is used, every call results in a blank node distinct from those in the dataset and distinct from blank nodes created by evaluating this constructor. If the form with a simple literal is used, every call results in distinct blank nodes for different simple literals, and the same blank node for calls with the same simple literal within expressions for one solution mapping.

I think that the added scope of subqueries in the first sentence is enough to clarify the function? The part added (in bold) in the second sentence is optional from a spec perspective (I think) , but highlights the distinctiveness of the blanknodes generated by bnode in relation to each other?

[hartig]

@jitsedesmet Okay. Yet, the problem of what "one solution mapping" is is still unsolved.

In the context of my example above, for me, the solution mapping

    μ = { ?v → :o1, ?b1 → _:x }

that would be produced after the first BIND clause (and, thus, is input to the second BIND clause) is not the same as the solution mapping

    μ' = { ?v → :o1, ?b1 → _:x, ?b2 → _:x }

that would come out of the second BIND clause. This is not "one solution mapping" to me.

[TallTed]

>One A few tweaks to the sentence the paragraph, to make the distinct phrases agree:

The BNODE function constructs a blank node that is not only distinct from the blank nodes in the dataset being queried but also distinct from blank nodes created by other calls to this constructor during the evaluation of the query (including potential subqueries).

The BNODE function constructs a blank node that is not only distinct from the blank nodes in the dataset being queried, but also distinct from blank nodes created during the evaluation of the query (including potential subqueries) in other solution mappings. If the form with no arguments is used, every call results in a blank node distinct from those in the dataset and distinct from blank nodes created by evaluating this constructor. If the form with a simple literal is used, every call results in a distinct blank node for each different simple literal, and the same blank node for calls with the same simple literal within expressions for one solution mapping.

I will of course also review whatever PR eventually answers this Issue.

[jitsedesmet]

I think the version of @TallTed address the issue I wanted to raise.
Nevertheless, I understand the need to more specifically define 'solution mapping' for the 3th sentence, as raised by @hartig.

The definition of solution mapping does indeed seem too broad for how it is used here since one could indeed interpret the solution mapping coming out of the first extend as different from the solution mapping coming out of the second extend. (Repeating here to validate I understand correctly)

Maybe we can solve our issue by talking about the solution mapping of the current query level?

I try starting from TallTed's definition:

The BNODE function constructs a blank node that is not only distinct from the blank nodes in the dataset being queried, but also distinct from blank nodes created during the evaluation of the query (including potential subqueries) in other solution mappings. If the form with no arguments is used, every call results in a blank node distinct from those in the dataset and distinct from blank nodes created by evaluating this constructor. If the form with a simple literal is used, every call results in a distinct blank node for each different simple literal, and the same blank node for calls with the same simple literal within expressions for one solution mapping of the current query level.

I think the query level does not need to be mentioned in the first sentence because the definition still stands without it and because the first sentence is already complex.

[hartig]

The definition of solution mapping does indeed seem too broad for how it is used here [...]

I would rather say too narrow ;-)

Maybe we can solve our issue by talking about the solution mapping of the current query level?

I try starting from TallTed's definition:

[...] within expressions for one solution mapping of the current query level.

The solution mappings μ = { ?v → :o1, ?b1 → _:x } and μ' = { ?v → :o1, ?b1 → _:x, ?b2 → _:x } (in my previous comment) are still two different solution mappings, not one.

It actually becomes more complicated: Let's change the order of things within the group graph pattern of my previous example query as follows.

SELECT ?b1 ?b2 WHERE {
  BIND(BNODE("a") AS ?b1)
  :s :p ?v
  BIND(BNODE("a") AS ?b2)
}

In this case, the solution mapping that comes out of the first BIND clause is μ = { ?b1 → _:x }. Next, this solution mapping is joined with the result of evaluating the triple pattern. If the queried graph consists of two triples:

:s :p :o1 .
:s :p :o2 .

then this join results in two solution mappings:
  μ1 = { ?b1 → _:x, ?v → :o1 } and μ2 = { ?b1 → _:x, ?v → :o2 }
These two solution mappings are the input to the second BIND clause, and they are clearly different. Should the query result still be as follows??

?b1	?b2
_:x	_:x
_:x	_:x

(What would our lives be without the continuous joy of talking about blank nodes :)