PRSC: From PG to RDF and back,using schemas

Abstract

Property graphs (PG) and RDF graphs are two popular database graph models, but they are not interoperable: data modeled in PG cannot be directly integrated with other data modeled in RDF. This lack of interoperability also impedes the use of the tools of one model when data are modeled in the other.

In this paper, we propose PRSC, a configurable conversion to transform a PG into an RDF graph. This conversion relies on PG schemas and user-defined mappings called PRSC contexts. We also formally prove that a subset of PRSC contexts, called well-behaved contexts, can be used to reverse back to the original PG, and provide the related algorithm. Algorithms for conversion and reversion are available as open-source implementations.

1. Introduction

Graphs are a popular data model in which knowledge is represented through objects and links between these objects. Today, there are two mainly used models of graphs: Property Graphs and RDF.

Property Graphs (PGs) are a family of implementations, in which data are represented with nodes and edges, and labels and properties (key-value pairs) can be attached to these nodes and edges. Property Graphs are not a uniform model: some implementations like Neo4j 1

¹

https://neo4j.com/

only allow exactly one label for each edge. Most PG engines offer easy-to-use graph query languages like Cypher [16] and Gremlin [28] that rely on graph traversal. While no uniform standard has been settled yet, the Property Graph needs a Schema Working Group 2 ²

https://www.w3.org/Data/events/data-ws-2019/assets/position/Juan%20Sequeda.txt

is working towards defining a schema language for PG, and a unified formalization of the PG model. In the rest of this paper, following other authors [2], the variability of implementations is neglected and PGs are considered as a uniform model.

Another popular graph model is the Resource Description Framework (RDF) model [34]. In this model, data are represented with triples that represent links between resources. The resources and the links between them are identified through Internationalized Resource Identifiers (IRI). This data model is a W3C standard, and has been studied through a large quantity of works, like RDFS [9] and OWL [24] for inference, or SHACL [22] for data validation. This model has been extended by RDF-star [20] that helps writing properties on triple terms in a more concise manner, but does not provide exactly the same modeling capabilities as PGs. For example, multiple links with the same predicate between two resources are still not supported and requires using extra constructs, like the occurrence pattern described in the “Triples and occurrences” section of the RDF-star community group final report [19].

While PG and RDF are both based on the idea of using graph data, the choice of one removes the ability to use the tools developed for the other. The maintainers of Amazon Neptune, a graph database service that can support both models independently, report that their users choose the solution that best suits their current use case, then struggle because they are stuck with the tools of this model even if the tools of the other model would better answer the new business problem they have [23]. Generally speaking, this diversity of graph models, and more precisely the lack of interoperability, hinders graph database adoption.

Numerous authors [14,29] highlight the benefits of interoperable systems, and in particular of interoperability between PGs and RDF graphs [15,32,35]. We can distinguish two levels of interoperability: syntactic interoperability and semantic interoperability. The former consists in having common data formats, for example JSON or CSV. The latter consists in having data not only in a common data format, but also that use shared vocabularies. Tim Berners-Lee theorized the 5-star Open-data model.3 ³

https://5stardata.info/en/

In this model, datasets are given a number of stars depending on how interoperable they are. RDF graphs are by design the best candidate to elevate the ranking of data in the 5-star data-model, in particular through the use of shared vocabularies. So, while internally developers may choose RDF or PG databases based on their preferences and the convenience of associated tools, RDF is better suited as a pivot model for interoperable exchange of data.

Among the many questions risen by the interoperability between PGs and RDF graphs, the scenario we want to support is the conversion from PGs to RDF (syntactic interoperability) without information loss, and while promoting the use of existing shared vocabularies (semantic interoperability). The requirement of using of existing shared vocabularies requires a converter to be highly customizable, in particular in terms of how the produced triples are structured. On the other hand, the requirement of not losing information, i.e. producing reversible conversions, requires to formally study the possible conversions.

In a previous paper [10], we introduced the motivations behind PREC (PG to RDF Experimental Converter), a user-configured mapping from Property Graphs (PG) to RDF graphs and proposed a mapping language, specialized for the PG to RDF conversion problem, to let the user describe how to convert the node labels, the edges and the properties of the original PG to an RDF graph. By converting the data stored in PGs into RDF, users are then able to use all the tools available for RDF. In this paper, we introduce a new mapping language, named PRSC,4 ⁴

PG to RDF: Schema-driven Converter, pronounced “presque”.

driven by a schema and a description of how to convert the elements of the types in the schema to RDF. This mapping language is formally defined, and conditions under which the conversion produced by PRSC is reversible are also defined. Compared to the previous mapping language, this language contains fewer terms and concepts, and should be easier to use. The PRSC engine is available under the MIT license5 ⁵

https://github.com/BruJu/PREC, https://npmjs.com/package/prec.

and can connect both to a Cypher endpoint and a Gremlin endpoint.

The rest of this paper is organized as follows. Section 2 gives an overview of PRSC to understand its principles. Section 3 gives generic formal definitions of PGs and RDF graphs. Section 4 gives a formal definition of a PRSC conversion, which is essentially a formal definition of Section 2. Section 5 studies reversibility, and proves that some contexts can convert PG to RDF graph without information loss. Section 6 discusses the existing works to make easier interoperability between PGs and RDF graphs relatively to PRSC. Section 7 discusses the proposed solution and describes some future works.

2. PRSC in practice

The Property Graph exposed on Fig. 1 describes the relationship between Tintin and Snowy. It is composed of two nodes. The first one holds the label Person and two properties: the first property has “name” as its key and “Tintin” as its value, the second has “job” as its key and “Reporter” as its value, or more simply its name is “Tintin” and its job is “Reporter”. The other node only has one property: the name “Snowy”. These two nodes are connected by an edge that holds one label, TravelsWith, and a property that tells that it is “since” “1978”.

A similar example represented in RDF-star is exposed on Listing 1. Most information that was in the PG is represented by the triples in lines 1–4 and 6. The information about since when Tintin travels with Snowy is represented through a nested RDF-star triple.

Fig. 1.

A small PG about Tintin that serves as a running example in this paper.

Listing 1.

An example of an RDF-star graph in Turtle Format

Using the user-defined mapping, PRSC is able to convert the PG in Fig. 1 into the RDF-star graph in Listing 1, and more generally any Property Graph with the same schema into the corresponding RDF graph. In this paper, we consider that Property Graphs with the same schema as the one in Fig. 1 are Property Graphs where all nodes have either (1) the “Person” label, a “name” property and a “job” property, (2) no label and a “name” property, (3) and where all edges have the “TravelWith” label and a “since” property. The mapping the user must provide to the PRSC engine is exposed on Listing 2 and is in Turtle-star format [27]. Rules are split in two parts:

• The target part that describes which elements of the Property Graph are targeted. The target is described depending on three criteria: (1) whether the element must be an edge or a node, (2) the labels and (3) the properties of the element.

• The production part that describes the triples to produce with a list of template triples. Values in the $\mathit{pvar}$ namespace are mapped to the blank node in the resulting RDF graph. The literals that use $\mathit{valueOf}$ as their datatype are converted to the property values in the RDF graph.

Listing 2.

The PRSC context that maps the PG running example to the RDF graph running example

The mapping, named PRSC context, exposed on Listing 2 reads as follows:

• The first rule is named _:PersonRule (line 1)

• The second rule is named _:NamedRule (line 12).

• The third rule is named _:TravelsWithRule (line 20):

Note that this mechanism of using quoted triples to describe templates in a pure Turtle-star file was already presented in our previous work [10]. Compared to R2RML [14], it lets the user describe the triples to produce with a syntax closer to the triples that will actually be produced, but it is currently impossible to express templated terms in any position. For example, if the user wants to generate a named node <http://example.org/person/{name}> in subject position in which the {name} part is substituted with the value of the name property, R2RML offers it as a native feature. As PRSC is currently unable to generate arbitrary IRIs, nodes and edges from the PG are always mapped to blank nodes and minting IRIs is left for future works.

3. General definitions

This section introduces some standard definitions, mostly inspired from previous works.

3.1. Notations and conventions

Let $\mathit{Str}$ be the set of all strings. Strings are noted between quotes. For example, $\text{“}\mathit{node}\text{”}$ , $\text{“}\mathit{edge}\text{”}$ , $\text{“}\mathit{since}\text{”}$ and $\text{“}\mathit{Snowy}\text{”}$ are strings.

Definition 1 (Domain and image of a function).

For all partial functions $\mathit{f}:\mathit{D}\to \mathit{A}$ , $\mathit{Dom}$ and $\mathit{Img}$ are defined as follows:

$\mathit{Dom}\mathrm{(}\mathit{f}\mathrm{)}=\{\mathit{x}|\exists \mathit{y}\in \mathit{A}\mathrm{,}\text{ such that }\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{y}\}$

$\mathit{Img}\mathrm{(}\mathit{f}\mathrm{)}=\{\mathit{y}|\exists \mathit{x}\in \mathit{D}\mathrm{,}\text{ such that }\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{y}\}$ .

Example 1.

For the partial function $\mathit{inverse}:\mathbb{R}\to \mathbb{R}$ , with $\mathit{inverse}\mathrm{(}\mathit{x}\mathrm{)}=1\mathrm{/}\mathit{x}$ , $\mathit{Dom}\mathrm{(}\mathit{inverse}\mathrm{)}=\mathit{Img}\mathrm{(}\mathit{inverse}\mathrm{)}=\mathbb{R}-\{0\}$ .

Let S be a set, we recall that $2^{\mathit{S}}$ denotes the set of all parts of S.

3.2. Compatible functions

For all functions f, we recall that they can be seen as sets: $\mathit{f}=\{\mathrm{(}\mathit{x}\mathrm{,}\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}|\mathit{x}\in \mathit{Dom}\mathrm{(}\mathit{f}\mathrm{)}\}$ . For all sets S of 2-tuples, S can be seen as a function iff (if and only if) $\forall \mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_2\mathrm{)}\mathrm{,}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{)}\in \mathit{S}\wedge \mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_2\mathrm{)}\in \mathit{S}\Rightarrow {\mathit{y}}_1={\mathit{y}}_2$ .

Example 2.

Consider the three functions ${\mathit{f}}_1$ , ${\mathit{f}}_2$ , ${\mathit{f}}_3$ exposed in Table 1.

Table 1

Some functions defined both with the usual function notation and with a set notation

Function notation	Set notation
${\mathit{f}}_1\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}0& \text{if }\mathit{x}=0\\ 1& \text{if }\mathit{x}=1\end{array}\right.$	${\mathit{f}}_1=\{\mathrm{(}0\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}1\mathrm{)}\}$
${\mathit{f}}_2\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}66& \text{if }\mathit{x}=-2\\ 33& \text{if }\mathit{x}=-1\\ 0& \text{if }\mathit{x}=0\end{array}\right.$	${\mathit{f}}_2=\{\mathrm{(}-2\mathrm{,}66\mathrm{)}\mathrm{,}\mathrm{(}-1\mathrm{,}33\mathrm{)}\mathrm{,}\mathrm{(}0\mathrm{,}0\mathrm{)}\}$
${\mathit{f}}_3\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}10& \text{if }\mathit{x}=0\\ 1& \text{if }\mathit{x}=1\end{array}\right.$	${\mathit{f}}_3=\{\mathrm{(}0\mathrm{,}10\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}1\mathrm{)}\}$

As ${\mathit{f}}_1$ , ${\mathit{f}}_2$ and ${\mathit{f}}_3$ can be defined with a set, it is possible to use the usual set operations.

The set ${\mathit{f}}_1\cup {\mathit{f}}_2=\{\mathrm{(}-2\mathrm{,}66\mathrm{)}\mathrm{,}\mathrm{(}-1\mathrm{,}33\mathrm{)}\mathrm{,}\mathrm{(}0\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}1\mathrm{)}\}$ is a function: the first element of all tuples has a different value. Using a function notation, it may be written as: $$\begin{array}{c}\mathrm{(}{\mathit{f}}_1\cup {\mathit{f}}_2\mathrm{)}\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}66& \text{if }\mathit{x}=-2[{\mathit{f}}_2\mathrm{(}-2\mathrm{)}=66]\\ 33& \text{if }\mathit{x}=-1[{\mathit{f}}_2\mathrm{(}-1\mathrm{)}=33]\\ 0& \text{if }\mathit{x}=0[{\mathit{f}}_1\mathrm{(}0\mathrm{)}={\mathit{f}}_2\mathrm{(}0\mathrm{)}=0]\\ 1& \text{if }\mathit{x}=1[{\mathit{f}}_1\mathrm{(}1\mathrm{)}=1]\end{array}\right.\end{array}$$

On the opposite, ${\mathit{f}}_1\cup {\mathit{f}}_3=\{\mathrm{(}0\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}0\mathrm{,}10\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}1\mathrm{)}\}$ is not a function. Both $\mathrm{(}0\mathrm{,}0\mathrm{)}$ and $\mathrm{(}0\mathrm{,}10\mathrm{)}$ are members of the set ${\mathit{f}}_1\cup {\mathit{f}}_3$ , $\mathrm{(}{\mathit{f}}_1\cup {\mathit{f}}_3\mathrm{)}\mathrm{(}0\mathrm{)}$ would be equal to both ${\mathit{f}}_1\mathrm{(}0\mathrm{)}=0$ and ${\mathit{f}}_3\mathrm{(}0\mathrm{)}=10$ which are different values.

Remark 1.

Instead of using the notation $\{\mathrm{(}{\mathit{x}}_0\mathrm{,}\mathit{f}\mathrm{(}{\mathit{x}}_0\mathrm{)}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{x}}_1\mathrm{,}\mathit{f}\mathrm{(}{\mathit{x}}_1\mathrm{)}\mathrm{)}\mathrm{,}\dots \}$ , the notation $\{{\mathit{x}}_0\mapsto \mathit{f}\mathrm{(}{\mathit{x}}_0\mathrm{)}\mathrm{,}{\mathit{x}}_1\mapsto \mathit{f}\mathrm{(}{\mathit{x}}_1\mathrm{)}\mathrm{,}\dots \}$ is sometimes used to clarify the fact that a set is a function. For example, ${\mathit{f}}_3$ may be noted as ${\mathit{f}}_3=\{0\mapsto 10\mathrm{,}1\mapsto 1\}$ .

Definition 2 (Functions compatibility).

Two functions f and g are compatible iff $\mathit{f}\cup \mathit{g}$ is a function, i.e. $\forall \mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{\mathit{f}}\mathrm{,}{\mathit{y}}_{\mathit{g}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{\mathit{f}}\mathrm{)}\in \mathit{f}\wedge \mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{\mathit{g}}\mathrm{)}\in \mathit{g}\Rightarrow {\mathit{y}}_{\mathit{f}}={\mathit{y}}_{\mathit{g}}$ .

In other words, two functions f and g are compatible iff for every common input, they share the same output i.e. $\forall \mathit{x}\in \mathit{Dom}\mathrm{(}\mathit{f}\mathrm{)}\cap \mathit{Dom}\mathrm{(}\mathit{g}\mathrm{)}$ , $\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}$ .

3.3. Property Graph

Definition 3 (Property Graph).

Following the definition of Angles [2], a property graph $\mathit{pg}$ is defined as the tuple $\mathrm{(}{\mathit{N}}_{\mathit{pg}}\mathrm{,}{\mathit{E}}_{\mathit{pg}}\mathrm{,}\mathit{sr}{c}_{\mathit{pg}}\mathrm{,}\mathit{des}{t}_{\mathit{pg}}\mathrm{,}{\mathit{labels}}_{\mathit{pg}}\mathrm{,}{\mathit{properties}}_{\mathit{pg}}\mathrm{)}$ , where:

${\mathit{N}}_{\mathit{pg}}$ and ${\mathit{E}}_{\mathit{pg}}$ are finite sets with ${\mathit{N}}_{\mathit{pg}}\cap {\mathit{E}}_{\mathit{pg}}=\varnothing$ . ${\mathit{N}}_{\mathit{pg}}$ and ${\mathit{E}}_{\mathit{pg}}$ are respectively the set of nodes and the set of edges of the property graph $\mathit{pg}$ .

$\mathit{sr}{c}_{\mathit{pg}}:{\mathit{E}}_{\mathit{pg}}\to {\mathit{N}}_{\mathit{pg}}$ and $\mathit{des}{t}_{\mathit{pg}}:{\mathit{E}}_{\mathit{pg}}\to {\mathit{N}}_{\mathit{pg}}$ are two total functions. These two functions map each edge to its starting and destination nodes.

${\mathit{labels}}_{\mathit{pg}}:{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\to 2^{\mathit{Str}}$ is a total function. This function maps the nodes and edges to their sets of labels.

${\mathit{properties}}_{\mathit{pg}}:\mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}\times \mathit{Str}\to \mathit{V}$ is a partial function. This function describes the properties of the elements. V is the set of all possible property values. Considering that a property is a key-value pair, it expects two inputs: a node or an edge, and a property key. The output is the property value.

The set of all property graphs is denoted $\mathit{PGs}$ .

In this paper, property graph nodes and edges are grouped under the term element.

In the rest of the paper, when any PG x is introduced, we allow ourselves to use the symbols ${\mathit{N}}_{\mathit{x}}$ , ${\mathit{E}}_{\mathit{x}}$ , ${\mathit{src}}_{\mathit{x}}$ , ${\mathit{dest}}_{\mathit{x}}$ , ${\mathit{labels}}_{\mathit{x}}$ and ${\mathit{properties}}_{\mathit{x}}$ without explicitly defining x as the tuple $\mathrm{(}{\mathit{N}}_{\mathit{x}}\mathrm{,}{\mathit{E}}_{\mathit{x}}\mathrm{,}{\mathit{src}}_{\mathit{x}}\mathrm{,}{\mathit{dest}}_{\mathit{x}}\mathrm{,}{\mathit{labels}}_{\mathit{x}}\mathrm{,}{\mathit{properties}}_{\mathit{x}}\mathrm{)}$ .

Example 3 (Running example of a Property Graph).

The PG exposed on Fig. 1 can formally be defined as the PG denoted $\mathit{TT}$ with

${\mathit{N}}_{\mathit{TT}}=\{{\mathit{n}}_1\mathrm{,}{\mathit{n}}_2\};{\mathit{E}}_{\mathit{TT}}=\{{\mathit{e}}_1\}$

${\mathit{src}}_{\mathit{TT}}=\{{\mathit{e}}_1\mapsto {\mathit{n}}_1\};{\mathit{dest}}_{\mathit{TT}}=\{{\mathit{e}}_1\mapsto {\mathit{n}}_2\}$

${\mathit{labels}}_{\mathit{TT}}=\{{\mathit{n}}_1\mapsto \{\text{“}\mathit{Person}\text{”}\};{\mathit{n}}_2\mapsto \varnothing ;{\mathit{e}}_1\mapsto \{\text{“}\mathit{TravelsWith}\text{”}\}\}$

$$\begin{array}{r}{\mathit{properties}}_{\mathit{TT}}=\left\{\begin{array}{c}\mathrm{(}{\mathit{n}}_1\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Tintin}\text{”};\mathrm{(}{\mathit{n}}_1\mathrm{,}\text{“}\mathit{job}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Reporter}\text{”}\\ \mathrm{(}{\mathit{n}}_2\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Snowy}\text{”};\mathrm{(}{\mathit{e}}_1\mathrm{,}\text{“}\mathit{since}\text{”}\mathrm{)}\mapsto 1978\end{array}\right\}\end{array}$$

Definition 4 (The empty PG).

The empty PG, which is the PG that contains no nodes and no edges, is formalized as follows: ${\mathit{pg}}_{\varnothing }$ with ${\mathit{N}}_{{\mathit{pg}}_{\varnothing }}={\mathit{E}}_{{\mathit{pg}}_{\varnothing }}=\varnothing$ , ${\mathit{src}}_{{\mathit{pg}}_{\varnothing }}={\mathit{dest}}_{{\mathit{pg}}_{\varnothing }}={\mathit{labels}}_{{\mathit{pg}}_{\varnothing }}=\varnothing \to \varnothing$ and ${\mathit{properties}}_{{\mathit{pg}}_{\varnothing }}:\varnothing \times \varnothing \to \varnothing$ .

3.3.1. Renaming Property Graphs and isomorphism

The chosen formal definition of the running example is not the only one that is possible: for example an arbitrary element named a could have been used in place of ${\mathit{n}}_1$ as the first listed node identifier in Example 3.

Definition 5 (Renaming function).

For all sets ${\mathit{N}}_1$ , ${\mathit{N}}_2$ , ${\mathit{E}}_1$ , ${\mathit{E}}_2$ where ${\mathit{N}}_1\cap {\mathit{E}}_1=\varnothing$ and ${\mathit{N}}_2\cap {\mathit{E}}_2=\varnothing$ , a renaming from ${\mathit{N}}_1$ and ${\mathit{E}}_1$ to ${\mathit{N}}_2$ and ${\mathit{E}}_2$ is a bijective function $\mathit{\varphi }:{\mathit{N}}_1\cup {\mathit{E}}_1\to {\mathit{N}}_2\cup {\mathit{E}}_2$ where $\forall \mathit{n}\in {\mathit{N}}_1$ , $\mathit{\varphi }\mathrm{(}\mathit{n}\mathrm{)}\in {\mathit{N}}_2\wedge \forall \mathit{e}\in {\mathit{E}}_1$ , $\mathit{\varphi }\mathrm{(}\mathit{e}\mathrm{)}\in {\mathit{E}}_2$ .

Example 4.

Let $\mathit{T}{T}^{\prime }$ be another formal definition of the PG in Fig. 1 that uses the sets ${\mathit{N}}_{\mathit{T}{T}^{\prime }}=\{\mathit{a}\mathrm{,}\mathit{b}\}$ and ${\mathit{E}}_{\mathit{T}{T}^{\prime }}=\{\mathit{c}\}$ .

An example of a renaming function ${\mathit{\varphi }}_{\mathit{TT}}$ from ${\mathit{N}}_{\mathit{TT}}=\{{\mathit{n}}_1\mathrm{,}{\mathit{n}}_2\}\cup {\mathit{E}}_{\mathit{TT}}=\{{\mathit{e}}_1\}$ to ${\mathit{N}}_{\mathit{T}{T}^{\prime }}=\{\mathit{a}\mathrm{,}\mathit{b}\}\cup {\mathit{E}}_{\mathit{T}{T}^{\prime }}=\{\mathit{c}\}$ is ${\mathit{\varphi }}_{\mathit{TT}}=\{{\mathit{n}}_1\mapsto \mathit{a};{\mathit{n}}_2\mapsto \mathit{b};{\mathit{e}}_1\mapsto \mathit{c}\}$ .

Definition 6 (Property Graph renaming).

Let $\mathit{pg}$ be a property graph, ${\mathit{N}}^{\prime }$ and ${\mathit{E}}^{\prime }$ be two sets and ϕ be a renaming function from ${\mathit{N}}_{\mathit{pg}}$ and ${\mathit{E}}_{\mathit{pg}}$ to ${\mathit{N}}^{\prime }$ and ${\mathit{E}}^{\prime }$ . We define the renamed PG $\mathit{rename}\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{pg}\mathrm{)}={\mathit{pg}}^{\prime }$ as follows:

${\mathit{N}}_{{\mathit{pg}}^{\prime }}={\mathit{N}}^{\prime }=\{\mathit{\varphi }\mathrm{(}\mathit{n}\mathrm{)}|\mathit{n}\in {\mathit{N}}_{\mathit{pg}}\}$

${\mathit{E}}_{{\mathit{pg}}^{\prime }}={\mathit{E}}^{\prime }=\{\mathit{\varphi }\mathrm{(}\mathit{e}\mathrm{)}|\mathit{e}\in {\mathit{E}}_{\mathit{pg}}\}$

${\mathit{src}}_{{\mathit{pg}}^{\prime }}=\{\mathit{e}\mapsto \mathit{\varphi }\mathrm{(}\mathit{sr}{c}_{\mathit{pg}}\mathrm{(}{\mathit{\varphi }}^{-1}\mathrm{(}\mathit{e}\mathrm{)}\mathrm{)}\mathrm{)}|\mathit{e}\in {\mathit{E}}_{{\mathit{pg}}^{\prime }}\}$

${\mathit{dest}}_{{\mathit{pg}}^{\prime }}=\{\mathit{e}\mapsto \mathit{\varphi }\mathrm{(}\mathit{des}{t}_{\mathit{pg}}\mathrm{(}{\mathit{\varphi }}^{-1}\mathrm{(}\mathit{e}\mathrm{)}\mathrm{)}\mathrm{)}|\mathit{e}\in {\mathit{E}}_{{\mathit{pg}}^{\prime }}\}$

${\mathit{labels}}_{{\mathit{pg}}^{\prime }}=\{\mathit{m}\mapsto {\mathit{labels}}_{\mathit{pg}}\mathrm{(}{\mathit{\varphi }}^{-1}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}|\mathit{m}\in {\mathit{N}}_{{\mathit{pg}}^{\prime }}\cup {\mathit{E}}_{{\mathit{pg}}^{\prime }}\}$

${\mathit{properties}}_{{\mathit{pg}}^{\prime }}=\{\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}\mapsto {\mathit{properties}}_{\mathit{pg}}\mathrm{(}{\mathit{\varphi }}^{-1}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{,}\mathit{key}\mathrm{)}|\mathit{m}\in {\mathit{N}}_{{\mathit{pg}}^{\prime }}\cup {\mathit{E}}_{{\mathit{pg}}^{\prime }}\wedge \mathit{key}\in \mathit{Str}\}$

Example 5.

Let us consider back $\mathit{TT}$ , the PG about Tintin defined in Example 3, $\mathit{T}{T}^{\prime }$ the other formalization of the same PG and ${\mathit{\varphi }}_{\mathit{TT}}$ the renaming function introduced in the Example 4.

The PG produced by $\mathit{rename}\mathrm{(}{\mathit{\varphi }}_{\mathit{TT}}\mathrm{,}\mathit{TT}\mathrm{)}=\mathit{T}{T}^{\prime }$ is

${\mathit{N}}_{\mathit{T}{T}^{\prime }}=\{\mathit{a}\mathrm{,}\mathit{b}\};{\mathit{E}}_{\mathit{T}{T}^{\prime }}=\{\mathit{c}\}$

${\mathit{src}}_{\mathit{T}{T}^{\prime }}=\{\mathit{c}\mapsto \mathit{a}\};{\mathit{dest}}_{\mathit{T}{T}^{\prime }}=\{\mathit{c}\mapsto \mathit{b}\}$

${\mathit{labels}}_{\mathit{T}{T}^{\prime }}=\{\mathit{a}\mapsto \{\text{“}\mathit{Person}\text{”}\};\mathit{b}\mapsto \varnothing ;\mathit{c}\mapsto \{\text{“}\mathit{TravelsWith}\text{”}\}\}$

$$\begin{array}{r}{\mathit{properties}}_{\mathit{T}{T}^{\prime }}=\left\{\begin{array}{c}\mathrm{(}\mathit{a}\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Tintin}\text{”};\mathrm{(}\mathit{a}\mathrm{,}\text{“}\mathit{job}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Reporter}\text{”}\\ \mathrm{(}\mathit{b}\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Snowy}\text{”};\mathrm{(}\mathit{c}\mathrm{,}\text{“}\mathit{since}\text{”}\mathrm{)}\mapsto 1978\end{array}\right\}\end{array}$$

Definition 7 (Isomorphic property graph).

Two PGs $\mathit{pg}$ and ${\mathit{pg}}^{\prime }$ are isomorphic iff there exists a renaming function ϕ from ${\mathit{N}}_{\mathit{pg}}$ and ${\mathit{E}}_{\mathit{pg}}$ to ${\mathit{N}}_{\mathit{p}{g}^{\prime }}$ and ${\mathit{E}}_{\mathit{p}{g}^{\prime }}$ such that $\mathit{rename}\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{pg}\mathrm{)}=\mathit{p}{g}^{\prime }$ . Note that because renaming functions are bijectives, it implies that ${\mathit{\varphi }}^{-1}$ exists and $\mathit{rename}\mathrm{(}{\mathit{\varphi }}^{-1}\mathrm{,}\mathit{p}{g}^{\prime }\mathrm{)}=\mathit{pg}$ .

Note that both $\mathit{TT}$ and $\mathit{T}{T}^{\prime }$ from Examples 3 and 4 match the graphical representation given in Fig. 1. An informal way to define the isomorphism between two PGs is to check if they have the same graphical representation.

Existing works [16,33] on PG query languages focus on extracting the properties of some nodes and edges, and never look for the exact identity of the elements. It is therefore possible to affirm that the exact identity is not important, and that if two PGs are isomorphic, they are the same PG for practical matter.

3.4. RDF-star definition

Definition 8 (Atomic RDF terms).

Let I be the infinite set of IRIs, $\mathit{L}=\mathit{Str}\times \mathit{I}$ be the set of literals and B be the infinite set of blank nodes. The sets I, L and B are disjoint.

IRIs, literals and blank nodes are grouped under the name “Atomic RDF terms”.

Notation: In the examples, the IRIs, the elements of I, will be either noted as full IRIs between brackets, e.g. <http://example.org/Tintin> or by using prefixes to shorten the IRI e.g. ex:Tintin. The list of prefixes used in this paper is described in Table 2.

Literals, the elements of L, can be noted either by using the usual tuple notation, e.g. $\mathrm{(}\text{“}\mathit{1978}\text{”}\mathrm{,}\mathtt{xsd}:\mathtt{integer}\mathrm{)}$ or with the compact notation $\text{“}\mathit{1978}{\text{”}}^{\mathit{xsd}:\mathit{integer}}$ .

Finally, the blank nodes, the elements of B, are denoted by blank node labels prefixed with the two symbols “ $\text{\_}:$ ” e.g. $\text{\_}:\mathit{edge}$ , $\text{\_}:\mathit{2021}$ or $\text{\_}:\mathit{node}\mathit{35}$ .

Table 2

List of prefixes used in this paper

Prefix	IRI
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
xsd	http://www.w3.org/2001/XMLSchema#
ex	http://example.org/
prec	http://bruy.at/prec#
pvar	http://bruy.at/prec-var#

Definition 9 (RDF(-star) triples and graphs).

The set of all RDF triples6 is denoted $\mathit{RdfTriples}$ and is defined as follows:

$\forall \mathit{subject}\in \mathit{I}\cup \mathit{B}$ , $\forall \mathit{predicate}\in \mathit{I}$ , $\forall \mathit{object}\in \mathit{I}\cup \mathit{B}\cup \mathit{L}$ , $\mathrm{(}\mathit{subject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{object}\mathrm{)}\in \mathit{RdfTriples}$ .

$\forall \mathit{tsubject}\in \mathit{RdfTriples}$ , $\forall \mathit{tobject}\in \mathit{RdfTriples}$ , and for all $\mathit{subject}$ , $\mathit{predicate}$ and $\mathit{object}$ defined as above, $\mathrm{(}\mathit{tsubject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{object}\mathrm{)}$ , $\mathrm{(}\mathit{subject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{tobject}\mathrm{)}$ and $\mathrm{(}\mathit{tsubject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{tobject}\mathrm{)}$ are members of $\mathit{RdfTriples}$ .

A subset of $\mathit{RdfTriples}$ is an RDF graph.

Both the atomic RDF terms defined in Definition 8 and RDF triples are terms. A triple used in another triple, in subject or object position, is a quoted triple. An RDF triple can not contain itself and can not be nested infinitely.

⁶

For the sake of readability, although RDF-star is not yet part of the official RDF recommendation [34], we conflate RDF-star and RDF in this paper. When we mention an RDF triple or an RDF graph, we allow them to contain quoted triples.

Example 6.

The triple $\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ is an element of $\mathit{RdfTriples}$ . Its Turtle representation is ex:tintin rdf:type ex:Person.

The RDF graph exposed in Listing 1 is composed of 5 triples written in Turtle format. In our formalism, the second triple, _:tintin foaf:name "Tintin", is $\mathrm{(}\text{\_}:\mathit{tintin}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}{\text{”}}^{\mathit{xsd}:\mathit{string}}\mathrm{)}$ .

$\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{ex}:\mathit{travelsWith}\mathrm{,}\mathit{ex}:\mathit{snowy}\mathrm{)}$ is an element of $\mathit{RdfTriples}$ .

$\mathrm{(}\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{ex}:\mathit{travelsWith}\mathrm{,}\mathit{ex}:\mathit{snowy}\mathrm{)}\mathrm{,}\mathit{ex}:\mathit{since}\mathrm{,}\text{“}1978{\text{”}}^{\mathit{xsd}:\mathit{integer}}\mathrm{)}$ is an element of $\mathit{RdfTriples}$ that has a quoted triple in subject position.

Definition 10 (Term membership).

The ∈ operator is extended to triples to check if a term is part of a triple. $$\begin{array}{rl}& \forall \mathit{term}\in \mathit{I}\cup \mathit{B}\cup \mathit{L}\cup \mathit{RdfTriples}\mathrm{,}\forall \mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\in \mathit{RdfTriples}\mathrm{,}\mathit{term}\in \mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\\ & \iff \left[\begin{array}{cc}& \mathit{term}=\mathit{s}\\ \vee & \mathrm{(}\mathit{s}\in \mathit{RdfTriples}\wedge \mathit{term}\in \mathit{s}\mathrm{)}\\ \vee & \mathit{term}=\mathit{p}\\ \vee & \mathit{term}=\mathit{o}\\ \vee & \mathrm{(}\mathit{o}\in \mathit{RdfTriples}\wedge \mathit{term}\in \mathit{o}\mathrm{)}\end{array}\right]\end{array}$$

Example 7 (Term membership examples).

$\mathit{rdf}:\mathit{type}\in \mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ .

$\mathit{ex}:\mathit{snowy}\notin \mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ .

$\text{\_}:\mathit{n}\in \mathrm{(}\text{\_}:\mathit{n}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$

$\text{\_}:\mathit{e}\notin \mathrm{(}\text{\_}:\mathit{n}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$

$\mathit{xsd}:\mathit{string}\in \mathrm{(}\mathit{xsd}:\mathit{string}\mathrm{,}\mathit{ex}:\mathit{p}\mathrm{,}\mathit{ex}:\mathit{o}\mathrm{)}$

$\mathit{xsd}:\mathit{string}\notin \mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{ex}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}{\text{”}}^{\mathit{xsd}:\mathit{string}}\mathrm{)}$

$\mathit{ex}:\mathit{tintin}\in \mathrm{(}\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{ex}:\mathit{travelsWith}\mathrm{,}\mathit{ex}:\mathit{snowy}\mathrm{)}\mathrm{,}\mathit{ex}:\mathit{since}\mathrm{,}\text{“}1978{\text{”}}^{\mathit{xsd}:\mathit{integer}}\mathrm{)}$

Definition 11 (List of blank nodes used in an RDF graph).

For every RDF graph $\mathit{rdf}$ , $\mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}$ is the set of blank nodes in $\mathit{rdf}$ i.e. $\forall \mathit{rdf}\subseteq \mathit{RdfTriples}$ , $\mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}=\{\mathit{bn}\in \mathit{B}|\exists \mathit{t}\in \mathit{rdf}\mathrm{,}\mathit{bn}\in \mathit{t}\}$ .

Example 8.

Let $\mathit{GTT}$ be the RDF graph exposed on Listing 1. $\mathit{BNodes}\mathrm{(}\mathit{GTT}\mathrm{)}=\{\text{\_}:\mathit{tintin}\mathrm{,}\text{\_}:\mathit{snowy}\}$

4. PRSC: Mapping PGs to RDF graphs

PRSC enables the user to convert any Property Graph to an RDF graph by using user-defined templates.

4.1. Property graphs with blank nodes

By default, every node and edge of the PG to convert is mapped by PRSC to an arbitrary fresh blank node. This mapping is arbitrary because blank nodes are essentially interchangeable, and because they have no global identifiers which would allow to map to a specific blank node anyway. This mapping is used throughout the transformation. For the sake of conciseness, we introduce the following modelling trick.

We note that in the respective definitions of PGs and RDF, the sets N and E of nodes and edges (in any PG) and the global set B of blank nodes (in RDF), are very loosely characterized. The only constraints are that N and E are disjoint and finite, and that B is disjoint from the sets of IRIs and literals. Theoretically, nothing prevents a property graph to take its nodes and edges in the set B, in other words, to have $\mathit{N}\subset \mathit{B}$ and $\mathit{E}\subset \mathit{B}$ .

Our arbitrary mapping from $\mathit{N}\cup \mathit{E}$ to fresh blank nodes can then be used as a renaming function to build a new PG that is isomorphic to the original one. As noted in Section 3.3.1, the two PGs are indistinguishable for any practical purpose, including the transformation to an RDF graph. Without loss of generality, all the definitions and algorithms in this paper expect PGs whose nodes and edges are elements of B. This amounts to assume that the arbitrary mapping to blank nodes has been set in advance, and is carried by the PG to transform: every element of $\mathit{N}\cup \mathit{E}$ is identified with the blank nodes it maps to.

Conversely, when we study the reversibility of some contexts in Section 5, we prove that the produced BPG is exactly the original one. Producing a PG with arbitrary elements, and proving that it was isomorphic to the original, would be much more complex.

Definition 12 (Blank Node Property Graph).

$\mathit{BPGs}$ is the set of property graphs with blank nodes only (BPG), i.e. $\mathit{BPGs}=\{\mathit{pg}\in \mathit{PGs}|\mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}\subseteq \mathit{B}\}$ .

Example 9.

By defining the renaming function ${\mathit{\varphi }}_{\mathit{BTT}}=\{{\mathit{n}}_1\mapsto \text{\_}:\mathit{n}\mathit{1};{\mathit{n}}_2\mapsto \text{\_}:\mathit{n}\mathit{2};{\mathit{e}}_1\mapsto \text{\_}:\mathit{e}\mathit{1}\}$ , it is possible to build the BPG $\mathit{BTT}=\mathit{rename}\mathrm{(}{\mathit{\varphi }}_{\mathit{BTT}}\mathrm{,}\mathit{TT}\mathrm{)}$ :

${\mathit{N}}_{\mathit{BTT}}=\{\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\text{\_}:\mathit{n}\mathit{2}\};{\mathit{E}}_{\mathit{BTT}}=\{\text{\_}:\mathit{e}\mathit{1}\}$

${\mathit{src}}_{\mathit{BTT}}=\{\text{\_}:\mathit{e}\mathit{1}\mapsto \text{\_}:\mathit{n}\mathit{1}\};{\mathit{dest}}_{{\mathit{TT}}^{\prime }}=\{\text{\_}:\mathit{e}\mathit{1}\mapsto \text{\_}:\mathit{n}\mathit{2}\}$

${\mathit{labels}}_{\mathit{BTT}}=\{\text{\_}:\mathit{n}\mathit{1}\mapsto \{\text{“}\mathit{Person}\text{”}\};\text{\_}:\mathit{n}\mathit{2}\mapsto \varnothing ;\text{\_}:\mathit{e}\mathit{1}\mapsto \{\text{“}\mathit{TravelsWith}\text{”}\}\}$

$$\begin{array}{r}{\mathit{properties}}_{\mathit{BTT}}=\left\{\begin{array}{c}\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Tintin}\text{”};\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\text{“}\mathit{job}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Reporter}\text{”}\\ \mathrm{(}\text{\_}:\mathit{n}\mathit{2}\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mapsto \text{“}\mathit{Snowy}\text{”};\mathrm{(}\text{\_}:\mathit{e}\mathit{1}\mathrm{,}\text{“}\mathit{since}\text{”}\mathrm{)}\mapsto 1978\end{array}\right\}\end{array}$$

By construction, $\mathit{BTT}$ is isomorphic to $\mathit{TT}$ , and as ${\mathit{N}}_{\mathit{BTT}}\cup {\mathit{E}}_{\mathit{BTT}}\subseteq \mathit{B}$ , $\mathit{BTT}\in \mathit{BPGs}$ .

This may raise the question of the meaning of two BPGs that share the same blank nodes, in particular if one blank node is used as a node in one BGP and as an edge in the other. However, this question could also be raised for all PGs: what would it mean for two PGs to have common elements in their respective sets of nodes and edges? In general, it would not hold any semantics, as PG elements are considered locally for a given PG. However, in Section 5.3.4, we will define operators for PGs, even the ones without blank nodes, that will consider PGs with shared PG elements and their possible relations.

4.2. Type of a PG element and PG schemas

We define the type of a PG element and PG schemas as follows. Let $\mathit{pg}$ be a PG.

Definition 13 (Property keys of an element).

We recall that in Section 2 and in Definition 3, properties are described as key-value pairs.

$\mathit{key}{s}_{\mathit{pg}}$ is the function that maps a PG element (node or edge) of the PG $\mathit{pg}$ to the list of property keys for which it has a value, i.e. ${\mathit{keys}}_{\mathit{pg}}:{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\to 2^{\mathit{Str}}$ , with $\forall \mathit{m}\in \mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}$ , $\mathit{key}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\{\mathit{key}|\mathit{propertie}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}\text{ is defined}\}$ .

Definition 14 (Type of a PG element).

A type is a triple composed of 1) the kind of the PG element, i.e. if it is a node or an edge, 2) a set of labels and 3) a set of property keys. The set of all types is denoted $\mathit{Types}$ and is defined as $\mathit{Types}=\mathrm{(}\{\text{“}\mathit{node}\text{”}\mathrm{,}\text{“}\mathit{edge}\text{”}\}\times 2^{\mathit{Str}}\times 2^{\mathit{Str}}\mathrm{)}$ .

The type of an element $\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ is $$\begin{array}{c}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\left(\left\{\begin{array}{cc}\text{“}\mathit{node}\text{”}& \text{if }\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\\ \text{“}\mathit{edge}\text{”}& \text{if }\mathit{m}\in {\mathit{E}}_{\mathit{pg}}\end{array}\right\}\mathrm{,}{\mathit{labels}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{,}\mathit{key}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\right)\end{array}$$

A set of PG types is named a schema.

The functions $\mathit{kind}$ , $\mathit{labels}$ and $\mathit{keys}$ are defined for types such that $\forall \mathit{type}=\mathrm{(}\mathit{u}\mathrm{,}\mathit{l}\mathrm{,}\mathit{key}\mathrm{)}\in \mathit{Types}$ , $\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\mathit{u}$ , $\mathit{labels}\mathrm{(}\mathit{type}\mathrm{)}=\mathit{l}$ , $\mathit{keys}\mathrm{(}\mathit{type}\mathrm{)}=\mathit{key}$ .

Example 10.

Table 3 shows the types of the PG elements in the running example.

Table 3

The types of the elements in the PG $\mathit{BTT}$

m	$\mathit{typeo}{f}_{\mathit{BTT}}\mathrm{(}\mathit{m}\mathrm{)}$
$\text{\_}:\mathit{n}\mathit{1}$	$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$
$\text{\_}:\mathit{n}\mathit{2}$	$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$
$\text{\_}:\mathit{e}\mathit{1}$	$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$

Remark 2.

If two PGs $\mathit{pg}$ and ${\mathit{pg}}^{\prime }$ are isomorphic, their elements share the same type.

Indeed, by definition, there exists a renaming function ϕ from the elements of $\mathit{pg}$ to the elements of ${\mathit{pg}}^{\prime }$ , and $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{typeo}{f}_{{\mathit{pg}}^{\prime }}\mathrm{(}\mathit{\varphi }\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ .

4.3. Template triples

PRSC resorts to a mechanism of templating: to produce an RDF graph from a PG, we use tuples of three elements, named template triples, that will be mapped to proper RDF triples.

Definition 15 (Placeholders).

There are four distinct elements, not included in either of the previously defined sets, named $\mathit{valueOf}$ , $?\mathit{self}$ , $?\mathit{source}$ and $?\mathit{destination}$ .7

⁷

In practice, our implementation of this paper maps $\mathit{valueOf}$ to the IRI prec:valueOf and all terms prefixed with ? to the pvar namespace. Examples given in Turtle reflect the implementation instead of fully fitting the theoretical definitions.

Let $\mathit{pvars}=\{?\mathit{self}\mathrm{,}?\mathit{source}\mathrm{,}?\mathit{destination}\}$ . $\mathit{pvars}$ elements serve as placeholders that will be replaced by the blank nodes that represent the nodes and edges in the PG.

Let $\mathit{P}=\{\mathrm{(}\mathit{l}\mathrm{,}\mathit{valueOf}\mathrm{)}|\mathit{l}\in \mathit{Str}\}$ . Elements of P can be noted with the same syntax as literals, for example $\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}$ is the pair $\mathrm{(}\text{“}\mathit{name}\text{”}\mathrm{,}\mathit{valueOf}\mathrm{)}$ . Each element of P serves as a placeholder to be replaced with an RDF literal that represents the value of a property in the PG.

Definition 16 (Template triples).

A template triple is a member of $\mathit{Templates}$ and is defined as follows:

$\forall \mathit{subject}\in \mathit{I}\cup \mathit{pvars}$ , $\forall \mathit{predicate}\in \mathit{I}$ , $\forall \mathit{object}\in \mathit{I}\cup \mathit{pvars}\cup \mathit{L}\cup \mathit{P}$ , $\mathrm{(}\mathit{subject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{object}\mathrm{)}\in \mathit{Templates}$ .

$\forall \mathit{tsubject}\in \mathit{Templates}$ , $\forall \mathit{tobject}\in \mathit{Templates}$ , and for all $\mathit{subject}$ , $\mathit{predicate}$ and $\mathit{object}$ defined as above, $\mathrm{(}\mathit{tsubject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{object}\mathrm{)}$ , $\mathrm{(}\mathit{subject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{tobject}\mathrm{)}$ and $\mathrm{(}\mathit{tsubject}\mathrm{,}\mathit{predicate}\mathrm{,}\mathit{tobject}\mathrm{)}$ are members of $\mathit{Templates}$ .

Note that unlike RDF triples, the elements of $\mathit{Templates}$ can not contain blank nodes but can contain placeholders: $\mathit{pvars}$ members can be used in subject (first) and/or object (third) position as they will be mapped later to blank nodes, and members of P are allowed in object position as they will be mapped later to literals. Similarly to RDF triples, template triples can not contain themselves and can not be nested infinitely.

Any subset of $\mathit{Templates}$ is named a template graph. The PRSC engine will use template graphs to produce RDF graphs.

Example 11.

The triple $\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ is both an element of $\mathit{RdfTriples}$ and an element of $\mathit{Templates}$ . Indeed, both $\mathit{RdfTriples}$ and $\mathit{Templates}$ allow IRIs in the subject, predicate and object positions.

The triple $\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ is a member of $\mathit{Templates}$ but not of $\mathit{RdfTriples}$ . The first member is an element of $\mathit{pvars}$ , which is only allowed in template triples. The two other members are IRIs, and $\mathit{pvars}\times \mathit{I}\times \mathit{I}$ is a subset of $\mathit{Templates}$ .

The triple $\mathrm{(}\mathit{ex}:\mathit{tintin}\mathrm{,}\mathit{ex}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}$ is also a member of $\mathit{Templates}$ but not of $\mathit{RdfTriples}$ . While the first two members are IRIs, the third member is an element of P. Again, elements of P are only allowed by template triples.

Definition 17 (Placeholders and template triple membership).

The ∈ operator, which we extended in Definition 10, is further extended to placeholders and template triples: $$\begin{array}{rl}& \forall \mathit{term}\in \mathit{I}\cup \mathit{B}\cup \mathit{L}\cup \mathit{RdfTriples}\cup \mathit{Templates}\mathrm{,}\forall \mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\in \mathit{RdfTriples}\cup \mathit{Templates}\mathrm{,}\\ & \mathit{term}\in \mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\iff \left[\begin{array}{cc}& \mathit{term}=\mathit{s}\\ \vee & \mathrm{(}\mathit{s}\in \mathit{RdfTriples}\cup \mathit{Templates}\wedge \mathit{term}\in \mathit{s}\mathrm{)}\\ \vee & \mathit{term}=\mathit{p}\\ \vee & \mathit{term}=\mathit{o}\\ \vee & \mathrm{(}\mathit{o}\in \mathit{RdfTriples}\cup \mathit{Templates}\wedge \mathit{term}\in \mathit{o}\mathrm{)}\end{array}\right]\end{array}$$

4.4. PRSC context

In this paper, the notion of PRSC context is the keystone to let the user drive the conversion from a PG to an RDF graph. It maps PG types to template graphs. The $\mathit{prsc}$ algorithm proceeds by looping on each node and edge of the PG, computing its type, finding the associated template graph in the context, and replacing the placeholders of this template graph with data extracted from the PG to produce an RDF graph.

Definition 18 (PRSC Context).

A PRSC context $\mathit{ctx}:\mathit{Types}\to 2^{\mathit{Templates}}$ is a partial function that maps types to template graphs.

All template graphs must be valid, i.e. for all types, the placeholders used in the associated template graph must be consistent with the type: (1) for any given property key, its associated placeholder may only be used in template graphs associated with types that contain the property key, for example the placeholder $\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}$ may only be used if the property key $\text{“}\mathit{name}\text{”}$ is in the type associated to this template; (2) and templates associated to node types are not allowed to use the placeholders $?\mathit{source}$ and $?\mathit{destination}$ , as they are related to the source or the destination of an edge.

Formally, all template graphs used by a context $\mathit{ctx}$ are valid iff $\forall \mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}$ :

$\forall \mathrm{(}\mathit{key}\mathrm{,}\mathit{valueOf}\mathrm{)}\in \mathit{P}$ , $\mathrm{(}\exists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}|\mathrm{(}\mathit{key}\mathrm{,}\mathit{valueOf}\mathrm{)}\in \mathit{tp}\mathrm{)}\Rightarrow \mathit{key}\in \mathit{keys}\mathrm{(}\mathit{type}\mathrm{)}$ .

$\mathrm{(}\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{node}\text{”}\mathrm{)}\Rightarrow [\nexists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}|?\mathit{source}\in \mathit{tp}\vee ?\mathit{destination}\in \mathit{tp}]$ .

The set of all context functions is denoted $\mathit{Ctx}$ .

Definition 19 (Complete PRSC contexts for a given PG).

A PRSC context is said complete for a property graph $\mathit{pg}\in \mathit{BPGs}$ iff there is a template graph defined for each type used in $\mathit{pg}$ . The set of all complete contexts for a PG $\mathit{pg}$ is noted ${\mathit{Ctx}}_{\mathit{pg}}=\{\mathit{ctx}\in \mathit{Ctx}|\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{,}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}\}$ .

Remark 3.

Note that the type system described in Definition 14 is trivial to resolve as the type of a PG element m, denoted by $\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ , only depends on its kind (node or edge), the list of its labels and the list of its property keys. For this reason, checking if a PRSC context $\mathit{ctx}$ is complete for a property graph $\mathit{pg}$ is also trivial as it consists in computing the type of each PG element of $\mathit{pg}$ and checking if all types are in the domain of $\mathit{ctx}$ .

Example 12.

Table 4 exposes an example of a complete $\mathit{ctx}$ context function for our running example. First, the function is a context as all template graphs are valid: The placeholders $\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}$ and $\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}$ are only used in types with the associated property key. The fact that the property key $\text{“}\mathit{since}\text{”}$ in the third type has no associated placeholder occurrence in the template graph does not invalidate the context. The placeholders $?\mathit{source}$ and $?\mathit{destination}$ are only used in the third type, which is an edge type. Then, all three types used by our running example have an associated template graph, so it is a complete context for the PG exposed in Example 1.

Table 4

An example of a complete context for the Tintin Property Graph

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\}$

Example 13.

The function $\mathit{ctx}$ exposed in Table 5 is not complete for the PG $\mathit{BTT}$ as its domain lacks the type of $\text{\_}:\mathit{n}\mathit{2}$ and the type of $\text{\_}:\mathit{e}\mathit{1}$ .

Table 5

An incomplete context for the Tintin PG

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$

Example 14.

The function $\mathit{ctx}$ exposed in Table 6 is not a context because $\text{“}\mathit{surname}\text{”}$ , which is used in the template graph mapped to the first listed type $\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$ , is not a value in $\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}$ .

Table 6

A function that is not a context

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{familyName}\mathrm{,}\text{“}\mathit{surname}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\}$

4.5. Application of a PRSC context on a PG

We now define formally the conversion operated by PRSC. A PRSC conversion of a PG depends on a chosen context $\mathit{ctx}\in \mathit{Ctx}$ .

Definition 20 (Property value conversion).

For the conversion of property values to literals, we consider that we have a fixed total injective function $\mathit{toLiteral}:\mathit{V}\to \mathit{L}$ , common for all PGs and contexts. We suppose that $\mathit{toLiteral}$ is reversible, i.e. we are able to compute ${\mathit{toLiteral}}^{-1}$ .

Definition 21 (The $\mathit{prsc}$ function).

The operation that produces an RDF graph from the application of a PRSC context $\mathit{ctx}\in {\mathit{Ctx}}_{\mathit{pg}}$ on a property graph $\mathit{pg}\in \mathit{BPGs}$ is noted $\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ . The result of the $\mathit{prsc}$ function is the union of the RDF graph built by converting all elements of the PG, into RDF. The conversion of a single element is materialized by the $\mathit{build}$ function.

$\forall \mathit{tps}\subseteq \mathit{Templates}$ , $\forall \mathit{pg}\in \mathit{BPGs}$ , $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $\mathit{build}\mathrm{(}\mathit{tps}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}=\{{\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}\mathrm{(}\mathit{tp}\mathrm{)}|\mathit{tp}\in \mathit{tps}\}$ with ${\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}$ defined as follows: $$\begin{array}{rl}& {\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}:\left\{\begin{array}{ll}\mathit{Templates}& \to \mathit{RdfTriples}\\ \mathit{P}\cup \mathit{L}& \to \mathit{L}\\ \mathit{I}& \to \mathit{I}\\ \mathit{pvars}& \to \mathit{B}\end{array}\right.\\ & {\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}\mathrm{(}{\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}\mathrm{(}{\mathit{x}}_{\mathit{s}}\mathrm{)}\mathrm{,}{\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}\mathrm{(}{\mathit{x}}_{\mathit{p}}\mathrm{)}\mathrm{,}{\mathit{\beta }}_{\mathit{pg}\mathrm{,}\mathit{m}}\mathrm{(}{\mathit{x}}_{\mathit{o}}\mathrm{)}\mathrm{)}& \text{if }\mathit{x}=\mathrm{(}{\mathit{x}}_{\mathit{s}}\mathrm{,}{\mathit{x}}_{\mathit{p}}\mathrm{,}{\mathit{x}}_{\mathit{o}}\mathrm{)}\in \mathit{Templates}\\ \mathit{x}& \text{if }\mathit{x}\in \mathit{L}\cup \mathit{I}\\ \mathit{m}& \text{if }\mathit{x}=?\mathit{self}\\ \mathit{sr}{c}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}& \text{if }\mathit{x}=?\mathit{source}\wedge \mathit{m}\in {\mathit{E}}_{\mathit{pg}}\\ \mathit{des}{t}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}& \text{if }\mathit{x}=?\mathit{destination}\wedge \mathit{m}\in {\mathit{E}}_{\mathit{pg}}\\ \mathit{toLiteral}\mathrm{(}{\mathit{properties}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}\mathrm{)}& \text{if }\mathit{x}=\mathrm{(}\mathit{key}\mathrm{,}\mathit{valueOf}\mathrm{)}\in \mathit{P}\\ \text{undefined}& \text{otherwise}\end{array}\right.\end{array}$$

As said previously, the result of $\mathit{prsc}$ is the union of the graphs produced by $\mathit{build}$ , i.e. $$\begin{array}{r}\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}={\displaystyle \bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}\end{array}$$

Example 15.

Table 7 exposes the resolution of $\mathit{prsc}$ on the running example.

Table 7

Application of a PRSC context on the running example

m	$\mathit{typeo}{f}_{\mathit{BTT}}\mathrm{(}\mathit{m}\mathrm{)}$	$\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{BTT}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$	$\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{BTT}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{BTT}\mathrm{,}\mathit{m}\mathrm{)}$
$\text{\_}:\mathit{n}\mathit{1}$	$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$	$\{\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$
		$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$	$\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}\text{”}\mathrm{)}\mathrm{,}$
		$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$	$\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{Reporter}\text{”}\mathrm{)}\}$
$\text{\_}:\mathit{n}\mathit{2}$	$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$	$\{\mathrm{(}\text{\_}:\mathit{n}\mathit{2}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Snowy}\text{”}\mathrm{)}\}$
$\text{\_}:\mathit{e}\mathit{1}$	$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\}$	$\{\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}\text{\_}:\mathit{n}\mathit{2}\mathrm{)}\}$

The resolution of $\text{\_}:\mathit{n}\mathit{2}$ is as follows: $$\begin{array}{rlr}& \mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{BTT}}\mathrm{(}\text{\_}:\mathit{n}\mathit{2}\mathrm{)}\mathrm{,}\mathit{BTT}\mathrm{,}\text{\_}:\mathit{n}\mathit{2}\mathrm{)}& \\ & =\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{BTT}\mathrm{,}\text{\_}:\mathit{n}\mathit{2}\mathrm{)}& \text{Resolution of the type}\\ & =\mathit{build}\mathrm{\left(}\right\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{prec}:\mathit{valueOf}}\mathrm{)}\}\mathrm{,}\mathit{BTT}\mathrm{,}\text{\_}:\mathit{n}\mathit{2}\mathrm{)}& \text{Application of }\mathit{ctx}\\ & =\left\{\mathrm{\right(}\text{\_}:\mathit{n}\mathit{2}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\mathit{toLiteral}\mathrm{(}{\mathit{properties}}_{\mathit{BTT}}\mathrm{(}\text{\_}:{\mathit{n}}_2\mathrm{,}\text{“}\mathit{name}\text{”}\mathrm{)}\mathrm{)}\mathrm{\left)}\right\}& \text{Application of }\mathit{build}\\ & =\left\{\mathrm{\right(}\text{\_}:\mathit{n}\mathit{2}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\mathit{toLiteral}\mathrm{(}\text{“}\mathit{Snowy}\text{”}\mathrm{)}\mathrm{\left)}\right\}& \text{Evaluation of the property “name”}\\ & =\left\{\mathrm{\right(}\text{\_}:\mathit{n}\mathit{2}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Snowy}{\text{”}}^{\mathit{xsd}:\mathit{string}}\mathrm{\left)}\right\}& \text{Application of }\mathit{toLiteral}\end{array}$$

Algorithm 1 gives an algorithmic view of the $\mathit{prsc}$ function presented by Definition 21.

Algorithm 1:

The $\mathit{prsc}$ function

4.6. Complexity analysis

In this section, we discuss the different metrics that can be used to evaluate the complexity and evaluate the complexity of the $\mathit{prsc}$ function.

4.6.1. Functions considered constant

For a given PG $\mathit{pg}$ , the complexity of the functions $\mathit{sr}{c}_{\mathit{pg}}$ , $\mathit{des}{t}_{\mathit{pg}}$ , ${\mathit{labels}}_{\mathit{pg}}$ and ${\mathit{properties}}_{\mathit{pg}}$ are considered constant.

The complexity of the functions $\mathit{key}{s}_{\mathit{pg}}$ , the $\mathit{toLiteral}$ and the ${\mathit{toLiteral}}^{-1}$ is also considered constant.

Evaluating if something is a member of a given set, for example if an entity is part of the set ${\mathit{N}}_{\mathit{pg}}$ , is generally considered to be constant time thanks to hash maps.8

⁸

Inserting and searching in a hash map is not strictly speaking a constant time operation but has an amortized constant complexity, and is linear in the worst case.

4.6.2. Considered metrics

For a given PG $\mathit{pg}$ and a given context $\mathit{ctx}$ , the following metrics are considered:

• The number of nodes and edges in $\mathit{pg}$ , denoted $\mathit{NbOfPGElements}$ . $$\begin{array}{c}\mathit{NbOfPGElements}=|{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}|\end{array}$$

• The size of the biggest template graph, denoted $\mathit{BiggestTemplateSize}$ . $$\begin{array}{c}\mathit{BiggestTemplateSize}=\underset{\mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}}{max}\mathrm{\left(}\right|\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}\left|\mathrm{\right)}\end{array}$$

• The complexity of the types in the context, denoted $\mathit{TypeComplexity}$ , reflected by the number of labels and the number of properties of the type with the highest number of labels and properties. Note that since the context has to be valid, i.e. all elements of the PG must have their type in the context, $\mathit{TypeComplexity}$ is also an upper bound of the type complexity of the types in the PG. $$\begin{array}{c}\mathit{TypeComplexity}=1+\underset{\mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}}{max}\mathrm{\left(}\right|{\mathit{labels}}_{\mathit{pg}}\mathrm{(}\mathit{type}\mathrm{)}|+|{\mathit{keys}}_{\mathit{pg}}\mathrm{(}\mathit{type}\mathrm{)}\left|\mathrm{\right)}\end{array}$$

• The number of types supported by the context $\mathit{NbTypes}=|\mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}|$ .

In RDF-star, quoted triples can be used as subject or object of other triples, without limit on how deeply triples can be nested. In practice, however, it is rare to have more than one level of nesting. Usually, users are expected to use atomic RDF triples like _:tintin :travelsWith _:haddock or to use RDF-star triples with a depth of one like << _:tintin :travelsWith _:haddock >> :since 1978. We therefore consider the depth of any triple to be bound by a constant. As a consequence, in all functions processing terms and triples recursively (such as β in Algorithm 1), we can ignore the recursion depth in the complexity analysis.

In all complexity analyses, all metrics are considered non null. Indeed, if there are no elements or if the biggest template graph is empty, the produced RDF graph will be empty so this case is not interesting. As we add one to the number of labels and properties, the type complexity can never be zero, even if the context only supports nodes and edges with no labels and no properties.

4.6.3. Complexity of $\mathit{ctx}$ calls in the $\mathit{prsc}$ function

For each given PG element m, the complexity of a call to $\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ is $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}$ :

The type of m in the PG $\mathit{pg}$ must be computed. $\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ has a complexity of $\mathcal{O}\mathrm{(}1\mathrm{)}$ :

• Evaluating if m is a node or an edge is constant as checking if an element is a member of a set is constant.

• Calls to ${\mathit{labels}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ and $\mathit{key}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ are considered constants in Section 4.6.1.

In the complexity analysis, we consider that $\mathit{ctx}$ is implemented as a hash map from the types to the template graphs. A $\mathit{ctx}$ call would first need to compute the hash of the type. To do so, it has to look at all the labels and properties in the type in a deterministic order; for this, the labels and keys needs to be sorted, which has a complexity of $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}$ . After the hash has been computed, the cost of retrieving the template graph has an amortized constant complexity. The overall complexity of a $\mathit{ctx}$ call is $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}$ .

4.6.4. Complexity of $\mathit{prsc}$

Given a PG $\mathit{pg}\in \mathit{BPGs}$ and a context $\mathit{ctx}\in \mathit{Ct}{x}_{\mathit{pg}}$ ,

• Calls to $\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ in line 4 have a complexity of $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}$ .

• Calls to the β function in line 7 are constant, as it has been assumed that the depth of the most nested triple is low enough to be ignored and the operations it performs are in constant time.

• There are two for loops, one iterating on all PG elements ( $\mathit{NbOfPGElements}$ ) and one iterating on all template triples of a template graph ( $\mathit{BiggestTemplateSize}$ ). All instructions in the $\mathit{prsc}$ but the one on line 4 are computed in constant time. Line 4 is inside the first loop but outside the second loop.

The $\mathit{prsc}$ function has an $\mathcal{O}\mathrm{(}\mathit{NbOfPGElements}\ast \mathrm{(}\mathit{BiggestTemplateSize}+\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}\mathrm{)}$ complexity.

5. PRSC reversibility

When PGs are converted into RDF graphs, an often desired property is to not have any information loss. To determine whenever or not a conversion induces information loss is to check if the conversion is reversible, i.e. if from the output, it is possible to compute back the input. The reversion is studied relatively to the used PRSC contexts: the PRSC context is used as both an input of both the PRSC algorithm and the reversion algorithm. In other words, we consider that the information stored in the PRSC context do not need to be stored in the produced RDF graph to produce a reversible conversion.

This section first shows that not all PRSC contexts are reversible. Then, properties are exhibited about PRSC contexts, leading to a description of a subset of reversible PRSC contexts, i.e. contexts that we prove do not induce information loss.

5.1. Reversibility in this paper

In this paper, we call a function f reversible if we can find back x in practice from $\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}$ . This implies that:

• The function f must be injective. Indeed, if two different values x and ${\mathit{x}}^{\prime }$ can produce the same value y, it is impossible to know if the value responsible for producing y was x or ${\mathit{x}}^{\prime }$ .

• The inverse function ${\mathit{f}}^{-1}$ must be computable and tractable in reasonable time. By counter-example, a public-key encryption function is supposed to be injective. It is theoretically possible, although prohibitively costly, to decipher a given message by applying the encryption function on all possible inputs until the result is the original encrypted message. This is not the kind of “reversibility” we are interested in.

We say that a context $\mathit{ctx}$ is reversible if for any PG $\mathit{pg}\in \mathit{BPGs}$ such that the context $\mathit{ctx}$ is complete for the PG $\mathit{pg}$ , it is possible to find back $\mathit{pg}$ from the context $\mathit{ctx}$ and the result of $\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ .

More formally, when studying reversibility, we want to check if for a given $\mathit{ctx}\in \mathit{Ctx}$ , we are able to define a tractable function ${\mathit{prs}{c}_{\mathit{ctx}}}^{-1}$ such that $\forall \mathit{pg}\in \mathit{BPGs}$ , $[\mathit{ctx}\in \mathit{Ct}{x}_{\mathit{pg}}\Rightarrow {\mathit{prsc}}_{\mathit{ctx}}^{-1}\mathrm{(}\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}\mathrm{)}=\mathit{pg}]$ .

Example 16 (A trivially non-reversible context).

Consider the context ${\mathit{ctx}}_{\varnothing }$ such that for all types, it returns the empty template graph, i.e. $\forall \mathit{type}\in \mathit{Types}$ , ${\mathit{ctx}}_{\varnothing }\mathrm{(}\mathit{type}\mathrm{)}=\varnothing$ . As it is complete for all property graphs, it is possible to use this context on any property graph. However, applying the context ${\mathit{ctx}}_{\varnothing }$ produces the empty RDF graph. Therefore, the use of the context ${\mathit{ctx}}_{\varnothing }$ makes the function $\mathit{prsc}$ not injective, and therefore not reversible.

Example 17 (A more realistic example of a non-reversible context).

Another example of a non-reversible context is the context exposed in Table 4: while this context can be applied on PGs in which edges have the “since” property, the value of this property will never appear in the produced RDF graph.

As not all contexts are reversible, the next sections focus on characterizing some contexts that produce reversible conversions.

5.2. Well-behaved contexts

5.2.1. Characterization function

To be able to reverse back to the original PG, we need a way to distinguish the triples that may have been produced by a given member of $\mathit{Templates}$ from the ones that cannot have been produced by it. For this purpose, this section introduces the κ function. This function must verify that, for every triple template $\mathit{tp}$ and every triple t, $\mathit{\kappa }\mathrm{(}\mathit{t}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$ if and only if t can be produced from $\mathit{tp}$ by the β function. It would then follow that two template triples that may produce the same triple have the same image through κ.

Definition 22 (Characterization function).

The κ function maps:

All template triples to a super set of triples that it is able to generate.

All RDF triples t to a super-set of the RDF triples that a template triple that may generate the triple t may also generate. For example, a literal may be generated by any element of P. An element of P may generate any literal. Therefore, the κ function maps all literals to the set of all literals.

$$\begin{array}{rl}& \mathit{\kappa }:\left\{\begin{array}{ll}\mathit{Templates}\cup \mathit{RdfTriples}& \to 2^{\mathit{RdfTriples}}\\ \mathit{L}\cup \mathit{P}& \to \{\mathit{L}\}\\ \mathit{I}& \to 2^{\mathit{I}}\\ \mathit{B}\cup \mathit{pvars}& \to \{\mathit{B}\}\end{array}\right.\\ & \mathit{\kappa }\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}\mathit{\kappa }\mathrm{(}\mathit{s}\mathrm{)}\times \mathit{\kappa }\mathrm{(}\mathit{p}\mathrm{)}\times \mathit{\kappa }\mathrm{(}\mathit{o}\mathrm{)}& \text{if }\mathit{x}=\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\in \mathit{RdfTriples}\cup \mathit{Templates}\\ \mathit{L}& \text{if }\mathit{x}\in \mathit{L}\cup \mathit{P}\\ \{\mathit{x}\}& \text{if }\mathit{x}\in \mathit{I}\\ \mathit{B}& \text{if }\mathit{x}\in \mathit{B}\cup \mathit{pvars}\end{array}\right.\end{array}$$

The κ function is extended to all template graphs and RDF graphs $\mathit{xs}$ as $\mathit{\kappa }\mathrm{(}\mathit{xs}\mathrm{)}={\bigcup }_{\mathit{t}\in \mathit{xs}}\mathit{\kappa }\mathrm{(}\mathit{t}\mathrm{)}$ .

Example 18 (κ applied to the running example from Fig. 1).

$\mathit{\kappa }\mathrm{(}?\mathit{source}\mathrm{)}=\mathit{B}$ , $\mathit{\kappa }\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{)}=\mathit{B}$ .

$\mathit{\kappa }\mathrm{(}\mathit{foaf}:\mathit{name}\mathrm{)}=\{\mathit{foaf}:\mathit{name}\}$ .

$\mathit{\kappa }\mathrm{(}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}=\mathit{L}$ , $\mathit{\kappa }\mathrm{(}\text{“}\mathit{Tintin}\text{”}\mathrm{)}=\mathit{L}$ .

$\mathit{\kappa }\mathrm{(}\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{)}=\mathit{B}\times \{\mathit{foaf}:\mathit{name}\}\times \mathit{L}$ .

$\mathit{\kappa }\mathrm{(}\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}\text{”}\mathrm{)}\mathrm{)}=\mathit{B}\times \{\mathit{foaf}:\mathit{name}\}\times \mathit{L}$ .

Note that

• $\mathit{\kappa }\mathrm{(}\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}\text{”}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{)}$

• $\mathrm{(}\text{\_}:\mathit{n}\mathit{1}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{Tintin}\text{”}\mathrm{)}\in \mathit{\kappa }\mathrm{(}\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{)}$

$\mathit{\kappa }\mathrm{(}\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\mathrm{)}=\mathit{B}\times \{\mathit{ex}:\mathit{isTeammateOf}\}\times \mathit{B}$

$\mathit{\kappa }\mathrm{(}\mathrm{(}\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\mathrm{,}\mathit{ex}:\mathit{since}\mathrm{,}\text{“}\mathit{since}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{)}=\mathrm{(}\mathit{B}\times \{\mathit{ex}:\mathit{isTeammateOf}\}\times \mathit{B}\mathrm{)}\times \{\mathit{ex}:\mathit{since}\}\times \mathit{L}$

Table 8 provides an example of applying κ on the running example context of Table 4.

Table 8

The running example context with the corresponding values through κ

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$	$\mathit{\kappa }\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}$
$\mathit{tn}\mathit{1}=\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$	$\mathrm{(}\mathit{B}\times \{\mathit{rdf}:\mathit{type}\}\times \{\mathit{ex}:\mathit{Person}\}\mathrm{)}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$	$\bigcup \mathrm{(}\mathit{B}\times \{\mathit{foaf}:\mathit{name}\}\times \mathit{L}\mathrm{)}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$	$\bigcup \mathrm{(}\mathit{B}\times \{\mathit{ex}:\mathit{profession}\}\times \mathit{L}\mathrm{)}$
$\mathit{tn}2=\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$	$\mathrm{(}\mathit{B}\times \{\mathit{foaf}:\mathit{name}\}\times \mathit{L}\mathrm{)}$
$\mathit{te}1=\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{source}\mathrm{,}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\}$	$\mathrm{(}\mathit{B}\times \{:\mathit{isTeammateOf}\}\times \mathit{B}\mathrm{)}$

Remark 4 (κ on terms and triples is, as expected, a super-set of the possible generated values).

When comparing the definition of the κ function with the β functions defined in Section 4.5, it appears that:

For elements in B, $\mathit{pvars}$ , L and P, the image of κ is equal to the corresponding image set of the β function.

For elements in I, the image of κ is equal to a singleton containing that element; β maps any IRI to itself.

If the given term is a triple, the image of κ is the cross product of the application of the κ function to the terms that compose the RDF triple. As β on triples recursively applies itself to the three terms in the triple, we can see that $\forall \mathit{\beta }\mathrm{,}\forall \mathit{triple}\mathrm{,}\mathit{\beta }\mathrm{(}\mathit{triple}\mathrm{)}\in \mathit{\kappa }\mathrm{(}\mathit{triple}\mathrm{)}$ .

Therefore, if x is a term or an RDF triple, for any β function, $\mathit{\beta }\mathrm{(}\mathit{x}\mathrm{)}\in \mathit{\kappa }\mathrm{(}\mathit{x}\mathrm{)}$ .

Remark 5 (The result of $\mathit{build}$ is, as expected, a subset of the result of κ).

The $\mathit{build}$ function, from which $\mathit{prsc}$ is defined, uses β on each template triple. After β is applied, the union of the singletons containing each triple is computed. This is similar to the definition of κ on a set of triples.

From Remark 4, it can be deduced that if $\mathit{tps}$ is a set of template triples, $\forall \mathit{pg}\mathrm{,}\forall \mathit{m}\mathrm{,}\mathit{build}\mathrm{(}\mathit{tps}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}\subseteq \mathit{\kappa }\mathrm{(}\mathit{tps}\mathrm{)}$ .

Remark 6 (A template and its produced values share the same image through κ).

When using the κ function, elements in B and $\mathit{pvars}$ both map to B, and elements in L and P both map to L. Elements in I are wrapped into a singleton and both $\mathit{RdfTriples}$ and $\mathit{Templates}$ apply the function recursively on their members.

When using the β function:

Elements in $\mathit{pvars}$ map for all PGs $\mathit{pg}\in \mathit{BPGs}$ to elements of ${\mathit{N}}_{\mathit{pg}}$ and ${\mathit{E}}_{\mathit{pg}}$ , which are both subsets of B.

Elements in P map to elements in $Img\mathrm{(}\mathit{toLiteral}\mathrm{)}$ , which is a subset of L.

Elements in L and I are mapped to themselves.

Elements in $\mathit{Templates}$ apply the β function recursively on their members.

Therefore, $\forall \mathit{tp}\in \mathit{Templates}$ , $\mathit{\kappa }\mathrm{(}\mathit{\beta }\mathrm{(}\mathit{tp}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$

As mentioned previously, the role of κ is to allow us to determine whether two template triples with placeholders may produce the same triple. It maps all placeholders to a super-set 9 of all elements they can generate with the $\mathit{build}$ function. All RDF Triples are mapped by the κ function to a subset of $\mathit{RdfTriples}$ they are a member of.

⁹

Note that as κ maps to a super set, it may catch false positives. For example, P can only generate elements in $\mathit{Img}\mathrm{(}\mathit{toLiteral}\mathrm{)}$ , but the κ function considers that all elements of L can be generated from P. For the scope of this paper, κ catching false positives is considered acceptable, as we are only trying to prove the reversibility of a given class of contexts, rather than to characterize the whole class of reversible contexts.

Lemma 1.

If a triple is generated by a template graph, then there exists a template triple with the same image through κ.

$\forall \mathit{pg}\in \mathit{BPGs}\mathrm{,}\forall \mathit{m}\in \mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}\mathrm{,}\forall \mathit{tps}\subseteq \mathit{Templates}\mathrm{,}\forall \mathit{td}\in \mathit{build}\mathrm{(}\mathit{tps}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}\mathrm{,}\exists \mathit{tp}\in \mathit{tps}|\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$

Proof.

Per the Definition 21 of $\mathit{build}$ , a triple can only be generated by a template graph by the application of β to one of its template triples. Per Remark 6, the generated triple and the corresponding template triple have the same image though κ.  □

Definition 23 ( $\mathit{unique}$ template triple).

A template triple $\mathit{tp}$ is $\mathit{unique}$ in a set of template triples if no other template triple in the set has the same image through κ equal to $\mathit{tp}$ .

It is defined as follows with $\mathit{tp}\in \mathit{tps}\subset \mathit{Templates}$ : $$\begin{array}{r}\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}=\mathrm{(}\forall \mathit{t}{p}^{\prime }\in \mathit{tps}\mathrm{,}\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{t}{p}^{\prime }\mathrm{)}\iff \mathit{tp}=\mathit{t}{p}^{\prime }\mathrm{)}\end{array}$$

Combined with Remark 6, what $\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}$ tells us is that any triple, with the same image through κ as $\mathit{tp}$ , can not have be generated by any other element of $\mathit{tps}$ than $\mathit{tp}$ itself. This leads us to Theorem 1 below.

Theorem 1 (Triples produced by a $\mathit{unique}$ template triple).

In the result of the $\mathit{build}$ function, if a data triple and a unique template triple have the same value through κ, then the data triple must have been produced by this template triple.

$\forall \mathit{pg}\in \mathit{BPGs}$ , $\forall \mathit{ctx}\in {\mathit{Ctx}}_{\mathit{pg}}$ , $\forall \mathit{m}\in \mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}$ , let $\mathit{tps}=\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ , $\forall \mathit{td}\in \mathit{build}\mathrm{(}\mathit{tps}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ , $\forall \mathit{tp}\in \mathit{tps}$ : $$\begin{array}{c}\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}\wedge \mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}\Rightarrow \mathit{td}\in \mathit{build}\mathrm{(}\{\mathit{tp}\}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}\end{array}$$

Proof.

We prove the theorem by contradiction.

Let us suppose that:

(A) $\mathit{td}\in \mathit{build}\mathrm{(}\mathit{tps}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}$

(B1) $\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}$ , i.e. $\mathrm{(}\forall \mathit{t}{p}^{\prime }\in \mathit{tps}\mathrm{,}\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{t}{p}^{\prime }\mathrm{)}\Rightarrow \mathit{tp}=\mathit{t}{p}^{\prime }\mathrm{)}$

(B2) $\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$

(C) $\mathit{td}\notin \mathit{build}\mathrm{(}\{\mathit{tp}\}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}$

$$\begin{array}{rlr}\mathit{td}& \in \mathit{build}\mathrm{(}\mathit{tps}-\{\mathit{tp}\}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}& \text{[(A) and (C)]}\\ & \Rightarrow \exists \mathit{tdp}\in \mathit{tps}-\{\mathit{tp}\}\mathrm{,}\mathit{\kappa }\mathrm{(}\mathit{tdp}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}& \text{[Lemma 1]}\\ & \Rightarrow \exists \mathit{tdp}\in \mathit{tps}-\{\mathit{tp}\}\mathrm{,}\mathit{\kappa }\mathrm{(}\mathit{tdp}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}& \text{[(B2)]}\\ & \Rightarrow \exists \mathit{tdp}\in \mathit{tps}-\{\mathit{tp}\}\mathrm{,}\mathit{tdp}=\mathit{tp}& \text{[(B1)]}\\ & \Rightarrow \mathit{tp}\in \mathit{tps}-\{\mathit{tp}\}& \end{array}$$

$\mathit{tp}$ can not be a member of the set $\mathit{tps}-\{\mathit{tp}\}$ , as it explicitly exclude it. As we reached a contradiction, it means that $\mathit{td}\in \mathit{build}\mathrm{(}\{\mathit{tp}\}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}$ .  □

Theorem 1 allows us to link an RDF triple to the unique template triple that produced it. Then by comparing the terms of the RDF triple to the corresponding placeholders in the template triple, we will be able to reconstruct the original PG.

5.2.2. Well-behaved PRSC context

In this section, we define a subset of contexts that we call well-behaved PRSC contexts. In the next section, we will prove that these contexts are reversible.

Definition 24 (Well-behaved contexts).

A PRSC context $\mathit{ctx}$ is well-behaved if it conforms to those 3 criteria:

$\forall \mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}$ , $\text{ let }\mathit{tps}=\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$

Element provenance: all generated triples must contain the blank node that identifies the node or the edge it comes from. This is achieved by using the $?\mathit{self}$ placeholder in all template triples:

• $\forall \mathit{tp}\in \mathit{tps}$ , $?\mathit{self}\in \mathit{tp}$

Signature template triple: $\mathit{tps}$ contains at least one template triple, called its signature and noted $\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}$ , that will produce triples that no other template in $\mathit{ctx}$ can produce. This will allow, for each blank node in the produced RDF graph, to identify its type in the original PG.

• $\exists \mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\in \mathit{tps}$ , $\forall \mathit{x}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}$ , $\mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}\subseteq \mathit{\kappa }\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}\Rightarrow \mathit{x}=\mathit{type}$

No value loss: for all elements in the PG, we do not want to lose information stored in properties, nor for edges, the source and destination node. Each of these pieces of information must be present in an unambiguously recognizable triple pattern.

• $\forall \mathit{key}\in \mathit{keys}\mathrm{(}\mathit{type}\mathrm{)}$ , $\exists \mathit{tp}\in \mathit{tps}|\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}\wedge \mathrm{(}\mathit{key}\mathrm{,}\mathit{valueOf}\mathrm{)}\in \mathit{tp}$

• $\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{edge}\text{”}\iff \exists \mathit{tp}\in \mathit{tps}|\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}\wedge ?\mathit{source}\in \mathit{tp}$

• $\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{edge}\text{”}\iff \exists \mathit{tp}\in \mathit{tps}|\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}\wedge ?\mathit{destination}\in \mathit{tp}$

The set of all well-behaved contexts is ${\mathit{Ctx}}^{+}$ , and the set of all well-behaved contexts for a PG $\mathit{pg}$ is ${\mathit{Ctx}}_{\mathit{pg}}^{+}$ . ${\mathit{Ctx}}^{+}\subset \mathit{Ctx}$ and ${\mathit{Ctx}}_{\mathit{pg}}^{+}={\mathit{Ctx}}^{+}\cap {\mathit{Ctx}}_{\mathit{pg}}$ .

Remark 7 (Handling multiple $\mathit{sig}{n}_{\mathit{ctx}}$ candidates).

In the case where there are multiple template triples candidates to become the signature template triple, the choice of the signature template triple among the candidates is generally not important.

To make the choice deterministic, it could be considered that the chosen signature template triple is the first in lexicographic order. In the case of the presented algorithms, the choice of the signature template triple is not important, and will lead to the same output.

Remark 8 (The template graphs used in well-behaved contexts are not empty).

A well-behaved context cannot map a type to an empty template graph: the signature template triple criterion ensures that every template graph contains at least one template triple: $\forall \mathit{tps}\in \mathit{Img}\mathrm{(}\mathit{ctx}\mathrm{)}$ , $\exists \mathit{tp}\in \mathit{tps}\iff |\mathit{tps}|⩾1$ .

Remark 9 (Inside a well-behaved context, all template graphs are different from all others).

For any well-behaved context $\mathit{ctx}$ , two types cannot share the same template graph. Indeed, if two types share the same template graph, i.e. there are two types $\mathit{type}\mathit{1}$ and $\mathit{type}\mathit{2}$ with $\mathit{type}\mathit{1}\ne \mathit{type}\mathit{2}$ such that $\mathit{ctx}\mathrm{(}\mathit{type}\mathit{1}\mathrm{)}=\mathit{ctx}\mathrm{(}\mathit{type}\mathit{2}\mathrm{)}$ , it would contradict the signature template triple criterion as it would lead to $\mathit{type}\mathit{1}=\mathit{type}\mathit{2}$ .

Example 19.

Table 8 studies the context used in our running example, exposed in Example 12.

The type $\mathit{tn}\mathit{1}$ matches all criteria of a well-behaved PRSC context:

• All triples contain $?\mathit{self}$ .

• At least one template triple is a signature: the image through κ of $\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}$ is not contained in the image through κ of other types. It is also the case of $\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}$ .

• The properties $\text{“}\mathit{name}\text{”}$ and $\text{“}\mathit{job}\text{”}$ have a unique template triple inside $\mathit{\kappa }\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{tn}\mathit{1}\mathrm{)}\mathrm{)}$ .

The type $\mathit{tn}\mathit{2}$ violates the signature template triple criterion as $\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}$ , its only template triple, is shared with the type $\mathit{tn}1$ ,

The type $\mathit{te}\mathit{1}$ violates the element provenance criterion as $?\mathit{self}$ is missing. It also violates the no value loss criterion as the term $\text{“}\mathit{since}{\text{”}}^{\mathit{valueOf}}$ is missing from any template triple.

For all these reasons, this context is not well-behaved.

Example 20 (A well-behaved context for the running example).

Let $\mathit{ct}{x}_{\mathrm{TTWB}}$ be the function described in Table 9. In this new context, an arbitrary $\mathit{ex}:\mathit{NamedEntity}$ IRI is used to sign the PG nodes that have no labels and only a name, and a classic RDF reification is used to model the PG edges.

This context is well-behaved:

Table 9

An example of a complete and well-behaved context for the Tintin Property Graph

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{\star }\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{\star }\}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{NamedEntity}\mathrm{)}\mathrm{\star }\}$
$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{subject}\mathrm{,}?\mathit{source}\mathrm{)}\mathrm{\star }\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{object}\mathrm{,}?\mathit{destination}\mathrm{)}\mathrm{\star }\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{predicate}\mathrm{,}\mathit{ex}:\mathit{TravelsWith}\mathrm{)}\mathrm{\star }\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{since}\mathrm{,}\text{“}\mathit{since}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{\star }\}$

• $?\mathit{self}$ appears in all triples,

• Template triples that are signature are marked with a ⋆. At least one signature triple appears for each type,

• All property keys have a unique template triple.

Listing 3.

The RDF graph produced by the application of the well-behaved context $\mathit{ct}{x}_{\mathrm{TTWB}}$ on the running example PG $\mathit{BTT}$

Listing 3 is the RDF graph produced by the application of the context $\mathit{ct}{x}_{\mathrm{TTWB}}$ on the PG $\mathit{BTT}$ . Each part that starts with a # denotes the application of a $\mathit{build}$ application to the PG element described in the comment. The elements are ordered in the same order as their type in Table 9, and the RDF triples and the template triples that produced them are also in the same order.

Remark 10 (Relationship between the empty PG and the empty RDF graph with well-behaved PRSC context).

For all well-behaved PRSC contexts, the only PG that can produce the empty RDF graph is the empty PG: $$\begin{array}{c}\forall \mathit{pg}\in \mathit{BPGs}\mathrm{,}\mathit{ctx}\in {\mathit{Ctx}}_{\mathit{pg}}^{+}\mathrm{,}|\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}|=0\iff \mathit{pg}={\mathit{pg}}_{\varnothing }\end{array}$$

Indeed, Remark 8 ensures that the template graphs are non-empty. So any application of the $\mathit{build}$ function with any well-behaved context produces at least one RDF triple. As the produced RDF graph is the union of the graphs produced by the use of $\mathit{build}$ on each node and edge, the only way to have an empty result is to have no node nor edge in the property graph.

5.2.3. Complexity analysis and implementation

PRSC well-behaved contexts will be proved to be reversible in Section 5.3, meaning that producing an RDF graph from them will preserve all information stored in the PG. It is therefore important to be able to determine if in practice, it is possible to compute if a PRSC context is well-behaved.

Lemma 2.

The values through κ of two given terms are either disjoint or equal:

Proof.

Consider any atomic RDF term t:

If $\mathit{t}\in \mathit{I}$ , its value through κ is the singleton composed of the element t. Other terms can not map κ to a super-set of the singleton $\{\mathit{t}\}$ , in particular no term can be mapped to I.

If $\mathit{t}\in \mathit{L}\cup \mathit{P}$ , the value through κ is L. No other term can be mapped to a super-set or a subset of L.

If $\mathit{t}\in \mathit{B}\cup \mathit{pvars}$ , the value through κ is B. No other term can be mapped to a super-set of a subset of B.

As L, I and B are pairwise disjoint, for two given atomic RDF terms, the value through κ is either disjoint or equal.

For two given RDF triples composed of atomic terms, their value through κ are equals to the Cartesian product of the value through κ of the components. As the values through κ of their components are either equals or disjoints, the values through κ of the triples are also either equals or disjoints. By induction, this is true for any two RDF triples, even if their subject or object are also triples.  □

Remark 11 (Implementing κ and complexity analysis).

The function κ is defined to return sets, some of them being infinite sets. While this definition is useful to prove different theorems in this paper, it is not practical from an implementation perspective.

Let λ and δ be two distinct values that are not members of the set I. We propose below an alternative function ${\mathit{\kappa }}_{\mathit{impl}}$ to be used instead of κ in algorithms: $$\begin{array}{c}{\mathit{\kappa }}_{\mathit{impl}}\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}\{\mathit{\kappa }\mathrm{(}\mathit{triple}\mathrm{)}|\mathit{triple}\in \mathit{x}\}& \text{if }\mathit{x}\in \mathit{RdfTriples}\cup \mathit{Templates}\\ \mathrm{(}{\mathit{\kappa }}_{\mathit{impl}}\mathrm{(}\mathit{s}\mathrm{)}\mathrm{,}{\mathit{\kappa }}_{\mathit{impl}}\mathrm{(}\mathit{p}\mathrm{)}\mathrm{,}{\mathit{\kappa }}_{\mathit{impl}}\mathrm{(}\mathit{o}\mathrm{)}\mathrm{)}& \text{if }\mathit{x}=\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}\in \mathit{RdfTriples}\cup \mathit{Templates}\\ \mathit{\lambda }& \text{if }\mathit{x}\in \mathit{L}\cup \mathit{P}\\ \mathit{x}& \text{if }\mathit{x}\in \mathit{I}\\ \mathit{\delta }& \text{if }\mathit{x}\in \mathit{B}\cup \mathit{pvars}\end{array}\right.\end{array}$$

Compared to Definition 22, we replaced:

the singleton $\{\mathit{x}\}$ with x, in the case where $\mathit{x}\in \mathit{I}$ ,

the sets L and B with two constants λ and δ that are not elements of I,

the cross product with a simple triple of the values returned for each element of x when x is a triple.

The complexity of the ${\mathit{\kappa }}_{\mathit{impl}}\mathrm{(}\mathit{x}\mathrm{)}$ is:

For any x that is not a triple nor a graph, calls to this function can be done in constant time, by simply checking the type of x.

When x is a triple, calls to this function involves recursive calls up to the depth of x, which we consider to be bounded by a constant (see Section 4.6.2). So it is also done in constant time.

When x is a graph, calls to this function involves calling ${\mathit{\kappa }}_{\mathit{impl}}$ on each triple of the graph. As the call on a triple is constant, the call on the graph x has a linear complexity depending on the size of the graph.

Note that:

For two triples, checking if their value through ${\mathit{\kappa }}_{\mathit{impl}}$ are equals can be done in constant time.

Thanks to Lemma 2, checking if the value through ${\mathit{\kappa }}_{\mathit{impl}}$ of a triple t is included in the value through ${\mathit{\kappa }}_{\mathit{impl}}$ of a graph $\mathit{tps}$ can be done in linear time by iterating on each triple $\mathit{tp}$ of the graph $\mathit{tps}$ and comparing the values through ${\mathit{\kappa }}_{\mathit{impl}}$ of the triples t and $\mathit{tp}$ .

Remark 12 (Complexity of checking if a PRSC context is a well-behaved).

The first task to check if a context $\mathit{ctx}$ is well-behaved consists in computing the value through κ of all triples used in it. As the depth of a template triple is considered to be negligible, the complexity is the number of template triples, bounded to the number of types multiplied by the size of the biggest template graph: $\mathcal{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{BiggestTemplateSize}\mathrm{)}$ .

After the value through κ of all template triples have been computed, for each type, we need to check if the type complies with the three criterion exposed in the Definition 24.

The element provenance criterion consists in checking if $?\mathit{self}$ is in all templates triples of all type. This task has an $\mathcal{O}\mathrm{(}1\mathrm{)}$ complexity for each template triple and an overall $\mathit{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{BiggestTemplateSize}\mathrm{)}$ complexity for the whole context.

The signature template triple consists in checking if there is at least one signature template triple in the template graph of all types, i.e. checking if the value through κ of one of the template triples of each type is not contained in the set of the value through κ of the other types template graph. As hash sets make the membership check constant, this task has an $\mathcal{O}\mathrm{(}\mathit{NbTypes}\mathrm{)}$ complexity for a single template triple candidate, and an overall $\mathit{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{BiggestTemplateSize}\ast \mathit{NbTypes}\mathrm{)}$ for the whole context.

For a given type, checking the no value loss criterion consists in checking if a $\mathit{unique}$ template triple can be found in the template graph for each placeholder, i.e. a placeholder corresponding to each property keys in the type; and if the PG element is an edge, the $?\mathit{source}$ and $?\mathit{destination}$ placeholders must also be found. Thanks to hash sets, checking if a template triple is $\mathit{unique}$ inside its template graph is constant. Implementing the test by following the definition leads to an $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast \mathit{BiggestTemplateSize}\mathrm{)}$ complexity for each type and an $\mathcal{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{TypeComplexity}\ast \mathit{BiggestTemplateSize}\mathrm{)}$ complexity for the whole context.

The final complexity of checking if a context is a well-behaved PRSC context is: $$\begin{array}{c}\mathcal{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{BiggestTemplateSize}\ast \mathrm{(}\mathit{NbTypes}+\mathit{TypeComplexity}\mathrm{)}\mathrm{)}\end{array}$$

5.3. Reversion algorithm

Algorithm 2 aims to convert an RDF graph, that was produced from a PG and a known well-behaved context, into the original PG.

It is a four steps algorithm: 1) it finds the elements of the PG, by assuming they are the same as the blank node in the RDF graph, 2) it gives a type to all PG elements with the $\mathit{FindTypeOfElements}$ function in Algorithm 3,10

¹⁰

To help the comprehension of Algorithm 3, we recall that for a given set A, the mathematical notation $\exists !\mathit{a}\in \mathit{A}\mathrm{,}\mathit{somepredicate}\mathrm{(}\mathit{a}\mathrm{)}$ means that in the set A, there is one and only one element, denoted by a, that matches $\mathit{somepredicate}$ . By extension, $\exists !\mathit{a}\in \mathit{A}$ means that there is one and only one element in the set A that is denoted by a.

3) it assigns each triple to a single PG element, corresponding to the production of the $\mathit{build}$ function, with the $\mathit{AssociateTriplesWithElements}$ function in Algorithm 4, and 4) it looks for the source, destination and properties of all elements with the $\mathit{buildpg}$ function in Algorithm 5.

Algorithm 2:

The main algorithm to convert back an RDF graph into a PG by using a context

Algorithm 3:

Associate the elements of the future PG with their types

Algorithm 4:

Associate each triple to the element that has produced it

Algorithm 5:

Produce a PG from the previous analysis of the elements and triples

Further subsections prove that for all $\mathit{ctx}\in {\mathit{Ctx}}^{+}$ , for all PGs $\mathit{pg}$ , applying these algorithms to $\mathit{rdf}=\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ actually produces $\mathit{pg}$ , meaning that the reversion algorithm is a sound and complete implementation of ${\mathit{prsc}}^{-1}$ for well-behaved contexts. Applying this algorithm to an arbitrary RDF graph and/or an arbitrary context is out of the scope of this paper.

5.3.1. Finding the elements of the PG

The first step of the algorithm relies on the assumption that the blank nodes of the RDF graph and the elements of the original PG are the same.

Theorem 2 (Equality between the elements of a PG and the blank nodes of the RDF graph).

If the RDF graph $\mathit{rdf}$ has been produced from a PG $\mathit{pg}$ and a PRSC well-behaved context $\mathit{ctx}$ , then the set of all blank nodes of $\mathit{rdf}$ is the set of PG elements of $\mathit{pg}$ . $$\begin{array}{c}\forall \mathit{pg}\in \mathit{BPGs}\mathrm{,}\mathit{ctx}\in {\mathit{Ctx}}_{\mathit{pg}}^{+}\mathrm{,}\mathit{rdf}=\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}\mathrm{,}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}=\mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}\end{array}$$

Proof.

The $\mathit{build}$ function, described in Section 4.5, produces specific triples depending on the given template. The template graphs cannot contain blank nodes: the blank node produced by $\mathit{prsc}$ are forced to be the elements of the converted BPG. So $\mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}\subseteq {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ .

From Remark 8, we know that $\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ contains at least one triple pattern $\mathit{tp}$ . Combined with the element provenance criterion from Definition 24-1, we know that $?\mathit{self}\in \mathit{tp}$ . When β is applied to $\mathit{tp}$ , a triple that contains m is forced to appear, meaning that ${\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\subseteq \mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}$ .

 □

Theorem 2 proves the correctness of the $\mathit{Elements}\leftarrow \mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}$ step in Algorithm 2.

5.3.2. Finding the type related to each element

In this part of the proof, we show that the $\mathit{FindTypeOfElements}$ function from Algorithm 3 is correct, i.e. it is able to find back the right type of all elements m in the original $\mathit{pg}$ graph.

Lemma 3.

If a data triple shares the same value through κ as one of the signature triples of a type (Definition  24 -2), then the element from which the data triple was produced must be of this type: $$\begin{array}{rl}& \forall \mathit{td}\in \mathit{rdf}\mathrm{,}\forall \mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}\mathrm{,}\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{,}\\ & [\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}{\mathit{sign}}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}\wedge \mathit{td}\in \mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{\left)}\right]\Rightarrow \mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{type}\end{array}$$

Proof.

$\forall \mathit{td}\in \mathit{rdf}$ , $\forall \mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}$ , $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ $$\begin{array}{rlr}& \text{Assuming (A)}\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}& \\ & \mathit{td}\in \mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}& \\ & \Rightarrow \exists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}|\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}& \text{[Lemma 1]}\\ & \Rightarrow \exists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\left|\mathit{\kappa }\mathrm{\right(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}& \text{[A]}\\ & \Rightarrow \exists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\left|\mathit{\kappa }\mathrm{\right(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}\subseteq \mathit{\kappa }\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{)}& \left[\begin{array}{c}\mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\\ \text{and by construction of }\mathit{\kappa }\end{array}\right]\\ & \Rightarrow \mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{type}& \left[\begin{array}{c}\text{Signature template triple}\\ \text{in Definition 24-2}\end{array}\right]\end{array}$$  □

Definition 25 (Formalizing $\mathit{candtypes}$ ).

For a given blank node/PG element b, $\mathit{candtype}{s}_{\mathit{nodes}}$ and $\mathit{candtype}{s}_{\mathit{edges}}$ , introduced in Algorithm 3, can be formally defined as: $$\begin{array}{rl}& \mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}=\{\mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}|\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{node}\text{”}\\ & \phantom{\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}}\wedge \exists \mathit{td}\in \mathit{rdf}|\mathit{b}\in \mathit{td}\wedge \mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}\}\\ & \mathit{candtype}{s}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}=\{\mathit{type}\in \mathit{Dom}\mathrm{(}\mathit{ctx}\mathrm{)}|\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{edge}\text{”}\\ & \phantom{\mathit{candtype}{s}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}}\wedge \exists \mathit{td}\in \mathit{rdf}|\mathit{b}\in \mathit{td}\wedge \mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}\}\end{array}$$

They give the set of all node types and edge types, respectively, for which one of their signature triple could have produced a triple with b.

Theorem 3 ( $\mathit{candtypes}$ correctness).

Even though the $\mathit{candtypes}$ functions are defined by only used the used context and the produced RDF graph, they can be used to compute the type of any blank node in the original PG:

$\forall \mathit{b}\in {\mathit{N}}_{\mathit{pg}}$ , $\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}=\{\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\}$

$\forall \mathit{b}\in {\mathit{E}}_{\mathit{pg}}$ , $\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}=\varnothing$ and $\mathit{candtype}{s}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}=\{\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\}$ .

Table  10 provides an overview of the cardinality of the different $\mathit{candtypes}$ sets.

Table 10

A simple view of Theorem 3

	$|\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}|$	$|\mathit{candtype}{s}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}|$
$\mathit{b}\in {\mathit{N}}_{\mathit{pg}}$	1	any
$\mathit{b}\in {\mathit{E}}_{\mathit{pg}}$	0	1

Proof.

$\forall \mathit{b}\in \mathit{BNodes}\mathrm{(}\mathit{rdf}\mathrm{)}$ , $\forall \mathit{type}\in \mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$

Per Definition 25, $\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{node}\text{”}\wedge \exists \mathit{td}\in \mathit{rdf}|\mathit{b}\in \mathit{td}\wedge \mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}$ .

We are going to restrict the portion of the graph $\mathit{rdf}$ where such triples $\mathit{td}$ may be located: $$\begin{array}{rlr}\mathit{td}& \in \mathit{rdf}& \\ & \iff \mathit{td}\in {\displaystyle \bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}& [\text{Definition of }\mathit{rdf}\text{ / }\mathit{prsc}]\\ & \Rightarrow \mathit{td}\in {\displaystyle \bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}|\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{type}}\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}& \left[\begin{array}{c}\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{)}\\ \text{and Lemma 3}\end{array}\right]\\ & \Rightarrow \mathit{td}\in {\displaystyle \bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}|\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{type}}\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}& [\mathit{kind}\mathrm{(}\mathit{type}\mathrm{)}=\text{“}\mathit{node}\text{”}]\end{array}$$

We see that all triples $\mathit{td}$ contributing to $\mathit{candtyp}{e}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$ must have been produced by the signature triple template applied to a node from the PG. Also remember that $\mathit{td}$ must contain b.

If $\mathit{b}\in {\mathit{N}}_{\mathit{pg}}$ , then the signature triple of $\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}$ must have generated a $\mathit{td}$ containing b (since it must contain $?\mathit{self}$ , according to Definition 24-1), so $\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\in \mathit{candtyp}{e}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$ . Furthermore, no other node can produce a $\mathit{td}$ containing b ( $?\mathit{self}$ is the only blank node placeholder in node type templates), so $\mathit{candtyp}{e}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$ can not contain any other type. Therefore $\mathit{candtyp}{e}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}=\{\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\}$ .

If $\mathit{b}\in {\mathit{E}}_{\mathit{pg}}$ , it is impossible to produce the blank node b from any node $\mathit{m}\in {\mathit{N}}_{\mathit{pg}}$ (again, $?\mathit{self}$ is the only blank node placeholder in node type templates). No $\mathit{td}$ containing b can be found, so $\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$ is empty.

The reasoning for $\mathit{candtype}{s}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}$ when b is an edge is similar to the one for $\mathit{candtype}{s}_{\mathit{nodes}}\mathrm{(}\mathit{b}\mathrm{)}$ when b is a node: only b can produce triples containing itself, and it will, because having at least one signature triple with $?\mathit{self}$ is imposed by Definition 24. So $\mathit{candtyp}{e}_{\mathit{edges}}=\{\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\}$ .

Finally, a blank node $\mathit{b}\in {\mathit{N}}_{\mathit{pg}}$ can appear in any number of triples that share the same value through κ with an edge signature template triple: an edge signature template triple can contain $?\mathit{source}$ or $?\mathit{destination}$ , that can be mapped to any node depending on the PG. So $\mathit{candtyp}{e}_{\mathit{edges}}\mathrm{(}\mathit{b}\mathrm{)}$ can contain an arbitrary number of types in that case.  □

Remark 13.

Theorem 3 not only shows that the $\mathit{FindTypeOfElements}$ function in Algorithm 3 will always find the right $\mathit{typeo}{f}_{\mathit{pg}}$ function by using $\mathit{candtypes}$ , i.e. that it is computable from $\mathit{rdf}$ and $\mathit{ctx}$ , but Table 10 also explicitly shows that the Error(No type found) scenario can not appear if the RDF graph was produced from a PG, making the $\mathit{FindTypeOfElements}$ function both sound and complete.

Remark 14 (Using different signatures to determine the types).

As mentioned previously, the choice of the signature template triple $\mathit{sig}{n}_{\mathit{ctx}}\mathrm{(}\mathit{type}\mathrm{)}$ of a given type is not important for the reversion algorithm. Choosing one or another signature template triple only leads to other data triples being used to determine the type of the elements. However, the end result does not change.

5.3.3. Finding the generated triples for each PG element

For each PG element, given the produced RDF graph and the type of this PG element, we are able to compute the list of RDF triples produced from this PG element. In other words, Algorithm 4 correctly partitions the RDF graph into sub-graphs describing each element of the original PG.

Theorem 4.

In Algorithm  4 , assuming that the passed value of $\mathit{typeof}$ is equal to $\mathit{typeo}{f}_{\mathit{pg}}$ , $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}=\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}$ .

Proof.

As $\mathit{rdf}={\bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ , each triple $\mathit{td}\in \mathit{rdf}$ is a member of at least one $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ . For all triples $\mathit{td}\in \mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ , the element provenance criterion ensures that $\mathit{m}\in \mathit{td}$ . So the first step that consists in listing in the set $\mathit{bns}$ the blank nodes in $\mathit{td}$ , and consider that m is part of the set $\mathit{bns}$ is correct: the actual element m is in the set.

The algorithm associates each triple $\mathit{td}$ with a single $\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}$ :

Let’s first recall that blank nodes in $\mathit{rdf}$ can only be produced via the placeholders from $\mathit{pvars}$ : $?\mathit{self}$ , $?\mathit{source}$ , and $?\mathit{destination}$ . Let’s also recall that every triple pattern in the Well-behaved context $\mathit{ctx}$ must contain $?\mathit{self}$ (per the element provenance criterion).

If $\mathit{bns}$ contains only one blank node m, then m must come from $?\mathit{self}$ , and the corresponding triple pattern must then belong to $\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ . $\mathit{td}$ must then have been produced by $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ so putting it in $\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}$ is correct.

If $\mathit{bns}$ contains multiple blank nodes, $\mathit{td}$ must have been produced by a template triples with several placeholders from $\mathit{pvars}$ .

• Node template graphs can contain only one placeholder from $\mathit{pvars}$ : $?\mathit{self}$ . No $\mathit{m}\in {\mathit{N}}_{\mathit{pg}}$ could then have produced $\mathit{td}$ . It follows that $\mathit{td}$ must have been produced by the template graph of an edge.

• Edge template graphs can contain several placeholders from $\mathit{pvars}$ . But by definition of β, only $?\mathit{self}$ can be mapped to an edge (when $\mathit{m}\in {\mathit{E}}_{\mathit{pg}}$ ); $?\mathit{source}$ and $?\mathit{destination}$ are always mapped to nodes. Of the multiple blank nodes in $\mathit{bns}$ , exactly one of them, m, must therefore be an edge, and come from $?\mathit{self}$ . Following the same reasoning as above, when $\mathit{bns}$ contained only one blank node, we conclude that $\mathit{td}$ must then have been produced by $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ and that putting it in $\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}$ is correct.

Error(No element provenance) will never be raised if $\mathit{rdf}$ was produced by $\mathit{prsc}$ : each triple will contain at least one blank node generated from $?\mathit{self}$ (per the element provenance criterion), and if there are multiple blank nodes we showed that there must be only one edge blank node.

As each triple in $\mathit{rdf}$ is attributed in $\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}$ to the right element m that produced it from $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ , $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $\mathit{builtfrom}\mathrm{(}\mathit{m}\mathrm{)}=\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}$ .  □

5.3.4. Building the PG element

Projecting Property Graphs As an RDF graph is defined as a set of RDF triples, any subset of that set, as well as the union of two RDF graphs, are formally defined and are also RDF graphs. Algorithm 5 constructs back the original PG in an iterative manner. To prove its correctness, we need operators similar to ⊂ and ∪ for RDF graphs, but for our formalization of PGs.

In this section, the projection of a Property Graph is defined by focusing only on a single PG element, node or edge. The concept of merging PGs, which is the inverse of the projection, is also defined.

Let $\mathit{pg}$ be a PG.

Definition 26 (π projection of a Property Graph on an element).

The π projection of a PG on a node is equal to the PG with only the node itself. The π projection of a PG on an edge is the edge, and its source and destination nodes without the labels and properties of these nodes.

$\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , ${\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}$ is a PG such as:

If $\mathit{m}\in {\mathit{N}}_{\mathit{pg}}$ , ${\mathit{N}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\{\mathit{m}\}$ , ${\mathit{E}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\varnothing$ , ${\mathit{src}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}={\mathit{dest}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\varnothing \to \varnothing$

If $\mathit{m}\in {\mathit{E}}_{\mathit{pg}}$ , ${\mathit{N}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\{{\mathit{src}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{,}{\mathit{dest}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\}$ , ${\mathit{E}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\{\mathit{m}\}$ , ${\mathit{src}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\{\mathit{m}\mapsto {\mathit{src}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\}$ , ${\mathit{dest}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}=\{\mathit{m}\mapsto {\mathit{dest}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\}$

$\forall \mathit{x}\in {\mathit{N}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}\cup {\mathit{E}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}$ , $$\begin{array}{r}{\mathit{labels}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}\mathrm{(}\mathit{x}\mathrm{)}=\left\{\begin{array}{ll}{labels}_{\mathit{pg}}\mathrm{(}\mathit{x}\mathrm{)}& \text{if }\mathit{x}=\mathit{m}\\ \varnothing & \text{otherwise}\end{array}\right.\end{array}$$

$\forall \mathit{key}\in {\mathit{keys}}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ , ${\mathit{properties}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}=\mathit{propertie}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}$ , all other values are undefined.

Definition 27 (Property Graph merge operator ⊕).

The merge operator ⊕ is the inverse of the projection operator π. It can only be used on two PGs that are compatible, i.e. (1) a PG element defined as a node is not defined as an edge in the other, (2) an edge defined in both PGs have the same source and destination in both, and (3) if in both PGs, the value of a property key on the same PG element is defined, the values should be the same. The ⊕ operator builds a PG with the PG elements, labels and properties of both PGs.

We now define the ⊕ merge operator on property graphs. $\forall \mathrm{(}\mathit{p}{g}^{\prime }\mathrm{,}\mathit{p}{g}^{″}\mathrm{)}\in {\mathit{PGs}}^2\mathrm{,}\oplus \mathrm{(}\mathit{p}{g}^{\prime }\mathrm{,}\mathit{p}{g}^{″}\mathrm{)}$ (or $\mathit{p}{g}^{\prime }\oplus \mathit{p}{g}^{″}$ ) is defined only if:

${\mathit{E}}_{\mathit{p}{g}^{\prime }}\cap {\mathit{N}}_{\mathit{p}{g}^{″}}=\varnothing \wedge {\mathit{N}}_{\mathit{p}{g}^{\prime }}\cap {\mathit{E}}_{\mathit{p}{g}^{″}}=\varnothing$

${\mathit{src}}_{\mathit{p}{g}^{\prime }}$ is compatible with ${\mathit{src}}_{\mathit{p}{g}^{″}}$ and ${\mathit{dest}}_{\mathit{p}{g}^{\prime }}$ is compatible with ${\mathit{dest}}_{\mathit{p}{g}^{″}}$ (see compatibility definition in Section 3.2).

${\mathit{properties}}_{\mathit{p}{g}^{\prime }}$ is compatible with ${\mathit{properties}}_{\mathit{p}{g}^{″}}$ .

Its value is $\oplus \mathrm{(}\mathit{p}{g}^{\prime }\mathrm{,}\mathit{p}{g}^{″}\mathrm{)}=\mathit{pg}$ with:

${\mathit{N}}_{\mathit{pg}}={\mathit{N}}_{\mathit{p}{g}^{\prime }}\cup {\mathit{N}}_{\mathit{p}{g}^{″}}$

${\mathit{E}}_{\mathit{pg}}={\mathit{E}}_{\mathit{p}{g}^{\prime }}\cup {\mathit{E}}_{\mathit{p}{g}^{″}}$

${\mathit{src}}_{\mathit{pg}}:{\mathit{E}}_{\mathit{pg}}\to {\mathit{N}}_{\mathit{pg}}$ , ${\mathit{src}}_{\mathit{pg}}={\mathit{src}}_{{\mathit{pg}}^{\prime }}\cup {\mathit{src}}_{{\mathit{pg}}^{″}}$ .

${\mathit{dest}}_{\mathit{pg}}:{\mathit{E}}_{\mathit{pg}}\to {\mathit{N}}_{\mathit{pg}}$ , ${\mathit{dest}}_{\mathit{pg}}={\mathit{dest}}_{\mathit{p}{g}^{\prime }}\cup {\mathit{dest}}_{\mathit{p}{g}^{″}}$ .

$\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $$\begin{array}{r}{labels}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}=\left\{\begin{array}{ll}{\mathit{labels}}_{{\mathit{pg}}^{\prime }}\mathrm{(}\mathit{m}\mathrm{)}\cup {\mathit{labels}}_{{\mathit{pg}}^{″}}\mathrm{(}\mathit{m}\mathrm{)}& \text{if both are defined}\\ {\mathit{labels}}_{{\mathit{pg}}^{\prime }}\mathrm{(}\mathit{m}\mathrm{)}& \text{if only }{\mathit{labels}}_{{\mathit{pg}}^{\prime }}\mathrm{(}\mathit{m}\mathrm{)}\text{ is defined}\\ {\mathit{labels}}_{{\mathit{pg}}^{″}}\mathrm{(}\mathit{m}\mathrm{)}& \text{if only }{\mathit{labels}}_{{\mathit{pg}}^{″}}\mathrm{(}\mathit{m}\mathrm{)}\text{ is defined}\end{array}\right.\end{array}$$

$\mathit{propertie}{s}_{\mathit{pg}}:\mathrm{(}{\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}\mathrm{)}\times \mathit{Str}\to \mathit{V}$ , $\mathit{propertie}{s}_{\mathit{pg}}=\mathit{propertie}{s}_{{\mathit{pg}}^{\prime }}\cup \mathit{propertie}{s}_{{\mathit{pg}}^{″}}$ .

Lemma 4.

⊕ is commutative, associative, and the neutral element is the empty PG ${\mathit{pg}}_{\varnothing }$

Proof. (Sketch).

⊕ is defined by using the ∪ operator, which is commutative, associative and whose neutral element is ∅. The equivalent of ∅ for PGs is ${\mathit{pg}}_{\varnothing }$ .  □

Theorem 5.

The ⊕ merge of the π projection of a PG on all its PG elements is equal to the PG itself: $$\begin{array}{c}\forall \mathit{pg}\in \mathit{PGs}\mathrm{,}\mathit{pg}=\underset{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}{{\displaystyle ⨁}}{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}\end{array}$$

Proof.

The proof is provided in Appendix A.  □

While the ⊕ operator has been primarily designed as the inverse operation of the projection operator π, it can only merge two PG that are consistent between themselves. If a PG defines an entity as a node, the other PG can not define it as an edge. If a PG has a given source and destination for a given edge, the other one can not define another source or destination. Properties must also be consistent in both PGs. The presented version of the merge operator can only add information, and in the case merging two PGs would lead to an inconsistent PG, the merge operator is undefined.

Relationship between the $\mathit{prsc}$ function and projections We are now going to redefine the $\mathit{prsc}$ function using the π operator.

The RDF graph built by $\mathit{prsc}$ from a PG $\mathit{pg}$ with a context $\mathit{ctx}$ is equal to: $$\begin{array}{c}\mathit{rdf}={\displaystyle \bigcup }_{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}\end{array}$$

The $\mathit{build}$ function is defined in such a way that the RDF triples it produces from an element m are only influenced by:

• m itself.

• Its labels, i.e. $\mathit{label}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ .

• Its property values, i.e. $\forall \mathit{key}$ , $\mathit{propertie}{s}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{,}\mathit{key}\mathrm{)}$ .

• If m is an edge, its source and destination nodes, i.e. $\mathit{sr}{c}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ and $\mathit{des}{t}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}$ .

• The template graph $\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}$ .

Therefore the following equality can be asserted, $\forall \mathit{pg}\in \mathit{BPGs}$ , $\forall \mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ , $\forall \mathit{ctx}\in \mathit{Ct}{x}_{\mathit{pg}}$ : $$\begin{array}{c}\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{m}\mathrm{)}=\mathit{build}\mathrm{\left(}\mathit{ctx}\mathrm{\right(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}\mathrm{,}{\mathit{\pi }}_{\mathit{m}}\mathbf{(}\mathit{pg}\mathbf{)}\mathrm{,}\mathit{m}\mathrm{)}\end{array}$$

${\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}$ can be considered as the minimal required Property Graph to produce the RDF triples related to the element m in the PG $\mathit{pg}$ . If we can prove that the reversion algorithm constructs all ${\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}$ graphs and merges them with the ⊕ operator, then it means that we have properly reconstructed the $\mathit{pg}$ PG.

Completing the proof of the reversion algorithm We are now back to proving that for all well-behaved contexts $\mathit{ctx}$ , the $\mathit{RDFToPG}$ function presented in Algorithm 2 is an implementation of the ${\mathit{prsc}}^{-1}$ function. $\mathit{pg}$ is a PG for which we know the value of $\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}=\mathit{rdf}$ . We are focusing on the last line of Algorithm 2, where the $\mathit{buildpg}$ function is invoked.

To prove the correctness of the $\mathit{buildpg}$ function in Algorithm 5, starting from an empty PG g, we are going to show that at each iteration, we are adding to the PG g the π projection of $\mathit{pg}$ on an element m. After iterating on all elements, as we merged the π projection of all PG elements, the PG g ends up being equal to the PG $\mathit{pg}$ itself.

Lemma 5 (Merging the projection of one PG element to the reconstructed PG).

In Algorithm  5 , assuming that the $\mathit{typeof}$ parameter is equal to $\mathit{typeo}{f}_{\mathit{pg}}$ and $\mathit{buildfrom}$ is a total function that maps all PG elements b to $\mathit{build}\mathrm{(}\mathit{ctx}\mathrm{(}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}$ , at the end of an iteration of an element $\mathit{b}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$ after line 13, the computed PG ${\mathit{g}}_{\mathit{after}}$ is equal to ${\mathit{g}}_{\mathit{before}}\oplus {\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}$ , where ${\mathit{g}}_{\mathit{before}}$ is the PG g at the beginning of the iteration between lines 3 and 4.

Proof.

The PG ${\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}$ is described in Table 11. Bold values are the ones for which we need to prove that we compute the correct value: ${\mathit{src}}_{\mathit{g}}\mathrm{(}\mathit{b}\mathrm{)}$ , ${\mathit{dest}}_{\mathit{g}}\mathrm{(}\mathit{b}\mathrm{)}$ and ${\mathit{properties}}_{\mathit{g}}\mathrm{(}\mathit{b}\mathrm{,}\mathit{key}\mathrm{)}$ . Other values are trivially correct by construction.

Table 11

Description of the PG projection that is built in Algorithm 5

	$\mathit{b}\in {\mathit{N}}_{\mathit{pg}}$	$\mathit{b}\in {\mathit{E}}_{\mathit{pg}}$
${\mathit{N}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}\mathrm{)}}$	$\{\mathit{b}\}$	$\mathit{Img}\mathrm{(}{\mathit{src}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}\mathrm{)}\cup \mathit{Img}\mathrm{(}{\mathit{dest}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}\mathrm{)}$
${\mathit{E}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$	∅	$\{\mathit{b}\}$
${\mathit{src}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$	$\varnothing \to \varnothing$	$\mathit{b}\mapsto \mathit{sr}{c}_g\mathbf{\left(}\mathit{b}\mathbf{\right)}$
${\mathit{dest}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$	$\varnothing \to \varnothing$	$\mathit{b}\mapsto \mathit{des}{t}_g\mathbf{\left(}\mathit{b}\mathbf{\right)}$

	$\mathit{b}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}$
${\mathit{labels}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$	$\{\mathit{b}\mapsto \mathit{labels}\mathrm{(}\mathit{type}\mathrm{)}\}$
${\mathit{properties}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$	${\bigcup }_{\mathit{key}\in \mathit{keys}\mathrm{(}\mathit{type}\mathrm{)}}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{key}\mathrm{)}\mapsto \mathit{propertie}{s}_g\mathbf{(}\mathit{b}\mathbf{,}\mathit{key}\mathbf{)}\}$

In the following, we want to check that $\mathit{extract}\mathrm{(}?\mathit{source}\mathrm{,}\mathit{build}\mathrm{(}{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}\mathrm{,}\mathit{pg}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}\mathrm{)}$ properly returns ${\mathit{src}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$ . Proofs for $?\mathit{destination}$ / ${\mathit{dest}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$ and $\mathit{key}\in {\mathit{keys}}_{\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{b}\mathrm{)}}$ / ${\mathit{properties}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}\mathrm{(}\mathit{b}\mathrm{,}\mathit{key}\mathrm{)}$ are identical.

The $\mathit{values}$ set is filled by iterating on all $\mathit{tp}$ such that $\mathit{unique}\mathrm{(}\mathit{tp}\mathrm{,}\mathit{tps}\mathrm{)}\wedge ?\mathit{source}\in \mathit{tp}$ . The no value loss criterion ensures that at least one such template triple exists, so the loop in $\mathit{extract}$ is iterated at least once.

Theorem 1 ensures that the built set $\mathit{samekappa}$ in the loop of the $\mathit{extract}$ function will always have 1 element, that we name $\mathit{td}$ . Error(Unique data triple is not unique) may never be raised if $\mathit{rdf}$ was produced by PRSC. By definition of the $\mathit{build}$ function, $?\mathit{source}$ in $\mathit{tp}$ and ${\mathit{src}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$ in $\mathit{td}$ are at the same position.

After the loop, because only ${\mathit{src}}_{{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}}$ is added to $\mathit{values}$ in the loop, Error(Not exactly one value for a placeholder) may never be raised.

The last instructions differ for $?\mathit{source}$ / $?\mathit{destination}$ and P. In the case of $?\mathit{source}$ and $?\mathit{destination}$ , the obtained value is directly the value of the PG node; in the case of P, the obtained RDF literal needs to be converted into the proper PG property value, which is possible because ${\mathit{toLiteral}}^{-1}$ is assumed to be computable in Section 4.5.

$\mathit{extract}$ properly computes the values that are missing in ${\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}$ . When these values are extracted, they are directly merged with the ∪ operator into the g property graph. Values that were already known or can be computed from the values that were just extracted, i.e. ${\mathit{labels}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}$ , ${\mathit{N}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}$ and ${\mathit{E}}_{{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}$ , are also merged into g.

As all values of ${\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}$ are merged into ${\mathit{g}}_{\mathit{before}}$ , ${\mathit{g}}_{\mathit{after}}={\mathit{g}}_{\mathit{before}}\oplus {\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}$  □

Remark 15 (Completeness of $\mathit{buildpg}$ ).

In the case where $\mathit{rdf}$ is built from a PG $\mathit{pg}$ , the value that a placeholder is mapped to is the same everywhere, so we never run at the risk of encountering multiples values, i.e. Error(Not exactly one value for a placeholder) is never raised. Furthermore, the proof of Lemma 5 shows that Error(Unique data triple is not unique) may not be raised, because we know that each unique template triple has produced one data triple.

Theorem 6 (Merging the projection of all PG elements to the reconstructed PG).

Under the same assumptions as Lemma  5 , the PG returned by Algorithm  5 is the original $\mathit{pg}$ , the PG that was used to produce the RDF graph $\mathit{rdf}=\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ .

Proof.

The PG g in the algorithm is initialized to ${\mathit{pg}}_{\varnothing }$ . Lemma 5 shows that after each iteration in the loop with an element b, the PG g is ⊕-merged with the PG ${\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}$ . The loop iterates on all elements in the PG $\mathit{pg}$ , so after all the iterations, the PG g is equal to: $$\begin{array}{rlr}\mathit{g}& =\mathit{p}{g}_{\varnothing }\oplus \underset{\mathit{b}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}{{\displaystyle ⨁}}{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}& \\ & =\underset{\mathit{b}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}}{{\displaystyle ⨁}}{\mathit{\pi }}_{\mathit{b}}\mathrm{(}\mathit{pg}\mathrm{)}& [\mathit{p}{g}_{\varnothing }\text{ is the neutral element of }\oplus ]\\ & =\mathit{pg}& [\text{Theorem 5}]\end{array}$$  □

As $\mathit{buildpg}$ in Algorithm 5 correctly reconstructs $\mathit{pg}$ , and as its value is directly returned by the $\mathit{RDFToPG}$ function in Algorithm 2, we have finally proven that the latter is a sound and complete implementation of the ${\mathit{prsc}}^{-1}$ function for any well-behaved PRSC context $\mathit{ctx}$ .

5.3.5. Complexity analysis

Let us now discuss the complexity of the $\mathit{RDFToPG}$ function described in Algorithm 2. In this discussion, a new metric is considered: the number of triples in the RDF graph: $\mathit{NbTriples}=|\mathit{rdf}|$ . It is assumed that we have first checked if the context $\mathit{ctx}$ is a well-behaved PRSC context, and computed the $\mathit{sig}{n}_{\mathit{ctx}}$ function so it can now be called in constant time.

Extracting the list of blank nodes of an RDF graph on line 2 has a linear complexity of $\mathcal{O}\mathrm{(}\mathit{NbTriples}\mathrm{)}$ .

The $\mathit{FindTypeOfElements}$ function in Algorithm 3 uses three nested loops and only uses constant time operations: its complexity is $\mathcal{O}\mathrm{(}\mathit{NbOfPGElements}\ast \mathit{NbTriples}\ast \mathit{NbTypes}\mathrm{)}$ .

Trivially, Algorithm 4 has a complexity of $\mathcal{O}\mathrm{(}\mathit{NbOfPGElements}+\mathit{NbTriples}\mathrm{)}$ .

In Algorithm 5:

• Calls to $\mathit{extract}\mathrm{(}\mathit{placeholder}\mathrm{,}\mathit{tds}\mathrm{,}\mathit{tps}\mathrm{)}$ have a complexity of $\mathcal{O}\mathrm{(}|\mathit{tps}{|}^2\ast |\mathit{tds}|\mathrm{)}$ :

• Inside the loop, building the $\mathit{samekappa}$ set forces to loop on all $\mathit{tds}$ , multiplying the complexity by a $|\mathit{tds}|$ factor.

In the context of the $\mathit{buildpg}$ function, the $\mathit{extract}$ function is always called with a template graph $\mathit{tps}$ from the PRSC context and a sub-graph of the RDF graph $\mathit{rdf}$ as $\mathit{tds}$ . the complexity of the calls of the $\mathit{extract}$ function in the $\mathit{buildpg}$ function is $\mathcal{O}\mathrm{(}{\mathit{BiggestTemplateSize}}^2+\mathit{NbTriples}\mathrm{)}$ .11

¹¹

Note that if $\mathit{rdf}$ has been generated by the $\mathit{prsc}$ function, the number of triples in the graph $\mathit{tds}$ is inferior or equal to the number of triples in the template graph $\mathit{tps}$ as $\mathit{tds}$ has been generated from $\mathit{tps}$ . In this case, the complexity of calling $\mathit{extract}$ in the context of the $\mathit{buildpg}$ function is $\mathcal{O}\mathrm{(}{\mathit{BiggestTemplateSize}}^3\mathrm{)}$ .

The $\mathit{buildpg}$ function loops on all PG elements.

• Notice that while $\mathit{ctx}\mathrm{(}\mathit{typeof}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}$ is called multiple times, it can be called once and then its value can be cached. Its cost is $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}\mathrm{)}$ as mentioned in Section 4.6.3.

• There are at most $2+\mathit{TypeComplexity}$ calls of the $\mathit{extract}$ function. All of them have a $\mathcal{O}\mathrm{(}\mathit{BiggestTemplateSize}\ast \mathit{NbTriples}\mathrm{)}$ complexity.

• The complexity of each iteration is $\mathcal{O}\mathrm{(}\mathit{TypeComplexity}\ast ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}+\mathit{TypeComplexity}\ast {\mathit{BiggestTemplateSize}}^2\ast \mathit{NbTriples}\mathrm{)}\mathrm{)}$

The overall complexity of the $\mathit{buildpg}$ function is $\mathcal{O}\mathrm{(}\mathit{NbOfPGElements}\ast \mathit{TypeComplexity}\ast \mathrm{(}ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}+{\mathit{BiggestTemplateSize}}^2\ast \mathit{NbTriples}\mathrm{)}\mathrm{)}$

The overall complexity of the $\mathit{RDFToPG}$ function presented in Algorithm 2 presented in this section for an RDF graph produced from a PG and a well-behaved PRSC context is: $$\begin{array}{rl}& \mathcal{O}\mathrm{(}\mathit{NbTriples}\\ & +\mathit{NbTypes}\ast \mathit{NbTriples}\ast \mathit{BiggestTemplateSize}\\ & +\mathit{NbOfPGElements}+\mathit{NbTriples}\\ & +\mathit{NbOfPGElements}\ast \mathit{TypeComplexity}\ast \mathrm{(}ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}+{\mathit{BiggestTemplateSize}}^2\ast \mathit{NbTriples}\mathrm{)}\mathrm{)}\\ & =\mathcal{O}\mathrm{(}\mathit{NbTypes}\ast \mathit{NbTriples}\ast \mathit{BiggestTemplateSize}\\ & +\mathit{NbOfPGElements}\ast \mathit{TypeComplexity}\ast \mathrm{(}ln\mathrm{(}\mathit{TypeComplexity}\mathrm{)}+{\mathit{BiggestTemplateSize}}^2\ast \mathit{NbTriples}\mathrm{)}\mathrm{)}\end{array}$$

The $\mathit{RDFToPG}$ function is computable in polynomial time w.r.t. all the considered metrics, and is therefore considered as tractable. Furthermore, in our implementation, the algorithm has been optimized to significantly lower the complexity. However, for the sake of concision, we do not describe these optimizations in this paper.

5.4. Edge-unique extension

In many cases, there is only one edge of certain types between two nodes, like the “TravelWith” edge in our running example or for relationships like knowing someone, a parental relationship… For this type of edges, it is more intuitive to represent them with a simple RDF triple, and get rid of the blank node corresponding to the edge. However, Well-Behaved PRSC contexts require $?\mathit{self}$ in edge templates. In this section, we propose an extension to allow $?\mathit{self}$ to be missing in edge templates and still produce reversible conversions.

Table 12

A context for the Tintin PG with the “since” property

$\mathit{type}$	$\mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\{\text{“}\mathit{Person}\text{”}\}\mathrm{,}\{\text{“}\mathit{name}\text{”}\mathrm{,}\text{“}\mathit{job}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{ex}:\mathit{Person}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\mathrm{,}$
	$\mathrm{(}?\mathit{self}\mathrm{,}\mathit{ex}:\mathit{profession}\mathrm{,}\text{“}\mathit{job}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{node}\text{”}\mathrm{,}\varnothing \mathrm{,}\{\text{“}\mathit{name}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{self}\mathrm{,}\mathit{foaf}:\mathit{name}\mathrm{,}\text{“}\mathit{name}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$
$\mathrm{(}\text{“}\mathit{edge}\text{”}\mathrm{,}\{\text{“}\mathit{TravelsWith}\text{”}\}\mathrm{,}\{\text{“}\mathit{since}\text{”}\}\mathrm{)}$	$\{\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\mathrm{,}$
	$\mathrm{(}\mathrm{(}?\mathit{source}\mathrm{,}\mathit{ex}:\mathit{isTeammateOf}\mathrm{,}?\mathit{destination}\mathrm{)}\mathrm{,}\mathit{ex}:\mathit{since}\mathrm{,}\text{“}\mathit{since}{\text{”}}^{\mathit{valueOf}}\mathrm{)}\}$

Consider the Tintin PG exposed in Fig. 1 and the context exposed in Table 12, which uses RDF-star to convert the “since” property. The output of PRSC from those two inputs is exposed in Listing 4. By looking at the produced RDF graph, it appears that the RDF graph captures all the information of the PG. More generally, RDF graphs produced by this context would always be reversible as long as the source PG does not contain multiple “TravelsWith” edges between two given nodes.

Listing 4.

The output of PRSC for the Tintin PG and the context exposed in Table 12

Definition 28 (Edge-unique extension).

a) In a context $\mathit{ctx}$ , an edge-unique type $\mathit{edgeunq}$ is an edge type such that:

$\mathit{ctx}\mathrm{(}\mathit{edgeunq}\mathrm{)}$ complies with the no value loss criterion (as per Definition 24-3) and is not empty.

For all template triples $\mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{edgeunq}\mathrm{)}$ :

• $?\mathit{source}\in \mathit{tp}$ and $?\mathit{destination}\in \mathit{tp}$

• $\mathit{tp}$ is a signature template triple (as per Definition 24-2), i.e. no other type has a template triple that shares its value through κ.

• $\mathit{tp}$ is a $\mathit{unique}$ template triple, i.e. no other template triple in $\mathit{ctx}\mathrm{(}\mathit{edgeunq}\mathrm{)}$ shares its value through κ.

b) A PG $\mathit{pg}$ is said edge-unique valid for a context $\mathit{ctx}$ if for all edge-unique types in the context, there is at most one edge of this type between two given nodes: $$\begin{array}{rl}\forall \mathit{e}\in {\mathit{E}}_{\mathit{pg}}\mathrm{,}\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{e}\mathrm{)}\text{ is an edge-unique type}\Rightarrow & \left(\forall {\mathit{e}}^{\prime }\in {\mathit{E}}_{\mathit{pg}}\mathrm{,}\left[\begin{array}{cc}& \mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{e}\mathrm{)}=\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}{\mathit{e}}^{\prime }\mathrm{)}\\ \wedge & \mathit{sr}{c}_{\mathit{pg}}\mathrm{(}\mathit{e}\mathrm{)}=\mathit{sr}{c}_{\mathit{pg}}\mathrm{(}{\mathit{e}}^{\prime }\mathrm{)}\\ \wedge & \mathit{des}{t}_{\mathit{pg}}\mathrm{(}\mathit{e}\mathrm{)}=\mathit{des}{t}_{\mathit{pg}}\mathrm{(}{\mathit{e}}^{\prime }\mathrm{)}\end{array}\right]\Rightarrow \mathit{e}={\mathit{e}}^{\prime }\right)\end{array}$$ c) The $\mathit{prscEdgeUnique}$ function is introduced to serve as a proxy to the $\mathit{prsc}$ function to be applied only if the given PG is edge-unique valid relatively to the given context: $$\begin{array}{c}\mathit{prscEdgeUnique}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}=\left\{\begin{array}{ll}\mathit{prsc}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}& \text{if }\mathit{pg}\text{ is edge-unique valid for }\mathit{ctx}\\ \text{undefined}& \text{otherwise}\end{array}\right.\end{array}$$

Theorem 7 shows that $\mathit{prscEdgeUnique}$ is reversible up to an isomorphism.

Theorem 7.

Let $\mathit{ctx}$ be a context such that each type either a) matches the constraints of a type in a well-behaved PRSC context in Definition  24 or b) is an edge-unique type.

For every two BPGs, $\mathit{p}{g}^{\prime }$ and $\mathit{p}{g}^{″}$ , such that $\mathit{prscEdgeUnique}\mathrm{(}\mathit{p}{g}^{\prime }\mathrm{,}\mathit{ctx}\mathrm{)}=\mathit{prscEdgeUnique}\mathrm{(}\mathit{p}{g}^{″}\mathrm{,}\mathit{ctx}\mathrm{)}$ , $\mathit{p}{g}^{\prime }$ and $\mathit{p}{g}^{″}$ are isomorphic.

There is an algorithm such that for all BPGs $\mathit{pg}$ , from the RDF graph $\mathit{prscEdgeUnique}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ and the context $\mathit{ctx}$ , the algorithm computes a PG $\mathit{p}{g}^{\prime }$ such that $\mathit{prscEdgeUnique}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}=\mathit{prscEdgeUnique}\mathrm{(}\mathit{p}{g}^{\prime }\mathrm{,}\mathit{ctx}\mathrm{)}$ , i.e. from the produced RDF graph and the context, it is possible to compute a PG that is isomorphic to the original one.

Proof. (Sketch).

The context $\mathit{ctx}$ is composed of two parts: a) the well-behaved part and b) the edge-unique part. The well-behaved part has been proved to be reversible. As template triples used for edge-unique types are signatures, their value trough κ is different from the triples produced from the value through κ of the triples of the well-behaved part: triples produced from edge-unique types are distinguishable from the rest of the RDF graph.

Denote W the set of all types in the well-behaved part and U the types in the edge-unique part. Let $\mathit{pg}$ be a PG such that $\mathit{rdf}=\mathit{prscEdgeUnique}\mathrm{(}\mathit{pg}\mathrm{,}\mathit{ctx}\mathrm{)}$ exists. It is possible to split $\mathit{pg}$ using W and U: $$\begin{array}{c}\mathit{pg}=\underset{\mathit{p}{g}_W}{\underbrace{\underset{\mathit{m}\in {\mathit{N}}_{\mathit{pg}}\cup {\mathit{E}}_{\mathit{pg}}|\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{m}\mathrm{)}\in \mathit{W}}{{\displaystyle ⨁}}{\mathit{\pi }}_{\mathit{m}}\mathrm{(}\mathit{pg}\mathrm{)}}}\oplus \underset{\mathit{p}{g}_U}{\underbrace{\underset{\mathit{u}\in {\mathit{E}}_{\mathit{pg}}|\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{u}\mathrm{)}\in \mathit{U}}{{\displaystyle ⨁}}{\mathit{\pi }}_{\mathit{u}}\mathrm{(}\mathit{pg}\mathrm{)}}}\end{array}$$

It is also possible to split $\mathit{rdf}$ by defining an $\mathit{isWellBehaved}$ predicate that uses κ to filter triples that come from types in the well-behaved part: $\forall \mathit{td}\in \mathit{RdfTriples}$ , $\mathit{isWellBehaved}\mathrm{(}\mathit{td}\mathrm{)}\iff \exists \mathit{type}\in \mathit{W}$ , $\exists \mathit{tp}\in \mathit{ctx}\mathrm{(}\mathit{type}\mathrm{)}$ , $\mathit{\kappa }\mathrm{(}\mathit{td}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$ . $$\begin{array}{c}\mathit{rdf}=\underset{\mathit{rd}{f}_W}{\underbrace{\{\mathit{td}\in \mathit{rdf}|\mathit{isWellBehaved}\mathrm{(}\mathit{td}\mathrm{)}\}}}\cup \underset{\mathit{rd}{f}_U}{\underbrace{\{\mathit{td}\in \mathit{rdf}|\neg \mathit{isWellBehaved}\mathrm{(}\mathit{td}\mathrm{)}\}}}\end{array}$$

From all the theorems on well-behaved contexts, there is a bijection between $\mathit{p}{g}_W$ and $\mathit{rd}{f}_W$ .

All template triples used in the template graph of edge-unique types are both signature and unique: from any triple in $\mathit{rd}{f}_U$ , it is possible to find which template triple produced it. Consider an arbitrary edge u, whose type is an edge-unique type, i.e. $\mathit{typeo}{f}_{\mathit{pg}}\mathrm{(}\mathit{u}\mathrm{)}\in \mathit{U}$ . As edge-unique template graphs must also comply with the no value loss criterion, all properties, the source node and the destination node of u can be found in a non-ambiguous manner in $\mathit{rd}{f}_U$ . The only missing information is the edge identity, i.e. the blank node u itself.

By using a fresh blank node for u, it is possible to build a PG isomorphic to ${\mathit{\pi }}_{\mathit{u}}\mathrm{(}\mathit{pg}\mathrm{)}$ from $\mathit{rd}{f}_U$ , by extension, a PG isomorphic to $\mathit{p}{g}_U$ from $\mathit{rd}{f}_U$ , and by extension a PG isomorphic to $\mathit{pg}$ from $\mathit{rdf}$ .  □

5.5. Discussion about the constraints on well-behaved PRSC contexts

In this section, we discuss the acceptability of the different constraints posed by PRSC well-behaved contexts in terms of usability. In other words, to what extent do they limit what can be achieved with PRSC?

The no value loss criterion on well-behaved contexts ensures that the data are still present and can be found unambiguously: as its name implies, this constraint is obviously required to avoid information loss. Therefore, it should not be perceived as overly constraining when building PRSC contexts.

The signature template triple is a method to force the user to type the resources, which is usually considered to be good practice. The type can either be explicit, through a triple with $\mathit{rdf}:\mathit{type}$ as the predicate, or implicit through a property that is only used by this type. For example, the template graph for a type Person could contain a template triple for the form $\mathrm{(}?\mathit{self}\mathrm{,}:\mathit{personId}\mathrm{,}\text{“}\mathit{pid}{\text{”}}^{\mathit{valueOf}}\mathrm{)}$ . The constraint of a signature composed of only one triple can be considered too strong: one may want to write a context that works for all PGs. For example, many authors [20,32] propose to map each label to an RDF type or a literal used as the object of a specific predicate like pgo:label. More generally, users may want to use a composite key to sign their types. For these kinds of mappings, our approach of identifying the type by finding a single signature template is not sufficient. It requires finding all the signature template triples and deciding to which type they are associated, for example through a Formal Concept Analysis process. This could be studied as a future extension of the PRSC reversion algorithm.

The element provenance constraint may hinder the integration of RDF data coming from a PG with regular RDF data: it forces the user to keep the structure exposed in the PG, with blank nodes representing the underlying structure of the PG. The edge-unique extension enables to leverage this constraint, by avoiding representing PG edges as RDF nodes.

6. Related works

Many works already exist to address the interoperability between PGs and RDF.

A common pivot for PGs and RDF To achieve interoperability, some authors propose to store the data into another data model, and then expose the data through usual PG and RDF APIs. Angles et al. propose multilayered graphs [4], for which the OneGraph vision from Lassila et al. [23] is a more concrete version. These works propose to describe the data with a list of edges, with the source of the edge, a label and the destination of the edge. All edges are associated with an identifier, that can be used as the source or the destination of other edges. However, authors note that several challenges are raised about the way to implement the interoperability between the OneGraph model and the existing PG and RDF APIs.

In a Unified Relational Storage Scheme [35], Zhang et al. propose to store the data in relational databases. While they specify how to store both models in a similar relational database structure, they do not mention how they align the data that come from one model with the data that come from another, for example to match the PG label “Person” with the RDF type foaf:Person.

The Singleton Property Graph model proposed by Nguyen et al. [25] is an abstract graph model that uses the RDF Singleton Property pattern that can be implemented both with a PG and an RDF graph. They also describe how to convert a regular RDF graph or a regular PG into a Singleton Property Graph. But the use of the Singleton Property pattern induces the creation of many different predicates, which hinders the performance of many RDF database systems as shown by Orlandi et al. [26].

From PGs to RDF In terms of PG to RDF conversion, the most impactful work is probably RDF-star [17–20], an extension of the RDF model originally proposed by Olaf Hartig and Bryan Thompson to bridge the gap between PGs and RDF by allowing the use of triples in the composition of other triples. Indeed, the most blatant difficulty when converting PG to RDF is converting the edge properties. However, most PG engines support multi-edges, i.e. two edges of the same type between the two same nodes. On the other hand, the naive approach consisting in using the source node, the type of the edge and the destination node as respectively the subject, the predicate and the object of an RDF triple would collapse the multi-edges. Converting each edge property to an RDF-star triple that uses the former triple as its subject would lead to the properties of each multi-edge to be merged. Khayatbashi et al. [21] study on a larger scale the different mappings described by Hartig and benchmark them. By allowing triples to be used as the subject and the object of other triples, it is possible to emulate the edge properties of PGs. While these mappings allow some kind of user customization, by letting them choosing the used IRIs, they never consider using different model structures for different PG types during the same conversion. For example, consider a PG with two types of edges: one edge type with the “knows” label and one with the “marriedTo” label. The mappings described in this paper do not enable the user to model edges with the “knows” label as a predicate and edges with the “marriedTo” label as a proper RDF resource. To tackle the edge property problem, Das et al. study how to use already existing reification techniques to represent properties [12]: the modelings that do not rely on quads can be used when writing a PRSC context.

Tomaszuk et al. propose the Property Graph Ontology (PGO) [32], an ontology to describe PGs in RDF. As this solution only describes the structure of the PG in RDF, the produced data is forced to use this ontology, with the exception of other already existing RDF ontologies without further transformations. Thanks to the Neosemantics12

¹²

https://github.com/neo4j-labs/neosemantics

plugin developed by Barrasa, Neo4j is able to benefit from RDF related tools like ontologies, and performs a 2-way conversion from and to RDF-star data. However, the PG to RDF conversion performed by Barrasa tends to affirm all triples it can, even for PG edges that may describe facts with a probability or that are time restricted: if the marriage between Alice and Bob has ended in 2017, the triple :Alice :marriedto :Bob should probably not be produced.

Gremlinator [31] allows users to query a PG and an RDF database by using the SPARQL language. This is a first step towards federated queries. However, it supposes that data stored in the PG and data stored in the RDF graph have a similar modeling, and it does not support RDF-star.

Instead of having a fixed mapping, our work on PREC [10] propose a mapping language named PREC to drive the conversion from PG to RDF. Delva propose RML-star [13], an extension of RML [14] and R2RML [30] that introduces new RML directives to generate RDF-star triples. As discussed in Section 2, the format in which the template triples are described in this work is closer to the produced triples, at the cost of reducing the ability to produce templated IRIs or terms.

To leverage the requirement for users to manually write the mapping, Fathy et al. proposed ProGoMap [15], an engine that first generates a putative ontology for the terms in a PG, aligns this ontology with a real world ontology, and finally converts the PG to an RDF graph with an RML mapping generated from the alignment. The authors motivate the choice of automating the ontology alignment process by mentioning that writing mapping manually can be time-consuming. While this may be true, we do not think that this hinders PRSC usefulness as 1) the schema part of a PRSC context may be generated automatically, and nothing prevents a tool from generating the template triples automatically, 2) a PG schema for which writing template triples is time-consuming may be an indicator that the schema is too complex, and therefore that the structure of the data stored in the PG should be cleaned, not only to make the conversion to RDF easier, but also as a benefit for the PG itself, and 3) while the process of aligning terms of the putative ontologies to terms of real ontologies indeed increase data interoperability, it still relies on the idea that the structure of the PG is somewhat close to the structure of the desired RDF graph. However, in this paper, we advocate that it may not be the case, and that the desired method to model each edge type depends on the semantics of held by each edge type.

In general, to the best of our knowledge, most existing works only tackle the syntactic aspect of converting PG to RDF data. While this level of interoperability is appreciated, it is not enough to be able to properly use the converted data in any existing RDF application without further modification of the RDF graph. Other existing works provide a level of semantic interoperability. However, they tend to choose one of the many syntactic representations of edges that exist, despite RDF ontologies having a great variety of patterns to model knowledge. PRSC gives full control to the user, by letting them choosing both the syntactic representation and use shared vocabularies in the produced RDF graph. The use of PG schemas in PRSC contexts guides users in the process of writing the context. The study on PRSC well-behaved contexts, and the related discussion on their constraints in Section 5.5, provide information on if the PRSC context written by the user leads to a reversible conversion or not, and by consequence, if any information is lost in the process of converting the data stored in the PG into RDF.

From RDF to PGs Abuoda et al. [1] study the different RDF-star to PG approaches and identified two classes: the RDF-topology preserving transformation which converts each term into a PG node, and the PG transformation that converts literals into property values. They also evaluate the performance of these different approaches. The PRSC reversion algorithm, and the general philosophy of this work clearly falls under the latter category. The former can be considered as using a PG database to store RDF data.

Angles et al. [5] discuss different methods to transform an RDF graph into a PG. They propose different mappings, including an RDF-topology preserving one and a PG transformation. Atemezing and Hyunh [6] propose to use a mapping similar to the former to publish and explore RDF data with PG tools, namely Neo4j. However, these works offer little customization for the user.

With G2GML [11], Chiba et al. propose to convert RDF data by using queries: the output of the query is transformed into a PG by describing a template PG, similar to a Cypher insert query. This approach can be considered to be a counterpart of PRSC, but to convert RDF into PG.

PG schemas Finally, the “Property Graph needs a Schema” Working Group propose a formal definition of PG schemas [3]. Some PG engines, like TigerGraph, are based on the use of schemas. For PG engines that do not enforce a schema at creation, like Neo4j or Amazon Neptune, the schema may be extracted from the data, as proposed by Bonifati et al. [8] or Beereen [7]. As PRSC uses schemas for mapping between PGs and RDF graphs, these approaches may be used to automatically list the types existing in the PG to convert i.e. the target of the rule part in Listing 2. Then the user would only have to provide the way to convert these types into RDF, i.e. the template graph part.

7. Conclusion

This work improves interoperability between the two worlds of Property Graphs and RDF graphs. We have presented PRSC, a mapping language to convert PGs into RDF graphs. A mapping, named PRSC context, is written by the user and is driven by a schema: PG elements are converted according to their type. By letting the user configure the conversion, we aim to better integrate PG data into already existing RDF graphs: the produced RDF graphs can be made to use a specific vocabulary, or comply with specific shapes.

We have also proved that some PRSC contexts, named well-behaved PRSC contexts, are reversible: they do not induce any information loss, and therefore it is possible to reverse back to the original PG from the produced RDF graph. Finally, we broaden the realm of reversible contexts with the edge-unique extension. Other existing works focus either on describing a syntactic construction, or providing a semantic construction that relies on a specific syntactic pattern. PRSC lets the user specify the semantics, and proved the reversibility for the two most popular methods to model edges: as an RDF resource in PRSC well-behaved contexts, and as a predicate through the edge-unique extension.

For big PGs, fully converting them into RDF may not scale. For this reason, future works include studying how to use PRSC context not only for PG conversion but also to convert SPARQL queries into the usual PG query languages Cypher and Gremlin. This would not only address the scalability issues, but also avoid data duplication and help for federated queries.

The expressiveness of PRSC contexts could also be extended. As it is currently presented, PRSC contexts are unable to reproduce RDF graphs complying with some ontologies, for example the PG ontology [32]. To solve this issue, PRSC contexts should be able to introduce new blank nodes, and not be limited to the ones in the original PG. This would lead to new challenges, as the presented reversion algorithm relies on the fact that all blank nodes are PG elements.

Other extensions on expressiveness may also be interesting. For examples, types in PRSC contexts are closed, in the sense that a complying element must have exactly the properties of the type, barring any other. Allowing extra properties in elements of the PGs would be useful, but raises the challenge of converting properties that are not known in advance.

To let PG data further benefit from the tools that have been developed around RDF, PRSC could also be explored in two directions. The use of blank nodes for the PG elements may not be suitable in all cases, especially in a linked data context. PRSC could be extended to mint IRIs for nodes and edges of the PG, but this would require to extend the mapping language to be able to express these template IRIs. It would also require an adaptation of the reversion algorithm to be able to differentiate the minted IRIs from the “static” IRIs of the template, which would require additional precautions on well-behaved contexts.

The provided reversion algorithm does not only work for RDF graphs that were produced by PRSC, but can work on any compatible RDF graph. One way to use it would be to use PRSC to convert a PG to an RDF graph, modify the produced RDF graph with RDF-specific tools, e.g. by using a reasoner designed for RDF graphs, and then transform back the RDF graph into a PG, which could be considered as equivalent as using a reasoner on a PG. However, this requires to formally characterize the modifications that can be performed on the RDF triples while maintaining the ability to convert it back to a PG.