Re: SPARQL EXISTS variations

Hi Peter,

On Mon, 2025-08-25 at 15:37 -0400, Peter F. Patel-Schneider wrote:
> Also mostly to EXISTS TF members:
>
> As far as I can tell, all that is required to do values injection (of any
> kind) is to have the (set of) injected binding set(s) incorporated into the
> result of the first construct of the translation of a GroupGraphPattern.  Once
> that is done the (set of) binding set(s) are available throughout the
> translation of the GroupGraphPattern.  So why not do this instead of having
> the (set of) injected binding set(s) joined into each BGP?

In principles, yes! However, I don't think it is possible to do that purely during the evaluation part of the
definitions because, at this point, it is not clear anymore which of the sub-expressions of the given algebraic query
expression has been such a "first construct of the translation of a GroupGraphPattern." To be able to do that, a special
marker needs to be added when constructing the algebraic query expression, as you propose below...

> This might be easier to understand [...]
>
> Further, given that the translation of GroupGraphPattern (before
> simplification) always starts with a placeholder empty basic graph pattern it
> would be possible to replace this pattern with a special construct that
> instead of just producing a single empty binding set instead produced the (set
> of) injected binding set(s).

That's indeed an alternative approach to define the DEEP INJECTION variations in the spec. It requires:

1. adding a new form of algebraic query expression [1], say "InjectContextMapping()" (without any argument),

2. using that form to initialize G in the algorithm for translating GroupGraphPattern [2] (instead of an empty BGP),

3. adding a case for this form to the definitions of the eval function in Section 18.6.2 [3]:

     eval( D(G), InsertContextMapping(), μ_ctx ) = { μ_ctx },

4. defining expr(μ, D, G) or expr(μ, D, G, Ω_ctx) as proposed in my document.

Notice that, for this approach, it is also necessary to extend the signature of the eval function as done by the
approach in my document (namely, by adding μ_ctx as an additional argument to the eval function), and to extend all
cases of the definitions of the eval function in Section 18.6.2 [3] such that μ_ctx is passed around (as illustrated in
the definition of the evaluation of Filter in my document [4]).

In the end, this approach affects more parts of the spec than the approach in my document. I think that both approaches
are equivalent in their effect (i.e., for every query and every dataset, the query result defined by both approaches is
the same). But perhaps you are right, this approach "might be easier to understand than having the values injection
potentially affect multiple components of the translation of GroupGraphPattern."

-Olaf

[1] https://www.w3.org/TR/sparql12-query/#defn_AlgebraicQueryExpression

[2] https://www.w3.org/TR/sparql12-query/#sparqlTranslateGraphPatterns

[3] https://www.w3.org/TR/sparql12-query/#sparqlAlgebraEval

[4]
https://github.com/w3c/sparql-query/blob/main/discussion/Defining_the_DEEP_INJECTION_approach_for_EXISTS.md#definition-evaluation-of-filter-semantics-deep-injection-and-once-without-projection



> 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://gist.github.com/hartig/3fffc7a02f3e0411158298e313b4c9c2

> >
> > 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://github.com/w3c/sparql-query/pull/270

> >
> >
> > 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://gist.github.com/hartig/3fffc7a02f3e0411158298e313b4c9c2
> > >
> > >
> > > 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://dydra.com/

> > > > >
> > > > >
> > > > >
> > > >
> > >
> >
>
>

Received on Tuesday, 26 August 2025 06:49:13 UTC