Re: on lists

Hi Jeremy,

On 18/10/2016 2:39, Jeremy J Carroll wrote:
>
> Hi Holger
>
> on your historical issue:
>
>
>> On Oct 15, 2016, at 8:57 PM, Holger Knublauch <holger@topquadrant.com 
>> <mailto:holger@topquadrant.com>> wrote:
>>
>> It is a bit surprising that there doesn't seem to be a standard 
>> definition of what a well-formed rdf:List is.
>
>
> Back in 2004 time-frame, the RDF group felt that it was out of scope 
> because the ‘obvious’ constraints were simply not the sort of complex 
> syntactical constraint at a graph level that the group felt were in 
> scope for that group.
> If when you merge graphs, apply inferences, etc etc you get an 
> ill-formed list, what do you do?
> i.e. the RDF Core WG was aware of the problem of ill-formed lists and 
> made an explicit decision that it was not within the focus of the work
>
> On the other hand, the OWL WG, were schizophrenic, with the DL/Lite 
> versions simply regarding the triples as a projection of the real OWL 
> syntax: in this projection all lists are well formed, but you cannot 
> use rdf lists as a general data structure.
> In OWL Full, OTOH, constraints are expressed semantically not 
> syntactically, and so the well-formedness constraint for RDF lists was 
> once again out of scope.

Thanks for your helpful background!

>
> It seems to me that this constraint is one of many potential high 
> level syntactic constraints on RDF triples expressing data structures, 
> and I am pleased to see that it is noted as in-scope for the shapes group:
>
> https://www.w3.org/TR/2015/WD-shacl-ucr-20150414/#uc26-rdf-lists-and-ordered-data
>
> This, to me at least, seems to be the appropriate level at which to 
> fix this long-standanding problem.

I have just used this opportunity to try and implement the use case 
above in SHACL. I ran into a problem. My current draft for such a 
ListShape is:


dash:ListShape
   rdf:type sh:Shape ;
   rdfs:comment "Defines constraints on what it means for a node to be a 
well-formed RDF list." ;
   rdfs:label "List shape" ;
   sh:or (
       [
         sh:hasValue () ;
         sh:property [
             sh:predicate rdf:first ;
             sh:maxCount 0 ;
           ] ;
         sh:property [
             sh:predicate rdf:rest ;
             sh:maxCount 0 ;
           ] ;
       ]
       [
         sh:not [
             sh:hasValue () ;
           ] ;
         sh:property [
             sh:predicate rdf:first ;
             sh:maxCount 1 ;
             sh:minCount 1 ;
           ] ;
         sh:property [
             sh:predicate rdf:rest ;
             sh:maxCount 1 ;
             sh:minCount 1 ;
             sh:shape dash:ListShape ;
           ] ;
         sh:property [
             dash:nonRecursive "true"^^xsd:boolean ;
             sh:path [
                 sh:oneOrMorePath rdf:rest ;
               ] ;
           ] ;
       ]
     ) .

(Note this uses dash:nonRecursive [1] which could alternatively be 
expressed with a sh:sparql constraint).

So either the list must be rdf:nil, and not have any rdf:first and 
rdf:rest, or it must not be rdf:nil and have rdf:first and rdf:rest plus 
rdf:rest must again be a well-formed list. And no cycles in the path 
rdf:rest+.

The problem - maybe someone has a better solution for this - is that the 
values of rdf:rest must recursively be well-formed rdf:List nodes. I 
have expressed this via sh:shape dash:ListShape. However, SHACL does not 
prescribe how to handle recursion, so some implementations may not be 
able to handle this scenario. In fact, my own implementation currently 
just throws a Failure when it encounters calls of sh:hasShape with the 
same argument combination, while other implementations may accept the 
recursion and only report the violation of the rdf:rest+ recursion.

I am hopefully missing something, but I don't see how to implement Use 
Case 26 with the current definition of SHACL. Maybe there is a solution 
using SPARQL paths, but that would be quite ugly. Expressing Use Case 26 
isn't a strict requirement, just a nice-to-have. Yet this makes it 
problematic to put something like a SHACL-based formal definition of 
well-formed lists into the SHACL document. It may also open yet another 
can of worms because such things are difficult to get right, covered 
with tests etc. A textual definition may be the best thing we can do, 
also in the short time frame that we currently have.

Cheers,
Holger

[1] http://datashapes.org/constraints.html#NonRecursiveConstraintComponent