BWT Indexes for Optimal Joins in Graph Databases

A graph database is an edge-labeled graph modeled as a finite set of triples $G\subseteq {𝒰}^3$ where, for simplicity, $𝒰$ will represent a finite and totally ordered set of constants. We will stick to the Resource Description Framework (RDF) model [27], as it is simpler than others and sufficient to present the important concepts. In RDF, each triple $(s,p,o)\in G$ represents the directed edge $s\stackrel{𝑝}{\to }o$, connecting vertex $s$ to vertex $o$, with $p$ being the edge label. The terms subject, predicate, and object are used to refer to $s$, $p$, and $o$, respectively. The number of edges (triples) in $G$ is denoted by $N=|G|$. The alphabet for the vertices of graph $G$ is defined as ${\mathrm{\Sigma }}_V=\{s,o|(s,p,o)\in G\}$, while ${\mathrm{\Sigma }}_L=\{p|(s,p,o)\in G\}$ represents the alphabet for the edge labels. We assume ${\mathrm{\Sigma }}_V\cap {\mathrm{\Sigma }}_L=\mathrm{\varnothing }$, implying that no edge label $p$ is used as a vertex in $G$. The domain of graph $G$ is given by $\mathrm{dom}(G)=\{s,p,o|(s,p,o)\in G\}\subseteq 𝒰$, so we can safely assume $|𝒰|\le 3N$. Figure 1 illustrates a sample graph, which will be used as our running example. The figure also presents a particular enumeration of the constants in $\mathrm{dom}(G)$, as well as the corresponding set of graph triples.

Joins are some of the most resource-intensive operations in relational algebra, making their efficient computation essential for the performance of database systems. A sloppy implementation might end up computing the whole cross product of the involved relations, wasting resources. For a join query $Q$ and a database instance $D$, a join algorithm enumerates $Q(D)$, the solutions for $Q$ over $D$. In order to formalize the study of efficient join algorithms, Atserias et al. [10] introduced the concept of the AGM bound (named after its authors). Consider a natural join query $Q$ on a database instance $D$, which comprises a collection of relations. A natural join can be seen as the subset of the Cartesian product where the values in the common attributes coincide (and only one column per common attribute is preserved). The AGM bound of $Q$ over $D$, denoted $Q^{\ast }$, is the highest possible number of tuples that can result from evaluating $Q$ on any database instance $D^{\prime }$ that includes, for each relation $R$ in $D$, a relation $R^{\prime }$ with the same attributes as $R$ and such that $|R^{\prime }|\le |R|$.

A join algorithm is termed worst-case optimal (wco) if its running time is bounded by $O(Q^{\ast })$, possibly multiplied by polylogs on $N$ (the number of tuples in $D$) and factors independent of $N$ (such as $|Q|$ or the number of attributes in $D$). Although originally conceptualized for relational databases, this idea has also been extended to include graph databases. Even though BGPs are more general than natural joins, it is still possible to apply the AGM bound by considering each triple pattern in a BGP as a relation comprising the triples that match its constants [25].

Next, we outline the Leapfrog Triejoin algorithm [35] (LTJ, for short), which is arguably the most commonly used wco join algorithm in practice. In order to work properly, LTJ requires the graph database to be structured using tries. The idea is to represent each triple (graph edge) storing its components in a trie following a particular order (e.g., in spo order). Indeed, to achieve worst-case optimality, all $3!=6$ possible permutations of the tuples need to be maintained, resulting in the storage of 6 tries (the rationale for this requirement will be explained subsequently). We will call $T_{\mathrm{𝑠𝑝𝑜}}$, $T_{\mathrm{𝑠𝑜𝑝}}$, $T_{\mathrm{𝑝𝑠𝑜}}$, $T_{\mathrm{𝑝𝑜𝑠}}$, $T_{\mathrm{𝑜𝑠𝑝}}$, and $T_{\mathrm{𝑜𝑝𝑠}}$ these tries. Figure 2 shows the 6 tries corresponding to our running-example graph of Figure 1.

Let $Q=\{t_1,\mathrm{\dots },t_q\}$ be a BGP, where $t_i$ is a triple pattern, for $1\le i\le q$. Let $𝐕(Q)=\{x_1,\mathrm{\dots },x_v\}$ be the set of variables of $Q$. The distinctive strategy of LTJ is known as variable elimination. This method involves $v=|𝐕(Q)|$ iterations, each focusing on a single variable from $𝐕(Q)$ to be “eliminated” from the join process. The particular order in which variables are eliminated determines a total order $⟨x_{i_1},\mathrm{\dots },x_{i_v}⟩$ of $𝐕(Q)$, which is called a Variable Elimination Order (VEO, for short). Throughout this process, each triple pattern $t_i$ is treated as a ternary relation that participates in the join. Once a VEO is established for $Q$, each triple pattern $t_i$ will have a particular trie $T_i$ associated with it. The trie $T_i$ should first traverse the constants in $t_i$, and then traverse the variables in $t_i$ in an order that is consistent with that of the VEO. This is why LTJ needs to store 6 tries. To illustrate this, consider the query $Q=\{(x,\mathrm{𝖺𝖽𝗏},y),(z,\mathrm{𝗇𝗈𝗆},x),(z,w,y)\}$, for $x,y,z,w\in 𝐕(Q)$. If the VEO is $⟨x,y,z,w⟩$, then the first triple is associated with trie $T_{\mathrm{𝑝𝑠𝑜}}$, the second with $T_{\mathrm{𝑝𝑜𝑠}}$, and the third one with $T_{\mathrm{𝑜𝑠𝑝}}$. If, instead, the VEO is $⟨z,y,x,w⟩$, then the tries are $T_{\mathrm{𝑝𝑜𝑠}}$, $T_{\mathrm{𝑝𝑠𝑜}}$, $T_{\mathrm{𝑠𝑜𝑝}}$. If some of these 6 tries were not stored, then some VEOs would become unmanageable.

The navigational operations that must be supported at any trie node $v$ of a trie $T$ are:

• $\mathrm{■}$

  $T.\mathrm{𝗋𝗈𝗈𝗍}()$: moves to the root node of trie $T$.

• $\mathrm{■}$

  $T.\mathrm{𝖼𝗁𝗂𝗅𝖽}(v,c)$: descends to the child of node $v$ labeled $c$ in trie $T$.

• $\mathrm{■}$

  $T.\mathrm{𝗅𝖾𝖺𝗉}(v,c_0)$: yields the smallest symbol $c\ge c_0$ that labels a child of node $v$ in trie $T$.

LTJ starts at the root of each $T_i$ and descends by the children that correspond to the constants in triple $t_i$. Next, we proceed to the variable elimination phase, assuming a VEO $⟨x_{i_1},\mathrm{\dots },x_{i_v}⟩$. For $j=1,\mathrm{\dots },v$, let $Q_j\subseteq Q$ be the set of triple patterns that contain variable $x_{i_j}$. Starting with the initial variable $x_{i_1}$ in the VEO, algorithm LTJ first identifies all values $c\in \mathrm{dom}(G)$ such that for every $t\in Q_1$, substituting $x_{i_1}$ with $c$ in $t$ results in a non-empty evaluation of the modified triple pattern $t$ over $G$ (indicating that there are potential solutions to $Q$ where $x_{i_1}$ equals $c$). If the trie $T$ related to $t$ is consistent with the VEO, then its current node’s children precisely represent the suitable values $c$ for $x_{i_1}$.

Throughout the execution, we maintain a mapping $\mu$ with the solutions of $Q$. When a suitable value $c$ is found for $x_{i_1}$, we bind $x_{i_1}$ to $c$, resulting in $\mu =\{(x_{i_1}:=c)\}$, and branch on this particular value $c$. In this branch, we go down by $c$ in all the virtual tries $T$ such that $t\in Q_1$. Next, the same process is applied to $Q_2$, determining suitable values $d$ for $x_{i_2}$, and extending the mapping to $\mu =\{(x_{i_1}:=c),(x_{i_2}:=d)\}$. This process is repeated for the remaining variables in the VEO. Once all variables have been bound in this way, $\mu$ effectively contains a solution for $Q$; this occurs multiple times due to the branching for each binding of $x_{i_1}$, $x_{i_2}$, and so forth. When all bindings $c$ for a variable $x_{i_j}$ have been considered, LTJ backtracks and moves on to the next binding for $Q_{j-1}$. Upon completion of this process, the algorithm has reported all possible solutions for $Q$.

Determining the values $c$, $d$, and so forth, involves finding the intersection among the child nodes of the current nodes across all tries $T_i$, for each $t_i\in Q_j$. The algorithm LTJ carries out this intersection using the primitive $T_i.\mathrm{𝗅𝖾𝖺𝗉}(v,c_0)$ to implement Barbay and Kenyon’s intersection algorithm [11]. Veldhuizen [35] proved that if the $\mathrm{𝗅𝖾𝖺𝗉}$ operation runs within polylogarithmic time, then LTJ is wco regardless of the VEO chosen, provided the tries have an appropriate attribute order.

We next illustrate how LTJ handles the query $Q=\{(x,\mathrm{𝖺𝖽𝗏},y),(z,\mathrm{𝗇𝗈𝗆},x),(z,w,y)\}$ using the VEO $⟨z,y,x,w⟩$. The triple patterns in $Q$ are associated with tries $T_{\mathrm{𝑝𝑜𝑠}}$, $T_{pso}$, and $T_{\mathrm{𝑠𝑜𝑝}}$, respectively. We set $\mu =\mathrm{\varnothing }$ and begin by processing the constants $\mathrm{𝖺𝖽𝗏}$ and $\mathrm{𝗇𝗈𝗆}$, identified as 6 and 7 in our example enumeration, descending to the respective nodes in $T_{\mathrm{𝑝𝑜𝑠}}$ and $T_{\mathrm{𝑝𝑠𝑜}}$. We then handle the variables following the VEO. Starting with $z$ in the second and third triple patterns of $Q$, we intersect the children at the current nodes of both tries (the node corresponding to string 7 in $T_{\mathrm{𝑝𝑠𝑜}}$ and the root of trie $T_{\mathrm{𝑠𝑜𝑝}}$). The only common child is 5, so we descend to those nodes in both tries, setting $\mu =\{(z:=5)\}$. We now proceed to $y$, in the first and third triple patterns. We intersect the children of nodes for string 6 in $T_{\mathrm{𝑝𝑜𝑠}}$ and 5 in $T_{\mathrm{𝑠𝑜𝑝}}$. The first intersection element is 1, leading us to descend in both tries and to update $\mu =\{(z:=5),(y:=1)\}$, and to proceed to $x$ in the first and second triple patterns. We intersect the children of nodes corresponding to string 61 in $T_{\mathrm{𝑝𝑜𝑠}}$ and $75$ in $T_{\mathrm{𝑝𝑠𝑜}}$. Since 4 is a common value, we descend to the appropriate nodes and update $\mu =\{(z:=5),(y:=1),(x:=4)\}$. Lastly, for $w$, present only in the third triple pattern, no intersection is required: all children of the node for string 51 in $T_{\mathrm{𝑠𝑜𝑝}}$ are valid for $w$. The only value is 8, so we set $\mu =\{(z:=5),(y:=1),(x:=4),(w:=8)\}$. Having bound all variables, $\mu$ is a solution to $Q$. According to our enumeration, these values translate to $z:=\mathrm{𝖭𝗈𝖻𝖾𝗅}$, $y:=\mathrm{𝖡𝗈𝗁𝗋}$, $x:=\mathrm{𝖶𝗁𝖾𝖾𝗅𝖾𝗋}$, $w:=\mathrm{𝗐𝗂𝗇}$, resulting in the set of triples $\{(\mathrm{𝖶𝗁𝖾𝖾𝗅𝖾𝗋},\mathrm{𝖺𝖽𝗏},\mathrm{𝖡𝗈𝗁𝗋}),(\mathrm{𝖭𝗈𝖻𝖾𝗅},\mathrm{𝗇𝗈𝗆},\mathrm{𝖶𝗁𝖾𝖾𝗅𝖾𝗋}),(\mathrm{𝖭𝗈𝖻𝖾𝗅},\mathrm{𝗐𝗂𝗇},\mathrm{𝖡𝗈𝗁𝗋})\}$ in the graph. Finally we backtrack, removing $w$ from $\mu$ and returning to variable $x$, and repeat the process until all bindings for the variables of $Q$ are found. In this example, this was the only answer for $Q$.

While LTJ is classically presented as running on tries, we take a more abstract view and consider the database triples $(s,p,o)$ as circular strings [12], where we regard all the strings $spo$, $osp$, and $pos$ as the same. We formalize circular strings using the concept of rotation.

In particular, $\mathring{spo}=\{spo,osp,pos\}$; note that $\mathring{spo}=\mathring{osp}=\mathring{pos}$. Note that, because the alphabet of the predicates is disjoint from that of subjects and objects, the three rotations of Def. 2 must be different in our case (because $p$ is at a different position). Therefore, there is a one-to-one correspondence between triples and c-strings.

The graph database is then seen as a set of c-strings, one per triple, and we identify each trie node $v$ with the set of c-strings corresponding to the triples that descend from $v$. Figure 3 shows the c-strings corresponding to three sample nodes of tries $T_{\mathrm{𝑠𝑝𝑜}}$ and $T_{pos}$.

For what follows, we will create two disjoint copies, ${\mathrm{\Sigma }}_{\text{s}}$ and ${\mathrm{\Sigma }}_{\text{o}}$, of the alphabet ${\mathrm{\Sigma }}_V$, in order to distinguish subjects from objects in c-strings. We will call ${\mathrm{\Sigma }}_{\text{p}}={\mathrm{\Sigma }}_L$ the alphabet of predicates for consistency. Thus, triples will belong to ${\mathrm{\Sigma }}_{\text{s}}\times {\mathrm{\Sigma }}_{\text{p}}\times {\mathrm{\Sigma }}_{\text{o}}$. Further, the three sub-alphabets will form disjoint lexicographic ranges. In our running example, we separate the alphabets by adding $|𝒰|$ to the $p$ components of each triple in the graph, while the $o$ components are increased by $2|𝒰|$. Let us also redefine triple patterns.

Every trie node $v$ then corresponds univocally to a triple pattern $t(v)$, where the edges that lead from the root to $v$ define the bound components of $t(v)$. The node $v$ then represents all the database triples that match $t(v)$. Figure 3 also shows the triple patterns corresponding to three nodes of tries $T_{\mathrm{𝑠𝑝𝑜}}$ and $T_{\mathrm{𝑝𝑜𝑠}}$.

For our purposes, a key property of the characterization as circular strings is the following.

The extended BWT (eBWT) [28, 14] is an extension of the Burrows-Wheeler Transform (BWT) [13] to a set of strings. It builds on the concept of omega-order [28] on strings, which is defined as follows.

Note that, if $S$ and $T$ are not a proper prefix of the other, then coincides with the lexicographic order, but it can differ otherwise.

We are now in position to define the Ring index.

Because of the alphabet separations, it follows that the rotations $X$ of all the c-strings $\mathring{spo}$ have $root(X)=X$ and $exp(X)=1$; therefore the omega-order boils down to the lexicographic order between their $\omega$-extensions. Further, because of our alphabet separation, such order boils down in turn to the plain lexicographic order of the strings. The Ring’s eBWT then lists all the strings of all c-strings $\mathring{spo}$ in the graph, sorts them lexicographically, and collects their last symbols.

Figure 4 (left) shows all the $\mathring{spo}$ strings corresponding to the edges of the graph from Figure 1. Since $|𝒰|=8$ in this case, we sum $8$ to the $p$ component of each triple, and 16 to the $o$ components, and thus ${\mathrm{\Sigma }}_{\text{s}}=[1..8]$, ${\mathrm{\Sigma }}_{\text{p}}=[9..16]$, and ${\mathrm{\Sigma }}_{\text{o}}=[17..24]$. On the right, the triples are lexicographically sorted, obtaining the corresponding Ring index as the last column of the table.

The following theorem shows that we can identify each node $v$ of the three chosen tries with a range of the eBWT of the Ring index.

The following definition will help us discuss how the eBWT works on the graph.

In our case, the order of $spo$ is spo, the order of $pos$ is pos, and the order of $osp$ is osp. Because the three alphabets form lexicographic ranges, eBWT contains a range where all the listed rotations are of order spo, and thus the eBWT contains only symbols of ${\mathrm{\Sigma }}_{\text{o}}$, a second range where all the rotations are of order pos and the eBWT contains only symbols of ${\mathrm{\Sigma }}_{\text{s}}$, and a third range where all the rotations are of order osp and the eBWT contains only symbols of ${\mathrm{\Sigma }}_{\text{p}}$. We store those three segments of the eBWT, respectively, as strings, called columns, $C_{\text{o}}[1..N]$, $C_{\text{s}}[1..N]$, and $C_{\text{p}}[1..N]$ (see the different ranges and colors in the last column in Figure 4), and say that their orders are spo, pos, and osp, respectively.

Let us first show that our representation allows accessing any desired triple $(s,p,o)$ starting from its position in any of the columns $C_{\text{x}}$. For example, to retrieve the triple represented at $C_{\text{o}}[i]$, we know immediately that $o=C_{\text{o}}[i]$. Now, by the classic BWT invariant [13, 16] (which holds true in the eBWT [28, Prop. 10]), we find the entry $C_{\text{p}}[j]$ corresponding to $C_{\text{o}}[i]$ with

where $A_{\text{x}}[c]$ counts the number of times symbols smaller than $c$ occur in $C_{\text{x}}$, and ${\mathrm{𝗋𝖺𝗇𝗄}}_c(X,i)$ counts the number of times $c$ occurs in $X[1..i]$. With $j$ we obtain $p=C_{\text{p}}[j]$, compute the position $k$ of the triple in $C_{\text{s}}$ with

and complete the process with $s=C_{\text{s}}[k]$. The eBWT invariants imply that

that is, we cycle on the string: the eBWT effectively regards the strings as circular and this permits retrieving the triples starting from any of their components.

See Figure 5 for an example of this process. In this case, we have $i=6$, and hence $o=C_{\text{o}}[6]=18$. So, $j=A_{\text{o}}[18]+{\mathrm{𝗋𝖺𝗇𝗄}}_{18}(C_{\text{o}},6)=2+2=4$. Then, $p=C_{\text{p}}[4]=16$, so $k=A_{\text{p}}[16]+{\mathrm{𝗋𝖺𝗇𝗄}}_{16}(C_{\text{p}},4)=4+2=6$. Then, $s=C_{\text{s}}[6]=5$. So, we get back to $i$ since $i=A_{\text{s}}[5]+{\mathrm{𝗋𝖺𝗇𝗄}}_5(C_{\text{s}},6)=3+3=6$. The corresponding $\mathrm{𝑠𝑝𝑜}$ triple is $(5,16,18)$.

The rationale of (say) Eq. (1) is the following. $C_{\text{o}}$ corresponds to the order spo and $C_{\text{p}}$ to the order osp. The second order is obtained from the first by stably reordering the tuples by their o component, in accordance with the lexicographic order. In a stable reordering of spo, position $C_{\text{o}}[i]=o$ will be moved to position $j$ such that (i) all the symbols less than $o$ come before $j$ (and those are counted in $A_{\text{o}}[o]$), and (ii) all the symbols $o$ preceding the one at $C_{\text{o}}[i]$ also come before $j$ (thus we add ${\mathrm{𝗋𝖺𝗇𝗄}}_o(C_{\text{o}},i)$). Figure 5 also shows one of those reorderings, from spo to osp.

Because the shifted symbols are stored in different strings $C_{\text{x}}$, the Ring remaps their alphabets back to ${\mathrm{\Sigma }}_{\text{x}}=[1..|{\mathrm{\Sigma }}_{\text{x}}|]$. The nodes that are both subjects and objects use the same identifier in both ${\mathrm{\Sigma }}_{\text{s}}$ and ${\mathrm{\Sigma }}_{\text{o}}$, in the range $[1..|{\mathrm{\Sigma }}_{\text{s}}\cap {\mathrm{\Sigma }}_{\text{o}}|]$. Also, the Ring stores the arrays $A_{\text{x}}$ using $N+o(N)$ bits, whereas function $\mathrm{𝗋𝖺𝗇𝗄}$ is computed in time $O(\log |𝒰|)$ using a wavelet tree [22] representation of the columns $C_{\text{x}}[1..N]$, just like a typical FM-index implementation [17]. Overall, it represents a graph database of $N$ triples over universe $𝒰$ using $3N\log |𝒰|+o(N\log |𝒰|)$ bits (logarithms are to the base 2), and can retrieve any triple in time $O(\log |𝒰|)$. This is almost the same space needed to store the $3N$ triple identifiers in plain form. What is striking is that, within this space, the Ring can implement all the operations required by the LTJ algorithm, as we see next.

Having separate columns, it is more convenient to identify the root of a trie starting with symbol of alphabet ${\mathrm{\Sigma }}_{\text{x}}$ as the whole range $C_{\text{x}}[1..N]$. This implements operation $\mathrm{𝗋𝗈𝗈𝗍}$ depending on the next triple component we will descend by.

Now assume we are in a range of the eBWT (that is, a range of $C_{\text{s}}$, $C_{\text{p}}$, or $C_{\text{o}}$) that corresponds to a trie node $v$. Recall that this means that the range is that of all the rotations that start with $P(t(v))$. Let us show how to simulate the trie operations $\mathrm{𝖼𝗁𝗂𝗅𝖽}$ and $\mathrm{𝗅𝖾𝖺𝗉}$ on this representation.

This process can be simulated with the Ring without using additional data structures. In this case, it is easier to start assuming that only $o$ is fixed, and derive the other cases analogously, so we use the reversed automaton. Our first step is to descend from the trie root by $o$, $v=\mathrm{𝖼𝗁𝗂𝗅𝖽}(\mathrm{𝗋𝗈𝗈𝗍}(),o)$, which is represented by the range $C_{\text{p}}[i..j]=C_{\text{p}}[A_{\text{o}}[o]+1..A_{\text{o}}[o+1]]$. We now analyze the automaton states to determine the symbols that would lead to active states. For each such symbol $p$, we descend to $u=\mathrm{𝖼𝗁𝗂𝗅𝖽}(v,p)$ using an analogous of Eq. (2), for predicate $p$ instead of for object $o$. The resulting range, $C_{\text{s}}[i^{\prime }..j^{\prime }]$, contains all the distinct sources $s$ that lead to $o$ by symbol $p$. Since there cannot be repetitions in this list, we extract each value of $s$ and iterate from it as the new source node, that is, setting $o\leftarrow s$.

Note that we do not need the Ring component $C_{\text{o}}$ for this simulation. Further, one can avoid duplicating the edges to support reversed symbols if one uses the “non-typical” case technique to handle them. Such a technique [32] was implemented over a bit-parallel simulation of the automaton, and shown to be very competitive in space and time with classic solutions. Further, it was shown that the used Ring components are equivalent to a known succinct representation of labeled graphs [31, Sec. 9.1.4]

An earlier Ring-based implementation [6], instead, does include the reversed edges, and thus it can always use the “typical” case formulas. This enables other optimizations that make the process faster. One possibility is that, instead of trying out the labels $p$ that are relevant for the automaton, one can enumerate the distinct labels $p$ that occur in $C_{\text{p}}[i..j]$, which could be less. The wavelet tree of $C_{\text{p}}$ can do this enumeration in logarithmic time per resulting symbol [21]. Further, the wavelet tree can be enriched with information on the automaton states that are sources of symbols in ranges of ${\mathrm{\Sigma }}_L$. Those can be intersected with the currently active states as we traverse the wavelet tree, so as to prune subtrees that cannot activate any state. This technique computes the intersection between the predicates that lead to active automaton states and those that leave from the current node, in optimal time, that is, proportional to the alternation complexity of both sets [11]. An analogous technique on the wavelet treee of $C_{\text{s}}$ avoids visiting sources of $C_{\text{s}}[i^{\prime }..j^{\prime }]$ that have already been visited with all the currently active states.

Using even more space (but still several times less than classic solutions), one can implement even smarter traversals, in considerably less time [6]. For example, the regular expression can be cut at an edge with a label $p$ that is infrequent in the graph. From each edge $s\stackrel{𝑝}{\to }o$, we launch a backward traversal from $s$ to nodes that activate the initial automaton state, and a forward traversal from $o$ to nodes that activate the final automaton states, and report the Cartesian product of both sets.