Re: SPARQL EXISTS variations

Hi all,

As promised during the discussion last Friday about deep injection ONCE vs OVERALL,
I had a closer look at Olaf's formal definitions.

I currently prefer ONCE because it feels more intuitive to me, and it seems closer to the original descriptions in 1.1:

> Variables in the pattern that are bound in the current solution mapping take the value that they have from the solution mapping.

> ... given the solution mapping being tested by the filter operation.

Solution mapping is always mentioned here in singular form, so the SET OF solution mappings that would be considered in the OVERALL approach seems to go counter to that.

Performance-wise, I do not foresee a big difference in both. But I have no implementations to confirm this, so this is just a feeling.

That being said, this is not a strong preference, and I would also be open to OVERALL.

Kind regards,
Ruben Taelman



On 27 Aug 2025, at 18:07, Peter F. Patel-Schneider <pfpschneider@gmail.com> wrote:

I created https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fw3c%2Fsparql-query%2Fissues%2F275&data=05%7C02%7CRuben.Taelman%40ugent.be%7C9f96a3cb27e84ff8777c08dde583eb85%7Cd7811cdeecef496c8f91a1786241b99c%7C1%7C0%7C638919076932684561%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=Ax2LlRMGGhtcIFU0CHfQYNueUxW6BhUa7pjiRaQooic%3D&reserved=0 for the interaction between deep injection and SERVICE.

peter


On 8/27/25 2:28 AM, Olaf Hartig wrote:
Hi Peter,
Okay, if SERVICE cannot be supported in the way outlined in my document, do you have any other proposal how it can be
supported?
If we don't find a way, we may have to disallow SERVICE clauses inside the pattern of an EXISTS expression.
-Olaf
On Tue, 2025-08-26 at 14:20 -0400, Peter F. Patel-Schneider wrote:
The problem with BNODE() is that it is a different bnode that the one in the
binding set.  Admittedly, sending a bnode through a service request is a bit
tricky, but I imagine that there might be a reason in some cases to have bnode
identity survive the transition.

In any case, I don't believe that BIND can be used for the OVERALL case.

peter


On 8/26/25 3:10 AM, Olaf Hartig wrote:
On Mon, 2025-08-25 at 17:00 -0400, Peter F. Patel-Schneider wrote:
I believe that there is a problem with SERVICE constructs - you can't send the
binding sets to the remote service as a VALUES construct because you can't
send blank nodes correctly.

You are right, that is a problem.

An alternative to adding such VALUES clauses would be to add BIND clauses, one BIND clause per variable bound in
μ_ctx.
In this case, for each variable ?v ∈ dom(μ_ctx) for which μ_ctx(?v) is a blank node, the BIND clause would be:

  BIND( BNODE() AS ?v )

It is okay that these are fresh blank nodes because the blank nodes in μ_ctx would be disjoint from the blank nodes
at
the SPARQL endpoint anyways.

For the OVERALL variant, it would have to be a UNION of multiple blocks of BIND clauses, one block per solution
mapping
in Ω_ctx.

The only tricky bit is the case in which μ_ctx binds multiple variables to the *same* blank node; e.g., ?v1,?v2 ∈
dom(μ_ctx) such that μ_ctx(?v1) is the same blank node as μ_ctx(?v2). I am not sure how to solve that.

-Olaf


peter


On 8/24/25 2:54 PM, Olaf Hartig wrote:
Hi EXISTS TF members,

I have updated my document after last Friday's discussion.

https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgist.github.com%2Fhartig%2F3fffc7a02f3e0411158298e313b4c9c2&data=05%7C02%7CRuben.Taelman%40ugent.be%7C9f96a3cb27e84ff8777c08dde583eb85%7Cd7811cdeecef496c8f91a1786241b99c%7C1%7C0%7C638919076932736445%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=eOE%2BReY%2BIf4gLDp64bY8T3H7HWU03Lwn8CmMvhsrKkM%3D&reserved=0


Most importantly, I have added a detailed discussion of all cases
possible for the pattern within an EXISTS expression---see the section
called "Why is a similar change not needed for the other cases?"

I have also tried to add the document into the repo [1], but somehow
the CI run of the corresponding PR failed. Until this is fixed, the
link above is the most recent version of the document.

-Olaf

[1]
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fw3c%2Fsparql-query%2Fpull%2F270&data=05%7C02%7CRuben.Taelman%40ugent.be%7C9f96a3cb27e84ff8777c08dde583eb85%7Cd7811cdeecef496c8f91a1786241b99c%7C1%7C0%7C638919076932787821%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=MPOJBiEvdEVJs4cve8Czk4xC36PyMdNVfnVrJHCYisA%3D&reserved=0



On Fri, 2025-08-22 at 11:03 +0000, Olaf Hartig wrote:
Hi,

As the different variations were mentioned only informally in Peter's
email, I wanted to convince myself that we can
also define them formally in the spec. For the DEEP INJECTION
variations it was not immediately clear to me how this
could be done; especially not for the OVERALL-variant of DEEP
INJECTION.

I found a way to do it (based on an idea that Andy mentioned during
the last TF meeting), and wrote a short document to
describe the exact changes that are needed:

https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgist.github.com%2Fhartig%2F3fffc7a02f3e0411158298e313b4c9c2&data=05%7C02%7CRuben.Taelman%40ugent.be%7C9f96a3cb27e84ff8777c08dde583eb85%7Cd7811cdeecef496c8f91a1786241b99c%7C1%7C0%7C638919076932828074%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=UD1KA0sTMsxINuLF4J2ZzVyfhAfbNAd%2BdQZTRNWrQFU%3D&reserved=0



Best,
Olaf


On Thu, 2025-08-21 at 10:09 +0000, Olaf Hartig wrote:
On Thu, 2025-08-21 at 03:17 +0200, James Anderson wrote:
On 20. Aug 2025, at 22:30, Andy Seaborne <andy@apache.org> wrote:
On 16/08/2025 15:45, Peter F. Patel-Schneider wrote:
There was again discussion in the SPARQL EXISTS task force on
different solutions to the SPARQL EXISTS
problems.
The solutions amount to, roughly:
Simple LEFTJOIN, where no bindings from outside the EXISTS
affect the pattern inside.

SEMIJOIN?

is it not the case that, where no variable from the solution is
free in the exists pattern, that pattern reduces to
a
boolean constant value which depends only on the state of the
target graph?

What do you mean with a variable being "free in the exists
pattern"?

I agree with Andy, it is a SEMIJOIN.

@Peter, thanks for this great summary! I agree with your believe
that ONCE versus OVERALL is relevant only for DEEP
INJECTION.

-Olaf



Values injection at the beginning of the pattern (SHALLOW
INJECTION).
Values injection inside the pattern (DEEP INJECTION), with
two variations
values projected out in sub-SELECTs are not affected
(PROJECTION) and
values projected out in sub-SELECTs are affected.




---
james anderson | james@dydra.com |
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdydra.com%2F&data=05%7C02%7CRuben.Taelman%40ugent.be%7C9f96a3cb27e84ff8777c08dde583eb85%7Cd7811cdeecef496c8f91a1786241b99c%7C1%7C0%7C638919076932857472%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=BPdRQmb0%2F7c%2FVuEfyn7zjDHzI3oxDWmIm76eKXarUjc%3D&reserved=0