Re: recursive shapes in shape expressions

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

> In our ICDT 2015 paper we have defined fully declarative semantics for
> Shape Expressions, in which recursion is well defined, and does not
> represent any particular difficulty regarding semantics. 
> http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
> 
> To say it briefly, in our semantics, a 'valid typing' consists in 
> associating a set of shapes with every node, s.t. the constraints of all
> the shapes associated with all nodes are satisfied.
> 
> There may exist several valid typings. It is unavoidable, since shapes
> have been thought for validating starting from some selected root nodes,
> and it is obvious that depending on the root nodes and their required
> types, the final typings can differ.

I guess that you mean that if the typing is forced for some node, then the
typings of other nodes may be affected.

> We however show that there exists a *unique maximal valid typing*, that 
> associates to every node as many shapes as possible. Uniqueness is very 
> interesting property, as it allows to define the /coverage/ of a shape in
> a sound manner.

I didn't see a definition of coverage in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
I'm not even sure what coverage would mean.

> Note that there does not exist a *unique* minimal valid typing, but some
> minimal valid typing can be obtained in some situations, that we
> identify.

> Here are the valid shapes for your examples, with our semantics.
> 
> Le sam. 21 févr. 2015 23:27:52 CET, Peter F. Patel-Schneider a écrit :
>> 
>> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
>> 
>> Shape Expressions includes recursive shapes, such as <IssueShape> { 
>> :status (:Assigned :Unassigned), ... , :related @<IssueShape>* } 
>> Recursive shapes are a prominent feature of Shape Expressions, showing
>> up in the introductory material and talks about Shape Expressions.
>> However, there appears to be problems in the semantics of recursive
>> shapes in Shape Expressions. If these problems cannot be fixed, then
>> recursive shapes may have to be removed from Shape Expressions.
>> 
>> Sometimes it is relatively obvious what nodes are have such recursive 
>> shapes. For example, in ex:i1 :related ex:i2 . ex:i1 :related ex:i3 . 
>> ex:i1 :status :Assigned . ex:i2 :status :Unassigned . ex:i3 :status
>> :Unassigned . all of ex:i1, ex:i2, and ex:i3 should have shape
>> <IssueShape>.
>> 
>> Do ex:j1, ex:i2, and ex:i3 have shape <IssueShape> here in Shape 
>> Expressions? Show how this can be determined in each of the semantics
>> for Shape Expressions.
>> 
> 
> There is a valid typing that associates {<IssueShape>} to ex:i1, ex:i2
> and
ex:i3.
> 
>> However, sometimes it is not obvious what nodes have a particular 
>> recursive shape. For example, in ex:j1 :related ex:j1 . ex:j1 :status
>> :Assigned . it is reasonable to consider ex:j1 as having shape
>> <IssueShape> but it is also reasonable to consider ex:j1 as not having
>> shape <IssueShape>.
> 
>> Does ex:j1 have shape <IssueShape> here in Shape Expressions? Show how
>> this can be determined in each of the semantics for Shape Expressions.
> 
> There is a valid typing that associates {<IssueShape>} with ex:j1.
> Indeed, the constraints of <IssueShape> are satisfied in this node. As a
> side remark, I do not see why it is reasonable to consider that ex:j1 
> should not have <IssueShape>

Your semantics shows why this is reasonable.  In your semantics it is be
permissable to have ex:j1 not typed with <IssueShape> if there is another
type to which ex:j1 could belong.

>> There are ever trickier situations involving recursive shapes. For
>> example, consider the two mutually recursive shapes <S> { ( ex:p @<S> |
>> ex:p @<T> ) } <T> { ( ex:p @<T> | ex:p @<S> ) } (something is in <S> if
>> it has an ex:p fillers and either all its ex:p fillers are in <S> or
>> its ex:p fillers are in <T> but not both, and similarly for <T>). It is
>> unclear as to which nodes should have shape <S> or <T> in the graph 
>> ex:a ex:p ex:b . ex:b ex:p ex:a .
>> 
> 
> With our semantics and considering /closed/ shapes,

As far as I can tell, the semantics in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
only handles closed shapes.  Is there a treatment of open shapes with this
semantics?

> the shape
> 
> <S> { ( ex:p @<S> | ex:p @<T> ) }
> 
> intuitively says that a <S> typed node should have exactly one outgoing 
> ex:p, that leads either to <S> or to <T> node. This however does not
> forbid the target node to have both <S> and <T>; we exclude any form of
> negative constraints.

This is the semantics in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
The other semantics for Shape Expressions appear to be different.

> There are 9 valid typings, associating with ex:a and ex:b, in this
> order, the sets of shapes: {<S>} {<S>} {<S>} {<T>} {<S>} {<S>,<T>} {<T>}
> {<S>} {<T>} {<T>} etc. actually all combinations in the Cartesian product
> { {<S>}, {<T>}, {<S>,<T>} } X { {<S>}, {<T>}, {<S>,<T>} } The unique
> maximal typing is <S>,<T> for both ex:a and ex:b.
> 
> 
> Considering /open/ shapes, the shape <S> { ( ex:p @<S> | ex:p @<T> ) } 
> intuitively says that a <S> typed node should have one outgoing ex:p
> that leads to <S> or to <P>, and any number of any other outgoing edges 
> (/open/). The  the maximal typing is the same as above.

Again, where is the treatment of open shapes with the semantics in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf

>> Which nodes have which shapes here? Show how this can be determined in
>> each of the semantics for Shape Expressions. Are the answers
>> independent of changes in the ordering of the disjuncts? Do the answers
>> depend on any ordering of the sets involved? Does this match any
>> intuitive notion of recursive shapes?
> 
> Yes, in our semantics, the maximal typing is independent on the ordering
> of the disjuncts. Non maximal typings depend on the order of evaluation,
> and the problem of non uniqueness occurs even without recursion.
> 
> I do not know what is your intuition for recursive shapes, but our
> intuition actually does not consider recursion at all. We considered that
> a shape defines *local* constraints, and these constraints might envolve
> that the neighbours of a node satisfy other shapes, that might eventually
> be the same shape as the one being defined.  We then have recursion while
> evaluating, but recursion does not influence the declarative semantics.

[...]

> Thanks for reading this long explanation. Hope it helps. I would be glad 
> to answer if you need to discuss on our semantics.

Well, I think that I do understand the semantics in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
at least with respect to closed types.

I'm not sure that the extension of the language in
http://www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
to the language in the W3C Shape Expressions submission is easy.

> Iovka

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

iQEcBAEBAgAGBQJU7LOjAAoJECjN6+QThfjzgQYIALmaGljJdv3gdOozOEqA9Gax
axW0CjluA0exuPkWlLgEa/Q/cp+xP7eUEvI/GiyYmtneei5GyfzK01RFgPh7bWne
eJY1h1I8cX3CpvmVCWEmStYXwUNd46XZaL4cO7TNSs/0rHkR2aaK38YvBW1KDcC1
1k8hy51xOYbvaA3d+pquZ2OyseCmEUJWGyZl40hv2yZam8SCIW6D+eZTkowSTTzD
ZAN8V0Y5L/EzqWfZTZSEmkDjsHw4pSXkklveJfSCnXq9nJaDHmbr8w4cynyIXyQ3
0K0o/1oZKxZ4xdSuBELXenf/DmtYNsNH3JUYofOaeT5sUYGB1mGckH30/oCrtCU=
=lTBt
-----END PGP SIGNATURE-----

Received on Tuesday, 24 February 2015 17:24:18 UTC