Re: differing accounts of Shape Expressions

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

Well, I would say "a plague on both your houses".

If there is no consensus on what Shape Expressions means, then why spend
more time on considering it?  It's hard enough considering something that
has a single definition.

peter


On 02/25/2015 10:43 AM, Karen Coyle wrote:
> Peter, do you have a suggested solution? - kc
> 
> On 2/25/15 10:04 AM, Peter F. Patel-Schneider wrote: 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

iQEcBAEBAgAGBQJU7k2bAAoJECjN6+QThfjzhasH/Ak4tq6rLxtFYrjkuSYgWb9d
wtSahJd6/P2gAntBqpW11rnXPXt2cWERFgHgoqVM4pCkmFU1DQrrLA4LyNnBLWns
P7Cq3LVqZrGWBIcxZFxnC9uxiAiz1V9S6c3CGqqHvxzmgI0GBoB1VL8mZFFPsnzb
JAPu7gYSXtgemBXfV99Q/K1EfuoMBInZOyIEpP7Aew9Nvk/9SXC8XZ4FWjDY3UgR
K0gREFtQFQqUgQZTPCvVbVvDzvqzrbX6nPXaDT/wrnK+16nEfOTQk2ec/AbYma5e
4+NWLOqupX6rAdKVBSVluEPTWY5Z0KJroFmOoUdvDi0vemwHdjQFf56bnUhGsog=
=O6pn
-----END PGP SIGNATURE-----

Received on Wednesday, 25 February 2015 22:33:31 UTC