Re: recursive shapes in shape expressions

Le 24/02/2015 16:02, Peter F. Patel-Schneider a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>
> On 02/24/2015 04:32 AM, Iovka Boneva wrote:
>> Le mar. 24 févr. 2015 02:02:02 CET, Peter F. Patel-Schneider a écrit :
>>> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
>>>
>>> Just a preliminary response to get at a particular part of one
>>> example.
>>>
>>> On 02/23/2015 07:25 AM, Iovka Boneva wrote:
>>>
>>>>
>>>> Le sam. 21 févr. 2015 23:27:52 CET, Peter F. Patel-Schneider a écrit
>>>> :
> [...]
>>>>> 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, 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.
>>>>
>>>> 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.
>>>
>>> Huh?
>>>
>>> If ex:b is of type {<S>,<T>} then <ex:a> should not be <S> or in <T>
>>> because both arms of the exclusive or disjunct are true. The literature
>>> that I have read on shape expressions is very clear that exclusive or
>>> is the meaning of the | construct - see
>>> http://www.w3.org/Submission/2014/SUBM-shex-primer-20140602/ for
>>> example.
>>>
>> Indeed, there is a difference between our semantics and the one on the
>> page you site. The reason for that is basically that we started our work
>> on a previous version of shapes, in which the Or was not exclusive. e.g.
>> http://www.w3.org/2013/ShEx/Primer.html
>>
>> If the user cases require Xor, then we can think of extending the
>> semantics. I would however not advise to introduce the possibility to
>> check whether a node *does not satisfy* a given shape. Some form of
>> exclusiveness can be expressed with closed shapes, or even with a
>> 'controlled' version of open shapes. Indeed, with closed shapes, a node
>> would match
>>
>> <S> { ( ex:p @<S> | ex:p @<T> ) }
>>
>> if it has exactly one ex:p outgoing property. The 'controlled' version of
>> /open/ shape would enforce that the shapes are 'open' only on the labels
>> not mentioned in the shape. So, the latter shape would be satisfied by
>> nodes that have exactly one outgoing ex:p, and any other outgoing edges
>> which label is different from ex:p.
> I don't remember having seen any open or controlled open treatment in this
> semantics.  It appears to me that there would have to be a complete rewrite
> of the semantics for this.
Open shapes are obtained by using the universal type, discussed on p. 23 
of the full version of the paper
http://arxiv.org/pdf/1404.1270v2
We only considered deterministic shapes there because in that section we 
were interested in efficient validation, but open shapes are perfectly 
definable for non-deterministic shapes.

There is no need of rewriting of the syntax, open shapes fit perfectly 
the remaining of the paper.

Lemma 8.6 states uniqueness and minimality of the typing, with well 
identified conditions, that I think fit quite well the user cases in 
which validation is performed starting from some identified root nodes 
(captured by the notion of pre-typing).
>> I believe that such controlled open semantics allows to talk about what
>> is expected to be in the graph, including cardinality constraints for
>> all properties that were mentioned, and in the same time allows to have
>> in the graph all other triples which predicates are outside of the
>> 'domain' of interest. Additionally, it has a well defined declarative
>> semantics.
> Where?
As I said before, basically p. 23 as addition of the semantics defined 
before in the same paper.

Iovka

-- 
Iovka Boneva
Associate professor (MdC) Université de Lille
http://www.cristal.univ-lille.fr/~boneva/
+33 6 95 75 70 25
Please note that I read my mails twice a day at 9:00 and 13:00 (CET)
For urgent matters, please contact me by phone

Received on Tuesday, 24 February 2015 16:47:35 UTC