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: Peter F. Patel-Schneider <pfpschneider@gmail.com>
Date: Wed, 25 Mar 2015 07:40:02 -0700
Message-ID: <5512C8C2.3060800@gmail.com>
To: Eric Prud'hommeaux <eric@w3.org>
CC: RDF Data Shapes Working Group <public-data-shapes-wg@w3.org>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



On 03/25/2015 07:12 AM, Eric Prud'hommeaux wrote:
> * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-03-25 
> 03:08-0700]
>> Exploring all the possible models is potentially exponential in the 
>> size of the data graph.  Someone is going to have to come up with an 
>> optimized method for exploring this large space of options.
> 
> Yeah, there will always be an exponential component. My strategy has
> been to reset some of the cached values between validating one target
> and another, specifically those that were involved in a cycle.

I don't know whether this is adequate. I don't even know whether it will
produce the correct answers. Right now, the demo is producing incorrect
answers (i.e., reporting validations that are not supported by any model) in
some cases.

>> One way of overcoming the problems of recursive shapes is just to 
>> forbid them.  This is the solution that I currently prefer.
> 
> What about if we start with a semantics that forbids them in order to 
> find a common ground, and then the folks who want oneOf beat you up
> until you yield? Or maybe come up with a satisfactory semantics or rule
> some stuff out with prose?

Well, it's not the semantics that forbids things like this, it's the syntax.
In any case, the common ground that currently appears to be missing is what
sort of semantics is going to be used, and forbidding recursive shapes
doesn't affect that.


peter
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAEBAgAGBQJVEsjCAAoJECjN6+QThfjzrSUH/iR91GVVW9DpXTcD1B1tAmG0
PKjo7RxPx1Xn1zduhT2GXi50g+H3fZBMt9ia5dht0r5x8Kb8EcufBMl7UV2Odngk
RPcB8goIPGzvssQXerGJPD9mYY4hrfFuqB/q+LvxohFLar3ig5mCvhPM1CTAfBHY
R25YfrRr5QErw27T1BO/EQu5UjKI12fMgcYU0l4JUyvkE3jq0sd8pATMlXgqonSI
XhwtvG7+R4PZ+98NsaXyuaxV8S+rKcRskJTiWeQShAn0KqaRqh2p8aecUBDLvcSJ
EZImZsdzgiFwDvF+crLpyr2ejFzZeCXfoPrefa+eKdb0Fs4GAZitVbaBY8Y3QKw=
=sQ3i
-----END PGP SIGNATURE-----
Received on Wednesday, 25 March 2015 14:40:31 UTC

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