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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 03/25/2015 07:53 AM, Eric Prud'hommeaux wrote:
> * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-03-25 
> 07:40-0700]
>> 
>> 
>> 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.
> 
> If you refer to the fact that some things say "assuming: " and nothing 
> afterwards, that list is the diffs from the model intersection (stuff 
> that's true in all models). (I've also just made that go away when the 
> list is empty.)

If the loops are of odd length, then no models are possible, but the system
reports answers, both positive and negative.

Consider for example,

PREFIX ex: <http://ex.example/#>
start = <S>
<S> { ( ex:p1 @<T> | ex:p2 @<T> ) }
<T> { ( ex:q @<Z> | ex:r @<T> ) }
<Z> { }

PREFIX ex: <http://ex.example/#>
ex:a ex:p1 ex:c .
ex:a ex:p2 ex:d .
ex:b ex:q ex:z .
ex:c ex:q ex:z .
ex:d ex:q ex:z .
ex:b ex:r ex:c .
ex:c ex:r ex:d .
ex:d ex:r ex:b .


>>>> 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.
> 
> Pure conjunction with no negation is adequately handled by assuming that 
> any cyclic passes, no?
> 
> schema: <S1> { :p1 @<S2> } <S2> { :p2 @<S1> }
> 
> data: :a :p1 :b . :b :p2 :c . :c :p1 :d . :d :p2 :a . <== here we've
> seen :a AS <S1> so we assume success.

Maybe. I would tend to lean in that direction.

peter


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

iQEcBAEBAgAGBQJVEtYEAAoJECjN6+QThfjzmMAH/3MfBaMgvOMbaLr/cJVcfUhd
Sl6p4LZXTqRKmH4kxGNlCtsZXokTA4tVGduFfMjd1i7mHX7b/yEnCSpXhOYyNzDo
HjgevUxu0rItpYQGusfeviJjzsgum8Gns5Czkodu33j3A9EbBrpshrrSaZLiMssr
iYVxtmjIXLeZEaO7P8TLmZmyPqANzDMjXAIhv0BBPjGAejm/tHzv8vA8kym/EApH
7xK8JBhMls+6Bl/Z5JJRoxodP3zPIw/sCUKoRcoIx84Qi43W8xt1t6u3/S++FzJE
4dJON7e7vHHOU4znn+Qe3XwcXfJ0wrMJIGdGWZxo1k/QwX4Slj1WnqxvQ99XKDc=
=cl6x
-----END PGP SIGNATURE-----

Received on Wednesday, 25 March 2015 15:37:05 UTC