Re: differing accounts of Shape Expressions

On Thu, Feb 26, 2015 at 2:56 AM, Simon Steyskal <simon.steyskal@wu.ac.at> wrote:
> Hi!
>
>> 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.
>
>
> Considering the fact that ShEx was (afaik) developed as a response to the
> RDF Validation Workshop[2} (as
> indicated in SotD[1]) I assume its final "specification" is still under
> permanent improvement.
>
> Before we reach the point of deciding on SHACL's "Compact, human-readable,
> non-RDF syntax for expressing constraints on RDF graph patterns (aka
> shapes)", it would (imho) be premature
> to make a decision on wether or not ShEx should be considered just because
> it has evolved over the last year.
> Apart from that, we basically have the entire "ShEx team" in our midst. They
> can take a stance on what final semantics we should consider for ShEx once
> the decision is required.

My semantics have changed over the last year in response to two
general categories of user requests:

  * relax the "single occurance" constraints to address use cases
where the same predicate is used multiple times with different
constraints, as typified by:

      my:PatientShape {
        ex:biologicalParent { ex:gender :Female } ,
        ex:biologicalParent { ex:gender :Male }
      }

  * show the triples that weren't covered by the shape validation.

Peter, regardless of whether the shapes people present a unified view
or a few different options, that will have to change in response to
the standardization process. Of course it would be better if some or
all of us were returning to a future where we'd already seen the
outcome of the working group decisions and community feedback. (At
least we're not intransigent.) All of the decisions that the ShEx
folks face are ones that the Shapes WG will eventually confront so it
seems like a good thing that the options are already laid out on the
table in the variances in ShEx approaches.

> simon
>
> [1] http://www.w3.org/2013/ShEx/Primer
> [2] http://www.w3.org/2012/12/rdf-val/
>
> ---
> DDipl.-Ing. Simon Steyskal
> Institute for Information Business, WU Vienna
>
> www: http://www.steyskal.info/  twitter: @simonsteys
>
> Am 2015-02-25 23:32, schrieb Peter F. Patel-Schneider:
>
>> -----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-----
>
>



-- 
-ericP
office: +1.617.258.5741
mobile: +1.617.599.3509

Received on Thursday, 26 February 2015 10:17:54 UTC