∎

11institutetext:  T. Mulder (0009-0002-5847-5941) 22institutetext: Technische
Universiteit Eindhoven, Eindhoven, Netherlands 22email<EMAIL_ADDRESS>33institutetext: G. Fletcher (0000-0003-2111-6769) 44institutetext: Technische
Universiteit Eindhoven, Eindhoven, Netherlands 44email<EMAIL_ADDRESS>55institutetext: N. Yakovets (0000-0002-1488-1414) 66institutetext: Technische
Universiteit Eindhoven, Eindhoven, Netherlands 66email<EMAIL_ADDRESS>
# Optimizing Navigational Graph Queries

Thomas Mulder  George Fletcher  Nikolay Yakovets

(Received: date / Accepted: date)

###### Abstract

We study the optimization of navigational graph queries, i.e., queries which
combine recursive and pattern-matching fragments. Current approaches to their
evaluation are not effective in practice. Towards addressing this, we present
a number of novel powerful optimization techniques which aim to constrain the
intermediate results during query evaluation. We show how these techniques can
be planned effectively and executed efficiently towards the first practical
evaluation solution for complex navigational queries on real-world workloads.
Indeed, our experimental results show several orders of magnitude improvement
in query evaluation performance over state-of-the-art techniques on a wide
range of queries on diverse datasets.

###### Keywords:

Information systems Query planning Query optimization Graph-based database
models

##  1 Introduction

State-of-the-art systems are effectively unable to evaluate complex
navigational queries in practice wdbench . In this work, we aim to overcome
this severe limitation by introducing new optimization techniques for
navigational queries with the ultimate goal to finally enable their evaluation
in practice.

Complex navigational queries are formed by the combination of the two types of
graph queries which form the core of modern graph query languages, namely
pattern-matching and recursive path queries DBLP:series/synthesis/2018Bonifati
.

Pattern-matching queries ask for all embeddings of a given query graph pattern
in a data graph. Path queries ask for all pairs of start- and end-points of
paths that can be formed by a finite number of repetitions of a pattern (the
number of repetitions might not be known at query-time). In other words, the
second type asks for the transitive closure of a binary relation which may be
obtained by projecting the result of any graph query to a pair of variables.

Powerful optimization opportunities arise from the interplay of these two
paradigms which together form the complex navigational queries arising in
practical graph data management applications. These opportunities have not
been exploited to their full potential in the state-of-the-art. As we show in
this paper, systematically realizing these opportunities enables significant
(up to several orders of magnitude) performance improvements over the state-
of-the-art on a wide range of queries on diverse datasets. We next outline our
contributions which enable these important performance gains, towards
realizing practical graph querying in contemporary graph applications.

##### Contribution (1): Novel optimization techniques

The foundation of our optimizations is that they leverage selectivity, as
introduced by filters and join predicates, from a query graph that contains
transitive closures to constrain the evaluation of those transitive closures
and thus improve the overall evaluation performance. We introduce novel
optimizations of this type that generalize to closures where both variables
participate in join-predicates as part of a conjunctive query. Optimizing such
closures in this way is beyond state-of-the-art methods. We will refer to
constraining transitive closures using filter- and join-predicates as seeding.

For example, consider a social network comprised of people and the friend- and
colleague relationships between them, and a query that asks for those pairs of
people that are both direct or indirect friends and colleagues. Using state-
of-the-art methods, both the friends- and colleagues transitive closures must
be evaluated fully, and subsequently intersected. A seeded plan which
leverages the potential selectivity of a join between friends and colleagues
in order to constrain the evaluation of both transitive closures (e.g., the
friends closure is evaluated starting only at those people for whom there
exists a friend that also participates in the colleague relationship and vice
versa for the colleagues closure) is not considered. Additionally, we observe
that when more than two such transitive closures are present in a navigational
query, seeding can be applied in a nested fashion which stacks the selectivity
of multiple closures. These novel optimizations techniques are explained in
more detail in § 3.2.

##### Contribution (2): Graph-structured query plans

We present a unified graph-structured model for the representation of query
plans which can incorporate both tree-based and automata-based optimizations.
Query plans- and optimization techniques for queries that contain transitive
closures have often been (partially) represented using formalism such as
automata DBLP:conf/sigmod/YakovetsGG16 ; DBLP:conf/icde/ArroyueloHNR22  or ad-
hoc procedural (sub)routines DBLP:conf/sigmod/JachietGGL20 , instead of the
more conventional tree-structured plans. This complicates, or even excludes,
the cross-optimization of recursive- and non-recursive parts of a query and
the use of well-known optimization techniques for tree-structured plans.
Graph-structured query plans are explained in more detail in § 4.1.1.

##### Contribution (3): Provably efficient enumeration

We outline a solution to the enumeration problem using a fast, scalable and
extendable enumerator featuring a top-down design relying on memoization which
guarantees the optimality of the chosen plan with respect to the cost model.
Many logical equivalences exist for (combinations of) logical operations in
database queries. These equivalences lead to a multitude of semantically
equivalent logical query plans for any query. The fact that two semantically
equivalent plans can display drastically different performance on the same
database instance necessitates the existence of a query optimizer as part of
any database system. The optimizer’s task is to pick, for any combination of
input query and database instance, an ‘optimal’ query plan. Therefore, a major
sub-task of the optimizer is to enumerate a set of semantically equivalent
query plans for the input query (enumeration of query plans should not be
confused with enumeration of query results). The plans in this set can then be
_costed_ against the database instance in an attempt to pick a good query plan
for that instance. Given an input query and a finite set of logical
equivalences we wish to consider, we define the enumeration problem as the
problem of enumerating all semantically equivalent query plans that can be
obtained by any finite, acyclic sequence of applications of the logical
equivalences.

Solving the enumeration problem for recursive queries over graph-structured
plans is not trivial. Enumerating plans with tree-breaking features such as
operators with multiple consumers and ‘cross-optimizable’ fix-point procedures
(i.e., not black boxes) requires a degree of flexibility of an enumerator that
is difficult to achieve using a conventional design. We design a top-down
enumerator that relies on memoization, embeds instances of recursive sub-
problems (i.e., sub-queries to be optimized) directly into partial solutions
and which can guarantee the optimality of the chosen plan with respect to a
cost model. The enumerator is presented in more detail in § 4.

Finally, we study the complexity of the enumeration procedure and investigate
in particular the complexity added by the proposed optimizations. Most
importantly, we prove that adding the proposed optimizations increases the
complexity only up to a constant factor, which effectively enables the
application of these optimizations in practice. The complexity of the
enumeration procedure is discussed in more detail in § 4.4.

##### Contribution (4): Practical feasibility

We show how to implement the described model of query plans, top-down
enumeration procedure and query optimization techniques related to seeding in
an industrial graph-database engine. Neither the optimization techniques, the
query plan model nor the enumerator’s design are particular to this engine and
all could be applied as part of any other system.

We demonstrate enumeration of a diverse and hitherto unexplored set of query
plans that employ seeding, and present empirical evidence showing that
enumerating such plans is feasible in practice and that cost-based
optimization can be employed effectively to reduce the time spent on- and
amount of data processed during query evaluation by up to three orders of
magnitude. The practical feasibility of the enumerator and the performance
improvements it enables are discussed in more detail in § 5.3.

##### Contribution (5): Support for Regular Queries

Seeding has not been studied in the context of the Regular Queries (RQs) which
are strictly more expressive than UCRPQs, are closed under the transitive
closure operation, have a decidable query containment problem, are at the
heart of industrial-strength languages such as SPARQL and GQL, and are
therefore the natural choice of query formalism for navigational queries. The
increased expressivity of RQs was shown to be incredibly useful in many
practical application areas DBLP:journals/mst/ReutterRV17 .

For example, consider a financial network comprised of people and accounts and
the ownership- and transaction relationships between them. A query that asks
for all pairs of people that own accounts for which there exists a direct or
indirect transaction relationship from one account to the other and that any
intermediary accounts have a direct or indirect transaction relationships with
the same fixed account, is a query that can be represented as an RQ, but not
as a UCRPQ because of the predicate that is imposed upon every intermediary
account. Such queries are important for validation- or fraud detection
purposes.

The structure of this paper is as follows. Property graphs are introduced as
the data model and the Regular Queries are defined in § 2. The concept of
seeding and two novel extensions to it are discussed in § 3. The enumerator is
discussed in terms of its design, the way it represents query plans and the
rules it uses in § 4, alongside the complexity of the enumeration procedure.
The experimental results and a case study are presented in § 5, § 6. Finally,
the related work and conclusions are discussed in § 7 and § 8.

##  2 Data model and query specification

###  2.1 Data model

Without loss of generality, we adopt the data model of property graphs,
recently standardized by ISO DBLP:series/synthesis/2018Bonifati ;
FrancisGGLMMMPR23 . Let $\mathcal{K}$ be a finite set of property keys,
$\mathcal{N}$ a finite set of property values, $I\subset\mathbb{N}$ a set of
numerical identifiers, and $I_{V}$ and $I_{E}$ finite subsets of $I$ such that
$I_{V}\cap I_{E}=\emptyset$ called vertex- and edge identifiers, respectively.
A property graph is defined as a pair $G=(E,P)$ with $E\subseteq I_{V}\times
I_{E}\times I_{V}$ and $P\subseteq(I_{V}\cup
I_{E})\times\mathcal{K}\times\mathcal{N}$. That is, $E$ is a set of triples of
the form $(s,e,t)$ where $s$ and $t$ are vertex identifiers representing the
end-points of a directed edge from $s$ to $t$, while $e$ uniquely identifies
an edge, and $P$ is a set of triples of the form $(o,k,v)$ where $o$ is a
vertex- or edge identifier, $k$ a property key and $v$ a property value.

###  2.2 Regular Queries

The Regular Queries (RQs) extend non-recursive Datalog with a transitive
closure operator on binary predicates. The RQs are a natural, rich and well-
behaved query language for graphs: a) RQs are closed under the transitive
closure operation; b) RQs generalize and extend existing fundamental graph
query languages such as unions of conjunctive 2-way regular path queries
(UC2RQPs) DBLP:conf/kr/CalvaneseGLV00/uc2rpq  and unions of conjunctive nested
2-way regular path queries (UCN2RPQs); and c),
DBLP:conf/amw/BarceloPR12/uc2nrpq  the query containment problem is decidable
for RQs DBLP:journals/mst/ReutterRV17 , opening the door to principled and
formally well-grounded optimization solutions.

Figure 1: A property graph capturing financial data

Consider again the financial network and the natural language query on it from
the introduction. An instance of such a network is displayed in Figure 1.
Vertices representing people and accounts are denoted $p_{i}$ and $a_{j}$,
respectively. The query that asks for all pairs of people who own accounts for
which there exists a path (i.e., sequence) of transaction relationships from
one account to the other and that for all accounts on this path, there exists
another path of transaction relationships to the account with IBAN IE12 BOFI
9000 0112 3456 78, is captured by Equation Q1 shown below as a Datalog
program. Here, $R^{+}(s,t)$ denotes a transitive closure over binary relation
$R(s,t)$.

$\displaystyle O(s,t)$ $\displaystyle\leftarrow
E(s,e,t),P(e,\text{label},\text{owns})$ (Q1) $\displaystyle T(s,t)$
$\displaystyle\leftarrow E(s,e,t),P(e,\text{label},\text{transaction})$
$\displaystyle F(s)$ $\displaystyle\leftarrow
T^{+}(s,t),P(t,\text{IBAN},\text{{IE12...78}})$ $\displaystyle I(x,y)$
$\displaystyle\leftarrow\,T(x,y),F(x)$ $\displaystyle Ans(w,z)$
$\displaystyle\leftarrow\,O(w,x),I^{+}(x,y),O(z,y),F(y)$

Because $I$ is defined in terms of a conjunction between $T$ and $F$, and
Equation Q1 is defined in terms of $I^{+}$ this query cannot be captured by a
UCN2RPQ, which do not allow for the transitive closure operation to be applied
to the result of a conjunction. Hence, this query is an RQ but not a UCN2RPQ.
One pair in the result of Equation Q1 on the property graph from Figure 1 is
$(p_{1},p_{3})$. There does not exist a direct transaction from account
$a_{1}$ to $a_{5}$ (the account with the desired IBAN), but the definition of
$F(s)$ is in terms of $T^{+}$, not just $T$. A path of transactions exists
from $a_{1}$ to $a_{5}$ via $a_{3}$.

##  3 Seeding

Let $R(s,t)$ be a binary relation and $R^{+}(s,t)$ its transitive closure. A
naive solution is to compute $R^{+}(s,t)$ ‘in full’ by starting from $R(s,t)$
and repeatedly expanding by one join with $R(s,t)$ until a fix-point is
reached (i.e., no new pairs are added by another join with $R(s,t)$). This
strategy is defined by Datalog Equation D1.

$\displaystyle R^{+}(s,t)$ $\displaystyle\leftarrow R(s,t)$ (D1)
$\displaystyle R^{+}(s,t)$ $\displaystyle\leftarrow R^{+}(s,x),R(x,t)$

Whenever $R^{+}(s,t)$ is also the desired output of the query, computing the
transitive closure in full cannot be avoided. However, as soon as a the query
contains other predicates besides the transitive closure (i.e., the transitive
closure is embedded into a larger query), computing it in full is often not
necessary. Instead, we can seed a transitive closure to avoid the exploration
of paths that do not join with the larger query into which the closure is
embedded. We define four key concepts involved in seeding.

###### Definition 1

A seed $S$ is a set of nodes from a property graph that is used to restrict
the transitive closure of a binary relation over the set of nodes in the
graph.

###### Definition 2

A seeding query $Q_{s}$ is a query whose result is used to obtain one or more
seeds.

###### Definition 3

A seeding relation $R(x_{1},...,x_{n})$ is the result of evaluating a seeding
query on a property graph and it is an $n$-ary relation where each variable
$x_{i}$ binds to a node in a graph.

###### Definition 4

Given a seed $S$, binary relation $T(x,y)$ and $T^{+}(x,y)$ its transitive
closure, a seeded closure
$\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}$ for $T^{+}$ on $S$ containing only end-points of paths starting at nodes
in $S$ is defined as:

$\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}=\\{\,(u,v)\,|\,(u,v)\in T^{+}\wedge u\in S\,\\}\cup\\{\,(u,u)\,|\,u\in
S\,\\}$

Symmetrically, a seeded closure
$\overset{\scriptscriptstyle\leftarrow}{T}\vphantom{T}^{\scriptscriptstyle S}$
containing only end-points of paths ending at nodes in $S$ is defined as:

$\overset{\scriptscriptstyle\leftarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}=\\{\,(u,v)\,|\,(u,v)\in T^{+}\wedge v\in S\,\\}\cup\\{\,(v,v)\,|\,v\in
S\,\\}$

That is,
$\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}$ is the union between the identity relation of $S$ and the subset of
$T^{+}$ containing only those pairs of nodes $(u,v)$ where $u$ occurs in the
seed $S$. The identity relation is included to guarantee that every tuple in
the seeding relation $R$ from which $S$ was obtained joins with at least one
pair in
$\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}$.

Consider a query that asks for all pairs of people and accounts $(p,a_{t})$
s.t. $p$ owns an account $a_{s}$ from which there exists a path of
transactions to $a_{t}$. This query is captured as an RQ by Equation Q2 (re-
definitions of $O$ and $T$ omitted), and it is displayed diagrammatically as a
query-graph in 2(a).

$\displaystyle Ans(x,z)$ $\displaystyle\leftarrow O(x,y),T^{+}(y,z)$ (Q2)

This query joins predicates $O(x,y)$ and $T^{+}(y,z)$ on variable $y$. This
presents an opportunity to avoid computing $T^{+}$ in full. The strategy is as
follows, we first define a seeding query $Q_{s}$ as the join between $O(x,y)$
and the base of the transitive closure, which is $T(y,z)$. Evaluating this
seeding query yields the seeding relation $R$. Then, we obtain a seed $S$ by
projecting $R$ to $z$ (i.e., $S=\Pi_{z}(R)$) and compute a seeded closure
$\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}(y,z)$. Finally, we join the seeded closure and the seeding relation. The
set of nodes comprising the seed $S$ for the property graph from Figure 1 are
highlighted in red. Note that more than half of the nodes representing
accounts are not part of $S$ and so no transaction paths starting at any of
these nodes will be explored. This is the core mechanism by which gains in
terms of query evaluation performance are achieved. Equation D2 defines the
seeding strategy as a Datalog program and its application is displayed
diagrammatically in Figure 3.

$\displaystyle R(w,y)$ $\displaystyle\leftarrow O(w,x),T(x,y)$ (D2)
$\displaystyle S(y)$ $\displaystyle\leftarrow R(\\_,y)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}(y,y)$ $\displaystyle\leftarrow S(y)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}(y,z)$
$\displaystyle\leftarrow\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}(y,v),T(v,z)$ $\displaystyle Ans(w,z)$ $\displaystyle\leftarrow
R(w,y),\overset{\scriptscriptstyle\rightarrow}{T}\vphantom{T}^{\scriptscriptstyle
S}(y,z)$

$\displaystyle X(s,t)$ $\displaystyle\leftarrow
E(s,e,t),P(e,\text{label},l_{x})$ (Q3) $\displaystyle Y(s,t)$
$\displaystyle\leftarrow E(s,e,t),P(e,\text{label},l_{y})$ $\displaystyle
Z(s,t)$ $\displaystyle\leftarrow E(s,e,t),P(e,\text{label},l_{z})$
$\displaystyle Ans(s,t)$ $\displaystyle\leftarrow
X^{+}(s,t),Y^{+}(s,t),Z^{+}(s,t)$

Note that while the cardinality of $R(x,z)$ may be much smaller than the
cardinality of $T(y,z)$, the reverse can also be true. Hence, the decision to
apply this strategy or not is a cost-based decision. The general strategy of
rewriting a transitive closure in terms of a seed predicate which leverages
conjunctions and filters from the query into which the transitive closure is
embedded in order to reduce the number of tuples processed in the fix-point
procedure is what we will refer to as seeding. We distinguish two types of
transitive closures in § 3.1, and show how one of the types can benefit from
seeding using novel methods that are beyond the capabilities of state-of-the-
art methods in § 3.2.

###  3.1 Interior- and exterior closures

In order to go beyond the known strategies for seeding, we distinguish two
types of transitive closures, namely interior and exterior closures. An
interior closure is any transitive closure predicate $T^{+}(s,t)$ where both
$s$ and $t$ occur in at least one other (but not necessarily the same)
predicate in the query. An exterior closure is any transitive closure
predicate $T^{+}(s,t)$ where either $s$ or $t$, but not both, occur in at
least one other predicate in the query. The transitive closure $T^{+}(y,z)$
from Equation Q2 is an exterior closure because $y$ occurs in $O(x,y)$, but
$z$ does not occur in any predicate other than $T^{+}(y,z)$. Conversely, the
transitive closure $I^{+}(x,y)$ from Equation Q1 is an interior closure
because $x$ occurs in $O(w,x)$ and $y$ occurs in $O(z,y)$.

###  3.2 Seeding interior closures

Existing approaches to seeding can seed exterior closures, but not interior
ones, because they require that one variable is ‘free’ (i.e., does not occur
in any other predicate) DBLP:conf/sigmod/YakovetsGG16 ;
DBLP:conf/sigmod/JachietGGL20 . We observe that there may be opportunities to
seed interior closures by evaluating the join predicates on one of its
variables only after the transitive closure has been computed using a seed. In
this way, a variable is ‘freed’ so that the closure can be seeded. To avoid
the use of Cartesian products in query plans, we will only apply this strategy
when the join graph of the seeding query remains connected.

Consider query Equation Q3 which asks for pairs of vertices $(s,t)$ such that
there exist three paths of edges labelled $l_{x},l_{y}$ and $l_{z}$
respectively, from $s$ to $t$. The query-graph for this query is displayed in
2(b). A possible strategy for this query would be to define the seeding
relation $R$ as the conjunction of $X,Y$ and $Z$ only on the variable $s$ but
not on $t$ (or the other way around) and to seed each transitive closure on
$\Pi_{u}(R)$ for a different variable $u$ for $X,Y$ and $Z$. This strategy is
defined by Equation D3 and is displayed in Figure 4.

$\displaystyle R(s,x,y,z)\leftarrow X(s,x),Y(s,y),Z(s,z)$ (D3) $\displaystyle
S(x)\leftarrow R(\\_,x,\\_,\\_)$ $\displaystyle T(y)\leftarrow
R(\\_,\\_,y,\\_)$ $\displaystyle U(z)\leftarrow R(\\_,\\_,\\_,z)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(x,x)\leftarrow S(x)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(s,x)\leftarrow\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(s,w),X(w,x)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(y,y)\leftarrow T(y)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(s,y)\leftarrow\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(s,w),Y(w,y)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(z,z)\leftarrow U(z)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(s,z)\leftarrow\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(s,w),Z(w,z)$ $\displaystyle{\scriptstyle Ans(s,t)}\leftarrow
R(s,x,y,z),\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(x,t),\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(y,t),\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(z,t)$

In this case, seeding the interior closures is possible because the definition
of $R(s,x,y,z)$ consists of three predicates $X,Y$ and $Z$ which have a common
variable $s$ and so its join graph is connected. The interior closure
$I^{+}(x,y)$ from Equation Q1 cannot be seeded because $O(w,x)$ would become
disconnected if the variable $x$ is freed, and both $O(z,y)$ and $F(y)$ would
become disconnected (from the remainder of the query, not from each other) if
the variable $y$ is freed.

####  3.2.1 Stacking selectivity

In Equation D3, all three of the transitive closures are expanded on top of
the same seeding relation. That is, the seeds $S,T$ and $U$ are all
projections onto a single variable of the same seeding relation $R$. In this
case, there is an opportunity to use a potentially more restrictive (i.e.,
lower cardinality) seed for one of the three transitive closures. Consider the
non-recursive rule
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(z,z)\leftarrow U(z)$ which populates
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}$ with the set of vertices that have an edge labelled $l_{z}$ incoming on
them, such that the source of this edge has edges labelled $l_{x}$ and $l_{y}$
outgoing from it. Now consider the set of vertices that have an edge labelled
$l_{z}$ incoming on them, such that the source of this edge has a path of
edges labelled $l_{x}$ and a path of edges labelled $l_{y}$ outgoing from it,
such that these two paths end up in the same vertex. The second set is a
subset of the first set, because two outgoing paths imply at least two
outgoing edges, but two outgoing edges may not lead to paths that end up in
the same vertex. Therefore, one possible strategy to reduce the size of the
seed and ultimately to further reduce the number of tuples processed in the
fix-point procedure for
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}$ is to use the intersection of
$\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}$ and
$\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}$ as a new seeding relation to base the expansion of
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}$ on. This strategy stacks the selectivity of the fact that the convergence
of $i$ paths with $i>1$ may be used to produce a more restrictive seed for the
$i+1^{th}$ transitive closure. This strategy is defined by Equation D4 (re-
definitions of $X$, $Y$ and $Z$ are omitted) and is displayed in Figure 5.

This optimization is very powerful when the expansion of
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}$ represents a large proportion of the total amount of work done to evaluate
the query, but the intersection between $X^{+}$ and $Y^{+}$ is selective.
Regarding the applicability of this optimization it is important to note that
the interior closures can ‘occur anywhere’ in the input query and do not need
to be adjacent, but Equation Q3 makes for a succinct example because all three
closures are adjacent.

$\displaystyle R(s,x,y,z)$ $\displaystyle\leftarrow X(s,x),Y(s,y),Z(s,z)$ (D4)
$\displaystyle S(x)$ $\displaystyle\leftarrow R(\\_,x,\\_,\\_)$ $\displaystyle
T(y)$ $\displaystyle\leftarrow R(\\_,\\_,y,\\_)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(x,x)$ $\displaystyle\leftarrow S(x)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(s,x)$
$\displaystyle\leftarrow\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(s,w),X(w,x)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(y,y)$ $\displaystyle\leftarrow T(y)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(s,y)$
$\displaystyle\leftarrow\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(s,w),Y(w,y)$ $\displaystyle W(s,w,z)$ $\displaystyle\leftarrow
R(s,x,y,z),\overset{\scriptscriptstyle\rightarrow}{X}\vphantom{X}^{\scriptscriptstyle
S}(x,w),\overset{\scriptscriptstyle\rightarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(y,w)$ $\displaystyle U(z)$ $\displaystyle\leftarrow W(\\_,\\_,z)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(z,z)$ $\displaystyle\leftarrow U(z)$
$\displaystyle\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(s,z)$
$\displaystyle\leftarrow\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(s,v),Z(v,z)$ $\displaystyle Ans(s,t)$ $\displaystyle\leftarrow
W(s,t,z),\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}(z,t)$

Note that the choice to expand
$\overset{\scriptscriptstyle\rightarrow}{Z}\vphantom{Z}^{\scriptscriptstyle
U}$ ‘last’ (i.e., on top of a more restrictive seed) was taken only for the
sake of the example. Depending on the cardinalities of $X^{+},Y^{+}$ and
$Z^{+}$ it may be preferable to expand one of the other two closures last.

(a) Query-graph for Q2

(b) Query-graph for Q3 & PCC3

(c) Query-graph for Q4

(d) Query-graph for CCC1

(e) Query-graph for CCC2

(f) Query-graph for CCC3

(g) Query-graph for CCC4

(h) Query-graph for PCC2

(i) Query-graph for RQ

Figure 2: Query-graphs of various queries and templates Figure 3: Application
of seeding in Equation D2 Figure 4: Application of seeding in Equation D3
Figure 5: Application of seeding in Equation D4

##  4 Enumeration

Informally, enumeration refers to the process of considering a set of
equivalent query plans and the enumerator refers to the component of the query
optimizer that facilitates this process. We elaborate on our enumerator’s
design, how we had to go beyond conventional design, and how it represents the
query plans it enumerates in § 4.1. In § 4.2 and § 4.3, two of the main
enumeration rules involved in optimizing navigational graph queries are
presented. Finally, the complexity of the enumeration procedure is discussed
in § 4.4.

###  4.1 Enumerator design

A conventional way of enumerating (tree-structured) query plans is to use a
bottom-up dynamic programming algorithm which constructs query plans for
increasingly larger sub-expressions of the input query by combining query
plans for smaller sub-expressions which have already been constructed
DBLP:conf/sigmod/MoerkotteDP . Let $n$ be the size of an input query. While a
query’s size is typically directly proportional to the number of predicates it
contains, we refrain from giving an exact definition here. A bottom-up
enumerator would start by producing plans for sub-problems of size $1$, which
would typically be reading ‘base’ relations. Then, the algorithm would
consider sub-problems of size $i$ with $2\leq i\leq n$ in increasing order,
and for each $i$ consider combining solutions to sub-problems of sizes $1\leq
k\leq i-1$ and $i-k$ into a solution to the sub-problem of size $i$.

A drawback of the bottom-up approach, is that many combinations of solutions
to sub-problems of sizes $k$ and $i-k$ will not produce a semantically valid
solution to the problem of size $i$. While checking the validity of such a
combination may not be very expensive, it is a source of inefficiency
nevertheless DBLP:conf/icde/FenderM11 ; DBLP:phd/de/Neumann2005a . This
problem is further compounded when we want to consider solutions to a sub-
problem of size $i$ that consist of more than two solutions to smaller sub-
problems. Our top-down approach avoids this problem by embedding instances of
sub-problems into partial solutions. Therefore, whenever a sub-problem is
considered, solving it must produce a semantically valid solution.

Another convention is to have a rule-based design. Such a design offers
modularity and extensibility to the enumerator. The enumerator’s overall
design and the set of rules it is configured to use at any one time together
determine the set of query plans that will be considered for an input query.
To extend the enumerator’s capabilities, new query features can be easily
supported by new rules, and new rules can easily be added to the set of rules.

We adopt the rule-based design for our enumerator. A set of enumeration rules
will typically contain at least one rule for each algebraic type (e.g., join,
select, project, etc.) supported by the input query language. This ensures
that a query plan can be found for any input query, regardless of the nesting
of algebraic types. In this paper, we refrain from giving an algebraic
specification of the Regular Queries and instead continue to present queries,
optimizations and enumeration rules using Datalog because this is more
convenient for a discussion on seeding. We do note that such algebras exist
though, for example the Regular Property Graph Algebra (RPGA)
DBLP:series/synthesis/2018Bonifati . In order to support the other constructs
that comprise RQs besides those discussed in the subsequent sections,
additional enumeration rules are required. Because these rules are not
directly relevant to the topic of seeding, they are presented in an online
appendix Ymous_Optimizing_Navigational_Queries  rather than the main body of
this text.

####  4.1.1 Query plan representation

Our model for representing query plans is a directed graph of logical
operators. A query plan is an expression of the form $\mathcal{P}=(O,r)$ with
$O$ a set of operators and $r\in O$ the root operator. The topology of a plan
is captured by a recursive parent-child relationship. Most operator types are
defined in terms of one or more child operators. We define eleven types of
operators to be used in query plans. Six of these operator types are well-
known from the Relational Algebra, although they might differ slightly from
Codd’s original specification codd_ra . The eleven types are as follows:

  * •

$E(i)$ obtains an intermediate result by reading the edge relation $E$ and
assigns an fresh identifier $i\in\mathbb{N}$ to distinguish multiple instances
of $E$,

  * •

$P(i)$ obtains an intermediate result by reading the property relation $P$ and
assigns an fresh identifier $i\in\mathbb{N}$ to distinguish multiple instances
of $P$,

  * •

$\bowtie(J,c_{l},c_{r})$ obtains an intermediate result from its left- and
right child operators $c_{l}$ and $c_{r}$ and joins them based on a set of
join predicates $J$,

  * •

$\Pi(V,c)$ obtains an intermediate result from its child operator $c$ and
projects each tuple only to the variables in the set of variables $V$,

  * •

$\rho(f,c)$ obtains an intermediate result from its child operator $c$ and
renames variables according to a function $f$,

  * •

$\sigma(F,c)$ obtains an intermediate result from its child operator $c$ and
filters it based on a set of filter predicates $F$,

  * •

$\cup(c_{1},...,c_{n})$ obtains intermediate results from its $n$ child
operators and produces their union,

  * •

$\alpha(b,c)$ obtains an intermediate result from its child operator $c$ and
writes it to a buffer $b$,

  * •

$\beta(b)$ obtains an intermediate result by reading from a buffer $b$,

  * •

$\delta(c)$ obtains an intermediate result from its child operator $c$ and
keeps only those tuples that were never part of this- or any previous
intermediate result obtained from $c$, and

  * •

$\square(Q)$ encapsulates a query $Q$ inside an abstraction operator.

The latter four operator types are not part of the Relational Algebra and so
require further clarification. The $\alpha$ and $\beta$ operators both
interact with a buffer. This buffer can be regarded as a temporary
materialized view which exists only for the duration of query evaluation. The
purpose of such buffers is to go beyond query plans with a strict tree
structure, to query plans where an operator can have more than one consumer.
Furthermore, the use of buffers allows a cyclic flow of tuples through a query
plan, thus enabling plans that can evaluate recursive queries, such as RQs.
Note that it is the flow of tuples which may follow a cycle. A query plan is
ultimately a high-level representation of a computer program and so cannot,
and will not, have direct cyclic dependencies between its operators. Such
dependencies are avoided by the use of buffers as intermediaries. The $\alpha$
operator captures writing to a buffer. As a consequence, there should be
exactly one $\alpha$ operator associated with each buffer used by any query
plan. The $\beta$ operator captures reading from a buffer, and so there should
be one or more $\beta$ operators associated with each buffer. It is worth
noting that the concept of a buffer is used only on the level of logical query
plans. The existence of buffers on the logical level does not imply that
intermediate results with multiple- or cyclic consumers will be (fully)
materialized in a view on the physical level, although this is one possible
solution.

The $\delta$ operator removes duplicates across multiple intermediate results.
This is necessary in plans that evaluate closures, in order to reach a fix-
point in the presence of cycles in the data graph.

The abstraction operator $\square$ allows for a query to be embedded into a
query plan. Embedding queries into query plans can be thought of as a specific
form of embedding instances of recursive sub-problems into partial solutions.
This embedding enables the construction of an extremely flexible top-down
enumerator that relies on memoization, rather than a bottom-up enumerator that
relies on a more rigid dynamic-programming table.

Because a bottom-up enumerator processes problems in order of increasing size,
it is guaranteed to consider all combinations of solutions to sub-problems
that could be combined into an optimal solution to each problem it processes.
Our top-down enumerator must have the same property, which we provide by
enforcing a depth-first order on the processing of abstractions. The depth-
first order ensures that the size of sub-problems being processed is always
decreasing, until a further decrease becomes impossible and the procedure
back-tracks. Because multiple (partial) plans can exist simultaneously, and
because each plan can contain multiple abstractions, we use a global stack of
query plans and a stack of abstractions per plan. The global stack will be
denoted $\mathcal{S}$ and $\mathcal{P.A}$ will denote the stack associated
with plan $\mathcal{P}$.

####  4.1.2 Enumeration algorithm

Let $R$ be a finite set of enumeration rules and $\mathcal{S}$ a stack of
query plans. The enumeration algorithm then boils down to a while-loop that
tries to empty $\mathcal{S}$ be repeatedly applying memoization and the
enumeration rules. Pseudo-code for this algorithm is shown in Algorithm 1.

Algorithm 1 Enumerate($Q_{in}$)

1:$\mathcal{P}_{in}\leftarrow(\\{o\\},o=\square(Q_{in}))$

2:Add $\mathcal{P}_{in}$ to $\mathcal{S}$

3:while $\mathcal{S}$ is not empty do

4: Let $\mathcal{P}$ be the top query plan on $\mathcal{S}$

5: if $\mathcal{P}$ contains no abstractions then

6: Memoize $\mathcal{P}$, remove it from $\mathcal{S}$ and continue

7: Let $\square(Q)$ be the top abstraction of $\mathcal{P.A}$

8: Let $M$ be the set of memoized plans for $\square(Q)$

9: if $M\neq\emptyset$ then

10: Let $\mathcal{P}_{M}$ be the memoized plan for $\square(Q)$

11: Let $\mathcal{P}_{R}$ be a copy of $\mathcal{P}$, replacing $\square(Q)$
by $\mathcal{P}_{M}$

12: Add $\mathcal{P}_{R}$ to $\mathcal{S}$

13: else

14: for rule $r$ in rule set $R$ do

15: for each $\mathcal{P}_{R}$ generated by applying $r$ to $\square(Q)$ do

16: Add $\mathcal{P}_{R}$ to $\mathcal{S}$

17:return the memoized solution for $\square(Q_{in})$

Figure 6: Example enumeration process (§ 4.2)

###  4.2 Join rule

The join rule can be applied to any query of the form
$Q(\overline{x})\leftarrow
L_{1}(\overline{y_{1}}),...,L_{n}(\overline{y_{n}})$ such that the join graph
for $Q$ is connected. Its purpose is to take the set of predicates in the body
$\mathcal{B}=\\{L_{1},...,L_{n}\\}$ and construct all possible pairs $(T,U)$
where $T$ and $U$ are strict, non-empty and disjoint subsets of $\mathcal{B}$
such that $T\cup U=\mathcal{B}$ holds, the join graphs of $T$ and $U$ are
connected and there exists at least one join predicate between $T$ and $U$.
Note that for any such pair $(T,U)$ there exists a symmetric pair $(U,T)$. We
want to consider exactly one pair per symmetric case. The problem of
enumerating all such pairs efficiently while avoiding symmetric cases, has
been studied extensively in the context of relational databases ono90 ;
DBLP:conf/icde/FenderM11 ; DBLP:journals/tkde/FenderM12/reassessing ;
DBLP:journals/pvldb/FenderM13/counterstrike ; DBLP:conf/sigmod/DeHaanT07 ;
DBLP:conf/sigmod/MoerkotteDP . Hence, we employ a state-of-the-art algorithm
developed in the relational context for precisly this purpose, namely
MinCutBranch (MCB)DBLP:conf/icde/FenderM11 .

$\displaystyle V(s,t)\leftarrow$
$\displaystyle\,E(s,e,t),P(e,\text{label},l_{1})$ (Q4) $\displaystyle
W(s,t)\leftarrow$ $\displaystyle\,E(s,e,t),P(e,\text{label},l_{2})$
$\displaystyle Y(s,t)\leftarrow$
$\displaystyle\,E(s,e,t),P(e,\text{label},l_{3})$ $\displaystyle
Z(s,t)\leftarrow$ $\displaystyle\,E(s,e,t),P(e,\text{label},l_{4})$
$\displaystyle{\scriptstyle Ans(x,y,z)}\leftarrow$
$\displaystyle\,V^{+}(s,x),W^{+}(x,y),Y^{+}(y,z),Z(x,z)$

The join rule would construct one plan for each of the following pairs of
subsets of $\\{V^{+},W^{+},Y^{+},Z\\}$ from Equation Q4 whose query-graph is
displayed in 2(c):

$\displaystyle(\\{V^{+}\\},\\{W^{+},Y^{+},Z\\})$
$\displaystyle(\\{W^{+}\\},\\{V^{+},Y^{+},Z\\})$
$\displaystyle(\\{Y^{+}\\},\\{V^{+},W^{+},Z\\})$
$\displaystyle(\\{Z\\},\\{V^{+},W^{+},Y^{+}\\})$
$\displaystyle(\\{V^{+},W^{+}\\},\\{Y^{+},Z\\})$
$\displaystyle(\\{V^{+},Z\\},\\{W^{+},Y^{+}\\})$

By repeated application of the join rule, all join orders avoiding Cartesian
products are constructed. In practice, we typically construct more than one
plan per pair of subsets. First, the pair is ‘switched’ to its symmetric
counter-part thus capturing the commutativity of the join operation.
Furthermore, various types of annotations may be added to distinguish hash-,
merge- and nested-loop joins, etc. Provided that the set of equivalences
(e.g., commutativity) and join algorithms (e.g., hash join) is fixed at
runtime, the number of plans constructed per pair of subsets is constant. In
order to simplify any analysis of the join rule, we will assume that only one
plan is constructed per pair of subsets.

The enumeration process for a query that expresses a join between relations
$R$ and $S$ and $S$ and $T$ (but not directly between $R$ and $T$) is
displayed in Figure 6. This process can be thought of as walking a tree where
the root is an abstraction over the input query (in this case represented as
$\square(RST)$) and the leaves are fully fledged or concrete logical plans.
The inner vertices of this tree are partial plans. Step 1 is to take
$\square(RST)$ and apply the set of enumeration rules. Application of the join
rule creates two plans which each contain a pair of abstractions. Step 2 is to
take the top plan and its top abstraction (in this case $\square(T)$) and
apply the enumeration rules again. This yields one concrete plan, which is
subsequently memoized. Step 3 replaces $\square(T)$ in the plan produced in
step 1 with the plan for $T$ memoized in step 2. The process of rule
application, memoization and replacement repeats until no more partial plans
remain.

###  4.3 Seeding rule

Informally, the seeding rule takes a conjunctive query that contains at least
one closure, tries to construct a seeding query and to use it to obtain seeds
for all transitive closures in the query. A more precise description follows
in § 4.3.1 and § 4.3.2, construction of the seeding query and the seeded
closures are discussed in § 4.3.3 through § 4.3.5.

####  4.3.1 Seeding rule overview

The seeding rule can be applied to any query of the form
$Q(\overline{x})\leftarrow
L_{1}(\overline{y}_{1}),...,L_{n}(\overline{y}_{n})$ such that the following
statements hold:

  * •

the join graph for $Q$ is connected,

  * •

the body of $Q$ contains at least one transitive closure, and

  * •

the body of $Q$ does not contain an interior closure for which freeing either
variable produces a disconnected seed.

We define the set of predicates in the body of $Q$ as
$\mathcal{B}=\\{L_{1},...,L_{n}\\}$ and the union of the output projections of
those predicates as $Y=\bigcup_{1\leq i\leq n}\overline{y}_{i}$. The purpose
of the seeding rule is to take $Q$ and ‘split’ it into a seeding query and
$1\leq k\leq n$ fix-point procedures and construct the corresponding query
plan. Note that exactly one plan is constructed for any valid input query. The
process can be subdivided into four steps, namely:

  1. 1.

partitioning $\mathcal{B}$ into sets $N,I$ and $X$,

  2. 2.

constructing a seeding query based on $N$, $I$ and $X$,

  3. 3.

processing each closure in $I$ and,

  4. 4.

processing each closure in $X$.

Steps two and three employ one heuristic each. While both heuristics introduce
a potential for missing a lower cost plan, they eliminate two sources of
exponential increase in the plan space size, namely:

  * •

$h1$ avoids enumerating $2^{m}$ options of which variable to free for $0<m$
interior closures, and

  * •

$h2$ avoids enumerating $\frac{1}{2}m!$ orders of stacking $2<m$ interior
closures.

####  4.3.2 Partitioning closures

We partition $\mathcal{B}$ into a set of non-recursive predicates $N$, a set
of interior closures $I$ and a set of exterior closures $X$, by checking for
each $L_{i}(\overline{y}_{i})\in\mathcal{B}$ whether it is recursive at all,
and if so, whether all variables in $\overline{y}_{i}$ participate in at least
one join-predicate. For Equation Q4, the resulting partitions would be:

$\displaystyle N=$
$\displaystyle\\{Z(x,z)\\},I=\\{W^{+}(x,y),Y^{+}(y,z)\\}\text{ and}$
$\displaystyle X=$ $\displaystyle\\{V^{+}(s,x)\\}$

This is because $Z(x,z)$ is not recursive, $V^{+}(s,x)$ is recursive but $s$
does not participate in any join-predicate in Equation Q4, and $W^{+}(x,y)$
and $Y^{+}(y,z)$ are both recursive and $x,y$ and $z$ all participate in at
least one join-predicate in Equation Q4.

####  4.3.3 Seeding query construction

Let $Q_{s}(\overline{x}_{s})\leftarrow\mathcal{B}_{s}$ be the seeding query.
The body $\mathcal{B}_{s}$ is defined as the conjunction of the predicates in
the set:

$\displaystyle N\cup\\{h_{1}(L_{i}^{+})\,|\,L_{i}^{+}\in
I\\}\cup\\{L_{i}\,|\,L_{i}^{+}\in X\\}$

where $h_{1}$ is a heuristic function that takes an interior closure
$L_{i}^{+}$, decides which variable to free, and produces a version of the
base $L_{i}$ in which the freed variable is renamed to a fresh variable (i.e.,
the join by way of a common variable between it and any other predicate in the
body of $Q_{s}$ is removed). In our implementation, $h_{1}$ picks $x$ for any
$L_{i}^{+}(x,y)$ if it produces a connected seeding relation, and only picks
$y$ if it does not. For any $L_{i}\in\mathcal{B}_{s}$ such that $L_{i}^{+}\in
I\cup X$ we may need to extend the set of output variables $\overline{x}_{s}$.
That is, by default $\overline{x}_{s}=\overline{x}$ but $\overline{x}$ may not
contain the free(d) variable from $L_{i}$, which must be added. For Equation
Q4 the resulting seeding query, assuming $h_{1}$ decides to free $y$ for both
$W^{+}(x,y)$ and $Y^{+}(y,z)$ and rename it to $y_{1}$ and $y_{2}$
respectively, would be:

$\displaystyle Q_{s}(s,x,y_{1},y_{2},z)\leftarrow
V(s,x),W(x,y_{1}),Y(y_{2},z),Z(x,z)$

Notice that the variable $s$ has been added to $\overline{x}_{s}$. This is
necessary because the set of nodes that will bind to $s$ during query
evaluation, is the set that will be used as the seed for
$\overset{\scriptscriptstyle\leftarrow}{V}\vphantom{V}^{\scriptscriptstyle
S}(s,x)$.

####  4.3.4 Process interior closures

Having defined a query $Q_{s}$ that captures a seeding query for our query
plan, we wish to process each $L_{i}^{+}\in I$ and extend our query plan by
adding a fix-point procedure to it (by way of constructing a new sub-graph).
Step 1 in Figure 7 shows the query plan containing an abstraction over the
seeding query $Q_{s}$ and an $\alpha$-operator writing the evaluation of the
seeding query into a buffer for consumption by multiple consumers (i.e.,
multiple closures from $I\cup X$).

Here we employ heuristic $h_{2}$ to decide the order in which interior
closures are stacked (and therefore, the order in which they are joined with
their seeding relations). In our implementation, we consider closures in $I$
in order of increasing cardinality estimates. The rationale for this is
twofold. First, joining the results of closures in order of increasing
cardinality is expected to minimize the output cardinalities of those joins.
Second, we in turn expect to minimize the cardinalities of the seeds produced
by selectivity stacking.

Hence, we iterate $I$ in order of increasing cardinality estimates for each
$L_{i}^{+}$ and add a fix-point procedure to the plan. Moreover, after every
join that joins the $i^{th}$ transitive closure with the preceding $1\leq j<i$
closures we instantiate a new buffer and corresponding $\alpha$-operator that
facilitates the selectivity stacking. Step 2 in Figure 7 shows the query plan
after processing $I$.

####  4.3.5 Process exterior closures

Having processed all interior closures, we wish to process each $L_{i}^{+}\in
X$ and extend our query plan by adding a fix-point procedure. Figure 7 shows
the query plan for $Q$ after processing $X$. Buffer $b_{4}$ facilitates
selectivity stacking. That is, the exterior closure
$\overset{\scriptscriptstyle\leftarrow}{V}\vphantom{V}^{\scriptscriptstyle S}$
is computed based on the content of buffer $b_{4}$ which is the evaluation of
the query:

$\displaystyle Q_{s^{\prime}}(s,x,y,z)\leftarrow
V(s,x),W^{+}(x,y),Y^{+}(y,z),Z(x,z)$

The query $Q_{s^{\prime}}$ is a seeding query that is at least as selective as
(but in practice often much more selective than) the seeding query $Q_{s}$
whose evaluation defines the content of buffer $b_{1}$.

Figure 7: Constructing a seeded plan (§ 4.3.4)

Notice the inclusion of abstractions over the queries $Q_{1},Q_{2}$ and
$Q_{3}$ in Figure 7. These abstractions capture the fact that the recursive
sub-problems of how to expand
$\overset{\scriptscriptstyle\rightarrow}{W}\vphantom{W}^{\scriptscriptstyle
T},\overset{\scriptscriptstyle\leftarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}$ and
$\overset{\scriptscriptstyle\leftarrow}{V}\vphantom{V}^{\scriptscriptstyle S}$
on top of their respective seeds still need to be solved by the enumerator.
These queries correspond to the recursive Datalog rules
$\overset{\scriptscriptstyle\rightarrow}{W}\vphantom{W}^{\scriptscriptstyle
T}(x,y)\leftarrow\overset{\scriptscriptstyle\rightarrow}{W}\vphantom{W}^{\scriptscriptstyle
T}(x,w),W(w,y)$ for $Q_{1}$,
$\overset{\scriptscriptstyle\leftarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(y,z)\leftarrow
Y(y,w),\overset{\scriptscriptstyle\leftarrow}{Y}\vphantom{Y}^{\scriptscriptstyle
T}(w,z)$ for $Q_{2}$ and
$\overset{\scriptscriptstyle\leftarrow}{V}\vphantom{V}^{\scriptscriptstyle
S}(s,x)\leftarrow
V(s,w),\overset{\scriptscriptstyle\leftarrow}{V}\vphantom{V}^{\scriptscriptstyle
S}(w,x)$ for $Q_{3}$.

###  4.4 Complexity analysis

We analyze the impact that the application of the proposed optimizations has
on the complexity of the enumeration procedure. To this end, we will count the
total number of plans generated during optimization for a query of a
particular size and shape. The following definitions allow us to analyze the
complexity of the enumeration procedure.

###### Definition 5

Let $Q$ be a query. The optimization tree $\mathcal{T}_{Q}$ is the tree of
plans generated implicitly by applying Algorithm 1 to $Q$.

A node is added to $\mathcal{T}_{Q}$ when a plan $\mathcal{P}$ is added to the
stack $\mathcal{S}$ in either line 2, 12 or 16 of Algorithm 1. An edge is
added from any plan $\mathcal{P}$ taken from $\mathcal{S}$ in line 4 to any
plan $\mathcal{P}_{R}$ added to $\mathcal{S}$ in either line 12 or 16. The
tree is generated implicitly, without being materialized.

###### Definition 6

Given an optimization tree $\mathcal{T}_{Q}$, the set of leaves of
$\mathcal{T}_{Q}$ is denoted $L(\mathcal{T}_{Q})$.

The set of leaves of an optimization tree $\mathcal{T}_{Q}$ corresponds to the
set of concrete plans generated by Algorithm 1 and therefore also to the
number of times a cost-model is called when memoizing a plan.

###### Definition 7

Given a query $Q$, the optimization tree $\mathcal{T}_{Q,u}$ is the tree
generated by Algorithm 1 when not using the seeding rule.

###### Definition 8

Given a query $Q$, the optimization tree $\mathcal{T}_{Q,o}$ is the tree
generated by Algorithm 1 when using the seeding rule.

We derive functions $P_{u}(n)$ and $P_{o}(n)$ which count
$L(\mathcal{T}_{Q,u})$ and $L(\mathcal{T}_{Q,o})$ respectively, for a query
$Q$ of a fixed shape and variable size $n$. Then, we argue that for any input
query $Q$ there exists a constant $c$ such that $P_{o}(n)\leq c\cdot P_{u}(n)$
holds. In other words, we will argue that the number of plans generated when
using the seeding rule (i.e., when applying the proposed optimizations) is
within a constant factor of the number of plans generated without using the
seeding rule. From this, it follows that the complexity of the optimization
procedure when applying the proposed optimizations is within a constant factor
of the complexity of the procedure without the proposed optimizations. This is
because the sizes of any $\mathcal{T}_{Q,u}$ and $\mathcal{T}_{Q,o}$ are
proportional to the sizes of their respective sets of leaves (i.e., numbers of
concrete plans generated) multiplied by the size of $Q$ because the length of
any path from the root of such a tree to a leaf is directly proportional to
the size of $Q$.

The question remains how to fix the shape to guarantee that if $P_{o}(n)\leq
c\cdot P_{u}(n)$ holds for any query of this shape, that it indeed holds for
any query in general. To do this, it must maximize $c$ amongst all possible
queries. In other words, the shape must be such that it increases $P_{o}(n)$
as much as possible relative to $P_{u}(n)$.

The worst-case query shape, from the perspective of maximizing $c$, is a star-
shaped query consisting only of recursive terms. This query shape is shown in
8(b).

(a) non-recursive

(b) recursive

Figure 8: Star-shaped queries of $n$ terms (§ 4.4)

This shape maximizes $c$ because it maximizes the number of opportunities for
the seeding rule to be applied. The reason for this is twofold. Firstly,
because all terms in this shape are recursive, the seeding rule applies to any
set of terms of size at least two. Secondly, the star-shape maximizes the rate
at which the number of possible plans grows, and this rate of growth is
proportional to the number of sub-queries of the input query ono90 . The
number of sub-queries is in turn proportional to the number of times the
seeding rule can be applied.

We derive $P_{u}(n)$ and $P_{o}(n)$ based on the query shapes presented in
8(a) and 8(b), respectively. By deriving $P_{u}(n)$ based on the non-recursive
query in 8(a), we ensure by construction that the seeding rule does not apply.

####  4.4.1 Analysis of non-recursive star-shaped queries

The query shape from 8(a) can be analyzed using two templates $T_{1}$ and
$T_{2}$. Template $T_{1}$ represents abstractions consisting of $2\leq k\leq
n$ terms arranged in a star. That is, with $k=n$ this template represents the
input query. Template $T_{2}$ represents abstractions over a single term
$E_{i}$. The templates are specified as follows:

$\displaystyle T_{2}:\,E_{1}...E_{k}\quad\text{for }2\leq k\leq n$
$\displaystyle T_{2}:\,E_{1}$ (9)

Using these templates we can derive $P_{u}(n)$. We observe that there are $n$
ways to instantiate $T_{2}$ because there are $n$ terms to pick from in the
input query. Each instantiation yields a single plan because a single term
cannot be broken down further. Similarly, there are $\binom{n}{k}$ ways to
instantiate $T_{1}$ because we can pick any $k$ out of $n$ terms. There are
$2^{k-1}-1$ non-empty, strict subsets of a set of $k$ elements when not
counting a subset and its complement separately. Hence each instantiation of
$T_{1}$ yields $2^{k-1}-1$ plans.

Let $T_{i}(n,k)$ denote the number of plans generated by template $T_{i}$ for
sizes $n$ and $k$. The formula $P_{u}(n)$ can then be defined in terms of
$T_{1}(n,k)$ and $T_{2}(n,k)$ as follows:

$\displaystyle P_{u}(n)$
$\displaystyle=T_{2}(n,1)+\sum\limits_{k=2}^{n}T_{1}(n,k)$
$\displaystyle=n+\sum\limits_{k=2}^{n}\tbinom{n}{k}(2^{k-1}-1)$
$\displaystyle=\frac{1}{2}(3^{n}-2^{n+1}+2n+1)$ (10)

####  4.4.2 Analysis of recursive queries

The query shape from 8(b) can be analyzed using the previously defined
templates $T_{1}$ and $T_{2}$ alongside two new templates. Templates $T_{3}$
and $T_{4}$ are similar to $T_{1}$ and $T_{2}$ respectively, but are used to
represent recursive terms $E_{i}^{+}$ or sequences thereof. The templates are
specified as follows:

$\displaystyle T_{3}:$ $\displaystyle\,E_{1}^{+}...E_{k}^{+}\quad\text{for
}2\leq k\leq n$ (11) $\displaystyle T_{4}:$ $\displaystyle\,E_{1}^{+}$

There are $n$ ways to instantiate $T_{4}$ and each instantiation generates one
plan which captures a fix-point procedure for $E_{1}^{+}$. Template $T_{3}$
can be instantiated in $\binom{n}{k}$ ways, just as $T_{1}$ was. The number of
plans generated for each instantiation of $T_{3}$ is $2^{k-1}$, with
$2^{k-1}-1$ generated by the join rule and one plan by the seeding rule. The
formula $P_{o}(n)$ can then be defined as follows:

$\displaystyle P_{o}(n)$
$\displaystyle=T_{2}(n,1)+T_{4}(n,1)+\sum\limits_{k=2}^{n}T_{1}(n,k)+T_{3}(n,k)$
$\displaystyle=2n+\sum\limits_{k=2}^{n}\tbinom{n}{k}(2^{k-1}-1)+\tbinom{n}{k}2^{k-1}$
$\displaystyle=2n+\sum\limits_{k=2}^{n}\tbinom{n}{k}(2^{k}-1)$
$\displaystyle=3^{n}+2^{n-1}(n-2)+3n$ (12)

Having defined $P_{u}(n)$ and $P_{o}(n)$ we can relate both formulas and
conclude that the proposed optimizations can be applied with only a constant
factor increase to the complexity of the optimization procedure.

###### Theorem 4.1

For all $n\geq 2$ it holds that:

$\displaystyle P_{o}(n)$ $\displaystyle\leq 6\cdot
P_{u}(n)\quad\Leftrightarrow$ $\displaystyle 3^{n}+2^{n-1}(n-2)+3n$
$\displaystyle\leq 6\cdot\Bigl{(}\frac{1}{2}(3^{n}-2^{n+1}+2n+1)\Bigr{)}$

###### Proof

By a straight-forward induction on $n$.

###### Corollary 1

The optimization procedure’s complexity when applying the proposed
optimizations is within a constant factor of its complexity when not applying
these optimizations.

###  4.5 Cost-based optimization

While the enumerator generates a set of query plans for a given input query,
only a single plan from this set is ultimately executed in order to obtain the
query’s result. Choosing which one plan to execute is commonly done on the
basis of some estimated cost. The estimated cost of a plan represents the
estimated amount of time and possibly other resources such as memory and disk
I/O required to execute the plan. A plan with lower estimated cost is to be
preferred over an alternative plan with higher estimated cost at any stage
during the optimization procedure. Producing high quality cost estimates (and
cardinality estimates as a component thereof) is a very challenging problem
DBLP:journals/tkde/LeeuwenFY23 ; 10.14778/3503585.3503586 , not only in the
graph- but also in the relational paradigm, and it is something that even
mature database systems often struggle with DBLP:journals/vldb/LeisRGMBKN18 .
As such, an in-depth discussion of cardinality- and cost estimation for
Regular Queries on graphs and the type of query plans we have proposed is
beyond the scope of this work.

Nevertheless, our approach does employ cost-based optimization and therefore
must provide some form of cost estimation. The estimation methods are similar
to existing approaches DBLP:conf/sigmod/YakovetsGG16 ;
DBLP:conf/sigmod/JachietGGL20  in so far as that they rely on a catalog of
stored facts and statistics about the database instance, such as the number of
edges in the graph, the number of edges with a certain label for each label in
the graph and synopses of the sets of nodes that have edges with a certain
label incoming on- or outgoing from them. Based on this information, a naive
cost estimate can be produced for any query plan our enumerator is capable of
generating. We will show experimentally that our naive approach to cost-based
optimization (naive w.r.t. the estimation only) already provides worthwhile
speed-ups in terms of query evaluation, while recognizing cardinality- and
cost estimation as two obvious areas of improvement for the system.

##  5 Experimental Study

We next investigate the empirical behavior of our new methods, demonstrating
that they enable orders of magnitude improvements in query evaluation
performance. Three main conclusions can be drawn from this experimental study,
which are summarized below.

##### Conclusion (1): the proposed optimizations are potent.

By which we mean that the performance improvements offered by the proposed
optimizations are significant. Note that this concerns the optimizations
themselves, and not yet their application in a cost-based optimizer. In other
words, we conclude that the performance of the best plan in practice that uses
any of the proposed optimizations, is often significantly better than the
performance of the best plan in practice amongst those plans that do not use
any of the proposed optimizations. Whether the optimizations can be applied
effectively in a cost-based optimizer is investigated separately.

##### Conclusion (2): the proposed optimizations can be applied effectively.

In order to apply an optimization technique effectively its application must
not have a detrimental effect on the performance of the optimization procedure
itself. Moreover, the improvement to query evaluation performance achieved
through cost-based optimization (i.e., choosing an estimated best plan, rather
than necessarily obtaining the best plan in practice) must be significant.

Template | CCC (#instances = 24) | PCC2 (#instances = 16) | PCC3 (#instances = 4) | All (#instances = 44)
---|---|---|---|---
Metric | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT
Min | 0.536 | 0.419 | 1 | 0.625 | 0.405 | 0.105 | 1 | 0.227 | 1.91 | 0.552 | 1.9 | 0.761 | 0.405 | 0.105 | 1 | 0.227
| 10 | 1 | 1 | 1.02 | 0.679 | 1 | 0.405 | 1 | 0.581 | 1.91 | 0.552 | 1.9 | 0.761 | 1 | 0.552 | 1 | 0.679
| 25 | 1.13 | 1.07 | 1.3 | 0.763 | 1 | 1 | 1 | 0.885 | 1.91 | 0.552 | 1.9 | 0.761 | 1 | 1 | 1.13 | 0.862
| 50 | 1.77 | 1.68 | 1.98 | 1.89 | 1 | 1 | 1.27 | 1.11 | 4.25 | 2.34 | 4.87 | 3.09 | 1.77 | 1.59 | 1.9 | 1.88
| 75 | 5.52 | 3.21 | 6.43 | 3.48 | 2.1 | 2.1 | 3.52 | 3.41 | 12.9 | 2.94 | 12.9 | 3.57 | 4.32 | 3 | 4.87 | 3.57
Percentile | 90 | 11.7 | 6.23 | 13 | 6.93 | 5.23 | 5.24 | 6.4 | 5.87 | 70.5 | 2.94 | 80 | 3.68 | 11.7 | 5.24 | 12.9 | 6.9
Max | 74.1 | 75 | 75 | 59.1 | 11.7 | 11.1 | 11.6 | 7.23 | 70.5 | 2.94 | 80 | 3.68 | 74.1 | 75 | 80 | 59.1
Mean | 6.42 | 5.38 | 6.93 | 5.35 | 2.38 | 2.25 | 2.74 | 2.28 | 22.4 | 2.19 | 24.9 | 2.78 | 6.4 | 3.95 | 7.04 | 4
PC (PT) = potential improvement in terms of cardinality (query time), AC (AT)
= actual improvement in terms of cardinality (query time)

Table 1: Potential- and minimal actual improvements on STRING (rounded to 3
significant digits). Median improvements in terms of query evaluation time
(PT, AT) are significant. Maximal improvements in terms of time (AT) are up to
an order of magnitude. For some instances, more data is processed by optimized
plans without large detriment to evaluation time. (§ 5.3.1,§ 5.3.2)

##### Conclusion (3): the application of the proposed optimizations enables
significant speed-ups of up to several orders of magnitude in terms of query
evaluation performance over state-of-the-art systems.

We place the performance figures obtained using our system in which the
proposed optimizations are implemented, in the context of the performance
achieved by state-of-the-art systems.

###  5.1 Methodology and setup

Some terminology is required to describe the methodology and setup. For an
arbitrary query $Q$ and plan $p$ we define:

  * •

$\mathbb{U}_{Q}$ the set of unoptimized plans for $Q$ (i.e., plans that do not
use any of the proposed optimizations),

  * •

$\mathbb{O}_{Q}$ the set of optimized plans for $Q$ (i.e., plans that use at
least one of the proposed optimizations),

  * •

$\widehat{p}_{u}\in\mathbb{U}_{Q}$ the estimated best unoptimized plan,

  * •

$\widehat{p}_{o}\in\mathbb{O}_{Q}$ the estimated best optimized plan,

  * •

$\overline{p}_{u}\in\mathbb{U}_{Q}$ the best unoptimized plan in practice,

  * •

$\overline{p}_{o}\in\mathbb{O}_{Q}$ the best optimized plan in practice,

  * •

$c(p)$ the total number of tuples (cardinality) processed during execution of
$p$,

  * •

$t_{\texttt{opt}}(p)$ the optimization time (ms) to obtain $p$,

  * •

$t_{\texttt{exe}}(p)$ the execution time (ms) of $p$,

  * •

$t(p)=t_{\texttt{opt}}(p)+t_{\texttt{exe}}(p)$ the evaluation time (ms) of
$p$,

  * •

$\dfrac{c(\overline{p}_{u})}{c(\overline{p}_{o})}$ the potential improvement
(PC) in terms of cardinality (i.e., total number of tuples processed),

  * •

$\dfrac{t(\overline{p}_{u})}{t(\overline{p}_{o})}$ the potential improvement
(PT) in terms of query evaluation time,

  * •

$\dfrac{c(\overline{p}_{u})}{c(\widehat{p}_{o})}$ the minimal actual
improvement (AC) in terms of cardinality, and

  * •

$\dfrac{t(\overline{p}_{u})}{t(\widehat{p}_{o})}$ the minimal actual
improvement (AT) in terms of query evaluation time.

By “total number of tuples processed” we mean the sum of all numbers of tuples
output by operators that generate new tuples (i.e., reading edge-triples,
performing joins, etc.) while ignoring the tuples output by operators that
only ‘forward’ tuples (i.e., unions, projections, selections, renames, et
cetera).

Note that the metrics AC and AT are minimal in the sense that the improvement
of $\widehat{p}_{o}$ over any $p\in\mathbb{U}_{Q}$ is at least as large as the
improvement over $\overline{p}_{u}$. This makes the baseline a hypothetical
system that always picks the best possible plan from $\mathbb{U}_{Q}$.
Therefore, the setup is disadvantageous to our proposed system on this point
making the results obtained conservative.

The reason for looking at total cardinality alongside query evaluation time,
is that the former offers an implementation-independent view on the savings
made through the use of the proposed optimizations. That is, if less data is
being processed in order to evaluate a query when the optimizations are used
(i.e., PC and AC are larger than one), this is beneficial regardless of the
system on which the evaluation is performed.

We investigate the PC and PT metrics for a multitude of queries on two diverse
datasets. To show that the proposed optimizations can be applied effectively
we look at the time $t_{\texttt{opt}}(\widehat{p}_{o})$ spent to obtain
$\widehat{p}_{o}$ for various queries, and we consider the metrics AC and AT.
Finally, to place the performance of our system with- and without the use of
the proposed optimizations in context w.r.t. state-of-the-art systems we
investigate the query evaluation time $t(\widehat{p}_{o})$ for various queries
and datasets. Note that $\widehat{p}_{o}$ is defined independently with
respect to each system.

The remainder of this section is structured as follows. The workloads, in
terms of query templates, instances and datasets are discussed in § 5.2. The
experimental environment and the systems under consideration are the subject
of § 5.2.3 and § 5.2.4. Finally, the experiments supporting each of the three
main conclusions are discussed in § 5.3.

###  5.2 Workloads

In our experimental study, we adopt the methodology used by state-of-the-art
studies DBLP:conf/sigmod/YakovetsGG16 ; DBLP:conf/sigmod/JachietGGL20 ;
arroyuelo2023optimizing . This involved defining benchmarking workloads by
_mining_ instances of queries based on predefined templates from a variety of
datasets across diverse application domains. The mined queries were then used
to evaluate the performance of the query evaluation engines of the systems
under study.

####  5.2.1 Query templates and instances

We will use the terms query template and query instance (or simply template
and instance) throughout the experimental section (not to be confused with the
templates used for analysis in § 4.4). A query template is a generic
specification of a graph query that lacks constants such as edge labels and
filter values. We mine combinations of edge labels and filter values from real
property graphs to construct concrete query instances. From the set of query
instances mined in this way, we identify a subset of valid instances. An
instance if valid if and only if it satisfies the following three criteria:

  1. 1.

the instance must have a non-empty result on the dataset from which it was
mined,

  2. 2.

evaluation of the instance must terminate successfully (e.g., without timing
out) on at least one system, and

  3. 3.

evaluation of the instance using $\widehat{p}_{u}$ on our system must take at
least one second.

The third criterion excludes queries that are already ‘fast’ and focuses
instead on those queries worth optimizing. Moreover, any performance gains
that could be made on queries which are already ‘sub-second’ are more
difficult to attribute wholly to the proposed optimizations. All query
instances are converted to count queries. That is, instead of materializing
the full set of results, we only count the number of results. We do not employ
optimizations for count queries in particular anywhere in our system.
Definitions for the templates are given in Equation 13.

These templates were chosen because they are fundamental, simple and
intuitive. They are fundamental because they capture the essence of the
navigational queries that are commonly used in practice wdbench . They are
simple because they are composed of few relations and filters. They are
intuitive because they capture intuitive natural language questions which
combine ‘connectedness’ (i.e., reachability) and conjunction. For example, the
CCC and PCC templates ask for “connected components which have something in
common” and “components which are connected in more than one way”,
respectively. The variables $l_{1},l_{2},l_{3}$ and $c_{1}$ are placeholders
for edge labels and a filter value. An exhaustive list of all query instances
used and their specification in SPARQL and SQL can be found here
Ymous_Optimizing_Navigational_Queries .

$\displaystyle R(s,t)\leftarrow E(s,e,t),P(e,\text{label},l_{1})$ (13)
$\displaystyle S(s,t)\leftarrow E(s,e,t),P(e,\text{label},l_{2})$
$\displaystyle T(s,t)\leftarrow E(s,e,t),P(e,\text{label},l_{3})$
$\displaystyle CCC1(x,y,z)\leftarrow R^{+}(x,y),S(x,z),T(z,y)$ $\displaystyle
CCC2(x,y,z)\leftarrow R^{+}(x,y),S(x,z),T(y,z)$ $\displaystyle
CCC3(x,y,z)\leftarrow R^{+}(x,y),S(z,x),T(z,y)$ $\displaystyle
CCC4(x,y,z)\leftarrow R^{+}(x,y),S(z,x),T(y,z)$ $\displaystyle
PCC2(x,y)\leftarrow R^{+}(x,y),S^{+}(x,y)$ $\displaystyle PCC3(x,y)\leftarrow
R^{+}(x,y),S^{+}(x,y),T^{+}(x,y)$ $\displaystyle I(x,y)\leftarrow
S(x,y),T^{+}(x,z),z=c_{1}$ $\displaystyle RQ(x,y,z)\leftarrow
R(x,y),I^{+}(y,z)$

####  5.2.2 Datasets

We conduct experiments on two real-world datasets coming from diverse
application domains, namely DBPedia’s 2020 release
(DBPedia)DBLP:journals/semweb/LehmannIJJKMHMK15 ;
DBLP:conf/i-semantics/HoferHDF20  and the sub-graph related to humans of the
Search Tool for the Retrieval of Interacting Genes/Proteins
(STRING)stringdb/gkac1000 . DBPedia is a knowledge graph composed of
information created in various Wikimedia projects. STRING is a database of
known and predicted protein-protein interactions, which can be searched on a
per-organism basis. The full 2020 release of DBPedia contains upwards of
$483$M edges and features almost $55$K distinct edge labels. The sub-graph of
STRING pertaining to humans contains just over 1.5M edges (protein-protein
interactions)111Protein-protein interactions are symmetric. As a consequence
the query templates CCC1, CCC2, CCC3 and CCC4 all default to the same semantic
meaning and so are referred to as CCC for STRING. and 19.5K nodes (distinct
proteins). Humans are the most frequently queried organism in practice on
STRING’s online access point Web:sting-statistics . Moreover, the sub-graph of
human proteins is particularly dense. Because our optimizations attempt to
leverage the selectivities of join predicates, a denser data graph is a more
challenging data graph. More detailed information on the process of turning
subsets of DBPedia and STRING into property graphs can be found here
Ymous_Optimizing_Navigational_Queries .

####  5.2.3 Environment

All systems are deployed in the same environment and evaluation times are
averaged over five runs. Plans that take more than a set time limit to
complete are timed-out. This time limit is 2 minutes for STRING and 10 minutes
for DBPedia. A lower limit is used for STRING because the average query
evaluation time is higher on STRING due to its density and as a consequence
exploring plan spaces exhaustively with a greater time limit is infeasible in
practice222As a further consequence, exhaustively exploring $\mathbb{O}_{Q}$
to find $\overline{p}_{o}$ is infeasible for the RQ template on STRING.. The
experiments are performed on a server running Ubuntu 20.04 with two Intel Xeon
E5-2697 v2 CPUs (12 cores each, 2 threads per core at 2.7GHz) and 492 GB of
RAM. The amount of RAM available to each database system is limited to 320 GB.

####  5.2.4 Systems

We evaluate the workloads on various state-of-the-art systems, namely:
AvantGraphu (our system with optimizations disabled (AGu)), AvantGrapho (our
system with optimizations enabled (AGo)), MillenniumDB 0.2 (MDB), DuckDB 0.8.1
(DDB), PostgreSQL 16.0 (PG), and Virtuoso 7.2 (VT).

Taken together these systems provide a representative view on the performance
of the query workloads on state-of-the-art systems. Furthermore, we note that
Kùzu kuzu:cidr ; kuzu-github  does not allow for the expression of transitive
closures, we could not obtain binaries for Umbra
DBLP:conf/cidr/NeumannF20/umbra  and TigerGraph
DBLP:journals/corr/abs-1901-08248/tigergraph  upon request, experienced
blocking technical difficulties in running DuckPGQ
DBLP:conf/cidr/WoldeSSB23/duckpgq ; Raasveldt_DuckDB/duckpgq .

Systems are configured as per vendor recommendations. For the relational
database systems DuckDB and PostgreSQL property graphs are stored as a table
of serialized triples (subject (S), predicate (P), object (O)) with several
indexes (SPO, PSO, OSP). For the SPARQL-based systems MillenniumDB and
Virtuoso property graphs are stored- and indexed using each system’s defaults
for graph-structured data. Finally, AvantGraph stores property graphs in a
compressed sparse row (CSR) format and two types of simple indexes are
constructed, namely one index facilitating the retrieval of all edges
associated with a key edge label and one index facilitating the retrieval of
all edges adjacent to- and associated with a key vertex and edge label.

###  5.3 Experiments

####  5.3.1 The proposed optimizations are potent

The potential improvements in terms of cardinality (PC) and evaluation time
(PT) are tabulated for STRING and DBPedia in Table 1 and Table 2,
respectively. We observe that the potential is high on STRING for the PCC3
template (median values of 4.25x and 4.87x), and significant for the other
templates (up to 1.98x for PT). For DBPedia, we observe that the potential is
high (median values in the range from 2.77x to 6.57x) for both PC and PT on
the CCC and RQ templates. Moreover, the potential for improvement is extreme
(median values in the range from 118x to 702x) for both PC and PT on the PCC2
and PCC3 templates.

There several instances of the PCC2 and PCC3 templates on both datasets for
which no $\overline{p}_{u}$ can be identified (i.e., all plans
$p\in\mathbb{U}_{Q}$ are timed-out). As a consequence, the necessary metrics
cannot be computed for these instances. It is important to note that the
proposed optimizations enable the evaluation of many such instances within the
time limit, as is shown in Table 3.

Template | CCC1 (# instances = 7) | CCC2 (# instances = 11) | CCC3 (# instances = 8) | CCC4 (# instances = 7)
---|---|---|---|---
Metric | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT
Min | 2.83 | 0.871 | 2.4 | 2.31 | 1.05 | 0.582 | 1.41 | 0.662 | 1.16 | 0.879 | 1.82 | 0.749 | 1.17 | 0.541 | 1.55 | 0.741
| 10 | 2.83 | 0.871 | 2.4 | 2.31 | 1.8 | 0.808 | 2.5 | 1.94 | 1.16 | 0.879 | 1.82 | 0.749 | 1.17 | 0.541 | 1.55 | 0.741
| 25 | 3.43 | 1.23 | 2.57 | 2.42 | 2.52 | 0.827 | 2.54 | 2.14 | 2.99 | 0.991 | 2.33 | 2.3 | 3.22 | 0.828 | 2.53 | 2.03
| 50 | 6.2 | 1.82 | 4.88 | 2.55 | 4.02 | 1.3 | 4.85 | 4.31 | 3.18 | 1.1 | 2.77 | 2.41 | 3.56 | 1.02 | 4.55 | 2.34
| 75 | 7.94 | 2.81 | 5.11 | 2.79 | 22.5 | 9.35 | 147 | 21.6 | 3.79 | 1.15 | 4.68 | 2.54 | 6.77 | 1.85 | 4.77 | 2.42
Percentile | 90 | 8.1 | 3.24 | 6.28 | 4.02 | 87.8 | 24.9 | 160 | 34.7 | 19.7 | 8.87 | 100 | 21.8 | 10.8 | 1.96 | 5.42 | 2.44
Max | 8.1 | 3.24 | 6.28 | 4.02 | 109 | 56.3 | 181 | 57.7 | 19.7 | 8.87 | 100 | 21.8 | 10.8 | 1.96 | 5.42 | 2.44
Mean | 5.73 | 1.95 | 4.15 | 2.73 | 22.5 | 9.59 | 47 | 12.5 | 5.23 | 2.14 | 15.5 | 4.67 | 4.8 | 1.19 | 3.97 | 2.1
Template | PCC2 (#instances = 57) | PCC3 (#instances = 4) | RQ (#instances = 127) | All (#instances = 221)
Metric | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT | PC | AC | PT | AT
Min | 1.36 | 0.575 | 1.53 | 1.03 | 25 | 0.944 | 50.3 | 0.675 | 3.06 | 1.02 | 2.31 | 0.929 | 1.05 | 0.541 | 1.41 | 0.662
| 10 | 17.4 | 2.23 | 19.2 | 2.26 | 25 | 0.944 | 50.3 | 0.675 | 5.03 | 1.97 | 2.75 | 1.09 | 4.02 | 1.1 | 2.74 | 1.12
| 25 | 65.1 | 2.27 | 75.6 | 2.4 | 25 | 0.944 | 50.3 | 0.675 | 5.99 | 2.07 | 4.58 | 1.16 | 5.99 | 2.06 | 4.62 | 1.18
| 50 | 141 | 43 | 185 | 42.9 | 118 | 1.89 | 702 | 1.42 | 6.57 | 2.11 | 4.9 | 1.2 | 22.5 | 2.17 | 28.7 | 1.32
| 75 | 601 | 121 | 623 | 132 | 383 | 4.43 | 727 | 1.48 | 123 | 2.25 | 95.9 | 1.25 | 131 | 24.9 | 144 | 34.7
Percentile | 90 | 2000 | 766 | 1060 | 846 | 800 | 4.43 | 882 | 2.51 | 144 | 33.6 | 152 | 71.5 | 239 | 52.7 | 385 | 83.6
Max | 11300 | 2120 | 6370 | 1480 | 800 | 4.43 | 882 | 2.51 | 217 | 56.8 | 173 | 98.9 | 11300 | 2120 | 6370 | 1480
Mean | 748 | 230 | 563 | 188 | 332 | 2.92 | 590 | 1.52 | 57.8 | 8.02 | 51.1 | 13 | 234 | 64.7 | 188 | 57
PC (PT) = potential improvement in terms of cardinality (query time), AC (AT)
= actual improvement in terms of cardinality (query time)

Table 2: Potential- and minimal actual improvements on DBPedia (rounded to 3
significant digits). Median improvements in terms of query evaluation time
(PT, AT) range from significant to extreme. The largest actual improvements
(AT) are up to three order of magnitude. (§ 5.3.1,§ 5.3.2)

Figure 9: Query evaluation time on STRING (left) and DBPedia (middle & right).
Significant speed-ups of up to several orders of magnitude are realised for
most templates (§ 5.3.3).

####  5.3.2 The proposed optimizations can be applied effectively

The effective application of the proposed optimizations depends on two things.
First, application of the optimizations should not be a detriment to the
performance of the query optimization procedure itself. Second, the
improvement to query evaluation performance achieved through cost-based
optimization should be significant.

Figure 10: The optimization time scales well in terms of query shape and size
(§ 5.3.2)

##### The impact on optimization time is modest.

We report that $t_{\texttt{opt}}(\widehat{p}_{o})$ is below $50$ milliseconds
for all query instances of all query templates on both datasets. In other
words, all queries considered in this work can be optimized very quickly using
the described procedure. To gain further insights into scalability we also
plot $t_{\texttt{opt}}(\widehat{p}_{o})$ for particular query shapes at
various sizes in Figure 10.

We consider two well-known query shapes that are extremely common in practice,
namely a chain query and a star query DBLP:journals/vldb/BonifatiMT20 . For
each shape, we consider a version consisting of $n$ non-recursive terms and
one (suffixed with ‘-r’) consisting of $n$ recursive terms, for values of $n$
from $2$ to $10$. For example, by “chain 3” we mean a query of three non-
recursive terms arranged in a chain pattern, and by “star-r 5” we mean a query
of five recursive terms arranged in a star pattern. Additionally, we consider
versions of the CCC template but with up to ten terms. We plot the time spent
on optimization for each combination of query shape and number of terms. All
times are averaged over five runs. We observe that the optimization times for
the chain and chain-r shapes increase very slowly as $n$ increases. This is as
expected because there exist relatively few viable join orders that avoid
Cartesian products for chain queries. The optimization times for the star,
star-r and CCC shapes increase at a significantly higher rate, roughly
tripling with each increment of $n$ for the larger values of $n$. This too is
expected, because the join graph for each of these shapes is a clique and so
the number of join orders increases exponentially. We conclude that the
enumerator’s design scales well since relatively ‘long’ chain-queries can be
optimized in far less than a second, and that even star-queries of up to six
recursive terms can be optimized in less than one second.

##### The improvements to query evaluation performance are significant.

The actual improvements (i.e., those achieved by the estimated best optimized
plan $\widehat{p}_{o}$ relative to $\overline{p}_{u}$ the best unoptimized
plan in practice) in terms of cardinality (AC) and evaluation time (AT) are
tabulated in Table 1 and Table 2.

We first consider the results on STRING. The median improvements in terms of
query evaluation time range from modest (1.11x) to significant (3.09x) and at
its most extreme, a 59-fold speed-up is achieved for the CCC template. We must
note that $\overline{p}_{u}$ outperforms $\widehat{p}_{o}$ on a few instances
(i.e., either AC or AT is below one). In such cases, the optimization
procedure simply ends up picking a worse plan than $\overline{p}_{u}$.
However, this happens only in a handful of instances.

In summary, the results on STRING show significant speed-ups in terms of
actual query evaluation time up to an order of magnitude while also showing
that even larger improvements are possible due to the discrepancies between
potential- and actual improvements. In other words, by improving the
optimizer’s ability to apply the proposed optimizations more effectively
(i.e., to make better cost-based decisions) more gains can be made.

On the DBPedia dataset even larger improvements are achieved. The median
improvements in terms of query evaluation time range from significant (1.2x)
to extreme (42.9x) and at its maximum, a 1480-fold improvement is achieved for
the PCC2 template. Again, we note that $\widehat{p}_{o}$ is sometimes
outperformed by $\overline{p}_{o}$ but this effect is milder compared to
STRING. Regarding the ‘gap’ between potential- and actual improvement, we note
a particularly large gap for the PCC3 template in DBPedia. We believe that
this is, at least in part, due to the greater complexity of these templates.
The potential improvement for PCC3 on STRING is much lower than it is on
DBPedia making this less of an issue.

In summary, we observe significant improvements across all templates in query
evaluation performance on DBPedia based on the AC and AT metrics, of up to
three orders of magnitude. We emphasize again that the actual improvements
obtained are minimal and therefore conservative, due to taking the performance
of the best unoptimized plan in practice as a baseline.

Dataset | DBPedia | STRING
---|---|---
Template | PCC2 (#57) | PCC2 (#2) | PCC3 (#13)
Metric | $t(\overline{p}_{o})$ | $t(\widehat{p}_{o})$ | $t(\overline{p}_{o})$ | $t(\widehat{p}_{o})$ | $t(\overline{p}_{o})$ | $t(\widehat{p}_{o})$
Min | 2 | 84 | 69489 | 78798 | 1983 | 2051
| 10 | 5 | 86 | 69489 | 78798 | 11926 | 12890
| 25 | 12 | 99 | 69489 | 78798 | 17637 | 23650
| 50 | 166 | 196 | 69489 | 78798 | 31673 | 72095
| 75 | 1399 | 1534 | 1.2E5 | 1.2E5 | 70377 | 1.2E5
Percentile | 90 | 11368 | 20108 | 1.2E5 | 1.2E5 | 94376 | 1.2E5
Max | 6E5 | 6E5 | 1.2E5 | 1.2E5 | 110333 | 1.2E5
Mean | 4640 | 6331 | 94745 | 99399 | 46865 | 70589

Table 3: Evaluation times for instances where all unoptimized plans timed out.
Optimization yields sub-second evaluation for many DBPedia instances and in-
time evaluation for many STRING instances. Other instances still time out. The
number of instances is denoted (#$n$) (§ 5.3.1,§ 5.3.2).

####  5.3.3 Query evaluation performance in context

Figure 9 plots the distributions of query evaluation times using each system’s
estimated best plan across all mined instances, templates and systems in order
to place AvantGraph’s performance in context. We observe significant speed-ups
of up to several orders of magnitude for most templates across the two
datasets. On the PCC3 template the performance of AvantGrapho lags behind that
of MillenniumDB on both datasets and behind PostgreSQL and DuckDB on STRING
and DBPedia, respectively. Coupled with the observations that the potential
improvement on this template is (much) higher than the actual improvement, as
was observed in Table 1 and Table 2, the primary reason for this appears to be
a lack of quality in the choice of $\widehat{p}_{o}$ (i.e., a lack of quality
in estimation).

##  6 DBPedia use-case Study

To study the potency of seeding interior closures in more detail, we consider
an instance $Q$ of query template PCC2 on DBPedia with $l_{1}$ and $l_{2}$ set
to “associatedMusicalArtist” (AMA) and “after” (AFT), respectively. This
instance asks for pairs of people for whom there exist two different paths
(i.e., paths composed of edges with different labels). Edges labeled AMA
capture loose associations between musicians, whereas edges labeled AFT
capture a generic notion of succession between people, to some position or
role. Hence, this instance asks for those pairs of people that have some
(in)direct musical association and the latter (in)directly succeeded the
former in some capacity. One embedding of this query instance in DBPedia,
including the intermediary ‘hidden’ vertices in each path, is displayed in
Figure 11. This embedding captures the fact that Chad Channing, Dale Crover,
Dan Peters and Dave Grohl are successive drummers for the band Nirvana and
that there exists a sequence of loose musical associations between Chad and
Dave spanning fifteen other musicians.

We exhaustively enumerate the plan spaces $\mathbb{U}_{Q}$ and
$\mathbb{O}_{Q}$ and execute all plans within them. This reveals the actual
best plans $\overline{p}_{u}\in\mathbb{U}_{Q}$ and
$\overline{p}_{o}\in\mathbb{O}_{Q}$. These plans are displayed in Figure 12.
Most edges between operators are annotated with the cardinality of the
corresponding intermediate result. Annotations with solid borders are used for
the edges outgoing from read- and join operators. These cardinalities
contribute to the total number of tuples processed. The other cardinalities
(i.e., without a border) do not contribute.

The cardinality of the seeding query used in $\overline{p}_{o}$ is only 2448,
whereas the cardinalities of sets of edges labelled AMA and AFT are $128\,958$
and $221\,854$. Because both closures in $\overline{p}_{o}$ are computed from
a seed, the intermediate result sizes for the closures drop from hundreds of
millions to millions for the AMA closure and from billions to tens of
thousands for the AFT closure.

The total number of tuples processed is $1\,552\,950\,884$ for
$\overline{p}_{u}$ while it is merely $6\,728\,721$ for $\overline{p}_{o}$.
This results in an evaluation time of $441\,674$ milliseconds (almost 7.5
minutes) for $\overline{p}_{u}$ and $1225$ milliseconds for
$\overline{p}_{o}$.

Figure 11: An embedding of PCC2 in DBPedia (§ 6).

##  7 Related work

Navigational queries are a key class of queries for graph database systems,
and while the problem of optimizing their evaluation has received considerable
attention in recent years, many systems still struggle with the evaluation of
such queries in practice wdbench .

While evaluating navigational queries certainly introduces a set of
challenges, it also introduces several opportunities. One such opportunity is
the concept of seeding, as introduced by Waveguide
DBLP:conf/sigmod/YakovetsGG16 . Waveguide allows for transitive closures to be
computed from a set of vertices that is constrained by other parts of the
query, such as joins or filters, thus potentially reducing the total number of
tuples manipulated in the evaluation of the transitive closure. A drawback of
Waveguide is its representation of query plans as automata, for which it is
practically infeasible to integrate them within the more conventional tree-
based model of query plans in use by the majority of query evaluation engines.

The $\mu$-RA introduced in DBLP:conf/sigmod/JachietGGL20  generalizes some of
Waveguide’s optimization techniques, and applies them to UCRPQs rather than
RPQs. It extends the Relational Algebra (RA) with a fix-point operator $\mu$
that is amendable to having various operations such as (anti-)projection,
filters, joins and even other fix-points pushed down to it. These
transformations are presented algebraically and their application is performed
in an ad-hoc manner, that is not guaranteed to consider all semantically
equivalent query plans induced by the set of transformations.

We improve upon Waveguide specifically by presenting a unified, graph-based
model for query plans that can capture all optimization techniques previously
represented by automata while generalizing the more conventional tree-based
model. We improve upon the $\mu$-RA specifically by addressing the problem of
enumerating query plans using a constructive, rule-based and top-down approach
that offers modularity and extensibility. We improve upon both existing
approaches by introducing novel forms of seeding and by considering RQs rather
than RPQs or UCRPQs.

Finally, our top-down, rule-based approach to query optimization bares some
similarity to more general program optimization techniques such as equality
saturation in frameworks such as Egg eggopt . Because these techniques and
frameworks apply to program optimization in general, rather than query
optimization in particular, there is no assumption of optimal sub-structure
regarding the composition of solutions based only on the optimal solutions to
sub-problems. As a consequence, such approaches are infeasible for the large
search spaces that are typically encountered in query optimization.

##  8 Conclusions

We have presented a comprehensive study of a novel approach to optimization of
navigational graph queries. In addition to strictly subsuming known
optimization techniques, our method introduces a number of novel powerful
optimizations with the goal to effectively enable practical evaluation of
complex navigational queries. We have shown that our approach is able to
significantly (up to several orders of magnitude) outperform state-of-the-art
query evaluation techniques on a wide range of queries on diverse data sets.
We have shown both analytically and empirically that our approach is able to
achieve this performance improvement at a small additional cost of query
optimization time. Future work includes improving cost estimation and
extending our approach to support more expressive navigational query
languages.

Figure 12: Plans $\overline{p}_{u}$ (left) and $\overline{p}_{o}$ (right) for
a PCC2 instance on DBPedia (§ 6)

## References

  * (1) Angles, R., Aranda, C.B., Hogan, A., Rojas, C., Vrgoč, D.: Wdbench: A wikidata graph query benchmark.  In: The Semantic Web – ISWC 2022: 21st International Semantic Web Conference, Virtual Event, October 23–27, 2022, Proceedings, p. 714–731. Springer-Verlag, Berlin, Heidelberg (2022).  DOI 10.1007/978-3-031-19433-7–“˙˝41.  URL https://doi.org/10.1007/978-3-031-19433-7{_}41
  * (2) Arroyuelo, D., Gómez-Brandón, A., Hogan, A., Navarro, G., Rojas-Ledesma, J.: Optimizing rpqs over a compact graph representation.  The VLDB Journal pp. 1–26 (2023)
  * (3) Arroyuelo, D., Hogan, A., Navarro, G., Rojas-Ledesma, J.: Time- and space-efficient regular path queries.  In: 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022, pp. 3091–3105. IEEE (2022).  DOI 10.1109/ICDE53745.2022.00277.  URL https://doi.org/10.1109/ICDE53745.2022.00277
  * (4) Barceló, P., Pérez, J., Reutter, J.L.: Relative expressiveness of nested regular expressions.  In: J. Freire, D. Suciu (eds.) Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27-30, 2012, _CEUR Workshop Proceedings_ , vol. 866, pp. 180–195. CEUR-WS.org (2012).  URL https://ceur-ws.org/Vol-866/paper13.pdf
  * (5) Bonifati, A., Fletcher, G., Voigt, H., Yakovets, N.: Querying Graphs.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers (2018).  DOI 10.2200/S00873ED1V01Y201808DTM051.  URL https://doi.org/10.2200/S00873ED1V01Y201808DTM051
  * (6) Bonifati, A., Martens, W., Timm, T.: An analytical study of large SPARQL query logs.  VLDB J. 29(2-3), 655–679 (2020).  DOI 10.1007/s00778-019-00558-9.  URL https://doi.org/10.1007/s00778-019-00558-9
  * (7) Calvanese, D., Giacomo, G.D., Lenzerini, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse.  In: A.G. Cohn, F. Giunchiglia, B. Selman (eds.) KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000, pp. 176–185. Morgan Kaufmann (2000)
  * (8) Codd, E.F.: A relational model of data for large shared data banks.  Commun. ACM 13(6), 377–387 (1970).  DOI 10.1145/362384.362685.  URL https://doi.org/10.1145/362384.362685
  * (9) CONSORTIUM, S.: String database — statistics (2023).  URL https://string-db.org/cgi/about?footer{_}active{_}subpage=statistics.  Accessed: 13 Oct 2023 16:00
  * (10) DeHaan, D., Tompa, F.W.: Optimal top-down join enumeration.  In: C.Y. Chan, B.C. Ooi, A. Zhou (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007, pp. 785–796. ACM (2007).  DOI 10.1145/1247480.1247567.  URL https://doi.org/10.1145/1247480.1247567
  * (11) Deutsch, A., Xu, Y., Wu, M., Lee, V.E.: Tigergraph: A native MPP graph database.  CoRR abs/1901.08248 (2019).  URL http://arxiv.org/abs/1901.08248
  * (12) Fender, P., Moerkotte, G.: A new, highly efficient, and easy to implement top-down join enumeration algorithm.  In: S. Abiteboul, K. Böhm, C. Koch, K. Tan (eds.) Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, pp. 864–875. IEEE Computer Society (2011).  DOI 10.1109/ICDE.2011.5767901.  URL https://doi.org/10.1109/ICDE.2011.5767901
  * (13) Fender, P., Moerkotte, G.: Reassessing top-down join enumeration.  IEEE Trans. Knowl. Data Eng. 24(10), 1803–1818 (2012).  DOI 10.1109/TKDE.2011.235.  URL https://doi.org/10.1109/TKDE.2011.235
  * (14) Fender, P., Moerkotte, G.: Counter strike: Generic top-down join enumeration for hypergraphs.  Proc. VLDB Endow. 6(14), 1822–1833 (2013).  DOI 10.14778/2556549.2556565.  URL http://www.vldb.org/pvldb/vol6/p1822-fender.pdf
  * (15) Feng, X., Jin, G., Chen, Z., Liu, C., Salihoğlu, S.: Kùzu Database Management System Source Code.  https://github.com/kuzudb/kuzu (2022)
  * (16) Feng, X., Jin, G., Chen, Z., Liu, C., Salihoğlu, S.: Kùzu graph database management system.  In: CIDR (2023)
  * (17) Francis, N., Gheerbrant, A., Guagliardo, P., Libkin, L., Marsault, V., Martens, W., Murlak, F., Peterfreund, L., Rogova, A., Vrgoc, D.: A researcher’s digest of GQL (invited talk).  In: F. Geerts, B. Vandevoort (eds.) 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece, _LIPIcs_ , vol. 255, pp. 1:1–1:22 (2023)
  * (18) Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L.W., Zeng, K., Cong, G., Qin, Y., Pfadler, A., Qian, Z., Zhou, J., Li, J., Cui, B.: Cardinality estimation in dbms: a comprehensive benchmark evaluation.  Proc. VLDB Endow. 15(4), 752–765 (2021).  DOI 10.14778/3503585.3503586.  URL https://doi.org/10.14778/3503585.3503586
  * (19) Hofer, M., Hellmann, S., Dojchinovski, M., Frey, J.: The new dbpedia release cycle: Increasing agility and efficiency in knowledge extraction workflows.  In: E. Blomqvist, P. Groth, V. de Boer, T. Pellegrini, M. Alam, T. Käfer, P. Kieseberg, S. Kirrane, A. Meroño-Peñuela, H.J. Pandit (eds.) Semantic Systems. In the Era of Knowledge Graphs - 16th International Conference on Semantic Systems, SEMANTiCS 2020, Amsterdam, The Netherlands, September 7-10, 2020, Proceedings, _Lecture Notes in Computer Science_ , vol. 12378, pp. 1–18. Springer (2020).  DOI 10.1007/978-3-030-59833-4–“˙˝1.  URL https://doi.org/10.1007/978-3-030-59833-4{_}1
  * (20) Jachiet, L., Genevès, P., Gesbert, N., Layaïda, N.: On the optimization of recursive relational queries: Application to graph queries.  In: D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, H.Q. Ngo (eds.) Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pp. 681–697. ACM (2020).  DOI 10.1145/3318464.3380567.  URL https://doi.org/10.1145/3318464.3380567
  * (21) van Leeuwen, W., Fletcher, G., Yakovets, N.: A general cardinality estimation framework for subgraph matching in property graphs.  IEEE Trans. Knowl. Data Eng. 35(6), 5485–5505 (2023).  DOI 10.1109/TKDE.2022.3161328.  URL https://doi.org/10.1109/TKDE.2022.3161328
  * (22) Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., van Kleef, P., Auer, S., Bizer, C.: Dbpedia - A large-scale, multilingual knowledge base extracted from wikipedia.  Semantic Web 6(2), 167–195 (2015).  DOI 10.3233/SW-140134.  URL https://doi.org/10.3233/SW-140134
  * (23) Leis, V., Radke, B., Gubichev, A., Mirchev, A., Boncz, P.A., Kemper, A., Neumann, T.: Query optimization through the looking glass, and what we found running the join order benchmark.  VLDB J. 27(5), 643–668 (2018).  DOI 10.1007/S00778-017-0480-7.  URL https://doi.org/10.1007/s00778-017-0480-7
  * (24) Moerkotte, G., Neumann, T.: Dynamic programming strikes back.  In: J.T. Wang (ed.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pp. 539–552. ACM (2008).  DOI 10.1145/1376616.1376672.  URL https://doi.org/10.1145/1376616.1376672
  * (25) Neumann, T.: Efficient generation and execution of dag-structured query graphs.  Ph.D. thesis, University of Mannheim, Germany (2005).  URL http://bibserv7.bib.uni-mannheim.de/madoc/volltexte/2005/1089/index.html
  * (26) Neumann, T., Freitag, M.J.: Umbra: A disk-based system with in-memory performance.  In: 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. www.cidrdb.org (2020).  URL http://cidrdb.org/cidr2020/papers/p29-neumann-cidr20.pdf
  * (27) Ono, K., Lohman, G.M.: Measuring the complexity of join enumeration in query optimization.  In: Proceedings of the Sixteenth International Conference on Very Large Databases, p. 314–325. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1990)
  * (28) Raasveldt, M., Muehleisen, H.: DuckDB (2023).  URL https://github.com/duckdb/duckdb
  * (29) Reutter, J.L., Romero, M., Vardi, M.Y.: Regular queries on graph databases.  Theory Comput. Syst. 61(1), 31–83 (2017).  DOI 10.1007/s00224-016-9676-2.  URL https://doi.org/10.1007/s00224-016-9676-2
  * (30) Szklarczyk, D., Kirsch, R., Koutrouli, M., Nastou, K., Mehryary, F., Hachilif, R., Gable, A.L., Fang, T., Doncheva, N., Pyysalo, S., Bork, P., Jensen, L., von Mering, C.: The STRING database in 2023: protein–protein association networks and functional enrichment analyses for any sequenced genome of interest.  Nucleic Acids Research 51(D1), D638–D646 (2022).  DOI 10.1093/nar/gkac1000.  URL https://doi.org/10.1093/nar/gkac1000
  * (31) Willsey, M., Nandi, C., Wang, Y.R., Flatt, O., Tatlock, Z., Panchekha, P.: Egg: Fast and extensible equality saturation.  Proc. ACM Program. Lang. 5(POPL) (2021).  DOI 10.1145/3434304.  URL https://doi.org/10.1145/3434304
  * (32) ten Wolde, D., Singh, T., Szárnyas, G., Boncz, P.A.: Duckpgq: Efficient property graph queries in an analytical RDBMS.  In: 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023. www.cidrdb.org (2023).  URL https://www.cidrdb.org/cidr2023/papers/p66-wolde.pdf
  * (33) Yakovets, N., Godfrey, P., Gryz, J.: Query planning for evaluating SPARQL property paths.  In: F. Özcan, G. Koutrika, S. Madden (eds.) Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pp. 1875–1889. ACM (2016).  DOI 10.1145/2882903.2882944.  URL https://doi.org/10.1145/2882903.2882944
  * (34) Ymous, A.: Optimizing Navigational Queries Online Appendix (2023).  URL https://github.com/ymous5380/ongq