Re: differing accounts of Shape Expressions

Thank you Peter for this careful study of the three semantics, which is 
very helpful for improving them and making them converge.

I agree with (most of) your statements, but not with your conclusions. 
Just few remarks.

The essential difference between SE1 and SE2 is that the former 
considers logical Xor and And, and the latter considers disjunction and 
unordered concatenation instead. These two ways of defining the 
semantics are (almost) equivalent if one forbids repetitions of symbols 
in ShEx. By the way, one can notice that all your examples illustrating 
the difference between the two rely on repetition of symbols.

Recall that initially ShEx did forbid repetition of symbols, and 
repetitions were allowed recently due to user requirements. Please give 
us some time for integrating these new requirements, and making the 
semantics effectively converge.

Concerning SE3, we already started discussions with Jose, identified 
some differences between SE2 and SE3, and have ideas how to fix them.

Iovka


Le 25/02/2015 19:04, Peter F. Patel-Schneider a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> There are three quite different accounts of Shape Expressions available off
> of http://www.w3.org/2001/sw/wiki/ShEx
>
>
> There is a primer and denotational semantics which appear to be early
> versions of the W3C submission http://www.w3.org/Submission/2014/03/, with
> the Primer by Eric Prud'hommeaux at www.w3.org/Submission/shex-primer/ and
> the definition by Harold Solbrig and Eric Prud'hommeaux at
> www.w3.org/Submission/shex-defn/.  There is also
> https://github.com/w3c/ShEx/blob/master/ShExZ/ShExZ.pdf?raw=true which is
> close to the definition in the submission.  Let's call this SE1.
>
>
> There is "Validating RDF with Shape Expressions" by Iovka Boneva, Jose
> Emilio Labra Gayo, Samuel Hym, Eric G. Prud'hommeau, Harold Solbrig, Sławek
> Staworko at arxiv.org/abs/1404.1270.  A paper with the same treatment is
> "Complexity and Expressiveness of ShEx for RDF" by Sławek Staworko , Iovka
> Boneva, Jose E. Labra Gayo, Samuel Hym, Eric G. Prud’hommeaux, and Harold
> Solbrig at www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf
> Let's call these SE2.
>
> There is the ShEx/Operational Semantics at
> http://www.w3.org/2001/sw/wiki/ShEx/OperationalSemantics_Operational_semantics
> This appears similar in spirit to an axiomatic semantics for SHACL prepared
> by Jose Emilio Labra Gayo.  Let's call this SE3.
>
>
> SE1:
>
> The syntax of SE1 uses rules like:
> <IssueShape> {
>      ex:state (ex:unassigned ex:assigned),
>      ex:reportedBy @<UserShape>,
>      ex:reportedOn xsd:dateTime,
>      ( ex:reproducedBy @<EmployeeShape>,
>        ex:reproducedOn xsd:dateTime      )?,
>      ex:related @<IssueShape>*
> }
>
> SE1 works on RDF graphs.  SE1 has conjunction, counting, cyclicity,
> exclusive disjunction, and a number of atomic constructs that involve node
> labels.
>
> The semantics of SE1 is given in an extension of Z.  The semantics is based
> on judgements of how well a node in an RDF graph matches a shape in a set of
> SE1 rules.  The semantics of SE1 is inherently an open semantics, i.e.,
> adding irrelevant edges to a graph does not affect results.  A closed
> semantics for SE1 woulld require a complete rewrite, as there is no
> determination of relevancy in the semantics.  The semantics of SE1 requires
> negative judgements, to handle the exclusive disjunction.
>
> SE1 is problematic because it uses an ill-founded extension to Z.  The
> meaning of cyclic references in rules cannot be determined in many
> situations, even if the cycles are all positive.
>
>
> SE2:
>
> SE2 works on labelled-edge graphs, not RDF graphs.  The language of SE2 uses
> rules like:
>     t0 -> a::t1 || (b::t2)[2;4]
> SE1 has disjunction, unordered concatenation, and cyclicity.  The language
> of SE2 is missing many of the features of SE1.
>
> The semantics of SE2 is in part an algebraic semantics, building up bag
> languages.  The other part of the semantics of SE2 is based on assignments.
> The semantics of SE2 is a closed semantics, i.e., all outgoing edges from a
> node have to be matched.  A syntactic transform can be used to open up the
> semantics, adding in universal types to soak up extra edges.
>
> SE2 is problematic because its language is missing many of the features in
> SE1.
>
>
> SE3:
>
> The semantics in SE3 is an axiomatic semantics.  It works on a version of
> RDF graphs.  It appears to be non-additive, in that the matched portions of a
> graph are unioned together, but the account is missing many details.
> Apparently adding the missing details results in a semantics that is
> non-additive, i.e., conjoining something with itself requires two copies of
> whatever is matched by the conjunct.  The semantics also appears to be
> closed, i.e., every edge in the graph has to be used.
>
> SE3 is problematic because there are many missing portions of the
> axiomatization.
>
>
>
> Differences between SE1 and SE2:
>
> SE1 and SE2 are very different, even aside from the differences in surface
> syntax.
>
> SE1 works on RDF graphs; SE2 works on edge-labelled graphs, which don't have
> node labels.
>
> SE1 has conjunction; in
>    ex:a ex:p ex:v .
> with
>    <S0> { ex:p (ex:v) , ex:p (ex:v) }
> ex:a has type <S0>
> SE2 has unordered concatenation, which is not conjunction; in
>    { < a p b > }
> with
>     t0 -> p::e || p::e
>     e ->
> a cannot have type t0.
>
> The basic edge construct in SE1 applies to all the outgoing edges for a
> particular property; in
>    ex:a ex:p ex:v .
>    ex:a ex:p ex:w .
>    ex:a ex:p ex:x .
> with
>    <S0> { ex:p (ex:v ex:w)>{2,3} }
> ex:a does not have type <S0>.
> The basic edge construct in SE2 does not need to apply to all of the
> outgoing edges for a particular property; in
>    { < a p b >, <b q x>, <a p c>, <c r y> }
> with
>    t0 -> (p::t1)+ || (p::t2)+
>    t1 -> q::e
>    t2 -> r::e
>    e ->
> a has type t0.
>
> SE1 can require that nodes have multiple types; in
>    ex:a ex:p ex:c .
>    ex:c ex:q ex:d .
>    ex:c ex:r ex:e .
> with
>    <S0> { ex:p <S1>, ex:p <S2> }
>    <S1> { ex:q ( ex:d ) }
>    <S2> { ex:r ( ex:e ) }
> ex:a having type <S0> requires that ex:c has both type <S1> and <S2>.
>
>
>
>
> Where does SE3 fit:
>
> SE3 appears to be an axiomatic semantics for the language of SE1 but it is
> hard to figure out just what is going on.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1
>
> iQEcBAEBAgAGBQJU7g60AAoJECjN6+QThfjzxBAH/1/CpTLE/ZCIbs/J+pdf4DA6
> +9tjYRjK+IXtJzSSu8gBilzpaCxlUo7/bP1iwsIxCUQ5EZ+V3vMDYgegivmPfzeb
> +rKx0S3dv30iBKpgmDk0yagErL+/vz//h6y51aG0Uwi/S0TYyB+BuwRuiad5+HXk
> 96x9E+L6d1tRKSYnzOeP7fiKqz1BaZ8yASiyYzPWcc+7rN457eofACXhu3anQeuz
> 4lHMILUCLw3IFfhJSFFNYYFgeam8jTSl5XRbkLMCMi4Ergle5sd1VKNCY0/muHCg
> zQMBXseISexrz83XDHQhty7Ju7x7UY5p8sTqrYkRLBDw76CFy6ocEsSSqMeuq0Q=
> =gafT
> -----END PGP SIGNATURE-----
>


-- 
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 Thursday, 26 February 2015 14:16:27 UTC