Re: formal objection to advancing to candidate recommendation status

> On Mar 24, 2017, at 9:18 AM, Irene Polikoff <irene@topquadrant.com> wrote:
>
> Peter,
>
> In order to make sure the WG clearly understands your objection, let me
>ask you the following questions.
>
> Your objection is based on the following 5 problems you have identified
>for SPARQL EXISTS. Correct?

Not correct.  I have identified several problems with the proposed definiton
of pre-binding.  This definition is largely taken from a proposal for
solving deficiencies of the current definition for EXISTS in SPARQL.  Some
of the problems with the definition of pre-binding are also problems with
the proposal for SPARQL EXISTS but some are for pre-binding only.

>> 1. The proposed definition of EXISTS depends on a mapping that replaces local
>>> variables in a SPARQL algebra expression.  This mapping is defined for all
>>> SPARQL algebra expressions except for projections.  Pre-binding is thus
>>> undefined on any query of the form SELECT $this ?value WHERE { ... }  and
>>> indeed on any SELECT query with no DISTINCT or REDUCED keyword.  This
>>> problem was reported to the working group in
>>> https://lists.w3.org/Archives/Public/public-rdf-shapes/2017Mar/0022.html
>
> Your example above appears to be wrong as per point 2 - as it binds
>>$this. Nevertheless, issues with mapping have been resolved based on your
>>own proposal.
>
> Please clarify what problems remain.

Binding this in the top-level SELECT is allowed in pre-binding, even when
this is pre-bound.  In fact, there are examples in the SHACL document that
do precisely this.

The problem is that a SELECT query without DISTINCT or REDUCED becomes a
projection in the SPARQL algebra.  This cannot happen for SPARQL EXISTS so
it is not a problem there even though projection was excluded from the
domain of PrjMap.

>> 2. Another problem affects SPARQL queries using AS.  Here the problem involves
>>> the Extend operator in the SPARQL algebra.  For example, the query
>>>  SELECT DISTINCT ?this WHERE { BIND ( ex:a AS ?this ) }
>>> with the variable this pre-bound results in an undefined use of Extend.
>>> This problem was reported to the SPARQL EXISTS Community Group in
>>> https://lists.w3.org/Archives/Public/public-sparql-exists/2017Mar/0000.html
>
> This issue has been responded to on the EXISTS mailing list
> https://lists.w3.org/Archives/Public/public-sparql-exists/2017Mar/0009.html

I believe that the message above indicates that point 1, which I had
initially thought was also a problem for EXISTS, isn't because the argument
cannot be a projection.

> It is an illegal query. And you said in the referenced e-mail that
> “perhaps, there is no problem”. Do you have another example of a problem?

This is not an illegal query for pre-binding.  Pre-binding is defined for
any SPARQL query.  Evaluting this query with ?this pre-bound results in an
undefined use of EXTEND.

>> 3. Another problem is that sometimes the proposal for pre-binding doesn't
>>> actually use the bindings.  For example,
>>>  SELECT DISTINCT $this WHERE { VALUES $this { ex:a ex:b ex:c } }
>>> with the variable this pre-bound to ex:d returns three solution bindings,
>>> one each with the variable this mapped to ex:a, ex:b, and ex:c, ignoring the
>>> pre-binding of the variable this.  This problem was reported to the SPARQL
>>> EXISTS Community Group in
>>> https://lists.w3.org/Archives/Public/public-sparql-exists/2017Mar/0001.html
>
> We do not see this as a problem. Nevertheless, it has been addressed.
>
> What is remaining?

How has this been addressed?  The problem here is that there is no place for
Replace to add in the values of variables from outside the filter resulting
in counter-intuitive results.

>> 4. Yet another problem with the definition of pre-binding involves an
>>> unintuitive result.  One might expect that
>>>  SELECT DISTINCT ?this WHERE { ex:a ex:b ex:c . MINUS { ex:a ex:b ex:c . } }
>>> with ?this pre-bound would produce some results because there is no variable
>>> shared between the left-hand and right-hand sides of the MINUS.  However,
>>> pre-binding introduces a binding for the variable this on both sides so
>>> no results are produced.  This problem was reported to the SPARQL EXISTS
>>> Community Group quite some time ago.
>
> The SPARQL EXISTS Community Group has already noted that MINUS is a
> problem in the current SPARQL 1.1 specification : see Issue 4. Some
> changes in the evaluation of MINUS are therefore to be expected. Use cases
> are used to understand the impact of such changes. In case of SHACL,
> pre-binding is for patterns that involve the use of ?this. Thus, we see
> this example as somewhat artificial and without practical relevance for
> SHACL.
>
> Issue 4:
>
https://w3c.github.io/sparql-exists/docs/sparql-exists.html#issue-4-substitution-can-flip-minus-to-its-disjoint-domain-case

Pre-binding is defined over all SPARQL queries.  Some uses of MINUS inside
EXISTS are problematic in the current SPARQL specification.  The query here
does not involve EXISTS at all so it is not problematic in the current
SPARQL specification.  Even if this use of MINUS was inside an EXISTS it
would still not be problematic in the current SPARQL specification.
However, this use of MINUS is newly problematic for pre-binding because of
the counter-intuitive result.

>> 5. There is also a potential problem with the definition of pre-binding as it
>>> depends on replacing variables in SPARQL queries with arbitrary new (fresh)
>>> variables.  As variable names do show up in SPARQL results, it should be
>>> demonstrated that this replacement does not affect the result of a SPARQL
>>> query.  I expect that this is indeed the case, but there is no demonstration
>>> of it in the SHACL document.  This problem was reported to the working group
>>> in https://lists.w3.org/Archives/Public/public-rdf-shapes/2017Mar/0009.html
>
> As we understand it, the problem has not been identified. There is no
> example or any other evidence of the problem. it is just that there is no
> mathematical proof that the problem does not exist. Correct?

The proposal for pre-binding adds a new kind of operation to SPARQL,
replacing a variable with a fresh variable.  This replacement can happen in
just about any SPARQL construct and context.  There is no demonstration in
the SHACL document that this replacement is well behaved.  I don't think
that it is acceptable to add this new kind of operation without some
demonstration of its suitability.

> The EXISTS document has some explanatory verbiage. It is not clear to us
> how to identify the basis on which the satisfactory proof could be built.
> Since you are the person who needs to be satisfied, the WG is ready to
> work with you on this after the CR transition - if you are willing to do
> so. In the absence of your willingness, we do not see a practical way in
> which a proof you'd find satisfactory could be produced.

The part of the EXISTS document that is used in SHACL is no more than a
proposal for a possible new definition of EXISTS in SPARQL.  There is no
consensus for it within the SPARQL EXISTS community group.  It is not a
proposal for pre-binding and indeed its use in pre-binding has opened up new
problems.

I have been working with the proposer to examine the replacement with fresh
variables and we have come to the conclusion that it is probable that this
part of the proposal is not problematic.  I have only been able to find one
SPARQL SERVICE (the Wikidata label service) where this replacement will
cause problems, but the service is not compliant with the definition of
SPARQL.

There is some wording in the EXISTS document that provides the basis of a
demonstration to the effect that the replacement with fresh variables is not
problematic.  However, this wording is not to be found in the SPARQL
document.

This new technology needs to be carefully and widely examined to ensure that
it does not cause problems.  So far only two people have looked at it at
all.

Peter F. Patel-Schneider
Nuance Communications



>>> Begin forwarded message:
>>>
>>> From: "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
>>> Subject: formal objection to advancing to candidate recommendation status
>>> Date: March 22, 2017 at 8:13:42 PM EDT
>>> To: "public-rdf-shapes@w3.org" <public-rdf-shapes@w3.org>
>>> Resent-From: public-rdf-shapes@w3.org
>>>
>>> This is a formal objection to the resolution of the RDF Data Shapes Working
>>> Group to advance the maturity level of https://www.w3.org/TR/shacl/ to
>>> Candidate Recommendation using the editors' draft at
>>> http://w3c.github.io/data-shapes/shacl/ as of 22 March 2017.  The reason for
>>> this objection is that a fundamental part of SHACL, pre-binding, still has
>>> significant known problems.  Problems with pre-binding have been known to
>>> the working group since at least June of 2015.  A summary of some current
>>> known problems with pre-binding is given at the end of this message.
>>>
>>> This objection is being filed at this time because pre-binding has been
>>> undergoing recent change and its known problems might have been fixed before
>>> requesting advancement for the document.
>>>
>>> Pre-binding is so central to the SPARQL extension mechanism for SHACL,
>>> SHACL-SPARQL, that any significant problem with pre-binding undermines the
>>> entirety of SHACL-SPARQL.  Pre-binding is also a central part of
>>> non-normative descriptions of targets and constraints in SHACL Core so
>>> problems with pre-binding also affect the rest of the SHACL document.
>>>
>>> The working group could have removed pre-binding from the document by
>>> splitting it into two pieces, one for SHACL Core and one for SHACL-SPARQL,
>>> and only advancing the SHACL Core piece.  This possibility had been
>>> discussed several times in the working group when there was more than
>>> adequate time to perform the split.
>>>
>>> So, in summary, as of 22 March 2017 pre-binding underpins a large part of
>>> SHACL and has several known problems which affect the definition of SHACL.
>>> The SHACL document should not advance to candidate recommendation until
>>> these problems are fixed or pre-binding is eliminated from the document.
>>>
>>> Peter F. Patel-Schneider
>>> Nuance Communications
>>>
>>>
>>>
>>> A summary of some known problems with pre-binding in SHACL:
>>>
>>> The current definition of pre-binding in SHACL is adapted from a proposed
>>> fix for SPARQL EXISTS, first appearing in
>>> https://lists.w3.org/Archives/Public/public-sparql-exists/2016Sep/0024.html
>>> Its current version is in a proposed editor's draft at
>>> https://w3c.github.io/sparql-exists/docs/sparql-exists.html
>>> The current adaptation of this proposal for pre-binding is at
>>> http://w3c.github.io/data-shapes/shacl/#pre-binding.
>>>
>>> The proposal for EXISTS itself has several problems, and its adaptation for
>>> defining pre-binding has several more.  Some of these problems are minor and
>>> technical but some of them are quite major or affect a large number of
>>> SPARQL queries.
>>>
>>> The proposed definition of EXISTS depends on a mapping that replaces local
>>> variables in a SPARQL algebra expression.  This mapping is defined for all
>>> SPARQL algebra expressions except for projections.  Pre-binding is thus
>>> undefined on any query of the form SELECT $this ?value WHERE { ... }  and
>>> indeed on any SELECT query with no DISTINCT or REDUCED keyword.  This
>>> problem was reported to the working group in
>>> https://lists.w3.org/Archives/Public/public-rdf-shapes/2017Mar/0022.html
>>>
>>> Another problem affects SPARQL queries using AS.  Here the problem involves
>>> the Extend operator in the SPARQL algebra.  For example, the query
>>>  SELECT DISTINCT ?this WHERE { BIND ( ex:a AS ?this ) }
>>> with the variable this pre-bound results in an undefined use of Extend.
>>> This problem was reported to the SPARQL EXISTS Community Group in
>>> https://lists.w3.org/Archives/Public/public-sparql-exists/2017Mar/0000.html
>>>
>>> Another problem is that sometimes the proposal for pre-binding doesn't
>>> actually use the bindings.  For example,
>>>  SELECT DISTINCT $this WHERE { VALUES $this { ex:a ex:b ex:c } }
>>> with the variable this pre-bound to ex:d returns three solution bindings,
>>> one each with the variable this mapped to ex:a, ex:b, and ex:c, ignoring the
>>> pre-binding of the variable this.  This problem was reported to the SPARQL
>>> EXISTS Community Group in
>>> https://lists.w3.org/Archives/Public/public-sparql-exists/2017Mar/0001.html
>>>
>>> Yet another problem with the definition of pre-binding involves an
>>> unintuitive result.  One might expect that
>>>  SELECT DISTINCT ?this WHERE { ex:a ex:b ex:c . MINUS { ex:a ex:b ex:c . } }
>>> with ?this pre-bound would produce some results because there is no variable
>>> shared between the left-hand and right-hand sides of the MINUS.  However,
>>> pre-binding introduces a binding for the variable this on both sides so
>>> no results are produced.  This problem was reported to the SPARQL EXISTS
>>> Community Group quite some time ago.
>>>
>>> There is also a potential problem with the definition of pre-binding as it
>>> depends on replacing variables in SPARQL queries with arbitrary new (fresh)
>>> variables.  As variable names do show up in SPARQL results, it should be
>>> demonstrated that this replacement does not affect the result of a SPARQL
>>> query.  I expect that this is indeed the case, but there is no demonstration
>>> of it in the SHACL document.  This problem was reported to the working group
>>> in https://lists.w3.org/Archives/Public/public-rdf-shapes/2017Mar/0009.html
>>>
>>> The above are mostly problems about how pre-binding is defined.  Only when
>>> these problems are eliminated can the definition of pre-binding be examined
>>> to see whether it does some right thing as far as SHACL is concerned.
>>> Indeed, a previous definition of pre-binding in SHACL suffered from this
>>> sort of problem.
>>>
>>
>

Received on Thursday, 30 March 2017 14:24:22 UTC