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 19:55:46 +0100
Message-ID: <550C6D32.2060107@univ-lille1.fr>
To: "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
CC: RDF Data Shapes Working Group <public-data-shapes-wg@w3.org>
I sent my previous mail by error before  finishing it...  so didn't have 
the occasion to say that unfortunately these  implementations are not 
accessible for testing. As I said they were made for our own needs as 
proof  of concept, and do not have friendly user interface.
I am however willing to send the API in a jar file, together with 
example code on how  to use it, if  somebody wants to play with that. 
Unfortunately next week I won't have time to do more (and anyway my 
technical skills are insufficient for publishing it for testing on the 
web, while spending a reasonable amount  of time on that).

My main point was that there are indeed working implementations with 
recursion.

Now to answer Peter's questions:
- the first algorithm is indeed for subclass of ShEx, which merely 
corresponds to the first version of ShEx (no repetition of symbols). It 
is however not so limiting, as it allows to handle a lot of the 
identified use cases, and can be easily extended for handling more 
cases,  as I already explained in a previous mail;
- the second one is for full ShEx,  (therefore its worse case complexity 
is not linear, and right  now I cannot give figures on its actual  
performance in practice).

Iovka




Le 20/03/2015 17:05, Peter F. Patel-Schneider a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/20/2015 08:42 AM, Iovka Boneva wrote:
>> 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;
> So this implementation is only for part of Shape Expressions?
>
>> - one for the same algorithm written in Python also using RDF API,
>> written by Slawek Staworko and Samuel Hym;
> And this implementation is also only for part of Shape Expressions?
>
>> - 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
>> Samuel.
> Does this implementation handle all of Shape Expressions?  Is there an
> on-line demo?  How can I get a copy of the system?
>
>> Our implementations were written for "proof of concept" prior to our
>> publication. 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.
>>
>> Iovka
>
> peter
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1
>
> iQEcBAEBAgAGBQJVDEVeAAoJECjN6+QThfjzS04H/3fibb1SUdlucX2MkTQ4iBFi
> kLMNHhJbYyLBWBMiVWAumRBynisyvRnLvUEe++ivqlajg+JzNQ+QZCjh5DgxxV1z
> GBA0vxdVYUcu81+Q91gn/OHtLgpcdS0kUX5yRkRpNBd9sYdcL7Qgp6jlWGaYULJU
> PWhjqGpDT9/XKCylRdetOWj8l24QQW5YGX9qYFacYwSxORl4WsDfeS54EhgzFDdM
> ik+BVeGy8rDXwT6l5HhApMcCbXPCiXlJ58FWbg5GzS+IjH34IoBHRFNp03vlNTcY
> tvrCHjhABHO6aKNR0VKhIz4n5Zft5i5kBUTxXTy+wtShBjfukknikzsTibbWuMY=
> =PUvz
> -----END PGP SIGNATURE-----
Received on Friday, 20 March 2015 18:56:17 UTC

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