The Various Versions of Shape Expressions

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

There appears to be three separate versions of Shape Expressions, two
sharing a syntax and being quite similar and a third having a different
syntax and being quite different.

There is the W3C Member Submission of 2 June 2014 consisting of the "Shape
Expressions 1.0 Primer" http://www.w3.org/Submission/shex-primer/ and the
"Shape Expressions 1.0 Definition" http://www.w3.org/Submission/shex-defn/.
The latter document contains a concrete and an abstract syntax and a
semantics for Shape Expressions (excluding semantic actions) in terms of an
extension of Z.

This account of Shape Expressions is ill-founded on recursive references
from one shape back to itself, either direct or indirect.  For example, with
the schema
  <S> { ex:p <S> }
it is undeterminable whether ex:a validates against <S> in
  ex:a ex:p ex:a .
because whether ex:a validates against <S> depends on whether ex:a validates
against <S>.

There is an axiomatic semantics of Shape Expressions described in "Shape
Expressions: An RDF validation and transformation language"
labra.github.io/ShExcala/papers/semantics2014.pdf and elsewhere.  This
account of Shape Expressions uses a context to try to resolve recursive
references.

However, this treatment also has difficulties.  For example, with the schema
  <S> { ex:q <Z> | ex:p <S> }
whether ex:a validates against <S> in
  ex:a ex:q ex:z .
  ex:b ex:q ex:z .
  ex:c ex:q ex:z .
  ex:a ex:p ex:b .
  ex:b ex:p ex:c .
  ex:c ex:p ex:a .
depends on how the context is started.  If the context is started at ex:a
then ex:a does not validate against <S> (because the context breaks the loop
back at ex:a assuming that ex:a does validate against <S> which then results
in ex:c not validating against <S>, ex:b validating against <S>, and finally
ex:a *not* validating against <S>).  If the context is started at ex:c
then ex:a does validate against <S> (because the context breaks the loop
back at ex:c assuming that ex:c does validate against <S> which then results
in ex:b not validating against <S>, ex:a *validating* against <S>, and finally
ex:c not validating against <S>).

Implementations of Shape Expressions appear to generally follow this
axiomatic semantics.


There are also Complexity and Expressiveness of ShEx for RDF
www.grappa.univ-lille3.fr/~staworko/papers/staworko-icdt15a.pdf and
Validating RDF with Shape Expressions http://arxiv.org/abs/1404.1270 that
define a language called Shape Expression Schema and gives it a semantics
over edge-labeled graphs via regular bag expressions.  This formalism has
significant differences from the previous Shape Expressions formalism.  In
particular, the analogue of conjunction is additive instead of being
combining.

There do not appear to be any formal problems here, but this version of
Shape Expressions ends up being very different from the version in the
Member Submission.  For example with schema
  <S> { ex:p <Z> {1} , ex:p <Z> {1} }
  <Z> { }
ex:a in
  ex:a ex:p ex:b .
  ex:a ex:p ex:c .
matches <S>.



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

iQEcBAEBAgAGBQJVECstAAoJECjN6+QThfjz3cAH/iUvKCPabJ1m1oQacB3T2Rzh
xtn1Qoj4hXD4CKytQSPd+nliouOxeHHusXz8d0y+63OlhEJzicMXYxeZj9mtQ8Uf
fUbwo43/0on1LxvF0IFDIFDBc4tmnLaG/nItdrssJ6sWvpJGiEXHEAa99uglQV+M
z4Yip7nSl5/Fy3tdn43zIJfe/1X+9vcfeO0arbbv+n0sZOKAclCETGX9O+ZbuW0T
sxGqQ2u+5sZExbIb8lIEYFHZQUuZ+QB4sutxHyZio0E//oFI0rz9F3uaB3PXdbv9
Uw3hHF44LcC9mzTnjoo5eECw0C4PoGnH9Nhu20eIGxHPJo1TCFTH0Ij6gKAyfgc=
=1xMb
-----END PGP SIGNATURE-----

Received on Monday, 23 March 2015 15:03:52 UTC