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: Eric Prud'hommeaux <eric@w3.org>
Date: Wed, 25 Mar 2015 10:12:18 -0400
To: "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
Cc: RDF Data Shapes Working Group <public-data-shapes-wg@w3.org>
Message-ID: <20150325141216.GA13412@w3.org>
* 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.


> 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?


> peter
> 
> 
> On 03/25/2015 12:02 AM, Eric Prud'hommeaux wrote:
> > * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-03-24
> > 15:28-0700]
> >> I don't think that the fix is to add extra explanation here.
> >> 
> >> Based on my analyses, the problem is with two of the three formal 
> >> specification of Shape Expressions. Any implementation of either of
> >> these two specifications is going to be problematic. Based on a bit of
> >> testing it appears that the Fancy ShEx Demo is based on an
> >> implementation of the axiomatic semantics.
> > 
> > If the goal is to match the users' expectations, I would expect that 
> > exploring all possible models would do that. For instance, if we say ex:b
> > matches <T> iff ex:c fails <T> ex:c matches <T> iff ex:b fails <T> ,
> > we've covered the possible solutions. An alternative is to say that ex:b
> > matches <T> ex:c matches <T> because they don't pass in all models. By
> > tracking the node/shape pairs involved in a particular solution, I think
> > we can cheaply explore the permutations of A iff !B. If this doesn't
> > appeal, what do you propose is a good answer to your dilema?
> > 

-- 
-ericP

office: +1.617.599.3509
mobile: +33.6.80.80.35.59

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.

There are subtle nuances encoded in font variation and clever layout
which can only be seen by printing this message on high-clay paper.
Received on Wednesday, 25 March 2015 14:12:21 UTC

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