Re: EXISTS : ways forward

On 09/23/2016 01:10 AM, james anderson wrote:> good morning;
>
> > On 2016-09-22, at 18:19, Peter F. Patel-Schneider <pfpschneider@gmail.com>
wrote:
> >
> > On 09/22/2016 05:07 AM, james anderson wrote:
> >> good afternoon;
> >>
> >>> On 2016-09-22, at 13:46, Andy Seaborne <andy@apache.org
> >>> <mailto:andy@apache.org>> wrote:
> >>>
> >>> […]
> >>>
> >>> There is a 3rd way which is to truly have bindings of variables as an
> >>> initial set.  Restrict the range of values at the point a variable in bound.
> >>> i.e. in the BGP and any AS usage (noting that BIND(... AS ?VAR) and ?VAR in
> >>> a earlier/deeper BGP is already illegal in SPARQL generally but not if ?VAR
> >>> is not in-scope at the point of BIND).
> >>
> >> this is the (kind of) semantics which is entailed by the simple goal, to have
> >> an exists definition which aims to be consistent with the remainder of the
> >> language.
> >
> > I don't understand what you mean by "consistent with the remainder of the
> > language”.
>
> that the definition is in terms of values from the language data model, not
> from its concrete syntax and that the definition follows established scoping
> rules or defines addition rules consistent with those which exist.

Well, the current definition of EXISTS certainly does not follow the scoping
rules in SPARQL.  That, I agree, is one of its problems.  However, the
approach outlined by Andy can easily have problems of its own.  There is no
more requirement that the rules for this kind of approach abide by the
scoping rules of SPARQL than there is for the kind of approach in the
current definition of EXISTS.

> >> it is straight-forward to define and realize this goal, if the semantics is
> >> sited at the correct level of interpretation - that is in the abstract
> >> algebra, rather than as a demonstration, that some things can never work, if
> >> attempted on the basis of the surface syntax.
> >
> > The definition of EXISTS actually works in the SPARQL algebra, not in the
> > surface syntax.
>
> if the proposed, problematic definition were not in terms of the surface
> syntax, there would be no problem with blank nodes and one would not
> conceive of substituting for symbols which bind variables rather than those
> which reference them only.

Not at all.

First, it is very common to define complex languages (e.g., the SPARQL
surface syntax) in terms of simpler languages (e.g., the SPARQL algebra).
In many cases (e.g., many logical formalisms) the simpler language is a
limited form of the surface syntax (e.g., the logic without disjunction and
existential quanification).  This amounts to saying that some constructs of
the language can be defined as macros over the rest of the language.  One
benefit of either transformational approach is that the fundamental bits of
the definition do not have to be repeated in several variations.  There is
absolutely nothing wrong in defining languages in this way.

So there is no fundamental problem with the transformational approach in
18.2.  As well, there is no serious problem with the specific transformation
for EXISTS given in 18.2.2.2.  (The problem, if it is a problem at all, is
that the EXISTS replacement in 18.2.2.2 will also replace EXISTS constructs
in interior FILTER expressions.  However, this does not cause anything to go
awry.)

The problem with EXISTS is in the definition of substitute in 18.6.

Substitute does perform substitution on patterns in the SPARQL algebra, and
these patterns can contain interior constraints that are still more or less
in the surface syntax of SPARQL.  It is true that EXISTS can go awry on
these interior constraints but this has nothing really to do with the fact
that these interior constraints are still more or less in the surface
syntax.

The problem with substitute is that it does a bunch of different bad things.
It replaces variables with graph terms in contexts in the SPARQL algebra
that can only take variables.  It replaces variables with graph terms in
contexts in the SPARQL algebra (inside MINUS) where this replacement
produces a meaning change.  It replaces variables with blank nodes in the
contexts in SPARQL algebra (inside BGPs) where this produces a meaning
change.  It replaces variables but does this wihtout consideration of
whether the occurence of the variable is connected to its own context.

It is true that non-local replacement is tricky.  (I seem to remember
reading that some early formalizations of predicate logic suffered from
variable capture, which is a problem that can arise in non-local
replacement.)  However, it is possible to usefully employ non-local
replacement in the definition of languages.

> best regards, from berlin,
> ---
> james anderson | james@dydra.com | http://dydra.com

Instead of arguing that an approach to defining EXISTS is bad or ugly, let's
instead try to come up with a definition of EXISTS that gives results that
we think are better.

peter

Received on Friday, 23 September 2016 21:45:48 UTC