# Designing and Comparing RPQ Semantics

Victor Marsault, Antoine Meyer

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

## To cite this version:

Victor Marsault, Antoine Meyer. Designing and Comparing RPQ Semantics. 2026. [hal-05514429](https://hal.science/hal-05514429v1)

HAL Id: hal-05514429

https://hal.science/hal-05514429v1

Preprint submitted on 17 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Designing and Comparing RPQ Semantics

Victor Marsault

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

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

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

Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

Antoine Meyer

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

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

Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

## Abstract

Modern property graph database query languages such as Cypher, PGQL, GSQL, and the standard GQL draw inspiration from the formalism of regular path queries (RPQs). In order to output walks explicitly, they depart from the classical and well-studied *homomorphism* semantics. However, it then becomes difficult to present results to users because RPQs may match infinitely many walks. The aforementioned languages use ad-hoc criteria to select a finite subset of those matches. For instance, Cypher uses *trail* semantics, discarding walks with repeated edges; PGQL and GSQL use *shortest walk* semantics, retaining only the walks of minimal length among all matched walks; and GQL allows users to choose from several semantics. Even though there is academic research on these semantics, it focuses almost exclusively on evaluation efficiency.

In an attempt to better understand, choose and design RPQ semantics, we present a framework to categorize and compare them according to other criteria. We formalize several possible properties, pertaining to the study of RPQ semantics seen as mathematical functions mapping a database and a query to a *finite* set of walks. We show that some properties are mutually exclusive, or cannot be met. We also give several new RPQ semantics as examples. Some of them may provide ideas for the design of new semantics for future graph database query languages.

**2012 ACM Subject Classification** Theory of computation → Database query languages (principles); Information systems → Query languages for non-relational engines; Information systems → Graph-based database models; Theory of computation → Regular languages

**Keywords and phrases** Regular Path Queries; RPQ; Semantics; Graph Databases; Pattern matching; Regular Expression

**Related Version** A short version of this work is published in [MM26].

**Acknowledgements** This work stems from discussions with many colleagues, including Claire David, Amélie Gheerbrant, Steven Sailly and Cristina Sirangelo. In particular, we also thank Thomas Colcombet for the idea leading to the definition of the ShVC semantics, and Nadime Francis and Sara Khichane for introducing us to the flashlight search technique used in Proposition 62. Finally, we thank Yann Strozecki for his help with the enumeration complexity framework.

## 1 Introduction

In the past decades, there has been increasing interest and use for graph database management systems (DBMS). The typical task when exploiting such databases consists in navigating the graph. To achieve this, most modern query languages contain features inspired by Regular Path Queries (RPQs) [CMW87]. RPQs and their generalizations were thoroughly studied in academic literature. Essentially, an RPQ is a regular expression used to query an edge-labeled graph. A walk (that is, an alternating sequence of vertices and edges) matches an RPQ $R$ if its label (that is, the concatenation of its edge labels) conforms to $R$.

In industry, RPQs were added to the standard language SPARQL [SPARQL13] for RDF. They were also the basis of the MATCH clause in Cypher [Cypher24; FG$^+$18a], the language introduced with the successful property graph DBMS Neo4j. RPQs were an inspiration for other query languages for graph DBMS [GSQL23; PGQL21]. Due in part to the success of Cypher and Neo4j, a standard query language for property graphs was designed [GQL24].

<figure><img src="image_8.png" /></figure>
Its navigational part is heavily influenced by RPQs, and was made compatible with SQL
[PGQ23].

RPQs are usually evaluated under *homomorphism semantics* [AA<sup>+17</sup>]. In this setting,
the answer to a query *R* is the set of all pairs (*s*, *t*) such that there exists a walk matching *R*
from *s* to *t*. In other words, the answer consists of the set of *endpoints* of all matching walks.
However, endpoint semantics turns out to be inadequate in some practical scenarios: users
sometimes need to have access to whole matched walks, and not only to their endpoints.

RPQs typically match infinitely many walks, hence if queries are to return whole walks
then their presentation to the user in full is problematic. To address this issue, many real-life
query languages for property graphs choose to return only a finite subset of matching walks
to the user, selected in various ways. Cypher uses *trail semantics*: a matching walk is only
returned if it contains no edge repetition. Other languages like GSQL or PGQL use *shortest
semantics*: a matching walk is returned only if there is no shorter match with the same
endpoints. Another well-known example is *acyclic semantics*: a matching walk is returned
only if it contains no vertex repetition. GQL allows the user to choose one of these semantics,
among others. We follow this modern approach in the current article: what we call an RPQ
semantics is any specification of a way to select, among a potentially infinite set of matching
walks, a *finite* subset of walks to return to the user.

Recent work on RPQs under various semantics focus on the evaluation process. Com-
putational problems related to evaluation are untractable under acyclic [BBG20] or trail
[MNP23] semantics. On the other hand, there exist efficient algorithms for evaluation under
shortest semantics [MT18; DFM24]. One of the challenges of query evaluation is the sheer
number of results, and there has been work on better, more succinct representations of the
set of results [MN<sup>+</sup>23; MN<sup>+</sup>24]. This draws a very one-sided picture: shortest semantics
always yields algorithms that are much more efficient. However, the most popular system
as of today (Neo4j) uses trail semantics, and our hypothesis is that this can be ascribed to
other desirable properties.

**Contributions.** To start this investigation, we propose a formal framework to define and categorize RPQ semantics. We call semantics like trail or acyclic *filter-based*, because they act as post-filters: each walk is individually considered good (e.g., with no repetition) or bad (e.g. with repetitions), independently of other matches. We call semantics like shortest *order-based*, because they select the best matched walks according to some global criterion. More precisely, such semantics are defined using (partial) ordering relations on walks, and return all walks that are minimal (among matches) with respect to this ordering.

We then define many properties that RPQ semantics may or may not possess, and discuss
why these properties may be desirable. To state a few, we introduce properties related to
monotonicity, continuity, composability using rational operators, and coverage. Since we
define RPQ semantics in the abstract, one may easily come up with unpractical or even
nonsensical semantics. Hence, we propose a list of properties that any reasonable semantics
should possess. We also show several impossibility theorems, in the form of sets of mutually
exclusive properties. The goal of these results is to facilitate the design of new and interesting
RPQ semantics. We often illustrate our definitions and statements with examples of new
RPQ semantics (which are compiled in the index, page 30). Some of them appear to be
reasonable candidates for possible practical use.

**Outline.** Section 2 contains preliminary vocabulary and definitions, in particular the models we use for data (labeled graph) and queries (regular expressions). Then, Section 3 presents
our framework: what RPQ semantics are, how to define one, and which ones we are interested in. Section 4 introduces several properties that RPQ semantics might possess. We summarize the properties of several usual semantics, and provide a few general statement (e.g., which properties are mutually exclusive). We also discuss the desirability of those properties. Section 5 recalls some known results about computational complexity.

In this document, we introduce many RPQ semantics, each with an acronym, and many properties for them. An index is provided on page 30.

**Related work.** As far as we know, few RPQ semantics were studied in academic work other than the endpoint, acyclic, trail and shortest semantics. The fragment of the RDF query language SPARQL which is related to RPQs is called *property paths* [SPARQL13], and in the process leading to their definition, one of the candidate semantics indeed computed sets of walks. In order to only present a finite number of results, it was decided that in this semantics the same walk could not be iterated using a Kleene star. This candidate semantics was discarded due to the fact that it was returning too many results [ACP12], a phenomenon sometimes referred to as the *Yotabyte problem*. It was finally decided that property paths in SPARQL would be evaluated under endpoint semantics, with a variation best explained in terms of rewriting: property paths are automatically rewritten using other SPARQL constructs in order to obtain a query in which all property paths have a Kleene star as outermost operator (see Section 9.3, *Property Paths and Equivalent Patterns*, of [SPARQL13]). This seemingly strange decision stems from the will to handle multiplicity consistently.

In GQL[GQL24] and SQL/GPQ[PGQ23], the keyword **SIMPLE** switches on a variant of acyclic semantics that returns not only simple walks but also simple cycles. It is usually not considered in theoretical articles, since it is computationally equivalent to acyclic semantics.

In [DFM23], the authors present two new semantics (simple run and binding trail) that filter walks based on the underlying matching process and not only on their topology. Such semantics are outside the scope of this article (see Sec. 3.4), but the introduction of [DFM23] is particularly relevant to our work. Indeed, their semantics are computationally better-behaved than trail, but worse than shortest. In order to explain that shortest is not always the best semantics, they use informal criteria that are not based on theoretical algorithmic efficiency. Our aim in the current text is to provide a more systematic argument.

## 2 Preliminaries

We assume the existence of $V, E, L$, three disjoint countably infinite sets of **vertex identifiers**, **edge identifiers** and **labels/letters**, respectively. We will later define all databases and regular expressions over these sets. This will allow us to define several notions independently of the underlying database. We call **identifier** any element in $V \cup E$, **renaming** any permutation $\nu$ of $V \cup E$ such that $\nu(V) = V$ and $\nu(E) = E$. We call **relabeling** any permutation of $L$.

### 2.1 Words, languages, expressions

An **alphabet** is a finite subset $\Sigma$ of $L$. A **word** over $\Sigma$ is a finite sequence of elements of $\Sigma$; the empty word is denoted by $\varepsilon$. The set of all words over $\Sigma$ is denoted by $\Sigma^*$. Subsets of $\Sigma^*$ are called **languages** over $\Sigma$. A word $u = (a_1, \dots, a_k)$ is usually written $a_1 \cdots a_k$, and $k$ is called the **length** of $u$. The **concatenation** of two words $u = a_1 \cdots a_k$ and $v = b_1 \cdots b_\ell$ is $u \cdot v = a_1 \cdots a_k b_1 \cdots b_\ell$, usually written simply $uv$. Concatenation is lifted to languages as follows: $L_1 \cdot L_2 = \{w_1 \cdot w_2 \mid w_1 \in L_1, w_2 \in L_2\}$.
A regular expression R over Σ is any formula over the set of letters, the unary function * and the binary functions + and · consistent with the following grammar.

$$R := \varepsilon \mid a \mid R^* \mid R \cdot R \mid R + R \quad \text{with } a \in \Sigma \qquad (1)$$

Any such R denotes a language L(R) over Σ, defined inductively as usual. Any word in L(R) is said to conform to R.

## 2.2 Walks and databases

A walk is a finite nonempty alternating sequence of vertices in V and edges in E that starts and ends with a vertex. We usually write such a walk w = (v₀, e₁, v₁, ..., eₖ, vₖ) as v₀ → e₁ v₁ → e₂ ... → eₖ vₖ. We call k the length of w and denote it by Len(w); we respectively call v₀ and vₖ the source and target of w and denote them by Src(w) and Tgt(w). The pair (v₀, vₖ) is the pair of endpoints of w, written EndP(w). Walks of length 0 are called trivial and consist of a single vertex. We denote by w[i] the edge eᵢ, with i ∈ {1, ..., k} and by w⟨i⟩ the vertex vᵢ, with i ∈ {0, ..., k}. Note that walks have no particular topology. Thus, it is possible for a walk w to be inconsistent with a database D or even inconsistent in itself (see below).

We let Walks denote the set of all walks (independently of any database). Two walks w and w' concatenate if Tgt(w) = Src(w'), and their concatenation, written w · w', is the walk

$$w \cdot w' = \mathrm{Src}(w) \xrightarrow{w[1]} \cdots \xrightarrow{w[k]} \mathrm{Tgt}(w) \xrightarrow{w'[1]} \cdots \xrightarrow{w'[k]} \mathrm{Tgt}(w')$$

where k = Len(w) and k' = Len(w'). Note that w · w' is of length k + k': it has k + k' edges and k + k' + 1 vertices (vertex Tgt(w) = Src(w') is not repeated). We lift · to sets of walks as usual: W · W' contains all walks w · w' with w ∈ W and w ∈ W' such that w and w' concatenate. We lift the * operator similarly: W* contains all walks w₁ · w₂ · ... · wₖ where every wᵢ belongs to W and every pair wᵢ, wᵢ₊₁ of consecutive walks concatenate.

In this document, we model graph databases as directed, labeled, multi-edge graphs, and simply refer to them as databases. A database D is a tuple (L_D, V_D, E_D, Src_D, Tgt_D, Lbl_D) where L_D ⊂ fin L, V_D ⊂ fin V, E_D ⊂ fin E and Src_D, Tgt_D and Lbl_D are functions respectively mapping each edge in E_D to its source, target and label.

A walk w is consistent with D if all elements in w are in V_D ∪ E_D and for every 0 < i ≤ Len(w), Src_D(w[i]) = w⟨i − 1⟩ and Tgt_D(w[i]) = w⟨i⟩. The set of all walks consistent with D, or for short the set of walks in D, is denoted by Walks(D). We say that n walks w₁, ..., wₙ are consistent if there is a database D such that {w₁, ..., wₙ} ⊆ Walks(D). Whenever n = 1, we say w₁ is self-consistent. We extend Lbl_D to Walks(D) as expected: Lbl_D(w) is the concatenation of successive edge labels in w. When the database D is clear from the context, we abuse terminology and notation by using each edge e ∈ E_D as the walk (Src_D(e), e, Tgt_D(e)). In particular we can ask whether a walk w and an edge e concatenate, and when they do, use the notation w · e.

Any renaming function ν is extended to walks by applying ν to all identifiers in it. It can also be extended to whole databases as follows: ν(D) = (L_D, ν(V_D), ν(E_D), Src'_D, Tgt'_D, Lbl'_D), where Src'_D(x) = ν(Src_D(ν⁻¹(x))), Tgt'_D = ν(Tgt_D(ν⁻¹(x))) and Lbl'_D(x) = Lbl_D(ν⁻¹(x)). Similarly, any relabeling function λ: L → L is extended to regular expressions by applying λ to all atoms, and to databases as follows: λ(D) = (λ(L_D), V_D, E_D, Src_D, Tgt_D, (λ ◦ Lbl_D)).
# 3 Regular Path Queries (RPQ) and their semantics

The concept of Regular Path Query (RPQ) consists in querying the content of a graph database $\mathcal{D}$ thanks to regular expressions over its edge labels.

**Definition 1 (Matches).** Given a regular expression $R$ and a database $\mathcal{D}$, we denote by $\text{Matches}(\mathcal{D}, R)$ the set of matches of $R$ in $\mathcal{D}$, which is the set of all walks in $\mathcal{D}$ whose label conforms to $R$: $\text{Matches}(\mathcal{D}, R) = \{w \in \text{Walks}(\mathcal{D}) | \text{ Label}(w) \in L(R) \}$. Given $v, v' \in V_{\mathcal{D}}$, we will also use the notation $\text{Matches}(\mathcal{D}, R, v, v')$ for the set of the walks $w$ in $\text{Matches}(\mathcal{D}, R)$ such that $\text{EndP}(w) = (v, v')$.

## 3.1 Arbitrary semantics

**Definition 2.** A semantics $S$ is a function mapping a database $\mathcal{D}$ and a query $R$ to a finite subset $S(\mathcal{D}, R)$ of $\text{Matches}(\mathcal{D}, R)$.

Aside from homomorphism semantics, which does not fit our framework because it does not return walks, the two most popular RPQ semantics are shortest-walk semantics and trail semantics. We define them below.

**Example 3 (Trail semantics Tr).** Trail semantics is the semantics of Cypher [FG$^+$18b] and may be used in GQL [DF$^+$22; GQL24] thanks to the keyword **TRAIL**. It is defined as follows. A walk $w$ is a **trail** if it has no duplicate edge, i.e. for all $i \neq j$, $w[i] \neq w[j]$. Trail semantics is defined by: $\text{Tr}(\mathcal{D}, R) = \{ w \in \text{Matches}(\mathcal{D}, R) | w \text{ is a trail} \}$.

**Example 4 (Shortest-walk semantics Sh).** Shortest semantics is the original semantics of GSQL [GSQL23] and PGQL [PGQL21]; it may be used in GQL [DF$^+$22; GQL24] thanks to the keyword **SHORTEST**. Let $\mathcal{D}$ be a database and $R$ a query. For every $s, t \in V_{\mathcal{D}}$, we write $\ell_{(s,t)}$ for the length of the shortest walk in $\text{Matches}(\mathcal{D}, R, s, t)$. Then, shortest semantics is defined by: $\text{Sh}(\mathcal{D}, R) = \bigcup_{s,t \in V_{\mathcal{D}}} \{ w \in \text{Matches}(\mathcal{D}, R, s, t) | \text{Len}(w) = \ell_{(s,t)} \}$.

We focus on semantics that are *walk-based*, as defined below. Intuitively, such semantics act as post-filters on matches: they only have access to the set of matched walks itself, not to the database, to the regular expression, or to the reason or way a given walk was matched by the query.

**Definition 5.** A semantics $S$ is **walk-based** if there is a function $r_S: 2^{\text{Walks}} \to 2^{\text{Walks}}$ such that $S(D, R) = r_S(\text{Matches}(D, R))$.

Even though the previous definition seems very general, walk-based semantics still have to output walks which match the query due to Definition 2. Instances of walk-based semantics are Tr and Sh given above, as well as shortest-trail semantics defined below. On the other hand, we will give in Section 3.4 a few examples of semantics that are not walk-based, such as binding-trail semantics and cheapest-walk semantics.

**Example 6 (Shortest-trail semantics ShT).** Shortest-trail semantics may be used in GQL [DF$^+$22; GQL24] thanks to the keyphrase **SHORTEST TRAIL**. For every $W \subseteq 2^{\text{Walks}}$, and every vertices $s, t \in V$, we let $\ell_{(s,t)}(W)$ denote the length of the shortest trail $w$ in $W$ such that $\text{EndP}(w) = (s, t)$, if it exists. Then, shortest-trail semantics is defined by: $\text{ShT}(\mathcal{D}, R) = r_{\text{ShT}}(\text{Matches}(\mathcal{D}, R))$, where $r_{\text{ShT}}(M)$ contains all trails $w$ in $M$ such that $\text{Len}(w) = \ell_{\text{EndP}(w)}(M)$.

For every $\mathcal{D}$ and $R$, $\text{ShT}(\mathcal{D}, R)$ is clearly a subset of $\text{Tr}(\mathcal{D}, R)$, since it only returns trails matching $R$ in $\mathcal{D}$. However, it may not be a subset of $\text{Sh}(\mathcal{D}, R)$ since the shortest walk matching $R$ between two vertices of $\mathcal{D}$ may or may not be a trail.
## 3.2 Filter-based semantics

**Definition 7.** A semantics S is called **filter-based** if there exists a function $f_S$: Walks $\to \{\top, \bot\}$ such that $S(D, R) = \{w \in \text{Matches}(D, R) | f_S(w) = \top\}$.

Note that every filter-based semantics is also walk-based. Trail semantics (Ex. 3) is the paramount example of a filter-based semantics. It is defined by the function $f_{\text{Tr}}$, that maps a walk $w$ to $\bot$ if there are $i < j$ such that $w[i] = w[j]$, or to $\top$ otherwise. However, it is quite easy to see that neither shortest-walk semantics (Ex. 4) nor shortest-trail semantics (Ex. 6) are filter-based. We give below three examples of filter-based semantics.

**Example 8 (Acyclic semantics Ac).** Acyclic semantics (corresponding to the **ACYCLIC** keyword in GQL) is the semantics defined by the filter $f_{\text{Ac}}$ that maps a walk $w$ to $\bot$ if there are $i < j$ such that $w(i) = w(j)$, and to $\top$ otherwise.

**Example 9 (Simple-cycle-or-walk semantics SWC).** Simple-cycle-or-walk semantics is a variant of Ac that corresponds to keyword **SIMPLE** in GQL. The difference is that simple cycles are also returned. It is defined by the filter $f_{\text{SWC}}$ that maps a walk $w$ to $\bot$ if there are $i < j$ such that $(i, j) \neq (0, \text{Len}(w))$ and $w(i) = w(j)$, and to $\top$ otherwise.

**Example 10 (Two-acyclic-sem 2Ac).** Two-acyclic semantics is a variant of Ac where each vertex is allowed to appear once or twice, but not more. It is defined by the filter below.

$$f_{2\text{Ac}}: w \mapsto \begin{cases} \bot & \text{if there are } i < j < k \text{ such that } w(i) = w(j) = w(k) \\ \top & \text{otherwise} \end{cases}$$

## 3.3 Order-based semantics

First, let us recall a few definitions about partial orders. A **partial order** is a binary, transitive, antisymmetric and reflexive relation. For any partial order $\leq$ we will denote by $\prec$ the associated **strict partial order**. A **well-partial-order** on a set $X$, or **wpo**, is a partial order $\leq$ such that in every infinite sequence $x_1, x_2, \dots, x_k, \dots$ of elements from $X$ there are two positions $i < j$ such that $x_i \leq x_j$. In other words, there exists no infinite strictly decreasing sequence nor any infinite sequence in which all elements are incomparable w.r.t. $\leq$. It is well-known that any subset of $X$ admits finitely many minimal elements w.r.t. a wpo over $X$, and that the restriction of any wpo over $X$ to a subset of $X$ is also a wpo.

**Definition 11 (Order-based semantics).** Let $\leq$ be a partial order on Walks such that for every database $D$, $\leq$ is a wpo on Walks($D$). Such an order is said to be **suitable**. The semantics based on $\leq$, denoted by $S_{\leq}$ is defined as follows for every database $D$ and regular expression $R: S_{\leq}(D, R) = \bigcup_{s,t \in V_D} \min_{\leq}(\text{Matches}(D, R, s, t))$

Note that a suitable order $\leq$ is a wpo on Matches($D, R, s, t$), since Matches($D, R, s, t$) is a subset of Walks($D$). It follows that $S_{\leq}(D, R)$ is always finite. Note also that the ordering of two walks $w, w'$ w.r.t. $\leq$ is irrelevant whenever $w$ and $w'$ have different endpoints. The same is true for walks $w$ and $w'$ that are inconsistent. It is sometimes useful to trim such irrelevant pairs from the orders we consider.

**Definition 12.** For every suitable order $\leq$ we let $\leq_t$ denote the order defined by: $w\leq_t w'$ iff $w$ and $w'$ are consistent walks with the same endpoints such that $w \leq w'$. We say that $\leq$ is **trimmed** if it is equal to $\leq_t$

**Lemma 13.** Each order-based semantics $S_{\leq}$ is identical to $S_{\leq_t}$.
A simple example of order-based semantics is the shortest-walk semantics Sh (Ex. 4). It is based on the partial order $\leq_S h$, the reflexive closure of the strict partial order defined by $w <_S h w'$ if $\text{Len}(w) < \text{Len}(w')$. It is not a wpo on Walks: since $\mathbb{E}$ is infinite, there are infinitely many walks of a given length, and they are all incomparable w.r.t. $<_S h$. However, one may verify that it is indeed a wpo on Walks($\mathcal{D}$) for every database $\mathcal{D}$, and that it is therefore suitable. Let us now define another order-based semantics.

**Definition 14 (Subwalk order).** Let $F$ be the following factor-inserting binary relation: $w F w'$ if there are three walks $w_1, w_2, w_3$ such that $w = w_1 \cdot w_3$ and $w' = w_1 \cdot w_2 \cdot w_3$. We define the **subwalk order** $\sqsubseteq$ as the reflexive and transitive closure of $F$.

It is straightforward to check that $\sqsubseteq$ is a partial order on Walks. Moreover, one may show that $\sqsubseteq$ is a suitable order. We call **subwalk-minimal** and denote by SM the semantics based on $\sqsubseteq$.

**Lemma 15.** For every database $\mathcal{D}$, $\sqsubseteq$ is a wpo on Walks($\mathcal{D}$)

Lemma 15 follows from a corollary of Higman's Lemma [Hig52] (see also [Kar15, Sec. 2.2]). Both are stated below.

**Lemma 16 (Higman's Lemma [Hig52]).** If $\leq$ is a wpo on some set $X$, then $\leq^*$ on $X^*$ is a wpo, where $\leq^*$ is the extension of $\leq$ to sequences, that is $a_1 \cdots a_k \leq^* b_1 \cdots b_\ell$ iff there exists a strictly increasing function $\varphi: \{1, \dots, k\} \to \{1, \dots, \ell\}$ such that $a_i \leq^* \varphi(a_i)$, for every $\{1, \dots, k\}$.

Note that Higman's Lemma is usually stated for *well-quasi-orders*, which are allowed not to be antisymmetric. The result also holds for well-partial-orders, with an identical proof. We are interested in a special case of Lemma 16 stated next, namely the case where $X$ is a finite set and $\leq$ is the equality relation on $X$.

**Corollary 17.** Let $X$ be a finite set, the subsequence relation over $X^*$ is a wpo.

**Proof of Lemma 15.** Let $\mathcal{D}$ be a database. We fix $X = V_{\mathcal{D}} \cup E_{\mathcal{D}}$, a finite set, and let $\leq$ denote the subsequence relation over $X^*$. Corollary 17 states that $\leq$ is a wpo on $X^*$. Note that Walks($\mathcal{D}$) $\subseteq$ $X^+$ and it may be checked that $\sqsubseteq$ is in fact a restriction of $\leq$, that is equal to $\{(u, v) \in \text{Walks}(\mathcal{D}) \times \text{Walks}(\mathcal{D}) \mid u \leq^* v\}$. This means in particular that the subwalk order $\sqsubseteq$ is a wpo on Walks($\mathcal{D}$). ◀

The reason for considering the subwalk order $\sqsubseteq$ and the associated semantics SM stems from the property of subwalk coverage guarantee, which we define later. Preliminary results about the complexity of query evaluation under SM can be found in [Khi24], and are recalled in Figure 2, page 25. To conclude this section, let us mention another interesting order-based semantics.

**Example 18 (Shortlex Semantics ShL).** Let $\leq_{\text{lex}}$ be the lexicographic ordering of walks based on some arbitrary order over $V \cup \mathbb{E}$. Let $\leq_{\text{shortlex}}$ be the corresponding length-lexicographic order: $w \leq_{\text{shortlex}} w'$ if either $|w| < |w'|$ or $(|w| = |w'|$ and $w \leq_{\text{lex}} w')$. Even though $\leq_{\text{lex}}$ is not suitable, it may be verified that $\leq_{\text{shortlex}}$ is. The corresponding shortlex-minimal semantics ShL is a possible implementation of the **ANY SHORTEST** keyphrase in GQL $[\text{DF}^+; 22; \text{GQL24}]$.
## 3.4 Examples of some out-of-scope semantics

This document focuses on semantics that output walks (Def. 3) and are walk-based (Def. 5), but it is of course not the only possible approach to defining meaningful RPQ semantics. The most studied semantics for RPQs in scientific literature is homomorphism semantics [AA$^{+}$17], which outputs the endpoints of matches only, hence does not fit our notion of semantics. On the other hand, [DFM23] propose run-based semantics, i.e. semantics S which require information on the way a walk was matched by the query in order to decide whether it belongs to S(D, R). We present one such run-based semantics below. Afterwards, we define another semantics that is not walk-based. It is loosely inspired by the keyword CHEAPEST, discussed during the elaboration of GQL in internal documents, but was not retained for version 1 (see language opportunity 052 in [PGQ23; GQL24]).

**► Example 19 (Binding-trail semantics BT [DFM23]).** Let $\mathcal{D}$ be a database, R a query, and k is the number of atoms in R. A binding walk (in $\mathcal{D}$ matching R) is a walk $w \in \text{Matches}(\mathcal{D}, R)$ together with a function $\{1, ..., \text{Len}(w)\} \to \{1, ..., k\}$ that maps each edge-position in w to the position of the atom in R that matched that edge. A binding trail (in $\mathcal{D}$ matching R) is a binding-walk $(w, \alpha)$ such that there are no distinct i, j such that $\alpha(i) = \alpha(j)$ and $w[i] = w[j]$. Binding-trail semantics, denoted by BT, is defined as follows.

$$ \text{BT: } (\mathcal{D}, R) \mapsto \{ w \mid \exists \alpha \text{ s.t. } (w, f) \text{ is a binding trail in } \mathcal{D} \text{ matching } R \} \quad (2) $$

See [DFM23] for a more formal definition. A similar semantics called simple-run semantics, based on the states of a finite automaton representing the query, is defined in the same paper.

**► Example 20 (Cheapest-Walk Semantics ChW<sub>c</sub>).** Let $c: \mathbb{L} \to (\mathbb{N} - \{0\})$ be a fixed cost function, which we lift to words by: $c(a_1 \cdots a_k) = \sum_{i=1}^{k} c(a_i)$. Then, the cost of a walk in a database $\mathcal{D}$ and query R is the cost of its label in $\mathcal{D}$. Cheapest-walk semantics, ChW<sub>c</sub>, is defined like shortest-walk semantics, using the cost of matches instead of their length.

Note that ChW<sub>c</sub> is not walk-based (unless the cost function c is constant), because a walk provides no information about the label its edges bear.

# 4 Properties

In this section we define and investigate several possible properties of RPQ semantics, in order to help compare and classify them. After listing a few basic properties, we distinguish properties relative to some forms of monotonicity, continuity, compatibility with rational operators, and coverage. Then, we systematically investigate the inclusions between sets of result for the same query according to various semantics. We conclude this section with a general discussion regarding the set of properties any “reasonable” semantics should possess.

## 4.1 Basics

We first list a few basic properties, which are almost always required for a semantics to be considered useful in our model.

**► Definition 21.** A semantics S is called **identifier-independent** if $\nu(S(\mathcal{D}, R)) = S(\nu(\mathcal{D}), R)$, for every renaming $\nu$, database $\mathcal{D}$ and regular expression R. Similarly, it is **label-independent** if $S(\mathcal{D}, R) = S(\lambda(\mathcal{D}), \lambda(R))$ for every relabeling $\lambda$, database $\mathcal{D}$ and regular expression R.
For instance, a semantics selecting results based on some arbitrary ordering on vertex and edge identifiers (e.g., ShL in Ex. 18), or based on the presence of similar arbitrary criteria, would *not* be identifier-independent. Identifier-independence is related to *genericity* in the classical database setting (see [AHV95] for instance). Indeed, if we consider a query *q* consisting of a regular expression and a semantics *S* to interpret it, then *S* is identifier-independent if and only if *q* is *empty*-generic.

Similarly, label-dependent semantics select their results based on arbitrary information regarding labels. Moreover, no label-dependent semantics is walk-based, as stated below.

**Lemma 22.** Every walk-based semantics is label-independent.

*Proof.* By definition, for any walk-based semantics $S$, we have $S(\mathcal{D}, R) = r_S(\text{Matches}(\mathcal{D}, R))$ for some function $r_S$. However, since $\text{Matches}(\mathcal{D}, R)$ retains no information on the labeling of walks, for any relabeling $\lambda$, $\text{Matches}(\lambda(\mathcal{D}), \lambda(R)) = \text{Matches}(\mathcal{D}, R)$. Therefore $S(\mathcal{D}, R) = S(\lambda(\mathcal{D}), \lambda(R))$. ◀

In this work, we will always be considering identifier- and label-independent semantics, unless explicitly stated otherwise.

**Definition 23.** A semantics *S* is **expression-independent** if, for every database *D* and every expressions *R*₁, *R*₂ such that *L*(*R*₁) = *L*(*R*₂), we have *S*(*D*, *R*₁) = *S*(*D*, *R*₂).

Expression-independent semantics select their results on the sole basis of the language denoted by the regular expression. In some settings, it may make sense to instead let the selection of results depend on the structure of the expression itself. Binding-trail semantics (Ex. 19) is one such example. However, this is out of the scope of this work, since all walk-based semantics are expression-independent, as stated below.

**Lemma 24.** Every walk-based semantics is expression-independent.

*Proof.* Similar to Lemma 22. If $L(R_1) = L(R_2)$ then $\text{Matches}(\mathcal{D}, R_1) = \text{Matches}(\mathcal{D}, R_2)$ by definition of Matches. Therefore $S(\mathcal{D}, R_1) = S(\mathcal{D}, R_2)$. ◀

**Definition 25.** A semantics *S* is called **unbounded** if, for every integer *n*, there is a database *D* and a regular expression *R* such that *S*(*D*, *R*) contains a walk of length *n* or more. Otherwise *S* is called **bounded**.

Of course, we expect any reasonable semantics to be unbounded since a bounded semantics never returns a walk longer than some constant.

## 4.2 Monotony

**Definition 26 (Monotony, co-monotony and restrictibility).** A semantics *S* is said to be **monotonous** if $S(\mathcal{D}, R) \subseteq S(\mathcal{D}', R)$, for every regular expression *R* and databases *D*, *D'* such that $\mathcal{D} \subseteq \mathcal{D}'$. It is **co-monotonous** if $S(\mathcal{D}, R) \supseteq (S(\mathcal{D}', R) \cap \text{Walks}(\mathcal{D}))$, for every regular expression *R* and databases *D*, *D'* such that $\mathcal{D} \supseteq \mathcal{D}'$. It is **restrictible** if both hold.

These notions are about the behavior of the semantics when a database is enriched with new vertices and edges. A monotonous semantics does not remove results when the database is enriched. A co-monotonous semantics does not add results that are unrelated to the new elements. Finally, a restrictible semantics means that one is able to compute part of the result, given part of the database. A simple verification shows that all semantics defined above are co-monotonous. This is in fact true of all filter-based and order-based semantics. Additionally, filter-based semantics are also monotonous, and therefore restrictible.
**► Lemma 27.** Every filter-based semantics is restrictible, and every order-based semantics is co-monotonous.

**Proof for filter-based semantics.** Let $S$ be a filter-based semantics defined by filter function $f_S$ (see Def. 7). Let $R$ be a regular expression and $D, D'$ two databases such that $D \subseteq D'$. We have:

$$S(D', R) = \{ w \in \text{Matches}(D', R) | f_S(w) = \top \}$$

Therefore:

$$S(D', R) \cap \text{Walks}(D) = \{ w \in \text{Matches}(D, R) | f_S(w) = \top \} = S(D, R)$$

◄

**Proof for order-based semantics.** Let $S$ be an order-based semantics defined by ordering $\leq$ (see Def. 11). Let $R$ be a regular expression and $D, D'$ two databases such that $D \subseteq D'$. Let $w$ be a walk between some vertices $s$ and $t$ in $S(D', R) \cap \text{Walks}(D)$. By definition, $w \in \min_{\leq}(\text{Matches}(D', R, s, t))$. But since $w \in \text{Walks}(D)$, we also have $w \in \text{Matches}(D, R)$. There can be no $w' \prec w$ in $\text{Matches}(D, R)$, otherwise $w$ would not be minimal in $\text{Matches}(D', R, s, t)$ either. Therefore $w \in \min_{\leq}(\text{Matches}(D, R, s, t))$, in other words $w \in S(D, R)$. ◄

We expect all “reasonable” semantics to be co-monotonous. In fact, semantics that are not co-monotonous are usually quite strange, as illustrated below.

**► Example 28 (Log-length semantics).** The log-length semantics LL returns all matches that are shorter than $\log_2(|D|)$. This semantics has the property that the size of $LL(D, R)$ is always polynomial in the size of $D$. It is not co-monotonous since doubling the size of $D$ (for instance by adding enough isolated vertices) may return longer walks which do not necessarily use the new isolated vertices. Note however that LL is monotonous, since no previous result may disappear when enriching the database.

Although LL is not walk-based, one could consider a variant that is. Indeed, it could return the walks shorter than $\log_2(|X(D, R)|)$, where $X(D, R)$ is the set of all edges appearing in some walk in $\text{Matches}(D, R)$.

As for monotony, the landscape is more interesting. We already saw that all filter-based semantics are monotonous (Lemma 27). However, it is notable that shortest semantics is not.

**► Lemma 29.** Sh is not monotonous.

**Proof.** Let $D$ be a database consisting of three vertices $v_1, v_2$ and $v_3$ and two edges $v_1 \xrightarrow{a} v_2$ and $v_2 \xrightarrow{a} v_3$, and let $R = aa + b$ where $a, b \in \mathbb{L}$. Hence $S(D, R) = \{v_1 \xrightarrow{e_1} v_2 \xrightarrow{e_2} v_3\}$. Then, let $D'$ be the database $D'$ resulting from adding in $D$ a new fresh edge $v_1 \xrightarrow{b} v_3$. Hence $S(D', R) = \{v_1 \xrightarrow{b} v_3\}$ which is not a superset of $S(D, R)$. ◄

At first glance, it may seem that all order-based semantics $S_{\leq}$ are bound to be non-monotonous, since it is enough to make a shortcut (w.r.t $\leq$) using new vertices and edges. However, one may show that the (order-based) subwalk-minimal semantics SM (Def. 14) is indeed monotonous. More generally, let us now characterize monotonous order-based semantics using a notion of element inclusion (Proposition 30). In the following, we denote by $\text{VertSet}(w)$ (resp. $\text{EdgeSet}(w)$) the set of vertices (resp. of edges) occurring in $w$. We also use $\text{ElemSet}(w)$ (resp. $\text{ElemBag}(w)$) to denote the set (resp. the bag) of vertices and edges appearing in $w$. We say that an order $\leq$ on Walks respects element inclusion if $w \leq w'$ implies $\text{ElemSet}(w) \subseteq \text{ElemSet}(w')$.
**Proposition 30.** Let $S_{\leq}$ be a semantics based on a trimmed order $\leq$. Then $\leq$ respects element inclusion iff $S_{\leq}$ is monotonous.

**Proof of Proposition 30, forward direction.** For the sake of contradiction, let us assume there are a query $R$, two databases $\mathcal{D} \subseteq \mathcal{D}'$ and a walk $w$ that belongs to $S(\mathcal{D}, R)$ but not to $S(\mathcal{D}', R)$. This means there is a walk $w' \in S(\mathcal{D}', R)$ satisfying $w' \prec w$. It follows from hypotheses that $\text{ElemSet}(w') \subseteq \text{ElemSet}(w)$ hence that $w' \in \text{Walks}(\mathcal{D})$. Since $S$ is co-monotonous (Lemma 27) $w' \in S(\mathcal{D}, R)$. Hence $w \notin S(\mathcal{D}, R)$, a contradiction. ◀

The proof of the backward direction requires some extra machinery (Definition 31) that will also be useful in future proofs.

**Definition 31 (Characteristic database, characteristic expression).** For simplicity, we will consider in the following that $\mathbb{E} \subseteq \mathbb{L}$, i.e. that edge identifiers are possible labels. To be formally correct, we would need to use some arbitrary bijection $\mathbb{E} \to \mathbb{L}$, but we prefer to leave it implicit.

1. Let $w_1, \dots, w_k$ be consistent walks. Let $\mathcal{D}$ be any database such that $\{w_1, \dots, w_k\} \subseteq \text{Walks}(\mathcal{D})$, and

$$V = \text{VertSet}(w_1) \cup \dots \cup \text{VertSet}(w_k)$$

$$E = \text{EdgeSet}(w_1) \cup \dots \cup \text{EdgeSet}(w_k)$$

Note that $V \subseteq V_{\mathcal{D}}$ and $E \subseteq E_{\mathcal{D}}$. The characteristic database of $\{w_1, \dots, w_k\}$ is the database

$$C_{w_1, \dots, w_k} = (L, V, E, \text{Src}, \text{Tgt}, \text{ Labl})$$

where $L = E$, $ Labl$ is the identity function, and $ \text{Src} $ (resp. $ \text{Tgt} $) is the restriction of $ \text{Src}_{\mathcal{D}} $ (resp. $ \text{Tgt}_{\mathcal{D}} $) to $ E $.

(One may verify that $C_{w_1, \dots, w_k}$ is independent of the database $\mathcal{D}$ chosen.)

2. Let $w$ be a walk of positive length $k$. Then we denote by $P_w$ the characteristic regular expression of $w$, defined as $P_w = w[1] \cdots w[k]$.

Intuitively, the characteristic database of a finite set of compatible walks is just the smallest database containing them all, i.e., $\{w_1, \dots, w_k\} \subseteq \text{Walks}(C_{w_1, \dots, w_k})$, and in which edges are labeled with their own identifier. The characteristic expression of a walk is just the sequence of its edge identifiers.

These definitions are chosen in such a way that the characteristic expression of each $w_i$ of positive length is matched exactly once ($\text{Matches}(C_{w_1, \dots, w_k}, P_{w_i}) = \{w_i\}$) and that the characteristic expression of any other walk of positive length is matched either once or not at all: $\text{Matches}(C_{w_1, \dots, w_k}, P_w)$ is either empty or equal to $\{w\}$.

We can now show that if an order-based semantics is monotonous, then the corresponding order preserves element inclusion.

**Proof of Proposition 30, backward direction.** Let $S_{\leq}$ be a monotonous semantics based on a trimmed order $\leq$.

Let $w$ and $w'$ be two walks such that $w \prec w'$. First, let us address the case where $\text{Len}(w) = 0$, in which case $\text{ElemSet}(w) = \{v\}$ for some vertex $v$. Since $\leq$ is trimmed, $w$ and $w'$ have the same endpoints. It follows that $v = \text{Src}(w') = \text{Tgt}(w')$ hence $\text{ElemSet}(w) \subseteq \text{ElemSet}(w')$.
Second, assume that $Len(w) > 0$. Since $\leq$ is trimmed, $w$ and $w'$ are consistent, which means in particular that the two databases $C_{w'}$ and $C_{w,w'}$ are well defined. Let us moreover consider the following query

$$R = \begin{cases} P_w + P_{w'} & \text{if } Len(w') > 0 \\ P_w + \varepsilon & \text{if } Len(w') = 0 \end{cases} \qquad (3)$$

Note that Matches($C_{w,w'}$, $R$) $\supseteq \{w, w'\}$, and that the inclusion might be strict when $Len(w') = 0$ because $\varepsilon$ will match every walk of length 0. Since $w < w'$, this implies that $w' \notin S(C_{w,w'}, R)$, and therefore, due to the monotony of $S$, that

$$w' \notin S_{\leq}(C_{w'}, R). \qquad (4)$$

If $w'$ were of length 0, then $C_{w'}$ would consist of a single isolated vertex. Therefore, since $Len(w) > 0$, $w$ is not a walk in $C_{w'}$. Hence we would have Matches($C_{w'}$, $R$) = $\{w'\}$ and thus $w' \in S_{\leq}(C_{w'}, R)$, a contradiction to (4). It follows that $w'$ must have a positive length, which means that Matches($C_{w,w'}$, $R$) = $\{w, w'\}$. Since Matches($C_{w'}$, $R$) $\subseteq$ Matches($C_{w,w'}$, $R$) = $\{w, w'\}$, Equation (4) implies that $w$ must belong to Matches($C_{w'}$, $R$) hence to Walks($C_{w'}$). By definition of the characteristic database, this is true only if ElemSet($w$) $\subseteq$ ElemSet($w'$). $\quad$

Consider the relation $\leq_1$ defined as: $w \leq_1 w'$ if ElemSet($w$) $\subseteq$ ElemSet($w'$). It is not antisymmetric, hence not a partial order. Now consider the relation $\leq_2$ defined as: $w <_2 w'$ if ElemSet($w$) $\not\subseteq$ ElemSet($w'$). Although $\leq_2$ is a partial order, it is not suitable: $\leq_2$ is not a wpo on Walks($D$) whenever $D$ contains a cycle. We give below two examples of semantics based on an order that preserves element inclusion. Example 32 takes multiplicity into account. Example 33 refines $\leq_2$ by adding a tiebreaker for walks with identical element sets.

**► Example 32 (Minimal-multiset semantics MM).** Let MM be the semantics based on the order $\leq$ defined by: $w < w'$ if ElemBag($w$) $\not\subseteq$ ElemBag($w'$). Recall that $\sqsubseteq$ denotes the subwalk order on walks (Def. 14). A simple verification yields that $w \sqsubseteq w'$ $\implies$ $w \leq w'$. Then, $\leq$ is a wpo on Walks($D$) for each database $D$, because so is $\sqsubseteq$ (Lemma 15). Indeed, let $(w_1, w_2, \dots)$ be an infinite sequence of walks in $D$. Since $\sqsubseteq$ is a wpo on $D$, there are $i < j$ such that $w_i \sqsubseteq w_j$, which implies that $w_i \leq w_j$.

**► Example 33 (Shortest-minimal-set semantics ShMS).** Let ShMS be the semantics based on the order $\leq$ defined by:

$$w < w' \iff \begin{cases} \text{either } ElemSet(w) \not\subseteq ElemSet(w') \\ \text{or } ElemSet(w) = ElemSet(w') \text{ and } Len(w) < Len(w') \end{cases}$$

The semantics MM and ShMS are finite, identifier-independent and restrictible. The complexity of query evaluation under them is explored in [Mar24] and recalled in Figure 2, page 25.

## 4.3 Continuity

In this section, we attempt to capture the property for a semantics $S$ to behave “reasonably” at the limit. Essentially, the sequence $(S(D, a + a^2 + \dots + a^k))_{k \in \mathbb{N}}$ should tend to $S(D, a^*)$ when $k$ tends to $\infty$. More precisely, results of non-decreasing sequences of RPQs (with respect to language inclusion) should eventually stabilize to some fixed set $W$, and furthermore whenever the whole sequence is captured by a single RPQ, then the set of results over that
RPQ should be W itself. These conditions prevent S to change gears and arbitrarily alter the set of results when moving to the limit. As we show below, it turns out that all filter-based and all order-based semantics possess these properties.

**Definition 34.** A semantics $S$ is said to be **stabilizing** if, for every database $\mathcal{D}$ and every sequence of regular expressions $(R_i)_{i \in \mathbb{N}}$ such that $(L(R_i))_{i \in \mathbb{N}}$ is non-decreasing, $(S(\mathcal{D}, R_i))_{i \in \mathbb{N}}$ is ultimately equal to some set $W$, and we say that $(S(\mathcal{D}, R_i))_{i \in \mathbb{N}}$ stabilizes to $W$.

Moreover, when $S$ is stabilizing, it is said to be **continuous** if, whenever there exists a sequence of regular expressions $(R_i)_{i \in \mathbb{N}}$ as above and a regular expression $R_\infty$ such that $L(R_\infty) = \bigcup_{i \in \mathbb{N}} L(R_i)$, it holds that $W = S(\mathcal{D}, R_\infty)$.

**Proposition 35.** All order-based and filter-based semantics are continuous.

**Proof for filter-based semantics.** Let $S$ be a semantics based on a filter $f$, and let $\mathcal{D}$ be a database. The function $F$ that maps every $W \subseteq \text{Walks}(\mathcal{D})$ to $\{w \in W \mid f(w) = \top\}$ is monotonous. Also note that $F(\text{Walks}(\mathcal{D}))$ is finite, otherwise $S(\mathcal{D}, \Sigma^*)$ would not be. It follows that $S$ is stabilizing and continuous. ◀

The proof for order-based semantics requires more care. We first prove that all order-based semantics are stabilizing (Lemma 36).

**Lemma 36.** All order-based semantics are stabilizing.

**Proof.** Consider an order-based semantics $S_\leq$, a sequence $(R_i)_{i \in \mathbb{N}}$ as in the statement of Definition 34 and a database $\mathcal{D}$, and let $\bar{M}_i = \text{Matches}(\mathcal{D}, R_i)$ and $S_i = S_\leq(\mathcal{D}, R_i)$. Since $(M_i)_{i \in \mathbb{N}}$ is non-decreasing and by definition of the $S_i$, we have

$$ \begin{array}{c|ccccccc} M_0 & \subseteq & M_1 & \subseteq & \cdots & \subseteq & M_i & \subseteq & \cdots \\ \cup & & \cup & & & & \cup & & \\ S_0 & & S_1 & & & & S_i & & \end{array} \qquad (5) $$

This implies in particular that $\bigcup_{j=0}^i S_j \subseteq \bigcup_{j=0}^i M_j \subseteq M_i$, for every $i \in \mathbb{N}$.

First, we claim that for every $i$ such that $S_{i+1} \neq S_i$, there exists a walk $w \in (S_{i+1} \setminus S_i)$. Since $S_{i+1} \neq S_i$, we have $(S_{i+1} \setminus S_i) \neq \emptyset$ or $(S_i \setminus S_{i+1}) \neq \emptyset$. In the first case, the claim immediately holds. In the second case, let $w'$ be some walk in $S_i \setminus S_{i+1}$. Since $w' \in S_i \subseteq M_i \subseteq M_{i+1}$ but $w' \notin S_{i+1}$, there must be a walk $w$ in $S_{i+1}$ such that $w \prec w'$. This walk cannot belong to $S_i$, otherwise $w'$ would not either. This concludes the proof of the claim.

Second, we claim that for every integer $i$ and walk $w$ such that $w \in (S_{i+1} \setminus S_i)$, there is no $w' \in \bigcup_{j=0}^i S_j$ such that $w' \preceq w$. By definition, since $w \in S_{i+1}$, then $w$ is minimal in $M_{i+1}$. It follows from (5) that $w$ is incomparable to or smaller than every element in $M_j$ (resp. in $S_j$), for every $j \leq i$ ($\ast$). It follows that the walk $w$ cannot be in $M_i$, otherwise it would also belong to $S_i$, a contradiction to its definition. We then deduce from (5) that for all $j \leq i$, $w \notin S_j$ ($\ast\ast$). This concludes the proof of the claim: any $w'$ as in the claim would either be equal to $w$, a contradiction to ($\ast\ast$), or distinct from $w$, a contradiction to ($\ast$).

Finally, if $(S_i)_{i \in \mathbb{N}}$ were not eventually constant, we could apply the two claims above on indices $i$ such that $S_{i+1} \neq S_i$. This yields a sequence of walks $(w_k)_{k \in \mathbb{N}}$ such that for each $k < k'$, it does not hold that $w_k \preceq w_{k'}$, a contradiction to the fact that $\preceq$ is a well-partial-order on Walks($\mathcal{D}$). ◀
**Proof of Proposition 35 for order-based semantics.** Let $S_{\leq}$ be an order-based semantics, $\mathcal{D}$ a database, $(R_i)_{i \in \mathbb{N}}$ a sequence of regular expressions such that $(L(R_i))_{i \in \mathbb{N}}$ is non-decreasing, and $R_\infty$ and expression such that $L(R_\infty) = \bigcup_{i \in \mathbb{N}} L(R_i)$. Since $S_{\leq}$ is stabilizing, there is a set $W$ and a bound $b$ such that for every $n > b$, $S(\mathcal{D}, R_n) = W$. We have to show that $S(\mathcal{D}, R_\infty) = W$, which follows from the fact that the following two statements are equivalent for every walk $w$:

- $w \in \text{Matches}(\mathcal{D}, R_\infty)$ and there exists $w' \in \text{Matches}(\mathcal{D}, R_\infty)$ such that $w' \prec w$;

- there exists an index $n > b$ and a walk $w'$ such that $w \in \text{Matches}(\mathcal{D}, R_n)$, $w' \in \text{Matches}(\mathcal{D}, R_n)$ and $w' \prec w$.

This equivalence follows from the definitions of the $R_i$'s and $R_\infty$. ◀

We expect any "reasonable" (walk-based) semantics to be continuous. Indeed, a non-continuous walk-based semantics must treat finite sets and infinite sets differently. To give the reader a flavor of what non-continuous semantics might look like, we give below two toy examples: a non-stabilizing semantics and a stabilizing but non-continuous semantics.

**► Example 37 (Giving-Up Semantics).** Most semantics presented in this document are designed to return at least one walk between each pair of vertices for which there is a match, even in cases where there are actually infinitely many such matches. In contrast, let $\text{GU}(\mathcal{D}, R)$ be the semantics which returns the whole set $\text{Matches}(\mathcal{D}, R)$ if this set is finite, and the empty set of walks otherwise. This implies that $\text{GU}(\mathcal{D}, R)$ is always a finite set.

Given expressions $(R_i = a^{\leq i})_{i \in \mathbb{N}}$ (each matching all walks labeled by some word $a^j$ with $j \leq i$), if $\mathcal{D}$ contains an $a$-labeled loop $e$ from some vertex $v$ to itself, then each $\text{GU}(\mathcal{D}, R_i)$ contains the new walk $(ve)^i v$. Hence $\text{GU}$ is clearly not stabilizing (and thus not continuous: note that in the above case $\text{GU}(\mathcal{D}, a^*) = \emptyset$).

$\text{GU}$ seems too bizarre to be interesting. But one may define variants which still have interesting properties. For instance, consider the semantics $\text{GU}'$, defined as follows. For a given set of elements $X$ and two vertices $s$ and $t$, let us denote by $\text{Matches}_X(\mathcal{D}, R, s, t)$ the set of matches $w$ for $R$ in $\mathcal{D}$ with $\text{EndP}(w) = (s, t)$ and $\text{ElemSet}(w) \subseteq X$. Let $\mathcal{T}$ be the set of all triples $(X, s, t)$ such that $\text{Matches}_X(\mathcal{D}, R, s, t)$ is finite. In other words, the walks whose set of elements support infinitely many other matches for $R$ are not returned as results. Then,

$$ \text{GU}'(\mathcal{D}, R) = \bigcup_{(X,s,t) \in \mathcal{T}} \text{Matches}_X(\mathcal{D}, R, s, t). \qquad (6) $$

Since $\mathcal{T}$ is finite, this semantics is finite by definition. It can be shown that it is in fact also walk-based and restrictible.

Semantics that are stabilizing but non-continuous are even stranger. The typical example is a semantics that changes behaviour in the presence of an infinite set.

**► Example 38 (Stabilizing non-continuous semantics).** Let $S$ be the semantics defined by:

$$ S(\mathcal{D}, R) = \begin{cases} \text{Sh}(\mathcal{D}, R) & \text{if } \text{Matches}(\mathcal{D}, R) \text{ is finite,} \\ \text{Tr}(\mathcal{D}, R) & \text{if } \text{Matches}(\mathcal{D}, R) \text{ is infinite.} \end{cases} \qquad (7) $$

It is stabilizing because, for every sequence of regular expressions $(R_i)_{i \in \mathbb{N}}$ such that $(L(R_i))_{i \in \mathbb{N}}$ is non-decreasing, the sequence $(\text{Matches}(\mathcal{D}, R_i))_{i \in \mathbb{N}}$ either contains only finite sets, or there is a bound $b$ such that $\text{Matches}(\mathcal{D}, R_i)$ is finite only if $i \leq b$. In both cases, $(S(\mathcal{D}, R_i))_{i \in \mathbb{N}}$ stabilizes because both $\text{Sh}$ and $\text{Tr}$ do. It is not continuous, as can be seen by considering the sequence $(a^{\leq i})_{i \in \mathbb{N}}$ and the limit expression $a^*$.
Other examples of stabilizing non-continuous semantics can be built as variants of other semantics in which we add a condition about the infiniteness of the set of matches. For instance, given any order-based semantics $S_{\leq}$, the semantics $S'_{\leq}$ defined below returns only those walks which are smaller than infinitely many walks with respect to $\leq$:

$$S'_{\leq}(\mathcal{D}, R) = \{w \in S_{\leq}(\mathcal{D}, R) | \exists \text{ infinitely many } w' \in \text{Matches}(\mathcal{D}, R) \text{ such that } w \leq w'\}$$

It is stabilizing because $S_{\leq}$ is, and the usual sequence of expressions $(a^{\leq i})_{i \in \mathbb{N}}$ with limit expression $a^*$ shows that it is not continuous.

## 4.4 Compatibility with rational operators

In this section we study interactions between the structure of an RPQ as a regular expression and the set of results. We define in particular the notions of composability and decomposability of a semantics with respect to a given RPQ operator. The intuition behind composability, stated in the case of concatenation, is as follows. A semantics is $\cdot$-decomposable if any result for $R \cdot R'$, that is a walk $w$ in $S(D, R \cdot R')$, can be decomposed into a result for $R$ and a result for $R'$. This means that there exist $w' \in S(D, R)$ and $w'' \in S(D, R')$ such that $w = w' \cdot w''$. Conversely, a semantics $S$ is $\cdot$-composable if the results for $R$ and $R'$ can be composed freely into (some of the) results for $R \cdot R'$. These notions are defined in more detail below.

**Definition 39.** We say that $S$ is $\cdot$-composable (resp. $\cdot$-decomposable) if Equation (8) (resp. Equation (9)), below, holds for every database $\mathcal{D}$ and RPQs $R, R'$.

$$S(\mathcal{D}, R \cdot R') \supseteq S(\mathcal{D}, R) \cdot S(\mathcal{D}, R') \qquad (8)$$

$$S(\mathcal{D}, R \cdot R') \subseteq S(\mathcal{D}, R) \cdot S(\mathcal{D}, R') \qquad (9)$$

If both (8) and (9) hold, we say that $S$ is **compatible with $\cdot$**, or **$\cdot$-compatible** for short. Similarly, we define **$+$-composability**, **$+$-decomposability**, **$+$-compatibility** from (10), below.

$$S(\mathcal{D}, R + R') \supseteq S(\mathcal{D}, R) \cup S(\mathcal{D}, R') \quad \text{and/or} \quad S(\mathcal{D}, R + R') \subseteq S(\mathcal{D}, R) \cup S(\mathcal{D}, R') \quad (10)$$

and **$*$-composability**, **$*$-decomposability**, **$*$-compatibility** from (11) below.

$$S(\mathcal{D}, R^*) \supseteq (S(\mathcal{D}, R))^* \quad \text{and/or} \quad S(\mathcal{D}, R^*) \subseteq (S(\mathcal{D}, R))^* \qquad (11)$$

Finally, we say that a semantics is **decomposable** if it is decomposable w.r.t. $\cdot$, $+$ and $*$.

**Definition 40.** We say that a semantics $S$ is **compatible with atoms**, or $a$-compatible, if $S(\mathcal{D}, a) = \text{Matches}(\mathcal{D}, a)$, for every $a \in \mathbb{L}$ and database $\mathcal{D}$.

We give below several statements regarding compatibility with rational operators. First, Lemma 41 states that all filter-based and order-based semantics are $\cdot$-decomposable, and that $\cdot$-composability is essentially equivalent to being filter-based.

**Lemma 41 (Compatibility with $+$).** 1. Every filter-based semantics is $\cdot$-compatible.

2. Every order-based semantics is $\cdot$-decomposable but not $\cdot$-composable.

3. For every $\cdot$-compatible semantics $S$, there exists a filter-based semantics $S'$ such that for every database $\mathcal{D}$, regular expression $R$ and walk $w$ **of positive length**: $w \in S(\mathcal{D}, R)$ iff $w \in S'(\mathcal{D}, R)$.
**Proof of Item 1.** This directly follows from definitions. Let $S_{\leq}$ be a filter-based semantics defined by filter $f$. For $+\text{-decomposability}$, consider any $R, R'$ and $\mathcal{D}$. If some walk $w$ labeled by $u$ is in $S(\mathcal{D}, R+R')$, then $f(w)$ holds, and either $u \in L(R)$ or $u \in L(R')$. Therefore either $w \in S(\mathcal{D}, R)$ or $w \in S(\mathcal{D}, R')$ (or both).

For $+\text{-composability}$, consider RPQs $R$ and $R'$ and some database $\mathcal{D}$. For any walk $w \in S(\mathcal{D}, R)$, i.e. such that $\text{ Label}(w) \in R$ and $f(w)$ holds, $w$ is also, by definition, in $S(\mathcal{D}, R+R')$ since $\text{ Label}(w) \in L(R+R')$. This holds similarly for any $w' \in S(\mathcal{D}, R')$. $\quad \triangleleft$

**Proof of Item 2.** Let $S_{\leq}$ be an order-based semantics. For $+\text{-decomposability}$, consider any $R, R'$ and $\mathcal{D}$. If some walk $w$ labeled by $u$ is in $S(\mathcal{D}, R+R')$, then $w$ is minimal w.r.t. $\leq$ among walks in Matches($\mathcal{D}, R+R'$). Since both Matches($\mathcal{D}, R$) and Matches($\mathcal{D}, R'$) are subsets of Matches($\mathcal{D}, R+R'$), $w$ is not strictly greater than any walk in those sets. Furthermore, $u \in L(R)$ or $u \in L(R')$. Therefore, $w \in S(\mathcal{D}, R)$ or $w \in S(\mathcal{D}, R')$.

To show that $S$ is not $+\text{-composable}$, consider a database $\mathcal{D}$ consisting of a vertex $v$ and a loop $v \xrightarrow{e} v$ labeled by some $a \in \mathbb{L}$. We let $w$ denote the walk $v \xrightarrow{e} v$, hence $w^i$ is well defined. Since $\leq$ is a wpo on Walks($\mathcal{D}$) then there exist distinct $i, j$ such that $w^i < w^j$. Hence $S(\mathcal{D}, a^i + a^j) = \{a^i\} \not\subseteq \text{eq}(S(\mathcal{D}, a^i) \cup S(\mathcal{D}, a^j))$. $\quad \triangleleft$

**Proof of Item 3.** Let us define the filter $f$ as follows. We use the notion and notation of characteristic database $C_w$ and regular expression $P_w$ (Def. 31). Each walk $w$ that is **not** self-consistent is mapped to $\perp$. Any self-consistent walk $w$ is mapped to $\top$ if $S(C_w, P_w) = \{w\}$, and to $\perp$ otherwise. Let $\mathcal{D}$ be a database and $R$ an RPQ. Let us show that a walk $w \in \text{Matches}(\mathcal{D}, R)$ of positive length is in $S(\mathcal{D}, R)$ if and only if $f(w) = \top$.

Let $w$ be a walk of positive length in Matches($\mathcal{D}, R$) and we write $u = \text{ Label}_{\mathcal{D}}(w)$. The language $L(R) - \{u\}$ is regular hence is denoted by a regular expression $R'$. Since $S$ is walk-based, we have the following.

$$ w \in S(\mathcal{D}, R) \iff w \in S(\mathcal{D}, R' + u) \qquad (12) $$

Note in particular that $w \notin \text{Matches}(\mathcal{D}, R')$, hence $+\text{-compatibility}$ of $S$ yields the following.

$$ w \in S(\mathcal{D}, R' + u) \iff w \in S(\mathcal{D}, u) \qquad (13) $$

Let $w_1, \dots, w_k$ be all the (finitely many) walks in Matches($\mathcal{D}, u$); hence $w_i = w$ for some $i$. All these walks have the same length, and since $w$ is among them, they have positive length. Let us now consider the database $\mathcal{D}'' = C_{w_1, \dots, w_k}$, and regular expression $R'' = \sum_{i=0}^k P_{w_i}$. In particular, Matches($\mathcal{D}''$, $R''$) = $\{w_1, \dots, w_k\}$ hence $S(\mathcal{D}, u) = S(\mathcal{D}''$, $R''$), which implies the following.

$$ w \in S(\mathcal{D}, u) \iff w \in S(\mathcal{D}'', R'') \qquad (14) $$

Finally, an easy induction using $+\text{-compatibility}$ of $S$ yields the following.

$$ w \in S \left( C_{w_1, \dots, w_k}, \sum_{i=0}^{i} P_{w_i} \right) \iff w \in S(C_{w_1, \dots, w_k}, P_w) \iff f(w) = \top \qquad (15) $$

$\quad \triangleleft$

**Remark 42.** The equivalence in the statement of Item 3 is not true for walks of length 0. Indeed, consider a semantics $S$ defined as follows. We denote by Walks$_0(\mathcal{D})$ the walks in Walks$_0(\mathcal{D})$ of length 0. Then, we define $S(\mathcal{D}, R) = \text{Walks}_0(\mathcal{D})$ if $\varepsilon \in L(R)$ and $\mathcal{D}$ has an even number of vertices; or $S(\mathcal{D}, R) = \emptyset$ otherwise. It may be checked that $S$ is walk-based and $+\text{-compatible}$, although it is clearly not filter-based.
As hinted previously, the two families of filter-based and order-based semantics are disjoint. It indeed follows from items 1 and 2 of Lemma 41.

**► Corollary 43.** *There is no semantics S that is both order-based and filter-based.*

Next, we state in Lemmas 44 and 45 that no order-based or filter-based semantics is --composable or *-composable, under very weak requirements.

**► Lemma 44 (Composability with $\cdot$).**
1. *No order-based semantics is --composable.*
2. *No identifier-independent, unbounded, filter-based semantics is --composable.*

**Proof of Item 1.** Consider a semantics $S$ based on some well-partial-order $\leq$ and the database $\mathcal{D}$ shown below (edge identifiers are not important).

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

Consider the RPQ $R = a(bc)^*d$. All matches of $R$ between $v_1$ and $v_4$ are labeled by $a(bc)^id$ for some $i$, and for every $i$ there is a single such match, which we call $w_i$. By definition, $S(\mathcal{D}, R)$ is the finite and non-empty subset of $\leq$-minimal elements of $\{w_i | i \geq 0\}$. Therefore, there must exist $n, k \geq 0$ such that $w_n < w_{n+k+1}$. Indeed, choose $m$ such that $w_m$ is the longest walk in $S(\mathcal{D}, R)$, hence $w_{m+1}$ does belong to Matches($\mathcal{D}, R$) but not to $S(\mathcal{D}, R)$. Hence $S(\mathcal{D}, R)$ must contain some $w_n$ with $n < m$ such that $w_n < w_{n+k}$, and finally fix $k = m - n$.

We now define the queries $R_1 = a(bc)^n(b+\varepsilon)$ and $R_2 = (c(bc)^k+\varepsilon)d$. $R_1$ has exactly two matches, the walk $u$ between $v_1$ and $v_2$ labeled $a(bc)^n$ and the walk $u'$ between $v_1$ and $v_3$ labeled $a(bc)^nc$. Since these two walks have different target, they both belong to $S(\mathcal{D}, R_1)$. Similarly, $R_2$ has exactly two matches, the walk $v$ between $v_2$ and $v_4$ labeled $d$ and the walk $v'$ between $v_3$ and $v_4$ labeled $c(bc)^kd$. Similarly, these two walks belong to $S(\mathcal{D}, R_2)$ because they have a different source.

If $S$ were --composable, then both $uv = w_n$ and $u'v' = w_{n+k+1}$ would be in $S(\mathcal{D}, R_1 \cdot R_2)$, which contradicts the fact that $w_n < w_{n+k+1}$. ◀

**Proof of Item 2.** Let $S$ be an identifier-independent unbounded semantics based on filter function $f$. Let $\mathcal{D}, R$ be such that $S(\mathcal{D}, R)$ contains some walk $w$ satisfying $\text{Len}(w) > 0$. Note that $w$ is a self-consistent walk such that $f(w) = \top$. Let $\nu$ be any renaming such that $\nu(\text{Src}(w)) = \text{Tgt}(w)$, $\nu(\text{Tgt}(w)) = \text{Src}(w)$ and $\nu(X) \cap X = \emptyset$, where:

$$X = (V_{\mathcal{D}} \cup E_{\mathcal{D}}) - \{\text{Src}(w), \text{Tgt}(w)\} \qquad (16)$$

The walk $w' = \nu(w)$ belongs to $\nu(\mathcal{D})$ and since $S$ is identifier-independent, $w' \in S(\nu(\mathcal{D}), R)$. Note that $w$ and $w'$ are consistent since they have no edge in common, and both are self-consistent. Also note that $w \cdot w'$ and $w' \cdot w$ are both well-defined. Hence, the characteristic database $C_{w,w'}$ (Def. 31) exists and contains the walks $(w \cdot w')^i$ for every $i \in \mathbb{N}$. If $P_w$ and $P_{w'}$ are the characteristic expressions of $w$ and $w'$ respectively (Def. 31), then $S(C_{w,w'}, P_w) \supset w$ and $S(C_{w,w'}, P_{w'}) \supset w'$. Let us assume for the sake of contradiction that $S$ is --composable. Then, $S(C_{w,w'}, R_i) \supset ((w \cdot w')^i)$ for some expression $R_i$ consisting of concatenations of $P_w$ and $P_{w'}$. Hence $f((w \cdot w')^i) = \top$ for every $i \in \mathbb{N}$, which implies that $S(C_{w,w'}, (P_w P_{w'})^*)$ is infinite, a contradiction. ◀
► **Lemma 45** (Composability with *). 1. No order-based semantics is *-composable.

2. No identifier-independent, unbounded, filter-based semantics is *-composable.

**Proof of Item 1.** Consider the database $\mathcal{D}$ with one vertex $v$ and one edge $e$ labeled by $a$ from $v$ to $v$. Then, by definition of an order-based semantics, $S(\mathcal{D}, a) = \{v \underset{e}{\to} v\}$ and by *-composability, $S(\mathcal{D}, a^*)$ is infinite, a contradiction. ◀

**Proof of Item 2.** For the sake of contradiction, let $S$ be a semantics that satisfies all four properties of the statement. By hypothesis, there is a database $\mathcal{D}$ and an RPQ $R$ such that $w \in S(\mathcal{D}, R)$ and $\text{Len}(w) \ge 1$. For every edge $e$ in $\mathcal{D}$, let $\bar{e}$ be a fresh identifier (i.e., in $\mathbb{E} \setminus E$), and for every vertex $v$ in $\mathcal{D}$, let $\bar{v}$ be defined as follows.

$$ \bar{v} = \begin{cases} s & \text{if } v = t \\ t & \text{if } v = s \\ \multicolumn{2}{c}{\text{a fresh identifier in } \mathbb{V} \setminus \mathbb{V} \text{ otherwise}} \end{cases} \qquad (17) $$

We then define the database $\mathcal{D}' = (L_{\mathcal{D}'}, V_{\mathcal{D}'}, E_{\mathcal{D}'}, \text{Src}_{\mathcal{D}'}, \text{Tgt}_{\mathcal{D}'}, \text{上年}_{\mathcal{D}'})$ as follows:

$$ \begin{array}{ll} L_{\mathcal{D}'} = L_{\mathcal{D}} & \text{Src}_{\mathcal{D}'} : e \mapsto \begin{cases} \text{Src}_{\mathcal{D}}(e) & \text{if } e \in E_{\mathcal{D}} \\ \text{Src}_{\mathcal{D}}(e) & \text{if } e \in \overline{E_{\mathcal{D}}} \end{cases} \\ V_{\mathcal{D}'} = V_{\mathcal{D}} \cup \overline{V_{\mathcal{D}}} & \text{Tgt}_{\mathcal{D}'} \text{ is defined similarly} \\ E_{\mathcal{D}'} = E_{\mathcal{D}} \cup \overline{E_{\mathcal{D}}} & \text{上年}_{\mathcal{D}'} : e \mapsto \begin{cases} \text{上年}_{\mathcal{D}}(e) & \text{if } e \in E_{\mathcal{D}} \\ \text{上年}_{\mathcal{D}}(f) & \text{if } e = \bar{f} \text{ and } f \in E_{\mathcal{D}} \end{cases} \end{array} $$

We lift $\bar{\cdot}$ to walks. Note that the database $\mathcal{D}'$ contains the walk $\bar{w}$ which: starts in $t$, ends in $s$, has the same label as $w$, and is equal to $w$ up to renaming. Therefore $w \cdot \bar{w}$ is a cycle around $s$ with label $uu$ in $\mathcal{D}'$. Since $w$ and $\bar{w}$ are equal up to renaming and $S$ is identifier-independent, $f(\bar{w}) = f(w) = \top$. Hence $\{w, \bar{w}\} \subseteq S(\mathcal{D}', R)$. Since $S$ is *-composable and $w \cdot \bar{w}$ is a cycle, the set $\{w, \bar{w}\}^*$ is infinite and is a subset of $S(\mathcal{D}', R^*)$, which is a contradiction. ◀

We conjecture that no “reasonable” semantics is composable w.r.t. $\cdot$ nor $*$-composable. However, it is not easy to define the minimal set of “reasonable” properties that implies *-non-composability or *-non-composability.

To conclude this section, Proposition 46 below summarizes properties regarding the compatibilities of some of the semantics defined in the previous sections.

► **Proposition 46.** Among the different composability and decomposability properties, only the following hold for the mentioned semantics:

1. Ac is only $+$-compatible and $(\cdot, \cdot)$-decomposable.

2. Tr and SWC are only $(a, +)$-compatible and $(\cdot, \cdot)$-decomposable.

3. Sh, SM, MM are only $a$-compatible and $(\cdot, +, \cdot)$-decomposable.

4. BT is only $(a, \cdot, +)$-compatible and $*$-decomposable.

Recall that BT is not walk-based (Ex. 19), hence although it is $*$-composable (item 4), it is not a counterexample to our conjecture that any “reasonable” walk-based semantics cannot be $*$-composable.
<figure><img src="image_10.png" /><figcaption>Figure 1 Inclusions of main semantics</figcaption></figure>

## 4.5 Inclusion of semantics

**Definition 47.** Given two semantics $S_1, S_2$, we say that $S_1$ is included in $S_2$, and denote by $S_1 \subseteq S_2$, if it holds $S_1(\mathcal{D}, R) \subseteq S_2(\mathcal{D}, R)$ for every database $\mathcal{D}$ and query $R$. We say that $S_1$ and $S_2$ are incomparable if neither $S_1 \subseteq S_2$ nor $S_1 \supseteq S_2$ hold.

Figure 1 shows the inclusions of the main semantics defined in this document. All inclusions are strict and the absence of a path means that semantics are incomparable. Due to the sheer number of them, we do not include proofs of these claims. All of them are easy, and some may be found in [DFM23], [Mar24] and [Khi24].

**Remark 48.** It is not easy to interpret the fact that two semantics $S_1, S_2$ satisfy $S_1 \subseteq S_2$. It is not always clear whether the results in the difference are mostly meaningful or redundant. Moreover, there are cases where the difference seems very small (e.g., MM and SM) but the complexity of query evaluation is substantially different (see Section 5).

## 4.6 Coverage

Recall that a semantics $S$ returns a finite subset of results $(S(\mathcal{D}, R))$ among the possibly infinite set of matches $(\text{Matches}(\mathcal{D}, R))$. Some information is bound to be lost in the process. Then, an interesting question is to characterize the coverage of a given semantics $S$, by which we mean *how well* $S(\mathcal{D}, R)$ represents $\text{Matches}(\mathcal{D}, R)$. In this section, we present a few possible definitions in an attempt to capture this intuition. On the one hand, coverage can be expressed in terms of vertices (resp. edges) of the database: all vertices (resp. edges) in some match must also appear in some result. On the other hand, coverage may be expressed in terms of subwalks: for every walk $w$ in $\text{Matches}(\mathcal{D}, R)$, the set $S(\mathcal{D}, R)$ must contain at least one subwalk of $w$. Finally, one may be interested in covering the expression instead: if some atom of $R$ is useful to match any walk, then some walk using it must be in $S(\mathcal{D}, R)$.
4.6.1 Vertex and edge coverage

**Definition 49.** A walk w covers a vertex v if v occurs in w. A set of walks W covers v if some walk in W covers v. We say that a semantics S is **vertex-covering** if for every $D, R$ all vertices covered by Matches($D, R$) are also covered by $S(D, R)$.

It can be shown that no filter-based semantics is vertex-covering, and any order-based semantics can be made vertex-covering, at the price of an exponential blow-up in the size of the set of results.

**Lemma 50.** *No filter-based semantics is vertex-covering.*

*Proof.* Consider some semantics $S$ defined by filter function $f$, and let $\mathcal{D}$ be the database containing a single vertex $v$ and a single edge $e$ with label $a$ looping around $v$. The set Matches($\mathcal{D}, a^*$) contains all walks of the form $w_n = v(ev)^n$ for $n \ge 0$. Since $S(\mathcal{D}, a^*)$ has to be finite, there must exist $k$ such that $w_k \notin S(\mathcal{D}, a^*)$, i.e. such that $f(w_k) = \perp$. Since this path is the only match in $\mathcal{D}$ for query $a^k$, $S(\mathcal{D}, a^k)$ must be empty. $S(\mathcal{D}, a^k)$ does not cover $v$ even though Matches($\mathcal{D}, a^k$) does, which shows that $S$ is not vertex-covering. ◀

**Lemma 51.** *For any order-based semantics $S$ based on order $\leq$, there exists a vertex-covering order-based semantics $S'$ based on some order $\leq'$ that is a refinement of $\leq$.*

*Proof.* Let $S$ be a semantics based on the well-partial-order $\leq$. $S$ might fail to be vertex-covering, because for a given database $\mathcal{D}$, vertex $v$ and query $R$ there is no guarantee that $v$ appears in some minimal walk in Matches($\mathcal{D}, R$).

Let us define the order $\leq'$ as: $w \leq' w'$ if both $w \leq w'$ and the sets of vertices appearing in $w$ and $w'$ are equal. In other words, we force walks over distinct sets of vertices to be incomparable. One may easily verify that the order-based semantics $S'$ defined by $\leq'$ is vertex-covering, since for each vertex occurring in Matches($\mathcal{D}, R$) there must exist at least one minimal element in which this vertex appears (actually at least one for each possible set of vertices appearing in a match containing this vertex). ◀

By construction of $\leq'$ in the proof of Lemma 51, one may see that there is an exponential blow-up in the size of the result set in some cases. For instance, over the $a$-labeled $n$-clique with query $a^*$, where the order-based semantics Sh returns a single result per pair of endpoints, the semantics obtained via this construction would return at least one result per non-empty set of vertices.

We now define a vertex-covering semantics which is neither filter-based nor (strictly speaking) order-based, while avoiding the previous blow-up in the size of results.

**Example 52 (Shortest-vertex-cover Semantics).** Let $\leq_{Sh}$ be the order used to define Sh.

$$ \mathrm{ShVC}(\mathcal{D}, R) = \bigcup_{(s,t,v) \in (V_{\mathcal{D}})^3} \min\{w \in \mathrm{Matches}(\mathcal{D}, R) \mid w \text{ starts in } s, \text{ ends in } t \text{ and covers } v\} $$

Note that for each vertex, ShVC returns all minimal-length matches covering this vertex. The complexity of query evaluation under ShVC is studied in [Khi24] and recalled in Figure 2, page 25. The following lemma summarizes some of its other properties.

**Lemma 53.** *ShVC is*

1. identifier-independent and unbounded;

2. neither filter-based nor order-based;

3. co-monotonous, but not monotonous;
4. continuous;

5. a-compatible and θ-decomposable, but not θ-composable for any θ ∈ {·, +, *}.

The proof of Item 1 is trivial. The proof of Item 4 is similar to the proof that all order-based semantics are continuous in Section 4.3.

**Proof of item 2.** Consider database $\mathcal{D}$ defined by the graph below:

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

For simplicity, we can identify each edge with its label. Consider the three queries and three walks below.

$$R_1 = ab + aefb \qquad R_2 = cd + aefb \qquad R_3 = ab + cd + aefb \qquad (18)$$

$$w_1 = v_1av_2bv_4 \qquad w_2 = v_1cv_3dv_4 \qquad w_3 = v_1av_2ev_3fv_2bv_4 \qquad (19)$$

Clearly, $\text{ShVC}(\mathcal{D}, R_1) = \{w_1, w_3\}$ (*) and $\text{ShVC}(\mathcal{D}, R_2) = \{w_2, w_3\}$ (†). Walk $w_3$ has to be retained in each set because it covers one more vertex than either $w_1$ or $w_2$ alone. Moreover, $\text{ShVC}(\mathcal{D}, R_3) = \{w_1, w_2\}$ (‡) does not contain $w_3$ even though it is also a match for $R_3$, because it is longer than $w_1$ and $w_2$ and covers no additional vertex.

Assume towards a contradiction that ShVC is defined using some order $\leq$. By (*) and (†) it must be that $w_1 \leq w_3$ and $w_2 \leq w_3$. However by (‡) we must have either $w_1 \leq w_3$ or $w_2 \leq w_3$, a contradiction.

Assume now that ShVC is defined using a filter function $f$. We must have $f(w_3) = \top$ by (*), but $f(w_3) = \bot$ by (‡), also a contradiction. ◀

**Proof of item 3.** To show co-monotonicity, suppose there exist $\mathcal{D} \subseteq \mathcal{D}'$, $R$ and $w \in \text{Walks}(\mathcal{D})$ such that $w \notin \text{ShVC}(\mathcal{D}, R)$ (*) but $w \in \text{ShVC}(\mathcal{D}', R)$ (†). By (*), then there must exist $w_1, \dots, w_k \in \text{ShVC}(\mathcal{D}, R)$ covering all vertices of $w$ and of strictly smaller length than $w$. Since $w_1, \dots, w_k$ are matches for $R$ and belong to $\text{Walks}(\mathcal{D}')$, they are in $\text{Matches}(\mathcal{D}', R)$. Therefore, (†) cannot hold.

To show non-monotonicity, consider databases $\mathcal{D}$ and $\mathcal{D}'$ defined by the graphs below:

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

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

and query $R = ab + cd + aed$. Clearly, $\mathcal{D} \subseteq \mathcal{D}'$, and the aed-labeled walk between $v_1$ and $v_4$ belongs to $\text{ShVC}(\mathcal{D}, R)$ but not to $\text{ShVC}(\mathcal{D}', R)$. ◀

**Proof of item 5.** First, let us show that ShVC is *-decomposable. Let $\mathcal{D}$ be a database, $R$ a query and $w$ be any walk in $\text{ShVC}(\mathcal{D}, R^*)$. By definition of ShVC, there exists a vertex $v$ such that $w$ is the shortest among all walks that cover $v$ and match $R$. Since $w \in \text{Matches}(\mathcal{D}, R^*)$, there is a factorization $w = w_1 \cdots w_k$ such that $w_i \in \text{Matches}(\mathcal{D}, R)$ for every $i \in \{1, \dots, k\}$.
For the sake of contradiction, let us assume that $w_i \notin \text{ShVC}(\mathcal{D}, R)$ for some $i$. We consider two cases.

1. If there exists a factor $w_j$ with $j \neq i$ visiting $v$, since $w_i \notin \text{ShVC}(\mathcal{D}, R)$ there must exist a walk $w'_i$ strictly shorter than $w_i$ and with the same endpoints in $\text{ShVC}(\mathcal{D}, R)$. Then, let $w'$ be the walk resulting from substituting $w'_i$ for $w_i$ in the factorization of $w$. The walk $w'$ is a strictly shorter than $w'$, has the same endpoints, has a label in $R^*$ and covers $v$. It is a contradiction to $w \in \text{ShVC}(\mathcal{D}, R^*)$.

2. Otherwise, since $w_i \notin \text{ShVC}(\mathcal{D}, R)$ there must exist some walk $w'_i$ in $\text{ShVC}(\mathcal{D}, R)$ with the same endpoints as $w_i$ covering $v$. We conclude as before by substituting $w'_i$ for $w_i$ in $w$.

Showing that ShVCis --decomposable is similar but easier, and showing that it is +-decomposable is trivial. Non-*-composability is shown using the same argument as Item 1 of Lemma 45.

One may show non-+-composability and non--composability using database $\mathcal{D}'$ from item 3. For non-+-composability, consider queries $R_1 = ab + cd$ and $R_2 = aed$. The walk $w$ between $v_1$ and $v_4$ labeled aed is in $S(\mathcal{D}', R_2)$ but not in $S(\mathcal{D}', R_1 + R_2)$. For non-+-composability, consider queries $R_3 = ae + c$ and $R_4 = b + d$. The walk $w$ between $v_1$ and $v_4$ labeled aed is in $S(\mathcal{D}', R_1) \cdot S(\mathcal{D}', R_2)$ but not in $S(\mathcal{D}', R_1 \cdot R_2)$. ◀

Note that replacing $\leq_{Sh}$ by any suitable order in Example 52 yields a valid RPQ semantics. This opens up a whole new way of defining semantics that we leave for future work.

**Edge Coverage.** The situation with respect to edge coverage is much like the one for vertex coverage. It may be defined similarly, and no semantics defined in this document is edge-covering. A shortest covering semantics, the shortest-edge-cover semantics ShEC, may be defined by adapting Example 52.

### 4.6.2 Subwalk guarantee

**► Definition 54.** A semantics $S$ possesses the **subwalk guarantee** if for every database $\mathcal{D}$, query $R$, and walk $w$ such that $w \in \text{Matches}(\mathcal{D}, R)$ there exists a subwalk of $w$ that belongs to $S(\mathcal{D}, R)$.

This property was introduced in Lemma 13 of [DFM23], which states that BT possesses it. This led to the definition of SM, which possesses it by definition. Other semantics discussed in this document do not possess it.

**► Lemma 55.** 1. SM and BT possess the subwalk coverage guarantee.

2. ShVC, ShMS, MM and Sh do not possess the subwalk coverage guarantee.

3. No filter-based semantics possesses the subwalk guarantee.

**Proof for item 1.** BT possess the subwalk coverage guarantee from [DFM23, Lemma 13]. SM possess it by definition. ◀

**Proof for item 2.** For ShMS, MM and Sh the results comes from the fact that they are strictly included in SM. Hence on the instances where the inclusion are counterexamples of the subwalk coverage guarantee.

For ShVC, consider the database $\mathcal{D}$ consisting of one a-cycle and two b-cycles given below.

$$v_1 \xrightarrow{a} v_2 \xrightarrow{a} v_3 \xrightarrow{a} v_1 \qquad (20)$$

$$v_1 \xrightarrow{b} v_2 \xrightarrow{b} v_1 \qquad (21)$$

$$v_1 \xrightarrow{b} v_3 \xrightarrow{b} v_1 \qquad (22)$$
For $R = aaa + bb$, it may be verified that no subwalk of the walk in (20) is $ShVC(D, R)$. ◀

**Proof sketch for item 3.** A filter-based semantics has at least one walk $w$ of positive length that it filters out. Consider the characteristic database $D$ and characteristic regular expression $R$ of $w$ (Def. 31). Then $S(D, R)$ is empty while $w$ belongs to $Matches(D, R)$. ◀

### 4.6.3 Atom coverage

Another, orthogonal type of coverage is worth mentioning. It covers the regular expression instead of the match set. Intuitively, we say a semantics $S$ is atom-covering if for every $D$ and $R$, and for every letter occurrence in $R$, $S(D, R)$ contains at least one walk matched using this letter occurrence if any such walk exists. We give below a formal definition.

**Definition 56.** Let $R$ be a regular expression over $\Sigma$. We denote by $k$ the number of atoms in $R$, and by $a_i$ the $i$-th atom of $R$, for $i \in \{1, \dots, k\}$.

1. A linearisation of $R$ is a copy $R'$ of $R$ in which each atom occurrence in $\Sigma$ is replaced by a different symbol in a new alphabet $\Gamma$. We denote by $\alpha$ the corresponding bijection $\{1, \dots, k\} \to \Gamma$ and by $\beta$ the function $\Gamma \to \Sigma$ defined by: $\forall i \in \{1, \dots, k\} \beta(\alpha(i)) = a_i$.

2. A word $u$ covers the $i$-th atom of $R$ if there exists some word $u' \in L(R')$ in which the letter $\alpha(i)$ occurs, and such that $u = \beta(u')$, for some linearisation $R'$ of $R$. A walk $w$ in $D$ covers the $i$-th atom of $R$ if its label does. Note that this notion is independent of the chosen linearisation.

3. A semantics $S$ is atom covering if for every database $D$, regular expression $R$ and position $i$ in $\{1, \dots, k\}$ such that some walk in $Matches(D, R)$ covers the $i$-th atom of $R$, there is a walk covering the $i$-th atom of $R$ in $S(D, R)$.

This definition expresses the idea that when designing a query with multiple alternatives, each alternative which yields at least a match should be reflected in the result set. It may be verified that no walk-based semantics can be atom-covering. As was the case for vertex and edge coverage, it is quite easy to define atom-covering semantics (although they are not walk-based in this case), such as the one given next.

**Example 57 (Shortest atom-cover ShAC).** Let $D$ be a database and $R$ be a regular expression. Let $\{1, \dots, k\}$ be the set of positions of atoms in $R$. Let $\leq_{Sh}$ be the shorter than order (on which $Sh$ is based). Then:

$$ \mathrm{ShAC}(D, R) = \bigcup_{s,t \in V_D} \bigcup_{i=1}^{k} \min_{\leq_{Sh}} \left\{ w \in \mathrm{Matches}(D, R) \mid \begin{array}{l} w \text{ starts in } s \text{ and ends in } t \\ w \text{ covers the } i\text{-th atom of } R \end{array} \right\} $$

It is routine to check that the definition of ShAC implies that it is atom-covering. Since BT includes ShAC semantics (See Section 4.5), it is also atom-covering.

**Proposition 58.** ShAC and BT are atom-covering.

## 4.7 Summary: what is a reasonable semantics?

Although many of the properties described in Sec. 4 are desirable, we saw that some of them are incompatible. We list below the properties that we think any reasonable semantics should satisfy. As we will see, there are caveats in a lot of cases.
**Identifier independence** (Def. 21) In database systems, identifiers are not always accessible to the user, nor guaranteed to remain constant over time. Therefore, it seems strange to have a semantics rely on identifiers. Note however that identifier-dependent semantics might still be useful to model cases where the database engine is allowed to make arbitrary choices, like the **ANY SHORTEST** keyphrase in GQL or the **ShL** semantics (Ex. 18).

**Label-independence** (Def. 21) Semantics are defined before (hence independently of) database schemas. Since labels are abstractions of relation names in schema, it seems strange to attach a meaning to them. On the other hand, one could use labels to model other aspects, such as the weight in a semantics like the one described by the **ANY CHEAPEST** keyphrase proposal in GQL (see Ex. 20).

**Unboundedness** (Def. 25) Bounded semantics only yield walks whose length is bounded by some constant *regardless of the query or the database*, which seems to defeat the whole purpose of using RPQs. Note that we are referring here to a property of the semantics itself, not to possible extensions of the query language allowing users to limit the length of returned walks (which could be useful in certain scenarios).

**Co-monotony** (Def. 26) A co-monotonous semantics ensures that, for a fixed query, whenever extending a database graph with new vertices or edges, the new results should always use some of the new vertices or edges. On the contrary, under a non-co-monotonous semantics, whether a match belongs to the result set or not depends on information that seems irrelevant.

**Decomposability** (Def. 39) Similarly to co-monotony, semantics that are not decomposable sometimes have new results that materialize out of thin air. In particular, for such semantics, results cannot be computed bottom up from the expression.

**Compatibility with atoms** (Def. 40) Using a semantics that is not compatible with atoms means that some edges might be missing from replies to atomic queries. If the semantics is moreover decomposable, these missing edges will never appear in the results of any query. Note that Ac, one of the semantics available in GQL, is in fact not compatible with atoms, due to possible self-loops in the graph. This probably means that Ac assumes the graph to have no self-loops.

**Continuity** (Def. 34) A (walk-based) semantics that is not continuous means that the semantics behaves differently for finite match sets and infinite match sets. Note that a semantics that is not expression-independent (hence also not walk-based, see Lemma 24), such as binding-trail semantics (Example 19), may be noncontinuous but still be considered meaningful.

**Complexity** The definition of filter-based (Def. 7) and order-based (Def. 11) semantics makes no requirement about the complexity class of the filter function or of the order. Reasonable semantics should be based on filter functions or orders that are tractable, otherwise the complexity classes of usual query evaluations are bound to be untractable (see Sec. 5).

# 5 Computational problems

This document is **not** about computational problems. In Section 5, we gather computational problems and known complexity results for them from other sources. In particular, Figure 2 sums up known results about the most interesting semantics mentioned in this document.
<table><caption>Figure 2 Summary of computational problem (data) complexity for the main semantics</caption><thead><tr><th>Semantics</th><th>Existence</th><th>Memb.</th><th>Extensibility</th><th>Enumeration</th></tr></thead><tbody><tr><td>Tr (Trail) [MNP23]</td><td>NP-c</td><td>NL</td><td>NP-c</td><td>Preproc. is NP-c</td></tr><tr><td>Ac (Acyclic) [BBG20]</td><td>NP-c</td><td>NL</td><td>NP-c</td><td>Preproc. is NP-c</td></tr><tr><td>Sh (Shortest walk)</td><td>NL-c</td><td>P</td><td>P</td><td>DelayP</td></tr><tr><td>BT (Binding trail) [DFM23]</td><td>NL-c</td><td>NP-c</td><td>NP-c</td><td>Open/DelayP<sup>1</sup></td></tr><tr><td>SM (Subwalk minimal) [Khi24]</td><td>NL-c</td><td>P</td><td>NP-c</td><td>Open</td></tr><tr><td>MM (Minimal Multiset) [Mar24]</td><td>NL-c</td><td>coNP-c</td><td>coNP-h</td><td>Not DelayP<br>unless P = NP</td></tr><tr><td>ShVC (Short. Vertex Cover) [Khi24]</td><td>NL-c</td><td>P</td><td>P</td><td>DelayP</td></tr></tbody></table>

<table><thead><tr><th colspan="2">EXISTENCE UNDER S</th></tr></thead><tbody><tr><td>Data:</td><td>A database <i>D</i> and two vertices <i>s</i> and <i>t</i> from <i>D</i>.</td></tr><tr><td>Query:</td><td>A regular expression <i>R</i>.</td></tr><tr><td>Output:</td><td>Is there a walk <i>w</i> from <i>s</i> to <i>t</i> in <i>S(D, R)</i>?</td></tr></tbody></table>

**► Theorem 59.** *Existence under S is in NL whenever S is order-based.*

As recalled in Figure 2, it is well-known that EXISTENCE is NP-complete under the semantics Tr and Ac. It is quite easy to show that it is also NP-complete under the variant SWC (Ex. 9) or 2Ac (Ex. 10). Actually, we conjecture that EXISTENCE is NP-hard for any filter-based semantics:

**► Conjecture 60.** *EXISTENCE UNDER S is NP-hard in data-complexity for every "reasonable" filter-based semantics.*

We added the restriction *reasonable* in Conjecture 60 because the problem is likely to be void otherwise. Indeed, definition of filter-based semantics (Def. 7) does not impose restrictions on the complexity of the filter function. Moreover, the proof is likely to require the semantics to satisfy other properties, such as the one provided in Sec. 4.7.

<table><thead><tr><th colspan="2">MEMBERSHIP UNDER S</th></tr></thead><tbody><tr><td>Data:</td><td>A database <i>D</i> and a walk <i>w</i> in <i>D</i>.</td></tr><tr><td>Query:</td><td>A regular expression <i>R</i>.</td></tr><tr><td>Output:</td><td>Does <i>w</i> belong to <i>S(D, R)</i>?</td></tr></tbody></table>

Once again, the definition of filter-based semantics does not impose any complexity restriction on the filter function. Hence, MEMBERSHIP under a filter-based semantics is computationally equivalent to the filter function. The situation is worse for order-based semantics: Membership under $S_{\leq}$ may be harder than the complexity of $\leq$. It is for instance coNP-hard under MM [Mar24], while the order itself is in NL. It is the worst-case scenario since MEMBERSHIP under a reasonable order-based semantics is always in coNP, as stated below.
**► Proposition 61.** Let $S_{\leq}$ is a semantics based on an order $\leq$ in $\mathbf{P}$. If there is a polynomial function $p$ such that for every walks $w' \leq w$, it holds $|w'| < p(|w|)$, then **MEMBERSHIP** under $S$ is in **coNP**.

**Sketch of proof.** Non-membership of $w$ amounts to finding a match $w'$ that satisfies $w' < w$. Checking that a given $w'$ satisfies both conditions may be done in polynomial time by hypotheses. On the other hand, any $w'$ satisfying $w' < w$ must have a length that is polynomial in the length of $w$, hence $w'$ is necessarily short enough to serve as a certificate for non-membership of $w$. ◀

### ENUMERATION UNDER $S$

**Data:** A database $\mathcal{D}$ and a walk $w$ in Walks($\mathcal{D}$).

**Query:** A regular expression $R$.

**Output:** All walks $w$ in $S(\mathcal{D}, R)$ going from $s$ to $t$.

The lower bound for the preprocessing time of ENUMERATION is at least as high as the lower bound of EXISTENCE, since one could use an algorithm for the former to solve the latter. This is the argument used to show that ENUMERATION under usual filter-based semantics (Tr, Ac, SWC, etc.) is intractable. The case of MM is remarkable in the sense that ENUMERATION is intractable, but due to the delay and not the preprocessing [Mar24].

We introduce below the less common problem of EXTENSIBILITY. It allows to use the well-known technique of the *flash-light search*: ENUMERATION is tractable, whenever both EXTENSIBILITY and MEMBERSHIP are.

### EXTENSIBILITY UNDER $S$

**Data:** A database $\mathcal{D}$, a walk $w$ in Walks($\mathcal{D}$) and a vertex $t$ in $\mathcal{D}$.

**Query:** A regular expression $R$.

**Output:** Is there a walk $w'$ such that $w \cdot w'$ belong to $S(\mathcal{D}, R)$ and ends in $t$?

EXTENSIBILITY is at least as hard as EXISTENCE since EXISTENCE amounts to providing empty walk as input to EXTENSIBILITY. Although it is not formally true, the definition of a semantics usually implies that EXTENSIBILITY is usually at least as hard as MEMBERSHIP.

**► Proposition 62 (Application of [Str21, Prop. 3.5]).** If EXTENSIBILITY and MEMBERSHIP under a semantics $S$ are both in $\mathbf{P}$ in data complexity, then ENUMERATION under $S$ is *DelayP* in data complexity (and memoryless, see [Str21]).

**Sketch of proof.** Let A database $\mathcal{D}$, a walk $w$ in Walks($\mathcal{D}$) and a vertex $t$ in $\mathcal{D}$ be the input of the problem. For every vertex $s$ of the database we call the function FORWARD below, with the trivial walk ($s$) as argument.

1. function FORWARD(Walk $w$)

2. if $\Gammagt(w) = t$ and MEMBERSHIP($\mathcal{D}, R, w$) returns **True**

3. Output $w$

4. for each edge $e$ going out from $\Gammagt(w)$

5. $w' \leftarrow w \cdot (\mathrm{Src}(e), e, \Gammagt(e))$

6. if EXTENSIBILITY($\mathcal{D}, R, w', t$) returns **True**

7. FORWARD($w'$)

8. return $\perp$
Note that the number of recursive calls to FORWARD on the stack is bounded by the length of the next walk to output.

► **Remark 63.** There are variants of EXISTENCE and ENUMERATION in which endpoints as not provided as input. Similarly, sometimes the target *t* of *Extensibility* is not provided. These changes usually have no impact on the complexity of those problems.

# 6 Conclusion and future work

Only a few RPQ semantics have been considered in industry, and their principled study was generally performed a posteriori. In this work, we took the opposite approach: first define the properties a RPQ semantics could have, in order to design better RPQ semantics in the future. We distinguished two simple classes of semantics: filter-based semantics which select results using a per-walk criterion, and order-based semantics which only retain minimal matches with respect to some ordering relation. We proposed a list of possible properties, some of which may be considered requirements for all RPQ semantics, while others turned out to be incompatible. This process yielded several promising semantics, such as subwalk-minimal and shortest-vertex-cover semantics, which probably deserve further investigations.

Our work is by no means exhaustive. It has several limitations, which constitute interesting leads for future work. First, some of our definitions may be too restrictive. For instance, the class of *filter-based* semantics is tailored to capture several semantics used in practice, but our definition appears to leave little room for novel designs. Another example is compatibility with rational operators. Most of them are verified by very few reasonable semantics, and weaker notions of compatibility might be worth considering. For instance, a weaker version of $*$-composability could be that $S(D, R)$ is always included in $S(D, R^*)$.

Second, we limited the scope of our study to walk-based semantics. A semantics is a way to restrict the potentially infinite set of matches to a finite and hopefully representative set of results for the user. From this perspective, walk-based semantics must make this selection using a very limited amount of information. This prevents us from considering semantics whose results depend on the actual syntax of the regular expression, such as the ones in [ACP12; DFM23]. Future work could investigate semantics that make use of more information, such as walk labels, the entire database, the syntax of the query, or how walks are matched by the query.

Third, both our data model and the query language we consider are rather simplistic. Adding features such as data or node labels should not affect our observations regarding walk-based semantics. However, these changes increase the design space when considering semantics that are not walk-based (as discussed above). Note that the GQL data model [DF+22; GQL24] allows edges (and nodes) to bear multiple labels. This raises the question of walk multiplicity in the result, a dimension we ignored entirely. It would also be interesting to study *dynamical semantics*: enrich the syntax to give users some control over the semantics, similar to *CHEAPEST* in GQL.
# 7 Bibliography

## 7.1 Academic publications

[AA$^{+}$17] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter and D. Vrgoč. 'Foundations of Modern Query Languages for Graph Databases'. In: *ACM Comput. Surv.* 50.5 (2017). DOI: 10.1145/3104031.

[ACP12] M. Arenas, S. Conca and J. Pérez. 'Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard'. In: *World Wide Web (WWW)*. ACM, 2012. DOI: 10.1145/2187836.2187922.

[AHV95] S. Abiteboul, R. Hull and V. Vianu. *Foundations of databases*. en. Reading, Mass: Addison-Wesley, 1995. ISBN: 978-0-201-53771-0.

[BBG20] G. Bagan, A. Bonifati and B. Groz. 'A trichotomy for regular simple path queries on graphs'. In: *J. Comput. Syst. Sci.* 108 (2020). DOI: 10.1016/j.jcss.2019.08.006.

[CMW87] I. F. Cruz, A. O. Mendelzon and P. T. Wood. 'A Graphical Query Language Supporting Recursion'. In: *SIGMOD'87*. Ed. by U. Dayal and I. L. Traiger. ACM Press, 1987. DOI: 10.1145/38713.38749.

[DF$^{+}$22] A. Deutsch, N. Francis, A. Green, K. Hare, B. Li, L. Libkin, T. Lindaaker, V. Marsault, W. Martens, J. Michels, F. Murlak, S. Plantikow, P. Selmer, H. Voigt, O. van Rest, D. Vrgoč, M. Wu and F. Zemke. 'Graph Pattern Matching in GQL and SQL/PGQ'. In: *SIGMOD'22*. ACM, 2022. DOI: 10.1145/3514221.3526057.

[DFM23] C. David, N. Francis and V. Marsault. 'Run-Based Semantics for RPQs'. In: *Principles of Knowledge Representation and Reasoning (KR'23)*. Aug. 2023. DOI: 10.24963/kr.2023/18.

[DFM24] C. David, N. Francis and V. Marsault. 'Distinct Shortest Walk Enumeration for RPQs'. In: *Proc. ACM Manag. Data* 2.2 (2024). DOI: 10.1145/3651601.

[FG$^{+}$18a] N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, M. Schuster, P. Selmer and A. Taylor. *Formal Semantics of the Language Cypher*. Arxiv Preprint. 2018. URL: https://arxiv.org/abs/1802.09984.

[FG$^{+}$18b] N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, P. Selmer and A. Taylor. 'Cypher: An Evolving Query Language for Property Graphs'. In: *SIGMOD'18*. ACM, 2018. DOI: 10.1145/3183713.3190657.

[Hig52] G. Higman. 'Ordering by Divisibility in Abstract Algebras'. In: *Proceedings of The London Mathematical Society* (1952). URL: https://api.semanticscholar.org/CorpusID:123011310.

[Kar15] P. Karandikar. 'Subwords : automata, embedding problems, and verification'. PhD thesis. École normale supérieure de Cachan - ENS Cachan ; Chennai Mathematical Institute, 2015. URL: https://theses.hal.science/tel-01157502/file/Karandikar2015.pdf.

[Khi24] S. Khichane. 'Study of New Semantics for Regular Path Queries'. MA thesis. Université Paris-Cité, 2024.

[Mar24] V. Marsault. *Matching walks that are minimal with respect to edge inclusion*. ArXiv Preprint. 2024. URL: http://arxiv.org/abs/2408.14048.

[MM26] V. Marsault and A. Meyer. 'Designing and Comparing RPQ Semantics'. In: *ICDT*. To appear. 2026. DOI: 10.4230/LIPIcs.ICDT.2026.6.
[MN+23] W. Martens, M. Niewerth, T. Popp, C. Rojas, S. Vansummeren and D. Vrgoč. 'Representing Paths in Graph Database Pattern Matching'. In: *Proc. VLDB Endow.* 16.7 (2023). DOI: 10.14778/3587136.3587151.

[MN+24] W. Martens, M. Niewerth, T. Popp, C. Rojas, S. Vansummeren and D. Vrgoč. 'Compact Path Representations for Graph Database Pattern Matching'. In: *ICDEW'24*. 2024. DOI: 10.1109/ICDEW61823.2024.00059.

[MNP23] W. Martens, M. Niewerth and T. Popp. 'A Trichotomy for Regular Trail Queries'. In: *Log. Methods Comput. Sci.* 19.4 (2023). DOI: 10.46298/LMCS-19(4:20)2023.

[MT18] W. Martens and T. Trautner. 'Evaluation and Enumeration Problems for Regular Path Queries'. In: *ICDT'18*. Ed. by B. Kimelfeld and Y. Amsterdamer. Vol. 98. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. DOI: 10.4230/LIPIcs.ICDT.2018.19.

[Str21] Y. Strozecki. *Enumeration Complexity: Incremental Time, Delay and Space*. Habilitation thesis. Université de Versailles – Saint-Quentin-en-Yvelines. 2021.

## 7.2 Language documentations and specifications

[Cypher24] Neo4j. *Cypher Manual (version 5)*. https://neo4j.com/docs/cypher-manual/5.2024.

[GQL24] International Organization for Standardization. *GQL*. https://www.iso.org/standard/76120.html. Standard ISO/IEC CD 39075. 2024.

[GSQL23] TigerGraph. *GSQL Language Reference (version 3.9)*. 2023. URL: https://docs.tigergraph.com/gsql-ref/3.9/intro/.

[PGQ23] International Organization for Standardization. *SQL — Part 16: SQL Property Graph Queries (SQL/PGQ)*. https://www.iso.org/standard/79473.html. Standard ISO/IEC CD 9075-16. Part 16 of [SQL23]. 2023.

[PGQL21] Oracle. *PGQL 2.0 Specification*. https://pgql-lang.org/spec/2.0/. 2021.

[SPARQL13] World Wide Web Consortium. *SPARQL 1.1 Query Language, Section 9: Property paths*. https://www.w3.org/TR/sparql11-query/#propertypaths. 2013.

[SQL23] International Organization for Standardization. *SQL*. Standard ISO/IEC CD 9075. Edition 6. 2023.
8 Index & Acronyms

#

2Ac, *stands for* Two-acyclic semantics, 6

Ac, *stands for* Acyclic semantics, 6

BT, *stands for* Binding-trail semantics, 8

ChW, *stands for* Cheapest semantics, 8

GU, *stands for* Giving-up semantics, 14

LL, *stands for* Log-length semantics, 10

MM, *stands for* Minimal-multiset semantics, 12

SM, *stands for* Subwalk-minimal semantics, 7

SR, *stands for* Simple-run semantics, 8

SWC, *stands for* Simple-walk-or-cycle semantics, 6

ShAC, *stands for* Shortest-atom-cover semantics, 23

ShL, *stands for* Shortlex semantics, 7

ShMS, *stands for* Shortest-minimal-set semantics, 12

ShT, *stands for* Shortest-trail semantics, 5

ShVC, *stands for* Shortest-vertex-cover semantics, 20

Sh, *stands for* Shortest semantics, 5

Tr, *stands for* Trail semantics, 5

A

Acyclic semantics (Ac), 6

Arbitrary semantics, 5

Atom coverage, 23

B

Binding-trail semantics (BT), 8

Bounded, 9

C

Characteristic database, 11

Characteristic expression, 11

Cheapest semantics (ChW), 8

Co-monotonous, 9

Compatible

with atoms, 15

with rational operators, 15

Composable

w.r.t. rational operators, 15

Continuous, 13

D

Decomposable

w.r.t. rational operators, 15

E

Expression independent, 9

F

Filter-based, 6

G

Giving-up semantics (GU), 14

I

Identifier independent, 8

L

Label independent, 8

Log-length semantics (LL), 10

M

Match, 5

Minimal-multiset semantics (MM), 12

Monotonous, 9

O

Order-based, 6

R

Restrictible, 9

S

Shortest semantics (Sh), 5

Shortest-atom-cover semantics (ShAC), 23

Shortest-minimal-set semantics (ShMS), 12

Shortest-trail semantics (ShT), 5

Shortest-vertex-cover semantics (ShVC), 20

Shortlex semantics (ShL), 7

Simple-run semantics (SR), 8

Simple-walk-or-cycle semantics (SWC), 6

Stabilizing, 13

Subwalk guarantee, 22

Subwalk-minimal semantics (SM), 7

Suitable, 6

T

Trail semantics (Tr), 5

Trimmed, 6

Two-acyclic semantics (2Ac), 6

U

Unbounded, 9

V

Vertex coverage, 20

W

Walk-based semantics, 5