Shape Expressions (ShEx) has been proposed as a concise and human-readable language to describe and validate RDF. Inspired by regular expressions, it ofers 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.
CEUR ceur-ws.org
0000-0001-8907-5348 (J. E. Labra-Gayo) CEUR Workshop Proceedings htp:/ceur-ws.org CEUR Workshop Proceedings (CEUR-WS.org) ISN1613-073
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
There has been a proposal for an extension of RDF called RDF-Star [
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.
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 : <http://example.org/> :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 [
1The full specification of ShEx is available at https://shex.io/shex-semantics/ :a :name shape expressions ∈ S is defined using the following abstract syntax: ::= | | | | | | | | | CLOSED {}
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 [
L
= *
ShEx has several concrete syntaxes like a compact syntax (ShExC) and an RDF syntax defined
prefix : <http://example.org/> prefix xsd: <http://www.w3.org/2001/XMLSchema#> :firstname xsd:string * ; :lastname xsd:string );
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 [
1; 2) 1 ∣ 2) −→ ) ()
=
G, , ⊨ ( l) =
G, , ⊨ = {⟨, , ⟩
∈ ℎ(, = ( = ( = {} = () = ∅ 1) ∪ ( 1) ∪ ( 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
1 2 ℎ = {⟨, , ⟩}
G, , ⊩
G, , ⊩ 1 1 G, , ⊩ 1 ∣ 2
G, , ⊨ not constrained by the shape (rule ℎ consider the whole neighborhood of the node (rule ℎ ).
). Conformance to a closed shape requires to
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
According to Boneva et al [
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 [
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:
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 2
G, , ⊩≪ G, , ⊩≪ −→ ≫ {||} −→
≫ {||} = {⟨, , ≪ ≫⟩}
G, , ⊨ ℎ(≪ ≫,
G) = ′
G, ′, ⊩ Inference rules for ShEx-Star new triple term expressions
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 : <http://example.org/> prefix skos: <http://www.w3.org/2004/02/skos/core#> :a :name "Alice" ;
:knows :b . :b :firstname "Robert", "Julius" ;
:lastname "Smith" . :knows skos:related :Friendship .
:a :name
:Friendship skos:related Example 7 (Example of a ShEx-N schema). The following ShEx-N schema defines the shape ℎ which validates the node :knows in example 6:
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.
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}
name: Alice n 1 r 1 knows describe the shape of nodes, triple expressions ( ) that describe the shape of edge relationships and property-value expressions ( node/edge identifiers.
) that describe sets of property/values associated with 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: * }
AND ::= | | | | | | | | | | | | CLOSED {} ::=
⌊ ∶ ⌋ Basic boolean condition on set of types ⊆ T
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 ℎ contains the type , i.e. ℎ is a condition that is satisfied when the set of types of a node true if ∈ and , are conditions on the values that are satisfied when the values have the corresponding type.
In order to define the semantic specification of PShEx we will need to define the neighborhood of a node in a property graph. 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
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 diferences 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 diference 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 [
We have presented three extensions to ShEx for diferent 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.
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. Kafee, 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 Communications), ICLP Technical Communications 2021, Porto (virtual event), 20-27th September 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. Kafee, S. Razniewski, G. Amaral, K. S. Alghamdi (Eds.), Proceedings of the 3rd Wikidata Workshop 2022 co-located with the 21st International Semantic Web Conference (ISWC2022), Virtual Event, Hanghzou, China, October 2022, volume 3262 of CEUR Workshop 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