=Paper= {{Paper |id=Vol-3747/dqmlkg_paper4 |storemode=property |title=Extending Shape Expressions for different types of knowledge graphs |pdfUrl=https://ceur-ws.org/Vol-3747/dqmlkg_paper4.pdf |volume=Vol-3747 |authors=Jose Emilio Labra Gayo |dblpUrl=https://dblp.org/rec/conf/text2kg/Emilio24 }} ==Extending Shape Expressions for different types of knowledge graphs== https://ceur-ws.org/Vol-3747/dqmlkg_paper4.pdf 
                                Extending Shape Expressions for different types of
                                knowledge graphs
                                Jose Emilio Labra-Gayo1
                                1
                                    WESO lab - University of Oviedo


                                                                         Abstract
                                                                         Shape Expressions (ShEx) has been proposed as a concise and human-readable language to describe
                                                                         and validate RDF. Inspired by regular expressions, it offers an expressive formalism to describe graph
                                                                         structures based on regular bag expressions. Although plain RDF is one of the common data formats
                                                                         employed to represent knowledge graphs, there have been several proposals to either extend RDF with
                                                                         the so-called RDF-Star or RDF 1.2, or to employ other formalisms like property graphs. In this paper
                                                                         we present an overview and comparison of those approaches and propose three possible extensions of
                                                                         ShEx: ShEx-Star which can be used to validate RDF-Star, ShEx-N: that can be used when nodes also
                                                                         act as properties in RDF and PShEx, which can be used to describe property graphs. We present some
                                                                         examples and a semantics of each extension.




                                1. Introduction
                                Although Knowledge graphs have been successfully adopted by the industry, an important
                                aspect of their practical application is the quality of the data that they contain. In order to
                                increase their quality, it is necessary to have some mechanisms that can check the conformance
                                of the data to some kind of schema. Knowledge graphs are usually considered schema-less,
                                because there is no mandatory schema, however, in most cases the data curators have an implicit
                                schema in mind. Having the possibility to materialize that implicit schema into a machine
                                processable form that can be automatically verified can mitigate the risk of non-conformant
                                data.
                                   In practice, there are several types of technologies that can be used for knowledge graphs [1]:
                                Directed edge-labeled graphs, whose main representative are RDF graphs, and Property graphs,
                                which allow property–value pairs and labels to be associated with nodes and edges.
                                   In the case of RDF, two main technologies have been proposed for validation: ShEx [2] and
                                SHACL [3], which are based on the notion of a shape as a description of the topology of some
                                specific kind of nodes. In this way, it is possible to define a schema as a set of shapes which
                                describe the expected properties of some nodes, their expected cardinalities and the kind of
                                nodes. These schemas, can be used to validate RDF data and check if it conforms to those shapes.
                                We employ ShEx in the paper because it can be seen as a description language for RDF acting
                                as grammar where a ShEx schema represents the set of all the RDF graphs that conform to it.

                                Envelope-Open labra@uniovi.es (J. E. Labra-Gayo)
                                GLOBE http://labra.weso.es (J. E. Labra-Gayo)
                                Orcid 0000-0001-8907-5348 (J. E. Labra-Gayo)
                                                                       Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
                                    CEUR
                                    Workshop
                                    Proceedings
                                                  http://ceur-ws.org
                                                  ISSN 1613-0073
                                                                       CEUR Workshop Proceedings (CEUR-WS.org)




CEUR
                  ceur-ws.org
Workshop      ISSN 1613-0073
Proceedings
   There has been a proposal for an extension of RDF called RDF-Star [4] and a Working Group
is currently working taking that proposal as input to define what is currently called RDF
1.2 [5]. The proposal extends RDF with the possibility of having triples as subjects or objects
in statements. The relationship between that extension and property graphs has already been
studied [6].
   Although ShEx was defined to describe and validate RDF, we consider that it can be extended
to describe and validate RDF-Star (or RDF 1.2), so in this paper we explore a possible extension
of the language in that direction. Apart from that, the shapes in ShEx are usually centered
on describing nodes that act as either subjects or objects, but in RDF, it is also possible to
add statements whose subjects or objects are also the predicates of other statements. We also
explore a possible extension of ShEx where it is possible to define shapes about nodes that act as
properties. Finally, although there have been several proposals to define schemas for property
graphs, we consider that the grammar-based approach of ShEx can also be helpful, so we also
explore what it would look like to extend ShEx for describing and validating property graphs.
   The main contributions of this paper are to present three extensions of ShEx: ShEx-Star
for RDF-Star (section 3), ShEx-N for describing nodes as properties (section 4) and PShEx for
property graphs (section 5), with their abstract syntax and semantic definitions.


2. RDF and ShEx
Definition 1 (RDF triple and RDF Graph). Given a set of IRIs I , a set of blank nodes B and a set
of literals Lit, an RDF triple is a tuple (𝑠, 𝑝, π‘œ) where 𝑠 ∈ I βˆͺ B is called the subject, 𝑝 ∈ I is called
the predicate and π‘œ ∈ I βˆͺ B βˆͺ Lit is called the object. An RDF graph G is a set of RDF triples.
  There are several syntaxes for RDF graphs like Turtle, N3, RDF/XML, etc. In this document,
we will use Turtle.
Example 1 (Example of an RDF graph in Turtle). The following snippet contains a simple RDF
graph with two nodes :a and :b .

 prefix : 

 :a :name "Alice" ;
    :knows :b .
 :b :firstname "Robert", "Julius" ;
    :lastname "Smith" .


   The neighbors of a node 𝑛 ∈ V in an RDF graph G are defined as π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛, G) = {(𝑛, 𝑝, 𝑦) ∣
(𝑛, 𝑝, 𝑦) ∈ G} βˆͺ {(π‘₯, 𝑝, 𝑛) ∣ (π‘₯, 𝑝, 𝑛) ∈ G} βˆͺ {(π‘₯, 𝑛, 𝑦) ∣ (π‘₯, 𝑛, 𝑦) ∈ G}.
   Shape Expressions (ShEx) were proposed as such a language in 2014 [2]. It was designed as a
high-level and concise domain-specific language to describe RDF. The syntax of ShEx is inspired
by Turtle and SPARQL, while the semantics was inspired by RelaxNG and XML Schema. In this
section we describe a simplified abstract syntax of ShEx following [7]1 .
    1
        The full specification of ShEx is available at https://shex.io/shex-semantics/
                                         :knows
                            :a                                  :b
                             :name                :rstname          :rstname     :lastname

                          "Alice"          β€œRobert"           β€œJulius"           β€œSmith"

Figure 1: Basic RDF graph example

Definition 2 (ShEx schema). A ShEx Schema is defined as a tuple ⟨L, π›ΏβŸ© where L is the set of
shape labels, and 𝛿 ∢ L β†’ S is a total function from labels to shape expressions. The set of
shape expressions 𝑠𝑒 ∈ S is defined using the following abstract syntax:
   𝑠𝑒 ::= cond            Basic boolean condition on nodes (node constraint)
         |    𝑠𝑒1 AND 𝑠𝑒2 Conjunction of 𝑠𝑒1 and 𝑠𝑒2
         |    @l          Shape label reference for l ∈ L
         |    CLOSED {𝑑𝑒} Closed shape
         |    {𝑑𝑒}        Open shape
   𝑑𝑒 ::= 𝑑𝑒1 ; 𝑑𝑒2       Each of 𝑑𝑒1 and 𝑑𝑒2
         |    𝑑𝑒1 ∣ 𝑑𝑒2   Either 𝑑𝑒1 or 𝑑𝑒2
         |    π‘‘π‘’βˆ—         Zero or more 𝑑𝑒
                 𝑝
         |      βˆ’
                β†’ 𝑠𝑒             Outgoing Triple with predicate 𝑝 and object conforming to 𝑠𝑒
                 𝑝
         |     𝑠𝑒 βˆ’
                  β†’              Incoming triple with predicate 𝑝 and subject conforming to 𝑠𝑒
         |     πœ–                 Empty triple expression
   Intuitively, shape expressions define conditions about nodes while triple expressions define
conditions about the neighborhood of nodes, and shapes qualify those neighborhoods by
allowing (open shapes) or disallowing (closed shapes) triples with other predicates. We omit
negation and disjunction operator to simplify the interactions between negation and recursion,
which led to a stratified negation requirement in ShEx.
   The restrictions imposed on shape expressions schemas in [8] also apply here. Namely, in a
schema (L, 𝛿, S)

    β€’ The shape label references used by the definition function 𝛿 are themselves defined, i.e. if
      @l appears in some shape definition, then l belongs to L;
    β€’ No definition 𝛿(l) uses a reference @l to itself, neither directly nor transitively, except
                                                                                                𝑝
      while traversing a shape. For instance, 𝛿(l) = @l AND 𝑠𝑒 is forbidden, but 𝛿(l) = { βˆ’
                                                                                          β†’ @l}
      is allowed.

Example 2 (Example of ShEx schema). A ShEx schema that describes the RDF graph presented
in example 1 can be defined as:
       L       =      {π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› }
                                 π‘›π‘Žπ‘šπ‘’             𝑓 π‘–π‘ π‘‘π‘›π‘Žπ‘šπ‘’                π‘™π‘Žπ‘ π‘‘π‘›π‘Žπ‘šπ‘’
   𝛿(π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›)    =     {     ( βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘” ∣      βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”*;       βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”);
                                 π‘˜π‘›π‘œπ‘€π‘ 
                              βˆ’βˆ’βˆ’βˆ’βˆ’β†’ @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› *
                      }
  ShEx has several concrete syntaxes like a compact syntax (ShExC) and an RDF syntax defined
based on JSON-LD (ShExJ) 2 .

Example 3. An example of a ShEx schema using ShExC compact syntax.

 prefix : 
 prefix xsd: 
  {
  (:name xsd:string |
   :firstname xsd:string * ; :lastname xsd:string );
  :knows @ *
 }



   The semantics of ShEx schemas is based on a conformance relation parameterized by a
shape assignment: we say that node 𝑛 in graph G conforms to shape expression 𝑠𝑒 with shape
assignment 𝜏, and we write G, 𝑛, 𝜏 ⊨ 𝑠𝑒.
   The following rules are defined similar to [9], where it is shown that there exists a unique
maximal shape assignment 𝜏max that allows us to define conformance independently of the
shape assignment. The conformance relation is defined recursively on the structure of 𝑠𝑒 by the
set of inference rules presented in table 1 where π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒) is the set of predicates that appear in
a triple expression 𝑑𝑒 and can be defined as:
                                π‘π‘œπ‘›π‘‘(𝑛) = π‘‘π‘Ÿπ‘’π‘’                   G, 𝑛, 𝜏 ⊨ 𝑠𝑒1       G, 𝑛, 𝜏 ⊨ 𝑠𝑒2
                        πΆπ‘œπ‘›π‘‘                             𝐴𝑁 𝐷
                                 G, 𝑛, 𝜏 ⊨ π‘π‘œπ‘›π‘‘                      G, 𝑛, 𝜏 ⊨ 𝑠𝑒1 AND 𝑠𝑒2

                       𝛿(l) = 𝑠𝑒     G, 𝑛, 𝜏 ⊨ 𝑠𝑒                           π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛, G) = 𝑑𝑠        G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒
          π‘†β„Žπ‘Žπ‘π‘’π‘…π‘’π‘“                                         πΆπ‘™π‘œπ‘ π‘’π‘‘π‘†β„Žπ‘Žπ‘π‘’
                               G, 𝑛, 𝜏 ⊨ @𝑙                                      G, 𝑛, 𝜏 ⊨ CLOSED {𝑑𝑒}

                                   𝑑𝑠 = {⟨π‘₯, 𝑝, π‘¦βŸ© ∈ π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛, G) ∣ 𝑝 ∈ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒)}       G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒
                      π‘‚π‘π‘’π‘›π‘†β„Žπ‘Žπ‘π‘’
                                                           G, 𝑛, 𝜏 ⊨ {𝑑𝑒}
Table 1
Inference rules for ShEx shape expressions

    π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ; 𝑑𝑒2 )       =      π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ) βˆͺ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒2 )
    π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ∣ 𝑑𝑒2 )       =      π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ) βˆͺ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒2 )
                  𝑝
    π‘π‘Ÿπ‘’π‘‘π‘ ( βˆ’ β†’ 𝑑𝑒) = {𝑝}
    π‘π‘Ÿπ‘’π‘‘π‘ (π‘‘π‘’βˆ—)       = π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒)
    π‘π‘Ÿπ‘’π‘‘π‘ (πœ–)         = βˆ…
   The rules for node constraints (πΆπ‘œπ‘›π‘‘) and conjunction are as expected. A node 𝑛 conforms
to an open shape with triple expression 𝑑𝑒 if its neighborhood restricted to the triples with
predicates from 𝑑𝑒 conform, meaning that triples whose predicates are not mentioned in 𝑑𝑒 are

    2
        See ShEx specification [8] for details.
not constrained by the shape (rule π‘‚π‘π‘’π‘›π‘†β„Žπ‘Žπ‘π‘’). Conformance to a closed shape requires to
consider the whole neighborhood of the node (rule πΆπ‘™π‘œπ‘ π‘’π‘‘π‘†β„Žπ‘Žπ‘π‘’).
   Conformance to a triple expression uses a second relation defined on sets on neighborhood
triples 𝑑𝑠 instead of nodes 𝑛. The set of neighborhood nodes 𝑑𝑠 of a graph G conforms to a triple
expression 𝑑𝑒 with shape assignment 𝜏, written as G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒, as defined by the inference rules
in table 2.
                                     (𝑑𝑠1 , 𝑑𝑠2 ) ∈ π‘π‘Žπ‘Ÿπ‘‘(𝑑𝑠)         G, 𝑑𝑠1 , 𝜏 ⊩ 𝑑𝑒1       G, 𝑑𝑠2 , 𝜏 ⊩ 𝑑𝑒2
                         πΈπ‘Žπ‘β„Žπ‘‚π‘“
                                                               G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ; 𝑑𝑒2

                                       G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1                                     G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒2
                         𝑂𝑛𝑒𝑂𝑓1                                           𝑂𝑛𝑒𝑂𝑓2
                                    G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ∣ 𝑑𝑒2                                G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ∣ 𝑑𝑒2

                      𝑑𝑠 = {⟨π‘₯, 𝑝, π‘¦βŸ©}         G, 𝑦, 𝜏 ⊨ 𝑠𝑒                    𝑑𝑠 = {βŸ¨π‘¦, 𝑝, π‘₯⟩}           G, 𝑦, 𝜏 ⊨ 𝑠𝑒
             𝑇 𝐢1                                                      𝑇 𝐢2
                                               𝑝                                                          𝑝
                               G, 𝑑𝑠, 𝜏 ⊩      βˆ’
                                               β†’ 𝑠𝑒                                      G, 𝑑𝑠, 𝜏 ⊩ 𝑠𝑒 βˆ’
                                                                                                       β†’

                    (𝑑𝑠1 , 𝑑𝑠2 ) ∈ π‘π‘Žπ‘Ÿπ‘‘(𝑑𝑠)        G, 𝑑𝑠1 , 𝜏 ⊩ 𝑑𝑒     G, 𝑑𝑠2 , 𝜏 ⊩ π‘‘π‘’βˆ—
          π‘†π‘‘π‘Žπ‘Ÿ2                                                                                   π‘†π‘‘π‘Žπ‘Ÿ1
                                              G, 𝑑𝑠, 𝜏 ⊩ π‘‘π‘’βˆ—                                                  G, βˆ…, 𝜏 ⊩ π‘‘π‘’βˆ—
Table 2
Inference rules for ShEx triple expressions


  A shape assignment 𝜏 for graph G and S is called valid if for every node 𝑛 in G and every
shape expression label l defined in S, if 𝑛@l ∈ 𝜏, then G, 𝑛, 𝜏 ⊨ @l.
  According to Boneva et al [7], for every graph G, there exists a unique maximal valid shape
assignment 𝜏max such that if 𝜏 is a valid shape assignment for G and S, then 𝜏 βŠ† 𝜏max .


3. RDF-Star and ShEx-Star
RDF-Star has been proposed as an extension of RDF where the subjects and objects can be
triples. We present a formal definition of RDF-Star based on [10]:

Definition 3 (RDF-Star). An RDF-Star triple is a tuple 𝑑 defined recursively as follows: Any
RDF triple 𝑑 ∈ (I βˆͺ B) Γ— I Γ— (I βˆͺ B βˆͺ Lit) is an RDF-Star triple; and given RDF-Star triples 𝑑 and 𝑑 β€²
and RDF terms 𝑠 ∈ (I βˆͺ B), 𝑝 ∈ I and π‘œ ∈ (I βˆͺ B βˆͺ Lit), the tuples (β‰ͺ 𝑑 ≫, 𝑝, π‘œ), (𝑠, 𝑝, β‰ͺ 𝑑 β€² ≫) and
(β‰ͺ 𝑑 ≫, 𝑝, β‰ͺ 𝑑 β€² ≫) are RDF-Star triples. An RDF-Star graph is a set of RDF-Star triples.

Example 4 (Example of an RDF-Star graph in Turtle-Star notation). The following snippet
contains a simple RDF-Star graph with two nodes :a and :b .

 prefix : 

 :a :name "Alice" .
 << :a :knows :b >> :certainty 0.5 .
 :b :firstname "Robert", "Julius" ;
    :lastname "Smith" .



                                          :knows                            :certainty
                              :a                                    :b                     "0.5"
                               :name               :firstname             :firstname       :lastname

                            "Alice"       β€œRobert"              β€œJulius"             β€œSmith"

Figure 2: Basic RDF-Star example


   We can extend ShEx to support ShEx-Star by adding the following declaration to the definition
of triple expressions 𝑑𝑒:
    𝑑𝑒 ::= . . .                 Same definitions as in 2
                       𝑝
         |        β‰ͺ    βˆ’
                       β†’ 𝑠𝑒 ≫{|𝑑𝑒|}           Outgoing Triple term constraint with predicate 𝑝
                        𝑝
         |        β‰ͺ 𝑠𝑒 βˆ’
                       β†’      ≫{|𝑑𝑒|}         Incoming triple term constraint with predicate 𝑝
Example 5 (Example of a ShEx-Star schema). A ShEx-Star schema that describes the RDF
graph presented in example 4 can be defined as:
                                   π‘›π‘Žπ‘šπ‘’                𝑓 π‘–π‘ π‘‘π‘›π‘Žπ‘šπ‘’                π‘™π‘Žπ‘ π‘‘π‘›π‘Žπ‘šπ‘’
    𝛿(π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›)      =    {    ( βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘” ∣         βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”*; βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”);
                                      π‘˜π‘›π‘œπ‘€π‘                         π‘π‘’π‘Ÿπ‘‘π‘Žπ‘–π‘›π‘‘π‘¦
                             β‰ͺ      βˆ’βˆ’βˆ’βˆ’βˆ’β†’ @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› ≫{| βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π·π‘’π‘π‘–π‘šπ‘Žπ‘™|}*
                        }
                               𝑝
   The expression β‰ͺ βˆ’    β†’ 𝑠𝑒 ≫{|𝑑𝑒|} describes a triple term whose predicate is 𝑝 and whose
object conforms to the shape expression 𝑠𝑒 and that can be the subject of triples conforming to
triple expression 𝑑𝑒. The formal semantics can be described as:

                   𝑑𝑠 = {⟨β‰ͺ 𝑑 ≫, 𝑝, π‘¦βŸ©}         G, 𝑦, 𝜏 ⊨ 𝑠𝑒       π‘›π‘’π‘–π‘”β„Žπ‘ (β‰ͺ 𝑑 ≫, G) = 𝑑𝑠 β€²         G, 𝑑𝑠 β€² , 𝜏 ⊩ 𝑑𝑒
         𝑇 𝑇 𝐢1
                                                                   𝑝
                                                  G, 𝑑𝑠, 𝜏 ⊩β‰ͺ      βˆ’
                                                                   β†’ 𝑠𝑒 ≫ {|𝑑𝑒|}

                   𝑑𝑠 = {⟨π‘₯, 𝑝, β‰ͺ 𝑑 β‰«βŸ©}         G, π‘₯, 𝜏 ⊨ 𝑠𝑒       π‘›π‘’π‘–π‘”β„Žπ‘ (β‰ͺ 𝑑 ≫, G) = 𝑑𝑠 β€²         G, 𝑑𝑠 β€² , 𝜏 ⊩ 𝑑𝑒
         𝑇 𝑇 𝐢2
                                                                    𝑝
                                                  G, 𝑑𝑠, 𝜏 ⊩β‰ͺ 𝑠𝑒 βˆ’
                                                                 β†’        ≫ {|𝑑𝑒|}
Table 3
Inference rules for ShEx-Star new triple term expressions




4. ShEx-N: Describing nodes that act as properties
In the RDF data model, predicates can also act as subjects or objects or triples. This aspect is
not taken into account in traditional ShEx, where the shapes describe the topology of nodes
without considering their potential role as predicates.
Example 6 (Example of an RDF graph a node acting as a property). The following snippet
contains a simple RDF graph where :knows is both a node and a property.

 prefix : 
 prefix skos: 

 :a :name "Alice" ;
    :knows :b .
 :b :firstname "Robert", "Julius" ;
    :lastname "Smith" .
 :knows skos:related :Friendship .



                                                   :Friendship
                                          skos:related
                                 :knows
                    :a                                      :b
                      :name                :firstname          :firstname               :lastname

                 "Alice"         β€œRobert"               β€œJulius"              β€œSmith"

Figure 3: RDF example with a property as a node


   In order to capture these appearances in a single shape, it is possible to add a new kind of
triple expression:
    𝑑𝑒 ::= . . .          Same definitions as in 2
          |   𝑠𝑒1 βˆ’β†’ 𝑠𝑒2 Triple constraint with focus node acting as predicate and subject
                          conforming to 𝑠𝑒1 and object conforming to 𝑠𝑒2
   The semantics of triple term constraints can be defined as:

                                𝑑𝑠 = {βŸ¨π‘ , π‘₯, π‘œβŸ©}   G, 𝑠, 𝜏 ⊨ 𝑠𝑒1      G, π‘œ, 𝜏 ⊨ 𝑠𝑒2
                         𝑁 𝑃1
                                               G, 𝑑𝑠, 𝜏 ⊩ 𝑠𝑒1 βˆ’
                                                              β†’ 𝑠𝑒2
Table 4
Inference rules for ShEx-N


Example 7 (Example of a ShEx-N schema). The following ShEx-N schema defines the shape
𝐹 π‘Ÿπ‘–π‘’π‘›π‘ β„Žπ‘–π‘π‘ƒπ‘Ÿπ‘œπ‘π‘’π‘Ÿπ‘‘π‘¦ which validates the node :knows in example 6:
                                              π‘ π‘˜π‘œπ‘ βˆΆπ‘Ÿπ‘’π‘™π‘Žπ‘‘π‘’π‘‘
    𝛿(𝐹 π‘Ÿπ‘–π‘’π‘›π‘‘π‘†β„Žπ‘–π‘π‘ƒπ‘Ÿπ‘œπ‘π‘’π‘Ÿπ‘‘π‘¦)         =   {     βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ [∢ 𝐹 π‘Ÿπ‘–π‘’π‘›π‘‘π‘ β„Žπ‘–π‘] ;
                                            @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› βˆ’β†’ @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›
                                       }
                                              βˆΆπ‘›π‘Žπ‘šπ‘’
              𝛿(π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›)            =   {      βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”
                                              βˆΆπ‘“ π‘–π‘Ÿπ‘ π‘‘π‘›π‘Žπ‘šπ‘’           βˆΆπ‘™π‘Žπ‘ π‘‘π‘›π‘Žπ‘šπ‘’
                                       ∣      βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”* ;   βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’βˆ’β†’ π‘†π‘‘π‘Ÿπ‘–π‘›π‘” ;
                                              π‘˜π‘›π‘œπ‘€π‘ 
                                              βˆ’βˆ’βˆ’βˆ’βˆ’β†’ @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› *
                                       }

5. Property graphs and PShEx
Property graphs have become popular thanks to several commercial graph databases like Neo4j 3 ,
JanusGraph 4 or Sparksee 5 . A property graph has unique identifiers for each node/edge and
allows to add property-value annotations to each node/edge in the arc as well as type annotations.
The following definition of a property graph follows [11].

Definition 4 (Property graph). Given a set of types T , a set of properties P, and a set of values
V , a property graph G is a tuple ⟨N , E, 𝜌, πœ†π‘› , πœ†π‘’ , 𝜎 ⟩ where N ∩ E = βˆ…, 𝜌 ∢ E ↦ N Γ— N is a total
function, πœ†π‘› ∢ N ↦ 𝐹 𝑖𝑛𝑆𝑒𝑑(T ), πœ†π‘’ ∢ E ↦ T , and 𝜎 ∢ N βˆͺ E Γ— P ↦ 𝐹 𝑖𝑛𝑆𝑒𝑑(V ).

  A property graph is formed by a set of node identifiers N and a set of edges E where 𝜌
associates a pair of nodes (𝑛1 , 𝑛2 ) to every 𝑒 ∈ E where 𝑛1 is the subject and 𝑛2 is the object, πœ†π‘›
associates a set of types for node identifiers (notice that property graphs allow nodes to have
more than one type), πœ†π‘’ associates a types for each edge identifier, and 𝜎 associates a set of
values to pairs (𝑖, 𝑝) such that 𝑖 ∈ N βˆͺ E is a node or edge and 𝑝 ∈ P is a property.

Example 8. As an example, we will represent information that Alice knows Robert with a
certainty of 0.5


  T = {Person, knows} P = {name, certainty} V = {”Alice”, ”Robert”, ”Julius”, ”Smith”, 0.5}
  N = {𝑛1 , 𝑛2 }       E = {π‘Ÿ1 }       𝜌 = π‘Ÿ1 ↦ (𝑛1 , 𝑛2 )
  πœ†π‘› = 𝑛1 ↦ {Person}, 𝑛2 ↦ {Person} πœ†π‘’ = π‘Ÿ1 ↦ knows
   𝜎 = (𝑛1 , π‘›π‘Žπ‘šπ‘’) ↦ {”Alice”} (𝑛2 , 𝑓 π‘–π‘Ÿπ‘ π‘‘π‘›π‘Žπ‘šπ‘’) ↦ {”Robert”, ”Julius”}
        (𝑛2 , π‘™π‘Žπ‘ π‘‘π‘›π‘Žπ‘šπ‘’) ↦ {”Smith”} (π‘Ÿ1 , π‘π‘’π‘Ÿπ‘‘π‘Žπ‘–π‘›π‘‘π‘¦) ↦ {0.5}

  Figure 4 presents a possible visualization of a property graph.
  We define a ShEx extension called PShEx that can be used to describe and validate Property
graphs. In property graphs, nodes and edges can have associated labels as well as a set of
property/values. In this way, it is necessary to adapt the definition of ShEx to describe pairs
or property/values. PShEx is composed of three main categories: shape expressions (𝑠𝑒) that
    3
      https://neo4j.com/
    4
      https://janusgraph.org/
    5
      https://www.sparsity-technologies.com/#sparksee
                                                                           Human
                   Human
                                                                  firstname: Robert, Julius
                name: Alice        n1            r1         n2
                                                                  lastname: Smith

                                               knows
                                           certainty: 0.5


Figure 4: Example graph visualization of a property graph

describe the shape of nodes, triple expressions (𝑑𝑒) that describe the shape of edge relationships
and property-value expressions (𝑝𝑣𝑠) that describe sets of property/values associated with
node/edge identifiers.

Definition 5 (PShEx schema). A PShEx Schema is a tuple ⟨L, π›ΏβŸ© where L set of shape labels, and
𝛿 ∢ L β†’ S is a total function from labels to shape expressions 𝑠𝑒 ∈ S defined using the abstract
syntax:
     𝑠𝑒 ::= π‘π‘œπ‘›π‘‘π‘‘π‘               Basic boolean condition on set of types 𝑑𝑠 βŠ† T
          |     𝑠𝑒1 AND 𝑠𝑒2     Conjunction
          |     @l              Shape label reference for l ∈ L
          |     𝑝𝑣𝑠             Property-value specifiers of a node
          |     CLOSED {𝑑𝑒}     Closed shape
          |     {𝑑𝑒}            Open shape
     𝑑𝑒 ::= 𝑑𝑒1 ; 𝑑𝑒2           Each of 𝑑𝑒1 and 𝑑𝑒2
          |     𝑑𝑒1 ∣ 𝑑𝑒2       Some of 𝑑𝑒1 or 𝑑𝑒2
          |     π‘‘π‘’βˆ—             Zero or more 𝑑𝑒
                   𝑝
           |      βˆ’
                  β†’ @l 𝑝𝑣𝑠          Triple constraint with property type 𝑝
                                    whose nodes satisfy the shape l and property-values 𝑝𝑣𝑠
    𝑝𝑣𝑠   ::=   βŒŠπ‘π‘ βŒ‹                Open property-value specifiers 𝑝𝑠
            |   βŒˆπ‘π‘ βŒ‰                Closed property-value specifiers 𝑝𝑠
    𝑝𝑠    ::=   𝑝𝑠1 , 𝑝𝑠2           Each of 𝑝𝑠1 and 𝑝𝑠2
            |   𝑝𝑠1 ∣ 𝑝𝑠2           OneOf of 𝑝𝑠1 or 𝑝𝑠2
            |   π‘π‘ βˆ—                 zero of more 𝑝𝑠
            |   𝑝 ∢ π‘π‘œπ‘›π‘‘π‘£           Property 𝑝 with value conforming to π‘π‘œπ‘›π‘‘π‘£
                                    π‘π‘œπ‘›π‘‘π‘£π‘  is a boolean condition on sets of values 𝑣𝑠 βŠ† V
Example 9. As an example, we can define a PShEx schema that describes the property graph
from example 8 where β„Žπ‘Žπ‘ π‘‡ 𝑦𝑝𝑒𝑑 is a condition that is satisfied when the set of types of a node
contains the type 𝑑, i.e. β„Žπ‘Žπ‘ π‘‡ 𝑦𝑝𝑒𝑑 (𝑣𝑠) = true if 𝑑 ∈ 𝑣𝑠 and π‘†π‘‘π‘Ÿπ‘–π‘›π‘”, π·π‘’π‘π‘–π‘šπ‘Žπ‘™ are conditions on the
values that are satisfied when the values have the corresponding type.
        L       = { π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›}
    𝛿(π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘›) = β„Žπ‘Žπ‘ π‘‡ 𝑦𝑝𝑒𝐻 π‘’π‘šπ‘Žπ‘› AND
                     βŒŠπ‘›π‘Žπ‘šπ‘’ ∢ π‘†π‘‘π‘Ÿπ‘–π‘›π‘” ∣ 𝑓 π‘–π‘Ÿπ‘ π‘‘π‘›π‘Žπ‘šπ‘’ ∢ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”βˆ— , π‘™π‘Žπ‘ π‘‘π‘›π‘Žπ‘šπ‘’ ∢ π‘†π‘‘π‘Ÿπ‘–π‘›π‘”βŒ‹ AND
                           π‘˜π‘›π‘œπ‘€π‘ 
                       {   βˆ’βˆ’βˆ’βˆ’βˆ’β†’ @π‘ƒπ‘’π‘Ÿπ‘ π‘œπ‘› βŒŠπ‘π‘’π‘Ÿπ‘‘π‘Žπ‘–π‘›π‘‘π‘¦ ∢ π·π‘’π‘π‘–π‘šπ‘Žπ‘™βŒ‹* }
   In order to define the semantic specification of PShEx we will need to define the neighborhood
of a node in a property graph.
   The neighbors of a node 𝑛 ∈ N in a property graph G = ⟨N , E, 𝜌, πœ†π‘› , πœ†π‘’ , 𝜎 ⟩ are defined as
π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛) = {(𝑛, 𝑝, 𝑦, 𝑣𝑠) ∣ βˆƒπ‘£ ∈ E such that 𝜌(𝑣) = (𝑛, 𝑦) ∧ πœ†π‘’ (𝑣) = 𝑝 ∧ 𝑣𝑠 = {(π‘˜, 𝑣) ∣ 𝜎 (π‘˜, 𝑣) =
𝑀𝑠 ∧ 𝑣 ∈ 𝑀𝑠}}. For a node 𝑛, we define the property value set as π‘π‘Ÿπ‘œπ‘π‘£π‘ (𝑛) = {(π‘˜, 𝑣) ∣ 𝜎 (π‘˜, 𝑣) =
𝑀𝑠 ∧ 𝑣 ∈ 𝑀𝑠}
   The semantic specification of PShEx can be defined in a similar way to the ShEx one. Given
a property graph G, and a shape assignment 𝜏, a node identifier 𝑛 ∈ N conforms with a shape
expression 𝑠𝑒, which is represented as G, 𝑛, 𝜏 ⊨ 𝑠𝑒 and follows the rules presented in 5 where
π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒) is the set of edge labels (or predicates) that appear in a triple expression 𝑑𝑒 and can be
defined as:
                    πœ†π‘› (𝑛) = 𝑣𝑠      π‘π‘œπ‘›π‘‘π‘‘π‘  (𝑣𝑠) = π‘‘π‘Ÿπ‘’π‘’                       G, 𝑛, 𝜏 ⊨ 𝑠𝑒1    G, 𝑛, 𝜏 ⊨ 𝑠𝑒2
          πΆπ‘œπ‘›π‘‘π‘‘π‘                                                     𝐴𝑁 𝐷
                             G, 𝑛, 𝜏 ⊨ π‘π‘œπ‘›π‘‘π‘‘π‘                                      G, 𝑛, 𝜏 ⊨ 𝑠𝑒1 AND 𝑠𝑒2

                                                 π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛, G) = 𝑑𝑠       G, 𝑑𝑠, 𝜏 ⊩ 𝑠 β€²
                                  πΆπ‘™π‘œπ‘ π‘’π‘‘π‘†β„Žπ‘Žπ‘π‘’
                                                          G, 𝑛, 𝜏 ⊨ CLOSED {𝑑𝑒}

                                  𝑑𝑠 = {⟨π‘₯, 𝑝, π‘¦βŸ© ∈ π‘›π‘’π‘–π‘”β„Žπ‘ (𝑛, G) ∣ 𝑝 ∈ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒)}         G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒
                   π‘‚π‘π‘’π‘›π‘†β„Žπ‘Žπ‘π‘’
                                                             G, 𝑛, 𝜏 ⊨ {𝑑𝑒}

                        𝛿(l) = 𝑠𝑒       G, 𝑛, 𝜏 ⊨ 𝑠𝑒                    π‘π‘Ÿπ‘œπ‘π‘£π‘ (𝑛) = 𝑠         G, 𝑠, 𝜏 ⊒ 𝑝𝑣𝑠
           π‘†β„Žπ‘Žπ‘π‘’π‘…π‘’π‘“                                              𝑃𝑉 𝑆
                               G, 𝑛, 𝜏 ⊨ @𝑙                                        G, 𝑛, 𝜏 ⊨ 𝑝𝑣𝑠
Table 5
Rules for PShEx shape expressions

    π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ; 𝑑𝑒2 )    =     π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ) βˆͺ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒2 )
    π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ∣ 𝑑𝑒2 )    =     π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒1 ) βˆͺ π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒2 )
              𝑝
    π‘π‘Ÿπ‘’π‘‘π‘ ( βˆ’  β†’ 𝑑𝑒) = {𝑝}
    π‘π‘Ÿπ‘’π‘‘π‘ (π‘‘π‘’βˆ—)          = π‘π‘Ÿπ‘’π‘‘π‘ (𝑑𝑒)
    π‘π‘Ÿπ‘’π‘‘π‘ (πœ–)            = βˆ…
  As in the case of ShEx, the previous definition uses a second conformance relation defined
on sets of triples 𝑑𝑠 instead of nodes 𝑛. The set of neighborhood nodes 𝑑𝑠 from a property graph
G conforms to a triple expression 𝑑𝑒 with shape assignment 𝜏, written G, 𝑑𝑠, 𝜏 ⊩ 𝑠, as defined by
the inference rules represented in table 6.
  In the case of PShEx we declare a new conformance relationship G, 𝑠, 𝜏 ⊒ π‘žπ‘  between a graph
G a set 𝑠 ∈ 𝑃 Γ— 𝑉 of property-value elements, a shape assignment 𝜏 and a property-value specifier
𝑝𝑣𝑠 whose rules are defined in table 7 where π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑣𝑠) is the set of properties that appear in a
property-value specifier 𝑝𝑠 and can be defined as:
    π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠1 , 𝑝𝑠2 ) = π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠1 ) βˆͺ π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠2 )
    π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠1 ∣ 𝑝𝑠2 ) = π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠1 ) βˆͺ π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠2 )
    π‘π‘Ÿπ‘œπ‘π‘ (π‘π‘ βˆ—)            = π‘π‘Ÿπ‘’π‘‘π‘ (𝑝𝑠)
    π‘π‘Ÿπ‘œπ‘π‘ (𝑝 ∢ π‘π‘œπ‘›π‘‘π‘£ ) = {𝑝}
  As in the case of ShEx, the semantics of ShEx schemas can be defined independently on shape
assignments. A shape assignment 𝜏 for graph G and S is called valid if for every node 𝑛 in G
and every shape expression label l defined in S, if 𝑛@l ∈ 𝜏, then G, 𝑛, 𝜏 ⊨ @l.
                                  (𝑑𝑠1 , 𝑑𝑠2 ) ∈ π‘π‘Žπ‘Ÿπ‘‘(𝑑𝑠)       G, 𝑑𝑠1 , 𝜏 ⊩ 𝑑𝑒1       G, 𝑑𝑠2 , 𝜏 ⊩ 𝑑𝑒2
                       πΈπ‘Žπ‘β„Žπ‘‚π‘“
                                                           G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ; 𝑑𝑒2

                                    G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1                                    G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒2
                       𝑂𝑛𝑒𝑂𝑓1                                        𝑂𝑛𝑒𝑂𝑓2
                                  G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ∣ 𝑑𝑒2                             G, 𝑑𝑠, 𝜏 ⊩ 𝑑𝑒1 ∣ 𝑑𝑒2

                                         𝑑𝑠 = {⟨π‘₯, 𝑝, 𝑦, π‘ βŸ©}         G, 𝑦, 𝜏 ⊨ @l          G, 𝑠, 𝜏 ⊒ π‘žπ‘ 
                     𝑇 π‘Ÿπ‘–π‘π‘™π‘’πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘
                                                                            𝑝
                                                             G, 𝑑𝑠, 𝜏 ⊩     βˆ’
                                                                            β†’ @l π‘žπ‘ 

                                                 π‘†π‘‘π‘Žπ‘Ÿ1
                                                           G, βˆ…, 𝜏 ⊩ π‘‘π‘’βˆ—

                                 (𝑑𝑠1 , 𝑑𝑠2 ) ∈ π‘π‘Žπ‘Ÿπ‘‘(𝑑𝑠)       G, 𝑑𝑠1 , 𝜏 ⊩ 𝑑𝑒       G, 𝑑𝑠2 , 𝜏 ⊩ π‘‘π‘’βˆ—
                        π‘†π‘‘π‘Žπ‘Ÿ2
                                                           G, 𝑑𝑠, 𝜏 ⊩ π‘‘π‘’βˆ—

Table 6
Rules for PShEx triple expressions
                  𝑠 β€² = {(𝑝, 𝑣) ∈ 𝑠|𝑝 ∈ π‘π‘Ÿπ‘œπ‘π‘ (𝑝𝑠)}           G, 𝑠 β€² , 𝜏 ⊒ 𝑝𝑠                        G, 𝑠, 𝜏 ⊒ 𝑝𝑠
      𝑂𝑝𝑒𝑛𝑃𝑉 𝑠                                                                        πΆπ‘™π‘œπ‘ π‘’π‘ƒπ‘‰ 𝑠
                                     G, 𝑠, 𝜏 ⊒ βŒŠπ‘π‘ βŒ‹                                               G, 𝑠, 𝜏 ⊒ βŒˆπ‘π‘ βŒ‰

                                                  G, 𝑠, 𝜏 ⊒ 𝑝𝑠1           G, 𝑠, 𝜏 ⊒ 𝑝𝑠2
                                    πΈπ‘Žπ‘β„Žπ‘‚π‘“ 𝑃𝑠
                                                            G, 𝑠, 𝜏 ⊒ 𝑝𝑠1 , 𝑝𝑠2

                                      G, 𝑠, 𝜏 ⊒ 𝑝𝑠1                                    G, 𝑠, 𝜏 ⊒ 𝑝𝑠2
                     𝑂𝑛𝑒𝑂𝑓 𝑃𝑠1                                     𝑂𝑛𝑒𝑂𝑓 𝑃𝑠2
                                   G, 𝑠, 𝜏 ⊒ 𝑝𝑠1 ∣ 𝑝𝑠2                              G, 𝑠, 𝜏 ⊒ 𝑝𝑠1 ∣ 𝑝𝑠2

                                                 (𝑠1 , 𝑠2 ) ∈ π‘π‘Žπ‘Ÿπ‘‘(𝑠)           G, 𝑠1 , 𝜏 ⊒ 𝑝𝑠    G, 𝑠2 , 𝜏 ⊒ π‘π‘ βˆ—
      π‘†π‘‘π‘Žπ‘Ÿπ‘ƒπ‘ 1                         π‘†π‘‘π‘Žπ‘Ÿπ‘ƒπ‘ 2
                 G, βˆ…, 𝜏 ⊒ π‘π‘ βˆ—                                              G, 𝑠, 𝜏 ⊒ π‘π‘ βˆ—

                                                  𝑠 = {(𝑝, 𝑀)}            π‘π‘œπ‘›π‘£π‘£ (𝑀) = true
                                π‘ƒπ‘Ÿπ‘œπ‘π‘’π‘Ÿπ‘‘π‘¦π‘‰ π‘Žπ‘™π‘’π‘’
                                                             G, 𝑠, 𝜏 ⊒ 𝑝 ∢ π‘π‘œπ‘›π‘‘π‘£
Table 7
Rules for PShEx property-value specifiers

6. Related work
ShEx was initially proposed in 2014 [2] as a concise and human readable language to describe
and validate RDF. It was based on a variant of regular expressions called Regular Bag Expres-
sions [12] which also supports recursive shapes. Combining negation with recursive shapes
was later studied in [9] where a well founded formal semantics for ShEx for proposed based
on stratification. Our definition of ShEx is based on that work, although we omitted negation,
disjunction and EXTRA declarations of shape expressions in this paper. After ShEx was pro-
posed, a W3C Data Shapes working group was chatered whose result was SHACL, proposed
as a recommendation in 2017 [3]. The specification of SHACL didn’t have an abstract syntax
and left the semantics of recursive shapes as an implementation dependent feature enabling the
appearance of several proposals that define an abstract syntax and add semantics for SHACL
with negation and recursion [13, 14, 15, 16]. A comparison between both ShEx and SHACL was
provided in [17] while in [18], a simple language was defined that can be used as a common
subset of both. We consider that some of our extensions to ShEx could also be applied to SHACL.
   The approach followed in this paper to extend ShEx was started in this paper [19] where we
had already proposed an initial version of PShEx and WShEx [20], another extension of ShEx to
support the Wikibase data model. WShEx is conceptually similar to PShEx although a distinct
feature of the Wikidbase data model is that the values of properties can also be nodes in the
graph, which can be considered as a generalized property graphs model. This model was called
MARS (Multi-Attributed Relational Structures) in [21].
   There are several proposals for property graphs schemas. GQL is an upcoming ISO standard
(ISO39075) 6 which is currently being developed and addresses the property graph model. In
order to provide support for GQL, PG-Schema [22] was proposed as a simple schema language
for property graphs. PG-Schema does not support cardinality constraints on edges, which
could be simulated using PG-Keys [23]. In [24], the authors propose a common framework for
property graph schema languages based on first order logic rules which supports cardinality
constraints. The closest proposal to PShEx would be the Property Graph Shapes Language
(ProGS) [11] although that language is based on SHACL and some of the differences SHACL
vs ShEx could also be applied to ProGS vs PShEx. For example, PShEx doesn’t have property
path expressions and ProGS doesn’t have regular bag expressions. Another difference is that
ProGS includes negation and recursion while in the version of PShEx included in this paper we
omitted negation. Comparison between RDF-Star and property graphs at the data model have
already been studied. In [25] proposes a common model for RDF, RDF-Star and property graphs
that they call statement graph, which is inspired by the OneGraph [26] vision. The conversion
between property graphs and RDF/RDF-Star is also studied in [6].


7. Conclusions and future work
We have presented three extensions to ShEx for different types of knowledge graphs: ShEx-*
adds support for RDF-Star, ShEx-N adds a constraint to describe nodes that act as properties,
and PShEx can be used to describe and validate property graphs. We presented an abstract
syntax and formal semantics for each of the variants.
   There are several lines of future work. On the theoretical level, it will be necessary to research
the computational complexity implications of these features as well as the combination of these
features with other features from ShEx like negation, disjunction, EXTRA declarations, and even
the potential integration of all the features together in a single language. On the implementation
level: it will be necessary to propose a concrete compact syntax for each variant that can be
useful by data model engineers as well as devise algorithms that can be used to check the
conformance of graphs to the corresponding schemas. Although we used ShEx in this paper,
another line of future work would be to check which of the features proposed in this paper
could also be applied to SHACL.


    6
        https://www.iso.org/standard/76120.html
Acknowledgments
This work has been partially funded by the Project ANGLIRU: ANGLIRU: Applying kNowledge
Graphs to research data interoperabiLIty and ReUsability, code: PID2020-117912RB. The discus-
sions held during our participation in Dagstuhl seminar 24102 Shapes in graph data: theory
and implementation helped us to write some of the ideas included in this paper.


References
 [1] A. Hogan, E. Blomqvist, M. Cochez, C. d’Amato, G. de Melo, C. GutiΓ©rrez, S. Kirrane,
     J. E. Labra Gayo, R. Navigli, S. Neumaier, A.-C. Ngonga Ngomo, A. Polleres, S. M. Rashid,
     A. Rula, L. Schmelzeisen, J. F. Sequeda, S. Staab, A. Zimmermann, Knowledge Graphs,
     number 22 in Synthesis Lectures on Data, Semantics, and Knowledge, Springer, 2021. URL:
     https://kgbook.org/. doi:10.2200/S01125ED1V01Y202109DSK022 .
 [2] E. Prud’hommeaux, J. E. Labra Gayo, H. Solbrig, Shape Expressions: An RDF Validation
     and Transformation Language, in: H. Sack, A. Filipowska, J. Lehmann, S. Hellmann (Eds.),
     Proceedings of the 10th International Conference on Semantic Systems, SEMANTICS
     2014, Leipzig, Germany, September 4-5, 2014, ACM Press, 2014, pp. 32–40. doi:10.1145/
     2660517.2660523 .
 [3] H. Knublauch, D. Kontokostas, Shapes Constraint Language (SHACL), W3C Recommen-
     dation 20 July 2017, W3C Recommendation, World Wide Web Consortium, 2017. URL:
     https://www.w3.org/TR/2017/REC-shacl-20170720/.
 [4] R. Cyganiak, D. Wood, M. Lanthaler, RDF-star and SPARQL-star, Draft Community Group
     Report, World Wide Web Consortium, 2021. URL: https://w3c.github.io/rdf-star/cg-spec.
 [5] O. hartig, P.-A. Champin, G. Kellogg, A. Seaborne, RDF 1.2 Concepts and Abstract Syntax,
     W3C Working Draft, World Wide Web Consortium, 2024. URL: https://www.w3.org/TR/
     rdf12-concepts/.
 [6] S. Khayatbashi, S. Ferrada, O. Hartig, Converting property graphs to rdf: a preliminary
     study of the practical impact of different mappings, in: Proceedings of the 5th ACM
     SIGMOD Joint International Workshop on Graph Data Management Experiences and
     Systems (GRADES) and Network Data Analytics (NDA), SIGMOD/PODS ’22, ACM, 2022.
     doi:10.1145/3534540.3534695 .
 [7] I. Boneva, J. E. Labra Gayo, E. G. Prud’hommeaux, Semantics and Validation of Shapes
     Schemas for RDF, in: C. d’Amato, M. FernΓ‘ndez, V. A. M. Tamma, F. LΓ©cuΓ©, P. CudrΓ©-
     Mauroux, J. F. Sequeda, C. Lange, J. Heflin (Eds.), The Semantic Web - ISWC 2017 - 16th
     International Semantic Web Conference, Vienna, Austria, October 21-25, 2017, Proceedings,
     Part I, volume 10587 of Lecture Notes in Computer Science, Springer, 2017, pp. 104–120.
 [8] E. Prud’hommeaux, I. Boneva, J. E. Labra Gayo, G. Kellog, Shape Expressions Language
     2.0, 2017. URL: https://shexspec.github.io/spec/.
 [9] I. Boneva, J. E. Labra Gayo, E. Prud’hommeaux, Semantics and validation of shapes schemas
     for rdf, in: International Semantic Web Conference, 2017.
[10] O. Hartig, Foundations of RDF* and SPARQL* – An Alternative Approach to Statement-
     Level Metadata in RDF, in: J. L. Reutter, D. Srivastava (Eds.), Proceedings of the 11th
     Alberto Mendelzon International Workshop on Foundations of Data Management and the
     Web, Montevideo, Uruguay, June 7-9, 2017, volume 1912 of CEUR Workshop Proceedings,
     Sun SITE Central Europe (CEUR), 2017. URL: http://ceur-ws.org/Vol-1912/paper12.pdf.
[11] P. Seifer, R. LΓ€mmel, S. Staab, ProGS: Property Graph Shapes Language, in: International
     Semantic Web Conference, volume 12922, Springer, 2021, pp. 392–401. doi:https://doi.
     org/10.1007/978- 3- 030- 88361- 4_23 . arXiv:2107.05566 .
[12] S. Staworko, I. Boneva, J. E. Labra Gayo, S. Hym, E. G. Prud’hommeaux, H. R. Solbrig,
     Complexity and Expressiveness of ShEx for RDF, in: 18th International Conference on
     Database Theory, ICDT 2015, volume 31 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum
     fuer Informatik, 2015, pp. 195–211.
[13] J. Corman, J. L. Reutter, O. Savković, Semantics and Validation of Recursive SHACL,
     in: D. VrandečiΔ‡, K. Bontcheva, M. C. SuΓ‘rez-Figueroa, V. Presutti, I. Celino, M. Sabou,
     L. Kaffee, E. Simperl (Eds.), The Semantic Web - ISWC 2018 - 17th International Semantic
     Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part I, volume
     11136 of Lecture Notes in Computer Science, Springer, 2018, pp. 318–336.
[14] M. Andresel, J. Corman, M. Ortiz, J. L. Reutter, O. Savkovic, M. Simkus, Stable model
     semantics for recursive shacl, in: Proceedings of The Web Conference 2020, WWW ’20,
     ACM, 2020. doi:10.1145/3366423.3380229 .
[15] B. Bogaerts, M. Jakubowski, Fixpoint semantics for recursive SHACL, in: A. Formisano, Y. A.
     Liu, B. Bogaerts, A. Brik, V. Dahl, C. Dodaro, P. Fodor, G. L. Pozzato, J. Vennekens, N. Zhou
     (Eds.), Proceedings 37th International Conference on Logic Programming (Technical Com-
     munications), ICLP Technical Communications 2021, Porto (virtual event), 20-27th Septem-
     ber 2021, volume 345 of EPTCS, 2021, pp. 41–47. URL: https://doi.org/10.4204/EPTCS.345.14.
     doi:10.4204/EPTCS.345.14 .
[16] A. Chmurovic, M. Ε imkus, Well-founded semantics for recursive shacl, in: CEUR Workshop
     Proceedings :, number 3203 in CEUR Workshop proceedings, 2022, pp. 2–13. URL: http:
     //ceur-ws.org/Vol-3203/.
[17] J. E. Labra Gayo, E. Prud’hommeaux, I. Boneva, D. Kontokostas, Validating RDF Data,
     volume 7 of Synthesis Lectures on the Semantic Web: Theory and Technology, Morgan &
     Claypool, 2017. URL: https://doi.org/10.2200/s00786ed1v01y201707wbe016. doi:10.2200/
     s00786ed1v01y201707wbe016 .
[18] J. E. Labra Gayo, H. GarcΓ­a-GonzΓ‘lez, D. FernΓ‘ndez-Alvarez, E. Prud’hommeaux, Challenges
     in RDF Validation, in: G. Alor-HernΓ‘ndez, J. L. SΓ‘nchez-Cervantes, A. RodrΓ­guez-GonzΓ‘lez,
     R. Valencia-GarcΓ­a (Eds.), Current Trends in Semantic Web Technologies: Theory and
     Practice, Studies in Computational Intelligence, Springer, 2019, pp. 121–151. doi:10.1007/
     978- 3- 030- 06149- 4_6 .
[19] J. E. L. Gayo, Creating knowledge graphs subsets using shape expressions, 2021.
     arXiv:2110.11709 .
[20] J.-E. Labra-Gayo, Wshex: A language to describe and validate wikibase entities, in:
     L. Kaffee, S. Razniewski, G. Amaral, K. S. Alghamdi (Eds.), Proceedings of the 3rd Wiki-
     data Workshop 2022 co-located with the 21st International Semantic Web Conference
     (ISWC2022), Virtual Event, Hanghzou, China, October 2022, volume 3262 of CEUR Work-
     shop Proceedings, CEUR-WS.org, 2022. URL: https://ceur-ws.org/Vol-3262/paper3.pdf.
[21] M. Marx, M. KrΓΆtzsch, V. Thost, Logic on MARS: ontologies for generalised property
     graphs, in: C. Sierra (Ed.), Proceedings of the 26th International Joint Conference on
     Artificial Intelligence (IJCAI’17), International Joint Conferences on Artificial Intelligence,
     2017, pp. 1188–1194. doi:10.24963/ijcai.2017/165 .
[22] R. Angles, A. Bonifati, S. Dumbrava, G. Fletcher, A. Green, J. Hidders, B. Li, L. Libkin,
     V. Marsault, W. Martens, F. Murlak, S. Plantikow, O. Savkovic, M. Schmidt, J. Sequeda,
     S. Staworko, D. Tomaszuk, H. Voigt, D. Vrgoc, M. Wu, D. Zivkovic, Pg-schema: Schemas
     for property graphs, Proceedings of the ACM on Management of Data 1 (2023) 1–25.
     doi:10.1145/3589778 .
[23] R. Angles, A. Bonifati, S. Dumbrava, G. Fletcher, K. W. Hare, J. Hidders, V. E. Lee, B. Li,
     L. Libkin, W. Martens, F. Murlak, J. Perryman, O. Savković, M. Schmidt, J. Sequeda,
     S. Staworko, D. Tomaszuk, Pg-keys: Keys for property graphs, in: Proceedings of
     the 2021 International Conference on Management of Data, SIGMOD/PODS ’21, ACM,
     2021. doi:10.1145/3448016.3457561 .
[24] N. Beeren, G. Fletcher, A formal design framework for practical property graph
     schema languages, in: J. Stoyanovich, J. Teubner, N. Mamoulis, E. Pitoura, J. MΓΌhlig,
     K. Hose, S. S. Bhowmick, M. Lissandrini (Eds.), Proceedings 26th International Confer-
     ence on Extending Database Technology, EDBT 2023, Ioannina, Greece, March 28-31,
     2023, OpenProceedings.org, 2023, pp. 478–484. URL: https://doi.org/10.48786/edbt.2023.40.
     doi:10.48786/EDBT.2023.40 .
[25] E. Gelling, G. Fletcher, M. Schmidt, Bridging graph data models: Rdf, rdf-star, and property
     graphs as directed acyclic graphs, CoRR abs/2304.13097 (2023). URL: https://doi.org/10.
     48550/arXiv.2304.13097. doi:10.48550/ARXIV.2304.13097 . arXiv:2304.13097 .
[26] O. Lassila, M. Schmidt, O. Hartig, B. Bebee, D. Bechberger, W. Broekema, A. Khandelwal,
     K. Lawrence, C. M. Lopez Enriquez, R. Sharda, B. Thompson, The onegraph vision:
     Challenges of breaking the graph model lock-in1, Semantic Web 14 (2022) 125–134.
     doi:10.3233/sw- 223273 .