An Algebraic Graph Transformation Approach
for RDF and SPARQL

Mathematical semantics of computer science languages has been advocated since early 1970’s. It allows one to give precise meaning of syntactical objects and paves the way for involved reasoning methods such as modularity, compositionality, security and verification techniques, to quote a few. Nowadays, graph databases are becoming a very influential technology in our society. Mastering programming languages involved in the encoding of such graph data is a necessity to elaborate robust modern data management systems. Relational algebra [7] was the main mathematical foundation underlying oldy SQL-like formalisms for databases. However, with the advent of new graph oriented formalisms such as the most recent recommendations of the World Wide Web Consortium (W3C) about the Resource Description Framework (RDF) [20] and the associated query language SPARQL [19], there is a clear need of an alternative to relational algebra which copes with this change in data encodings, see e.g., [5, 16, 13]. In this paper, we consider RDF and SPARQL languages and propose a new mathematical semantics of a kernel of these formalisms within algebraic graph transformations setting.

RDF graphs are the key data structure in RDF. In [20, Section 3], an RDF graph is defined as a set of RDF triples, where an RDF triple has the form $(subject,predicate,object)$. The subject is either an IRI (Internationalized Resource Identifier) or a blank node, the predicate is an IRI and the object is either an IRI, a literal (denoting a value such as a string, a number or a date) or a blank node. Blank nodes are arbitrary elements as long as they differ from IRIs and literals and they do not have any internal structure: they are used for indicating the existence of a thing and the blank node identifiers are locally scoped. For instance, let us consider a toy database, $T_{data}$, consisting of the following four triples $T_{data}=\{(Alice,knows,Bob),(Tom,knows,Dave),(Bob,knows,blank_{1}),(blank_{1},knows,Alice)\}$. The two first triples say that Alice knows Bob and Tom knows Dave whereas the last two triples say that Bob knows someone, represented by the blank node $blank_{1}$, who knows Alice. Notice that a predicate in an RDF triple cannot be a blank. For example, a triple such as $(Paul,blank_{2},Henry)$ standing for “there is some relationship between Paul and Henry” is not allowed in RDF, but only in generalized RDF [20, Section 7]. Following the theoretical point of view we propose in this paper, there is no harm to consider blank predicates within RDF triples. We thus consider data graphs in a more general setting including RDF graphs.

The query language SPARQL for RDF databases is based on basic graph patterns, which are kinds of RDF graphs with variables [19, Section 2]. In this paper, we consider query graphs which generalize basic graph patterns by allowing blanks to be predicates. The SPARQL query processor searches for triples within a given RDF database which match the triple patterns in the given basic graph pattern, and returns a multiset of solutions or an RDF graph. Considering basic graph patterns, one may wonder what is the difference between variables and blank nodes. SPARQL specifications in [19, Section 4.1.4] suggest similarities between them, whereas the opposite is made in [19, Section 16.2]. In the formalization of SPARQL we propose, blank nodes and variables are clearly distinguished by their respective roles in the definition of morphisms.

In the SPARQL recommendation [19], the SELECT query form is described lengthily. This query form can be compared to the SELECT query form of SQL, which returns a multiset of solutions. In contrast, the CONSTRUCT query form returns an RDF graph. Let us consider again the previous toy database $T_{data}$ and assume we formulate a CONSTRUCT query that constructs triples of the form $R=(x,acquaintedWith,z)$ every time there exists a third party $y$ such that the following condition, which we call $L$, is satisfied : $(x,knows,y)$ and $(y,knows,z)$. Then, $L$ and $R$ are query graphs with variables $x,y$ and $z$. They intuitively stand for the left-hand and right-hand sides of a rule representing the considered CONSTRUCT query. To perform such query, one should consider all matches, $m$, of the condition $L$ against the database $T_{data}$ and for each match $m$, create a new triple $(m(x),acquaintedWith,m(z))$. Starting from database, $T_{data}$, this process yields the following result

From graph transformation point of view, $T_{data}$ is a host graph to be transformed by a rule whose left-hand and right-hand sides are respectively $L$ and $R$. Notice that the resulting graph $H$ does not contain the non-matched triple $(Tom,knows,Dave)$. This means that the considered transformations are not necessarily local. In addition, the graph $H$ gathers all possible results triggered by the matches of $L$ against the host graph $T_{data}$. This toy example is considered in Example 28.

Following our formalization, the CONSTRUCT query form, which is described very shortly in [19, Section 16.2], is more fundamental than the SELECT query form. Actually, we start by proposing an operational semantics for CONSTRUCT queries based on a new approach of algebraic graph transformations which we call POIM and we show afterward how SELECT queries can be easily encoded as CONSTRUCT queries. This new POIM approach represents a CONSTRUCT query as a rule of the form $L\rightarrow K\leftarrow R$ where $L,K$ and $R$ are basic graph patterns, and a rewrite step is made of a pushout followed by an image factorization. The result of a CONSTRUCT query is the outcome of the transformation one obtains when running the above rule against an RDF database. It happens that such rules and rewrite techniques can be used also to encode the solutions computed by SELECT query forms. As said earlier, the involved graph transformations are not local in the sense that only query answers should be computed out of the graph database. All parts which are not matched are deleted. Classical graph transformation techniques such as Double Pushout [9] and Single Pushout [10] or even more RDF oriented transformations like MPOC-PO [6] are not best recommended in this case (cf. Section 6 for a comparison with related work).

The paper is organized as follows. Section 2 defines the objects and the morphisms of the categories of data graphs and query graphs. Section 3 introduces the POIM algebraic transformation. In Section 4, we define two different operational semantics for CONSTRUCT queries and prove their equivalence. We first define a high-level calculus as a mere application of the POIM transformation. Then we propose a low-level calculus which is defined by means of several applications of the POIM transformation followed by a “merging” process. Both calculi implement faithfully the SPARQL semantics for CONSTRUCT queries (Theorem 21). In Section 5, we show how the POIM transformation can be used to define a novel operational semantics of the SELECT queries. This semantics, which is faithful to SPARQL definitions (Theorem 40), is obtained by an original translation of each SELECT query into a CONSTRUCT query. Concluding remarks and related work are discussed in Section 6.

The set of IRIs, denoted $\mathit{Iri}$, and the set of literals, denoted $\mathit{Lit}$, with its usual operations, are defined in [20]. Essentially, an IRI (Internationalized Resource Identifier) is an internet address and a literal denotes a value such as a string, a number or a date. The sets $\mathit{Iri}$ and $\mathit{Lit}$ are disjoint. In addition, let $B$ be a countably infinite set, disjoint from $\mathit{Iri}$ and $\mathit{Lit}$. The elements of $B$ are called blanks. According to [20, Section 3.1], an RDF graph is a set of RDF triples, where an RDF triple consists of three components: the subject, which is an IRI or a blank node; the predicate, which is an IRI; and the object, which is an IRI, a literal or a blank node. The set of nodes of an RDF graph is the set of subjects and objects of triples in the graph. Using set-theoretic notations, this can be expressed as follows: let $\mathit{Tr}=(\mathit{Iri}\cup B)\times\mathit{Iri}\times(\mathit{Iri}\cup\mathit{Lit}\cup B)$, then an RDF triple is an element of $\mathit{Tr}$ and an RDF graph is a subset of $\mathit{Tr}$. Let us also consider the following extension of RDF [20, Section 7]: A generalized RDF triple is a triple having a subject, a predicate, and object, where each can be an IRI, a blank node or a literal. A generalized RDF graph is a set of generalized RDF triples. Let $I=\mathit{Iri}\cup\mathit{Lit}$, so that a generalized RDF triple is an element of $(I\cup B)^{3}$ and a generalized RDF graph is a subset of $(I\cup B)^{3}$.

Let $V$ be a countably infinite set disjoint from $\mathit{Iri}$, $\mathit{Lit}$ and $B$. The elements of $V$ are called variables. According to [19, Section 2] a set of triple patterns is called a basic graph pattern, where triple patterns are like RDF triples except that each of the subject, predicate and object may be a variable. Let $\mathit{Tr}_{V}=(\mathit{Iri}\cup B\cup V)\times(\mathit{Iri}\cup V)\times(\mathit{Iri}\cup\mathit{Lit}\cup B\cup V)$, then a triple pattern is an element of $\mathit{Tr}_{V}$ and a basic graph pattern is a subset of $\mathit{Tr}_{V}$. Since $\mathit{Tr}_{V}$ is a subset of $(I\cup B\cup V)^{3}$, each basic graph pattern is a subset of $(I\cup B\cup V)^{3}$.

RDF graphs and basic graph patterns are generalized in Definition 2 as data graphs and query graphs respectively, are both relying on Definition 1.

Thus, by mapping $a$ to $|a|$ we get a one-to-one correspondence between the morphisms $a:T\to T^{\prime}$ of graphs on $A$ and the maps $M:|T|\to|T^{\prime}|$ such that $M^{3}(T)\subseteq T^{\prime}$.

An isomorphism (i.e., an invertible morphism) in $\mathbf{G}(A)$ is a morphism $a:T\to T^{\prime}$ of graphs on $A$ such that $|a|:|T|\to|T^{\prime}|$ is a bijection and $a(T)=T^{\prime}$. A morphism $a$ fixing $C$ is determined by the restriction of the map $|a|$ to $|T|\cap\overline{C}$, where $\overline{C}=A\setminus C$. An isomorphism $a$ in $\mathbf{G}_{C}(A)$ is a morphism $a:T\to T^{\prime}$ of graphs on $A$ such that $|a|$ is the identity on $|T|\cap C$ and a bijection between $|T|\cap\overline{C}$ and $|T^{\prime}|\cap\overline{C}$ and $a(T)=T^{\prime}$. The notions of inclusion, subgraph, image and union for graphs on $A$ are defined as inclusion, subset, image and union for subsets of $A^{3}$.

Thus, since $I=\mathit{Iri}\cup\mathit{Lit}$, the RDF graphs are the data graphs where only nodes can be blanks and only nodes that are not subjects can be literals, and the RDF terms of an RDF graph are its attributes when it is seen as a data graph. Then the isomorphisms of RDF graphs, as defined in [20, Section 3.6.], are the isomorphisms in the category $\mathbf{D}_{I}$ of data graphs fixing $I$: indeed, two data graphs $G_{1}$ and $G_{2}$ are isomorphic in $\mathbf{D}_{I}$ if and only if they differ only by the names of their blanks. For each data graph $T$, let $|T|_{I}=|T|\cap I$ and $|T|_{B}=|T|\cap B$, so that $|T|$ is the disjoint union of $|T|_{I}$ and $|T|_{B}$. Similarly, the basic graph patterns of SPARQL are the query graphs where only nodes can be blanks and only nodes that are not subjects can be literals. For each query graph $T$, let $|T|_{I}=|T|\cap I$, $|T|_{B}=|T|\cap B$ and $|T|_{V}=|T|\cap V$, so that $|T|$ is the disjoint union of $|T|_{I}$, $|T|_{B}$ and $|T|_{V}$.

Morphisms of graphs can be used, for instance, for substituting the variables of a query graph (Definition 3) or for interpreting a data graph in a universe of discourse (Definition 4).

Thus, a match fixes each resource identifier and it maps a variable or a blank to a resource identifier or a blank.

The interpretations of an RDF graph are also kinds of morphisms, see Definition 4. Note that this will not be used later in this paper. We define an interpretation of a data graph $G$ in a universe of discourse $U$ by generalizing the definition of a morphism, according to [20, Section 1.2.]: Any IRI or literal denotes something in the world (the “universe of discourse”). These things are called resources. The predicate itself is an IRI and denotes a property, that is, a resource that can be thought of as a binary relation. Recall that the binary relations on a set $R$ are the subsets of $R^{2}$. It may happen that a binary relation on $R$ is itself an element of $R$, this is important for understanding Definition 4 and the semantics of RDF in general.

In this paper, we consider categories $\mathbf{D}_{C}$ and $\mathbf{Q}_{C}$ for various subsets $C$ of ${IB}$ and ${IBV}$ respectively. It will always be the case that $C$ contains $I$, so that we can say that resource identifiers have a “global scope”. In contrast, blanks have a “local scope”: in the basic part of RDF and SPARQL considered in this paper, the scope of a blank node is restricted to one data graph or one query graph. The note about blank node identifiers in [20, Section 3.4] distinguishes two kinds of syntaxes for RDF: an abstract syntax where blank nodes do not have identifiers and concrete syntaxes where blank nodes have identifiers. In our approach a blank is an attribute, which corresponds to a concrete syntax, and the abstract syntax is obtained by considering data graphs as objects of the category $\mathbf{D}_{I}$ up to isomorphism, so that any blank node can be changed for a fresh blank node if needed.

Now let us focus on some kinds of colimits of graphs on $A$: coproducts in Proposition 9 and pushouts in Proposition 10. Recall that colimits in any category are defined up to isomorphism in this category. Remember that a morphism $a:T\to T^{\prime}$ in $\mathbf{G}(A)$ and a map $M:|T|\to|T^{\prime}|$ are such that $M(x)=|a|(x)$ for each attribute $x\in|T|$ if and only if $M^{3}(t)=a(t)$ for each triple $t\in T$.

This means that $D$ is a kind of “union of $G$ and $K$ over $L$”, however it is not the case that $D$ is the union of $G$ and $K\setminus L$, in general. It is always the case that $D=G\cup D_{2}$ where $D_{2}=N^{3}(K\setminus L)$ but in general $N^{3}$ is not the identity on $K\setminus L$ and moreover $G$ and $D_{2}$ are not disjoint.

A SPARQL query like “CONSTRUCT {$R$} WHERE {$L$}” is called basic when both $R$ and $L$ are basic graph patterns. In such a query, variables with the same name in $L$ and $R$ denote the same RDF term, whereas it is not the case for blank nodes. The statement “blank nodes in graph patterns act as variables” in [19, Section 4.1.4] holds for $L$, whereas blank nodes in $R$ give rise to fresh blank nodes in the result of the query as in Examples 18 and 23. Thus, the meaning of blank nodes in $L$ is unrelated to the meaning of blank nodes in $R$, and in both $L$ and $R$ each blank can be replaced by a fresh blank.

We generalize this situation in Definition 11 by allowing any data graphs for $L$ and $R$ up to isomorphism in $\mathbf{Q}_{{IV}}$: the resource identifiers and the variables in $L$ and $R$ are fixed but each blank can be replaced by a fresh blank. Thus, without loss of generality, we can assume that $|L|_{B}\cap|R|_{B}=\emptyset$. Under this assumption, the set of triples $K=L\cup R$ with the inclusions of $L$ and $R$ in $K$ is a coproduct of $L$ and $R$ in the category $\mathbf{Q}_{{IV}}$. We also assume that each variable in $R$ occurs in $L$, so that every substitution for the variables in $L$ provides a substitution for the variables in $R$. The relevance of this assumption with respect to SPARQL queries is discussed in Section 4.1. Note that this assumption $|R|_{V}\subseteq|L|_{V}$ is equivalent to $|K|_{V}=|L|_{V}$.

When a basic SPARQL query “CONSTRUCT {$R$} WHERE {$L$}” is run against an RDF graph $G$, and when there is precisely one match of $L$ into $G$, the result of the query is an RDF graph $H$ obtained by substituting the variables in $R$. This substitution can be seen as a match of $R$ into $H$. We claim that the process of building $H$ with this match of $R$ into $H$ from the match of $L$ into $G$ can be seen as a two-step process involving an intermediate match of $K$ in an RDF graph $D$. This claim will be proved, more generally, in Section 4. The definition of this two-step process relies on an algebraic construction that we call the POIM transformation: PO for pushout and IM for image (Definition 14). The POIM transformation is related to a large family of algebraic graph transformations based on pushouts, like the SPO (Simple Pushout) [10], DPO (Double Pushout) [9] or SqPO (Sesqui-Pushout) [8]. In the POIM transformation, the PO step creates fresh blank nodes and instantiates the variables of $K$, while the IM step deletes everything that is not in the image of $R$, as explained now.

Given a basic construct query $(L,R)$ and its transformation rule $L\stackrel{{\scriptstyle l}}{{\to}}K\stackrel{{\scriptstyle r}}{{\leftarrow}}R$, the POIM transformation is defined as a map from the matches of $L$ to the matches of $R$, in two steps: first from the matches of $L$ to the matches of $K$, then from the matches of $K$ to the matches of $R$. Given an inclusion $l:L\to K$ in $\mathbf{Q}_{I}$, the cobase change along $l$ is the map $l_{*}:\mathit{Match}(L)\to\mathit{Match}(K)$ that maps each $m:L\to G$ to $l_{*}(m):K\to D$ defined from the pushout of $l$ and $m$ in $\mathbf{Q}_{I}$, as described in Proposition 10. Note that $D$ is a data graph because of the assumption $|K|_{V}=|L|_{V}$. Given an inclusion $r:R\to K$ in $\mathbf{Q}_{I}$, the image factorization along $r$ is the map $r^{+}:\mathit{Match}(K)\to\mathit{Match}(R)$ that maps each $n:K\to D$ to $r^{+}(n):R\to H$ where $H$ is the image of $R$ in $D$ and $r^{+}(n)$ is the restriction of $n$ and $h:H\to D$ is the inclusion. This leads to Definition 14 and Proposition 15.

Proposition 15 says that $H$ is obtained from $R$ by instantiating all variables as in $L$ and by renaming blanks in an arbitrary way, as long as this renaming is one-to-one. Note that only the image of the match is transformed and the remaining parts of the RDF graph are deleted.

This Section begins with our definition of the query result of applying a basic construct query (Definition 11) to a data graph (Definition 2). Theorem 21 in Section 4.1 proves that our query result coincides (up to renaming blanks) with the answer returned by SPARQL when $L$ and $R$ are basic graph patterns and $G$ is an RDF graph. In Section 3, we defined the POIM transformation for running a basic construct query $(L,R)$ against a data graph $G$, when there is exactly one match from $L$ to $G$. Now, we define two different calculi for running a basic construct query against a data graph $G$ without any assumption on the number of matches. The high-level calculus (Definition 24) is one “large” application of the POIM transformation. The low-level calculus (Definition 26) consists of several “small” applications of the POIM transformation followed by a “merging” process. The construction of the high-level calculus is simpler, while the low-level calculus better fits with the description of the running process in SPARQL. Proposition 25 in Section 4.2 and Proposition 29 in Section 4.3 prove that both calculi compute the query result.