W3C home > Mailing lists > Public > public-data-shapes-wg@w3.org > March 2015

Re: is there an implementation of Shape Expressions that correctly handles recursive shapes?

From: Iovka Boneva <iovka.boneva@univ-lille1.fr>
Date: Fri, 20 Mar 2015 16:42:10 +0100
Message-ID: <550C3FD2.4020306@univ-lille1.fr>
To: "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
CC: RDF Data Shapes Working Group <public-data-shapes-wg@w3.org>
We do have 3 implementations of recursive shapes with bag semantics, for 
2 different algorithms
- one for validating against deterministic schemas w/o repetitions, with 
a set of pre-typed root nodes. It is written in Java using jena, and 
works both with in-memory RDF-graphs, and using the Jena RDF-database 
API. Written by myself;
- one for the same algorithm written in Python also using RDF API, 
written by Slawek Staworko and Samuel Hym;
- one for validation of a whole graph w/o pre-typed root nodes, using 
our greatest fixed point algorithm. Also written in Python by Slawek and 

Our implementations were written for "proof of concept" prior to our 
We also have an algorithms for generating large graphs on which we 
tested our implementations, and they indeed ran in linear time in the 
size of the graph, as they were supposed to from theoretical point of view.


Le ven. 20 mars 2015 14:54:24 CET, Peter F. Patel-Schneider a écrit :
> Hash: SHA1
> I have been looking over recursive shapes in Shape Expressions. It appears
> to me that two of the three definitions for Shape Expressions are
> ill-founded on recursive shapes.
> I have also been trying to test out implementations of recursive shapes in
> Shape Expressions. There are five implementations of Shape Expressions
> listed on http://www.w3.org/2001/sw/wiki/ShEx
> Of these five
> the section on Fancy ShEx Demo has links to three online tools of 
> which the
> ShEx Demo appears to be the one to use to check out how Shape 
> Expressions work,
> the link for JSShexTest puts up a bare-bones online tool,
> the link for RDFShape does not produce any result,
> the link to ShExcala produces a page that points to RDFShape as its online
> tool, and
> the link to Haws produces a 404 error.
> I tried the following example of a recursive shape in all the ways that I
> could think of in the online tools:
> PREFIX ex: <http://ex.example/#>
> start = <S>
> <S> { ex:p @<T>* }
> <T> { ( ex:q @<Z> | ex:r @<T> ) }
> <Z> { }
> PREFIX ex: <http://ex.example/#>
> ex:a ex:p ex:b .
> ex:a ex:p ex:c .
> ex:b ex:q ex:z .
> ex:c ex:q ex:z .
> ex:b ex:r ex:c .
> ex:c ex:r ex:b .
> ShEx Demo (http://www.w3.org/2013/ShEx/FancyShExDemo) appears to go 
> into an
> infinite loop on this input.
> JSShexTest (http://www.jessevandam.nl/) very quickly produces
> Shex validation: Succes
> Result: FAIL
> which I read to mean that the validation failed, as expected. However, I
> was not sure so I dug further. The description of JSShexTest is 
> supposed to
> be in http://www.w3.org/2001/sw/wiki/ValidationCode. That page gives or as
> an inclusive or and not the exclusive or of Shape Expressions. Under this
> reading of or, it appears to me that the result should be a success, 
> but the
> documentation is too spotty for me to be sure of this.
> Is there an implementation of Shape Expressions that correctly handles
> recursive shapes?
> peter
> Version: GnuPG v1
> IrnjOQ+PdGRlmHUwDsifIM/lV1B8wyjU1kWIGm4JzYC5ZQanKAFzolQNWSZdXYOn
> YFlc2OjjTR5ilz4diH4FCCwJKclBTdZpQFS3dUUKKDzU9AWHQhdtzOVLwIhKxnou
> mmwnTldrPCY/QsXujpOAuhYdo9xbi8VY1Q9sQscsBpQCiisuyPD5VnLjcaICHWDP
> eEwgyVFGNGcgHLB2hnfkYVOxPTa/5JW7bFOPsnwPM6Wg3Ai+dAYLj3QioEPmJp4u
> FGy27J21UK2p5cD8X7qj1mJ40vocSQqgQB58sOeat98YPSguQXHU3BF7uoxs9Tk=
> =3Pgi

Iovka Boneva
Associate professor (MdC) Université de Lille
+33 6 95 75 70 25
Please note that I read my mails twice a day at 9:00 and 13:00 (CET)
For urgent matters, please contact me by phone
Received on Friday, 20 March 2015 15:42:53 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:30:18 UTC