#  PG-Schemas: Schemas for Property Graphs

Renzo Angles  Universidad de Talca, IMFDChile ,  Angela Bonifati  Lyon 1 Univ.
& Liris CNRSFrance ,  Stefania Dumbrava  ENSIIE & IP ParisFrance ,  George
Fletcher  Eindhoven Univ. of TechnologyNetherlands ,  Bei Li  GoogleUSA ,  Jan
Hidders  Birkbeck, University of LondonUK ,  Alastair Green  LDBCUK ,  Leonid
Libkin  U. of Edinburgh & RelationalAIUK & France ,  Victor Marsault  LIGM, U
Eiffel, CNRSFrance ,  Wim Martens  University of BayreuthGermany ,  Filip
Murlak  University of WarsawPoland ,  Stefan Plantikow  Neo4jGermany ,  Ognjen
Savković  Free University of BolzanoItaly ,  Michael Schmidt  Amazon Web
ServicesUSA ,  Juan Sequeda  data.worldUSA ,  Sławek Staworko  RelationalAIUSA
,  Dominik Tomaszuk  University of BialystokPoland ,  Hannes Voigt
Neo4jGermany ,  Domagoj Vrgoč  University of Zagreb & PUC ChileCroatia & Chile
,  Mingxi Wu  TigerGraphUSA and  Dušan Živković  Integral Data SolutionsUK

(2023)

###### Abstract.

Property graphs have reached a high level of maturity, witnessed by multiple
robust graph database systems as well as the ongoing ISO standardization
effort aiming at creating a new standard Graph Query Language (GQL). Yet,
despite documented demand, schema support is limited both in existing systems
and in the first version of the GQL Standard. It is anticipated that the
second version of the GQL Standard will include a rich DDL. Aiming to inspire
the development of GQL and enhance the capabilities of graph database systems,
we propose PG-Schemas, a simple yet powerful formalism for specifying property
graph schemas. It features PG-Types with flexible type definitions supporting
multi-inheritance, as well as expressive constraints based on the recently
proposed PG-Keys formalism. We provide the formal syntax and semantics of PG-
Schemas, which meet principled design requirements grounded in contemporary
property graph management scenarios, and offer a detailed comparison of its
features with those of existing schema languages and graph database systems.

property graphs; schemas; graph databases

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
2023 International Conference on Management of Data; June 18–23, 2023;
Seattle, USA††booktitle: Proceedings of the 2023 International Conference on
Management of Data (SIGMOD ’23), June 18–23, 2023, Seattle, USA††price:
15.00††doi: ??††isbn: ??††ccs: Information systems Integrity checking††ccs:
Theory of computation Data modeling††ccs: Theory of computation Database
constraints theory

##  1\. Introduction

Property graphs have come of age. The property graph data model is widely used
in social and transportation networks, biological networks, finance, cyber
security, logistics, and planning domains to represent interconnected multi-
labeled data enhanced with properties given by key/value pairs (Sakr et al.,
2021). Its maturity is reflected in the ongoing efforts by ISO (International
Organization for Standardization)111ISO’s Working Group for Database Languages
is known as ISO/IEC JTC1 SC32 WG3. to create a standard Graph Query Language
GQL, which is expected to appear in 2024 (Deutsch et al., 2022).

Despite the maturity of commercial and open-source property graph databases,
their schema support is limited. Schemas are a fundamental building block for
many data systems. They provide structure to data in a formal language, and
are used in different scenarios. In the _schema-first_ scenario, dominating in
production settings of stable systems, schema is provided during the setup and
plays a _prescriptive role_ , limiting data modifications. In the _flexible
schema_ scenario, suitable for rapid application development and data
integration, schema information comes together with data and plays a
_descriptive role_ , telling users and systems what to expect in the data. In
the _partial schema_ scenario, useful at advanced development stages, the user
wants to enforce a prescriptive schema over stable parts of the data and
maintain a descriptive schema depicting the whole data including its evolving
parts.

A recent survey of graph processing users (Sahu et al., 2020a) revealed that
schema compliance is a highly desirable feature that is lacking in property
graph database systems. Our inspection of eleven property graph engines
reveals a fragmented landscape, where no system offers comprehensive support
for schemas, which should allow the user to impose structure on nodes, edges,
and properties of the underlying graph instances, as well as enforce
constraints. This calls for a unified property graph schema language.

Our goal is to support the endeavours surrounding the GQL standard and
accelerate the development of a future standardized property graph schema
language by presenting a concrete proposal. Our proposal, called PG-Schema,
consolidates and extends discussions arising out of the Property Graph Schema
Working Group of the Linked Data Benchmark Council. This model of providing
recommendations to standards committees has proven successful, as evidenced by
G-CORE (Angles et al., 2018) and PG-Keys (Angles et al., 2021) influencing
GQL222Seven authors of this paper are also members of ISO’s Working Group for
Database Languages..

Person name STRING
---
Customer id INT32
---
CreditCard num STRING
---
Account name STRING
---
Transaction num STRING
---
ownsuseschargesamount DOUBLEdepositswithdraws Figure 1. A diagram of a fraud
graph schema.

⬇

CREATE GRAPH TYPE fraudGraphType STRICT {

(personType: Person {name STRING}),

(customerType: personType & Customer {id INT32}),

(transactionType: Transaction {num STRING}),

(accountType: Account {id INT32}),

...

(:transactionType)

-[activityType: deposit|withdraw]->(:accountType)

}

Figure 2. PG-Schema of a fraud graph schema.

To illustrate the key features required of schemas for property graphs we now
provide a concrete example of a schema in fraud detection, a common
application of graph databases (Gosnell and Broecheler, 2022), and show how
the schema can be used in interactive graph exploration, which in itself is a
common functionality provided by graph databases (Browser, 2022b; Notebooks,
2022; Browser, 2022a; GraphStudioTM, 2022; Gra.fo, 2022). The diagram in
Figure 1 represents a schema describing a fraud graph. This schema is used by
Andrea, who works as a financial compliance officer and utilizes an
interactive graph explorer to investigate fraud. The following user session
highlights how schema information can enhance Andrea’s user experience.

  1. (1)

Andrea opens the graph explorer and connects to the fraud graph, one of the
resources in the data catalog. While establishing the connection, the
application bootstraps by loading schema information.

  2. (2)

Andrea first seeks to identify pairs of suspicious customers. Being aware of
the schema, the graph explorer leverages the node type definitions to
construct a start page that proposes search for any of the entities available
in the domain: Customer, Account, etc. Andrea proceeds with Customer.

  3. (3)

Based on the schema information, the graph explorer dynamically constructs a
Customer search form. It contains separate search fields for the known
properties of Customer nodes: in our example id and name (inherited from
Person). Based on the data type constraints in the schema, the id field
accepts only integers as input. Andrea uses the name field to search for
customers of interest and obtains a visual representation of the customer
nodes in response.

  4. (4)

To inspect potential fraudulent behavior, Andrea needs to understand
connections between customers. Exploiting the schema, the graph explorer
leverages the edge type constraints to enumerate and propose specific types of
connections. For instance, knowing that Customers use CreditCards and
Transactions charge CreditCards, it identifies structural connection patterns,
written here in Cypher/GQL style,

⬇

(x:Customer)-[:uses]->(:CreditCard)

<-[:uses]-(y:Customer),

(x:Customer)-[:uses]->(:CreditCard)

<-[:charges]-(t:Transaction)-[:charges]->

(:CreditCard)<-[:uses]-(y:Customer)

and lets Andrea choose the patterns of interest.

  5. (5)

Andrea selects the first pattern, which aims to identify shared credit cards
that were used by two customers. Based on the schema knowledge, the
application constructs and executes an efficient query that quickly identifies
all shared credit cards usages between customers.

  6. (6)

The graph explorer visualizes the results of the connection search. Upon
further investigation, Andrea confirms suspicious cross-customer usage of the
same credit card and classifies the cases as fraudulent behavior.

As illustrated by this sample session, the graph explorer would not have been
able to effectively guide Andrea through the exploration without concrete
schema information. The suggestion of property specific search restrictions is
made possible by content types. The schema-assisted query formulation
leverages _node_ and _edge types_. Going beyond our example, it is easy to see
how other type and constraint information may help: for instance, key
constraints could indicate preferred search fields; more general participation
constraints may improve the schema-assisted query formulation process;
orthogonal tooling for schema generation might give graph explorers a
standardized path to approximate schema information in case it has not been
provided by the graph database authors. These considerations lead to a number
of design requirements (see Section 2), upon which we base our proposal.

Our proposed PG-Schema (_Property Graph Schema Language_) comprises PG-Types
and PG-Keys. PG-Types specifies possible combinations of labels and properties
in nodes and edges of different types, as well as constraining the types of
edges allowed between nodes of certain types, with the help of a rich
inheritance mechanism and abstract types. PG-Keys (Angles et al., 2021)
support diverse integrity constraints, including keys and participation
constraints. Via the mechanism of _strict_ and _loose_ schemas, and partial
validation, PG-Schemas support both the descriptive and prescriptive function
of schemas. No existing graph database system nor currently envisioned
standard covers this arsenal of features; nor do they provide full schema
validation support. Our PG-Schema proposal provides both existing systems
(reviewed in Section 5) and forthcoming standards with these features,
responding to users’ demands.

We give a detailed description of PG-Schema in Section 4. As a sample,
consider the graph type definition in Figure 2, representing part of the
schema diagram of Figure 1. The graph type fraudGraphType specifies node types
(e.g., personType, customerType), and edge types (e.g., activityType) using
the ASCII-art notation of Cypher (Francis et al., 2018), also adopted by GQL.
Properties are declared in curly braces {...}. For example, the first
statement defines a node type personType with label Person and a property with
key name of type STRING; and the last statement defines an edge type
activityType, whose label is either deposit or withdrawal, which connects
nodes of types transactionType and accountType.

Contributions. We make the following contributions:

  1. (1)

an analysis of the requirements for property graph schemas;

  2. (2)

a proposal for a flexible, agile, usable, and expressive formalism called PG-
Schema that fulfills these requirements;

  3. (3)

full syntax and semantics of PG-Schema, making the proposal easy to
incorporate into both standards and systems;

  4. (4)

a parser for PG-Schema (Bonifati et al., 2022b);

  5. (5)

a detailed analysis of schemas in other structured and semi-structured data
models and practical graph database systems, as well as their comparison with
PG-Schema.

Our contributions impact the following audiences:

  1. (a)

graph database standards committee members, who can build upon our
recommendations for upcoming features,

  2. (b)

graph database vendors, who can use our framework as a guideline to
incorporate schemas in their systems, and

  3. (c)

researchers, who can use a concrete model of schemas for property graphs as a
basis for further investigation.

##  2\. Design Requirements

In this section, we elaborate on the design requirements for a suitable notion
of schema for property graphs. To set the context, we briefly discuss key
characteristics of Property Graph Databases and outline the relevant functions
that schemas play in databases.

###  2.1. Property Graphs and Database Schemas

Beyond the ubiquity of applications that focus on graph-structured data and
graph analytics, the popularity of graph databases is also generally
attributed to the following factors (Neo4j, 2016; Needham and Hodler, 2019;
Robinson et al., 2015; Sahu et al., 2020b).

:

Agility. Thanks to its proximity to conceptual data models, the property graph
data model allows for an efficient translation from domain concepts to
database items. This facilitates high responsiveness i.e., the ability to
quickly and reliably adapt to emerging organizational and domain needs, which
is often achieved with iterative and incremental software development
processes.

:

Flexibility. Graph databases are aligned with an iterative and incremental
development methodology because they do not require a rigid schema-based data
governance mechanism, but rather favor test-driven development, which embraces
the additive nature of graphs. The data does not need to be modeled in
exhaustive detail in advance but rather new kinds of objects and relationships
can emerge naturally as new domain needs are addressed by evolving
applications.

Database schemas have a number of important functions that we split into two
general categories (Bonifati et al., 2019).

:

Descriptive function. Schemas provide a key to understanding the semantics of
the data stored in a database. More precisely, a schema allows to construct a
(mental) map between real-world information and structured data used to
represent it. This knowledge is essential for any user and application that
wishes to access and potentially modify the information stored in a database.

:

Prescriptive function. A schema is a contract between the database and its
users that provides guarantees for reading from the database and limits the
possible data manipulations that write to the database. To ensure that the
contract is respected, a mandatory schema can be enforced by the database
management system.

Our main goal is to develop a schema formalism for property graph databases
that fulfills both the descriptive and prescriptive roles while facilitating,
and possibly enhancing, the strengths of property graph databases.
Additionally, we aim at a formalism which enforces correct data modeling
practices through its syntax. First, however, we discuss the meaning of two
fundamental terms that are essential for defining schemas but are often
confused.

###  2.2. Types and Constraints

The notions of _type_ and _constraint_ are two main building blocks in
virtually any database schema formalism. When used sensibly, they enable the
division of schematic information into self-contained fragments that
correspond to real-world classes of objects (types) and pieces of knowledge
about them (constraints). In general, there is no clear distinction between
types and constraints, e.g., data value types are often considered as implicit
(domain) constraints. We employ the following nomenclature throughout the
paper.

:

Type is a property that is assigned to elements (data values, nodes, edges) of
a property graph database. Types group together similar elements that
represent the same kind of real-world object and/or that share common
properties, e.g., the set of applicable operations and the types of their
results.

:

Constraint is a closed formula over a vocabulary that permits quantification
over elements of the same type. The purpose of constraints is to impose
limitations and to express semantic information about real-world objects.

Both types and constraints impose limitations (and provide guarantees) but
types are of local nature while constraints are more global. More precisely,
checking that an element has a given type should require only inspecting the
element itself and possibly the immediately incident elements. On the other
hand, validating constraints may require inspecting numerous database elements
that need not even be directly connected. Consequently, types are typically
verified statically whereas constraints are dynamically verified.

###  2.3. Requirements

#### Property Graph Types

The descriptive function of schemas can be particularly beneficial to the
agility of property graph databases. Indeed, agility requires a good grasp of
the correspondence between database objects and real-world entities, which is
precisely the descriptive function of schemas. To communicate this
correspondence efficiently, schemas should allow and even encourage a use of
types that is consistent with how information about real-world objects is
normally/typically divided into nodes, edges, and properties of a property
graph database. Node are used to represent individual objects with all their
attributes stored as node properties.

  * R1

Node types. Schemas must allow defining types for nodes that specify their
labels and properties.

Edges are used to represent relationships between objects of given kinds, and
therefore should additionally specify node types of their endpoints.

  * R2

Edge types. Schemas must allow defining types for edges that specify their
labels and properties as well as the types of incident nodes.

Naturally, schemas must also allow a great degree of expressiveness when
describing the _content_ of nodes and edges, i.e., sets of properties and
their values.

  * R3

Content types. Schemas must support a practical repertoire of data types in
content types.

#### Property Graph Constraints

To further ensure that schemas can properly fulfill the descriptive role and
strengthen the agility of property graph databases, we additionally consider
the data modeling power that a suitable schema formalism should have. We
deliberately target minimal data modeling capabilities and as a reference
point we take the most basic variant of Entity-Relationship (ER) diagrams (see
Section 5), as the ultimate lower bound in the expressiveness of conceptual
modelling languages. To that end, schemas, in addition to the previous
requirements, must allow defining keys, which also provide the ability to
define weak entities and functional (one-to-many) relationships.

  * R4

Key constraints. Schemas must allow specifying key constraints on sets of
nodes or edges of a given type.

Schemas must allow participation constraints that require participation of
nodes of a given type in a relationship of a given type.

  * R5

Participation constraints. Schemas must allow specifying participation
constraints.

Finally, ER diagrams allow defining hierarchies of node types, a data modeling
feature that is even more crucial for property graphs, where a single node may
be an instance of multiple node types.

  * R6

Type hierarchies. Schemas must allow specifying type hierarchies.

#### Flexibility

As we saw in Sections 1 and 2.1, Property Graphs in practice are often popular
in dynamic applications with volatile and evolving graph structures, where new
kinds of objects are introduced following the evolving application demands.
These typical scenarios require support for flexible schema design across the
full range between schema-first and schema-later, with evolvable and
extensible schemas.

  * R7

Evolving data. Schemas must allow defining node, edge, and content types with
a finely-grained degree of flexibility in the face of evolving data.

  * R8

Compositionality. Schemas must provide a fine-grained mechanism for
compositions of compatible types of nodes and edges.

#### Usability

Finally, schemas must be usable in practice. Basic requirements here are that
the formalism must be implementable, with a well-defined semantics and human-
friendly declarative syntax. Furthermore, schemas must be easy to derive from
graph instances and validation of graph instances with respect to schemas must
be efficient. These basic requirements are fundamental for the practical
success of any schema solution, as we saw in Section 1.

  * R9

Schema generation. There should be an intuitive easy-to-derive constraint-free
schema for each property graph that can serve as a descriptive schema in case
one is not specified.

  * R10

Syntax and semantics. The schema language must have an intuitive declarative
syntax and a well-defined semantics.

  * R11

Validation. Schemas must allow efficient validation and validation error
reporting.

##  3\. Data model

We assume countable sets $\mathcal{L}$, $\mathcal{K}$, and $\mathcal{V}$ of
_labels_ , _property names (keys)_ , and _property values_. A _record_ with
keys from $\mathcal{K}$ and values from $\mathcal{V}$ is a finite-domain
partial function
$o\colon\mathcal{K}\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\to$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\to$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\to$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\to$\cr}}}\mathcal{V}$ mapping keys to values. We
write $\mathcal{R}$ for the set of all records.

###### Definition 3.1 (Property Graph).

A _property graph_ is defined as a tuple $G=(N,E,\rho,\lambda,\pi)$ where:

  * •

$N$ is a finite set of nodes;

  * •

$E$ is a finite set of edges such that $N\cap E=\emptyset$;

  * •

$\rho:E\rightarrow(N\times N)$ is a total function mapping edges to ordered
pairs of nodes (the endpoints of the edge);

  * •

$\lambda:(N\cup E)\rightarrow 2^{\mathcal{L}}$ is a total function mapping
nodes and edges to finite sets of labels (including the empty set);

  * •

$\pi:(N\cup E)\to\mathcal{R}$ is a function mapping nodes and edges to
records.

For an edge $e\in E$ with $\rho_{G}(e)=(u,v)$, the nodes $u$ and $v$ are the
_endpoints_ of $e$, where $u$ is the _source_ and $v$ is the _target_ of $e$.
For an element $x\in N\cup E$, the record $\pi(x)$ collects all _properties_
of $x$ (key-value pairs) and is called the _content_ of $x$.

##  4\. PG-Schemas

Most existing data definition languages for relational and semistructured data
consist of two parts: _types_ , which define the basic topological structure
of the data, and _constraints_ , which define data integrity. Likewise, PG-
Schemas consist of two parts. The first part, PG-Types, describes the shape of
data and the types of its components such as nodes and edges. It specifies

  * •

node types, describing the allowed combinations of labels and contents;

  * •

edge types, describing the allowed combinations of labels, contents, and
endpoint types; and

  * •

graph types, describing the types of nodes and edges present in the graph.

The second part describes constraints imposed on the typed data. Here, we
propose a slight extension of the existing proposal called PG-Keys (Angles et
al., 2021), which specifies integrity constraints such as keys and
participation constraints.

This section starts with a guided tour of PG-Types; the full syntax can be
found in the technical report (Bonifati et al., 2022c) and a parser is
available on Zenodo (Bonifati et al., 2022b) (with a third-party web
alternative (Wileński and Tomaszuk, 2022)). We then define their semantics
formally, provide a validation algorithm, and explain how PG-Types interact
with PG-Keys.

###  4.1. PG-Types by Example

We first discuss the basic ingredients of PG-Types (node types, edge types,
and graph types) and then move on to more sophisticated aspects such as
inheritance and abstract types. We use GQL’s predefined data types like DATE,
STRING, INT. These are orthogonal to our proposal and could, in principle, be
replaced by any other set of data types. Nevertheless, they take care of
requirement R3.

Generally, there are two main options for creating types in schemas. One can
create _open_ types and _closed_ types. Both kinds of types are able to
specify content that they _require to be present_. The difference between the
two is what they allow in addition to the explicitly mentioned content: closed
types forbid any content that is not explicitly mentioned, whereas open types
allow any such content. Closed types are what we have in SQL, but also in
programming languages such as C++ and Java. Open types are the default in JSON
Schema. We provide both options here, and use the keyword OPEN to indicate the
places where we use open types. We use declarative syntax closely aligned with
the syntax of types in GQL. It adopts the evocative ASCII-art formatting ( )
for node types and ( )-[ ]->( ) for edge types, originating from Cypher
(Francis et al., 2018).

#### Base Node Types

The most basic type is a node type. The following example specifies a node
type for representing a person:

⬇

(personType: Person {name STRING, OPTIONAL birthday DATE})

It specifies a node of type personType with a label Person. To distinguish
type names from labels, we end type names with the suffix Type. By default,
types are closed. That is, Person is the only allowed label. To permit nodes
of type personType to have arbitrary additional labels, one should write
(personType: Person OPEN {...}). In terms of properties, the type requires the
node to have a property name of type STRING. Optionally, the node can have a
property birthday. If it is present, it should have type DATE. No additional
properties are allowed for this node type. Again, if we would like to allow
them, we should write

⬇

{name STRING, OPTIONAL birthday DATE, OPEN}

inside the definition. More precisely, this content description specifies that
nodes should have name of type STRING and arbitrary additional properties. If
the property birthday is present, its type should be DATE. Notice that the
OPEN modifier applies independently to labels and properties: OPEN inside
{...} applies to properties only and the occurrence outside applies to labels
only.

Nodes in property graphs carry _sets_ of labels. In PG-Types, we can associate
multiple labels to a node type using the &-operator:

⬇

(customerType: Person & Customer

{name STRING, OPTIONAL since DATE})

The node type customerType requires nodes to carry both labels Person and Customer, and no other labels. In general, we specify the allowed combinations of labels with a variant of _label expressions_ built from $\ell$ (labels) and $\ell?$ (optional labels) using operators $\&$ (and), $|$ (choice). Syntactically, these constitute a subset of label expressions used by GQL and SQL/PGQ for pattern matching in queries. We define their semantics in Section 4.2. Intuitively, A & B? would require A and additionally allow B; and A | B gives the choice between the label A or B (not allowing both). It is easy to define an _inclusive or_ A \/ B as syntactic sugar for A | B | (A & B). A label expression can be accompanied with OPEN which, if specified, allows arbitrary additional labels.

This part of PG-Schema fulfils requirement R1. Since we will introduce more
advanced node types later using inheritance, we refer to the node types that
we explained here as _base node types_.

#### Base Edge Types

Let us define an edge type called friendType. Edges of type friendType carry
the labels Knows and Likes, and connect two nodes of type personType. They are
required to have a property since of type DATE. The ASCII art ( )-[ ]->( )
indicates that we are talking about edges.

⬇

(:personType)

-[friendType: Knows & Likes {since DATE}]->(:personType)

If one would like to be more liberal and allow customerType nodes on the ends
of friendType edges, one could use the |-operator:

⬇

(:personType|customerType)

-[friendType: Knows & Likes {since DATE}]->

(:personType|customerType)

One could be even more liberal and use personType OPEN to allow arbitrary
labels and properties in addition to the material required by personType. This
part of PG-Schema fulfils requirement R2.

#### Graph Types

A graph type combines node and edge types in one syntactic construct. It
includes the types of the schema, as we will see here, but also the
constraints, which we will see in Section 4.4. Here is an example:

⬇

CREATE GRAPH TYPE fraudGraphType STRICT {

(personType: Person

{name STRING, OPTIONAL birthday DATE}),

(customerType: Person & Customer

{name STRING, OPTIONAL since DATE}),

(suspiciousType: Suspicious OPEN {reason STRING, OPEN}),

(:personType|customerType)

-[friendType: Knows & Likes]->

(:personType|customerType)

}

The graph type fraudGraphType contains three node types and one edge type. The
keyword STRICT specifies how a property graph should be typed against the
schema. It means that, for a graph $G$ to be valid w.r.t. fraudGraphType, it
should be possible to assign at least one type within fraudGraphType to every
node and every edge of $G$. The alternative, LOOSE, allows for _partial
validation_ , addressing R7. Informally, it means that the validation process
simply assigns types to as many nodes and edges in the graph as possible, but
without the restriction that every node or edge should receive at least one
type. We discuss this further in Section 4.2.

We would like to point out the difference between open/closed element types
and loose/strict graph types. Why do we use different terminology (and
keywords) here? Element types work fundamentally differently from graph types.
A node type of the form

⬇

(nodeType: Label {prop STRING, ...})

requires each node of type nodeType to have a property prop. A graph type such
as fraudGraphType does not require nodes of type customerType. It merely
requires that every node gets assigned _some_ node type that is declared in
the graph type. Therefore, an open node type can require a certain label to be
present in a node, but a loose graph type cannot require a given element type
to be present in the graph.

The example also shows the keyword CREATE. If a node or edge type is created
as a catalog object, the declaration should likewise be preceded by CREATE
NODE TYPE or CREATE EDGE TYPE, respectively. Node (and edge) types outside
CREATE GRAPH TYPE statements should therefore always start with CREATE. If
personType and customerType had been already created outside, one could define
fraudGraphType more succinctly as:

⬇

CREATE GRAPH TYPE fraudGraphType STRICT {

personType, // import the type personType

customerType, // import the type customerType

(suspiciousType: Suspicious OPEN {reason STRING, OPEN}),

(:personType|customerType)

-[friendType: Knows & Likes]->

(:personType|customerType)

}

This leads us to a subtle difference between simply _referring_ to a type that
has been declared outside of the definition of a graph type, versus
_importing_ such a type. By default, we are always allowed to refer to any
type $t$ that is a catalog object. So, by omitting the import of personType
and customerType, the edge type friendType would still be well-defined.
However, by _importing_ $t$ we also allow objects in the graph type to be
assigned the type $t$, which is important for the notion of _validity_ of a
graph. When checking if a property graph $G$ is valid against FraudGraphType,
one needs to be able to assign at least one type $t$ to each element of $G$
such that $t$ is either _declared within_ FraudGraphType or _imported to_
FraudGraphType.

#### Inheritance

Specifying contents for all relevant combinations of labels explicitly can be
cumbersome and error-prone. We therefore allow reusing previously defined
types in definitions of other types. Such reuse not only makes schemas more
compact and modular, but also allows schema designers to follow a natural
approach of classifying things as more general or more specialised, as is done
in object-oriented modeling. With this mechanism we fulfil requirement R6
(type hierarchies).

Consider the following example:

⬇

(salariedType: Salaried {salary INT})

(employeeType: personType & salariedType)

The node type employeeType inherits labels and properties from personType and
salariedType. That is, it has the labels Person (inherited from personType)
and Salaried (inherited from salariedType). Its properties are name and
optionally birthday (inherited from personType), as well as salary (inherited
from salariedType). Note that inheritance automatically conflates properties
that are compatible. If salariedType had a property name, then employeeType
would only be well-defined if its name were a STRING.

Similar to nodes, PG-Type allows using edge types when specifying another edge
type:

⬇

(:employeeType)

-[buddyType: friendType {since DATE, casual BOOL}]->

(:employeeType)

The edge type buddyType is an edge of type friendType but restricts the end
nodes to be of type employeeType, i.e., end nodes also need to have a salary
property and Salaried label. The type additionally requires the properties
since of type DATE and casual of type BOOL. Notice that since is already
required by friendType, so type buddyType would not change if we omitted it
from the definition of buddyType. Intuitively, we can think that inherited
types collect all the property specifications of the parent types, and add the
newly specified ones. If we declared since to be of a different type than
DATE, the resulting edge type would be impossible to instantiate, and as such
it would be redundant. The precise rules for how edge types and node types of
endpoints are combined are in Section 4.2.

We also support _graph inheritance_. By writing

⬇

CREATE GRAPH TYPE fraudGraphType STRICT

IMPORTS socialGraphType {...}

all types in socialGraphType are imported to fraudGraphType.

#### Including Types in Label Expressions

We can combine inheritance with adding new properties or labels. For instance,
if we wrote

⬇

(employeeType: personType & salariedType {birthday DATE})

then birthday would be a mandatory property in nodes of type employeeType, in
addition to inherited properties salary and name.

Formally, we combine properties using the $\oplus$-operator, inspired by
mixins (Bracha and Cook, 1990) and explained in Section 4.2. Abstractly, if we
define

⬇

(xType: A & B {propertyA INT, propertyB INT})

(yType: B & C {propertyB INT, propertyC INT})

(zType: xType & yType)

then nodes of type zType have all labels A, B, and C, and all properties
propertyA, propertyB, and propertyC. Since both xType and yType are closed,
this means that a node can be of type zType, but not of type xType and not of
type yType.

If both xType and yType were open types, i.e., declared their label sets and
contents to be OPEN, then nodes of type zType would automatically fulfill
xType and yType. That is, for open types, we support _intersection types_ via
the operator &.

More generally, in the definitions of types we allow arbitrary expressions built from labels and previously defined types using operators ?, &, and |. Of course, declarations of node types should only refer to node types and similarly for edge types. Also, references should not be cyclic, as is standard in inheritance hierarchies. Notice that using | we can define a _union type_ , which allows going beyond base types. For instance,

⬇

(aType: A {propertyA INT})

(bType: B {propertyB INT})

(cType: aType | bType)

creates a node type cType which either has the label A or B. However, A is
only allowed to occur together with propertyA and B only with propertyB (but
not A with propertyB). One cannot define cType as a base type, since base
types always admit all combinations of matching label sets and matching
property sets. Furthermore, if one of the base types were open, the derived
type would automatically be open. This holds for both label openness and
property openness. However, if both base types are closed, the derived type
can be declared open (independently for labels and properties).

The inclusion of types in label expressions makes the formalism highly
compositional, fulfilling requirement R8.

#### Abstract Types

In some cases, one may want to declare a type as _abstract_ , i.e., it cannot
be directly instantiated.

⬇

ABSTRACT (salariedType {salary INT})

(employeeType: personType & salariedType)

Notice that salariedType specifies nodes with no labels and a single property
salary. On its own, this type may not be very useful, since we expect nodes
with property salary to have labels and possibly other properties as well.
Through inheritance from salariedType, the type employeeType matches nodes
with all the labels and properties allowed in personType, plus an additional
property salary.

###  4.2. Formal Definition and Semantics

So far we have been talking about graph types by means of syntax. We now
present a syntax-independent definition. Later we shall see how the two
connect, thus providing the semantics for our declarative syntax, and
fulfilling design requirement R10.

#### Types and conformance

Recall from Section 3 that $\mathcal{L}$ is the set of labels, and
$\mathcal{R}$ the set of all possible records. We define a _formal base type_
as a pair $(L,R)$, where $L\subseteq\mathcal{L}$ and $R\subseteq\mathcal{R}$.
We write $\mathcal{T}$ for the set of all formal base types. An element (a
node or an edge) with label set $K$ and content $o$ _conforms_ to a formal
base type $(L,R)$, if $K=L$ and $o\in R$. For the formal definition, we allow
arbitrary subsets of $\mathcal{R}$ to form base types. In the concrete syntax
of the previous section these will be given by record types; e.g., for the
type {a INT, b STRING}, the set $R$ consists of all partial functions that map
a to an integer and b to a string.

###### Definition 4.1.

A _formal graph type_ is a tuple $S=(N_{S},E_{S},\nu_{S},\eta_{S})$ where

  * •

$N_{S}$ and $E_{S}$ are disjoint finite sets of node and edge type names;

  * •

$\nu_{S}:N_{S}\to 2^{\mathcal{T}}$ maps node type names to sets of formal base
types;

  * •

$\eta_{S}:E_{S}\to 2^{\mathcal{T}\times\mathcal{T}\times\mathcal{T}}$ maps
edge type names to sets of triples of formal base types: one for the source
node, one for the edge itself, and one for the target node.

For brevity, we shall often refer to the elements of $N_{S}$ and $E_{S}$ as
node and edge types, rather than node and edge type names. For dealing with
_strict_ and _loose_ typing, we will use slightly different but connected
notions, namely _conformance_ and _typings_.

###### Definition 4.2.

Let $G=(N_{G},E_{G},\lambda_{G},\rho_{G},\pi_{G})$ be a property graph and
$S=(N_{S},E_{S},\nu_{S},\eta_{S})$ be a formal graph type. A node $v\in N_{G}$
_conforms_ to a node type $\tau\in N_{S}$ if it conforms to a formal base type
in $\nu_{S}(\tau)$. An edge $e\in E_{G}$ _conforms_ to an edge type $\sigma\in
E_{S}$ if for the pair $(v_{1},v_{2})=\rho_{G}(e)$ there is a triple
$(t_{1},t,t_{2})\in\eta_{S}(\sigma)$ such that $v_{1}$ conforms to $t_{1}$,
$e$ conforms to $t$, and $v_{2}$ conforms $t_{2}$. A property graph $G$
_conforms_ to a formal graph type $S$ if every element in $G$ conforms to at
least one type in $S$.

The _typing of $G$_ wrt. $S$ is the mapping $\mathsf{Types}:N_{G}\cup E_{G}\to
2^{N_{S}}\cup 2^{N_{S}}$ defined as follows for all $u\in N_{G}$ and $e\in
E_{G}$:

$\displaystyle\mathsf{Types}(u)$ $\displaystyle=\\{\tau\in N_{S}\mid u\text{
conforms to }\tau\\}\,,$ $\displaystyle\mathsf{Types}(e)$
$\displaystyle=\\{\tau\in E_{S}\mid e\text{ conforms to }\tau\\}\,.$

Hence, $G$ conforms to $S$ if $\mathsf{Types}$ only maps to non-empty sets.

#### Schema compilation

We now explain how to interpret the syntax described in Section 4.1 in terms
of formal graph types introduced above, thus providing the semantics for the
syntax. This process, which we call _schema compilation_ , will effectively
amount to unravelling and normalising all type definitions.

Let $T$ be a syntactically represented graph type. We shall define a
corresponding formal graph type $S=(N_{S},E_{S},\nu_{S},\eta_{S})$. For
$N_{S}$ and $E_{S}$ we take the sets of node and edge type names used in $T$.
Because type definitions in $T$ are acyclic, we can use a bottom-up approach
to unravel them.

Consider a node type definition ($\tau$:$F$) in $T$. Recall that $F$ is an
expression built from labels $\ell$ and node type names $\sigma$ using
operators $?$, $\&$, and $|$, followed by an optional keyword OPEN and an
optional content description $r$. Assume that $\nu_{S}$ is already defined
over all node type names $\sigma$ used in $F$ (the base case is when $\tau$ is
defined as a base node type). The expression $F$ defines the family $\Lparen
F\Rparen\subseteq\mathcal{T}$ of formal base types allowed for type $\tau$.
Intuitively speaking, $F$ describes how the allowed formal base types can be
generated, starting from the simplest ones, much like a regular expression
describes how to generate words.

Let $t_{\emptyset}=(\emptyset,\\{\bot\\})$ and
$t_{\ell}=(\\{\ell\\},\\{\bot\\})$, where $\bot$ stands for the empty record.
These are the empty formal base type and the formal base type of a single
label, with no content. We add content using content descriptions, which are
record types written as

$r=\\{\text{[{\small{OPTIONAL}}]
}k_{1}\>\mathbb{b}_{1},\ldots,\text{[{\small{OPTIONAL}}]
}k_{n}\>\mathbb{b}_{n},\text{[{\small{OPEN}}]}\\}\,$

where the square brackets mean that the keywords OPTIONAL and OPEN are
optional, the $k_{i}$s are keys from $\mathcal{K}$, and the $\mathbb{b}_{i}$s
are base property types such as INT or DATE. Let $\mathbb{B}_{i}$ be the
extent of $\mathbb{b}_{i}$ (e.g., $\mathbb{Z}$ for INT). When the keyword OPEN
is present, the semantics $\Lparen r\Rparen$ of $r$ is the set of all records
$o\in\mathcal{R}$ such that for all $i\leq n$, if $k_{i}\in\mathrm{dom}(o)$
then $o(k_{i})\in\mathbb{B}_{i}$, and $k_{i}$ must belong to $\mathrm{dom}(o)$
unless it is preceded by the keyword OPTIONAL. When the keyword OPEN is
absent, we additionally require that
$\mathrm{dom}(o)\subseteq\\{k_{1},\ldots,k_{n}\\}$.

With these tools we could define the semantics of node types with a single
label and a content description. In order to handle more complex types we need
a way to combine formal base types. We begin from records. We call records
$o_{1},o_{2}\in\mathcal{R}$ _compatible_ if $o_{1}(k)=o_{2}(k)$ for each
$k\in\mathrm{dom}(o_{1})\cap\mathrm{dom}(o_{2})$. For compatible $o_{1}$ and
$o_{2}$ we define their _combination_ $o_{1}\oplus o_{2}$ as $(o_{1}\oplus
o_{2})(k)=o_{1}(k)$ for $k\in\mathrm{dom}(o_{1})$ and $(o_{1}\oplus
o_{2})(k)=o_{2}(k)$ for $k\in\mathrm{dom}(o_{2})\setminus\mathrm{dom}(o_{1})$.
For sets $O_{1},O_{2}\subseteq\mathcal{R}$ we let $O_{1}\oplus O_{2}$ be the
set of all records of the form $o_{1}\oplus o_{2}$ for compatible $o_{1}\in
O_{1}$ and $o_{2}\in O_{2}$. This operation is akin to the natural join known
from relational algebra. The only difference is that in relational algebra
columns are fixed for each relation, whereas a set of records may contain
records with different sets of keys. We lift the $\oplus$ operator to formal
base types by letting $(L_{1},R_{1})\oplus(L_{2},R_{2})=(L_{1}\cup
L_{2},R_{1}\oplus R_{2})$. Note that in the absence of content, this amounts
to taking the union of two sets of labels.

Now we can define the semantics recursively for all subexpressions of $F$ as
follows:

$\Lparen\ell\Rparen=\big{\\{}t_{\ell}\big{\\}}\,,\qquad\qquad\qquad\Lparen\sigma\Rparen=\nu_{S}(\sigma)\,,$
$\Lparen F_{1}?\Rparen=\Lparen
F_{1}\Rparen\cup\big{\\{}t_{\emptyset}\big{\\}}\,,\qquad\Lparen
F_{1}\mathbin{|}F_{2}\Rparen=\Lparen F_{1}\Rparen\cup\Lparen F_{2}\Rparen\,,$
$\Lparen
F_{1}\mathbin{\&}F_{2}\Rparen=\big{\\{}(L_{1},R_{1})\oplus(L_{2},R_{2})\bigm{|}(L_{i},R_{i})\in\Lparen
F_{i}\Rparen\text{ for }i=1,2\big{\\}}\,,$ $\Lparen F_{1}\text{
{\small{OPEN}}}\Rparen=\big{\\{}(L,R)\bigm{|}\exists\,L^{\prime}\subseteq
L\text{ such that }(L^{\prime},R)\in\Lparen F_{1}\Rparen\big{\\}}\,,$ $\Lparen
F_{1}\,r\Rparen=\big{\\{}\big{(}L,R\oplus\Lparen
r\Rparen\big{)}\bigm{|}(L,R)\in\Lparen F_{1}\Rparen\big{\\}}\,.$

With that, the semantics of $\tau$ is defined as

$\nu_{S}(\tau)=\Lparen F\Rparen\,.$

For edge types we proceed in the same vein as for node types. Consider an edge
type in $T$ defined as
(:$F_{\mathsf{src}}$)-[$\tau$:$F$]->(:$F_{\mathsf{tgt}}$). Expressions
$F_{\mathsf{src}}$ and $F_{\mathsf{tgt}}$ specifying source and target
endpoints are interpreted as explained above. We first explain the expression
$F$, which defines the set $\llbracket
F\rrbracket\subseteq\mathcal{T}\times\mathcal{T}\times\mathcal{T}$ of triples
of formal base types, according to the following rules:

$\llbracket\ell\rrbracket=\big{\\{}\big{(}t_{\emptyset},t_{\ell},t_{\emptyset}\big{)}\big{\\}}\,,\qquad\llbracket\sigma\rrbracket=\eta_{S}(\sigma)\,,\qquad\llbracket
F_{1}\mathbin{|}F_{2}\rrbracket=\llbracket F_{1}\rrbracket\cup\llbracket
F_{2}\rrbracket\,,\qquad$ $\llbracket F_{1}?\rrbracket=\llbracket
F_{1}\rrbracket\cup\big{\\{}\big{(}t_{\emptyset},t_{\emptyset},t_{\emptyset}\big{)}\big{\\}}\,,\qquad\quad\llbracket
F_{1}\mathbin{\&}F_{2}\rrbracket=\llbracket F_{1}\rrbracket\oplus\llbracket
F_{2}\rrbracket\,,$ $\llbracket F_{1}\text{
{\small{OPEN}}}\rrbracket=\big{\\{}\big{(}t_{1},(L,R),t_{2}\big{)}\bigm{|}\exists\,L^{\prime}\subseteq
L\text{ s.t. }\big{(}t_{1},(L^{\prime},R),t_{2}\big{)}\in\llbracket
F_{1}\rrbracket\big{\\}}\,,$ $\llbracket
F_{1}\,r\rrbracket=\big{\\{}\big{(}t_{1},(L,R\oplus\Lparen
r\Rparen),t_{2}\big{)}\bigm{|}\big{(}t_{1},(L,R),t_{2}\big{)}\in\llbracket
F_{1}\rrbracket\big{\\}}\,,$

where the $\oplus$ operator is extended to sets
$Y_{1},Y_{2}\subseteq\mathcal{T}\times\mathcal{T}\times\mathcal{T}$ of triples
of formal base types by

$Y_{1}\oplus Y_{2}=\big{\\{}\big{(}s_{1}\oplus t_{1},s\oplus t,s_{2}\oplus
t_{2}\big{)}\bigm{|}\big{(}s_{1},s,s_{2}\big{)}\in
Y_{1},\big{(}t_{1},t,t_{2}\big{)}\in Y_{2}\big{\\}}\,.$

With that, we define the semantics of the edge type $\tau$, as used in the
syntactic construct (:$F_{\mathsf{src}}$)-[$\tau$:$F$]->(:$F_{\mathsf{tgt}}$),
as

$\eta_{S}(\tau)=\big{(}\Lparen
F_{\mathsf{src}}\Rparen\times\\{t_{\emptyset}\\}\times\Lparen
F_{\mathsf{tgt}}\Rparen\big{)}\oplus\llbracket F\rrbracket\,.$

After all type definitions in $T$ have been unravelled, as the last step, we
restrict the sets $N_{S}$ and $E_{S}$ to type names whose definitions in $T$
are not preceded by the keyword ABSTRACT.

Having defined how a syntactically represented graph type $T$ corresponds to a
formal graph type $S_{T}=(N_{S},E_{S},\nu_{S},\eta_{S})$, we can now explain
validation of a property graph $G$ against LOOSE and STRICT graph types. For
both options, one first starts by computing the typing of $G$ w.r.t. $S_{T}$.
If $T$ is LOOSE, this is where the _validation of $G$ against $T$_ ends; the
mapping $\mathsf{Types}$ fully specifies which element of $G$ can be assigned
which types from $T$. If $T$ is STRICT, we do one more step, namely we test if
$\mathsf{Types}$ assigns at least one type in $S_{T}$ to each element in $G$.
If it does, we say that $G$ _conforms to_ $T$.

###  4.3. Validation and Graph Type Generation

We now discuss how to validate a graph against a graph type. For a formal
graph type, the process is straightforward: for each node type we identify the
nodes that conform to it, and we use this information to identify for every
edge type the set of edges that conform to it. The validation for general
graph types, defined with the syntax in Section 4.1, can be accomplished
efficiently with an analogous procedure thanks to the mathematical simplicity
of the schema compilation rules in Section 4.2. More importantly, such a
validation procedure can be implemented in a reasonably expressive graph query
language. In essence, such a language would need to support standard set
operations and would need to allow identification of nodes and edges based on
their labels, property names, and property value types. Consequently, the
proposed graph schema formalism satisfies requirement R11.

We also propose a simple method of generating a graph type for a given
property graph. For every node we introduce an anonymous node type that fits
precisely its set of labels and properties, we gather those types into a set,
and finally generate their names. Using anonymous types allows to eliminate
repetitions of syntactically identical types easily. We next apply an
analogous procedure for edges remembering to use previously identified node
types of the endpoints. Finally, we group types of all elements into the
resulting graph type. This shows the satisfaction of requirement R9. One might
wish for a more sophisticated method of schema generation, but those fall into
the domain of schema inference (Bonifati et al., 2022d; Groz et al., 2022)
that are out of scope of the paper and left as future work.

###  4.4. Adding Constraints

Our focus until now was on _types_ in PG-Schema. The other crucial aspect of
PG-Schema are its _constraints_. To this end, we leverage existing work on
_keys for property graphs_ (Angles et al., 2021), called PG-Keys. Despite
their name, PG-Keys go beyond the capability of expressing key constraints.
Statements in PG-Keys are of the form

⬇

FOR $p(x)$ <qualifier> $q(x,\bar{y})$ ,

where <qualifier> specifies the kind of constraint that is being expressed and
consists of combinations of EXCLUSIVE, MANDATORY, and SINGLETON. Both $p(x)$
and $q(x,\bar{y})$ are queries. For instance, if we want to express that, for
every output $x$ of $p(x)$ there should be at least one tuple
$\bar{y}=(y_{1},y_{2},\dots,y_{n})$ that satisfies $q(x,\bar{y})$, we write
FOR $p(x)$ MANDATORY $q(x,y_{1},\ldots,y_{n})$. SINGLETON would mean that
there should be at most one such $\bar{y}$ for each $x$, and EXCLUSIVE that no
$\bar{y}$ should be shared by two different values of $\bar{x}$. Inside the
queries, we can use the keyword WITHIN to make clear what the output of the
queries is, i.e., what we want to be EXCLUSIVE, etc.

In PG-Schemas, we slightly extend the syntax of PG-Keys by allowing the
constraints to refer to a _type name_ at each point where PG-Keys allows a
label. The semantics of the resulting expression is that _a type name $t$
matches every node that conforms to $t$_.

Consider the following code snippet:

⬇

CREATE GRAPH TYPE socialGraphType STRICT {

(personType: Person {name STRING, id INT}),

(customerType: Customer {id INT}),

(:personType)

-[friendType: Knows & Likes & Bestie?]->(:personType),

// Constraints

FOR (x:personType) EXCLUSIVE MANDATORY SINGLETON x.id,

FOR (x:customerType) MANDATORY y.id

WITHIN (y:personType) AND y.id=x.personID,

FOR (x:personType) SINGLETON y

WITHIN (x)-[y: friendType & Bestie]->()

}

The example describes a graph with two kinds of nodes: persons (personType)
and customers (customerType). Furthermore, we have friend-edges between
persons. The edge type friendType requires labels Knows and Likes and allows
label Bestie on the edge.

We also have three PG-Key constraints in the example. The first expresses that
the value of the property id should be a key for nodes of type personType. The
second PG-Key expresses that every personID value of a customer should be an
id of a person, which is a foreign key. PG-Keys (and therefore PG-Schema) can
therefore handle _key and foreign key constraints_ (requirement R4). The third
PG-Key expresses that each person is allowed to have at most one best friend.
Notice that y: friendType & Bestie means that $y$ should have label Bestie and
it should conform to the type friendType. If we would write MANDATORY y WITHIN
(x)-[y:friendType]->() in the second constraint, it would express that each
person participates in the friendType relation, i.e., it expresses a
participation constraint (requirement R5). PG-Keys are also powerful enough to
express SQL-style CHECK constraints, such as FOR (x:salariedType) MANDATORY
x.salary >= 0, or denial constraints, such as FOR (x:customerType) MANDATORY
(x:!employeeType), where ! denotes negation. Concerning validation, notice
that the typing of a property graph $G$ w.r.t. a graph type $S$ can be
computed efficiently. Once we have this typing, PG-Keys can be evaluated as in
the original paper (Angles et al., 2021), using types as if they were labels
in the graph.

We conclude this section with the observation that PG-Schema satisfies all
requirements identified in Section 2.

##  5\. Relationship to Other Paradigms

We now compare PG-Schema with existing schema formalisms and with existing
graph schema technologies. We consider a wide range of formalisms. First, we
consider _conceptual data models_ such as the Entity-Relationship Model (Chen,
1976) (Chen ER), its extensions, i.e., the Extended Entity-Relationship Model
(Thalheim, 2018) (Extended ER) and the Enhanced Entity-Relationship Models
(Elmasri and Navathe, 2015) (Enhanced ER), as well as ORM2 diagrams (Halpin,
2015) and UML Class diagrams (Fowler, 2003). Second, we discuss graph schemas
stemming from the _Semantic Web_ setting, by reviewing RDF Schema (RDFS)
(Brickley and Guha, 2014), the Web Ontology Language (OWL) (Hitzler et al.,
2012), SHACL (Knublauch and Kontokostas, 2017; Corman et al., 2018), and ShEx
(Staworko et al., 2015). Third, we overview _tree-structured data_ formalisms.
These are XML, together with its main schema languages (Document Type
Definition (DTD) (Yergeau et al., 2008), XML Schema (Sperberg-McQueen et al.,
2012) and REgular LAnguage for XML Next Generation (RELAX NG) (ISO/IEC
19757-2:2008, 2008)), and JSON Schema (Wright et al., 2020; Pezoa et al.,
2016). A detailed description of these existing schema formalisms is omitted
for space reasons and can be found in an external technical report (Bonifati
et al., 2022c).

In order to perform this comparison, we define several features in Section
5.1, and discuss their support in Section 5.2. Finally, we propose potential
PG-Schema extensions in Section 5.3.

###  5.1. Existing Graph Schema Features

We briefly describe the main features used to compare state-of-the-art graph
schema languages in Table 1. We group these into: type features, constraint
features, and schema features.

#### Type features

We first look at the _number of built-in primitive data types readily
available in the schema language library_ (PDT). Next, we inspect _support for
specifying union or intersection types for nodes, edges, and properties_
(UIT). Another considered feature is the _ability to rely on inheritance to
define new types from existing ones and thus construct type hierarchies_ (TH).
We check whether the schema languages _allow abstract types (interfaces) for
nodes or edges, in order to specify their structure without having to build
concrete instances for these_ (AT). We examine whether the _declared types can
be open or closed, i.e., whether instances can have labels or properties that
are not mentioned in their type_ (OCT). We analyze the way in which properties
are handled, i.e., if they _can be assigned to nodes or edges_ (EP), if they
_can be declared as mandatory or optional_ (MOP), and if their type _can be
complex_ and specify recursively nested combinations of collection and tuple
types (CPT). We also check whether one can _explicitly limit the allowed
property values, by providing range constraints_ (RC).

#### Constraint features

We examine the capability to _define key constraints to identify graph
objects_ (KC). Other features are declaring the _mandatory participation of
certain types of nodes in certain types of edges_ (MP) and the _upper/lower
bounds for their number_ (CC). Lastly, we check whether the _relations
represented by edges can be further specified through binary constraints_
(BC), i.e., defined to be (ir)reflexive, (in)transitive, (a)cyclic,
(a/anti)symmetric, etc.

#### Schema features

We first assess whether _instances can be tractably validated_ (TV), i.e., in
polynomial time when considering combined complexity, and whether the computed
result can be a subset indicating their _partial conformance_ (PC). We also
inspect whether the schema is amenable to _introspection_ (ISP), i.e., whether
it can itself be regarded as a graph instance and, as such, directly queried.
Finally, we specify if the schema can be defined: 1) _first_ , subsequently
enforcing it for all instances, 2) _partially_ , allowing some of its
components to be descriptive (e.g., the element types) and some to be
prescriptive (e.g., the constraints), or 3) _flexible_ , creating and updating
instances in an unconstrained manner while possibly maintaining a descriptive
schema (SFPX).

###  5.2. Support of the Features

We comment on some of the differences between PG-Schema and the existing
state-of-the-art graph schema formalisms and systems from Table 1, with a
focus on existing graph technologies.

Table 1. Overview of the features supported by state-of-the-art graph schema
formalisms

PDT UIT TH AT OCT EP MOP CPT RC KC MP CC BC TV PC IS SFPX PG-Schema [GQL] n/e
n/e/[-] n/e/[-] o/c n/e m/o [-] [-] $\checkmark$ $\checkmark$ [-] -
$\checkmark$ $\checkmark$ - f/p/x Chen ER (Chen, 1976) [-] - - - c n/e m - [-]
[$\checkmark$] $\checkmark$ - - [-] - - f Extended ER (Thalheim, 2018) [-] n/e
n/e/p n/e c n/e m/o $\checkmark$ [-] $\checkmark$ $\checkmark$ $\checkmark$ -
[-] - - f Enhanced ER (Elmasri and Navathe, 2015) [-] n/e n/e n c n/e m/o
$\checkmark$ [-] [$\checkmark$] $\checkmark$ $\checkmark$ - [-] - - f ORM2
(Halpin, 2015) [-] n/e/p n/e/p n/e c n/e m/o [-] $\checkmark$ $\checkmark$
$\checkmark$ $\checkmark$ $\checkmark$ [-] - - f UML Class Diagrams (Fowler,
2003) [5] n n n c n/e m/o [-] $\checkmark$ $\checkmark$ $\checkmark$
$\checkmark$ $\checkmark$ [-] - - f RDFS (Brickley and Guha, 2014) 34 - n/e/p
- o [-] [o] - - - - - - $\checkmark$ $\checkmark$ $\checkmark$ f/x OWL
(Hitzler et al., 2012) [33] n/e/p n/e/p - o n [m]/[o] - $\checkmark$
$\checkmark$ [-] $\checkmark$ $\checkmark$ [$\checkmark$] $\checkmark$
$\checkmark$ f/x SHACL (Knublauch and Kontokostas, 2017) 34 n/e/p n/e/p - o/c
n m/o - $\checkmark$ [$\checkmark$] $\checkmark$ $\checkmark$ - [$\checkmark$]
$\checkmark$ $\checkmark$ f/p/[x] ShEx (Baker and Prud’hommeaux, 2019;
Staworko et al., 2015) 34 n/e/p n/e/p - o/c n m/o - $\checkmark$
[$\checkmark$] $\checkmark$ $\checkmark$ - [$\checkmark$] $\checkmark$
$\checkmark$ f/p/[x] DTD (Yergeau et al., 2008) 6 [n] - - o/c n m/o [-] - [-]
$\checkmark$ - - $\checkmark$ - [$\checkmark$] f/x JSON Schema (Wright et al.,
2020) 6 n/e n/e/p n o/c n m/o $\checkmark$ $\checkmark$ [$\checkmark$]
$\checkmark$ $\checkmark$ - $\checkmark$ - $\checkmark$ f/x RELAX NG (ISO/IEC
19757-2:2008, 2008) [2] n n/e/p n o/c n m/o $\checkmark$ $\checkmark$ [-]
$\checkmark$ - - $\checkmark$ - $\checkmark$ f/x XML Schema (Sperberg-McQueen
et al., 2012) [47] n n/e/p n o/c n m/o $\checkmark$ $\checkmark$ $\checkmark$
$\checkmark$ $\checkmark$ - $\checkmark$ - $\checkmark$ f/x GraphQL SDL
(Facebook, 2018; Hartig and Pérez, 2018) 5 n/[e] n/e n/e c n/e m/o
$\checkmark$ [$\checkmark$] $\checkmark$ $\checkmark$ - - [-] $\checkmark$
$\checkmark$ f openCypher Schema (Bonifati et al., 2019) [openCypher] [n] n/e
n/e c n/e m $\checkmark$ - $\checkmark$ $\checkmark$ - - $\checkmark$
$\checkmark$ $\checkmark$ p/x SQL/PGQ (9075-16, 2022; Deutsch et al., 2022)
[SQL] n/e [n]/[e] n/e c n/e m/o $\checkmark$ [$\checkmark$] $\checkmark$
$\checkmark$ [-] - $\checkmark$ - $\checkmark$ f AgensGraph (AgensGraph, 2022)
[-] - n/e/p - o [n]/[e] m/o [$\checkmark$] [$\checkmark$] [$\checkmark$]
$\checkmark$ - - [$\checkmark$] $\checkmark$ [$\checkmark$] f/x ArangoDB
(ArangoDB, 2022) 6 [n]/[e] n/e/p n o/c n/e m/o $\checkmark$ [$\checkmark$]
[$\checkmark$] $\checkmark$ [$\checkmark$] - [$\checkmark$] - $\checkmark$ f/x
DataStax (DataStax, 2022) [25] - - - [o] n/e m/o $\checkmark$ [$\checkmark$]
$\checkmark$ $\checkmark$ - - ? $\checkmark$ $\checkmark$ f/x JanusGraph
(JanusGraph, 2022) 12 - - - [o] n/e m/o $\checkmark$ - $\checkmark$
$\checkmark$ $\checkmark$ - $\checkmark$ $\checkmark$ [$\checkmark$] f/x
Nebula Graph/nGQL (Wu et al., 2022) 5 - - - c n/e m/o - - - - - - [-] -
$\checkmark$ f Neo4j (Technology, 2022) 11 [n] [-] [-] o n/e m/o
[$\checkmark$] - $\checkmark$ - [-] - - $\checkmark$ $\checkmark$ p/x
Oracle/PGQL (Oracle, 2022) 11 [n]/[e] - - c n/e [m]/[o] - [$\checkmark$]
[$\checkmark$] [$\checkmark$] [-] - [$\checkmark$] $\checkmark$ $\checkmark$
f/x OrientDB/SQL (OrientDB, 2022) 23 [n]/[e] [n]/[e] [n]/[e] o/c n/e [m]/[o]
$\checkmark$ [$\checkmark$] [$\checkmark$] [$\checkmark$] [-] - [$\checkmark$]
$\checkmark$ [$\checkmark$] f/[p] Sparksee (Technologies, 2022) 8 - - - c n/e
m/o [$\checkmark$] - $\checkmark$ $\checkmark$ - - [-] - [$\checkmark$] f
TigerGraph/GSQL (TigerGraph, 2022) 8 [n]/[e] - [-] c n/e [m]/[o] $\checkmark$
[$\checkmark$] $\checkmark$ - [-] [$\checkmark$] [$\checkmark$] - $\checkmark$
f TypeDB/TypeQL (Vaticle, 2022) 5 - n/e/p n/e/p c n/e m $\checkmark$
[$\checkmark$] $\checkmark$ $\checkmark$ [-] $\checkmark$ [-] - $\checkmark$ f

Legend: ‘$\checkmark$’ = _supported_ , ‘-’ = _not supported_ , ‘?’ = _unknown_
, [$x$] = _qualified $x$_, n/e/p = _supported for (n)odes, (e)dges, and
(p)roperties_ ,
o/c = _(o)pen and (c)losed_ , m/o = _(m)andatory and (o)ptional_ , f/p/x =
_schema (f)irst, (p)artial, and fle(x)ible_

####  PG-Schema

The support for union and intersection types (UIT), type hierarchies (TH),
abstract types (AT), open / closed types (OCT), element properties (EP) and
mandatory / optional properties (MOP) are discussed in Section 4. PG-Schema is
assumed to be able to function as an embedded language within SQL. Therefore,
its design supports SQL’s complex value types and so can be assumed to support
(CPT) and (RC). The support for (KC) and (MP) is discussed in Section 4.4. A
possible extension to support (CC), that fits well with the support for KC and
MP, is discussed in Section 5.3. There is currently no commonly agreed upon
definition within PG-Schema of how schemas are represented as property graphs,
and hence it does not fully support introspection (IS). How this
representation can capture all features and yet remain intuitive, as in the
diagram of Figure 1, is an issue for future research.

The tractability of validation (TV) in PG-Schema is a consequence of the fact
that, for full conformance, one only needs to verify that each element has an
element type that it conforms to, and this requires only local checks. If a
graph only partially conforms, this can be easily explained to users, in terms
of which elements conform and which do not, and so it is easy to support (PC).
Finally, it is possible to indicate that the validation should be loose, and
only check the constraints, thus allowing partial schema validation. PG-Schema
also allows defining graphs without a schema (so a schema-flexible approach)
or without full validation (so a schema-partial approach), hence fully
supporting (SFPX).

#### Conceptual data models

ER-based data models tend to be agnostic with respect to attribute types,
since these may depend on the back-end for which the data model is designed.
Most support inheritance hierarchies and, in that way, can model union and
intersection types. Entity types can be modelled as abstract types, by
indicating that its entities must belong to at least one of its subtypes.
Since the final goal is to design a relational schema, which is closed, none
of them support open types. Most ER-based models allow attributes to be
composed and/or multi-valued, and so can model complex nested values. A
surprising restriction is that most conceptual data models only allow a single
key and require it to be a single attribute. A notable exception is ORM2,
which can support any number of composed keys. Schema validation is not
applicable in this context, as there is no notion of a schema-independent
instance.

#### RDF formalisms

RDF-based formalisms inherit XML datatypes with some limitations (PDT). Both
SHACL and ShEx are based on a kind of _open_ semantics in which the closeness
of a constraint needs to be specified with a keyword _close_ (OCT). The
element properties are expressible only over the nodes, except the recent
proposal of RDF-star, that extends RDF exactly with properties over edges
(EP). SHACL and ShEx are missing explicit support for key-like constraints
(KC), but allow for cardinality constraints (CC), to which SHACL applies set
and ShEx bag semantics. The complexity of validation (TV) of RDF-based
formalisms is a well researched topic. While it is not tractable in general
for the most expressive cases, practically useful fragments do have this
property.

#### Tree-structured data

DTDs support union types (UIT) in content type expressions by allowing
disjunction, despite it not being applicable to the names of XML element
types. This is, however, possible in both RELAX NG and XML Schema, where we
have full union types, although both require the regular expressions that
describe the content to be deterministic. DTDs do not support inheritance (TH)
or abstract types (AT), although element types can can be embedded in the
content of other element types. However, RELAX NG and XML Schema have explicit
support for these features. In DTDs, the content of an element can be made
open by using PCDATA, which allows any XML fragment as content, so (OCT) is
more or less supported. In RELAX NG and XML Schema it is possible to have an
even more sophisticated mix of open and closed parts within a content type.
Attributes of XML elements can be declared as required and are optional by
default. For some basic attribute types there are multi-valued variants that
can be assigned, but, otherwise, there are no complex nested attribute types.
Here again, RELAX NG and XML Schema offer a set of type constructors that
enable users to build new and more complex attribute types. Concerning (KC),
both in DTDs and RELAX NG, an attribute can be defined as key, by giving it
the type ID, but there is no way to declare an arbitrary set of attributes as
key. XML Schema, on the other hand, has a very elaborate notion of key
constraint that can define a complex key for elements where this key consists
of several values, is not restricted to attributes of the element, and is
applicable only to a specified set of elements. DTDs support mandatory
participation (MP), since they can require that the content of a certain
element be nonempty or that a certain attribute reference some document
element. This is the case in XML Schema, which also supports foreign keys, and
RELAX NG. DTDs offer some support for (IS), in the sense that they are
regarded as included in the XML document, and so are accessible by software
processing the document. For both XML Schema and RELAX NG there is an XML
syntax, and so they allow full introspection. For DTDs, XML Schema, and RELAX
NG, it holds that XML documents can be created without a schema, but it is
also possible to restrict updates to only allow those which maintain the
document’s conformance to the schema; thus, for (SFPX), both schema-first and
schema-flexible are supported.

JSON Schema supports unions and intersections of open types (UIT), through the
anyOf and, respectively, allOf keywords. The latter also supports building
type hierarchies (TH), but only for open types. Whether types are instantiated
depends on the choice of the root object, and so there is arguably support for
abstract types (AT). One can control whether types are open or closed, by
setting additionalProperties to True or False. Fields are optional by default,
but can be marked as mandatory through the required construct. Range
constraints (RC) are limited to numerical values and strings. Field values
support (CPT), as they can encode nested objects and arrays. Key constraints
(KC) are not supported and cardinality constraints (CC) specify bounds for
arrays. Finally, as the schema is itself a JSON object, it allows
introspection (IS).

#### Existing graph technologies

We now discuss the extent to which type, constraints, and schema features are
supported in several state-of-the-art graph schema languages and systems.

_Type features_ , such as union and intersection types (UIT), type hierarchies
(TH), and abstract types (AT), are largely supported by SQL, GraphQL, and JSON
Schema. These capabilities propagate to SQL-based systems, such as
OrientDB/SQL, and to systems able to leverage JSON Schema, such as ArangoDB
and AgensGraph. The strongly typed TypeDB database has a rich type system that
also offers subtyping for entities, relations, and attributes/properties.
While other considered systems cannot directly handle TH, some can emulate it
through multi-labels, by adding all the intended parent types of a node as its
additional labels. Nevertheless, this is problematic for validation, as one
cannot ensure that all subtypes have been assigned the correct label. Note
that most examined technologies only implement closed types (OCT), except
ArangoDB and OrientDB, in which also open types are possible, and Neo4j, which
considers types open and, hence, extensible, by default.

Nodes and edges can be enriched with element properties (EP) in all surveyed
graph technologies, and in AgensGraph these can be defined using JSON objects.
Such properties are optional by default in AgensGraph, ArangoDB, DataStax,
JanusGraph, Neo4j, and Sparksee, though users can define mandatory constraints
to enforce them being non-nullable. In Nebula Graph, users can specify, when
designing their schema, whether null-valued attributes are allowed, while in
TypeDB these are not supported. Finally, the (MOP) feature is present in SQL-
based technologies. Most reviewed graph languages and system also allow for
(CPT), although specific restrictions are sometimes required. For example, in
Neo4j, complex property values can only be homogeneous lists of simple types
and byte arrays, despite the latter not being first class Cypher data types.
AgensGraph draws its support for (CPT) from openCypher and JSON, while in
Sparksee, multi-valued properties can only be defined using array attributes,
using all but the String and Text data types. In addition, range constraints
(RC) can be specified for any data type, in SQL-based technologies, and for
numerical values and strings, in systems that build on JSON Schema or that
provide regular expressions, such as TypeDB.

Regarding _constraint features_ , we remark that key constraints are available
in all reviewed graph schema languages. At a system level, AgensGraph, Neo4j,
and Sparksee support node uniqueness constraints, disallowing the same
property values from appearing in more than one node of a given label or type,
while ArangoDB enables specifying uniqueItems for arrays, thanks to JSON
Schema. Some technologies, such as DataStax, Oracle/PGQL, and TigerGraph,
offer primary keys for nodes, which enforce property values to be unique,
mandatory, and single-valued. TigerGraph GSQL also supports the notion of a
discriminator, which is an attribute or set of attributes that can be used to
uniquely identify an edge, when multiple instances of a given type exist
between a pair of vertices. Finally, the considered SQL-based systems can rely
on SQL’s mechanism for defining unique key constraints for tables. These
systems also feature mandatory participation (MP) and uniqueness constraints.

More general forms of cardinality constraints (CC) are only provided by a few
systems. Among these, JanusGraph allows to declare edge label multiplicity:
the MULTI and SIMPLE keywords can specify whether multiple edges or at most
one can be defined between any node pair; MANY2ONE and ONE2MANY respectively
allow at most one outgoing/incoming edge, without constraining the number of
incoming/outgoing ones. The system also provides property key cardinalities,
i.e., declaring whether one (SINGLE), an arbitrary number (LIST), or multiple,
non-duplicate values (SET) can be associated with a node key. Other examples
include ArangoDB, leveraging JSON Schema’s minProperties/maxProperties
keywords to restrict the number of object properties, and TypeDB, which
provides high-level CCs at the type level, requiring relationships to have at
least one role that specifies its nature. The system is also one of the only
ones to handle binary constraints (BC), such as symmetry and transitivity, by
expressing them via inference rules. In TigerGraph, the only supported BC
allows declaring reverse edge types.

Tractable validation (TV) is a _schema feature_ supported by systems that
leverage JSON Schema and SQL. In JanusGraph and Sparksee, the schema is
defined through their specific APIs and there is no formal account of their
schema validation mechanisms. Partial conformance (PC) is possible in all
systems that are not exclusively schema-first or that do not have native
schema mechanisms (like ArangoDB, which relies on JSON Schema). Concerning
introspection (IS), all reviewed systems support it either directly, through
the query language itself, or indirectly, via a management API (like in
JanusGraph and Sparksee). Finally, the only reviewed system that natively
supports (SPFX) is OrientDB/SQL, which has schema-first, schema-less, and
explicit schema-hybrid modes.

###  5.3. Possible Extensions of PG-Schema

We discuss how currently unsupported features from Table 1 could be integrated
into PG-Schema.

#### Range constraints.

Some schema languages allow for range constraints (RC). The syntax of PG-
Schema can be thus extended, specifying restrictions on acceptable values for
properties. For instance, the following example defines a node type Book, with
properties title (a string with maximum 100 characters), genre (an
enumeration), and isbn (a string conforming to a regular expression):

⬇

(bookType: Book {

title STRING(100),

genre ENUM("Prose", "Poetry", "Dramatic") ,

isbn STRING ^(?=(?:\D*\d){10}(?:(?:\D*\d){3})?$)[\d-]+$

})

The restrictions in the example above can be based on XSD facets (Peterson et
al., 2012), and additional features can be similarly implemented.

#### Complex datatypes.

We have only included primitive datatypes in PG-Schema. Looking at the CPT
column in Table 1 we see that complex property values are widely supported in
other formalisms. Our syntax can easily be extended to support collections.
For instance, if we wish to specify that a name is an array of strings, we
could write name STRING ARRAY {1,2}. The (optional) curly braces specify the
minimum (the first value in curly braces) and the maximum number (the second
value in curly braces) of elements in the array.

#### Intersections and unions for content types.

In Section 4, we assumed that union and intersection can be used in element
types. Such combinations can also be introduced into properties (see UIT in
Table 1). We can for example allow the _union_ (|) and _intersection_ (&)
operators from label expressions also between property types and between
content types. The following example allows the name to be broken down into a
givenName and a familyName:

⬇

(personType: Person

( { name STRING } |

{ givenName STRING, familyName STRING } )

{ height (INT | FLOAT) })

Note that we use round brackets to group content definitions.

#### Advanced cardinalities.

The notation of PG-Keys can be readily extended to specify cardinality
constraints by taking the general form FOR $p(x)$ <qualifier> $q(x,\bar{y})$,
and allowing for <qualifier> an expression of the form COUNT <lower
bound>?..<upper bound>? OF, expressing that the number of distinct results
returned by $q(x,\bar{y})$ must be within that range. If the upper bound and
lower bound are identical, we allow the short-hand COUNT <bound> OF.

The constraint stating that each department has at least two employees working
for it, could be written as

⬇

FOR (d: Department) COUNT 2.. OF e

WITHIN (e: Employee)-[:worksIn]->(d) .

And if employees can work on at most 3 projects, this could be written as

⬇

FOR (e: Employee) COUNT 0..3 OF p

WITHIN (e)-[: worksOn]->(p: Project) .

This notation also allows us to express disjointness and denial constraints
without using negation in patterns. For example, if reptiles cannot be
amphibians, we can write this as

⬇

FOR (a: Amphibian) COUNT 0 OF (a: Reptile) .

As discussed in (Bonifati et al., 2022a), such constraints are relevant for
many practical use cases and can be efficiently evaluated.

##  6\. Summary and Looking ahead

PG-Schema is the first unifying schema language for property graphs, which
serves as a recommendation for future versions of GQL. This work is the result
of academia and industry collaborating to bridge gaps and accelerate
standardization efforts that benefit both communities at large.

#### Summary

PG-Schema is a schema language that caters for basic needs such as defining
node and edge types, as well as advanced scenarios such as expressing complex
type hierarchies and integrity constraints. It has been designed to support
both descriptive and prescriptive roles, with a focus on enabling agile
evolution, flexible validation, and usability. The language comes with an
ASCII-art, yet formal, syntax and a well-defined semantics. The core of PG-
Schema centers around the rich PG-Types type system, with desirable features
such as compositionality, abstract types, type hierarchies, and multi-
inheritance, as well as around PG-Keys, which allows the expression of complex
key and participation constraints. The language thus supports a wide-range of
capabilities, largely absent from the state-of-the-art schema languages and
systems we have reviewed. Finally, PG-Schema is easily extensible with further
features, such as range constraints, complex data types, content type
combinators, and advanced cardinalities.

#### Looking Ahead

In addition to impact on standardization efforts, this is an opportunity for
graph database vendors to increase functionality and support current and
future customer demands. Our work also provides a basis for future research by
the academic community. Finally, this successful high-impact academia-industry
collaboration model is one we hope will be replicated by other communities at
large, in data management and beyond.

## References

  * (1)
  * 9075-16 (2022) ISO/IEC 9075-16. 2022\.  _Information technology — Database languages SQL — Part 16: Property Graph Queries (SQL/PGQ)_.  Standard. International Organization for Standardization, Geneva, CH.
  * AgensGraph (2022) AgensGraph. 2022\.  AgensGraph.  https://bitnine.net/agensgraph (visited: 2022-11).
  * Angles et al. (2018) Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt. 2018.  G-CORE: A Core for Future Graph Query Languages. In _SIGMOD Conference_. ACM, 1421–1432.
  * Angles et al. (2021) Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Keith W. Hare, Jan Hidders, Victor E. Lee, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Josh Perryman, Ognjen Savkovic, Michael Schmidt, Juan F. Sequeda, Slawek Staworko, and Dominik Tomaszuk. 2021.  PG-Keys: Keys for Property Graphs. In _International Conference on Management of Data (SIGMOD)_. ACM, 2423–2436.
  * ArangoDB (2022) ArangoDB. 2022.  ArangoDB.  https://www.arangodb.com/ (visited: 2022-11).
  * Baker and Prud’hommeaux (2019) Thomas Baker and Eric Prud’hommeaux. 2019.  _Shape Expressions (ShEx) 2.1 Primer_.  W3C Community Group Final Report. W3C.  https://shex.io/shex-primer/index.html.
  * Berners-Lee et al. (2001) Tim Berners-Lee, James Hendler, and Ora Lassila. 2001\.  The semantic web.  _Scientific american_ 284, 5 (2001), 34–43.
  * Bonifati et al. (2022a) Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Matthias Hofer, Wim Martens, Filip Murlak, Joshua Shinavier, Sławek Staworko, and Dominik Tomaszuk. 2022a.  Threshold Queries in Theory and in the Wild.  _Proc. VLDB Endow._ 15, 5 (may 2022), 1105–1118.  https://doi.org/10.14778/3510397.3510407
  * Bonifati et al. (2022b) Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, and Mingxi Wu. 2022b.  domel/pgschema: PG-Schema Grammar 0.3.  (Nov 2022).  https://doi.org/10.5281/zenodo.7362078 https://zenodo.org/record/7362078.
  * Bonifati et al. (2022c) Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, and Mingxi Wu. 2022c.  PG-Schema: Schemas for Property Graphs.  https://doi.org/10.48550/arXiv.2211.10962
  * Bonifati et al. (2022d) Angela Bonifati, Stefania-Gabriela Dumbrava, Emile Martinez, Fatemeh Ghasemi, Malo Jaffré, Pacome Luton, and Thomas Pickles. 2022d.  DiscoPG: Property Graph Schema Discovery and Exploration.  _Proc. VLDB Endow._ 15, 12 (2022), 3654–3657.  https://www.vldb.org/pvldb/vol15/p3654-bonifati.pdf
  * Bonifati et al. (2019) Angela Bonifati, Peter Furniss, Alastair Green, Russ Harmer, Eugenia Oshurko, and Hannes Voigt. 2019\.  Schema Validation and Evolution for Graph Databases. In _ER_ _(Lecture Notes in Computer Science, Vol. 11788)_. Springer, 448–456.
  * Bracha and Cook (1990) Gilad Bracha and William R. Cook. 1990.  Mixin-based Inheritance. In _Conference on Object-Oriented Programming Systems, Languages, and Applications / European Conference on Object-Oriented Programming, OOPSLA/ECOOP 1990, Ottawa, Canada, October 21-25, 1990, Proceedings_ , Akinori Yonezawa (Ed.). ACM, 303–311.  https://doi.org/10.1145/97945.97982
  * Brickley and Guha (2014) Dan Brickley and Ramanathan Guha. 2014.  _RDF Schema 1.1_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2014/REC-rdf-schema-20140225/.
  * Browser (2022a) Neo4J Browser. 2022a.  Neo4J Browser.  https://neo4j.com/product/developer-tools/#browser (visited: 2022-11).
  * Browser (2022b) Tom Sawyer Graph Database Browser. 2022b.  Tom Sawyer Graph Database Browser.  https://www.tomsawyer.com/graph-database-browser (visited: 2022-11).
  * Chen (1976) Peter P. Chen. 1976\.  The Entity-Relationship Model - Toward a Unified View of Data.  _ACM Trans. Database Syst._ 1, 1 (1976), 9–36.
  * Corman et al. (2018) Julien Corman, Juan L. Reutter, and Ognjen Savkovic. 2018\.  Semantics and Validation of Recursive SHACL. In _International Semantic Web Conference (1)_ _(Lecture Notes in Computer Science, Vol. 11136)_. Springer, 318–336.
  * DataStax (2022) DataStax. 2022.  DataStax.  https://www.datastax.com/ (visited: 2022-11).
  * Deutsch et al. (2022) Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. 2022\.  Graph Pattern Matching in GQL and SQL/PGQ. In _SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022_ , Zachary Ives, Angela Bonifati, and Amr El Abbadi (Eds.). ACM, 2246–2258.
  * Deutsch et al. (2019) Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. 2019\.  TigerGraph: A Native MPP Graph Database.  _CoRR_ abs/1901.08248 (2019).
  * Elmasri and Navathe (2015) Ramez Elmasri and Shamkant B. Navathe. 2015.  _Fundamentals of Database Systems (7th edition)_ (7th ed.).  Pearson.
  * Facebook (2018) Facebook. 2018.  GraphQL.  https://spec.graphql.org/June2018/.
  * Fowler (2003) Martin Fowler. 2003\.  _UML Distilled: A Brief Guide to the Standard Object Modeling Language_ (3 ed.).  Addison-Wesley Longman Publishing Co., Inc., USA.
  * Francis et al. (2018) Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018\.  Cypher: An Evolving Query Language for Property Graphs. In _SIGMOD Conference_. ACM, 1433–1445.
  * Gosnell and Broecheler (2022) D.K. Gosnell and M. Broecheler. 2022.  The Practitioner’s Guide to Graph Data.  https://gra.fo/faq/ (visited: 2022-11).
  * Gra.fo (2022) Gra.fo. 2022.  Gra.fo.  https://gra.fo/faq/ (visited: 2022-11).
  * GraphStudioTM (2022) TigerGraph GraphStudioTM. 2022\.  TigerGraph GraphStudioTM.  https://docs.tigergraph.com/gui/current/graphstudio/overview (visited: 2022-11).
  * Groz et al. (2022) Benoît Groz, Aurélien Lemay, Slawek Staworko, and Piotr Wieczorek. 2022.  Inference of Shape Graphs for Graph Databases. In _25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference)_ _(LIPIcs, Vol. 220)_ , Dan Olteanu and Nils Vortmeier (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1–14:20.  https://doi.org/10.4230/LIPIcs.ICDT.2022.14
  * Halpin (2015) Terry Halpin. 2015\.  _Object-Role Modeling Fundamentals: A Practical Guide to Data Modeling with ORM_.  Technics Publications.
  * Hartig (2017) Olaf Hartig. 2017\.  RDF* and SPARQL*: An Alternative Approach to Annotate Statements in RDF.. In _International Semantic Web Conference (Posters, Demos & Industry Tracks)_.
  * Hartig and Pérez (2018) Olaf Hartig and Jorge Pérez. 2018.  Semantics and complexity of GraphQL. In _Proceedings of the 2018 World Wide Web Conference_. 1155–1164.
  * Hitzler et al. (2012) Pascal Hitzler, Sebastian Rudolph, Markus Krötzsch, Peter Patel-Schneider, and Bijan Parsia. 2012\.  _OWL 2 Web Ontology Language Primer (Second Edition)_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2012/REC-owl2-primer-20121211/.
  * ISO/IEC 19757-2:2008 (2008) ISO/IEC 19757-2:2008 2008.  _Information technology — Document Schema Definition Language (DSDL) — Part 2: Regular-grammar-based validation — RELAX NG_.  Standard. International Organization for Standardization, Geneva, CH.
  * JanusGraph (2022) JanusGraph. 2022\.  JanusGraph.  https://janusgraph.org/ (visited: 2022-11).
  * Knublauch and Kontokostas (2017) Holger Knublauch and Dimitris Kontokostas. 2017.  _Shapes Constraint Language (SHACL)_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2017/REC-shacl-20170720/.
  * Lanthaler et al. (2014) Markus Lanthaler, Richard Cyganiak, and David Wood. 2014\.  _RDF 1.1 Concepts and Abstract Syntax_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/.
  * Needham and Hodler (2019) Mark Needham and Amy E. Hodler. 2019.  _Graph Algorithms_.  O’Relly Media.
  * Neo4j (2016) Neo4j 2016.  _The Definitive Guide to Graph Databases for the RDBMS Developer_.  Neo4j.
  * Notebooks (2022) Graph Notebooks. 2022\.  Graph Notebooks.  https://github.com/aws/graph-notebook (visited: 2022-11).
  * Oracle (2022) Oracle. 2022.  Oracle Spatial and Graph.  https://www.oracle.com/database/technologies/spatialandgraph.html (visited: 2022-11).
  * OrientDB (2022) Ltd OrientDB. 2022\.  OrientDB.  https://orientdb.org/ (visited: 2022-11).
  * Peterson et al. (2012) David Peterson, Sandy Gao, Paul V. Biron, Michael Sperberg-McQueen, Ashok Malhotra, and Henry Thompson. 2012.  _W3C XML Schema Definition Language (XSD) 1.1 Part 2: Datatypes_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2012/REC-xmlschema11-2-20120405/.
  * Pezoa et al. (2016) Felipe Pezoa, Juan L. Reutter, Fernando Suárez, Martín Ugarte, and Domagoj Vrgoč. 2016.  Foundations of JSON Schema. In _Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11 - 15, 2016_ , Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, and Ben Y. Zhao (Eds.). ACM, 263–273.  https://doi.org/10.1145/2872427.2883029
  * Robinson et al. (2015) Ian Robinson, Jim Webber, and Emil Eifrem. 2015.  _Graph Databases_.  O’Reilly Media.
  * Ryman et al. (2013) Arthur G Ryman, Arnaud Le Hors, and Steve Speicher. 2013\.  OSLC Resource Shape: A language for defining constraints on Linked Data.  _LDOW_ 996 (2013).
  * Sahu et al. (2020a) Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M. Tamer Özsu. 2020a.  The ubiquity of large graphs and surprising challenges of graph processing: extended survey.  _VLDB J._ 29, 2-3 (2020), 595–618.
  * Sahu et al. (2020b) Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M. Tamer Özsu. 2020b.  The ubiquity of large graphs and surprising challenges of graph processing: extended survey.  _The VLDB Journal_ 29, 2 (2020), 595–618.  https://doi.org/10.1007/s00778-019-00548-x
  * Sakr et al. (2021) Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid G. Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer Özsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, Gábor Szárnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki. 2021.  The future is big graphs: a community view on graph processing systems.  _Commun. ACM_ 64, 9 (2021), 62–71.
  * Sperberg-McQueen et al. (2012) Michael Sperberg-McQueen, Henry Thompson, David Beech, Murray Maloney, Noah Mendelsohn, and Sandy Gao. 2012.  _W3C XML Schema Definition Language (XSD) 1.1 Part 1: Structures_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2012/REC-xmlschema11-1-20120405/.
  * Staworko et al. (2015) Slawomir Staworko, Iovka Boneva, José Emilio Labra Gayo, Samuel Hym, Eric Gordon Prud’Hommeaux, and Harold Solbrig. 2015.  Complexity and Expressiveness of ShEx for RDF. In _18th International Conference on Database Theory (ICDT 2015)_.
  * Technologies (2022) Sparsity Technologies. 2022\.  Sparksee.  https://sparsity-technologies.com/#sparksee (visited: 2022-11).
  * Technology (2022) Neo Technology. 2022\.  Neo4j.  https://neo4j.com/ (visited: 2022-11).
  * Thalheim (2018) Bernhard Thalheim. 2018\.  Extended Entity-Relationship Model.  In _Encyclopedia of Database Systems, Second Edition_ , Ling Liu and M. Tamer Özsu (Eds.). Springer.  https://doi.org/10.1007/978-1-4614-8265-9_157
  * TigerGraph (2022) TigerGraph. 2022\.  TigerGraph.  https://www.tigergraph.com/ (visited: 2022-11).
  * Tomaszuk (2017) Dominik Tomaszuk. 2017\.  RDF validation: A brief survey. In _International Conference: Beyond Databases, Architectures and Structures_. Springer, 344–355.
  * van Rest et al. (2016) Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. 2016.  PGQL: a property graph query language. In _GRADES_. ACM, 7\.
  * Vaticle (2022) Vaticle. 2022.  TypeDB.  https://vaticle.com/ (visited: 2022-11).
  * Wileński and Tomaszuk (2022) Damian Wileński and Dominik Tomaszuk. 2022.  damianw27/pgs-grammar-check: Version 1.0.0.  (Nov 2022).  https://doi.org/10.5281/zenodo.7344227 Available at https://damianw27.github.io/pgs-grammar-check/.
  * Wright et al. (2020) Austin Wright, Henry Andrews, Ben Hutton, and Greg Dennis. 2020\.  _JSON Schema: A Media Type for Describing JSON Documents_.  Draft. Internet Engineering Task Force.
  * Wu et al. (2022) Min Wu, Xinglu Yi, Hui Yu, Yu Liu, and Yujue Wang. 2022.  Nebula Graph: An open source distributed graph database.  _CoRR_ abs/2206.07278 (2022).
  * Yergeau et al. (2008) François Yergeau, Michael Sperberg-McQueen, Tim Bray, Jean Paoli, and Eve Maler. 2008\.  _Extensible Markup Language (XML) 1.0 (Fifth Edition)_.  W3C Recommendation. W3C.  https://www.w3.org/TR/2008/REC-xml-20081126/.

##  Appendix A PG-Schema Grammar

The core productions of the PG-Schema grammar in EBNF are presented in Figure
3. The nonterminals label, key, and propertyType are instantiated as string
representations of labels ($\mathcal{L}$), keys ($\mathcal{K}$), and base
property types ($\mathcal{B}$). The full grammar and railroad diagrams
(Bonifati et al., 2022b) are available at https://github.com/domel/pgschema. A
third-party implementation (Wileński and Tomaszuk, 2022) is available at
https://damianw27.github.io/pgs-grammar-check/.

⬇

pgschema ::= (createType ";"?)+

createType ::= createNodeType | createEdgeType | createGraphType

createNodeType ::= CREATE NODE TYPE (ABSTRACT)? nodeType

createEdgeType ::= CREATE EDGE TYPE (ABSTRACT)? edgeType

createGraphType ::= CREATE GRAPH TYPE graphType

graphType ::= typeName graphTypeMode graphTypeImports? graphTypeElements

graphTypeMode ::= STRICT | LOOSE

graphTypeImports ::= IMPORTS typeName ("," typeName)*

graphTypeElements ::= "{" elementTypes? "}"

elementTypes ::= elementType ("," elementType )*

elementType ::= typeName | nodeType | edgeType

nodeType ::= "(" typeName labelPropertySpec ")"

edgeType ::= endpointType "-" middleType "->" endpointType

middleType ::= "[" typeName labelPropertySpec "]"

endpointType ::= "(" labelPropertySpec ")"

labelPropertySpec ::= (":" labelSpec)? OPEN? propertySpec?

labelSpec ::= "(" labelSpec ")"

| "[" labelSpec "]"

| labelSpec ( ( "|" | "&" ) labelSpec | "?" )

| label | typeName

propertySpec ::= "{" (properties ("," OPEN)? | OPEN)? "}"

properties ::= property ("," property)*

property ::= (OPTIONAL)? key propertyType

typeName ::= StringLiteral

label ::= $l$ for  $l\in\mathcal{L}$

key ::= $k$ for  $k\in\mathcal{K}$

propertyType ::= $b$ for  $b\in\mathcal{B}$

Figure 3. Core productions of the PG-Schema grammar with labels $\mathcal{L}$,
keys $\mathcal{K}$, and base property types $\mathcal{B}$

##  Appendix B A Graph-based Data Catalog

An enterprise data catalog is a metadata management tool that companies use to
inventory data resources and organize the data within their systems. Data
catalogs enable data discovery in order to empower the company’s workforce to
search and find data, get more information from data investments, gaining
better data insights as a whole, and making smart business decisions quickly.

To accomplish this, data catalogs need to create and manage collections of
data and curate the relationships among them, to provide a unified view of the
data landscape to data producers (e.g. data engineers) and data consumers
(e.g. data scientists and analysts). These collections traditionally include
tables and columns of a database, business glossary terms, analysis, and
reports from BI dashboards, but quickly evolve to include all types of data
resources (e.g. ETL tools, DBT models, proprietary data systems, ML models,
the latest data tech, etc).

Businesses evolve quickly, and with that evolution come changes in the data
landscape. For example, when a company acquires another company, they also
acquire all their data systems. These new data systems need to be catalogued
and related to the existing business terminology, in order to provide a
holistic view of the new data landscape. Thus, a data catalog must be able to
keep up with the pace of business evolution, and understand what data
resources exist, what new data resources are coming in, and how these are
related. Therefore, there is a need to have a formalism to describe the set of
known data resources and the growing and evolving set of unknown data
resources that a company may encounter. This evolution can be empowered by PG-
Schema (R7), allowing for flexible definitions of node types, content types
and relationship types.

Property Graphs provide an intuitive way to model data catalog concepts via
different kinds of relationships. The catalogs and different types of data
resources the contain (such as databases tables, columns, or any other data
injected in the system) are naturally modelled as graph nodes; the containment
relationships are encoded as typing inheritance relationships (R6) (i.e.
tables, columns etc. are node subtypes of the resource node type), while the
data lineage relationships (such as the information about derivations of each
resource from other resources) can be represented as graph edges. Exploring a
dataset and its downstream resources can be easily represented as quantified
path pattern matching (Deutsch et al., 2022). Furthermore, as new data
resources emerge and their attributes evolve, schema needs to accommodate the
changes flexibly (R7).

Property Graph schemas need to capture node and edge types, type hierarchy,
meanwhile providing flexibility for fast-evolving business landscape where new
data types and relationships emerge frequently. For example, if a schema is
defined for a certain type (e.g. Data Transformation resource), and a new
subtype is defined representing a new data resource that has been acquired
(e.g. Vendor A’s ETL tool resource), the data catalog’s integrity needs to be
enforced based on the original type (R6) . Combinations of flexible schemas
with partial schemas can be devised in this case, to cover the evolution of
data catalogs.

Figure 4 illustrates the PG-Schema of a data catalog. Node types (R1) include
Catalog representing the collection of data resources, the abstract type
DataResource representing all data resources, and its subclasses (R6)
Database, Table, Column etc. each representing a concrete data resource type.
Edge types (R2) include hasResource connecting Catalog nodes to any
DataResources nodes, derivedFrom connecting DataResources to DataResources
indicating their lineage, and other types such as hasTable and hasColumn
indicating the containment relationships between data resources. Node and edge
types have also defined their properties (R3). Some of the specified types
(CatalogGraph, Table, Column etc.) have identities (R4).

⬇

CREATE GRAPH TYPE CatalogGraphType STRICT {

(CatalogType: Catalog {id INT}),

(DataResourceType: DataResource),

(DatabaseType: DataResourceType

{path STRING, owner STRING}),

(TableType: DataResourceType {id INT, name STRING}),

(ColumnType: DataResourceType

{id INT, name STRING, dataType STRING}),

(GraphType: DataResourceType {id INT, name STRING}),

(:CatalogType)

-[HasResourceType: hasResource {since DATE}]->

(:DataResourceType),

(:DataResourceType)

-[DerivedFromType: derivedFrom {since DATE}]->

(:DataResourceType),

(:DatabaseType)-[HasTableType: hasTable {since DATE}]->

(:TableType),

(:TableType)-[HasColumnType: hasColumn {since DATE}]->

(:ColumnType),

FOR (CatalogType) EXCLUSIVE c.id WITHIN (c CatalogType)

...

}

Figure 4. PG-Schema of a graph-based data catalog.

PG-Schema are by definition flexible and agile, and by building a data catalog
on a property graph and its companion PG-Schema, they enable the flexibility
of extending that same graph schema across any new sources of data that
organizations acquire (R7–R8). Schema validation and efficient error reporting
(R11) must be guaranteed thanks to the agile property types and constraints.
In fact, the very nature of a property graph schema makes it easy to extend
the data catalog alongside growing graph ecosystems (Sakr et al., 2021).

##  Appendix C Existing Graph Schema Languages

##### Conceptual Data Models

By _conceptual data models_ we mean here data models that aim to be conceptual
in nature, i.e., closer and more faithful to the _Universe of Discourse_ of
the stakeholders than traditional database models, such as the relational
model, aim to be. Typical examples of conceptual data models are the Entity-
Relationship Model (Chen, 1976) and its various extensions which are usually
described as EER models and include the _Extended Entity-Relationship Model_
(Thalheim, 2018) and the various _Enhanced Entity-Relationship Models_ that
can be found in database text books such as (Elmasri and Navathe, 2015). Other
conceptual data models that were inspired by ER but have some important
differences are _ORM2 diagrams_ (Halpin, 2015) and _UML Class diagrams_ when
used for the conceptual perspective (Fowler, 2003).

Typically conceptual data models are not used as native data models of DBMSs
or data stores, but are mapped to the data model that is supported by the DBMS
that is used in the implementation. Therefore the semantics of diagrams in ER,
EER and ORM are usually defined in terms of mappings to the relational model.
They have in common that the data is modelled in terms of entities,
relationships and attributes, although there is variation in how these are
exactly defined. The ability to express constraints is typically limited to
what can be effectively mapped to an SQL DBMS, with the notable exception of
UML Class diagrams which allow constraints to be expressed in the Turing-
complete language OCL.

##### RDF formalisms

The Resource Description Framework (RDF) (Lanthaler et al., 2014) is the World
Wide Web Consortium (W3C) recommendation for representing data interchange on
the Semantic Web (Berners-Lee et al., 2001). RDF corresponds to a directed,
edge-labeled multigraph, which links Web resources. These are identified by
Internationalized Resource Identifiers (IRIs) and described by properties and
property values. Thus, an RDF graph is a set of triples, each specifying a
given resource’s identifier (subject node), property (predicate edge), and
corresponding property value (object node). RDF is innately self-describing
and prominently supports a _schema-flexible approach_ whereby data is allowed
to evolve naturally, unconstrained by an a priori schema. To describe the
structure of RDF data, the W3C proposed the RDF Schema (RDFS) (Brickley and
Guha, 2014) and, subsequently, the Web Ontology Language (OWL) (Hitzler et
al., 2012). Both provide additional vernacular for resource properties and
classes and, thus, allow the organizing of RDF data according to a typed
hierarchy. Recently, RDF data shape languages (Tomaszuk, 2017) (e.g. SHACL
(Knublauch and Kontokostas, 2017; Corman et al., 2018), ShEx (Baker and
Prud’hommeaux, 2019; Staworko et al., 2015), ReSh (Ryman et al., 2013)) have
been proposed to address the growing need for schemas for RDF and describing
RDF graph structures. It should be mentioned that RDF Schema, contrary to what
its name may suggest, is not a schema language in the classical sense but is
primarily used to infer implicit facts. RDF data shape languages define
conditions that RDF (data) graphs must meet to be considered ”conformant”:
which nodes and edges may appear in a given graph, in what combinations, and
with what datatypes. The main difference between RDF formalisms and our
proposal is that RDF does not support properties for edges333RDF-star supports
this feature, but currently, solutions such as SHACL and ShEx do not support
RDF-star (Hartig, 2017). Both ShEx and SHACL allow greater expression
possibilities in the areas of cardinality, constraints on values, and datatype
facets.

##### Tree-structured data

Tree-structured data is organized in a hierarchy that starts from a root
element and branches out to its child elements, each of which can have further
sub-elements. Prominent tree-structured data languages include XML and JSON,
each with their dedicated schema formalisms.

For XML, the main schema languages are Document Type Definition (DTD) (Yergeau
et al., 2008), XML Schema (Sperberg-McQueen et al., 2012), and REgular
LAnguage for XML Next Generation (RELAX NG) (ISO/IEC 19757-2:2008, 2008). The
former specifies, for each element: 1) a regular expression defining the
permitted names of its child nodes, 2) a list of associated attribute names
and whether they are mandatory, and 3) a description of textual content of
elements and attributes. Note that, in DTD, there is no distinction between
element names and their types. This is supported by XML Schema and RELAX NG.
These allow complex type definitions for child nodes and the usage of simple
types (strings, dates, integers, etc.) to describe the content pattern of
elements and attributes.

JSON Schema (Wright et al., 2020) allows describing the desired structure of a
JSON file in terms of recursive rules, accounting for the fact that internal
elements are either object or array nodes. For the former, each outgoing edge
has a different, mandatory label, among an optionally specified list of
possible labels, and children are unordered and can be subject to specific
rules. For the latter, incoming edges are unlabeled, children are ordered, and
one can specify a range for their number, as well as specific rules, for all
or some of them. Additionally JSON Schema provides syntactical mechanisms for
specifying boolean combinations of rules and, thus, for taking the union,
intersection, and complement of schemas.

##### Existing graph technologies

openCypher Schema (Bonifati et al., 2019) is a schema DDL for property graphs,
whose main features are as follows. First, the language enables one to specify
labels and mandatory property, thus strictly typing graph objects. Second, a
schema validation mechanism is proposed, allowing to construct not only
instances, but also schemas, as property graphs, thus facilitating
introspection. Third, the formalism supports defining property keys.
Additionally, graph rewriting rules facilitate update propagation between the
instance and the schema, in a way that preserves consistency.

While not a graph database technology, in the narrow sense of the word,
GraphQL (Facebook, 2018; Hartig and Pérez, 2018) is based on a graph data
model and schema formalism (SDL), consisting of a directed, edge-labeled
multigraph. Its nodes are JSON-style objects, which contain a collection of
fields, each with their own type and with values from back-end data stores
(obtained using resolver functions). Its edges are specified by defining
object fields, whose types are other object fields. Each object field has a
mandatory name and type, as well as zero or more named arguments and
directives (optional or required). An argument allows users to send data that
can affect the outcome of GraphQL operations. When an argument is optional, it
is possible to define a default value. A directive is an additional
configuration that can extend each field with annotations. By default, every
field in GraphQL is nullable, but users can change this using a non-null type
modifier. GraphQL also supports interface and union types.

SQL/PGQ (9075-16, 2022; Deutsch et al., 2022) comprises the novel Part 16 of
the SQL standard. This allows defining graph view schemas from SQL tables, as
well as querying such views through a graph pattern matching mechanism that
resembles that of Cypher, PGQL, and G-CORE.

AgensGraph (AgensGraph, 2022) is a multi-model database based on PostgresQL.
It supports the property graph data model, alongside the relational one and
JSON documents, as well as uniform querying through both the SQL and
openCypher languages.

ArangoDB (ArangoDB, 2022) is a multi-model database system, in which data can
be stored as key or value pairs, documents or graphs and uniformly queried
using the AQL language. While ArangoDB is considered to be essentially schema-
less, one can enforce structure at the document and collection levels using
JSON Schema.

DataStax (DSG) (DataStax, 2022) is a real-time distributed graph database,
which is tightly integrated with Apache Cassandra. The system’s underlying
model is that of a property graph and its query language leverages Apache
TinkerPop’s Gremlin functional language. DataStax’s schema language allows one
to define node and edge labels, as well as property keys and indexes.

JanusGraph (JanusGraph, 2022) is a scalable, distributed database system. It
provides support for the property graph model, as exposed by Apache TinkerPop,
and for querying it using the Gremlin graph traversal language. Graph schemas
can be defined either explicitly, by specifying labels and properties for
nodes and edges, or implicitly, through its DefaultSchemaMaker. This infers
types that are natively supported by the system and automatically assigns
single cardinality to property keys and multiple cardinality to edge labels.

Nebula Graph (Wu et al., 2022) is a distributed native graph database, whose
data model is a directed property graph. The system is schema-full and also
recommends limiting schema modifications (in particular at the level of
node/edge properties), in accordance with its “strong-Schema” paradigm. It
supports both openCypher and nGQL, a Nebula native query language.

Neo4j (Technology, 2022) is a graph database that leverages the property graph
model and its native Cypher query language. While considered to be a schema-
free system, Neo4j allows users to enforce the following constraints: unique
node property, node and relationship property existence, as well as node key
constraints. It also has a mechanism for automatically inferring the schema of
a graph instance that, itself, is seen as a property graph that can be
queried.

Oracle/PGQL (Oracle, 2022; van Rest et al., 2016) leverages a SQL-like query
language for property graphs. Note that we focus only on its graph data model.
Its DDL contains a CREATE PROPERTY GRAPH statement for building a graph from
edge and node tables and storing it as a schema. Keys in node and edge tables
uniquely identify these objects in the graph.

OrientDB/SQL (OrientDB, 2022) is a multi-model database whose engine was built
to natively support the property graph, document, key/value and object models.
The system can handle schema-less, schema-full, and schema-mixed modes,
depending on how classes, i.e., node/edge labels, can be defined. In first
case, classes can either have no properties or only optional ones); in the
second case, classes only have mandatory properties. In the third case,
classes can have both mandatory and optional fields and, moreover, users can
only set constraints for certain fields and add custom fields to records.

Sparksee (Technologies, 2022) is a graph database whose data model is a
directed, label, attributed multigraph. It is a schema-full system, as types
are mandatory, in order to create new graph objects, each of which has an
unique and immutable OID. In terms of integrity restrictions, objects are only
allowed one label, the only multi-valued attributes are Array ones, and
attribute value uniqueness can be specified.

TigerGraph/GSQL (TigerGraph, 2022; Deutsch et al., 2019) is a graph database
system in which users are required to define a fixed schema at the object
level, i.e., node and edge types. The particularities of its GSQL schema
definition are as follows. First, each edge type has a default primary key and
an optional discriminator. This is a set of attributes that enables
distinguishing between edges that share the same pair of source and target
node instances. Even though, by default, the primary keys of the source and
target nodes are used to uniquely identify edge instances, discriminators help
to further differentiate these, when multiple ones link the same node pair.
Second, edges can have reverse counterparts that share their schema and data,
albeit having a different direction and name. Third, GSQL labels are semantic
tags that can be attached to any group of graph elements.

TypeDB/TypeQL (Vaticle, 2022) is a strongly-typed database, whose rich type
system fully implements the Entity-Relationship model, thus providing a
concept-level schema, and whose underlying data model is that of a hypergraph.
Moreover, its TypeQL native query language allows users to extract information
from the graph data and its schema. It also allows reasoning about the data
through rules that essentially correspond to Horn Clauses.