# Schema-Based Query Optimisation for Graph Databases

Chandan Sharma, Pierre Genevès, Nils Gesbert, Nabil Layaïda

## ► To cite this version:

Chandan Sharma, Pierre Genevès, Nils Gesbert, Nabil Layaïda. Schema-Based Query Optimisation for Graph Databases. SIGMOD 2025 - ACM International Conference on Management of Data, Jun 2025, Berlin, Germany. pp.1-29, 10.1145/3709722. hal-04485125v3

HAL Id: hal-04485125

https://inria.hal.science/hal-04485125v3

Submitted on 11 Feb 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
SCHEMA-BASED QUERY OPTIMISATION FOR GRAPH DATABASES

Chandan Sharma, Pierre Genevès, Nils Gesbert, Nabil Layaïda

Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG
Grenoble, France, 38000

ABSTRACT

Recursive graph queries are increasingly popular for extracting information from interconnected data found in various domains such as social networks, life sciences, and business analytics. Graph data often come with schema information that describe how nodes and edges are organized. We propose a type inference mechanism that enriches recursive graph queries with relevant structural information contained in a graph schema. We show that this schema information can be useful in order to improve the performance when evaluating recursive graph queries. Furthermore, we prove that the proposed method is sound and complete, ensuring that the semantics of the query is preserved during the schema-enrichment process.

**Keywords** Graph Schema · Query Optimisation · Graph Databases · Relational Algebra

# 1 Introduction

The creation, utilisation and, most importantly, analysis of highly interconnected data has become pervasive in various domains, including social media, astronomy, chemistry, bio-informatics, transportation networks and semantics associations (criminal investigation) Bell et al. [2009], Barrett et al. [2000], Sheth et al. [2005], Yang et al. [2020]. Graph databases have become appealing for modeling, managing and analysing highly interconnected data Sharma et al. [2021], Alotaibi et al. [2021].

Discovering complex relationships between graph-structured data requires expressive graph query languages to use recursion to navigate paths connecting nodes in a graph database Jachiet et al. [2020], Duschka et al. [2000]. Therefore, the design of contemporary graph query languages is based on formalisms such as *regular path queries* (RPQ), *two-way regular path queries* (2RPQ) and *nested regular expressions* (NRE) along with their extensions such as *conjunctive two-way regular path queries* (C2RPQ) Calvanese et al. [1999], *union of conjunctive two-way regular path queries* (UC2RPQ) Bonifati et al. [2018], Angles et al. [2017], *conjunctive nested regular expressions* (CNRE), *union of conjunctive nested two-way regular path queries* (UCN2RPQ) Barceló et al. [2013], Libkin et al. [2018], Reutter et al. [2017], XPath for graph databases (GXPath) Vrgoc [2014], Libkin et al. [2013] and more recently *conjunctive queries and union of conjunctive queries extended with Tarski's algebra* (CQT/UCQT) Sharma et al. [2021]. These foundations form the basis of languages such as SPARQL Hogan and Hogan [2020], Cypher Francis et al. [2018] and PGQL van Rest et al. [2016]. Furthermore, projects such as ISO/IEC 39075 <fnref n="1" /> and Linked Data Benchmark Council <fnref n="2" /> (LDBC) are working towards creating a standard query language for graph databases. At the core of all these graph query languages is *recursion*. It is essential to perform complex navigation and data extraction from the graph.

Furthermore, graph data often follow a certain organization, structural patterns, or even sets of constraints on the admissible graph shapes. Such knowledge may be left implicit or made explicit by the means of a so-called *graph schema* specification. In an ongoing standardization effort, *PG-Schema* Angles et al. [2023] and *PG-Keys* Angles et al. [2021] have been proposed to serve as a reference graph schema language for graph databases.

One fundamental idea of the work presented in this paper is to leverage the schema constraints in order to improve query evaluation. Intuitively, we conjecture that taking advantage of the constraints expressed in a schema can be useful

<footnote n="1">¹GQL: https://www.iso.org/standard/76120.html</footnote>

<footnote n="2">²LDBC: https://ldbcouncil.org</footnote>
to reduce the amounts of graph data involved when evaluating a query. This research proposes a schema-based query rewriting approach to optimize graph queries. We use a basic yet expressive graph schema formalism (based on Angles et al. [2023]) to express graph constraints. We consider graph queries expressed in the formalism of UCQT. We propose a type inference method for injecting relevant schema information into the query and produce a schema-aware UCQT variant that is semantically equivalent.

The optimization of recursive queries (even independently from schema constraints) is already known to be significantly more challenging than in the non-recursive setting Nguyen and Kim [2017], Yakovets et al. [2015], Jachiet et al. [2020]. Extensions to classical relational algebra have been proposed to support recursion Agrawal [1988], Gomes-Jr et al. [2015], Yakovets et al. [2015], Leeuwen et al. [2022]. As a result, many graph database engines use the query optimisation techniques developed for relational databases Sun et al. [2015], Shanmugasundaram et al. [1999], Jindal et al. [2014], Xirogiannopoulos et al. [2017]. Numerous optimisation techniques have been developed Meimaris et al. [2017], Neumann and Moerkotte [2011], Bornea et al. [2013], Jachiet et al. [2020] to optimise recursive graph queries independently from the schema.

However, due to the schema optional nature of contemporary graph databases Sharma and Sinha [2022], earlier schema-based methods that have been researched in other settings for recursive queries have been largely ignored. Examples of such earlier methods include static query analyses for Datalog Bonatti [2004], Calvanese et al. [1998, 2005], semi-structured Deutsch and Tannen [2001], Calvanese et al. [1998], Florescu et al. [1998] databases and XML Benedikt et al. [2008], Lakshmanan et al. [2004], Geerts and Fan [2005], Genevès and Layaïda [2006] databases. While these works are essentially of theoretical nature, they can still bring useful insights for schema-based graph query analyses and optimization.

The main contributions of this research work are:

**Schema-based approach for query rewriting** We propose a type inference mechanism capable of leveraging structural information of a graph schema in order to rewrite UCQT queries. In particular, the type inference mechanism enriches the edge label-based navigational graph queries with additional information related to node labels. This approach aims at reducing the size of intermediate subquery results in order to improve the overall query performance. The approach automatically optimises recursive graph queries and is capable of eliminating costly transitive closure operations using schema information. The soundness and completeness of type inference ensure that the semantics of the query is preserved during optimization.

**Prototype implementation** We have developed a prototype implementation to demonstrate the practical application of the schema-based approach. The prototype translates schema-based rewritten queries into graph patterns for graph databases and into recursive relational algebra for relational databases. We demonstrate the efficiency of the approach on graph and relational database systems.

**Experimental evaluation** In order to empirically evaluate the effectiveness of the approach, we use the LDBC social network benchmark dataset which is a property graph, and the YAGO dataset which is a knowledge graph. We use third-party recursive and non-recursive queries. Experiments show that the proposed schema-based approach is effective, especially for recursive queries.

**Organisation:** We present preliminary concepts related to graph databases in Sec. 2, including schemas and the UCQT graph query language. The main contribution to schema-based query rewriting is presented in Sec. 3, where we present an inference system to enrich queries with annotations deduced from the schema. The prototype implementation is presented in Sec. 4, where we describe the overall system architecture. We then report on empirical evaluation results in Sec. 5, where we also consider several (relational and graph-based) database systems. Finally, we discuss related works in Sec. 6 before concluding in Sec. 7.

## 2 Graph Databases

We present a few basic definitions related to graph databases. In particular, we define the notions of graph schema, graph database, schema-database consistency and graph queries. These notions are vital for schema-based query rewriting. Furthermore, we use the graph database representation of the YAGO dataset as a running example to illustrate various definitions present in subsequent sections.
## 2.1 Graph Schema

A *graph schema* is a directed pseudo multigraph: a graph in which loops on nodes and multiple directed edges between two nodes are permitted. A graph schema captures the structural and properties-based restrictions in a graph database, with nodes representing entities and edges representing relationships between entities. In graph schemas, nodes and edges are labeled, and properties associated with nodes are expressed in the form of *key-type* pairs. Let $L_N$ be a finite set of node labels and $L_E$ be a finite set of edge labels such that $L_N \cap L_E = \emptyset$. Let $K_S$ be a set of keys (for example: id, name, age), and $T$ be a finite set of data types (for example: String, Integer, Date). We define a finite set of properties $P_S$ such that $P_S \subseteq (K_S \times T)$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Sample graph schema for YAGO dataset.</figcaption></figure>

**Definition 1 (Graph Schema)** A graph schema is a tuple $S = (N_S, E_S, L_N, L_E, P_S, \lambda_S, \eta_S, \xi_S, \Delta_S)$ where,

* $N_S$ and $E_S$ are finite set of nodes and edges such that $N_S \cap E_S = \emptyset$.

* $\lambda_S : E_S \to N_S \times N_S$ is a function which maps all edges to source and target nodes.

* $\eta_S : N_S \to L_N$ is a function which maps all nodes to the set of node labels.

* $\xi_S : E_S \to L_E$ is a function which maps all edges to the set of edge labels.

* $\Delta_S : N_S \to 2^{P_S}$ is a function which maps all nodes to all possible subsets of the property set $P_S$.

**Example 1** Fig. 1 shows a graph schema for the YAGO dataset Hoffart et al. [2013] consisting of five nodes and seven edges. All edges are labeled and directed; some edges can represent loops on the same nodes. For instance, the edge labeled as *isMarriedTo* has the same source and target node labeled as *PERSON*. All nodes are labeled and have properties associated with them. For instance, a node is labeled as *REGION* and has a property *name: String* as a key:*type pair*.

## 2.2 Graph Database

A graph database is a graph instance that allows modeling real-world entities as labeled nodes and edges, with properties associated with nodes. Let $K_D$ be an infinite set of keys (for example, id, name, age), $V$ be a finite set of values (for example, 345, James). We define a function $\Upsilon: V \to T$ that maps values in $V$ to their respective data types in $T$. The set of properties associated with the nodes of a graph database are defined as $P_D$ such that $P_D \subseteq (K_D \times V)$ where each $p_d \in P_D$ is a *key-value pair* and each value has a data type. Formally, a graph database is defined as follows:

**Definition 2 (Graph database)** A graph database is a tuple $D = (N_D, E_D, L_N, L_E, P_D, \lambda_D, \eta_D, \xi_D, \Delta_D)$ where,

* $N_D$ and $E_D$ are finite set of nodes and edges such that $N_D \cap E_D = \emptyset$.

* $\lambda_D : E_D \to N_D \times N_D$ is a function which maps all edges to source and target nodes.

* $\eta_D : N_D \to L_N$ is a function which maps all nodes to the set of node labels.

* $\xi_D : E_D \to L_E$ is a function which maps all edges to the set of edge labels.

* $\Delta_D : N_D \to 2^{P_D}$ is a function which maps all nodes to all possible subsets of the property set $P_D$.
<figure><img src="image_3.png" /><figcaption>Figure 2: An example of YAGO graph database.</figcaption></figure>

**Example 2** Fig. 2 shows an example of a YAGO graph database consisting of seven nodes and nine edges. All nodes are labeled, and have optional properties associated with them. All edges are labeled and can be identified by unique source and target node identifiers using function $\lambda_D$. For instance, edge $(n_2, n_1)$ is labeled as owns, with $n_2$ as the source and $n_1$ as the target node identifier. The node with identifier $n_2$ is labeled as PERSON and has name: John and age: 28 as properties.

## 2.3 Schema-database consistency

The notion of schema-database consistency implies that a graph database follows the structural and property based restrictions established by a graph schema. We define a function $\mathcal{SD}: D \to S$ that maps elements in the graph database to at most one element in the graph schema (also known as strict graph schema Angles et al. [2023]).

**Definition 3 (Schema database consistency)** Given a graph database D and a graph schema S, we say that D is consistent with S when there exists a schema-database mapping $\mathcal{SD}$ such that:

* For every node $n_i \in D$ there exists a corresponding node in the schema: $\mathcal{SD}(n_i) \in S$, and we have $\eta_D(n_i) = \eta_S(\mathcal{SD}(n_i))$.

* For every edge $e_i \in D$ there exists a corresponding edge in the schema: $\mathcal{SD}(e_i) \in S$. Let $(n_i, n_j) = \lambda_D(e_i)$, then we have $\lambda_S(\mathcal{SD}(e_i)) = (\mathcal{SD}(n_i), \mathcal{SD}(n_j))$; furthermore, we have $\eta_D(n_i) = \eta_S(\mathcal{SD}(n_i))$, $\eta_D(n_j) = \eta_S(\mathcal{SD}(n_j))$ and $\xi_D(e_i) = \xi_S(\mathcal{SD}(e_i))$.

* For each $n_i \in N_D$ and for each $(k, v) \in \Delta_D(n_i)$, we have $(k, \Upsilon(v)) \in \Delta_S(\mathcal{SD}(n_i))$.

**Example 3** By using Def. 3, we can observe that the graph database presented in Fig. 2 is consistent with the graph schema shown in Fig. 1. For instance, edge $(n_2, n_3)$ is labeled as *isMarriedTo*; moreover, source and target nodes are labeled as PERSON and follow the property-based restrictions imposed in the YAGO graph schema.

In this study, we only consider graph databases that are consistent with the graph schema; that is, we exclude any database that does not conform to Def. 3. Furthermore, we consider graph databases with restrictions, including each node/edge can have at most one node/edge label associated with it, and edges do not have properties associated with them. However, as mentioned in Vrgoc [2014] our graph data model can easily be modified to accommodate properties over edges. In our graph data model we allow zero or more properties associated with nodes. Moreover, we consider that properties are atomic entities and cannot have maps nor lists as data types<fnref n="3" />.

## 2.4 Querying graph databases

Graph patterns are essential in graph query languages as they assist in defining the structure of data to be extracted from a graph database Angles et al. [2017], Francis et al. [2023a], Sharma et al. [2021].

The core component of a graph pattern is a *path expression* corresponding to specifying directed edges and/or paths defined over the edge labels of a graph database. To specify path expressions we use the formalism of *Tarski's algebra*

<footnote n="3">³Interested readers may refer to Angles et al. [2020], Sharma et al. [2021], Sharma and Sinha [2022] for detailed discussions on graph data model restrictions.</footnote>
which is strictly more expressive than other graph query formalisms such as two-way regular path queries (2RPQ) and nested regular expressions (NRE) Hellings [2018], Hellings et al. [2017]. The grammar of Tarski's algebra used to formulate a path expression $\phi$ is presented in Fig. 3.

<figure><img src="image_4.png" /><figcaption>Figure 3: Tarski's algebra grammar (adapted from Hellings [2018], Sharma et al. [2021]).</figcaption></figure>

In our adaptation of Tarski's algebra, the reverse operation can be used with single-edge labels, as shown in Fig. 3. Notice that it is possible to use the reverse operator in front of general path expressions $\phi$, as this does not offer any additional expressive power compared to the reverse operation on single-edge labels Hellings [2018].

In the sequel, we define and use the formalism of conjunctive queries and union of conjunctive queries extended with Tarski's algebra (CQT/UCQT) to express graph patterns based on path expressions. We choose the UCQT query language formalism for its high expressive power as it encompasses most existing query language formalisms. In particular, UCQT subsumes both union of conjunctive two-way regular path queries (UC2RPQ) and union of conjunctive nested two-way regular path queries (UCN2RPQ) which are used in many practical graph query languages such as Cypher, SPARQL and PGQL Sharma et al. [2021], Vrgoc [2014], Reutter et al. [2017].

Additionally, in UCQT, the conjunction operator is closed under transitive closure Sharma et al. [2021], Hellings [2018], which adds the ability to express recursive queries that search for arbitrary-length paths with repeating cyclic structures between the start and end nodes. Such queries cannot be expressed in the formalisms of UC2RPQ and UCN2RPQ Sharma et al. [2021].

### 2.4.1 Syntax of CQT/UCQT

Given a graph schema S and a graph database D, let $V_N$ be a finite set of node variables and $P_\phi$ be a set of path expressions $\{\phi_1, \dots, \phi_n\}$, such that each path expression $\phi_i \in P_\phi$ is defined over the set of edge labels $L_E$.

**Definition 4 (CQT)** A conjunctive query with Tarski's algebra is a logical formula in the $\exists, \wedge$-fragment of first order logic, of the form $C = \{(h_1, \dots, h_i) | \exists (b_1, \dots, b_j) r_1 \wedge \dots \wedge r_l \wedge a_1 \wedge \dots \wedge a_k\}$ where,

* $H = \{h_1, \dots, h_i\}$ is a finite set of head variables. $B = \{b_1, \dots, b_j\}$ is a finite set of body variables such that $(B \cup H) \subseteq V_N$ and $(B \cap H) = \emptyset$.

* $A = \{a_1, \dots, a_k\}$ is a finite set of atomic formulas formed by a labeling function $\eta_A: V_N \to (L_N \cup \epsilon)$ that maps all node variables to node labels in $L_N$ or to the empty label. These formulas can be of the form e. g. $\eta_A(Y) = \text{PERSON}$ to specify that nodes represented by the variable $Y$ must be labeled as PERSON.

* $\text{Rel} \subseteq (V_N \times P_\phi \times V_N)$ is a finite set of relations where each relation $r_i \in \text{Rel}$ either represent directed edge(s) or path(s) connecting two nodes.

<figure><img src="image_5.png" /><figcaption>Figure 4: Example of a graph pattern.</figcaption></figure>

**Example 4** The graph pattern in Fig. 4 identifies people living in regions and countries who also own properties. It consists of two relations: $(Y, owns, Z)$ searches for people who own properties. While $(Y, livesIn/isLocatedIn^+, M)$
specifies a path expression to search for paths that have edges labeled as *livesIn* followed by an unbounded number of edges labeled as *isLocatedIn* returning node that either correspond to regions or countries. Both relations share the same node variable *Y*, specifying that both relations must search for the same person.

$$C_1 = \{Y \mid \exists(Z, M) (Y, (livesIn/isLocatedIn+), M) \wedge (Y, owns, Z)\}$$

**Example 5** Query $C_1$, presents a graph pattern in Fig. 4 expressed as a CQT where $Z, M$ are body variables and $Y$ is a head variable. Relations $(Y, owns, Z)$ and $(Y, livesIn/isLocatedIn^+, M)$ describe the structure of the graph pattern.

We extend the CQT query language formalism to the formalism of the union of conjunctive queries with Tarski's algebra (UCQT) which is analogous to extending the formalism of C2RPQ to UC2RPQ. The formalism of UCQT represents the disjunction of conjunctive queries with Tarski's algebra. A UCQT query is written as $UC = H \leftarrow \{C_1 \cup \dots \cup C_n\}$, where all $C_i$ are union compatible CQT queries, that is, they share the same set of head variables H Pérez et al. [2006], Jachiet et al. [2020].

### 2.4.2 Semantics of CQT/UCQT

As discussed in Sec. 2.4, path expressions form the core components for syntactically describing graph patterns as CQT/UCQT. We first present the semantics of path expressions $\phi$ that are based on Tarski's algebra $^4$. The interpretation of the path expression $\phi$ when evaluated over a graph database D (represented as $[[\phi]]_D$) is defined in Fig. 5. The output produced after evaluating a path expression $\phi$ consists of all pairs of nodes (source and target nodes) that are connected by the path $\phi$ in the graph database.

$$ \begin{align*} [[l_e]]_D &= \{ (n, m) | n \xrightarrow{l_e} m \in E_D \wedge n, m \in N_D \wedge l_e \in L_E \} \\ [[\phi_1/\phi_2]]_D &= \{ (n, m) | \exists z \in N_D \wedge (n, z) \in [[\phi_1]]_D \wedge (z, m) \in [[\phi_2]]_D \} \\ [[\phi_1 \cup \phi_2]]_D &= [[\phi_1]]_D \cup [[\phi_2]]_D \\ [[\phi_1 \cap \phi_2]]_D &= [[\phi_1]]_D \cap [[\phi_2]]_D \\ [[\phi_1[\phi_2]]_D &= \{ (n, m) | \exists z \in N_D \wedge (n, m) \in [[\phi_1]]_D \wedge (m, z) \in [[\phi_2]]_D \} \\ [[[\phi_1]\phi_2]]_D &= \{ (n, m) | \exists z \in N_D \wedge (n, z) \in [[\phi_1]]_D \wedge (n, m) \in [[\phi_2]]_D \} \\ [[-l_e]]_D &= \{ (m, n) | (n, m) \in [[l_e]]_D \} \\ [[\phi^+]]_D &= \bigcup_{i \ge 1} [[\phi^i]]_D, \phi^k = (\phi / \dots / \phi) \text{ where } 1 \le k \le i. \end{align*} $$

<caption>Figure 5: Semantics of Tarski's algebra (adapted from Sharma et al. [2021]).</caption>

**Example 6** Given a graph schema (Fig. 1) and a graph database (Fig. 2) for the YAGO dataset, consider $\phi_1 = [owns]([isMarriedTo] livesIn)$ a path expression used to search for all married property owners living in cities. The path expression $\phi_1$ first searches for people living in cities using the *livesIn* edge label. After that, the branching operation on *isMarriedTo* edge label only serves as an existential node test to select married people. Finally, the branching operation on the *owns* edge label only selects married people living in cities and owning properties.

Based on the semantics in Fig. 5, the query returns nodes $\{(n_2, n_4)\}$ as the final result set, where node $n_2$ represents a person "John" who lives in a city named "Elerslie" (represented by node $n_4$). Furthermore, John is married and owns a property as shown in Fig. 2.

The formalism of CQT/UCQT expresses queries of two types: non-recursive graph queries (NQ) and recursive graph queries (RQ). Non-recursive graph queries are restricted CQT/UCQT that do not allow transitive closure, whereas recursive graph queries allow general path expressions with transitive closure.

The semantics of graph query language formalisms are broadly of two types (i) evaluation semantics and (ii) output semantics Angles et al. [2017], Sharma et al. [2021]. The formalism of CQT/UCQT uses homomorphism-based evaluation semantics for non-recursive graph queries (NQ), arbitrary path semantics for recursive graph queries (RQ) and set-based output semantics Sharma et al. [2021].

<footnote n="4">⁴Interested readers may refer Sharma et al. [2021] for detailed discussion on the semantics of CQT/UCQT</footnote>
## 3 Schema-Based Query Rewriting

We introduce a method that leverages schema information for query evaluation. Specifically the method rewrites a query so that structural schema information is injected in relevant part of the queries, namely in path expressions. As a preliminary step, we first transform path expressions into a form where redundancies are eliminated. We then present how schema information can be injected into path expressions.

**Preliminary path simplifications** The purpose of rewrite rules presented in Fig. 6 is to eliminate redundancies from path expressions in order to simplify queries. These rewrite rules are general in that they apply independently from any particular schema.

$$ (\phi^{+})^{+} \rightarrow \phi^{+} \quad (R1) \qquad \begin{aligned} & \phi_{1}^{+}[\phi_{2}^{+}] \rightarrow \phi_{1}^{+}[\phi_{2}] \quad (R2) & \phi_{1}[\phi_{2}/\phi_{3}] \rightarrow \phi_{1}[\phi_{2}[\phi_{3}]] \quad (R3) \\ & [\phi_{2}^{+}]\phi_{1}^{+} \rightarrow [\phi_{2}]\phi_{1}^{+} \quad (R4) & [\phi_{2}/\phi_{3}]\phi_{1} \rightarrow [\phi_{2}[\phi_{3}]]\phi_{1} \quad (R5) \end{aligned} $$

<caption>Figure 6: Rewrite rules for path expression simplification.</caption>

Rule R1 removes the redundant use of transitive closures.

Rules R2 and R4 simplify transitive closures within the branching operator since computing full transitive closure in branching expressions is not required Hellings [2018], Hellings et al. [2017]. Rules R3 and R5 turn path compositions into branching operations when possible, as also done in prior works Hellings et al. [2017], Hellings [2018], Hellings et al. [2020, 2023], Jaakkola and Kuusisto [2023]. Correctness of these rules follows immediately from the formal semantics of path expressions, and in particular from the existential semantics of the branching operator defined in Figure 5.

$$ \phi_{red} = ((((\text{owns}[\text{isMarriedTo}^{+}/\text{livesIn}/\text{dealsWith}^{+}]))/(\text{isLocatedIn}^{+})^{+})^{+})^{+} \\ \phi_{opt} = ((((\text{owns}[\text{isMarriedTo}[\text{livesIn}[\text{dealsWith}]]]/\text{isLocatedIn})^{+})^{+})^{+} $$

<caption>Figure 7: Application of path simplification rules.</caption>

**Example 7** In Fig 7, $\phi_{red}$ is a path expression with redundant plus operations and uses the concatenation operation within the branched path expressions. Rule R1 removes redundant plus operations, rule R2 removes plus operation inside branched expressions, and rule R3 replaces concatenation with branching operation in branched expressions. The optimised path expression is presented in Fig. 7 as the path expression $\phi_{opt}$.

### 3.1 Schema-based query analysis

Path expressions in Tarski's algebra do not contain any information about node labels. However, given a graph schema, it is possible to use the structure of a path expression to infer information about node labels. This information can then be used to rewrite the original query into a more precise query. The rewritten query generates fewer intermediate results in general, but is always equivalent to the original one in terms of the final result set, when the queried database conforms strictly to the schema.

**Example 8** In the graph database of the YAGO dataset shown in Fig. 2, suppose we need to search for a path such as owns/isLocatedIn. To answer this query, we only need to look for paths that start from a node labeled PERSON with an outgoing edge labeled owns to a node labeled PROPERTY, followed by an outgoing edge labeled isLocatedIn to nodes labeled CITY. This path traversal information can be inferred from the graph schema to formulate a precise path traversal query. When we do not use this schema information, the query considers all edges labeled isLocatedIn that start from nodes labeled PROPERTY, CITY, and REGION, respectively.

#### 3.1.1 Annotated path expressions

We first extend the grammar of Tarski's algebra to annotate concatenations with node labels: annotated path expressions $\psi$ follow the same grammar as described in Fig. 3 except that concatenation / can be replaced by its annotated version $l_n$ where $l_n$ is a node label. The expression $\psi_1/l_n\psi_2$ represents paths which follow $\psi_1$, arrive at a node labeled $l_n$, and go on from there following $\psi_2$. Formally, we define:

$$ [[\psi_1/l_n\psi_2]]_D = \{(n, m) \mid \exists z \in N_D \eta_D(z) = l_n \land (n, z) \in [[\psi_1]]_D \land (z, m) \in [[\psi_2]]_D\} $$

where $[\cdot]$ is defined as in Fig. 5 for the other cases.
<figure><img src="image_6.png" /><figcaption>Figure 8: Inference rules for the path expression-graph schema triple compatibility relation.</figcaption></figure>

Our idea here is that, when querying a database, replacing a plain path expression with a set of annotated ones can help reduce the size of intermediary results by keeping only the relevant data and thus improve efficiency. To determine how these annotations can be added, we use the schema.

### 3.1.2 Graph schema triples

Given a graph schema S as in Def. 1, we have that for each edge $e_i \in E_S$, there exists a pair of source and target nodes $\lambda_S(e_i) = (n_i, n_j)$. For each such edge, we consider the basic graph schema triple $t_i = (l_n, l_e, l'_n)$ constituted by the source label, the edge label and the target label, without any information about properties. Formally:

**Definition 5** The set of basic graph schema triples of S, $\mathcal{T}_b(S)$, is defined as follows:

$$ \mathcal{T}_b(S) = \{(l_n, l_e, l'_n) \mid \exists n_i, n_j \in N_S \ \exists e_i \in E_S \ \xi_S(e_i) = l_e \wedge \lambda_S(e_i) = (n_i, n_j) \wedge \eta_S(n_i) = l_n \wedge \eta_S(n_j) = l'_n\} $$

**Example 9** The graph schema as shown in Fig. 1 contains seven edges; therefore, the set associated with the schema contains seven basic graph schema triples $\mathcal{T}_b(S) = \{t_1, \dots, t_7\}$. For instance, the triple $t_1 = (\text{PERSON}, \text{owns}, \text{PROPERTY})$ has PERSON as source node label, PROPERTY as target node label and owns as an associated edge label. Similarly, the triple $t_2 = (\text{PROPERTY}, \text{isLocatedIn}, \text{CITY})$ has PROPERTY as source node label, CITY as target node label and isLocatedIn as an associated edge label.

Consider the path expression owns. The only triple containing this label is $t_1$. If we query a database conforming to our schema, we are able to know that this path expression will only return results conforming to $t_1$, in the sense that their source node will be labeled PERSON and their target node PROPERTY.

Basic graph schema triples correspond to path expressions consisting of a single edge label. More generally, we define graph schema triples as follows:

**Definition 6** A graph schema triple is a triple $(l_n, \psi, l'_n)$ where $l_n$ and $l'_n$ are node labels and $\psi$ an annotated path expression. For a graph schema triple $t$, we write $sc(t)$, $eT(t)$ and $tr(t)$ respectively the source node label, annotated path expression and target node label.

Given a plain path expression and a graph schema, we can compute a number of graph schema triples which are compatible with the path expression. For example, if we consider the path expression owns/isLocatedIn, considering that triples $t_1$ and $t_2$ from Exp. 9 share a common node label PROPERTY, we can build the triple $(\text{PERSON}, \text{owns}, \text{PROPERTY}, \text{isLocatedIn}, \text{CITY})$. In that example, it is the only triple compatible with the expression.

### 3.1.3 Path expression and triple compatibility

The set of triples compatible with a given path expression $\phi$ according to a schema S can be computed inductively from the sets of triples compatibles with the parts of $\phi$. We do this using inference rules and an auxiliary function.

**Definition 7 (path expression-triple compatibility)** Let $\phi$ be a path expression, S a graph schema and t a graph schema triple. The judgement $\vdash_S \phi : t$ means that under schema S, $\phi$ is compatible with t. It is defined inductively by the rules in Fig. 8, where $\mathcal{T}_S(\phi)$ represents the set of all triples compatible with $\phi$:

$$ \mathcal{T}_S(\phi) = \{t \mid \vdash_S \phi : t\} $$

The last rule, TPLUS, relies on the auxiliary function PIC, which works on the whole set of triples compatible with $\phi$ at once. This function, defined below, generates two kinds of triples: (a) triples where the path expression is $\phi^+$ itself, with all annotations dropped, and (b) triples where the path expression does not contain $+$, the transitive closure operator, anymore. The rationale is that if the schema information allows us to avoid the costly$^5$ transitive closure, we prefer to do so. However, we do not want to overcomplicate the expression if we cannot avoid the transitive closure operation.

<footnote>$^5$In terms of time and computing resources required for querying graph databases Hellings [2018], Hellings et al. [2023].</footnote>
To determine when transitive closure can be avoided, we associate to the set $\mathcal{T}_S(\phi)$ the directed graph whose vertices are the node labels and whose edges are the triples. Any path of length $n$ in that graph yields a triple compatible with $\phi^n$ (as we can infer by repeated application of TCONCAT). Since the meaning of $\phi^+$ is the union of the $\phi^n$ for all $n \ge 1$, the set of all (non-empty) paths in the graph corresponds to triples compatible with $\phi^+$. If this set is finite, we actually define it as the set of triples compatible with $\phi^+$. If it is infinite, then transitive closure cannot be removed. Since the existence of infinitely many paths is equivalent to the presence of cycles in the graph, we propose the following algorithm for computing PIC:

**Definition 8 (Plus Compatibility)** PIC$(\phi, T)$ is the set of triples resulting of the following:

1. Let G be the directed graph associated with $T$;

2. Let K be the set of vertices of G which are part of a cycle;

3. Let R be the initially empty result set;

4. For each path $p$ from A to B without cycles in G:

* if any of the vertices of $p$ (including A and B) is in K, then add to R the triple $(A, \phi^+, B)$

* else

- let $\psi$ be the annotated path expression resulting of concatenating all triples in $p$;

- add to R the triple $(A, \psi, B)$

5. Return R.

**Example 10** Consider the path expression $\phi_4 = \text{livesIn}/\text{isLocatedIn}^+/\text{dealsWith}^+$, and let S be the schema of Fig. 1. Table 1 shows the sets of triples associated to $\phi_4$ and its three sub-terms $\phi_1 = \text{livesIn}(\text{lvIn})$, $\phi_2 = \text{isLocatedIn}^+(\text{isL}^+)$ and $\phi_3 = \text{dealsWith}^+(\text{dw}^+)$.

For $\phi_3$, we have $\mathcal{T}_S(\text{dealsWith}) = \{(\text{COUNTRY}, \text{dealsWith}, \text{COUNTRY})\}$. The graph associated to that singleton set has one vertex and one edge which forms a cycle, therefore the transitive closure cannot be eliminated: we have $\mathcal{T}_S(\text{dealsWith}^+) = (\text{COUNTRY}, \text{dealsWith}^+, \text{COUNTRY})$.

For $\phi_2$, the set $\mathcal{T}_S(\text{isLocatedIn})$ contains 3 triples; the associated graph has 4 vertices (PROPERTY, CITY, REGION and COUNTRY) and 3 edges corresponding to the 3 triples. It contains no cycle, therefore $\mathcal{T}_S(\text{isLocatedIn}^+)$ contains 6 triples, corresponding to the 6 non-empty paths in the graph.

Notice that, while TPLUS can yield many triples when it is possible to remove the transitive closure, TCONCAT on the other hand can drastically reduce their number, so that in the end there is only one triple compatible with $\phi_4$.

<table><caption>Table 1: Application of the inference rules of Fig. 8 to the term $\phi_4 = \text{livesIn}/\text{isLocatedIn}^+/\text{dealsWith}^+$.</caption><thead><tr><th>TERM</th><th>TRIPLES</th><th>RULE</th></tr></thead><tbody><tr><td>lvIn</td><td>(PER, lvIn, CITY)</td><td>TBASIC</td></tr><tr><td>isL<sup>+</sup></td><td>(PRO, isL, CITY), (CITY, isL, REG), (REG, isL, CUN),<br>(PRO, isL/cITYisL, REG), (PRO, isL/cITYisL/REGisL, CUN),<br>(CITY, isL/REGisL, CUN)</td><td>TPLUS</td></tr><tr><td>dw<sup>+</sup></td><td>(CUN, dw<sup>+</sup>, CUN)</td><td>TPLUS</td></tr><tr><td>lvIn/isL<sup>+</sup></td><td>(PER, lvIn/cITYisL, REG), (PER, lvIn/cITYisL/REGisL, CUN)</td><td>TCONCAT</td></tr><tr><td>lvIn/isL<sup>+</sup>/dw<sup>+</sup></td><td>(PER, lvIn/cITYisL/REGisL/cUNdw<sup>+</sup>, CUN)</td><td>TCONCAT</td></tr></tbody></table>

isL=isLocatedIn, lvIn=livesIn, REG=REGION
dw=dealsWith, PER=PERSON, PRO=PROPERTY,
CUN=COUNTRY

### 3.1.4 Properties of the compatibility relation

The path expression-triple compatibility relation is defined relative to a schema. Consider now a database conforming to this schema. The compatibility relation enjoys the following properties relative to any such database:
* Soundness, meaning that whenever our path expression $\phi$ is compatible with some triple $(l_n, \psi, l'_n)$, then all pairs of a node labeled $l_n$ and a node labeled $l'_n$ linked, in the database, by a path conforming to $\psi$, are part of the result of $\phi$;

* Completeness, meaning that whenever $\phi$ returns a pair of a node labeled $l_n$ and a node labeled $l'_n$, there exists a triple $(l_n, \psi, l'_n)$, compatible with $\phi$, such that these nodes are linked, in the database, by a path conforming to $\psi$.

These two properties make the initial path expression semantically equivalent to its set of compatible triples, so long as we only consider databases conforming to the schema. Formally:

**Theorem 1** Let S be a graph schema, let D be a graph database conforming to S via the schema-database mapping $SD$, and let $\phi$ be a path expression.

**SOUNDNESS.** Assume $\vdash_S \phi : (l_n, \psi, l'_n)$ holds for some triple $(l_n, \psi, l'_n)$. Let $(s, t) \in [[\psi]]_D$ such that $\eta_D(s) = l_n$ and $\eta_D(t) = l'_n$. Then $(s, t) \in [[\phi]]_D$.

**COMPLETENESS.** Let $(s, t) \in [[\phi]]_D$. Then there exists $\psi$ such that $(s, t) \in [[\psi]]_D$ and $\vdash_S \phi : (\eta_D(s), \psi, \eta_D(t))$.

**Proof 1** Both properties are proved by structural induction on $\phi$. The base cases, where $\phi$ is a single edge label, are a direct consequence of the consistency between D and S (def. 3) and of the definition of basic graph schema triples (def. 5). The inductive cases other than transitive closure are straightforward since the inference rules of Fig. 8 follow exactly the structure of the semantics defined in Fig. 5. Finally, we detail the case of transitive closure:

**Soundness:** assume the property holds for $\phi$. Let $(l_n, \psi, l'_n) \in \text{PIC}(\phi, \mathcal{T}_S(\phi))$ and let $(s, t) \in [[\psi]]_D$ such that $\eta_D(s) = l_n$ and $\eta_D(t) = l'_n$. We have two cases: if $\psi = \phi^+$ then the result is immediate. Otherwise, according to Def. 8, it means that there exists a sequence of triples $t_1, \dots, t_n \in \mathcal{T}_S(\phi)$ such that: $\text{sc}(t_1) = l_n$, $\text{tr}(t_i) = \text{sc}(t_{i+1})$ for all $i < n$, $\text{tr}(t_n) = l'_n$, and $\psi$ is the concatenation of $t_1 \dots t_n$ (i. e. $\psi = \text{eT}(t_1)/_{\text{tr}(t_1)} \text{eT}(t_2)/_{\text{tr}(t_2)} \dots /_{\text{tr}(t_{n-1})} \text{eT}(t_n)$). Since $(s, t)$ is in $[[\psi]]_D$, it means that there is a path in D from s to t which conforms to $\psi$. Since $\psi$ is the concatenation of $t_1 \dots t_n$, that path has to be the concatenation of n sub-paths conforming respectively to the triples $t_1 \dots t_n$. Since each of those triples is compatible with $\phi$, we can use the induction hypothesis for each of them and see that the source-target pair for each one is in $[[\phi]]_D$. It results that $(s, t)$ is in $[[\phi^n]]_D$, and therefore in $[[\phi^+]]_D$.

**Completeness:** assume the property holds for $\phi$. Let $(s, t) \in [[\phi^+]]_D$. By definition, there exists $k \ge 1$ such that $(s, t) \in [[\phi^k]]_D$. This means that there is a sequence $n_0 \dots n_k$ of nodes in D with $n_0 = s$ and $n_k = t$ such that we have $(n_{i-1}, n_i) \in [[\phi]]_D$ for all $i$ between 1 and $k$. By induction hypothesis, for each $i$ there is a triple $t_i = (\eta_D(n_{i-1}), \psi_i, \eta_D(n_i))$ such that $\vdash_S \phi : t_i$ and $(n_{i-1}, n_i) \in [[\psi_i]]_D$. Let G and K be the graph and set of vertices defined in Def. 8. The sequence $t_1 \dots t_k$ forms a path from $\eta_D(s)$ to $\eta_D(t)$ in G. If this path contains no cycle, then we see from step (4) of Def. 8 that $\text{PIC}(\phi, \mathcal{T}_S(\phi))$ contains a triple $(\eta_D(s), \psi, \eta_D(t))$ with $\psi$ equal either to $\phi^+$ or to the concatenation of $\psi_1 \dots \psi_k$. In both cases, we have $(s, t) \in [[\psi]]_D$. If the path $t_1 \dots t_k$ does contain a cycle, say $\eta_D(n_i) = \eta_D(n_j)$ with $j > i$, then the sequence $t_1 \dots t_i, t_{j+1} \dots t_k$ is also a path in G without that cycle, and we have $\eta_D(n_j) \in K$ since $t_{i+1} \dots t_j$ is a cycle in G. If that path still contains a cycle, we can reiterate this 'shortcutting' until there are none left, and obtain a path from $\eta_D(s)$ to $\eta_D(t)$ without cycles and containing at least one vertex in K. Therefore, $\text{PIC}(\phi, \mathcal{T}_S(\phi))$ must contain the triple $(\eta_D(s), \phi^+, \eta_D(t))$, which allows us to conclude since we already have $(s, t) \in [[\phi^+]]_D$.

## 3.2 From triples to rewritten query

### 3.2.1 Merging triples

The compatibility relation allows us to obtain, from a path expression $\phi$ and a schema S, a set $\mathcal{T}_S(\phi)$ of triples which represent all the paths, annotated with node labels, which can possibly contribute to the query result. In principle, we could then convert each individual triple from $\mathcal{T}_S(\phi)$ into a (very specific) query of its own, combine all those queries with a union and obtain a query which, provided the database conforms to the schema, is equivalent to the initial path expression, while avoiding the computation of intermediary results we know from the schema are useless. However, when several triples have the same underlying path expression and differ only by the node labels, it would not be efficient to compute their results separately and do the union afterwards. So, we merge such triples by replacing all single node labels with sets of possible node labels.

**Definition 9** Let T be a set of graph schema triples with the same underlying path expression $\phi$. The merged triple of T is the triple $M(T) = (L_1, \Psi, L_2)$ where $L_1 = \{l \mid (l, \_, \_) \in T\}$, $L_2 = \{l \mid (\_, \_, l) \in T\}$, and $\Psi$ is the path
<figure><img src="image_7.png" /><figcaption>Figure 9: Translation of annotated path expressions into CQTs.</figcaption></figure>

expression $\phi$ where each concatenation step is annotated with the set of all labels annotating the same concatenation step in $\{\psi | (\_, \psi, \_) \in T\}$.

**Example 11** Consider an initial path expression $\phi_1 = a^+/b/d$. Suppose the set of triples $\mathcal{T}_S(\phi)$ contains the following: $(m, a^+/_nb/l/d, p)$ and $(m, a^+/_qb/r/d, l)$. These triples can be merged into $(\{m\}, a^+/_{n,q}\}b/_{l,r}\{d, \{p, l\}\})$.

From the set $\mathcal{T}_S(\phi)$, we compute the set of merged triples of $\phi$, $M_S(\phi)$, by: 1. partitioning $\mathcal{T}_S(\phi)$ in subsets having the same underlying path expression, and 2. taking the merged triple of each subset. Note that in many cases, this will result in one single merged triple, whose underlying path expression is $\phi$ itself, but it is not the case whenever $\phi$ contains a union, or a transitive closure which could be removed.

### 3.2.2 Removing redundant annotations

In some cases, the source and target node labels assigned to a specific edge label in an annotated path expression are the only source and target node labels associated with that same edge label in the graph schema. In such a case, the annotation would not be useful for minimizing intermediate result size since the whole dataset already conforms to the annotation: on the contrary, it would introduce a useless filtering step. Therefore, as a last step before constructing the rewritten query, we detect and remove such annotations.

**Example 12** Let us assume that in a graph schema, source and target nodes associated with edges labeled as d and b are l and r respectively. The node labels l and r can be eliminated from the annotated path expression in Ex. 11, resulting in $(\{m\}, a^+/_{n,q}\}b/d, \{p, l\})$.

Note that, after merging triples and removing redundant annotations, some queries may revert to the initial path expression. This means that the schema did not contain information which would allow optimizing the query.

### 3.2.3 Rewritten queries

We now want to translate merged triples into CQT queries. For this, we first observe that the annotated path expressions $\psi$ generated by the rules of Fig. 8 and Def. 8 always obey some syntactic restrictions, namely: no annotations appear under the transitive closure operator, and the union operator never appears, except possibly under transitive closure. Furthermore, the reverse operation only occurs in front of edge labels. These observations allow us to reduce the number of cases in the translation: $\psi$ is either a plain path expression, a concatenation, a branching or a conjunction.

**Definition 10 (CQT of a merged triple)** The translation is defined using a function $Q(\alpha, \beta, \psi)$, where $\alpha$ and $\beta$ are CQT variables and $\psi$ an annotated path expression, which returns a triple $(B, A, \text{Rel})$ corresponding to a CQT representing $\psi$ with $H = \{\alpha, \beta\}$ (see Def. 4). This function is defined in Fig. 9.

For a given merged triple $t = (L, \psi, L')$, we then define the associated CQT as $C(t) = (\{\alpha, \beta\}, B, A \cup \{\eta_A(\alpha) \in L, \eta_A(\beta) \in L'\}, \text{Rel})$ where $(B, A, \text{Rel}) = Q(\alpha, \beta, \psi)$.

This allows us to associate to any path expression, given a schema S, a UCQT representing the query enriched with schema information:
**Definition 11 (schema-enriched query)** Given a path expression $\phi$ and a schema S, the schema-enriched query of $\phi$, $R_S(\phi)$, is the following UCQT: $R_S(\phi) = \{\alpha, \beta\} \leftarrow \{\bigcup_{t \in M_S \phi} C(t)\}$

Thanks to Theorem 1, we have that $\phi$ is equivalent to $R_S(\phi)$ on any database conforming strictly to S.

**Example 13** Consider the path expression $\phi_4 = \text{lvIn}/\text{isL}^+/\text{dw}^+$ of Example 10. We saw that our inference system derives exactly one triple compatible with it in schema S: $(\text{PER}, \text{lvIn}/\text{CITY}\text{isL}/\text{REG}\text{isL}/\text{CUN}\text{dw}^+, \text{CUN})$. Then, since there is only one triple, there is nothing to merge. We then remove redundant labels: the schema S of Fig. 1 only allows livesIn from PERSON to CITY and dealsWith from COUNTRY to COUNTRY, so the final unique merged triple is: $(\emptyset, \text{lvIn}/\text{isL}/\{\text{REG}\}\text{isL}/\text{dw}^+, \emptyset)$. Therefore, we can rewrite this expression into:

$$R_S(\phi_4) = \{\alpha, \beta | \exists \gamma (\alpha, \text{lvIn}/\text{isL}, \gamma) \wedge (\gamma, \text{isL}/\text{dw}^+, \beta) \wedge \eta_A(\gamma) \in \{\text{REG}\}$$

We can notice that the rewritten query allows the database engine to avoid computing the transitive closure of isL at all.

# 4 System Implementation

We analyse the performance of queries augmented with schema information. The approach has been implemented as a system whose architecture is depicted in Figure 10. Our system architecture consists of three main modules (i) Rewriter, (ii) Translator and (iii) Backend.

<figure><img src="image_8.png" /><figcaption>Figure 10: System architecture.</figcaption></figure>

**Rewriter** The rewriter module consists of three components Preliminary Path Simplifier (PPS), Schema-based Query Rewriter (SQ-Rewriter) and Schema-based Query Merge (SQ-Merge). The PPS component takes a UCQT query as input, then applies the preliminary path simplification rules presented in Fig. 6 and produces a simplified UCQT query $q$ as output. The SQ-Rewriter component implements the query rewrites leveraging schema information presented in Sec. 3 for the UCQT query language (defined in Section 2.4). It takes a UCQT query $q$ and a graph schema $s$ described in the graph schema formalism (using Def. 1) as input and generates a schema-aware UCQT query $q'$ as output. The SQ-Merge component uses the graph schema to remove redundant annotations by merging path expressions as described in Sec. 3.2. It takes a schema-aware UCQT query $q'$ as input and produces merged UCQT query $q''$ as output.

**Translator** The translator module compiles an UCQT query into a graph query that can be executed by a graph database management system (GDBMS) and a recursive SQL query that can be executed by a relational database management system (RDBMS). The translator module uses the UCQT2GP component to convert the UCQT query into a union of
graph patterns, which is then transformed into a Cypher query by the GP2Cypher component. Due to the limited expressive power offered by Cypher Sharma et al. [2021], only UC2RPQ graph patterns (not UCQT) can be converted into Cypher. Since we use the UCQT graph query language formalism to express graph patterns, our approach extends beyond Cypher: it can also be applied to other practical graph query languages such as SPARQL and PGQL Sharma et al. [2021]. If one starts from a query written in any of these formalisms, it can easily be translated into UCQT before being given as input to our system.

The translator module uses the UCQT2RRA component to translate UCQT query into a term in recursive relational algebra (RRA), and that is further optimised using the μ-RA system based on the rewritings proposed in Jachiet et al. [2020]. Compared to the path expressions considered in Jachiet et al. [2020], we consider additional rules for translating conjunction and branching operations as shown in Tab. 2.

<table><caption>Table 2: Conjunction and branching translation to Recursive Relational Algebra.</caption><thead><tr><th>Path expression</th><th>Recursive Relational Algebra term</th></tr></thead><tbody><tr><td>(|φ<sub>1</sub> ∩ φ<sub>2</sub>|) =</td><td>{ρ<sub>n</sub><sup>Tr</sup>(ρ<sub>m</sub><sup>Sr</sup>(ρ<sub>Tr</sub><sup>n</sup>(ρ<sub>Sr</sub><sup>m</sup>(φ<sub>1</sub>))) | ϕ<sub>1</sub> ∈ (|φ<sub>1</sub>|) ∧ ϕ<sub>2</sub> ∈ (|φ<sub>2</sub>|)}</td></tr><tr><td>(|φ<sub>1</sub>[φ<sub>2</sub>|) =</td><td>{ρ<sub>m</sub><sup>Tr</sup>(ρ<sub>Tr</sub><sup>m</sup>(φ<sub>1</sub>) | ϕ<sub>1</sub> ∈ (|φ<sub>1</sub>|) ∧ ϕ<sub>2</sub> ∈ (|φ<sub>2</sub>|))}</td></tr><tr><td>([φ<sub>1</sub> | φ<sub>2</sub>|) =</td><td>{ρ<sub>m</sub><sup>Sr</sup>(ρ<sub>Sr</sub><sup>m</sup>(π<sub>Sr</sub>(φ<sub>1</sub>))) | ϕ<sub>1</sub> ∈ (|φ<sub>1</sub>|) ∧ ϕ<sub>2</sub> ∈ (|φ<sub>2</sub>|)}</td></tr></tbody></table>

Our system architecture is modular, allowing for components such as UCQT2RRA (currently based on the μ-RA system) to be replaced with other systems such as α-extended RA Agrawal [1988], β-RA Gomes-Jr et al. [2015], WAVEGUIDE Yakovets et al. [2015], AVANTGRAPH Leeuwen et al. [2022] and Datalog based RRA systems Aref et al. [2015], Leone et al. [2006], Urbani et al. [2016]. However, as discussed in Jachiet et al. [2020], Fejza et al. [2023], the μ-RA system is superior in query optimisation capabilities.

The optimised RRA term is transformed into a concrete recursive SQL syntax for each RDBMS using the RRA2SQL component where the fixpoints are translated into recursive view statements<fnref n="6" />.

**Backend** To evaluate our approach, we conducted experiments on one GDBMS and three RDBMS. Specifically, we used Neo4j, PostgreSQL, MySQL, and SQLite. Graph databases can be directly stored as property graphs on Neo4j. However, in the relational data model, we represent the nodes and edges of the graph database as relational tables.

For instance, in the YAGO dataset's graph representation (as shown in Fig. 2), there are four graph edges labeled `isLocatedIn` connecting different pairs of nodes labeled as (PROPERTY, CITY), (CITY, REGION), and (REGION, COUNTRY) respectively. In the relational representation of the YAGO dataset, a table is created for each type of edge label, each with at least two columns `Sr` and `Tr`, which are foreign keys pointing to the source and target nodes. Similarly, a table is created for each type of node label, with a specific column `Sr` serving as a primary key and potentially many other columns for properties. Fig. 11 shows two node tables (PROPERTY, CITY) and two edge tables (owns, isLocatedIn). Overall, each row in node or edge tables represents a node or an edge of the graph database.

<figure><img src="image_9.png" /><figcaption>Figure 11: Relational representation of nodes and edges.</figcaption></figure>

# 5 Experiments

We assess the impact on performance of the schema-based approach experimentally with a complete prototype implementation. Concretely, we try to answer the following questions: (i) Does the schema-based approach improve the performance of query evaluation on real and synthetic benchmark datasets? (ii) How does the approach behave on different database management systems?

<footnote n="6">⁶MySQL: CREATE OR REPLACE VIEW WITH RECURSIVE, SQLite: CREATE VIEW WITH RECURSIVE PostgreSQL: CREATE TEMPORARY RECURSIVE VIEW</footnote>
# 5.1 Experimental Setup

## 5.1.1 Datasets

We consider datasets of different nature:

* YAGO Yago [2019], which is a real knowledge graph. We use a preprocessed and cleaned version of the real-world dataset YAGO2s Yago [2019] in which only nodes with unique identifiers are present. We split the set of RDF triples into multiple edge relations (tables), one for each predicate name. We create a node relation (table) for each node class. The dataset conforms to the YAGO schema constructed for this study. In other terms, the constructed schema does not exclude any existing triples from this YAGO dataset.

* the Social Network Benchmark (SNB) interactive workload from the Linked Data Benchmark Council (LDBC) Erling et al. [2015] which is a synthetic reference benchmark for property graphs. Specifically, we used the LDBC-SNB dataset in CSV format provided from Szárnyas [2023].

<table><caption>Table 3: Summary of dataset characteristics.</caption><thead><tr><th>Name</th><th>SF</th><th>#NR</th><th>#ER</th><th>#Nodes</th><th>#Edges</th><th>Size</th></tr></thead><tbody><tr><td rowspan="3">YAGO</td><td>N/A</td><td>7</td><td>88</td><td>98,582</td><td>150,391,592</td><td>26 GB</td></tr><tr><td>0.1</td><td></td><td></td><td>416,311</td><td>2,034,983</td><td>0.3 GB</td></tr><tr><td>0.3</td><td></td><td></td><td>1,154,108</td><td>6,235,570</td><td>0.9 GB</td></tr><tr><td rowspan="6">LDBC-SNB</td><td>1</td><td></td><td></td><td>3,966,203</td><td>23,056,025</td><td>3.3 GB</td></tr><tr><td>3</td><td>8</td><td>16</td><td>11,407,480</td><td>69,482,982</td><td>9.9 GB</td></tr><tr><td>10</td><td></td><td></td><td>36,485,994</td><td>231,532,873</td><td>33 GB</td></tr><tr><td>30</td><td></td><td></td><td>88,789,972</td><td>541,279,759</td><td>82 GB</td></tr></tbody></table>

Tab. 3 summarises the characteristics of the pre-processed datasets. The YAGO dataset has 98k nodes and 150M edges, with 7 node relations and 88 edge relations. LDBC-SNB uses 8 node relations (NR) and 16 edge relations (ER). LDBC-SNB has property graphs of varying sizes measured by scale factors (SF), ranging from 0.1 to 30. We consider 6 of them shown in Tab. 3. LDBC property graph with SF 0.1 has 416k nodes and 2M edges, SF 30 has 88M nodes and 541M edges <fnref n="7" />. The size column in Tab. 3 shows the size on disk of the PostgreSQL database.

## 5.1.2 Schemas

YAGO does not have a graph schema, therefore we developed a basic one, as illustrated in Fig. 1 <fnref n="8" />, inspired by the SHACL semantic constraints from Suchanek et al. [2023] that specify the disjointness of certain classes. The LDBC-SNB dataset comes with a pre-defined property graph schema Erling et al. [2015].

## 5.1.3 Queries

We selected 30 queries from the LDBC-SNB workload Erling et al. [2015], divided into two categories: non-recursive graph queries (NQ) and recursive graph queries (RQ). As shown in Tab. 4 out of the 30 queries, 12 are non-recursive, and 18 are recursive. Out of the 30 queries of Tab. 4, 22 are third-party queries. Queries labeled as (IC and IS) are extracted from the LDBC interactive workload, while queries labeled as (BI) are from the business intelligence workload, and queries labeled as (LSQB) are extracted from the large-scale subgraph query benchmark Mhedhbi et al. [2021]. Finally, we proposed queries labeled as (Y) as complementary queries, inspired by YAGO-style queries found in Jachiet et al. [2020].

We consider 18 queries on the YAGO dataset. These queries were previously used in studies such as Abul-Basher et al. [2017], Gubichev et al. [2013], Yakovets et al. [2015]. All the queries selected for the YAGO dataset are recursive graph queries.

## 5.1.4 Baseline

All experiments conducted using the schema-based approach are systematically compared to the initial (non-schema enriched) query considered as a baseline.

<footnote n="7">⁷LDBC-SNB contains large property graphs with scale factors 100, 1000</footnote>

<footnote n="8">⁸Due to space constraints, we only provide a small schema for YAGO in Fig. 1. The complete schema is available as supplementary material (see Sec. 5.1.7).</footnote>
<table><caption>Table 4: Queries for the LDBC-SNB Dataset.</caption><thead><tr><th>Query Label</th><th>Path expressions as UCQT queries</th><th>Query Type</th></tr></thead><tbody><tr><td>IC1</td><td>x1, x2 &larr; (x1, knows1..3/(isL &amp; (workAt &amp; studyAt)/isL), x2)</td><td>NQ</td></tr><tr><td>IC2</td><td>x1, x2 &larr; (x1, knows/-hasC, x2)</td><td>NQ</td></tr><tr><td>IC6</td><td>x1, x2 &larr; (x1, knows1..2/(-hasC[hasT])[hasT], x2)</td><td>NQ</td></tr><tr><td>IC7</td><td>x1, x2 &larr; (x1, (-hasC/-likes) &amp; ((-hasC/-likes) &amp; knows), x2)</td><td>NQ</td></tr><tr><td>IC8</td><td>x1, x2 &larr; (x1, -hasC/-replyOf/hasC, x2)</td><td>NQ</td></tr><tr><td>IC9</td><td>x1, x2 &larr; (x1, knows1..2/-hasC, x2)</td><td>NQ</td></tr><tr><td>IC11</td><td>x1, x2 &larr; (x1, knows1..2/workAt/isL, x2)</td><td>NQ</td></tr><tr><td>IC12</td><td>x1, x2 &larr; (x1, knows/-hasC/replyOf/hasT/hasTY/isSubC+, x2)</td><td>RQ</td></tr><tr><td>IC13</td><td>x1, x2 &larr; (x1, knows+, x2)</td><td>RQ</td></tr><tr><td>IC14</td><td>x1, x2 &larr; (x1, (knows &amp; (-hasC/replyOf/hasC))+, x2)</td><td>RQ</td></tr><tr><td>Y1</td><td>x1, x2 &larr; (x1, knows+/studyAt/isL+/isP+, x2)</td><td>RQ</td></tr><tr><td>Y2</td><td>x1, x2 &larr; (x1, likes/hasC/knows+/isL+, x2)</td><td>RQ</td></tr><tr><td>Y3</td><td>x1, x2 &larr; (x1, likes/replyOf+/isL+/isP+, x2)</td><td>RQ</td></tr><tr><td>Y4</td><td>x1, x2 &larr; (x1, hasM/(studyAt &amp; workAt)/isL+/isP+, x2)</td><td>RQ</td></tr><tr><td>Y5</td><td>x1, x2 &larr; (x1, -hasM/([cof]hasT)/hasTY/isSubC+, x2)</td><td>RQ</td></tr><tr><td>Y6</td><td>x1, x2 &larr; (x1, replyOf+/isL+/isP+, x2)</td><td>RQ</td></tr><tr><td>Y7</td><td>x1, x2 &larr; (x1, hasMod/hasI/hasTY/isSubC+, x2)</td><td>RQ</td></tr><tr><td>Y8</td><td>x1, x2 &larr; (x1, ([cof/hasC]hasM)/isL/isP+, x2)</td><td>RQ</td></tr><tr><td>IS2</td><td>x1, x2 &larr; (x1, -hasC/replyOf/hasC, x2)</td><td>RQ</td></tr><tr><td>IS6</td><td>x1, x2 &larr; (x1, replyOf+/-cof/hasM, x2)</td><td>RQ</td></tr><tr><td>IS7</td><td>x1, x2 &larr; (x1, (-hasC/replyOf/hasC) &amp; ((-hasC/replyOf/hasC) &amp; knows), x2)</td><td>NQ</td></tr><tr><td>BI11</td><td>x1, x2 &larr; (x1, ([[isL/isP]knows][isL/isP]) &amp; (knows/([isL/isP]knows))), x2)</td><td>NQ</td></tr><tr><td>BI10</td><td>x1, x2 &larr; (x1, (knows+[isL/isP])/(-hasC[hasT])/hasT/hasTY, x2)</td><td>RQ</td></tr><tr><td>BI3</td><td>x1, x2 &larr; (x1, -isP/-isL/-hasMod/ cof/-replyOf+/hasT/hasTY, x2)</td><td>RQ</td></tr><tr><td>BI9</td><td>x1, x2 &larr; (x1, replyOf+/hasC, x2)</td><td>RQ</td></tr><tr><td>BI20</td><td>x1, x2 &larr; (x1, (knows &amp; (studyAt/-studyAt))+, x2)</td><td>RQ</td></tr><tr><td>LSQB1</td><td>x1, x2 &larr; (x1, -isP/-isL/-hasM/ cof/-replyOf/hasT/hasTY, x2)</td><td>RQ</td></tr><tr><td>LSQB4</td><td>x1, x2 &larr; (x1, ([likes[hasT]]=-replyOf])/hasC, x2)</td><td>NQ</td></tr><tr><td>LSQB5</td><td>x1, x2 &larr; (x1, -hasT/-replyOf/hasT, x2)</td><td>NQ</td></tr><tr><td>LSQB6</td><td>x1, x2 &larr; (x1, knows/knows/hasI, x2)</td><td>NQ</td></tr></tbody></table>

isL=isLocatedIn, hasT=hasTag, isP=isPartOf, isSubC=isSubClassOf, hasI=hasInterest, hasTY=hasType, coF=containerOf, hasMod=hasModerator, hasC=hasCreator, hasM=hasMember

### 5.1.5 Measures and timeout

We set a 30-minute computation time limit for each query to evaluate schema-based and baseline approaches. If the computation exceeded 30 minutes, we stopped the process and deemed the query infeasible with the given approach, allowing us to measure the system's performance in a reasonable time frame. Each reported query execution time corresponds to the average of 5 runs.

In experiments, some queries result in timeouts at a given scale factor but not with smaller dataset sizes. The primary focus is to measure the relative performance improvements brought by the proposed optimisations rather than conducting pure performance comparisons between systems. In particular, we want to check if such optimisations are capable of turning infeasible queries to feasible ones at some scale factors on the various systems.

### 5.1.6 Hardware and software setup

All experiments have been conducted by using a Macbook Air laptop with Apple M2 chip, 8 cores (4 performance and 4 efficiency), 24 GB of RAM and 1 TB hard disk. The main backend used for evaluation is PostgreSQL 15.4. We also provide performance comparisons with the graph database system Neo4j 5.21.2 community edition. We do not report on comparisons with MySQL and SQLite because both systems are significantly less efficient than PostgreSQL in executing queries for large LDBC datasets. No queries could be successfully executed on MySQL and SQLite beyond scale factor 1.

### 5.1.7 Availability

The datasets, schemas, initial and rewritten queries are available<fnref n="9" />.

## 5.2 Query feasibility

For the YAGO dataset, 17 queries out of 18 did run successfully with both approaches within the allowed timeout period. Only one query (query 7) timed out. Furthermore, during the process of schema enrichment and query factorization,

<footnote n="9">⁹ https://gitlab.inria.fr/tyrex-public/schema-graph-query.git</footnote>
query 7 automatically reverted to the initial query form since no schema-based optimization was found. The LDBC dataset consists of ten queries (IC2, IC6, IC7, IC9, IC13, Y7, BI11, BI9, BI20, and LSQB6) that returned to their initial path expressions after going through the schema enrichment and query factorization process. Among these, six are non-recursive, while the remaining four are recursive.

These queries highlight an advantage of our approach, which is to automatically avoid schema enrichment when it does not detect any significant performance gain. This allows us to prevent query performance degradation. For example, query 7 for YAGO and ten LDBC queries did not benefit from schema enrichment, but their performance was not made worse.

Out of ten LDBC queries, only three queries Y7, BI11 and BI20 could be executed on all six scale factors. Tab. 5 summarizes the number and percentage of successful runs for the various scale factors (data size) on the LDBC dataset.

<table><caption>Table 5: LDBC query feasibility across six scale factors (SF).</caption><thead><tr><th rowspan="2">SF</th><th colspan="4">Recursive</th><th colspan="4">Non Recursive</th></tr><tr><th>Count</th><th>Baseline Percentage</th><th>Count</th><th>Schema Percentage</th><th>Count</th><th>Baseline Percentage</th><th>Count</th><th>Schema Percentage</th></tr></thead><tbody><tr><td>0.1</td><td>18</td><td>100</td><td>18</td><td>100</td><td>12</td><td>100</td><td>12</td><td>100</td></tr><tr><td>0.3</td><td>16</td><td>88.9</td><td>18</td><td>100</td><td>9</td><td>75</td><td>9</td><td>75</td></tr><tr><td>1</td><td>14</td><td>77.8</td><td>15</td><td>83.3</td><td>9</td><td>75</td><td>9</td><td>75</td></tr><tr><td>3</td><td>11</td><td>61.1</td><td>13</td><td>72.2</td><td>7</td><td>58.3</td><td>7</td><td>58.3</td></tr><tr><td>10</td><td>10</td><td>55.6</td><td>11</td><td>61.1</td><td>7</td><td>58.3</td><td>7</td><td>58.3</td></tr><tr><td>30</td><td>5</td><td>27.8</td><td>7</td><td>38.9</td><td>4</td><td>33.3</td><td>4</td><td>33.3</td></tr></tbody></table>

As shown in Tab. 5, the percentage of queries that did timeout increase with the scale factor for both approaches. For scale factor 30, the baseline approach could only execute 27.8% of recursive graph queries, whereas the schema-based approach could execute 38.9% recursive graph queries. Both approaches successfully executed the same number of non-recursive graph queries across all scale factors. Using the schema-based approach, more recursive graph queries could be executed compared to the baseline across all scale factors, as shown in Tab. 5.

We now evaluate the impact of the proposed approach on performance.

## 5.3 Performance results on YAGO

<figure><img src="image_10.png" /><figcaption>Figure 12: Query runtime for YAGO dataset.</figcaption></figure>

Fig. 12 presents the evaluation times for the schema-based approach compared to the baseline. We observe that the schema-based approach outperforms the baseline for all YAGO queries; on average, YAGO queries run 6.1 times faster using the schema-based approach compared to the baseline. Notice that the time scale is logarithmic.

As mentioned in Sec. 3, the schema-enrichment approach enables the removal of the transitive closure operation from certain queries. Tab. 6 illustrates the replacement of the sub-path expression `isLocatedIn` by fixed-length paths in YAGO queries.
<table><caption>Table 6: Statistics on generated fixed-length paths</caption><thead><tr><th>YAGO Queries</th><th>#Paths</th><th>Min</th><th>Avg</th><th>Max</th></tr></thead><tbody><tr><td>1,2,3,4,5</td><td>1</td><td>2</td><td>2</td><td>2</td></tr><tr><td>12</td><td>2</td><td>1</td><td>1.5</td><td>2</td></tr><tr><td>6,8,10,11,14,15,16,17,18</td><td>3</td><td>1</td><td>2</td><td>3</td></tr><tr><td>9</td><td>8</td><td>1</td><td>2.5</td><td>4</td></tr></tbody></table>

Tab. 6 displays the total number of fixed length paths (#Paths) along with minimum (Min), average (Avg) and maximum (Max) lengths of paths generated as replacement for transitive closure. Specifically, the transitive closure operation can be eliminated in 16 out of 18 queries for the YAGO dataset.

All (third-party) queries considered in these YAGO experiments happen to be recursive (RQ) graph queries. In order to further experimentally assess the impact of the approach on performance, we next investigate with graphs of different topology and varying sizes, in combination with recursive and non-recursive queries.

## 5.4 Performance results on LDBC

<figure><img src="image_11.png" /><figcaption>Figure 13: Box plot of query runtime for six scale factors (SF=Scale Factor, B=Baseline, S=Schema)</figcaption></figure>

We execute the 30 queries of Tab. 4 for the six different scales of the LDBC-SNB datasets, for both the schema-based approach and the baseline. Therefore each query is run 6 × 2 = 12 times, which yields 360 query runs. Some queries timed out. Among the successful executions, times spent in evaluations can significantly vary from a query to another. In order to extract useful insights from these measurements, we resort to statistical measures and aggregations on successful executions.

**Performance analysis when dataset size varies** We test the hypothesis that performance of query execution is improved by the schema-based approach as compared to the baseline. We conduct this test across all scale factors. Fig. 13, presents a summary of statistics based on box plots for all the successful runs of the 30 queries of Tab. 4 for the two approaches for graphs of increasing sizes. Running times reported on the y-axis use a logarithmic scale. This suggests that the schema-based approach is more efficient for executing queries, especially when the dataset size increases. Notably, the performance of the schema-based approach improved after scale factor 0.3, as depicted in Fig. 13.

**Performance analysis between recursive and non recursive queries** To further analyze the benefits of the schema-based approach, we categorize queries into recursive and non-recursive. Then, we collectively analyze both approaches across all six scale factors. Tab. 7 compares schema-based and baseline (non-schema-based) approaches in query runtime. Here, Count, Min, Q1, Q2, Q3, Max, and Mean represent the total number of queries, minimum, 25th percentile, median, 75th percentile, maximum and mean query runtime in seconds, respectively.

As reported in Tab. 7 comparing the schema-based approach and the baseline for recursive queries across all six scale factors, the results demonstrate that the schema-based approach outperforms the baseline. Specifically, the schema-based approach is 3.26 times faster on average than the baseline for recursive queries. Both approaches exhibit comparable performance when examining non-recursive queries. However, it is worth noticing that the schema-based approach generally demonstrates faster median, 75th percentile, maximum and mean query runtimes compared to the baseline.

Measurements in Tab. 8 suggest that the schema-based approach consistently outperforms the baseline, with an average improvement of 2.58 times for feasible queries at all six scale factors.
<table><caption>Table 7: Query runtime summary statistics (in seconds)</caption><thead><tr><th rowspan="2"></th><th colspan="2">Recursive</th><th colspan="2">Non Recursive</th></tr><tr><th>Baseline</th><th>Schema</th><th>Baseline</th><th>Schema</th></tr></thead><tbody><tr><th>Count</th><td>78</td><td>78</td><td>48</td><td>48</td></tr><tr><th>Min</th><td><strong>0.0137</strong></td><td><strong>0.0137</strong></td><td><strong>0.087</strong></td><td><strong>0.087</strong></td></tr><tr><th>Q1</th><td><strong>2.839</strong></td><td><strong>1.968</strong></td><td>1.211</td><td>1.271</td></tr><tr><th>Q2</th><td><strong>16.254</strong></td><td><strong>11.284</strong></td><td><strong>10.574</strong></td><td><strong>9.515</strong></td></tr><tr><th>Q3</th><td><strong>140.446</strong></td><td><strong>46.759</strong></td><td><strong>45.397</strong></td><td><strong>44.938</strong></td></tr><tr><th>Max</th><td><strong>1800.0</strong></td><td><strong>1171.876</strong></td><td><strong>360.887</strong></td><td><strong>353.044</strong></td></tr><tr><th>Mean</th><td><strong>213.282</strong></td><td><strong>65.244</strong></td><td><strong>46.727</strong></td><td><strong>45.398</strong></td></tr></tbody></table>

<table><caption>Table 8: Overall analysis of query runtime (in seconds)</caption><thead><tr><th></th><th>Count</th><th>Min</th><th>Q1</th><th>Median</th><th>Q3</th><th>Max</th><th>Mean</th></tr></thead><tbody><tr><th>Baseline</th><td>126</td><td><strong>0.0137</strong></td><td><strong>2.6</strong></td><td><strong>14.45</strong></td><td><strong>80.37</strong></td><td><strong>1800.0</strong></td><td><strong>149.833</strong></td></tr><tr><th>Schema</th><td>126</td><td><strong>0.0137</strong></td><td><strong>1.38</strong></td><td><strong>10.45</strong></td><td><strong>46.76</strong></td><td><strong>1171.87</strong></td><td><strong>58.066</strong></td></tr></tbody></table>

Experimental statistics show that the effect of the schema-enrichment process is even more significant for YAGO compared to LDBC. First, YAGO queries provide more optimisation opportunities for transitive closure removal. In contrast, the transitive closure operation can only be removed in 5 out of the 30 LDBC queries. Second, YAGO queries also provide more opportunities for semi-join insertion as they use less branching and conjunction operators. Overall, 10 out of 30 LDBC queries returned to their original UCQT form. In contrast, only 1 out of 18 YAGO queries, reverted to its initial form. When the query reverts to its original form, the schema-based approach obviously has the same runtime than the baseline. This affects the overall performance impact and explains the more favorable aggregate statistics for YAGO queries.

## 5.5 Evaluation on other database systems

We now conduct experiments to evaluate the schema-enrichment approach on PostgreSQL relational database system and Neo4j graph database system. We conducted experiments on the LDBC-SNB dataset, focusing on *chain-shaped* queries Bonifati et al. [2020a]. These queries are expressed without branching and conjunction operations and correspond to the formalism of the union of two-way conjunctive regular path queries (UC2RPQ). The Cypher query language used in the Neo4j graph database only supports a restricted form of UC2RPQ Sharma et al. [2021]. In particular, only 15 out of 30 queries from the LDBC-SNB dataset shown in Tab. 4 are expressible in Cypher and hence supported by Neo4j.

<figure><img src="image_12.png" /><figcaption>Figure 14: Query runtimes on Neo4j (N) and PostgreSQL (P) for LDBC-SNB. (SF=Scale Factor, B=Baseline, S=Schema, PB=PostgreSQL Baseline)</figcaption></figure>

Fig. 14, provides a comprehensive overview of the summary statistics for query runtimes using box plots specifically for the LDBC-SNB dataset at scale factors of 0.1, 0.3, 1, and 3. For scale factors 10, and 30, Neo4j could not complete the query evaluations within 30 minutes. Results shown in Fig. 14 suggest that the schema-based approach improves the performance on each individual system. Overall, the median query runtime of the schema-based approach is consistently better than the baseline across both database systems considered in this study. From our results we observed that PostgreSQL offers more scalability as it is capable of handling scale factors 10 and 30 (See Fig. 13), and yet its performance still benefits from the schema-based enrichment approach. These performance improvements are particularly important at scale factor 30.
Measurements with Neo4j are not reported for YAGO queries as it is by far the most inefficient system for evaluating YAGO queries. This was also noticed by Jachiet et al. [2020].

**Plan-level impact of annotated path expressions** To illustrate the plan-level impact of the schema enrichment process on annotated path expressions, we consider a query $Q_1$ and its schema-enriched version as query $Q_2$ in the LDBC dataset.

$$ 
\begin{array}{l@{\hspace{1em}}l@{\hspace{1em}}l}
\text{SRC, TRG} & \leftarrow & (\text{SRC, knows/workAt/isLocatedIn, TRG}) & Q_1 \\
\text{SRC, TRG} & \leftarrow & (\text{SRC, knows/workAt/\textit{Organisation} isLocatedIn, TRG}) & Q_2
\end{array}
$$

The translated versions of queries $Q_1$ and $Q_2$ in SQL and Cypher are presented in Figures 15 and 16, respectively.

1 // SCHEMA-ENRICHED ($Q_2$)
2 SELECT DISTINCT kw.Sr AS SRC, isLin.Tr AS TRG
3 FROM knows AS kw
4 JOIN workAt AS wr ON kw.Tr=wr.Sr
5 JOIN (SELECT loc.Sr AS Sr, loc.Tr AS Tr
6 FROM (SELECT Sr FROM Organisation) AS org
7 JOIN isLocatedIn AS loc ON loc.Sr=org.Sr
8 ) AS isLin ON wr.Tr-isLin.Sr;

1 // BASELINE ($Q_1$)
2 SELECT DISTINCT kw.Sr AS SRC, isLin.Tr AS TRG
3 FROM knows AS kw
4 JOIN workAt AS wr ON kw.Tr=wr.Sr
5 JOIN isLocatedIn AS isLin ON wr.Tr-isLin.Sr;

<caption>Figure 15: Schema-enriched and baseline queries in SQL</caption>

In Fig. 15, the schema-enriched version of the SQL query contains an additional semi-join between the Organisation node relation and isLocatedIn edge relation (lines 5-7). The result of this semi-join is then combined with the workAt edge relation (line 8). On the other hand, in the baseline version of the query, additional node relation-based semi-join is not performed.

1 // SCHEMA-ENRICHED ($Q_2$)
2 MATCH (SRC)-[:knows]->()-[:workAt]->(:Organisation)-[:isLocatedIn]->(TRG)
3 RETURN DISTINCT SRC, TRG;

1 // BASELINE ($Q_1$)
2 MATCH (SRC)-[:knows]->()-[:workAt]->()-[:isLocatedIn]->(TRG)
3 RETURN DISTINCT SRC, TRG;

<caption>Figure 16: Schema-enriched and baseline queries in Cypher</caption>

In Fig. 16, the schema-enriched version of the Cypher query includes an extra node label in the graph pattern (line 2). The schema-enriched graph pattern indicates the selection of isLocatedIn labeled edges that start from nodes labeled as Organisation in the graph database. In contrast, the baseline version of the query in Cypher does not impose such constraints on the graph pattern.

In order to concretely illustrate the reduction of intermediate results enabled by the schema-enrichment process, Fig. 17 presents the schema-enriched and baseline query execution plans for queries $Q_2$ and $Q_1$, annotated with costs and cardinalities as estimated by PostgreSQL. In Fig. 17, the schema-enriched execution plan generated for query $Q_2$, indicates that the number of intermediate rows significantly decreased after a semi-join is performed between the Organisation node relation and isLocatedIn edge relation (lines 12-16). The isLocatedIn edge relation contains 11 million rows, however, after the semi-join, the number of rows reduced to approximately 8 thousand. In the schema-enriched execution plan, the result of the semi-join is combined with the workAt edge relation (lines 9-11), where the total number of estimated rows is 58,912 for an estimated cost of 2,190.11 (line 9). Conversely, in Fig. 17,
1 // SCHEMA-ENRICHED QUERY EXECUTION PLAN (Q2)
2 HashAggregate (cost = 215,265.50 rows = 2,085,899)
3 Group Key: knows.Sr, islocatedin.Tr
4 Planned Partitions: 32
5 Hash Join (cost = 40,408.50 rows = 2,085,899)
6 Hash Cond: (knows.Tr = workat.Sr)
7 Seq Scan on knows (cost = 12,221.46 rows = 704,246)
8 Hash (cost = 2,190.11 rows = 58,912)
9 Hash Join (cost = 2,190.11 rows = 58,912)
10 Hash Cond: (workat.Tr = Organisation.Sr)
11 Seq Scan on workat (cost = 965.12 rows = 58,912)
12 Hash (cost = 315.51 rows = 7,955)
13 Merge Join (cost = 315.51 rows = 7,955)
14 Merge Cond: (Organisation.Sr = islocatedin.Sr)
15 Index Scan on Organisation (cost = 215.61 rows = 7,955)
16 Index Scan on islocatedin (cost = 337,785.74 rows = 11,118,487)

1 // BASELINE QUERY EXECUTION PLAN (Q1)
2 HashAggregate (cost = 219,592.34 rows = 2,085,899)
3 Group Key: knows.Sr, islocatedin.Tr
4 Planned Partitions: 32
5 Hash Join (cost = 44,735.33 rows = 2,085,899)
6 Hash Cond: (knows.Tr = workat.Sr)
7 Seq Scan on knows (cost = 12,221.46 rows = 704,246)
8 Hash (cost = 6,516.95 rows = 58,912)
9 Merge Join (cost = 6,516.95 rows = 58,912)
10 Merge Cond: (islocatedin.Sr = workat.Tr)
11 Index Scan on islocatedin (cost = 337,785.74 rows = 11,118,487)
12 Sort (cost = 5,780.08 rows = 58,912)
13 Sort Key: workat.Tr
14 Seq Scan on workat (cost = 965.12 rows = 58,912)

<caption>Figure 17: Execution plans for schema-enriched and baseline queries</caption>

the baseline execution plan generated for query Q1, the isLocatedIn edge relation does not undergo filtering. It is directly joined with the workAt edge relation (line 10), for an estimated higher cost of 6,516.95 (line 9). The same number of rows is estimated for both the baseline and the schema-enriched execution plans (line 9).

Overall, as shown in Fig. 17, the schema-enriched plan (line 2) has a smaller estimated cost compared to the baseline plan (line 2) for the same number of rows in the final result set.

## 6 Related Work

Query rewriting techniques that rely on the structural information of the schema have been proposed Chakravarthy et al. [1990]. Authors of Abiteboul and Vianu [1997], Buneman et al. [1998, 2000a], Vielle [1989] emphasize the schema's significance in the query rewriting. Additionally, authors in Buneman et al. [1997], Fernandez and Suciu [1998] suggest that knowing the structure of the database can help reduce the query search space, leading to a significant improvement in overall query runtime. We now briefly discuss schema-based query rewriting techniques proposed for databases following different data models.

**Semi-structured databases** Schema-based query rewriting techniques for queries over semi-structured databases is proposed in Abiteboul and Vianu [1997], Buneman et al. [1998, 2000a]. In semi-structured databases, schemas are expressed as *path constraints* that are regular expressions defined over edge labels Buneman et al. [2000b]. The use of path constraints to rewrite queries expressed in the formalism of C2RPQ and UC2RPQ is proposed in Deutsch and Tannen [2001], Calvanese et al. [1998], Florescu et al. [1998]. However, a significant limitation of using path constraints as a schema language is that the schema database consistency can only be established when path constraints are defined without using the Kleene star operator Buneman et al. [2000a].
**XML databases** Authors in Neven and Schwentick [2006], Wood [2003] propose rewriting XPath queries using the structural information stored in the schema of XML databases. For XML databases, schemas are expressed as *Document Type Definition* (DTDs), which are essentially regular expressions defined over the edge labels Martens [2022]. Authors Miklau and Suciu [2004], Benedikt et al. [2008], Lakshmanan et al. [2004], Geerts and Fan [2005], Hidders [2004], Czerwiński et al. [2015] study the satisfiability of XPath queries in presence of DTDs and suggest that satisfiability is undecidable for XPath queries in presence of recursive DTDs (DTDs defined using Kleene star operator). Authors in Bressan et al. [2005], Marian and Siméon [2003] propose the creation of smaller XML documents by using the XPath query and structure of XML schema. Authors in Benzaken et al. [2006] suggest a type system-based approach for XML document pruning; however, they highlight that creating pruned XML documents can be time-consuming and may take a similar amount of time as running the original query.

**Datalog** Schema-based query rewriting of conjunctive queries (CQ) and union of conjunctive queries (UCQ) in the presence of schema expressed as Datalog rules is proposed in Meier et al. [2010]. Furthermore, authors Barceló et al. [2020] suggest that query containment of CQ and UCQ is decidable in the presence of schema expressed as non-recursive Datalog. Authors Bancilhon et al. [1985], Vielle [1989], de Moor et al. [2008], Schäfer and de Moor [2010] study the containment of Datalog queries in the presence of schema and suggest that the containment is decidable in the presence of non-recursive schemas. Regarding graph query language formalism, authors in Bonatti [2004], Calvanese et al. [1998, 2005] express the formalisms of C2RPQ and UC2RPQ as Datalog queries and suggest that the query containment is decidable in the presence of non-recursive Datalog schema.

**Graph databases** Graph query and schema languages have been extensively researched in the context of knowledge graphs Wiharja et al. [2020], Hu et al. [2022], Bellomarini et al. [2022] with RDFS and OWL in particular Henriksson and Małuszyński [2004], Lu et al. [2007], and the standard query language SPARQL Bonifati et al. [2020b], Haller [2023], Chekol et al. [2018, 2012]. Query rewriting based on the structure of the Resource Description Framework (RDF) has been proposed in Kim et al. [2017], Abbas et al. [2017] for non-recursive SPARQL queries.

For property graphs, significant research and standardisation effort are still in progress Sakr et al. [2021a], Bonifati [2021], Sakr et al. [2021b], Bonifati and Voigt [2022], Bonifati et al. [2023a], Rost et al. [2024], Deutsch et al. [2022], Francis et al. [2023b], Angles et al. [2018]. So far, the lack of standard schema language hinders the application of schema-based query rewriting techniques. Contemporary research in property graph data models mainly focuses on property graph schema design and inference techniques Alotaibi et al. [2021], Lbath et al. [2021], Ragab [2020], Sakr et al. [2021a], Bonifati et al. [2023b, 2022, 2019]. The design of our graph schema is motivated by existing works such as PG-Schema and PG-Keys proposed in Angles et al. [2023, 2021].

In Colazzo and Sartiani [2015], a type inference approach is proposed to rewrite queries expressed in the formalisms of RPQ and 2RPQ using a recursive graph schema. However, the type inference system presented in Colazzo and Sartiani [2015] is neither sound nor complete for graph query language formalisms containing branching and conjunction operations. Additionally, the type inference system is only explored theoretically.

Compared to the state-of-the-art, our approach can take a UCQT query and a graph schema as input and generate a UCQT query as output, which is enhanced with structural schema information. The rewritten schema-aware query preserves the initial query semantics under the graph schema. We experimentally demonstrate that for recursive UCQTs, the generated UCQT can be executed more efficiently using our approach.

# 7 Conclusion and Perspectives

We propose a graph query rewriting method aimed at leveraging the structural information of a graph schema. The purpose is to enrich an initial query with schema information in order to improve query performance. To this end, we introduce inference rules capable of incorporating schema constraints in the path expressions contained in a query. The difficulty comes from the fact that pushing constraints through regular path expressions is complex. Our approach automates a process which would be tricky and error-prone if done manually by a developer. The soundness and completeness of the approach are proved to ensure that the initial query semantics is preserved under the schema. Furthermore, our approach is opportunistic in that it is applied only when performance gains are expected. We conducted extensive experiments on real and synthetic datasets, with several database systems. Experimental results show that schema-based query rewriting provides significant performance gains for recursive path queries in graphs. A perspective for further work is to extend the approach by considering queries with aggregations.
# 8 Acknowledgments

This research was partially funded by the ANR GraphRec project under grant number "ANR-23-CE23-0010".

## References

Gordon Bell, Tony Hey, and Alex Szalay. Beyond the data deluge. *Science*, 323(5919):1297-1298, 2009.

Chris Barrett, Riko Jacob, and Madhav Marathe. Formal-language-constrained path problems. *SIAM Journal on Computing*, 30(3):809-837, 2000.

Amit Sheth, Boanerges Aleman-Meza, I Budak Arpinar, Clemens Bertram, Yashodhan Warke, Cartic Ramakrishanan, Chris Halaschek, Kemafar Anyanwu, David Avant, F Sena Arpinar, et al. Semantic association identification and knowledge discovery for national security applications. *Journal of Database Management (JDM)*, 16(1):33-53, 2005.

Fang Yang, Kunjie Fan, Dandan Song, and Huakang Lin. Graph-based prediction of protein-protein interactions with attributed signed graph embedding. *BMC bioinformatics*, 21(1):1-16, 2020.

Chandan Sharma, Roopak Sinha, and Kenneth Johnson. Practical and comprehensive formalisms for modelling contemporary graph query languages. *Information Systems*, 102:101816, 2021.

Rana Alotaibi, Chuan Lei, Abdul Quamar, Vasilis Efthymiou, and Fatma Özcan. Property graph schema optimization for domain-specific knowledge graphs. In *2021 IEEE 37th International Conference on Data Engineering (ICDE)*, pages 924-935. IEEE, 2021.

Louis Jachiet, Pierre Genevès, Nils Gesbert, and Nabil Layaïda. On the optimization of recursive relational queries: Application to graph queries. In *Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data*, pages 681-697, 2020.

Oliver M Duschka, Michael R Genesereth, and Alon Y Levy. Recursive query plans for data integration. *The Journal of Logic Programming*, 43(1):49-73, 2000.

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y Vardi. Rewriting of regular expressions and regular path queries. In *Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pages 194-204, 1999.

Angela Bonifati, George Fletcher, Hannes Voigt, Nikolay Yakovets, and HV Jagadish. *Querying graphs*, volume 10. Springer, 2018.

Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. Foundations of modern query languages for graph databases. *ACM Computing Surveys (CSUR)*, 50(5):1-40, 2017.

Pablo Barceló, Jorge Pérez, and Juan Reutter. Schema mappings and data exchange for graph databases. In *Proceedings of the 16th International Conference on Database Theory*, pages 189-200, 2013.

Leonid Libkin, Juan L Reutter, Adrián Soto, and Domagoj Vrgoč. Trial: A navigational algebra for rdf triplestores. *ACM Transactions on Database Systems (TODS)*, 43(1):1-46, 2018.

Juan L Reutter, Miguel Romero, and Moshe Y Vardi. Regular queries on graph databases. *Theory of computing Systems*, 61:31-83, 2017.

Domagoj Vrgoc. *Querying graphs with data*. PhD thesis, University of Edinburgh, UK, 2014. URL https://hdl.handle.net/1842/8953.

Leonid Libkin, Wim Martens, and Domagoj Vrgoč. Querying graph databases with xpath. In *Proceedings of the 16th International Conference on Database Theory*, pages 129-140, 2013.

Aidan Hogan and Aidan Hogan. Sparql query language. *The Web of Data*, pages 323-448, 2020.

Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. Cypher: An evolving query language for property graphs. In *Proceedings of the 2018 international conference on management of data*, pages 1433-1445, 2018.

Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. Pgql: a property graph query language. In *Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems*, pages 1-6, 2016.

Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, et al. Pg-schema: Schemas for property graphs. *Proceedings of the ACM on Management of Data*, 1(2):1-25, 2023.
Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Keith W Hare, Jan Hidders, Victor E Lee, Bei Li, Leonid Libkin, Wim Martens, et al. Pg-keys: Keys for property graphs. In *Proceedings of the 2021 International Conference on Management of Data*, pages 2423–2436, 2021.

Van-Quyet Nguyen and Kyungbaek Kim. Estimating the evaluation cost of regular path queries on large graphs. In *Proceedings of the 8th International Symposium on Information and Communication Technology*, pages 92–99, 2017.

Nikolay Yakovets, Parke Godfrey, and Jarek Gryz. Waveguide: Evaluating sparql property path queries. In *EDBT*, volume 2015, pages 525–528, 2015.

Rakesh Agrawal. Alpha: An extension of relational algebra to express a class of recursive queries. *IEEE Transactions on Software Engineering*, 14(7):879–885, 1988.

Luiz Gomes-Jr, Bernd Amann, and André Santanchè. Beta-algebra: Towards a relational algebra for graph analysis. In *EDBT/ICDT 2015 Joint Conference*, volume 157, 2015.

Wilco v Leeuwen, Thomas Mulder, Bram van de Wall, George Fletcher, and Nikolay Yakovets. Avantgraph query processing engine. *Proceedings of the VLDB Endowment*, 15(12):3698–3701, 2022.

Wen Sun, Achille Fokoue, Kavitha Srinivas, Anastasios Kementsietsidis, Gang Hu, and Guotong Xie. Sqlgraph: An efficient relational-based property graph store. In *Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data*, pages 1887–1901, 2015.

J Shanmugasundaram, K Tufte, C Zhang, G He, DJ DeWitt, and JF Naughton. Relational databases for querying xml documents: Limitations and opportunities, in 'vldb'99: Proc. of the 25th int. conf. on very large data bases', 1999.

Alekh Jindal, Praynaa Rawlani, Eugene Wu, Samuel Madden, Amol Deshpande, and Mike Stonebraker. Vertexica: your relational friend for graph analytics! 2014.

Konstantinos Xirogiannopoulos, Virinchi Srinivas, and Amol Deshpande. Graphgen: Adaptive graph processing using relational databases. In *Proceedings of the Fifth International Workshop on Graph Data-management Experiences & Systems*, pages 1–7, 2017.

Marios Meimaris, George Papastefanatos, Nikos Mamoulis, and Ioannis Anagnostopoulos. Extended characteristic sets: graph indexing for sparql query optimization. In *2017 IEEE 33rd International Conference on Data Engineering (ICDE)*, pages 497–508. IEEE, 2017.

Thomas Neumann and Guido Moerkotte. Characteristic sets: Accurate cardinality estimation for rdf queries with multiple joins. In *2011 IEEE 27th International Conference on Data Engineering*, pages 984–994. IEEE, 2011.

Mihaela A Bornea, Julian Dolby, Anastasios Kementsietsidis, Kavitha Srinivas, Patrick Dantressangle, Octavian Udrea, and Bishwaranjan Bhattacharjee. Building an efficient rdf store over a relational database. In *Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data*, pages 121–132, 2013.

Chandan Sharma and Roopak Sinha. Flasc: a formal algebra for labeled property graph schema. *Automated Software Engineering*, 29(1):37, 2022.

Piero A Bonatti. On the decidability of containment of recursive datalog queries-preliminary report. In *Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pages 297–306, 2004.

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. On the decidability of query containment under constraints. In *Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 149–158, 1998.

Diego Calvanese, Giuseppe De Giacomo, and Moshe Y Vardi. Decidable containment of recursive queries. *Theoretical Computer Science*, 336(1):33–56, 2005.

Alin Deutsch and Val Tannen. Optimization properties for classes of conjunctive regular path queries. In *International Workshop on Database Programming Languages*, pages 21–39. Springer, 2001.

Daniela Florescu, Alon Levy, and Dan Suciu. Query containment for conjunctive queries with regular expressions. In *Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 139–148, 1998.

Michael Benedikt, Wenfei Fan, and Floris Geerts. Xpath satisfiability in the presence of dtds. *Journal of the ACM (JACM)*, 55(2):1–79, 2008.

Laks VS Lakshmanan, Ganesh Ramesh, Hui Wang, and Zheng Zhao. On testing satisfiability of tree pattern queries. In *VLDB*, volume 4, pages 120–131, 2004.

Floris Geerts and Wenfei Fan. Satisfiability of xpath queries with sibling axes. In *International Workshop on Database Programming Languages*, pages 122–137. Springer, 2005.
Pierre Genevès and Nabil Layaïda. A system for the static analysis of xpath. *ACM Trans. Inf. Syst.*, 24(4):475–502, 2006. doi:10.1145/1185877.1185882. URL https://doi.org/10.1145/1185877.1185882.

Johannes Hoffart, Fabian M. Suchanek, Klaus Berberich, and Gerhard Weikum. YAGO2: A spatially and temporally enhanced knowledge base from wikipedia. *Artif. Intell.*, 194:28–61, 2013. doi:10.1016/J.ARTINT.2012.06.001. URL https://doi.org/10.1016/j.artint.2012.06.001.

Renzo Angles, Harsh Thakkar, and Dominik Tomaszuk. Mapping rdf databases to property graph databases. *IEEE Access*, 8:86091–86110, 2020.

Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. Gpc: A pattern calculus for property graphs. In *Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems*, pages 241–250, 2023a.

Jelle Hellings. On tarski's relation algebra: querying trees and chains and the semi-join algebra, 2018.

Jelle Hellings, Catherine L Pilachowski, Dirk Van Gucht, Marc Gyssens, and Yuqing Wu. From relation algebra to semi-join algebra: An approach for graph query optimization. In *Proceedings of the 16th International Symposium on Database Programming Languages*, pages 1–10, 2017.

Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of sparql. In *International semantic web conference*, pages 30–43. Springer, 2006.

Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, and George HL Fletcher. Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. *Information Systems*, 89:101467, 2020.

Jelle Hellings, Marc Gyssens, Jan Van Den Bussche, and Dirk Van Gucht. Expressive completeness of two-variable first-order logic with counting for first-order logic queries on rooted unranked trees. In *2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)*, pages 1–13. IEEE, 2023.

Reijo Jaakkola and Antti Kuusisto. Complexity classifications via algebraic logic. In *31st EACSL Annual Conference on Computer Science Logic*, CSL 2023. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.

Molham Aref, Balder ten Cate, Todd J Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L Veldhuizen, and Geoffrey Washburn. Design and implementation of the logicblox system. In *Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data*, pages 1371–1382, 2015.

Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. The dlv system for knowledge representation and reasoning. *ACM Transactions on Computational Logic (TOCL)*, 7 (3):499–562, 2006.

Jacopo Urbani, Ceriel JH Jacobs, and Markus Krötzsch. Vlog: A column-oriented datalog system for large knowledge graphs. In *ISWC (Posters & Demos)*, 2016.

Amela Fejza, Pierre Genevès, Nabil Layaïda, and Sarah Chlyah. The μ-ra system for recursive path queries over graphs. In *Proceedings of the 32nd ACM International Conference on Information and Knowledge Management*, pages 5041–5045, 2023.

YAGO Yago. A high-quality knowledge base. https://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago, 2019.

Orri Erling, Alex Averbuch, Josep Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat, Minh-Duc Pham, and Peter Boncz. The ldbc social network benchmark: Interactive workload. In *Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data*, pages 619–630, 2015.

Gábor Szárnyas. Ldbc social network benchmark graphs. https://hdl.handle.net/11112/e6e00558-a2c3-9214-473e-04a16de09bf8, 2023.

Fabian Suchanek, Mehwish Alam, Thomas Bonald, Pierre-Henri Paris, and Jules Soria. Integrating the wikidata taxonomy into yago, 2023.

Amine Mhedhbi, Matteo Lissandrini, Laurens Kuiper, Jack Waudby, and Gábor Szárnyas. Lsqb: a large-scale subgraph query benchmark. In *Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)*, pages 1–11, 2021.

Zahid Abul-Basher, Nikolay Yakovets, Parke Godfrey, Shadi Ghajar-Khosravi, and Mark H Chignell. Tasweet: optimizing disjunctive regular path queries in graph databases. In *EDBT/ICDT 2017 Joint Conference 20th International Conference on Extending Database Technology*, pages 470–473, 2017.

Andrey Gubichev, Srikanta J Bedathur, and Stephan Seufert. Sparqling kleene: fast property paths in rdf-3x. In *First International Workshop on Graph Data Management Experiences and Systems*, pages 1–7, 2013.
Angela Bonifati, Wim Martens, and Thomas Timm. An analytical study of large sparql query logs. *The VLDB Journal*, 29(2-3):655-679, 2020a.

Upen S Chakravarthy, John Grant, and Jack Minker. Logic-based approach to semantic query optimization. *ACM Transactions on Database Systems (TODS)*, 15(2):162–207, 1990.

Serge Abiteboul and Victor Vianu. Regular path queries with constraints. In *Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 122–133, 1997.

Peter Buneman, Wenfei Fan, and Scott Weinstein. Path constraints on semistructured and structured data. In *Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 129–138, 1998.

Peter Buneman, Wenfei Fan, and Scott Weinstein. Query optimization for semistructured data using path constraints in a deterministic data model. In *Research Issues in Structured and Semistructured Database Programming: 7th International Workshop on Database Programming Languages, DBPL’99 Kinloch Rannoch, UK, September 1–3, 1999 Revised Papers* 7, pages 208–223. Springer, 2000a.

Laurent Vielle. Recursive query processing: The power of logic. *Theoretical computer science*, 69(1):1–53, 1989.

Peter Buneman, Susan Davidson, Mary Fernandez, and Dan Suciu. Adding structure to unstructured data. In *Database Theory—ICDT’97: 6th International Conference Delphi, Greece, January 8–10, 1997 Proceedings* 6, pages 336–350. Springer, 1997.

Mary Fernandez and Dan Suciu. Optimizing regular path expressions using graph schemas. In *Proceedings 14th International Conference on Data Engineering*, pages 14–23. IEEE, 1998.

Peter Buneman, Wenfei Fan, and Scott Weinstein. Path constraints in semistructured databases. *Journal of Computer and System Sciences*, 61(2):146–193, 2000b.

Frank Neven and Thomas Schwentick. On the complexity of xpath containment in the presence of disjunction, dtds, and variables. *Logical Methods in Computer Science*, 2, 2006.

Peter T Wood. Containment for xpath fragments under dtd constraints. In *Database Theory—ICDT 2003: 9th International Conference Siena, Italy, January 8–10, 2003 Proceedings* 9, pages 300–314. Springer, 2003.

Wim Martens. Towards theory for real-world data. In *Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems*, pages 261–276, 2022.

Gerome Miklau and Dan Suciu. Containment and equivalence for a fragment of xpath. *Journal of the ACM (JACM)*, 51 (1):2–45, 2004.

Jan Hidders. Satisfiability of xpath expressions. In *Database Programming Languages: 9th International Workshop, DBPL 2003, Potsdam, Germany, September 6-8, 2003. Revised Papers* 9, pages 21–36. Springer, 2004.

Wojciech Czerwiński, Wim Martens, Pawel Parys, and Marcin Przybylko. The (almost) complete guide to tree pattern containment. In *Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems*, pages 117–130, 2015.

Stéphane Bressan, Barbara Catania, Zoé Lacroix, Ying Guang Li, and Anna Maddalena. Accelerating queries by pruning xml documents. *Data & Knowledge Engineering*, 54(2):211–240, 2005.

Amélie Marian and Jérôme Siméon. Projecting xml documents. In *Proceedings 2003 VLDB Conference*, pages 213–224. Elsevier, 2003.

Véronique Benzaken, Giuseppe Castagna, Dario Colazzo, and Kim Nguyen. Type-based xml projection. In *VLDB*, volume 6, pages 271–282, 2006.

Michael Meier, Michael Schmidt, Fang Wei, and Georg Lausen. Semantic query optimization in the presence of types. In *Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pages 111–122, 2010.

Pablo Barceló, Diego Figueira, Georg Gottlob, and Andreas Pieris. Semantic optimization of conjunctive queries. *Journal of the ACM (JACM)*, 67(6):1–60, 2020.

Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D Ullman. Magic sets and other strange ways to implement logic programs. In *Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems*, pages 1–15, 1985.

Oege de Moor, Damien Sereni, Pavel Avgustinov, and Mathieu Verbaere. Type inference for datalog and its application to query optimisation. In *Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pages 291–300, 2008.
Max Schäfer and Oege de Moor. Type inference for datalog with complex type hierarchies. In *Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages*, pages 145–156, 2010.

Kemas Wiharja, Jeff Z Pan, Martin J Kollingbaum, and Yu Deng. Schema aware iterative knowledge graph completion. In *Journal of Web Semantics*, 65:100616, 2020.

Zhiwei Hu, Víctor Gutiérrez-Basulto, Zhiliang Xiang, Xiaoli Li, Ru Li, and Jeff Z Pan. Type-aware embeddings for multi-hop reasoning over knowledge graphs. *arXiv preprint arXiv:2205.00782*, 2022.

Luigi Bellomarini, Andrea Gentili, Eleonora Laurenza, and Emanuel Sallinger. Model-independent design of knowledge graphs-lessons learnt from complex financial graphs. In *EDBT*, pages 2–524, 2022.

Jakob Henriksson and Jan Maluszyński. Static type-checking of datalog with ontologies. In *Principles and Practice of Semantic Web Reasoning: Second International Workshop, PPSWR 2004, St. Malo, France, September 6-10, 2004. Proceedings 2*, pages 76–89. Springer, 2004.

Jing Lu, Li Ma, Lei Zhang, Jean-Sébastien Brunner, Chen Wang, Yue Pan, and Yong Yu. Sor: A practical system for ontology storage, reasoning and search. In *VLDB*, volume 7, pages 1402–1405, 2007.

Angela Bonifati, Wim Martens, and Thomas Timm. Sharql: Shape analysis of recursive sparql queries. In *Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data*, pages 2701–2704, 2020b.

David Haller. A query-driven approach for shacl type inference. In *Conference on Very Large Data Bases (VLDB 2023)*, 2023.

Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. Sparql query containment under schema. *Journal on Data Semantics*, 7(3):133–154, 2018.

Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. Sparql query containment under shi axioms. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 26, pages 10–16, 2012.

HyeongSik Kim, Padmashree Ravindra, and Kemafor Anyanwu. Type-based semantic optimization for scalable rdf graph pattern matching. In *Proceedings of the 26th International Conference on World Wide Web*, pages 785–793, 2017.

Abdullah Abbas, Pierre Genevès, Cécile Roisin, and Nabil Layaïda. Optimising sparql query evaluation in the presence of shex constraints. In *BDA 2017-33ème conférence sur la «Gestion de Données—Principes, Technologies et Applications»*, pages 1–12, 2017.

Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid Aref, Marcelo Arenas, Maciej Besta, Peter A Boncz, et al. The future is big graphs: a community view on graph processing systems. *Communications of the ACM*, 64(9):62–71, 2021a.

Angela Bonifati. Graph processing systems back to the future. In *Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)*, pages 1–1, 2021.

Sherif Sakr, Angela Bonifati, Hannes Voigt, and Alexandru Iosup. Ensuring the success of big graph processing for the next decade and beyond. *Communications of the ACM*, 64(9), 2021b.

Angela Bonifati and Hannes Voigt. Special issue on big graph data management and processing. *The VLDB Journal*, 31 (2):201–202, 2022.

Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Matthias Hofer, Wim Martens, Filip Murlak, Joshua Shinavier, Slawek Staworko, and Dominik Tomaszuk. Threshold queries. *ACM SIGMOD Record*, 52(1):64–73, 2023a.

Christopher Rost, Riccardo Tommasini, Angela Bonifati, Emanuele Della Valle, Erhard Rahm, Keith W Hare, Stefan Plantikow, Petra Selmer, and Hannes Voigt. Seraph: Continuous queries on property graph streams. 2024.

Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, et al. Graph pattern matching in gql and sql/pgq. In *Proceedings of the 2022 International Conference on Management of Data*, pages 2246–2258, 2022.

Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. A researchers digest of gql. In *The 26th International Conference on Database Theory*, 2023, pages 1–1. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023b.

Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter Boncz, George Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan Sequeda, et al. G-core: A core for future graph query languages. In *Proceedings of the 2018 International Conference on Management of Data*, pages 1421–1432, 2018.
Hanâ Lbath, Angela Bonifati, and Russ Harmer. Schema inference for property graphs. In *EDBT 2021-24th International Conference on Extending Database Technology*, pages 499–504, 2021.

Mohamed Ragab. Large scale querying and processing for property graphs phd symposium. 2020.

Angela Bonifati, Stefania Dumbrava, Emile Martinez, and Nicolas Mir. The quest for schemas in graph databases. *Looking Ahead*, 4:5, 2023b.

Angela Bonifati, Stefania Dumbrava, Emile Martinez, Fatemeh Ghasemi, Malo Jaffré, Pacôme Luton, and Thomas Pickles. Discopg: property graph schema discovery and exploration. *Proceedings of the VLDB Endowment*, 15(12): 3654–3657, 2022.

Angela Bonifati, Peter Furniss, Alastair Green, Russ Harmer, Eugenia Oshurko, and Hannes Voigt. Schema validation and evolution for graph databases. In *Conceptual Modeling: 38th International Conference, ER 2019, Salvador, Brazil, November 4–7, 2019, Proceedings 38*, pages 448–456. Springer, 2019.

Dario Colazzo and Carlo Sartiani. Typing regular path query languages for data graphs. In *Proceedings of the 15th Symposium on Database Programming Languages*, pages 69–78, 2015.