text:
\section{Introduction}
\label{sec:intro}
\input{./sections/intro.tex}

\section{Data model}
\label{sec:data}
\input{./sections/data-dv.tex}

\section{Query language}
\label{sec:lang}
\input{./sections/lang.tex}

\section{System architecture}
\label{sec:architecture}
\input{./sections/architecture.tex}

\section{Benchmarking}
\label{sec:benchmark}
\input{./sections/benchmark.tex}

\section{Conclusions and looking ahead}
\label{sec:concl}
\input{./sections/concl.tex}

\begin{acks}
This work was supported by ANID -- Millennium Science Initiative Program -- Code ICN17\_002.
\end{acks}

\bibliographystyle{ACM-Reference-Format}

\newpage

\subsection{Basic graph patterns}

At the core of domain queries are basic graph patterns.\footnote{Basic graph patterns correspond to conjunctive queries (CQs) over graphs.}
A \emph{basic graph pattern} is defined as a pair $(V,\phi)$ such that $\phi : (\mathsf{Obj} \cup \mathsf{Var}) \rightarrow (\mathsf{Obj} \cup \mathsf{Var}) \times (\mathsf{Obj} \cup \mathsf{Var}) \times (\mathsf{Obj} \cup \mathsf{Var})$ is a partial mapping with a finite domain and $V \subseteq \Var{\phi}$, where $\Var{\phi}$ is the set of variables occurring in the domain or in the range of $\phi$. Thus, $\phi$ can be thought as a domain graph that allows a variable in any position, together with a set $V$ of output variables (hence the restriction that each variable in $V$ occurs in $\phi$).

The evaluation of a basic graph pattern returns a set of solution
mappings.  A \textit{solution mapping} (or simply \textit{mapping}) is
a partial function $\mu: \mathsf{Var} \rightarrow \mathsf{Obj}$.
The \emph{domain} of a mapping $\mu$, denoted by $\Dom{\mu}$, is the set of variables on which $\mu$ is defined.
Given $v \in \mathsf{Var}$ and $o \in \mathsf{Obj}$, we use $\mu(v) = o$ to denote that $\mu$ maps variable $v$ to object $o$.
Besides, given a set $V'$ of variables, the term $\mu_{|_{V'}}$ is used to denote the mapping obtained by restricting $\mu$ to $V'$, that is, $\mu_{|_{V'}} :
(\Dom{\mu} \cap V') \to \mathsf{Obj}$ such that $\mu_{|_{V'}}(v) = \mu(v)$ for every $v \in (\Dom{\mu} \cap V')$ (notice that $V'$ is not necessarily a subset of $\Dom{\mu}$).
Finally, for the sake of presentation, we assume that $\mu(o)=o$, for
all $o\in \mathsf{Obj}$.

The evaluation of a basic graph pattern $B = (V,\phi)$ over a property-domain graph
$G=(O,\gamma)$, denoted by $\semp{B}{G}$, is defined as
  $\semp{B}{G} = \{ \mu_{|_V} \mid \mu \in \semp{\phi}{G}\}$,
where:
\begin{eqnarray*}
  \semp{\phi}{G} \ = \ \{ \mu \mid
  \Dom{\mu} = \Var{\phi} \text{ and if } \phi(a) = (a_1,a_2,a_3),
  \text{then } \gamma(\mu(a)) = ( \mu(a_1), \mu(a_2), \mu(a_3)  ) \}.
\end{eqnarray*}
For example, consider the basic graph pattern $(V,\phi)$ where $V = \{ v_2, v_4, v_6\}$ and $\phi$ is given by the assignments:
\begin{verse}
$\phi(v_1) = (v_2, \texttt{position held}, \texttt{President of Chile})$,\\
$\phi(v_3) = (v_1, \texttt{start date}, v_4)$, and\\
$\phi(v_5) = (v_1, \texttt{replaces}, v_6)$.
\end{verse}
In Figure \ref{fig:bgp}, we provide a graphical representation of the above graph pattern, and the solution mappings obtained by evaluating the graph pattern over the property domain graph shown in Figure~\ref{fig:dg}. The solution mappings are presented as a table with columns $v_2$, $v_4$, $v_6$ (i.e. the variables in $V$), and each row represents an individual mapping. In our definitions, different variables may map to the same object in a single solution. Thus, our notion of evaluation follows a homomorphism-based semantics, similar to query languages such as SPARQL~\cite{AnglesABHRV17}.\footnote{Isomorphism-based semantics~\cite{AnglesABHRV17} -- such as Cypher's no-repeated-edge semantics, which disallows the same solution to use the same edge twice -- can be emulated by filtering solutions after they are generated.}

\begin{figure}[tb]
\setlength{\vgap}{1.2cm}
\setlength{\hgap}{4cm}
\centering

\begin{tabular}[t]{ll}
\begin{tabular}{l}
\begin{tikzpicture}

\node[iri,anchor=center,minimum width=7.5cm,minimum height=0.7cm,dashed] (e1) {};

\node[anchor=south east,above left=0.1ex of e1.south east] (e1i) {$v_1$};

\node[iri,right=1ex of e1.west,anchor=west] (sp1) {$v_2$};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp1);

\node[iri,below=\vgap of sp1] (v4) {$v_4$}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,below=\vgap of ch1] (mb) {$v_6$}
  edge[arrin] node[lab,xshift=-1ex] {replaces} (e1);

\end{tikzpicture}
\end{tabular} \hspace{1cm}
&
\begin{tabular}{lllllll}
\toprule
$v_2$ & $v_4$ & $v_6$ \\
\midrule
\texttt{Michelle bachelet} & \texttt{2006-03-11} & \texttt{Ricardo Lagos} \\
\texttt{Michelle bachelet} & \texttt{2018-03-11} & \texttt{Sebastián Piñera}\\
\bottomrule
\end{tabular}
\end{tabular}

\caption{Graphical representation of a basic graph pattern (left), and the tabular representation of the solution mappings (right) obtained by evaluating the basic graph pattern
  over the property domain graph shown in Figure~\ref{fig:dg} \label{fig:bgp}.}
\end{figure}

\subsection{Navigational graph patterns}
A characteristic feature of graph query languages is the ability to match paths of arbitrary length that satisfy certain criteria. We call basic graph patterns enhanced with this feature \textit{navigational graph patterns}, and we define them next.

A popular way to express criteria that paths should match is through regular expressions on their labels, aka.\ \textit{regular path queries} (\textit{rpqs}). More precisely, an \textit{rpq expression} $r$ is defined by the following grammar:
\begin{eqnarray*}
  r & ::= & \varepsilon \ \mid \ o \in \mathsf{Obj} \ \mid \  (r/r) \ \mid \ (r + r) \ \mid \ \inv{r} \ \mid \ r^*.
\end{eqnarray*}
The semantics of an rpq expression $r$ is defined in terms of its
evaluation on a property-domain graph $G$, denoted by $\semp{r}{G}$, which
returns a set of pair of nodes in the graph that are connected by
paths satisfying $r$. More precisely, assuming that $G = (O,\gamma)$,
$o \in \mathsf{Obj}$ and $r,r_1,r_2$ are rpq expressions, we have that:
\begin{eqnarray*}
\semp{\varepsilon}{G} & = & \{(o,o) \mid o\in O\},\\
\semp{o}{G} & = & \{(o_1,o_2) \mid \exists o' \in \mathsf{Obj} : \gamma(o') = (o_1,o,o_2)\},\\
\semp{(r_1 / r_2)}{G} & = & \{ (o_1,o_2) \mid \exists o' \in \mathsf{Obj} : (o_1,o') \in \semp{r_1}{G} \text{ and } (o',o_2) \in \semp{r_2}{G}\}, \\
\semp{(r_1 + r_2)}{G} & = & \semp{r_1}{G}\cup \semp{r_2}{G}, \\
\semp{\inv{r}}{G} & = & \{(o_1,o_2) \mid (o_2,o_1)\in \semp{r}{G}\}.
\end{eqnarray*}
Moreover, assuming that $r^1 = r$ and $r^{n+1} = r/r^n$ for every $n \geq 1$, we have that:
\begin{eqnarray*}
  \semp{r^*}{G} & = & \semp{\varepsilon}{G} \, \cup \, \bigcup_{k \geq 1} \semp{r^k}{G}.
\end{eqnarray*}
Other rpq expressions widely used in practice can be defined by
combining the previous operators.
In particular, $r? = \varepsilon + r$ and $r^+ = r/r^*$.

A \textit{path pattern} is a tuple $(a_1,r,a_2)$ such that $a_1, a_2 \in \mathsf{Obj} \cup \mathsf{Var}$ and $r$ is an rpq expression.
As for the case of basic graph patterns, given a path pattern $p$, we use the term $\Var{p}$ to denote the set of variables occurring in $p$.
Moreover, the evaluation of $p = (a_1,r,a_2)$ over a property-domain graph $G$, denoted by $\semp{p}{G}$, is defined as:
\begin{eqnarray*}
  \semp{p}{G} &=& \{ \mu \mid \Dom{\mu} = \Var{p} \text{ and } (\mu(a_1),\mu(a_2)) \in \semp{r}{G} \}.
\end{eqnarray*}
For example, the expression (\texttt{Michelle Bachelet}, \texttt{(replaced by)}$^+$, $v$) is a path pattern that returns all the Presidents of Chile after Michelle Bachelet.
Given a set $\psi$ of path patterns, $\Var{\psi}$ also denotes the set of variables occurring in $\psi$, and the evaluation of $\psi$ over a property-domain graph $G$ is defined as:
\begin{eqnarray*}
  \semp{\psi}{G} & = & \{ \mu \mid \Dom{\mu} = \Var{\psi} \text{ and } \mu_{|_{\Var{p}}} \in \semp{p}{G} \text{ for each } p \in \psi \}.
\end{eqnarray*}

A \emph{navigational graph pattern} is a triple $(V,\phi,\psi)$ where $(V', \phi)$ is a basic graph pattern for some $V' \subseteq V$, $\psi$ is a set of path patterns, and $V \subseteq \Var{\phi} \cup \Var{\psi}$.
The semantics of a navigational graph pattern $N = (V,\phi,\psi)$ is defined as:
\begin{eqnarray*}
	\semp{N}{G} & = & \{ \mu_{|_V} \mid \Var{\mu} = \Var{\phi} \cup \Var{\psi}, \mu_{|_{\Var{\phi}}} \in \semp{\phi}{G} \ \text{ and } \
	\mu_{|_{\Var{\psi}}} \in \semp{\psi}{G} \}.
\end{eqnarray*}

Hence, the result of a navigational graph pattern $N = (V,\phi,\psi)$ is a set of mappings $\mu$ projected onto the set $V$ of output variables, where $\mu$ satisfies the structural restrictions imposed by $\phi$ and the path constrainst imposed by $\psi$.
Notice that multiple rpq expressions can link the same pair of nodes. This is similar to the existential semantics of path queries, as specified in the SPARQL standard \cite{HarrisS13}.

Given a domain graph $G=(O,\gamma)$, we define paths over the directed labeled graph that forms the range of $\gamma$; in other words, we do not allow for matching paths that emanate from an edge object. Such a feature could be considered in the future. We may also consider adding semantics for shortest paths, additional criteria on node or edges in the path, etc.

\subsection{Relational graph patterns}
As previously discussed (and seen in the example of Figure~\ref{fig:bgp}), graph patterns return relations (tables) as solutions. Thus we can -- and many practical graph query languages do -- use a relational-style algebra to transform and/or combine one or more sets of solution mappings into a final result.

Towards defining this algebra, we need the following terminology.
Two mappings $\mu_1$ and $\mu_2$ are \emph{compatible}, denoted by $\mu_1 \sim \mu_2$, if $\mu_1(v) = \mu_2(v)$ for all variables $v$ which are in both $\Dom{\mu_1}$ and $\Dom{\mu_2}$. If $\mu_1 \sim \mu_2$, then we write $\mu_1 \cup \mu_2$ for the mapping obtained  by extending $\mu_1$ according to $\mu_2$ on all the variables in $\Dom{\mu_2}\setminus\Dom{\mu_1}$.
Given two sets of mappings $\Omega_1$ and $\Omega_2$, the \emph{join}
and \emph{left outer join} between $\Omega_1$ and $\Omega_2$ are defined respectively as follows:
\begin{eqnarray*}
\Omega_1 \Join \Omega_2  &=& \{ \mu_1 \cup \mu_2 \mid \mu_1 \in \Omega_1,\, \mu_2 \in \Omega_2 \text{ and } \mu_1 \sim \mu_2 \},\\
\Omega_1 \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \Omega_2  &=& (\Omega_1 \Join \Omega_2) \cup (\Omega_1 \setminus \Omega_2).
\end{eqnarray*}
With this terminology, a \textit{relational graph pattern} is recursively defined as follows:
\begin{itemize}
\item If $N$ is a navigational graph pattern, then $N$ is also relational graph pattern;
\item If $R_1$ and $R_2$ are relational graph patterns, then $(R_1 ~\operatorname{AND}~ R_2)$ and $(R_1 ~\operatorname{OPT}~ R_2)$ are relational graph patterns.
\end{itemize}
The evaluation of a relational graph pattern $R$ over a property-domain graph $G$, denoted by $\semp{R}{G}$, is recursively defined as follows:
\begin{itemize}
\item if $R$ is a navigational graph pattern $N$, then $\semp{R}{G} = \semp{N}{G}$;
\item if $R$ is $(R_1 ~\operatorname{AND}~ R_2)$ then $\semp{R}{G} = \semp{R_1}{G} \Join \semp{R_2}{G}$;
\item if $R$ is  $(R_1 ~\operatorname{OPT}~ R_2)$ then $\semp{R}{G} = \semp{R_1}{G} \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \semp{R_2}{G}$.
\end{itemize}

\subsection{Selection conditions}
In addition to match a graph pattern against a property-domain graph, we would like to filter the solutions by imposing selection conditions over the resulting objects (i.e. nodes and edges).
More precisely, a \emph{selection condition} is defined recursively as follows:
(a) if $v_1, v_2 \in \mathsf{Var}$ and $o \in \mathsf{Obj}$, $k_1, k_2 \in \mathcal{K}$, $v \in \mathcal{V}$ then $(v_1 = v_2)$, $(v_1 = o)$, $v_1.k_1 = v_2.k_2$ and $v_1.k_1 = v$ are selection conditions; and (b) if $C_1, C_2$ are selection conditions, then $(\neg\ C_1)$, $(C_1 \land C_2)$, $(C_1
\lor C_2)$ are selection conditions.

Given a property-domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, a mapping $\mu$, and a selection condition $C$, we say that $\mu$ satisfies $C$ under $G$, denoted by $\mu \models_G C$, if one of the following statements holds:
\begin{itemize}
\item
$C$ is $({v_1} = {v_2})$, $v_1, v_2 \in \Dom{\mu}$ and $\mu(v_1) = \mu(v_2)$;

\item
$C$ is $({v_1} = o_1)$, $v_1 \in \Dom{\mu}$ and $\mu(v_1) = o_1$;

\item
$C$ is $({v_1.k_1} = {v_2.k_2})$, $v_1, v_2 \in \Dom{\mu}$,
$\texttt{prop}(\mu(v_1),k_1) = \texttt{prop}(\mu(v_2),k_2)$;

\item
$C$ is $({v_1.k_1} = {v})$, $v_1 \in \Dom{\mu}$ and $\texttt{prop}(\mu(v_1),k_1) = v$;

\item
$C$ is $(\neg C_1)$, and it is not the case that $\mu \models_G C_1$;

\item
$C$ is $(C_1 \land C_2)$, $\mu \models_G C_1$, and $\mu \models_G C_2$;

\item
$C$ is $(C_1 \lor C_2)$ and either $\mu \models_G C_1$, $\mu \models_G C_2$, or both.
\end{itemize}

\subsection{Solution modifiers}
We consider an initial set of solution modifiers that allow for applying a final transformation on the solutions generated by a graph pattern.
These include:
\textsf{selection}, which defines a set of elements (variables and properties) to be returned;
\textsf{order by}, which orders the solutions according to a sort criteria; and
\textsf{limit}, which returns the first $n$ mappings in a sequence of solutions.

Let $\mathbf{S}$ be the set of strings, $v \in var$ and $k \in \mathcal{K}$.
A \emph{selection mapping} is a function $\tau : \mathbf{S} \to \mathsf{Obj} \cup \mathcal{V}$.
A \emph{selection element} is either a variable $v$ or an expression $v.k$.
Assume that there is a simple way to transform a selection element into a string in $\mathbf{S}$.
Given a sequence of selection mappings $S$ and an integer $n$, the function $\texttt{limit}(S,n)$ returns the first $n$ elements of $S$ when $n > 0$, and returns $S$ otherwise.

Given a property-domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, a mapping $\mu$, and a sequence of selection elements $E$, the function $\texttt{sel}(\mu,E)_G$ returns a selection mapping $\tau$ defined as follows:
if $v \in E$ then $``v" \in \text{dom}(\tau)$ and $\tau(``v") = \mu(v)$;
if $v.k \in E$ then $``v.k" \in \text{dom}(\tau)$ and $\tau(``v.k") = \texttt{prop}(\mu(v),k)$.
Moreover, given a set of solution mappings $\Omega$, the function $\texttt{select}$ returns a set of selection mappings defined as
$\texttt{select}(\Omega,E)_G = \{ \texttt{sel}(\mu,E)_G \mid \mu \in \Omega \}$.

An \emph{order modifier} is a tuple $(e,\beta)$ where $e$ is a selection element and $\beta$ is either \texttt{asc} or \texttt{desc}.
Given a sequence of selection mappings $S$ and an order modifier $o = (e,\beta)$, we say that $S$ satisfies $o$, denoted $S \models o$, if it applies that:
(i) $\beta$ is \texttt{asc} and $S$ satisfies an ascending order with respect to $e$;
or (ii) $\beta$ is \texttt{desc} and $S$ satisfies a descending order with respect to $e$.
Moreover, given a sequence of order modifiers $O = (o_1, \dots, o_n)$, we say that $S$ satisfies $O$, denoted $S \models O$, if it applies that:
(i)  $S \models o_1$ when $n = 1$; or
(ii) $S \models o_1$ and, for every sub-sequence of selection mappings $S' \subseteq S$ it applies that $S' \models (o_2, \dots, o_n)$ such that $\tau_i(e_1) = \tau_j(e_1)$ for any pair of selection mappings $\tau_i, \tau_j \in S'$, with $o_1 = (e_1,\beta_1)$.

\subsection{Graph Queries}
A \textit{graph query} $Q$ is defined as a tuple ($R$, $C$, $E$, $O$, $n$), where $R$ is a relational graph pattern, $C$ is a selection condition, $E$ is a sequence of selection elements, $O = \{ o_1, \dots, o_n \}$ is a sequence of order modifiers, and $n$ is a positive integer. We assume that $R$ is the unique mandatory component.
Given a variable $v \in \text{dom}(R)$, the rest of components have the following expressions by default: $C$ is $v = v$, $E$ is $v$, $O$ is $(v,\texttt{asc})$ and $n = 0$.

The evaluation of $Q$ over $G$ is defined as $\texttt{limit}(S,n)$ where
$S = \texttt{Select}(\Omega,E)_G$,  $S \models O$, and
$\Omega = \{ \mu_{|_V} \mid \mu \in \semp{R}{G} \land \mu \models^G C \}$.
We will assume that every graph query $Q$ = ($R$, $C$, $E$, $O$, $n$) satisfies the following two conditions:
(i)  For every sub-pattern $R' = (R_1 ~\operatorname{OPT}~ R_2)$ of $R$ and for every variable $v$ occurring in $R$, it applies that, if $v$ occurs both inside $R_2$ and outside $R'$, then it also occurs in $R_1$;
(ii) It applies that $\var(C) \subseteq \var(R)$.
Then, we say that $Q$ is a \emph{well-designed graph query}.

We finish this section noting that the semantics of a declarative query expression:

\begin{dql}
	SELECT E
	MATCH  R
	WHERE  C
	ORDER BY O
	LIMIT n
\end{dql}

\noindent is defined as the outputs of the graph query
($R$, $C$, $E$, $O$, $n$).

\begin{comment}

\subsection{Concrete syntax}

The language supported by MillenniumDB borrows syntax from popular graph query languages SPARQL \cite{HarrisS13} and Cypher \cite{FrancisGGLLMPRS18}. The following is an example of a query in MillenniumDB which finds all people that a person named John knows, and additionally, the city where these people live, if this information is known:

\begin{lstlisting}
SELECT ?y, ?z
MATCH (?x :Person)-[:knows]->(?y :Person)
	OPTIONAL {(?y)-[:livesIn]->(?z :City)}
WHERE ?x.name == "John"
\end{lstlisting}

Intuitively, the \texttt{SELECT} clause specifies which of the matched variables will be returned (\textit{projection}), while the \texttt{MATCH} clause specifies the basic or navigational graph pattern which we will look for in our graph. We can transform or combine the results of one or more \texttt{MATCH} clauses using relational operators to generate a complex graph pattern. In the example, the \texttt{OPTIONAL} pattern invokes a left-outer-join that extends the obtained result with the name of the city only if this information is known (and assigns no value to \texttt{?z} otherwise). Note that \texttt{OPTIONAL} can be interpreted as \texttt{OPTIONAL MATCH}, i.e., it is a binary operator that combines the results of two basic or navigational graph patterns. Finally, the \texttt{WHERE} clause is used to filter result based on a selection, usually by restricting the values of some of the attributes of a matched object.

\begin{figure}
\begin{center}
\begin{lstlisting}
SELECT SelOptions
MATCH  MatchPattern
WHERE  Condition
\end{lstlisting}
\end{center}
\caption{Shape of a query in MillenniumDB}
\label{fig-shape}
\end{figure}

\begin{figure*}
\begin{center}
\fbox{Query elements}
\end{center}
\begin{align*}
\texttt{SelOptions} & :- \ \textcolor{blue}{\texttt{*}} \ | \ v \ | \ v\textcolor{blue}{\textbf{.}}k \ \quad , \quad v\in \mathsf{Var}, k \in \mathcal{K}\\
\texttt{MatchPattern} & :- \ \texttt{GraphPattern}\ |\   \textcolor{red}{\texttt{(}}\ \texttt{MatchPattern}\ \textcolor{red}{\texttt{)}} \ \textcolor{blue}{\texttt{OPTIONAL}} \ \textcolor{blue}{\texttt{\{}} \ \texttt{MatchPattern} \ \textcolor{blue}{\texttt{\}}}\\
\texttt{GraphPattern} & :- \ \texttt{GraphElement} \ | \  \texttt{GraphElement} \textcolor{blue}{\texttt{\textbf{,}}} \  \textcolor{red}{\texttt{(}} \ \texttt{GraphPattern} \ \textcolor{red}{\texttt{)}}\\
\texttt{GraphElement} & :- \ \texttt{NodePattern} \ |\ \texttt{EdgePattern} \ |\ \texttt{PropertyPath} \\
\texttt{Condition} & :- \ \texttt{Comparison} \ | \ \textcolor{blue}{\texttt{(}}\texttt{Condition \textcolor{blue}{AND} Condition}\textcolor{blue}{\texttt{)}} \ | \  \textcolor{blue}{\texttt{(}}\texttt{Condition \textcolor{blue}{OR} Condition}\textcolor{blue}{\texttt{)}}\\
\texttt{Comparison} & :- \ v\textcolor{blue}{\textbf{.}}k \sim val \ | \ v\textcolor{blue}{\textbf{.}}k \sim v'\textcolor{blue}{\textbf{.}}k' \quad , \quad v, v'\in \mathsf{Var}, k, k'\in \mathcal{K}, val \in \mathcal{V}, \sim \in \{\textcolor{blue}{\texttt{==,<=,>=,<,>}}\}
\end{align*}

\begin{center}
\fbox{Nodes, edges and property paths}
\end{center}
\begin{align*}
\texttt{NodePattern} & :- \ \textcolor{blue}{\texttt{(}} \ \texttt{Node}? \ \texttt{Labels}? \ \texttt{Properties}? \ \textcolor{blue}{\texttt{)}}\\
\texttt{Node} & :- \ v \in \mathsf{Var} \ | \ o\in \mathsf{Obj}\\
\texttt{Labels} & :- \ \textcolor{blue}{\textbf{:}}l \ | \ \textcolor{blue}{\textbf{:}}l \ \texttt{Labels} \quad , \quad l\in \mathcal{L}\\
\texttt{Properties} & :- \ \textcolor{blue}{\texttt{\{}} \ \texttt{PropertyList} \ \textcolor{blue}{\texttt{\}}}\\
\texttt{PropertyList} & :- \ k\textcolor{blue}{\textbf{:}}val \ | \ k\textcolor{blue}{\textbf{:}}val\textcolor{blue}{\textbf{,}}\ \texttt{PropertyList}  \quad , \quad k\in \mathcal{K}, val\in \mathcal{V}\\
 & \\
 \texttt{EdgePattern} & :- \ \texttt{NodePattern} \ \texttt{\textcolor{blue}{-}} \texttt{Edge}? \texttt{\textcolor{blue}{>}} \ \texttt{NodePattern} \ |\            \texttt{NodePattern} \ \texttt{\textcolor{blue}{<-}} \texttt{Edge}? \texttt{\textcolor{blue}{}} \ \texttt{NodePattern} \\
\texttt{Edge} & :- \ \texttt{\textcolor{blue}{[}} \ v? \ \texttt{Type}? \ \texttt{Properties}? \ \texttt{\textcolor{blue}{]-}} \quad , \quad v\in \mathsf{Var} \\
 \texttt{Type} & :-\ \textcolor{blue}{\textbf{:}}o \ | \ \textcolor{blue}{\texttt{=TYPE(}}v\textcolor{blue}{\texttt{)}} \quad , \quad o\in \mathsf{Obj}, \ v\in \mathsf{Var}\\
 & \\
 \texttt{PropertyPath} & :- \ \texttt{NodePattern} \ \textcolor{blue}{\texttt{=[}} \ \texttt{pathExp} \ \textcolor{blue}{\texttt{]=>}} \ \texttt{NodePattern} \ |\  \texttt{NodePattern} \ \textcolor{blue}{\texttt{<=}} \textcolor{blue}{[} \ \texttt{pathExp} \ \textcolor{blue}{\texttt{]=}} \ \texttt{NodePattern}\\
 \texttt{pathExp} & :- \ \texttt{\textcolor{blue}{\textbf{:}}}o  \ |\ \textcolor{blue}{\hat{ }} \ \texttt{pathExp} \ |\  \textcolor{blue}{\texttt{(}}\texttt{pathExp\textcolor{blue}{\textbf{/}}pathExp}\textcolor{blue}{\texttt{)}} \ |\ \texttt{pathExp}^{\textcolor{blue}{\texttt{*}}} \ |\\
 & \quad \quad \texttt{pathExp}^{\textcolor{blue}{\texttt{+}}} \ | \  \texttt{pathExp\textcolor{blue}{\{}n\textcolor{blue}{\textbf{,}}m\textcolor{blue}{\}}} \ |\ \textcolor{blue}{\texttt{(}}\texttt{pathExp \textcolor{blue}{|} pathExp}\textcolor{blue}{\texttt{)}} \ |\ \texttt{pathExp}\textcolor{blue}{\texttt{?}} \quad , \quad o\in \mathsf{Obj}, \texttt{n,m}\in \mathbf{N}, \texttt{n}\leq \texttt{m}
\end{align*}
\caption{Specification of query patterns in MilleniumDB. Blue symbols are taken literally. Red brackets in \texttt{MatchPattern} and \texttt{GraphPattern} are grouping specification for unambiguous parsing, and are not specified when writing the query.}
\label{fig-syntax}
\end{figure*}

The general structure of a query in MillenniumDB is defined in Figure \ref{fig-shape}. The syntax of different patters that appear in a query is defined in Figure \ref{fig-syntax}. The workhorse of a query in MillenniumDB is specified in the \texttt{MatchPattern}, which specifies a pattern that needs to be present in our graph. The \texttt{Condition} from the \texttt{WHERE} clause is then applied as a filter to the selected results, and \texttt{SelOptions} specify which data is to be projected out as the final result. To illustrate the use of these components consider following query:

\begin{lstlisting}
SELECT *
MATCH (?x :Person), (?y)-[:knows]->(?z), (?y)=[:follows*]=>(?w)
	OPTIONAL {(?x)-[:knows]->(?w)}
		OPTIONAL {(?x)-[:follows]->(?w)}
WHERE ?x.name == ?y.name
\end{lstlisting}

As specified by Figure \ref{fig-syntax}, the \texttt{MatchPattern} consists of a single \texttt{GraphPattern}, followed by a series of \texttt{OPTIONAL} patterns. The \texttt{GraphPattern} is a series of \texttt{GraphElements} which match a specific node, edge, or a path between nodes, separated by a comma. In the example above, the pattern \texttt{(?x :Person)} is saying that
 we want to match a node with the label \texttt{Person}, and store the result in the variable \texttt{?x}. Similarly, \texttt{(?y)-[:knows]->(?z)} matches an edge between a node stored in the variable \texttt{?y} and a node stored in the variable \texttt{?z}, that has a type \texttt{knows}. Lastly, the pattern \texttt{(?y)=[:follows*]=>(?w)} looks for a pair of nodes, stored in \texttt{?y} and \texttt{?w}, respectively, connected by a path of arbitrary length, where each edge has the type \texttt{follows}. Intuitively, the result of a \texttt{GraphPattern} can be thought as obtained by joining the results of each of its constituent \texttt{GraphElements}.

 Following a \texttt{GraphPattern}, we have a series of \texttt{OPTIONAL} statements. Each of these can again specify a new \{\ \texttt{MatchPattern}\ \}, placed inside braces, and can thus include nested \texttt{OPTIONAL} statements. Several consecutive \texttt{OPTIONAL} statements are parsed as being grouped to the left. We signal this in Figure \ref{fig-syntax} by placing the \texttt{MatchPattern} to the left of an optional into red braces. Similarly, in order to parse them unambiguously, \texttt{GraphPatterns} can be thought as being grouped to the right. That is, the \texttt{MatchPattern} above is grouped as follows:

\begin{lstlisting}
( ( (?x :Person), (?y)-[:knows]->(?z), (?y)=[:follows*]=>(?w) )
	OPTIONAL { (?x)-[:knows]->(?w) } )
		OPTIONAL { (?x)-[:follows]->(?w) }
\end{lstlisting}

The semantics of a query $q$ over a property-domain graph $G$ is defined in terms of mappings, analogously to SPARQL \cite{PerezAG09}, or to homomorphism based semantics of property graphs \cite{AnglesABHRV17}. A \textit{mapping} is a partial function $\mu: \mathsf{Var} \mapsto \mathsf{Obj}$. The \emph{domain} $\Dom{\mu}$ of a mapping $\mu$
is the set of variables on which $\mu$ is defined. Additionally, we will assume that $\mu(o)=o$, for all $o\in \mathsf{Obj}$. We begin by defining the semantics of mappings over each atomic block of a query, that is over a \texttt{NodePattern, EdgePattern} and \texttt{PropertyPath}. Before doing this, notice that each \texttt{NodePattern} can have an explicit identifier (e.g. in \texttt{(Q320 :Person)}), or a variable (e.g. in \texttt{(?x :Person)}), and each \texttt{Edge} can have a variable (e.g. in \texttt{(?x)-[?e :knows]->(?y)}). When these are not present, they are assumed to be existentially quantified; namely, when we write \texttt{(Q320)-[:knows]->()}, we are simply trying to count all the nodes that \texttt{Q320} can reach via an edge of the type \texttt{knows}, and these are ``virtually" assigned to an ``invisible" variable \texttt{?y} inside the empty node pattern\texttt{()}.

When defining the set of variables used in a query $q$, without loss of generality, we will assume that all \texttt{NodePattern} or \texttt{Edge} elements which do not have either an explicit identifier, nor a variable, are assigned a unique fresh variable not used elsewhere in $q$. We call such variables \textit{anonymous variables} of $q$, and denote them $\avar{q}$. All the \textit{explicit variables} of a query $q$, that is, the ones appearing in the definition of $q$, are denoted by $\evar{q}$. The set of variables of $q$, denoted $\qvars{q}$ equals the union $\avar{q} \cup \evar{q}$. We can now define the semantics of  a query $q$ over a property domain-graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, denoted $\semp{q}{G}$, inductively as the set of all mappings $\mu:\qvars{q}\mapsto \mathsf{Obj}$.

Basically, we do this in the next section in a bit more general setting (optional patterns are more general there).

\riveros{Can we query the domain graph, namely, the `keys' in the function? Also I would write some queries using the running example of Section 2.}

\end{comment}

\subsection{Basic Graph Patterns}
\label{ss-bgps}
We focus first on basic graph pattern queries. To test different query execution strategies of MillenniumDB, we use two benchmarks: \emph{Troublesome BGPs} and \emph{Complex BGPs}, which are described next.

\paragraph*{Troublesome BGPs} The Wikidata SPARQL query log contains millions of queries~\cite{MalyshevKGGB18}, but many of them are trivial to evaluate. We thus decided to generate our benchmark from more challenging cases, i.e., a smaller log of queries that timed-out on the Wikidata public endpoint~\cite{MalyshevKGGB18}. From these queries we extracted their BGPs, removing duplicates (modulo isomorphism on query variables). We further removed queries that give zero results over \textit{Wikidata Truthy}. We distinguish queries consisting of a single triple pattern (\emph{Single}) from those containing more than one triple pattern (\emph{Multiple}). The former set tests the triple matching capabilities of the systems, whereas queries in the latter set test join performance.
\textit{Single} contains 399 queries, whereas \textit{Multiple} has 436 queries.

Table~\ref{tab:queries1} (top and middle) summarizes the query times on this set, whereas Figure~\ref{fig:bgp-queries1} (left and middle) shows boxplots with more detailed statistics on the distributions of runtimes.

\begin{table}
\caption{Summary of query times, in seconds, for BGPs. Average and median are for all the queries, including timeouts. \label{tab:queries1}}
\footnotesize%
\setlength{\tabcolsep}{3.2pt}%
\begin{tabular}{crrrrrrr}
\toprule
\multicolumn{8}{c}{\textit{Single}} \\
\midrule
		  & MillDB LF & MillDB NL & BlazeG & Jena & Jena LF & Virtuoso & Neo4J \\
\midrule
Supported         & 399  & 399  & 399  & 399   & 395   & 399   & 394\\
Error             & 0    & 0    & 0    & 0     & 4     & 0     & 5\\
Timeouts          & 0    & 0    & 0    & 0     & 0     & 0     & 0\\
Average           & 0.07 & 0.07 & 2.21 & 14.10 & 10.08 & 2.22  & 28.00\\
Median            & 0.05 & 0.05 & 0.09 & 0.34  & 0.44  & 0.32  & 1.33\\
\midrule
\end{tabular}

\vspace{2mm}

\begin{tabular}{crrrrrrr}
\toprule
\multicolumn{8}{c}{\textit{Multiple}} \\
\midrule
		  & MillDB LF & MillDB NL & BlazeG & Jena & Jena LF & Virtuoso & Neo4J\\
\midrule
Supported         & 436   & 436   & 436   & 426   & 418   & 436   & 405 \\
Error             & 0     & 0     & 0     & 10    & 18    & 0     & 31\\
Timeouts          & 0     & 1     & 3     & 0     & 0     & 0     & 0\\
Average           & 4.77 & 11.01 & 31.79 & 35.43 & 16.78 & 7.87  & 75.55\\
Median            & 0.27  & 0.30  & 2.42  & 4.90  & 3.39  & 5.11  & 6.84\\
\hline
\end{tabular}
\vspace{2mm}

\begin{tabular}{lrrrrrrr}
\toprule
\multicolumn{8}{c}{\textit{Complex}} \\
\midrule
		  & MillDB LF & MillDB NL & BlazeG & Jena & Jena LF & Virtuoso & Neo4J\\
\midrule
Supported         & 850   & 850   & 850   & 850   & 850   & 850   & 850 \\
Error             & 0     & 0     & 0     & 2    & 0    & 0     & 10\\
Timeouts          & 0     & 1     & 2     & 0     & 0     & 0     & 0\\
Average           & 0.37 & 3.36 & 4.63 & 3.37 & 0.88 & 1  & 17.92\\
Median            & 0.1  & 0.17  & 0.34  & 0.16  & 0.14  & 0.19  & 0.66\\
\midrule
\end{tabular}
\end{table}
MillenniumDB sharply outperforms the alternatives on the \textit{Single} queries.
The next best performers on average, Blazegraph
and Virtuoso, are more than 30 times slower for average runtimes. In terms of medians, Blazegraph comes closest, but is still almost twice as slow as
MillenniumDB. It is also much less stable: the third quartile of Blazegraph is
an order of magnitude higher than the most costly queries in MillenniumDB.%
\footnote{Excluding the outliers, which are not included between whiskers.} The
other systems tested are slower on \textit{Single}, with their averages being two orders of magnitude
higher than those of MillenniumDB and their medians being higher than all of the
times shown for MillenniumDB.

MillenniumDB also outperforms the other systems on queries of the \textit{Multiple} set. Its medians are an
order of magnitude faster than those of Blazegraph, the next best contender.
Indeed, the median of Blazegraph is an order of magnitude higher than all the
queries in MillenniumDB (excluding outliers). Even the first quartile of
Blazegraph is close to the most costly queries in MillDB LF. The difference is
less sharp for averages, but still MillDB LF takes 60\% of the time of Virtuoso,
the next best contender. The comparison between both query strategies of
MillenniumDB shows that, though both medians are close, the worst-case-optimal
MillDB LF offers more stable times than the nested-loop strategy of MillDB NL.

\begin{figure}[t]
\centering
\hbox{
\includegraphics[width=0.339\columnwidth]{plots/BGP-Single.pdf}
\includegraphics[width=0.320875\columnwidth]{plots/BGP-Multiple.pdf}
\includegraphics[width=0.339\columnwidth]{plots/BGP-Synthetic.pdf}
}

    \vspace{0.3cm}
    \begin{tikzpicture}
       \begin{customlegend}[legend columns=4,legend style={draw=none,column sep=1ex, font=\footnotesize, cells={anchor=west}, at={(0.5,-0.15)},
      anchor=north, /tikz/every even column/.append style={column sep=0.4cm}},legend entries={\small\textsf{MillDB LF}, \small\textsf{MillDB NL}, \small\textsf{Blazegraph}, \small\textsf{Jena}, \small\textsf{Jena LF}, \small\textsf{Virtuoso}, \small\textsf{Neo4J}}]
          \pgfplots@addlegendimage{black,fill=red, ybar stacked}
          \pgfplots@addlegendimage{black,fill=olive, ybar stacked}
          \pgfplots@addlegendimage{black,fill=brown,ybar stacked}
          \pgfplots@addlegendimage{black,fill=blue,ybar stacked}
          \pgfplots@addlegendimage{black,fill=blue!30,ybar stacked}
          \pgfplots@addlegendimage{black,fill=red!20,ybar stacked}
	  \pgfplots@addlegendimage{black,fill=yellow,ybar stacked}
       \end{customlegend}
    \end{tikzpicture}
\caption{Boxplots for the query time distribution on the set of troublesome Single BPG queries (left), troublesome Multiple BPG queries (middle), and Complex BGP queries (right).}
\label{fig:bgp-queries1}
\end{figure}

\paragraph{Complex BGPs.}
This is a benchmark used to test the performance of worst-case optimal joins~\cite{HoganRRS19}. Here, 17 different complex join patterns were selected, and 50 different queries generated for each pattern, resulting in a total of 850 queries. Figure~\ref{fig:bgp-queries1} (right), and Table~\ref{tab:queries1} (bottom), show the resulting query times. In this case, the difference between the two evaluation strategies of MillenniumDB is more clear. The worst-case-optimal version (MillDB LF) is not only considerably more stable than the nested-loop version (MillDB NL), but also twice as fast in the median. After MillDB LF, the next-best competitor is Jena LF, showing the benefits of worse-case optimal joins. Virtuoso follows not far behind, while MillDB NL, Jena, Blazegraph and Neo4j are considerably slower. Overall, MillDB LF offers the
best performance for every statistic shown in the plot.

\subsection{Property Paths}
\label{ss-paths}

To test the performance of path queries, we extracted 2RPQ expressions from a log of queries that timed out on the Wikidata endpoint~\cite{MalyshevKGGB18}.
The original log has 2110 queries. After removing queries that yield no results (due to missing data), we ended up with 1683 queries. These were run in succession, each restricted to return at most 100{,}000 results.
Each system was started after cleaning the system cache, and with a timeout of 10 minutes. Since these are originally SPARQL queries, not all of them were supported by Neo4J given the restricted regular-expression syntax it supports. We remark that MillenniumDB and Neo4J were the only systems able to handle timeouts without being restarted.\footnote{In fact, MillenniumDB did not give any timeouts. However, we re-ran the experiments with a lower timeout, and observed that the system could recover from interrupting the query gracefully and was able to return the results found before being interrupted.} In this comparison we did not include MillDB NL, nor Jena LF, since these deploy precisely the same execution strategy for property paths as do MillDB LF, and Jena, respectively. The experimental results are summarized in Table~\ref{tab-pp1} and Figure~\ref{fig:rpqs}.

\begin{table}
\caption{Summary of query times, in seconds, for property paths, when limiting the queries to 100{,}000 results. Average and median are for all the queries, including errors and timeouts. Avg. succ. and median succ. excludes the queries that gave a timeout or an error for that particular engine.}
\label{tab-pp1}
\footnotesize%
\begin{tabular}{lrrrrr}
\toprule
		& MillDB & BlazeG & Jena 	& Virtuoso & Neo4J \\
\midrule
Supported 	& 1683 	& 1683	& 1683 	& 1683	& 1622 \\
Error 		& 0	& 2	& 19 	& 55	& 42 \\
Timeouts    & 0	& 44	& 41 	& 4	& 42 \\
Average 	& 1.1	& 27.6	& 22.8 	& 5.8 	& 23.3 \\
Median 		& 0.094	& 0.396	& 0.207 & 0.325 & 0.328 \\
Avg. succ. 	& 1.1	& 11.2	& 6.3 	& 1.8 	& 8.0 \\
Median succ. 	& 0.094	& 0.382	& 0.175 & 0.294 & 0.277 \\
\bottomrule
\end{tabular}
\end{table}

\begin{figure}[t]
\includegraphics[width=0.45\columnwidth]{plots/rpq100k.pdf}

    \vspace{0.3cm}
    \begin{tikzpicture}
       \begin{customlegend}[legend columns=5,legend style={draw=none,column sep=1ex, font=\footnotesize, cells={anchor=west}, at={(0.5,-0.15)},
      anchor=north, /tikz/every even column/.append style={column sep=0.2cm}},legend entries={\small\textsf{MillDB}, \small\textsf{Blazegraph}, \small\textsf{Jena}, \small\textsf{Virtuoso}, \small\textsf{Neo4J}}]
          \pgfplots@addlegendimage{black,fill=red, ybar stacked}
          \pgfplots@addlegendimage{black,fill=brown,ybar stacked}
          \pgfplots@addlegendimage{black,fill=blue,ybar stacked}
          \pgfplots@addlegendimage{black,fill=red!20,ybar stacked}
          \pgfplots@addlegendimage{black,fill=yellow,ybar stacked}
       \end{customlegend}
    \end{tikzpicture}
\caption{Boxplots of query times on property paths, limiting the results to 100{,}000.}
\label{fig:rpqs}
\end{figure}

We can observe that, again, MillenniumDB is the fastest and has the most stable performance, being able to run all the queries. Its average is near a second, i.e., five times faster than the next best contender (Virtuoso). Its median, below 0.1 seconds, is half the next one (Jena's). Even after removing the queries that timed-out on the other systems, they are considerably slower than MillenniumDB.
In particular, if we only consider the queries that run successfully on Virtuoso (i.e., excluding the 59 queries that timed-out or gave an error), we get an average time of 0.85 seconds and a median time of 0.086 seconds on MillenniumDB, less than half the times of Virtuoso. The boxplots further show the
stability of MillenniumDB:
the medians of
other baselines are over the third quartile of MillenniumDB.
Their third quartile is 5--10 times higher than that of
MillenniumDB, and higher than its topmost whisker.

To further test robustness,
we also ran all of the queries {\it without limiting the output size} on MillenniumDB. In this test, the engine timed out in only 15 queries, each returning between 800 thousand and 44 million results before timing out. When running queries to completion, MillenniumDB averaged 13.4 seconds per query (8 seconds if timeouts were excluded), with a mean of 0.1 seconds (both with and without timeouts).

\begin{comment}
Next, we do a finer analysis of the query results by splitting the query set into three subsets, based on how they performed in our first experiment:
\begin{itemize}
\item Subset1 contains only the queries which managed to successfully complete in less than 1 minute on each engine.
\item Subset2 contains only the queries that successfully completed on each engine (in less than 15 minutes), but ran more than 1 minute on some.
\item Subset3 contains the remaining queries; namely, the ones that timed out on some engine.
\end{itemize}

Subset1 is used to test the performance of engines on queries that they evaluate efficiently. Subset2 does the same, but now with queries that the engines need to do some work with, and the Subset3 tests the engines on challenging queries. We summarize the results in Table \ref{tab-pp2}. As we can see, on ``fast" queries, Virtuoso now performs extremely well, but on more challenging queries the difference between MillenniumDB and the other engines  is still marked. We remark two things about these results: (i) the execution times can vary significantly compared to the first batch which ran all 1684 queries in succession; and (ii) there is query in Subset2 which now times out on Jena. Both of these anomalies can be explained due to the fact that the performance of a database engine is highly affected by the state of its buffer, and the interaction between the OS and the hard disc (which is by default undeterministic). We believe that running the experiments one after the other as proposed here actually gives a better picture of how a system will perform under a realistic load than doing the cold/hot run comparison\footnote{As a side note, a hot run of each query in MillenniumDB is extremely fast. Even for queries that take a few minutes to execute on a cold run, the second execution terminates in less than 20 milliseconds.}. Finally, the queries that time out in the first set of experiments  were run at the end (Subset3).

TODO: NEED TO EXPLAIN WHY THERE ARE MORE TIMEOUTS COMPARED TO TABLE 1 ON JENA!!!! ON THE OTHER TWO PRECISELY THE SAME QUERIES TIMEOUT.

\begin{table}
\resizebox{\columnwidth}{!}{
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{Subset1}\\
\hline
& Neo4J & Jena & BlazeG & Virtuoso & MillDB \\
\hline
Average (s) & ? & 3.3 & 2.75 & 0.33 & 0.65\\
Mean (s) & ? & 0.124 & 0.119 & 0.136 & 0.044\\
\hline
\hline
\multicolumn{6}{|c|}{Subset2}\\
\hline
& Neo4J & Jena & BlazeG & Virtuoso & MillDB \\
\hline
Average (s) & ? & $79.3^\dagger$ & 153.9 & 24.3 & 10\\
Mean (s) & ? & $23.343^\dagger$ & 81.954 & 7.089 & 0.080\\
\hline
\hline
\multicolumn{6}{|c|}{Subset3}\\
\hline
& Neo4J & Jena & BlazeG & Virtuoso & MillDB \\
\hline
Errors & ? & 62 & ? & 43 & 0\\
Average (s) & ? & 404 & & 377 & 2.44\\
Mean (s) & ? & 7.5 & & 19.6 & 0.129\\
Avg. succ. (s) & ? & 28.1 & & 20.9 & 2.44\\
Mean succ. (s) & ? & 0.36 & & 0.85 & 0.129\\
\hline
\end{tabular}
}
\caption{Queries divided based on their first run. $\dagger$ on this run Jena timed out on a single query. This query was removed for the purposes of calculating the average and the mean. For Subset3 the values are reported both with and without queries that timed out.}
\label{tab-pp2}
\end{table}

Progression of experiments:
\begin{itemize}
\item All Aidan's queries, stripped of the ones that now give 0 results due to the reduced dataset. Running one after the other. Other engines either crash or need to be restarted when giving a timeout.
\item We split the dataset in 3 classes: (i) quick queries <1min in all the engines; (ii) slow queries >1 <5 min in all the engines; (iii) queries that time out on some engine. A note: the results change from the first set to the split sets. This is most likely due to the buffer management policies, and the disk/OS interaction.
\item The timeout queries are run on MillenniumDB: as in the experiments, with no limit, and also printing the paths.
\item The mega query is created: a CRPQ consisting of all the queries that timeout on other engines.
\item We could go into Diego's classification: namely, for the 10 most numerous classes of queries, we can find two patterns such that: the first one runs fast, the second one timeouts.
\end{itemize}

\end{comment}

\subsection{Wikidata Complete}
\label{ss-full}
To show the scalability of MillenniumDB, and to leverage its domain graph, we ran experiments with \textit{Wikidata Complete} to measure query performance. We ran the same queries from the four benchmarks above (\textit{Single}, \textit{Multiple}, and \textit{Complex} BGPs, as well as property paths). The number of outputs on the two versions of the data, while not the same, was within the same order of magnitude averaged over all the queries. The results are presented in Table \ref{tab-full}. As we can observe, MillenniumDB shows no deterioration in performance when a larger database is considered for similar queries. This is mostly due to the fact that the buffer only loads the necessary pages into the main memory, and will probably require a rather similar effort in both cases. We also note that, again, no queries resulted in a timeout over the larger dataset.

\begin{table}
\caption{Average and median runtimes, in seconds, for MillenniumDB on the complete version of Wikidata with the same query load as in the previous subsections.}
\label{tab-full}
\footnotesize
\begin{tabular}{lrrrr}
\toprule
		& Single & Multiple & Complex & Paths \\
\midrule
Average 	& 0.08	& 4.04	& 0.35 	& 1.04  \\
Median 		& 0.07	& 0.28	& 0.095 &  0.10  \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Popular Graph Data Models}

A number of graph-based data models have become popular in recent years~\cite{AnglesABHRV17}. Perhaps the simplest such model is that of \textit{directed labelled graphs}, that is a set of nodes and edges such that every edge relates a pair of nodes. An edge is graphically represented as \gedge[arrin][0.6cm]{$a$}{$b$}{$c$}, where $a$ is called the source node, $b$ the edge label, and $c$ the target node. A real example of edge might be \gedge[arrin][2cm]{Michelle Bachelet}{position held}{President of Chile}. Hence, nodes are used to represent entities and edges represent binary relations.

While directed labelled graphs work straightforwardly for representing binary relations, things become more complicated if we wish to consider higher arity relations, such as to indicate \textit{when} Michelle Bachelet held the position of President of Chile. Figure~\ref{fig:mb} presents a statement group from the Wikidata knowledge graph~\cite{VrandecicK14} where labels are presented in English for readability. This example contains two statements relating to two different presidencies of \texttt{Michelle Bachelet}. Each statement is associated with its own \textit{qualifiers}, including \texttt{start date} and \texttt{end date}, whom she was replaced by, and whom she replaced. Statements may also be associated with ranks, references, and so forth. Complex statements like this can be cumbersome to be represent as a directed labelled graph, requiring some form of \textit{reification} to decompose $n$-ary relations into binary relations~\cite{HernandezHK15}. For example, Figure~\ref{fig:delg} shows a graph where $e_1$ and $e_2$ are nodes representing $n$-ary relationships. The reification is given by the use of the edges labelled as \texttt{source node}, \texttt{edge} and \texttt{target node}.

\begin{figure}[tb]
\centering
{\sf
\begin{tabular}{l}
\large\textbf{Michelle Bachelet\wid{Q320}}\\[1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad
{\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2014-03-11\\
end date \wid{P582} 	& 2018-03-11\\
replaces\wid{P155}	& Sebastián Piñera\wid{Q306}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}\\
\\[-1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad {\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2006-03-11\\
end date \wid{P582} & 2010-03-11\\
replaces\wid{P155} & Ricardo Lagos\wid{Q331}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}
\end{tabular}
}
\caption{Wikidata statement group for Michelle Bachelet \label{fig:mb}}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=8.5cm]{./images/digraph.png}
\caption{Directed edge-labelled graph reifying the statements of Figure~\ref{fig:mb} \label{fig:delg}}
\end{figure}

Using reification may make the graph model less intuitive, and may be verbose in terms of using several edges to represent one relation. An alternative is to use a model able to represent higher-arity relationships. Among the most popular alternatives are property graphs~\cite{FrancisGGLLMPRS18}, RDF datasets~\cite{CyganiakWL14}, and RDF*~\cite{Hartig17}.

In property graphs, both nodes and edges can be associated with an id, a label, and one or more key--value pairs called properties. Figure~\ref{fig:pg1} shows a property graph for the statements of the running example.
Note that the two presidencies of \texttt{Michell Bachellet} are represented by using two different edges, and the specific qualifiers are represented as properties of such edges.
Although we are have solved the problem found by using a directed labelled graph (i.e. the use of reification for representing n-ary relations), we can observe that we are not able to associate more information to the properties of nodes and edges (e.g. \texttt{Sebastián Piñera} is a simple value instead of node that can be described). The later implies that the property graph model does not support relationships with multiple levels of descriptions or qualifiers.

\begin{figure}[t]
\centering
\includegraphics[width=8cm]{./images/pg1.png}
\caption{Property graph for the statements of Figure~\ref{fig:mb}.\label{fig:pg1}}
\end{figure}

Regarding RDF*~\cite{Hartig17}, the idea is to allow statements about statements, i.e. we can add edges to an edge. We illustrate this idea in Figure~\ref{fig:rdf-star}, where the statement \gedge[arrin][2cm]{Michelle Bachelet}{position held}{President of Chile} has been associated with qualifiers and other meta-data.  While this approach might appear promising at first glance, the two statements of Figure~\ref{fig:mb} cannot be distinguished as the model does not support multiple instances of the same statement; this would then conflate the qualifiers for the two presidencies.

\begin{figure}[t]
\centering
\includegraphics[width=8cm]{./images/rdf-star.png}
\caption{RDF* representation of the first statement of Figure~\ref{fig:mb} \label{fig:rdf-star}}
\end{figure}

\ma{If we want to distinguish the two statements of Figure~\ref{fig:mb}, couldn't we use two identifiers for the triple? In RDF* this could be written as follows:

\urit{t1} \urit{represents} <<\urit{Q320} \urit{P39} \urit{Q466956}>>

\urit{t2} \urit{represents} <<\urit{Q320} \urit{P39} \urit{Q466956}>>

And then we can use either \urit{t1} or \urit{t2} depending on the triple we are making reference to.
}

\ah{Yep, but then you are reifying the triple, and reification is precisely what RDF* is trying to avoid. :) Here, \urit{t1} and \urit{t2} represent the statements, which are basically the nodes $e_1$ and $e_2$ of Figure~\ref{fig:delg}. Maybe this could be clarified ...}

Finally we have RDF datasets~\cite{CyganiakWL14}, supported in SPARQL as named graphs~\cite{HarrisS13}, where multiple graphs can be defined and managed as a single instance. In this setting we can assign each statement to its own named graph, and then use the graph's name to define meta-data on the statement~\cite{HernandezHK15}. However, this approach has some practical limitations. Foremost of these, the model considers multiple distinct graphs rather than one graph; as a result, for example, path queries in SPARQL cannot be applied over multiple graphs at once, requiring either a default graph to be defined as the union of all graphs, or requiring the graphs on which the path should be applied to be explicitly named in the query.

These models are the most popular for graph databases in practice. Although they have different strengths and weaknesses, they all follow a graph abstraction and are thus interoperable, where one can convert data from one model to the other with relative ease (possibly using reification if moving from higher to lower arity).

\subsection{Property-Domain Graphs}
\label{sec-proposal}
In this section we introduce the notion of property-domain graph, which is the data model used in MillenniumDB.
The property-domain graph model extends the property graph model by allowing edges between edges, without any kind of restriction. This extension allows a multi-dimensional representation of relationships.

Assume an infinite set $\mathcal{L}$ of labels, and a set $\mathcal{V}$ of atomic values  (e.g. integers, strings, floats, dates, etc.).
\begin{definition}[Property-domain graph]
 A property-domain graph is a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
\item $O$ is a finite set of object identifiers;
\item $\gamma : O \to O \times O \times O$ is a partial function that associates objects with a tuple of three objects;
\item $\texttt{lab} : O \to \mathcal{L}$ is a partial function that associates objects with labels; and
\item $\texttt{prop} : O \times \mathcal{L} \to \mathcal{V}$ is a partial function that associates objects with labels and values (i.e. properties).
\end{itemize}
\end{definition}

 \begin{figure}[t]
\centering
\includegraphics[width=8.5cm]{./images/dgraph.png}
\caption{Property-domain graph for the statements of Figure~\ref{fig:mb}. \label{fig:dgraph}}
\end{figure}

The set $O$ is called the \textit{domain}, referring to both the universe of objects, and the domain of the function $\gamma$.
Each object in $O$ have a single identifier, zero or one label (defined by function $\texttt{lab}$), and zero or many properties (defined by function $\texttt{prop}$). In terms of data modeling, an object can represent an entity, a relationship (when it is in the domain of $\gamma$), or both.

An example of property-domain graph is presented in Figure \ref{fig:dgraph}.
We use different shapes to represent the componentes of an object: the object identifier and the label is inside a rounded square (e.g. $o_1:$ \texttt{Person}); the properties are inside a square (e.g. \texttt{Name = ``Michelle bachelet''}), and the 3-tuple associate to an object is inside a rounded dotted square (e.g. \gedge[arrin][1cm]{$o_1$}{$o_4$}{$o_5$}).

The objects are organized in groups called \emph{representation levels}.
Level 1 contains objects representing simple entities (e.g. $o_4:$) or complex entities (e.g. $o_1$).
Level 2 contains objects representing relations among the entities of level 1.
Level 3 contains objects from the lower leves, and so on.

Note that the property-domain graph is compatible with other graph models.
In fact, we just need a two-level property-domain graph to represent directed labeled graphs, RDF* graphs and named graphs.

\subsection{Domain Graphs (OLD, TO BE REMOVED)}
\label{sec-proposal}

We now define the graph data model used in MillenniumDB in order to generalise the aforementioned models used in practice. Assume a countably infinite set $\mathsf{Obj}$ of objects.

\begin{definition}
A \emph{domain graph} $G = (O,\gamma)$ consists of a finite set of objects $O\subseteq \mathsf{Obj}$ and a partial mapping $\gamma : O \rightarrow O \times O \times O$.
\end{definition}

The set $O$ is called the \textit{domain}, referring to both the universe of objects, and the domain of the function $\gamma$. Objects in $O$ may be either primitive or complex objects. Primitive objects include strings, IRIs, integers, existential variables, non-existential values, etc. Complex objects may include values with datatypes, units, precision, or languages; sets, bags, or ordered tuples/lists of values; items with nested ids, labels, property--value attributes, etc. Complex objects can often be replaced by primitive nodes described in the graph itself (as a classical example, RDF lists provide a mechanism for representing ordered terminated lists within an RDF graph without need for a dedicated list object~\cite{CyganiakWL14}). However, such representations might end up being verbose and inefficient to cope with. On the other hand, each new type of complex object requires higher level tools and languages to have dedicated logic and features to be able to correctly interpret and work with that object. We abstract away such details, assuming that graphs representing such objects can be lifted (to complex objects) and lowered (to a sub-graph of more primitive objects) as needs be. The domain of $\gamma$ can be handled internally by the database or externally by the user/dataset; the image of $\gamma$ (a graph) can also be queried independently of its domain.

The domain graph\xspace itself can be conceptualised in a number of ways. We can think of it as a directed edge-labelled graph (e.g., an RDF graph), where each edge has a unique identifier that makes it an object. Or we may consider it as akin to a directed labelled multigraph (sometimes known as a \emph{labelled quiver}).

An example of a domain graph\xspace representing the two statements of Figure~\ref{fig:mb} is given in Figure~\ref{fig:doma}. Here an object that is also a connection id (aka.\ an edge id) is denoted with lower case $e$. For example $\gamma(e_1) = (\texttt{Q320},\texttt{P39},\texttt{Q466956})$. The object $e_1$ then participates in two other connections $e_3$, and $e_4$. These can again be connected to other objects. Intuitively, in  $\gamma(e_1) = (\texttt{Q320},\texttt{P39},\texttt{Q466956})$, $e_1$ represents a connection between $\texttt{Q320}$ and $\texttt{Q466956}$, and $\texttt{P39}$ is a descriptor, or type/label of this connection. The descriptor itself can then be part of a connection, as is the case with, for instance, $\texttt{P39}$ in Figure~\ref{fig:mb}.

An important property of domain graphs\xspace is that they can be directly represented in the relational model and indexed straightforwardly. A domain graph\xspace can viewed as a single quaternary relation $Q(S,P,O,\underline{E})$, with primary key $E$, such that $\gamma(E)=(S,P,O)$. We will speak in more detail about indexing later in Section~\ref{sec:storage}.

Domain graphs\xspace also have the advantage of being compatible with other proposed models. For instance, they can model RDF graphs immediately: the range of $\gamma$ is a directed-edge labelled graph.

Similarly, RDF* graphs are also representable as a domain graph\xspace by either allowing RDF triples as complex objects, or by lowering, e.g., $((s,p,o),p',o')$ to $\gamma(e_1) = (s,p,o)$, $\gamma(e_2) = (e_1,p',o')$.

Likewise although RDF datasets are more general than domain graph\xspace, being representable as a relation $D(S,P,O,G)$ without $G$ being a primary key (here assuming a fixed IRI for the default graph), we can represent $(s,p,o,g)$ as $\gamma(e_1) = (s,p,o)$, $\gamma(e_2) = (e_1,\texttt{graph},g)$.

Additionally, if one allows complex objects in $O$ with labels and properties, they can also simulate property graphs in a direct way. More precisely, assuming a set $\mathcal{L}$ of labels, a set $\mathcal{K}$ of keys/attributes, and a set $\mathcal{V}$ of atomic values  (e.g. ints, strings, floats, dates, etc.), we define property-domain graphs\xspace as follows:

\begin{definition}[Property-domain graph\xspace]
 A property-domain graph\xspace is a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
    \item $(O,\gamma)$ is a domain graph\xspace;
    \item $\texttt{lab} : O \mapsto 2^\mathcal{L}$ is the labelling function assigning a finite set of labels to each object; and
    \item $\texttt{prop} : O \times \mathcal{K} \mapsto \mathcal{V}$ is a partial function.
\end{itemize}
\end{definition}

Each (multi-valued) property graph $G = (V,E,\rho,\lambda,\sigma)$, as defined in \cite{AnglesABHRV17}, is immediately modelled as a property-domain graph\xspace $G' = (O,\gamma,\texttt{lab},\texttt{prop})$, where $O = V\cup E$,  $\gamma(o) = (o_1,\varepsilon,o_2)$ whenever $\rho(o) = (o_1,o_2)$, $\texttt{lab}(o) = \lambda(o)$, and $\texttt{prop}(o,k)=\sigma(o,k)$. The intermediate node $\varepsilon$ is not used and can be removed for indexing; alternatively, if edges are restricted to have precisely one label (per Cypher/Neo4j~\cite{FrancisGGLLMPRS18}), then we can define $\varepsilon = \texttt{lab}(o)$ and use $\texttt{lab}$ for node labels only (now with $O = V\cup E \cup L$). To query on label and property data, auxiliary indexes would be required for $\texttt{lab}$ and $\texttt{prop}$. As an alternative to adding auxiliary indexes, the property-domain graph\xspace can be lowered to remove $\texttt{lab}$ and $\texttt{prop}$ on complex objects, representing $\texttt{lab}(o) = \{ l_1,\ldots,l_m \}$ as $\gamma(e_{l1}) = (o,\texttt{lab},l_1), \ldots, \gamma(e_{lm}) = (o,\texttt{lab},l_m)$, and representing $\texttt{prop}(o,k) = \{ v_1,\ldots,v_n \}$ as $\gamma(e_{p1}) = (o,k,v_1), \ldots, \gamma(e_{ln}) = (o,k,v_n)$ (now with $O = V\cup E \cup L \cup K \cup V$).

\subsection{Analysis of data models}
\label{sec-models}

\subsubsection{Data model 1}.

Assume an infinite set $\mathsf{Obj}$ of object identifiers, an infinite set $\mathcal{L}$ of labels, and a set $\mathcal{V}$ of atomic values  (e.g. integers, strings, floats, dates, etc.).
A property-domain graph is a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
\item $O \subset \mathsf{Obj}$ is a finite set of object identifiers;
\item $\gamma : O \to O \times O \times O$ is a partial function that associates objects with a tuple of three objects;
\item $\texttt{lab} : O \to \mathcal{L}$ is a partial function that associates objects with labels; and
\item $\texttt{prop} : O \times \mathcal{L} \to \mathcal{V}$ is a partial function that associates objects with labels and values (i.e. properties).
\end{itemize}

\begin{itemize}
\item It is a merge of the hypegraph data model (where edges can connect more than two nodes) and the hypernode data model (where a node can be a graph).
\item The function $\gamma$ is not compatible with the traditional notion of  (property) graph where an edge connects a pair of nodes.
\item The transversal use of labels for objects and properties simplify its definition and understanding.
\end{itemize}

\subsubsection{Data model 2}.

\newcommand{\operatorname{type}}{\operatorname{type}}

Assume an infinite set $\mathsf{Obj}$ of object identifiers, an infinite set $\mathcal{L}$ of labels,  a set $\mathcal{K}$ of keys/attributes, and a set $\mathcal{V}$ of atomic values  (e.g. integers, strings, floats, dates, etc.).
A property-domain graph is a tuple $G=(O,\gamma,\operatorname{type},\texttt{prop})$, where:
\begin{itemize}
\item $O \subset \mathsf{Obj}$ is a finite set of object identifiers;
\item $\gamma : O \to O \times O$ is a partial function;
\item $\operatorname{type}$ is a subset of $O \times O$;
\item $\texttt{prop} : O \times \mathcal{K} \to \mathcal{V}$ is a partial function.
\end{itemize}

Notes:
\begin{itemize}
\item The difference with Data Model 1 is the definition of the $\gamma$ function.
\item It is compatible with traditional (property) graphs as an edge is a pair of nodes.
\item Function $\operatorname{type}$ is a little confusing. It implies that any object can be a node, an edge, or a type.
\item The representation power could be higher than Data Model 1.
\end{itemize}

\subsubsection{Data model 3}.

Assume an infinite set $\mathsf{Obj}$ of object identifiers, an infinite set $\mathcal{L}$ of labels, and a set $\mathcal{V}$ of atomic values  (e.g. integers, strings, floats, dates, etc.).
A property-domain graph is a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
\item $O \subset \mathsf{Obj}$ is a finite set of object identifiers;
\item $\gamma : O \to O \times O$ is a partial function;
\item $\texttt{lab} : O \to \mathcal{L}$ is a partial function that associates objects with labels; and
\item $\texttt{prop} : O \times \mathcal{L} \to \mathcal{V}$ is a partial function that associates objects with labels and values (i.e. properties).
\end{itemize}

Notes:
\begin{itemize}
\item The difference with Data Model 1 is the definition of the $\gamma$ function.
\item It is compatible with traditional (property) graphs as an edge is a pair of nodes.
\item The transversal use of labels for objects and properties simplify its definition and understanding.
\item It seems to have the same representation power than Data Model 1.
\end{itemize}

\subsection{Query language for Data Model 3}
\label{sec-op1}

\smallskip
\noindent
\textbf{Data model}

Assume an infinite set $\mathsf{Obj}$ of object identifiers, an infinite set $\mathcal{L}$ of labels, and a set $\mathcal{V}$ of atomic values  (e.g. integers, strings, floats, dates, etc.).
 A property-domain graph is a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
\item $O \subset \mathsf{Obj}$ is a finite set of object identifiers;
\item $\gamma : O \to O \times O$ is a partial function (used to define edges);
\item $\texttt{lab} : O \to \mathcal{L}$ is a partial function that associates objects with labels; and
\item $\texttt{prop} : O \times \mathcal{L} \to \mathcal{V}$ is a partial function that associates objects with labels and values (i.e. properties).
\end{itemize}

The set $O$ is called the \textit{domain}, referring to both the universe of objects, and the domain of the function $\gamma$.
Each object in $O$ have a single identifier, zero or one label (defined by function $\texttt{lab}$), and zero or many properties (defined by function $\texttt{prop}$). In terms of data modeling, an object can represent an entity, a relationship (when it is in the domain of $\gamma$), or both.

\smallskip
\noindent
\textbf{Query language syntax}.

Assume a countably infinite set $\mathsf{Var}$ of variables disjoint with the set of objects $\mathsf{Obj}$.

An \textit{path expression} \texttt{p} is defined recursively as as follows:
\begin{itemize}
\item if $a \in labels$ then $a$ is a simple path expression, and $\hat{ }a$ is an inverse path expression;
\item if $p_1$ and $p_2$ are path expressions then
 \begin{itemize}
  \item $p_1 \slash p_2$ is a sequence path expression;
  \item $p_1 + p_2$ is an alternative path expression;
  \item $p_1^*$ is a zero-or-more path expression;
  \item $e?$ is a zero-or-one path expression;
 \end{itemize}
\end{itemize}

Let $t_1, t_2, t_3 \in \mathsf{Obj} \cup \mathsf{Var}$ and $p$ be a path expression.
A \emph{graph pattern} is defined recursively as follows:
A tuple $(t_1,t_2,t_3)$ is a graph pattern called \emph{simple pattern};
A tuple $(t_1, p, t_2)$ is a graph pattern called \emph{path pattern};
If $P_1$ and $P_2$ are graph patterns then $(P_1 ~\operatorname{AND}~ P_2)$ and $(P_1 ~\operatorname{OPT}~ P_2)$ are complex graph patterns.

A \emph{selection condition} is defined recursively as follows:
(a) If $?X,?Y \in \mathsf{Var}$, $p,q \in \mathcal{L}$ and $a \in \mathcal{V}$ then $({?X} = {?Y})$, ${label(?X)} = {p}$, ${label(?X)} = {label(?Y)}$, ${?X.p} = {?Y.q}$, ${?X.p} = {a}$ are atomic selection conditions;
(b) If $C_1, C_2$ are selection conditions then $(C_1 \land C_2)$, $(C_1 \lor C_2)$ and $(\neg C_1)$ are complex selection conditions.

Let $?X \in \mathsf{Var}$, $p \in \mathcal{L}$ and $q \in \mathcal{L}$.
A \emph{projection function} is any of the following expressions: $?X \operatorname{AS} p$, $o.p \operatorname{AS}  q$, $label(?X) \operatorname{AS} q$.
A \emph{projection clause} is a set of projection functions.

A \emph{query} is a tuple $(S,P,C)$ where $S$ is a projection function, $P$ is a graph pattern, and $C$ is a selection condition.

\smallskip
\noindent
\textbf{Query language semantics}

A \textit{solution mapping} (or simply \textit{mapping}) is a partial function $\mu: \mathsf{Var} \rightarrow \mathsf{Obj}$.
The \emph{domain} of a mapping $\mu$, denoted $\Dom{\mu}$, is the set of variables on which $\mu$ is defined.
Given $?X \in \mathsf{Var}$ and $o \in \mathsf{Obj}$, we use $\mu(?X) = o$ to denote that $\mu$ maps variable $?X$ to object $o$.
Additionally, we will assume that $\mu(o)=o$, for all $o\in \mathsf{Obj}$.

Two mappings $\mu_1, \mu_2$ are \emph{compatible}, denoted $\mu_1 \sim \mu_2$, when for all $?X \in \text{dom}(\mu_1) \cap \text{dom}(\mu_2)$ it satisfies that $\mu_1(?X)=\mu_2(?X)$.
Note that two mappings with disjoint domains are always compatible.
The union of compatible mappings, denoted $\mu_1 \cup \mu_2$, is also a mapping.

Let $\Omega_1$ and $\Omega_2$ be sets of mappings.
The operations of join, union, difference and left outer-join between $\Omega_1$ and $\Omega_2$ are defined as follows:
\begin{verse}
$\Omega_1 \Join \Omega_2  = \{ \mu_1 \cup \mu_2 \mid \mu_1 \in \Omega_1 ~\land~ \mu_2 \in \Omega_2 ~\land~ \mu_1 \sim \mu_2 \}$

$\Omega_1 \cup \Omega_2  = \{ \mu \mid \mu_1 \in \Omega_1 ~\lor~ \mu_2 \in \Omega_2 \}$

$\Omega_1 \setminus \Omega_2  = \{ \mu _1 \in \Omega_1 \mid \forall \mu_2 \in \Omega_2, \text{ is false that } \mu_1 \sim \mu_2  \}$

$\Omega_1 \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \Omega_2  = (\Omega_1 \Join \Omega_2) \cup (\Omega_1 \setminus \Omega_2) \}$
\end{verse}

The semantics of selection conditions is defined as follows.
Given a selection condition $C$, a mapping $\mu$, and a graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, we say that $\mu$ satisfies $C$ under $G$, denoted by $\mu \models_G C$, if.
\begin{itemize}
\item
$C$ is ${?X} = {?Y}$, $?X \in \text{dom}(\mu)$, $?Y \in \text{dom}(\mu)$, $\mu(?X) \in O$, $\mu(?Y) \in O$, and $\mu(?X) = \mu(?Y)$;
\item
$C$ is ${label(?X)} = {p}$, $?X \in \text{dom}(\mu)$, $\mu(?X) \in O$, and $\texttt{lab}(?X) = p$;
\item
$C$ is ${label(?X)} = {label(?Y)}$, $?X \in \text{dom}(\mu)$, $?Y \in \text{dom}(\mu)$, $\mu(?X) \in O$, $\mu(?Y) \in O$, and $\texttt{lab}(?X) = \texttt{lab}(?Y)$;
\item
$C$ is ${?X.p} = {?Y.q}$, $?X \in \text{dom}(\mu)$, $?Y \in \text{dom}(\mu)$, $\mu(?X) \in O$, $\mu(?Y) \in O$ and $\texttt{prop}(\mu(?X),p) = \texttt{prop}(\mu(?Y),q)$;
\item
$C$ is ${?X.p} = {a}$, $?X \in \text{dom}(\mu)$, $\mu(?X) \in O$ and $\texttt{prop}(\mu(?X),p) = a$;
\item
$C$ is $(C_1 \land C_2)$, $C_1$ and $C_2$ are selection conditions, $\mu \models_G C_1$ and $\mu \models_G C_2$;
\item
$C$ is $(C_1 \lor C_2)$, $C_1$ and $C_2$ are selection conditions, $\mu \models_G C_1$ or $\mu \models_G C_2$;
\item
$C$ is $(\neg C_1)$, $C_1$ is a selection condition, and it is not the case that $\mu \models_G C_1$.
\end{itemize}

The evaluation of a graph pattern $P$ over a property domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, is defined as a function $\semp{P}{G}$ which returns a set of solution mappings.
If $P$ is a simple pattern $(t_1, t_2, t_3)$ then
\begin{verse}
$\semp{P}{G} = \{ \mu \mid \text{dom}(\mu) = var(P) ~\land~ \gamma(\mu(t_2)) = (\mu(t_1), \mu(t_3)) \}$
\end{verse}
where $var(P)$ is the set of variables occurring in $P$.
The semantics of complex graph patterns is defined as follows:
\begin{verse}
$\semp{(P_1 ~\operatorname{AND}~ P_2)}{G} = \semp{P_1}{G} \Join \semp{P_2}{G}$

$\semp{(P_1 ~\operatorname{OPT}~ P_2)}{G} = \semp{P_1}{G} \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \semp{P_2}{G}$
\end{verse}

Given a domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, a path in $G$ is a sequence $ S = [o_1, \dots, o_n] $ where $o_1, \dots, o_n \in \mathsf{Obj}$, and satisfying that for each pair $(o_i, o_{i+1})$ with $1 \leq i < n$, it applies that $\gamma(o_i) = (a,b)$ and $\gamma(o_{i+1})=(b,c)$. The length of $S$, denoted as $length(S)$, is $n$.

\subsection{Graph Data Models}

One of the simplest models used for representing knowledge graphs is based on \textit{directed labelled graphs}, which consist of a set of nodes and edges such that every edge relates a pair of nodes. An edge is graphically represented as \gedge[arrin][0.6cm]{$a$}{$b$}{$c$}, where $a$ is called the source node, $b$ the edge label, and $c$ the target node. Such graphs are the basis of the RDF data model~\cite{CyganiakWL14}, where the source node, edge label and target node are called \textit{subject}, \textit{predicate} and \textit{object}, respectively. In the context of knowledge graphs, nodes are used to represent entities and edges represent binary relations. For example, with the edge \gedge[arrin][1.8cm]{Michelle Bachelet}{position held}{President of Chile}, we can state that Michelle Bachelet was (or is) the president of Chile.

However, directed labelled graphs are sometimes \textit{too} simple. While they elegantly represent binary relations, they are cumbersome when representing higher arity relations. Take, for example, the statements from the Wikidata knowledge graph~\cite{VrandecicK14} illustrated in Figure~\ref{fig:mb}. We see that the statements encode the same binary relation, but it is now associated with nested \textit{qualifiers} that provide additional information: in this case a start date, and end date, who replaced her, and whom she was replaced by. We also see that the same binary relation is expressed twice, indicating two distinct periods when she held the position. Representing statements like this in a directed labelled graph requires some form of \textit{reification} to decompose $n$-ary relations into binary relations~\cite{HernandezHK15}. For example, Figure~\ref{fig:delg} shows a graph where $e_1$ and $e_2$ are nodes representing $n$-ary relationships. The reification is given by the use of the edges labelled as \texttt{source}, \texttt{label} and \texttt{target}. For simplicity, we use human-readable nodes and labels, where in practice, a node \gnode{Sebastián Piñera} will rather be given as the identifier \gnode{Q306}, and an edge label \texttt{replaces} will rather be given as \texttt{P155}.

\newcommand{\wid}[1]{{\color{gray}~[#1]}}

\begin{figure}[tb]
\centering
{\sf
\begin{tabular}{l}
\large\textbf{Michelle Bachelet\wid{Q320}}\\[1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad
{\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2014-03-11\\
end date \wid{P582} 	& 2018-03-11\\
replaces\wid{P155}	& Sebastián Piñera\wid{Q306}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}\\
\\[-1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad {\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2006-03-11\\
end date \wid{P582} & 2010-03-11\\
replaces\wid{P155} & Ricardo Lagos\wid{Q331}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}
\end{tabular}
}
\caption{Wikidata statement group for Michelle Bachelet \label{fig:mb}}
\end{figure}

\begin{figure}[t]
\setlength{\vgap}{0.45cm}
\setlength{\hgap}{2.5cm}
\centering
\begin{tikzpicture}
\node[iri] (e1) {$e_1$};

\node[iri,right=\hgap of e1] (pe1) {position held}
  edge[arrin] node[lab] {label} (e1);

\node[iri,above=\vgap of pe1] (se1) {Michelle Bachelet}
  edge[arrin] node[lab] {source} (e1);

\node[iri,below=\vgap of pe1] (oe1) {President of Chile}
  edge[arrin] node[lab] {target} (e1);

\node[iri,above=\vgap of se1] (sp) {Sebastian Piñera}
  edge[arrin] node[lab] {replaced by} (e1)
  edge[arrin,bend right=19] node[lab,pos=0.45] {replaces} (e1);

\node[iri,right=\hgap of pe1] (e2) {$e_2$}
  edge[arrout] node[lab] {label} (pe1)
  edge[arrout] node[lab] {source} (se1)
  edge[arrout] node[lab] {target} (oe1)
  edge[arrout] node[lab] {replaced by} (sp);

\node[iri,below=2.2\vgap of e1] (sd1) {2014-03-11}
  edge[arrin] node[lab] {start date} (e1);
\node[iri,above=2.2\vgap of e1] (ed1) {2018-03-11}
  edge[arrin] node[lab] {end date} (e1);

\node[iri,below=2.2\vgap of e2] (sd2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);
\node[iri,above=2.2\vgap of e2] (ed2) {2010-03-11}
  edge[arrin] node[lab] {end date} (e2);

\node[iri,below=\vgap of oe1] (rl) {Ricardo Lagos}
  edge[arrin,bend right=17] node[lab] {replaces} (e2);
\end{tikzpicture}
\caption{Directed edge-labelled graph reifying the statements of Figure~\ref{fig:mb} \label{fig:delg}}
\end{figure}

A number of graph models have been proposed to capture higher-arity relations more concisely, including property graphs~\cite{FrancisGGLLMPRS18} and RDF*~\cite{Hartig17}. However, all of these have limitations that render them incapable of modelling the statements shown in Figure~\ref{fig:mb} without resorting to reification~\cite{HoganRRS19}. Property graphs allow labels and property--value pairs to be associated with both nodes and edges, as shown in Figure~\ref{fig:pg}. Though more concise than reification, labels, properties and values are considered to be simple strings, which are disjoint with nodes; for example, \texttt{"Ricardo Lagos"} is not a node nor a pointer to a node, but a string, which would complicate, for example, querying for the parties of presidents that Michelle Bachelet replaced. On the other hand, RDF* allows an edge to be a node, where Figure~\ref{fig:rdf*} illustrates how it can represent the first statement. However,  we can only represent one of the statements (without reification), as we can only have one distinct node per edge; if we add the qualifiers for both statements, then we would not know which start date pairs with which end date, for example.

\begin{figure}[t]
\setlength{\vgap}{1.5cm}
\setlength{\hgap}{1cm}
\centering
\begin{tikzpicture}

  \node[nrect] (n1) {
   \alt{
       \uri{given name} & =\,\uri{"Verónica"} } };

  \node[rt] (ln1) at (n1.north) {\uri{human : Michelle Bachelet}};

  \node[nrect,right=\hgap of n1] (n2) {
   \alt{
      \uri{inception} & =\,\uri{"09 July 1826"} } };

  \node[rt] (ln2) at (n2.north) {\uri{public office: President of Chile}};

  \draw[arrout,pos=0.5,bend left=25] (ln1) to node[rte,yshift=-0.2cm] (le1)
   {\uri{$e_1$ $:$ position held}}
  (ln2);

  \node[erect,anchor=south,yshift=-0.5ex] at (le1.north) (e1) {
     \alt{ \uri{start date} & =\,\uri{"11 March 2014"}\\[-0.7em]
           \uri{end date} & =\,\uri{"11 March 2018"}\\[-0.7em]
           \uri{replaces} & =\,\uri{"Sebastián Piñera"}\\[-0.7em]
           \uri{replaced by} & =\,\uri{"Sebastián Piñera"} } };

  \draw[arrout,pos=0.5,bend right=25] (n1) to node[rte] (le2) {\uri{$e_2$ $:$ position held}} (n2);

  \node[erect,anchor=north,yshift=0.5ex] (e2) at (le2.south) {
     \alt{ \uri{start date} & =\,\uri{"11 March 2006"}\\[-0.7em]
           \uri{end date} & =\,\uri{"11 March 2010"}\\[-0.7em]
           \uri{replaces} & =\,\uri{"Ricardo Lagos"}\\[-0.7em]
           \uri{replaced by} & =\,\uri{"Sebastián Piñera"}\\ } };
\end{tikzpicture}
\caption{Property graph for the statements of Figure~\ref{fig:mb}, with some additional data\label{fig:pg}}
\end{figure}

\begin{figure}[tb]
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.9cm}
\centering
\begin{tikzpicture}
\node[iri,anchor=center,minimum width=6.3cm,minimum height=0.7cm,dashed] (e1) {};
\node[iri,right=1ex of e1.west,anchor=west] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp1);

\node[iri,below=\vgap of e1] (mb) {Sebastián Piñera}
  edge[arrin,bend right=40] node[lab,xshift=1ex] {replaces} (e1)
  edge[arrin,bend left=40] node[lab,xshift=-1ex] {replaced by} (e1);

\node[iri,left=\hgap of mb] (ttt) {2018-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,right=\hgap of mb] (ttf) {2014-03-11}
  edge[arrin] node[lab] {end date} (e1);
\end{tikzpicture}
\caption{RDF* graph for the first statement of Figure~\ref{fig:mb} \label{fig:rdf*}}
\end{figure}

\subsection{Domain Graphs}
\label{sec-proposal}

Our data model proposes a simple extension of directed labelled graphs in order to more concisely represent higher-arity relations: each edge of the form \gedge[arrin][1.8cm]{Michelle Bachelet}{position held}{President of Chile} is assigned a unique (possibly internal, autogenerated) identifier that can be used elsewhere in the graph. Figure~\ref{???} illustrates how the statements of Figure~\ref{fig:mb} are represented in our model.

\ah{Giving three alternatives for how to draw the domain graph: Figure~\ref{fig:dg1}, Figure~\ref{fig:dg2}, Figure~\ref{fig:dg3}. We would only use one, whatever is preferred.}
\ra{I like Figure~\ref{fig:dg2}, although it just works for a single level of edge-with-edge.}
\dv{I would still vote for Figure~\ref{fig:dg3}, but putting "edges" into different types of boxes. I can live with the other two as well though.}
\riveros{My vote is for Figure~\ref{fig:dg2}. It is in line of the spirit of Domain graphs. However, it is a bit misleading, because each edge should also have an identifier. I would explain this in the text. }

\begin{figure}[tb]
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.9cm}
\centering
\begin{tikzpicture}
\node[iri,anchor=center,minimum width=6.8cm,minimum height=1.3cm,dashed] (e1) {};

\node[anchor=south east,above left=0.1ex of e1.south east,dashed] (e1i) {$e_1$};

\node[iri,right=1ex of e1.west,anchor=west,yshift=1ex] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp1);

\node[iri,anchor=center,minimum width=6.8cm,minimum height=1.3cm,anchor=mid,fill=none,xshift=-4ex,yshift=2ex,dashed] (e2) at (e1) {};

\node[anchor=north west,below right=0.1ex of e2.north west] (e2i) {$e_2$};

\node[iri,below=\vgap of e1] (ttt) {2018-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,left=\hgap of ttt] (mb) {Sebastián Piñera}
  edge[arrin,bend right=20] node[lab,xshift=1ex] {replaces} (e1)
  edge[arrin] node[lab,xshift=-1ex] {replaced by} (e1)
  edge[arrin,bend left=10] node[lab,xshift=-1ex] {replaced by} (e2.190);

\node[iri,right=\hgap of ttt] (ttf) {2014-03-11}
  edge[arrin] node[lab] {end date} (e1);

\node[iri,above=\vgap of e2] (ttt2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);

\node[iri,left=\hgap of ttt2] (rl) {Richard Lagos}
  edge[arrin] node[lab,xshift=1ex] {replaces} (e2);

\node[iri,right=\hgap of ttt2] (ttf2) {2010-03-11}
  edge[arrin] node[lab] {end date} (e2);

\end{tikzpicture}
\caption{Domain graph for Figure~\ref{fig:mb} (v1) \label{fig:dg1}}
\end{figure}

\begin{figure}[tb]
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.9cm}
\centering
\begin{tikzpicture}
\node[iri,anchor=center,minimum width=6.6cm,minimum height=0.7cm,dashed] (e1) {};

\node[anchor=south east,above left=0.1ex of e1.south east] (e1i) {$e_1$};

\node[iri,right=1ex of e1.west,anchor=west] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp1);

\node[iri,below=\vgap of e1] (mb) {Sebastián Piñera}
  edge[arrin,bend right=40] node[lab,xshift=1ex] {replaces} (e1)
  edge[arrin,bend left=40] node[lab,xshift=-1ex] {replaced by} (e1);

\node[iri,left=\hgap of mb] (ttt) {2018-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,right=\hgap of mb] (ttf) {2014-03-11}
  edge[arrin] node[lab] {end date} (e1);

\node[iri,anchor=center,below=\vgap of mb,minimum width=6.6cm,minimum height=0.7cm,dashed] (e2) {}
  edge[arrout] node[lab,xshift=-1ex] {replaced by} (mb);

\node[anchor=south east,above left=0.1ex of e2.south east,dashed] (e2i) {$e_2$};

\node[iri,right=1ex of e2.west,anchor=west] (sp2) {Michelle Bachelet};
\node[iri,right=\hgap of sp2] (ch2) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp2);

\node[iri,below=\vgap of e2] (rl) {Richard Lagos}
  edge[arrin] node[lab] {replaces} (e2);

\node[iri,left=\hgap of rl] (ttt2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);

\node[iri,right=\hgap of rl] (ttf2) {2010-03-11}
  edge[arrin] node[lab] {end date} (e2);

\end{tikzpicture}
\caption{Domain graph for Figure~\ref{fig:mb} (v2) \label{fig:dg2}}
\end{figure}

\begin{figure}[tb]
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.6cm}
\centering
\begin{tikzpicture}
\node[iri,anchor=west,yshift=1ex] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin,bend left=40] node[fill=white] (e1) {$e_1:$ position held} (sp1)
  edge[arrin,bend right=40] node[fill=white] (e2) {$e_2:$  position held} (sp1);

\node[iri,below=\vgap of e1] (ttt) {2018-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,left=0.5\hgap of sp1] (mb) {Sebastián Piñera}
  edge[arrin,bend right=30] node[lab,xshift=1ex] {replaces} (e1)
  edge[arrin,bend right=10] node[lab,xshift=-1ex] {replaced by} (e1)
  edge[arrin,bend left=20] node[lab,xshift=-1ex] {replaced by} (e2);

\node[iri,right=0.5\hgap of ttt] (ttf) {2014-03-11}
  edge[arrin] node[lab,xshift=1ex] {end date} (e1);

\node[iri,above=\vgap of e2] (ttt2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);

\node[iri,left=0.5\hgap of ttt2] (rl) {Richard Lagos}
  edge[arrin] node[lab] {replaces} (e2);

\node[iri,right=0.5\hgap of ttt2] (ttf2) {2010-03-11}
  edge[arrin] node[lab,xshift=1ex] {end date} (e2);

\end{tikzpicture}
\caption{Domain graph for Figure~\ref{fig:mb} (v3) \label{fig:dg3}}
\end{figure}

Formally, assume a countably infinite set $\mathsf{Obj}$ of objects. We can define a domain graph as follows:
\riveros`{I would aim the presentation to VLDB people. Saying ``countably infinite'' has no practical implications for the model and it only scares a potential VLDB reviewer.}

\begin{definition}
A \emph{domain graph} $G = (O,\gamma)$ consists of a finite set of objects $O\subseteq \mathsf{Obj}$ and a partial mapping $\gamma : O \rightarrow O \times O \times O$.
\end{definition}

\ra{Is an object an identifier, a label, a value, the three above?}
\dv{This is explained below, but I agree that mentioning it as qualifiers is a bit confusing.}

Alternatively we can define our model as a relation:
\[\textsc{DomainGraph}(\textsf{source},\textsf{type},\textsf{target},\underline{\textsf{eid}}) \]
where \underline{\textsf{eid}} is a primary key of the relation.
\riveros{I would show here an example of how the relation of the running example would look. This will help to be more concrete about the model. }

In essence, one could argue that everything in domain graphs is a node, since it can be later referenced again in the mapping $\gamma$. This way domain graphs avoid the aforementioned limitations of other models. When compared with property graphs, the values of the qualifiers are nodes, not strings, which allows us to directly query for other edges involving that node. Compared with RDF*, we can have multiple nodes (with different identifiers) for the same edge. Compared with both, we can ``nest'' qualifiers without issue given that the edges encoding qualifiers themselves have identifiers, which we can use as nodes. We can also represent graphs in other models as domain graphs. Representing RDF* is direct: we simply assign identifiers to edges. In the case of property graphs, node labels can be modelled with an edge like \gedge[arrin]{Michelle Bachelet}{label}{human}, while property--value pairs on nodes or edges can be modelled as edges emanating from those nodes or edges.

\ah{We could define property domain graphs here in more detail, if preferred.}

Of course, features of the property graph data model such as node labels, or properties with their values, offer practical advantages when filtering classes of nodes and/or edges, as well as allowing to specify non trivial path constraints that are not captured purely by edge \textsf{types}. For this reason, and to ensure backwards compatibility with property graphs, in MillenniumDB we actually support an extended version of domain graphs, called property domain graphs.

\begin{definition}
 A \emph{property-domain graph\xspace} is defined as a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
    \item $(O,\gamma)$ is a domain graph\xspace;
    \item $\texttt{lab} : O \mapsto 2^\mathcal{L}$ is the labelling function assigning a finite set of labels to each object; and
    \item $\texttt{prop} : O \times \mathcal{K} \mapsto \mathcal{V}$ is a partial function assigning a value of a certain key (property) of some object, to its value.
\end{itemize}
\end{definition}
\riveros{I would specify $\mathcal{L}$, $\mathcal{K}$, and $\mathcal{V}$ in the definition of the model.}

In brief, domain graph\xspace capture the graph structure of our model, while property-domain graph\xspace additionally allow to assign labels and key value pairs to objects, as ordinary property graphs do.
A relational representation of property-domain graph\xspace would then contain the following two relations, in addition to the \textsc{DomainGraph} specified above:
\[\textsc{Labels}(\textsf{object},\textsf{label})\]
\[\textsc{Properties}(\underline{\textsf{object},\textsf{key}},\textsf{value})\]
where \underline{\textsf{object, key}} is a primary key of the second relation, with the first relation allowing multiple labels per object.

To sum, up the full data model supported by MillenniumDB allows the user to treat their graph as a:
\begin{itemize}
\item Standard property graph (by ignoring quantifiers and nested structures).
\item RDF graph (the domain graph\xspace model already accomplishes this by ignoring the edge id).
\item Wikidata \cite{VrandecicK14} knowledge graph which uses qualifiers that can again be nodes/objects.
\item Property graph with nested qualifiers (i.e. the full data model).
\end{itemize}

We note that an exploration of the expressive power of this data model lies outside of the scope of this paper, so we omit it here.
\riveros{Maybe I would add in the appendix ``simple'' translations of the main models in the literature to property-domain graphs. This is important for convincing the reader that the model is natural.}
As a side note in this direction, nested qualifiers actually allow the domain graph\xspace model to express features that are outside of the scope of hypergraphs.
\subsection{Domain Graphs}
\label{sec-proposal}

The structure of knowledge graphs is captured in MillenniumDB via \textit{domain graphs\xspace}, which follow the natural idea of assigning ids to directed labeled edges in capture higher-arity relations within graphs~\cite{HernandezHK15,IlievskiGCDYRLL20,LassilaSBBBKKLST}. Formally, assume a universe $\mathsf{Obj}$ of objects (ids, strings, numbers, IRIs, etc.). We define domain graphs\xspace as follows:

\begin{definition}
A \emph{domain graph} $G = (O,\gamma)$ consists of a finite set of objects $O\subseteq \mathsf{Obj}$ and a partial mapping $\gamma : O \rightarrow O \times O \times O$.
\end{definition}

Intuitively, $O$ is the set of objects that appear in our graph database, and $\gamma$ models edges between objects. If $\gamma(e)=(n_1,t,n_2)$, this states that the edge $(n_1,t,n_2)$ has id $e$, type $t$, and links the source node $n_1$ to the target node $n_2$.\footnote{Herein, we say ``\textit{edge type}'' rather than ``\textit{edge label}'' to highlight that the type forms part of the edge, rather than being an annotation on the edge, as in property graphs.} We can analogously define our model as a relation:
\[\textsc{DomainGraph}(\textsf{source},\textsf{type},\textsf{target},\underline{\textsf{eid}}) \]
where \underline{\textsf{eid}} (edge id) is a primary key of the relation.

The domain graph\xspace model of MillenniumDB already subsumes the RDF graph model~\cite{CyganiakWL14}. Recall that an RDF graph is a set of triples of the form $(a,b,c)$. An RDF graph can be visualized as a \textit{directed labeled graph}~\cite{AnglesABHRV17,MendelzonW89}, which is a set of edges of the form \gedge[arrin][0.6cm]{$a$}{$b$}{$c$}, where $a$ is the source node (aka \textit{subject}), $b$ the edge type (aka \textit{predicate}), and $c$ the target node (aka \textit{object}). Alternatively, an RDF graph can be seen as a relation $\textsc{RDFGraph}(\textsf{source},\textsf{type},\textsf{target})$. To show how RDF is modeled in domain graphs\xspace, consider the following edge, claiming that Michelle Bachelet was the president of Chile

\medskip
\begin{center}
\gedge[arrin][2.5cm]{Michelle Bachelet}{position held}{President of Chile}
\end{center}
\medskip

\noindent
We can encode this triple in a domain graph\xspace by storing the tuple \textsf{(Michelle Bachelet, position held, President of Chile, e)} in the \textsf{DomainGraph} relation, where \textsf{e} denotes a unique (potentially auto-generated) edge id, or equivalently stating that:
$$\gamma(\textsf{e}) = \textsf{(Michelle Bachelet, position held, President of Chile)}.$$

\noindent
The id of the edge itself is not accessible in the RDF data model. However, the edge id can be useful when modeling RDF* graphs or named graphs based on RDF, as we will discuss in Section~\ref{ssec:whydg}.

Property graphs~\cite{AnglesABHRV17} further allow nodes and edges to be annotated with labels and property--value pairs, as shown in Figure~\ref{fig:pgmb}. Domain graphs can directly capture property graphs, where, for example, the property--value pair $(\textsf{gender},\textsf{"female"})$ on node $n_1$ can be represented by an edge $\gamma(e_3) = (n_1,\textsf{gender},\textsf{female})$, the property--value pair $(\textsf{order},\textsf{"2"})$ on an edge $e_2$ becomes $\gamma(e_4) = (e_2,\textsf{order},\textsf{2})$, the label on $n_1$ becomes $\gamma(e_5) = (n_1,\textsf{label},\textsf{human})$, the label on $e_1$ becomes the type of the edge $\gamma(e_1) = (n_1,\textsf{father},n_2)$, etc.\footnote{To represent edges in property graphs that permit multiple labels, multiple edges with different types can be added (or the labels can be added on the edge ids).} However, given a legacy property graph, there are some potential ``incompatibilities'' with the resulting domain graph; for example, strings like \textsf{"male"}, labels like \textsf{human}, etc., now become nodes in the graph, generating new paths through them that may affect query results.

\begin{figure}
\begin{tikzpicture}
\node[nrect] (n1) {
\alt{
\uri{gender} & = \uri{"female"}\\[-0.7em]
\uri{children} & = \uri{"3"}\\[-0.7em]
\uri{first name} & = \uri{"Michelle"}\\[-0.7em]
\uri{last name} & = \uri{"Bachelet"}\\[-0.2em]
}};

\node[rt] (ln1) at (n1.north) {$n_1$ $:$ \uri{human}};

\node[rect, right=2.4cm of n1] (n2) {
\alt{
\uri{gender} & = \uri{"male"}\\[-0.7em]
\uri{children} & = \uri{"2"}\\[-0.7em]
\uri{first name} & = \uri{"Alberto"}\\[-0.7em]
\uri{last name} & = \uri{"Bachelet"}\\[-0.7em]
\uri{death} & = \uri{"12 March 1974"}\\[-0.2em]
}};

\node[rt] (ln2) at (n2.north) {$n_2$ $:$ \uri{human}};

\draw[arrout,bend left=7,transform canvas={yshift=0.25cm}] (n1) to
node[lab] (le1) {$e_1$ $:$ \uri{father}}
(n2);

\draw[arrout,bend left=7,transform canvas={yshift=0.27cm}] (n2) to
node[lab] (le2) {$e_2$ $:$ \uri{child}}
(n1);

\node[erect,anchor=south] (e2) at (n2.south-|le2.mid) {
\alt{
\uri{order} & = \uri{"2"}\\[-0.2em]
}
};
\end{tikzpicture}
\caption{A property graph with two nodes and two edges. We use the order property on edge $e_2$ to indicate that Michelle Bachelet is the second child of Alberto Bachelet}\label{fig:pgmb}
\end{figure}

For stricter backwards compatibility with legacy property graphs (where desired), MillenniumDB implements a simple extension of the domain graph\xspace model, called \textit{property domain graphs\xspace}, which allows for \textit{external annotation}, i.e., adding labels and property--value pairs to nodes and edges without creating new nodes and edges. Formally, if $\mathcal{L}$ is a set of labels, $\mathcal{P}$ a set of properties, and  $\mathcal{V}$ a set of values, we define a property domain graph\xspace as follows:

\begin{definition}
 A \emph{property domain graph\xspace} is defined as a tuple $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where:
\begin{itemize}
    \item $(O,\gamma)$ is a domain graph\xspace;
    \item $\texttt{lab} : O \rightarrow 2^\mathcal{L}$ is a function

    assigning a finite set of labels to an object; and
    \item $\texttt{prop} : O \times \mathcal{P} \rightarrow \mathcal{V}$ is a partial function assigning a value to a certain property of an object.

\end{itemize}
Moreover, we assume that for each object $o \in O$, there exists a finite number of properties $p \in \mathcal{P}$ such that $\texttt{prop}(o,p)$ is defined.
\end{definition}

In summary, domain graphs\xspace capture the graph structure of our model, while property domain graphs\xspace additionally permit annotating that graph structure by adding labels and property--value pairs to objects, as ordinary property graphs do; such annotations are then considered external from the graph structure. The property graph in Figure~\ref{fig:pgmb}
can be represented with the following property domain graph\xspace $G=(O,\gamma,\texttt{lab},\texttt{prop})$, where the graph structure is as follows:
{\small
\begin{align*}
O & = \{n_1,n_2,e_1,e_2\}, \\%[-0.6ex]
\gamma(e_1) & = (n_1,\textsf{father},n_2),\\%[-0.6ex]
\gamma(e_2) & = (n_2,\textsf{child},n_1),
\end{align*}}
and the annotations of the graph structure are as follows:
\vspace{-2mm}
\begin{center}
{\small
\begin{tabular}{ll}
$\textsf{lab}(n_1)= \textsf{human}$ &
$\textsf{prop}(n_1,\textsf{last name}) = \textsf{"Bachelet"}$\\
$\textsf{lab}(n_2) = \textsf{human}$ &
$\textsf{prop}(n_2,\textsf{gender}) = \textsf{"male"}$\\
$\textsf{prop}(e_2,\textsf{order}) = \textsf{"2"}$ &
$\textsf{prop}(n_2,\textsf{children}) = \textsf{"2"}$\\
$\textsf{prop}(n_1,\textsf{gender}) = \textsf{"female"}$ &
$\textsf{prop}(n_2,\textsf{first name}) = \textsf{"Alberto"}$\\
$\textsf{prop}(n_1,\textsf{children}) = \textsf{"3"}$ &
$\textsf{prop}(n_2,\textsf{last name}) = \textsf{"Bachelet"}$\\
$\textsf{prop}(n_1,\textsf{first name}) = \textsf{"Michelle"}$ &
$\textsf{prop}(n_2,\textsf{death}) = \textsf{"12 March 1974"}$
\end{tabular}
}
\end{center}
\medskip

\noindent The relational representation of property domain graph\xspace then adds two new relations alongside \textsc{DomainGraph}:
\begin{center}
$\textsc{Labels}(\textsf{object},\textsf{label})$,\\
$\textsc{Properties}(\underline{\textsf{object},\textsf{property}},\textsf{value}),$
\end{center}
where \underline{\textsf{object},\,\textsf{property}} is a primary key of the second relation, with the first relation allowing multiple labels per object.

\subsection{Why domain graphs\xspace?}\label{ssec:whydg}

Why did we choose domain graphs\xspace as the model of MillenniumDB? As discussed in the previous section, it can be used to model both directed labeled graphs (like RDF) as well as property graphs. It also has a natural relational expression, which facilitates its implementation in a query engine. But it is also heavily inspired by the needs of real-world knowledge graphs like Wikidata~\cite{VrandecicK14}.

Consider the two Wikidata statements shown in Figure~\ref{fig:mb}. Both statements claim that Michelle Bachelet was a president of Chile, and both are associated with nested \textit{qualifiers} that provide additional information: in this case a start date, an end date, who replaced her, and whom she was replaced by. There are two statements, indicating two distinct periods when she held the position. Also the ids for objects (for example, \textsf{Q320} and \textsf{P39}) are shown; any positional element can have an id and be viewed as a node in the knowledge graph.

\newcommand{\wid}[1]{{\color{gray}~[#1]}}

\begin{figure}[t]
\centering
{\sf
\begin{tabular}{l}
\large\textbf{Michelle Bachelet\wid{Q320}}\\[1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad
{\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2014-03-11\\
end date \wid{P582} 	& 2018-03-11\\
replaces\wid{P155}	& Sebastián Piñera\wid{Q306}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}\\
\\[-1ex]
\large\qquad position held\wid{P39} \quad President of Chile\wid{Q466956}\\
\qquad \qquad {\begin{tabular}{l@{\qquad~~}l}
start date \wid{P580} & 2006-03-11\\
end date \wid{P582} & 2010-03-11\\
replaces\wid{P155} & Ricardo Lagos\wid{Q331}\\
replaced by\wid{P156} & Sebastián Piñera\wid{Q306}\\
\end{tabular}}
\end{tabular}
}
\caption{Wikidata statement group for Michelle Bachelet \label{fig:mb}}
\end{figure}

Representing statements like this in a directed labeled graph requires some form of \textit{reification} to decompose $n$-ary relations into binary relations~\cite{HernandezHK15}. For example, Figure~\ref{fig:delg} shows a graph where $e_1$ and $e_2$ are nodes representing $n$-ary relationships. The reification is given by the use of the edges typed as \textsf{source}, \textsf{type} and \textsf{target}. As before, we use human-readable nodes and labels, where in practice, a node \gnode{Sebastián Piñera} will rather be given as the identifier \gnode{Q306}, and an edge type \textsf{replaces} will rather be given as \textsf{P155}.

\begin{figure}[t]
\setlength{\vgap}{0.45cm}
\setlength{\hgap}{2.5cm}
\centering
\begin{tikzpicture}
\node[iri] (e1) {$e_1$};

\node[iri,right=\hgap of e1] (pe1) {position held}
  edge[arrin] node[lab] {type} (e1);

\node[iri,above=\vgap of pe1] (se1) {Michelle Bachelet}
  edge[arrin] node[lab] {source} (e1);

\node[iri,below=\vgap of pe1] (oe1) {President of Chile}
  edge[arrin] node[lab] {target} (e1);

\node[iri,above=\vgap of se1] (sp) {Sebastian Piñera}
  edge[arrin] node[lab] {replaced by} (e1)
  edge[arrin,bend right=19] node[lab,pos=0.45] {replaces} (e1);

\node[iri,right=\hgap of pe1] (e2) {$e_2$}
  edge[arrout] node[lab] {type} (pe1)
  edge[arrout] node[lab] {source} (se1)
  edge[arrout] node[lab] {target} (oe1)
  edge[arrout] node[lab] {replaced by} (sp);

\node[iri,below=2.2\vgap of e1] (sd1) {2014-03-11}
  edge[arrin] node[lab] {start date} (e1);
\node[iri,above=2.2\vgap of e1] (ed1) {2018-03-11}
  edge[arrin] node[lab] {end date} (e1);

\node[iri,below=2.2\vgap of e2] (sd2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);
\node[iri,above=2.2\vgap of e2] (ed2) {2010-03-11}
  edge[arrin] node[lab] {end date} (e2);

\node[iri,below=\vgap of oe1] (rl) {Ricardo Lagos}
  edge[arrin,bend right=17] node[lab] {replaces} (e2);
\end{tikzpicture}
\caption{Directed labeled graph reifying the statements of Figure~\ref{fig:mb} \label{fig:delg}}
\end{figure}

A number of graph models have been proposed to capture higher-arity relations more concisely, including property graphs~\cite{FrancisGGLLMPRS18} and RDF*~\cite{Hartig17}. However, both have limitations that render them incapable of modeling the statements shown in Figure~\ref{fig:mb} without resorting to reification~\cite{HoganRRS19}. On the one hand, property graphs allow labels and property--value pairs to be associated with both nodes and edges. For example, the statements of Figure~\ref{fig:mb} can be represented as the property graph:

\begin{center}
\vspace{2pt}
\setlength{\vgap}{1.5cm}
\setlength{\hgap}{1.5cm}
\begin{tikzpicture}

  \node[nrect] (n1) {
   \alt{
       \uri{name} & =\,\uri{"Michelle Bachelet"} } };

  \node[rt] (ln1) at (n1.north) {$n_1$ : \uri{human}};

  \node[nrect,right=\hgap of n1] (n2) {
   \alt{
      \uri{name} & =\,\uri{"President of Chile"} } };

  \node[rt] (ln2) at (n2.north) {$n_2$ : \uri{public office}};

  \draw[arrout,pos=0.5,bend left=25] (ln1) to node[rte,yshift=-0.1cm] (le1)
   {$e_1$ $:$ position held}
  (ln2);

  \node[erect,anchor=south,yshift=-0.5ex] at (le1.north) (e1) {
     \alt{ \uri{start date} & =\,\uri{"11 March 2014"}\\[-0.7em]
           \uri{end date} & =\,\uri{"11 March 2018"}\\[-0.7em]
           \uri{replaces} & =\,\uri{"Sebastián Piñera"}\\[-0.7em]
           \uri{replaced by} & =\,\uri{"Sebastián Piñera"} } };

  \draw[arrout,pos=0.5,bend right=25] (n1) to node[rte,yshift=-0.1cm] (le2) {$e_2$ $:$ position held} (n2);

  \node[erect,anchor=north,yshift=0.5ex] (e2) at (le2.south) {
     \alt{ \uri{start date} & =\,\uri{"11 March 2006"}\\[-0.7em]
           \uri{end date} & =\,\uri{"11 March 2010"}\\[-0.7em]
           \uri{replaces} & =\,\uri{"Ricardo Lagos"}\\[-0.7em]
           \uri{replaced by} & =\,\uri{"Sebastián Piñera"}\\ } };
\end{tikzpicture}
\vspace{2pt}
\end{center}

Though more concise than reification, labels, properties and values are considered to be simple strings, which are disjoint with nodes; for example, \textsf{"Ricardo Lagos"} is neither a node nor a pointer to a node, but a string, which would complicate, for example, querying for the parties of presidents that Michelle Bachelet replaced.

On the other hand, RDF* allows an edge to be a node. For example, the first statement of Figure~\ref{fig:mb} can be represented as follows in RDF*:

\begin{center}
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.9cm}
\vspace{2pt}
\begin{tikzpicture}
\node[iri,anchor=center,minimum width=6.3cm,minimum height=0.7cm,enode] (e1) {};
\node[iri,right=1ex of e1.west,anchor=west] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[lab] {position held} (sp1);

\node[iri,below=\vgap of e1] (mb) {Sebastián Piñera}
  edge[arrin,bend right=40] node[lab,xshift=1ex] {replaces} (e1)
  edge[arrin,bend left=40] node[lab,xshift=-1ex] {replaced by} (e1);

\node[iri,left=\hgap of mb] (ttt) {2014-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,right=\hgap of mb] (ttf) {2018-03-11}
  edge[arrin] node[lab] {end date} (e1);
\end{tikzpicture}
\vspace{2pt}
\end{center}
However,  we can only represent one of the statements (without reification), as we can only have one distinct node per edge; if we add the qualifiers for both statements, then we would not know which start date pairs with which end date, for example.

The domain graph\xspace model allows us to capture higher-arity relations more directly. In Figure \ref{fig:dg} we have one possible representation of the statements from Figure \ref{fig:mb}. We only show edge ids as needed (all edges have ids). We do not use the ``property part" of our data model for external annotation, considering that the elements of Wikidata statements shown can form nodes in the graph itself.

Domain graphs are inspired by \textit{named graphs} in RDF/SPARQL (where named graphs have one triple/edge each). Both domain graphs and named graphs can be represented as quads. However, the edge ids of domain graphs identify each quad, which, as we will discuss in Section~\ref{sec:architecture}, simplifies indexing. Named graphs were proposed to represent multiple RDF graphs for publishing and querying. SPARQL thus uses syntax -- such as \textsf{FROM}, \textsf{FROM NAMED}, \textsf{GRAPH} -- that is unintuitive when querying singleton named graphs representing higher-arity relations. Moreover, SPARQL does not support querying paths that span named graphs; in order to support path queries over singleton named graphs, all edges would need to be duplicated (virtually or physically) into a single graph~\cite{HernandezHK15}. Named graphs (with multiple edges) could be supported in domain graphs using a reserved term \textsf{graph}, and edges of the form $\gamma(e_3) = (e_1,\textsf{graph},g_1)$, $\gamma(e_4) =(e_2,\textsf{graph},g_1)$; optionally, \textit{named domain graphs} could be considered in the future to support multiple domain graphs with quins.

\begin{figure}[t]
\setlength{\vgap}{0.8cm}
\setlength{\hgap}{1.6cm}
\centering
\begin{tikzpicture}
\node[iri,anchor=west,yshift=1ex] (sp1) {Michelle Bachelet};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin,bend left=40] node[enode] (e1) {$e_1:$ position held} (sp1)
  edge[arrin,bend right=40] node[enode] (e2) {$e_2:$  position held} (sp1);

\node[iri,below=\vgap of e1] (ttt) {2014-03-11}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,left=0.5\hgap of sp1] (mb) {Sebastián Piñera}
  edge[arrin,bend right=30] node[lab,xshift=1ex] {replaces} (e1.210)
  edge[arrin,bend right=10] node[lab,xshift=-1ex] {replaced by} (e1.190)
  edge[arrin,bend left=20] node[lab,xshift=-1ex] {replaced by} (e2.170);

\node[iri,right=0.5\hgap of ttt] (ttf) {2018-03-11}
  edge[arrin] node[lab,xshift=1ex] {end date} (e1);

\node[iri,above=\vgap of e2] (ttt2) {2006-03-11}
  edge[arrin] node[lab] {start date} (e2);

\node[iri,left=0.5\hgap of ttt2] (rl) {Ricardo Lagos}
  edge[arrin] node[lab] {replaces} (e2);

\node[iri,right=0.5\hgap of ttt2] (ttf2) {2010-03-11}
  edge[arrin] node[lab,xshift=1ex] {end date} (e2);

\end{tikzpicture}
\caption{Domain graph for Figure~\ref{fig:mb} \label{fig:dg}}
\end{figure}

The idea of assigning ids to edges/triples for similar purposes as described here is a natural one, and not new to this work. \citet{HernandezHK15} explored using singleton named graphs in order to represent Wikidata qualifiers, placing one triple in each named graph, such that the name acts as an id for the triple. In parallel with our work, recently a data model analogous to domain graphs has been independently proposed for use in Amazon Neptune, which the authors call 1G~\cite{LassilaSBBBKKLST}. Their proposal does not discuss a formal definition for the model, nor a query language, storage and indexing, implementation, etc., but the reasoning and justification that they put forward for the model is similar to ours. To the best of our knowledge, our work is the first to describe a query language, storage and indexing schemes, query planner -- and ultimately a fully-fledged graph database engine -- built specifically for this model. Furthermore, with property domain graphs, we support annotation external to the graph, which we believe to be a useful extension that enables better compatibility with property graphs.

Table~\ref{tab:gmodel} summarizes the features that are directly supported by the respective graph models themselves without requiring \textit{reserved terms}, which would include, for example, \textsf{source}, \textsf{label} and \textsf{target} in Figure~\ref{fig:delg} (all features except \textit{External annotation} can be supported in all models with reserved vocabulary). Reserved terms can add indirection to modeling (e.g., reification~\cite{HernandezHK15}), and can clutter the data, necessitating more tuples or higher-arity tuples to store, leading to more joins and/or index permutations. The features are then defined as follows, considering directed (labeled) edges:

\begin{itemize}
\item \textit{Edge type/label}: assign a type or label to an edge.
\item \textit{Node label}: assign labels to nodes.
\item \textit{Edge annotation}: assign property--value pairs to an edge.
\item \textit{Node annotation}: assign property--value pairs to a node.
\item \textit{External annotation}: nodes/edges can be annotated without adding new nodes or edges.
\item \textit{Edge as node}: an edge can be referenced as a node (this allows edges to be connected to nodes of the graph).
\item \textit{Edge as nodes}: a single unique edge can be referenced as multiple nodes.
\item \textit{Nested edge nodes}: an edge involving an edge node can itself be referenced as a node, and so on, recursively.
\item \textit{Graph as node}: a graph can be referenced as a node.
\end{itemize}

Some \nmark's in Table~\ref{tab:gmodel} are more benign than others; for example, \textit{Node label} requires a reserved term (e.g., \textsf{rdf:type}), but no extra tuples; on the other hand, \textit{Edge as node} requires reification, using at least one extra tuple, and at least one reserved term.

Wikidata requires \textit{Edge as nodes} for cases as shown in Figure~\ref{fig:mb} (since values such as \textsf{Ricardo Lagos} are themselves nodes). Only named graphs, domain graphs and property domain graphs can model such examples without reserved terms. Comparing named graphs and domain graphs, the latter sacrifices the ``\textit{Graph as node}'' feature without reserved vocabulary to reduce indexing permutations (discussed in Section~\ref{sec:architecture}). Such a feature is not needed by Wikidata. Property domain graphs further support external annotation, and thus better compatibility with legacy property graphs.

\begin{table}
\caption{The features supported by graph models without reserved terms (NG = Named Graphs, PG = Property Graphs, DG = Domain Graphs, PDG = Property Domain Graphs) \label{tab:gmodel}}
\begin{tabular}{ccccccc}
\toprule
 & RDF & RDF* & NG & PG & DG & PDG \\
\toprule
\textit{Edge type/label} & \ymark & \ymark & \ymark & \ymark & \ymark & \ymark \\
\textit{Node label} & \nmark & \nmark & \nmark & \ymark & \nmark & \ymark \\
\textit{Edge annotation} & \nmark & \ymark & \ymark & \ymark & \ymark & \ymark \\
\textit{Node annotation} & \ymark & \ymark & \ymark & \ymark & \ymark & \ymark \\
\textit{External annotation} & \nmark & \nmark & \nmark & \ymark & \nmark & \ymark \\
\textit{Edge as node} & \nmark & \ymark & \ymark & \nmark & \ymark & \ymark \\
\textit{Edge as nodes} & \nmark & \nmark & \ymark & \nmark & \ymark & \ymark \\
\textit{Nested edge nodes} & \nmark & \ymark & \ymark & \nmark & \ymark & \ymark \\
\textit{Graph as node} & \nmark & \nmark & \ymark & \nmark & \nmark & \nmark \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Features of Graph Query Languages}

A variety of query languages for graphs have been proposed down through the years~\cite{AnglesG08}, including AQL~\cite{ArangoDB} (used by ArangoDB), Cypher~\cite{FrancisGGLLMPRS18} (used by Neo4j~\cite{Webber12}), Gremlin~\cite{Rodriguez15} (used by Amazon Neptune~\cite{AmazonNeptune}, JanusGraph~\cite{JanusGraph}, Neo4j~\cite{Webber12}, OrientDB~\cite{OrientDB}), G-Core~\cite{AnglesABBFGLPPS18}, GSQL~\cite{TigerGraph} (used by TigerGraph~\cite{TigerGraph}) SPARQL~\cite{HarrisS13} (used by various systems~\cite{AliSYHN21}, including Allegrograph~\cite{AllegroGraph}, Amazon Neptune~\cite{AmazonNeptune}, Blazegraph~\cite{ThompsonPC14}, GraphDB~\cite{BishopKOPTV11}, Jena TDB~\cite{JenaTDB}, Stardog~\cite{Stardog} and Virtuoso~\cite{Erling12}), SQL-Match~\cite{OrientDB} (used by OrientDB~\cite{OrientDB}).

While the syntax of these query languages vary widely, they share a large common core in terms of querying primitives. Specifically, all such query languages support different types of \textit{graph patterns} that transform a graph into a relation (aka.\ a table) of results~\cite{AnglesABHRV17}. The simplest form of graph pattern is a \textit{basic graph pattern}, which in its most general form, is a graph pattern structured like the data, but that also allows variables to replace constants. Next we have \textit{navigational graph patterns}, which allow for specifying path expressions that can match arbitrary-length paths in the graphs. We also have \textit{relational graph patterns} which, noting that a graph pattern converts a graph into a relation, allows the use of relational operators to transform and/or combine the results of one or more graph patterns into a single relation. Finally, query languages may support other features, such as \textit{solution modifiers} that order or limit results, convert results back into a graph, etc.

\input{./sections/ql-actual.tex}

\subsection{Domain Graph Queries}

Per our goal of supporting multiple graph models, MillenniumDB aims to support a number of graph query languages, such as those that we previously discussed. However, no existing query language would take full advantage of the property domain graph model defined in the previous section. We have thus implemented a base query language, called DGQL\xspace, which closely resembles Cypher~\cite{FrancisGGLLMPRS18}, but is adapted for the property domain graph model, and adds features of other query languages, such as SPARQL, that are commonly used for querying knowledge graphs like Wikidata~\cite{BonifatiMT20}. Herein we provide a guided tour of the syntax of DGQL\xspace.

A DGQL\xspace query takes the following high-level form:

\begin{dql}
SELECT Variables
MATCH Pattern
WHERE Filters
\end{dql}

\noindent
When evaluated over a property domain graph\xspace, such a query will return a multiset of mappings binding \dqlt{Variables} to database objects (or values) that satisfy the \dqlt{Pattern} specified in the \dqlkw{MATCH} clause and the \dqlt{Filters} specified in the \dqlkw{WHERE} clause.

\paragraph*{Querying objects.} The most basic query will return all the objects (or more precisely, their ids) in our property domain graph\xspace. In MillenniumDB we can achieve this via the following query:

\begin{dql}
SELECT ?x
MATCH (?x)
\end{dql}

\noindent
Of course, one usually wants to select objects with a certain label, or a certain value in a specific property. For instance, if we want to select all people in the property (domain) graph from Figure~\ref{fig:pgmb} with two children, we could do this as follows:

\begin{dql}
SELECT ?x, ?x.gender
MATCH (?x :human { children : "2" })
\end{dql}

\noindent This would return the ids of nodes with label \dqlt{human} and value \dqlt{"2"} for the property \dqlt{children}, along with their associated value for the property \dqlt{gender}, i.e., a single result $\{ \{ \dqlt{?x} \mapsto n_2, \dqlt{?x.gender} \mapsto \dqlt{"male"} \} \}$.
If $n_2$ did not have a gender, we would still want to return the node that makes the match, but signal that the gender is not specified. To do so, we would return  $\{ \{ \dqlt{?x} \mapsto n_2, \dqlt{?x.gender} \mapsto \dqlt{null} \} \}$.

If we wish to specify a range, we can rather use the \dqlkw{WHERE} clause:

\begin{dql}
SELECT ?x, ?x.gender
MATCH (?x :human)
WHERE ?x.children >= "2"
\end{dql}

\noindent which returns two solutions:  $\{ \{ \dqlt{?x} \mapsto n_2, \dqlt{?x.gender} \mapsto \dqlt{"male"} \},$ $\{ \dqlt{?x} \mapsto n_1, \dqlt{?x.gender} \mapsto \dqlt{"female"} \} \}$. If we replaced \dqlt{>=} with \dqlt{==}, the results would be the same as for the previous query.

\paragraph*{Querying edges.} In order to query over edges, we can write the following query, which returns $\gamma$, i.e., the relation $\textsc{DomainGraph}$:

\begin{dql}
SELECT *
MATCH (?x)-[?e TYPE(?t)]->(?y)
\end{dql}

\noindent
The \dqlkw{SELECT} \dqlt{*} operation projects all variables specified in the \dqlkw{MATCH} pattern, while the construct \texttt{(?x)-[?e TYPE(?t)]->(?y)} specifies that we want to connect the object in \texttt{?x} with an object in \texttt{?y}, via an edge with type \texttt{?t} and id \texttt{?e}. This is akin to a query \textsc{DomainGraph}(\texttt{?x,?t,?y,?e}) over the domain graph relation.

We can also restrict which edges are matched. The following query in DGQL\xspace will return ids for edges of type child, where both nodes have the same last name, and the child is not the oldest; it also returns the order of the child:

\begin{dql}
SELECT ?e, ?e.order
MATCH (?x)-[?e child]->(?y)
WHERE (?x.lastname == ?y.lastname) AND (?e.order > "1")
\end{dql}

\noindent
This returns $\{ \{ \dqlt{?e} \mapsto e_2, \dqlt{?e.order} \mapsto \dqlt{2} \} \}$ when evaluated over the graph in Figure~\ref{fig:pgmb}. If we need to query for the second oldest (an equality condition), we could use the syntax \dqlt{(?x)-[?e child \{order : "2"\}]->(?y)} on the edge (or replace \dqlt{(?e.order > "1")} with \dqlt{(?e.order == "1")}). As shown here, the \dqlkw{WHERE} clause may use Boolean combinations. Notice that edge types are written ``as is'', which is in contrast to object labels that are prefixed with the \texttt{:} symbol.

\paragraph*{Querying known objects.} Knowing the id of an object, we might want to query more about it.
For instance, in the domain graph of Figure~\ref{fig:dg} representing statements from Wikidata, we may query for the positions held by Michelle Bachelet as follows:

\begin{dql}
SELECT ?x
MATCH (Michelle Bachelet)-[position held]->(?x)
\end{dql}

\noindent This would return duplicate results $\{ \{ \dqlt{?x} \mapsto \dqlt{President of Chile} \},$  $\{ \dqlt{?x} \mapsto \dqlt{President of Chile} \} \}$ due to the two edges $e_1$ and $e_2$. Recall that for clarity we use human-readable ids, where for Wikidata, the node id \dqlt{Michelle Bachelet} may rather be given as \dqlt{Q320}, and \dqlt{position held} by \dqlt{P39}.

\paragraph*{Path queries.} A key feature of graph databases is their ability to explore paths of arbitrary length. Like SPARQL~\cite{HarrisS13} (but not Cypher\footnote{Of these 2RPQ features, Cypher only supports Kleene star. However, 2RPQs are widely used for querying Wikidata~\cite{BonifatiMT20}, and thus we have prioritized adding this feature. We do not support SPARQL's negated property sets, which are used infrequently~\cite{BonifatiMT20}.}), DGQL\xspace supports two-way regular path queries (2RPQs), which specify regular expressions over edge types, including concatenation (\dqlt{/}), disjunction (\dqlt{|}), inverses (\verb|^|), optional (\dqlt{?}), Kleene star (\dqlt{*}) and Kleene plus (\dqlt{+}). For instance, if we need to find all descendants of people named Alberto, we could use the regular expression \texttt{child+} in the following way:

\begin{dql}
SELECT ?y
MATCH (?x { first name : "Alberto" })=[child+]=>(?y)
\end{dql}

\noindent This returns $\{ \{ \dqlt{?y} \mapsto n_1  \}\}$ over the graph in Figure~\ref{fig:pgmb}, and would include children of $n_1$, and their children, recursively, if present. We use \dqlt{=[]=>} (rather than \dqlt{-[]->}) to signal a path query in DGQL\xspace. If we want to capture more results, we could replace \dqlt{[child+]} with an extended expression like \verb#[(child|^father|^mother)+]# which also traverses backwards along edges of type \dqlt{father} and \dqlt{mother}, and may thus return more results. We can also concatenate paths with $\dqlt{/}$, where the expression \verb#[(father|mother)*/sister]# could find sisters, aunts, grand-aunts, and so forth.

Like Cypher (but not SPARQL), DGQL\xspace can return a single shortest path witnessing the query result via the following construct:

\begin{dql}
SELECT ?y, ?p
MATCH (?x { first name : Alberto })=[?p child+]=>(?y)
\end{dql}

\noindent
The variable \texttt{?p} stores a shortest path connecting each \texttt{Alberto} with each descendant \texttt{?y}. No manipulation of path variables, apart from outputting the result, is currently supported in MillenniumDB, but a full path algebra will be supported in future versions.

\paragraph*{Basic and navigational graph patterns.} Basic graph patterns~\cite{AnglesABHRV17} lie at the core of many graph query languages, including DGQL\xspace. These are graphs following the same structure as the data model, but where variables are allowed in any position. They can also be seen as expressing natural (multi)joins over sets of atomic edge patterns. In DGQL\xspace, they are given in the \dqlkw{MATCH} clause. As a way to illustrate this, the following query finds pairs of nodes who share the same father:

\begin{dql}
SELECT ?x, ?y
MATCH (?x)-[father]->(?z),
      (?y)-[father]->(?z)
\end{dql}

\noindent
We evaluate basic graph patterns under \textit{homomorphism-based semantics}~\cite{AnglesABHRV17}, which allows multiple variables in a single result to map to the same element of the data. If we evaluate this query over Figure~\ref{fig:pgmb}, we would thus get one solution: $\{ \{ \dqlt{?x} \mapsto n_1, \dqlt{?y} \mapsto n_1,  \} \}$.

If we further allow path queries within basic graph patterns, we arrive at \textit{navigational graph patterns}~\cite{AnglesABHRV17}. Suppose we need to find, for example, pairs of nodes that share a common ancestor along the paternal line and held the same position; we could write this as:

\begin{dql}
SELECT ?x, ?y
MATCH (?x)=[father+]=>(?z),
      (?y)=[father+]=>(?z),
      (?x)-[position held]->(?w)
      (?y)-[position held]->(?w)
WHERE ?x != ?y
\end{dql}

\noindent This time we filter results that map \dqlt{?x} and \dqlt{?y} to the same node.

\paragraph*{Taking advantage of the domain graph\xspace model.} The DGQL\xspace query language allows us take full advantage of
domain graphs, by allowing joins between edges, types, etc. To illustrate this, consider the following query, evaluated over the domain graph of Figure~\ref{fig:dg}:

\begin{dql}
SELECT ?x, ?d
MATCH (Michelle Bachelet)-[?e position held]->
                             (President of Chile),
      (?e)-[replaces]->(?x),
      (?e)-[start date]->(?d)
\end{dql}

\noindent The variable \dqlt{?e} invokes a join between an edge and a node, returning two solutions: $\{ \{ \dqlt{?x} \mapsto \dqlt{Ricardo Lagos}, \dqlt{?d} \mapsto \dqlt{2006-03-11} \},$ $\{ \dqlt{?x} \mapsto \dqlt{Sebastián Piñera} , \dqlt{?d} \mapsto \dqlt{2014-03-11} \} \}$. Hence, this query is used to return the list of presidents that were replaced by \dqlt{Michelle Bachelet}, and the dates they were replaced by her.
Illustrating a join on an edge type, consider the following query:

\begin{dql}
SELECT ?x, ?y
MATCH (?x)-[?e TYPE(?t)]->(?y),
      (?t)=[subproperty of*]=>(parent)
\end{dql}

\noindent This query returns all pairs of nodes with an edge whose type is \dqlt{parent}, or a transitive sub-property of  \dqlt{parent}; for example, Wikidata defines \dqlt{father} and \dqlt{mother} to be sub-properties of \dqlt{parent}.

\paragraph*{Optional matches.} DGQL\xspace also supports optional graph patterns, which behave akin to left outer joins. For instance, we may wish to query for presidents of Chile, and if available, the president they replaced, and if further available, the president that the latter president replaced. The following DGQL\xspace query accomplishes this:

\noindent
\begin{dql}
SELECT ?x, ?y, ?z
MATCH (?x)-[?e1 position held]->(President of Chile),
      OPTIONAL {
        (?e1)-[replaces]->(?y)
        OPTIONAL {
          (?y)-[?e2 position held]->(President of Chile),
          (?e2)-[replaces]->(?z)
        }
      }
\end{dql}

\noindent If evaluated on the domain graph of Figure~\ref{fig:dg}, we would get two solutions: $\{ \{ \dqlt{?x} \mapsto \dqlt{Michelle Bachelet}, \dqlt{?y} \mapsto \dqlt{Ricardo Lagos} \},$ $\{ \dqlt{?x} \mapsto \dqlt{Michelle Bachelet}, \dqlt{?y} \mapsto \dqlt{Sebastián Piñera} \} \}$, where in both cases, the variable \dqlt{?z} is left \textit{unbound} as the data is not available for the inner optional graph pattern. As shown, nested optionals are supported, but with the restriction that they form \textit{well-designed patterns} as defined in
\cite{PerezAG09}.

\paragraph*{Limits and ordering.} Some additional operators that MillenniumDB supports are \dqlkw{LIMIT} and \dqlkw{ORDER BY}. These allow us to limit the number of output mappings, and sort the obtained results. For instance, if we need to obtain the ten most recent presidents of Chile, we could accomplish this with the following query:

\begin{dql}
SELECT ?x
MATCH (?x)-[?e position held]->(President of Chile),
      (?e)-[start date]->(?d)
LIMIT 10
ORDER BY DESC (?d)
\end{dql}

\noindent Ordering is always applied before limiting results.

\paragraph{Formal definitions.} At~\cite{extended}, we include an extended version of this paper, which contains a full specification of DGQL\xspace, as well as a formal definition of its semantics. A grammar for generating DGQL\xspace queries is presented in Appendix A of~\cite{extended}. The abstract syntax and formal semantics of the language is given in Appendix B of~\cite{extended}.

\subsection{Semantics of Domain Graph Queries}

Queries in MillenniumDB are
based on an abstract notion of \textit{domain graph query}, which
generalise the types of graph patterns used
by modern graph query languages~\cite{AnglesABHRV17}. This query
abstraction provides modularity in terms of how the database is
constructed, flexibility in terms of what concrete query syntax is
supported, and allows for defining its semantics and studying its
theoretical properties in a clean way.

This section provides an overview of the formal definition of the
MillenniumDB query language
(its complete definition can be found in Appendix
\ref{sec-app-semantics}). From now on, assume a countably infinite
set $\mathsf{Var}$ of variables disjoint with the set of objects $\mathsf{Obj}$.

\textbf{Basic graph patterns.} At the core of domain queries are basic graph patterns.\footnote{Basic graph patterns correspond to conjunctive queries (CQs) over graphs.}
A \emph{basic graph pattern} is defined as a pair $(V,\phi)$ such that $\phi : (\mathsf{Obj} \cup \mathsf{Var}) \rightarrow (\mathsf{Obj} \cup \mathsf{Var}) \times (\mathsf{Obj} \cup \mathsf{Var}) \times (\mathsf{Obj} \cup \mathsf{Var})$ is a partial mapping with a finite domain and $V \subseteq \Var{\phi}$, where $\Var{\phi}$ is the set of variables occurring in the domain or in the range of $\phi$. Thus, $\phi$ can be thought of as a domain graph that allows a variable in any position, together with a set $V$ of output variables (hence the restriction that each variable in $V$ occurs in $\phi$).

The evaluation of a basic graph pattern returns a set of solution
mappings.  A \textit{solution mapping} (or simply \textit{mapping}) is
a partial function $\mu: \mathsf{Var} \rightarrow \mathsf{Obj}$.
The \emph{domain} of a mapping $\mu$, denoted by $\Dom{\mu}$, is the set of variables on which $\mu$ is defined.
Given $v \in \mathsf{Var}$ and $o \in \mathsf{Obj}$, we use $\mu(v) = o$ to denote that $\mu$ maps variable $v$ to object $o$.
Besides, given a set $V$ of variables, the term $\mu_{|_V}$ is used to denote the mapping obtained by restricting $\mu$ to $V$, that is, $\mu_{|_V} :
(V \cap \Dom{\mu}) \to \mathsf{Obj}$ such that $\mu_{|_V}(v) = \mu(v)$ for every $v \in (V \cap \Dom{\mu})$ (notice that $V$ is not assumed to be subset of $\Dom{\mu}$).
Finally, for the sake of presentation, we assume that $\mu(o)=o$, for
all $o\in \mathsf{Obj}$.

The evaluation of a basic graph pattern $B = (V,\phi)$ over a property-domain graph
$G=(O,\gamma)$, denoted by $\semp{B}{G}$, is defined as
  $\semp{B}{G} = \{ \mu_{|_V} \mid \mu \in \semp{\phi}{G}\}$,
where
\begin{multline*}
  \semp{\phi}{G} \ = \ \{ \mu \mid
  \Dom{\mu} = \Var{\phi} \text{ and if } \phi(a) = (a_1,a_2,a_3),\\
  \text{then } \gamma(\mu(a)) = ( \mu(a_1), \mu(a_2), \mu(a_3)  ) \}.
\end{multline*}
For example, consider the basic graph pattern $(V,\phi)$ where $V = \{ v_2, v_4, v_6\}$ and $\phi$ is given by the assignments:
\begin{verse}
$\phi(v_1) = (v_2, \texttt{position held}, \texttt{President of Chile})$,\\
$\phi(v_3) = (v_1, \texttt{start date}, v_4)$, and\\
$\phi(v_5) = (v_1, \texttt{replaces}, v_6)$.
\end{verse}
In Figure \ref{fig:bgp}, we provide a graphical representation of the above graph pattern, and the solution mappings obtained by evaluating the graph pattern over the property domain graph shown in Figure~\ref{fig:dg2}. The solution mappings are presented as a table with columns $v_2$, $v_4$, $v_6$ (i.e. the variables in $V$), and each row represents an individual mapping. Per our definitions, different variables may map to the same object in a single solution. Thus, our notion of evaluation follows a homomorphism-based semantics, similar to query languages such as SPARQL~\cite{AnglesABHRV17}.\footnote{Isomorphism-based semantics~\cite{AnglesABHRV17} -- such as Cypher's no-repeated-edge semantics, which disallows the same solution to use the same edge twice -- can be emulated by filtering solutions after they are generated.}

\begin{figure}[tb]
\setlength{\vgap}{1.2cm}
\setlength{\hgap}{4cm}
\centering

\begin{tikzpicture}

\node[iri,anchor=center,minimum width=7.5cm,minimum height=0.7cm,dashed] (e1) {};

\node[anchor=south east,above left=0.1ex of e1.south east] (e1i) {$v_1$};

\node[iri,right=1ex of e1.west,anchor=west] (sp1) {$v_2$};
\node[iri,right=\hgap of sp1] (ch1) {President of Chile}
  edge[arrin] node[iri,draw=none] {position held} (sp1);

\node[iri,below=\vgap of sp1] (v4) {$v_4$}
  edge[arrin] node[lab] {start date} (e1);

\node[iri,below=\vgap of ch1] (mb) {$v_6$}
  edge[arrin] node[lab,xshift=-1ex] {replaces} (e1);

\end{tikzpicture}

\medskip

\begin{tabular}{lllllll}
\toprule
$v_2$ & $v_4$ & $v_6$ \\
\midrule
\texttt{Michelle bachelet} & \texttt{2006-03-11} & \texttt{Ricardo Lagos} \\
\texttt{Michelle bachelet} & \texttt{2018-03-11} & \texttt{Sebastián Piñera}\\
\bottomrule
\end{tabular}

\caption{Graphical representation of a basic graph pattern (top), and the tabular representation of the solution mappings (bottom) obtained by evaluating the basic graph pattern
  over the property domain graph shown in Figure~\ref{fig:dg2} \label{fig:bgp}.}
\end{figure}

\textbf{Navigational graph patterns.}
A characteristic feature of graph query languages is the ability to match paths of arbitrary length that satisfy certain criteria. We call basic graph patterns enhanced with this feature \textit{navigational graph patterns}, and we define them next.

A popular way to express criteria that paths should match is through regular expressions on their labels, aka.\ \textit{regular path queries} (\textit{rpqs}). More precisely, an \textit{rpq expression} $r$ is defined by the following grammar:
\begin{eqnarray*}
  r & ::= & \varepsilon \ \mid \ o \in \mathsf{Obj} \ \mid \  (r/r) \ \mid \ (r + r) \ \mid \ \inv{r} \ \mid \ r^*.
\end{eqnarray*}
The semantics of an rpq expression $r$ is defined in terms of its
evaluation on a property-domain graph $G$, denoted by $\semp{r}{G}$, which
returns a set of pair of nodes in the graph that are connected by
paths satisfying $r$. More precisely, assuming that $G = (O,\gamma)$,
$o \in \mathsf{Obj}$ and $r,r_1,r_2$ are rpq expressions, we have that:
\begin{eqnarray*}
\semp{\varepsilon}{G} & = & \{(o,o) \mid o\in O\},\\
\semp{o}{G} & = & \{(o_1,o_2) \mid \exists o' \in \mathsf{Obj} : \gamma(o') = (o_1,o,o_2)\},\\
\semp{(r_1 / r_2)}{G} & = & \{ (o_1,o_2) \mid \exists o' \in \mathsf{Obj} : (o_1,o') \in \semp{r_1}{G} \text{ and}\\
&& \phantom{\{ (o_1,o_2) \mid} (o',o_2) \in \semp{r_2}{G}\}, \\
\semp{(r_1 + r_2)}{G} & = & \semp{r_1}{G}\cup \semp{r_2}{G}, \\
\semp{\inv{r}}{G} & = & \{(o_1,o_2) \mid (o_2,o_1)\in \semp{r}{G}\}.
\end{eqnarray*}
Moreover, assuming that $r^1 = r$ and $r^{n+1} = r/r^n$ for every $n \geq 1$, we have that:
\begin{eqnarray*}
  \semp{r^*}{G} & = & \semp{\varepsilon}{G} \, \cup \, \bigcup_{k \geq 1} \semp{r^k}{G}.
\end{eqnarray*}
Other rpq expressions widely used in practice can be defined by
combining the previous operators.
In particular, we have that $r? = \varepsilon + r$ and $r^+ = r/r^*$.

An \textit{path pattern} is a tuple $(a_1,r,a_2)$ such that $a_1, a_2 \in \mathsf{Obj} \cup \mathsf{Var}$ and $r$ is an rpq expression.
As for the case of basic graph patterns, given a path pattern $p$, we use the term $\Var{p}$ to denote the set of variables occurring in $p$.
Moreover, the evaluation of $p = (a_1,r,a_2)$ over a property-domain graph $G$, denoted by $\semp{p}{G}$, is defined as:
\begin{eqnarray*}
  \semp{p}{G} &=& \{ \mu \mid \Dom{\mu} = \Var{p} \text{ and } (\mu(a_1),\mu(a_2)) \in \semp{r}{G} \}.
\end{eqnarray*}

For example, the expression ( \texttt{Michelle Bachelet}, \texttt{replaced by}$^+$, $v$) is a path pattern that returns all the Presidents of Chile after Michelle Bachelet.

Given a set $\psi$ of path patterns, $\Var{\psi}$ also denotes the set of variables occurring in $\psi$, and the evaluation of $\psi$ over a property-domain graph $G$ is defined as:
\begin{multline*}
  \semp{\psi}{G} \ = \ \{ \mu \mid \Dom{\mu} = \Var{\psi} \text{ and}\\ \mu_{|_{\Var{p}}} \in \semp{p}{G} \text{ for each } p \in \psi \}.
\end{multline*}

\begin{definition}
A \emph{navigational graph pattern} is a triple $(V,\phi,\psi)$ where $(V' \subseteq V, \phi)$ is a basic graph pattern, $\psi$ is a set of path patterns and $V \subseteq \Var{\phi} \cup \Var{\psi}$.
The semantics of a navigational graph pattern $N = (V,\phi,\psi)$ is defined as:
\begin{multline*}
   \semp{N}{G} \ = \ \{ \mu_{|_V} \mid \Var{\mu} = \Var{\phi} \cup \Var{\psi},\\ \mu_{|_{\Var{\phi}}} \in \semp{\phi}{G} \ \text{ and } \
    \mu_{|_{\Var{\psi}}} \in \semp{\psi}{G} \}. \qed
  \end{multline*}
\end{definition}
Hence, the result of a navigational graph pattern $N = (V,\phi,\psi)$ is a set of mappings $\mu$ projected onto the set $V$ of output variables, where $\mu$ satisfies the structural restrictions imposed by $\phi$ and the path constrainst imposed by $\psi$.
Notice that multiple rpq expressions can link the same pair of nodes. This is similar to the existential semantics of path queries, as specified in the SPARQL standard \cite{HarrisS13}.

Given a domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, currently we define paths over the directed edge-labelled graph that forms the range of $\gamma$; in other words, we do not allow for matching paths that emanate from an edge object. Such a feature could be considered in the future. We may also consider adding semantics for shortest paths, additional criteria on node or edges in the path, etc.

\textbf{Relational graph patterns.}
As previously discussed (and seen in the example of Figure~\ref{fig:bgp}), graph patterns return relations (tables) as solutions. Thus we can -- and many practical graph query languages do -- use a relational-style algebra to transform and/or combine one or more sets of solution mappings into a final result.

Towards defining this algebra, we need the following terminology.
Two mappings $\mu_1$ and $\mu_2$ are \emph{compatible}, denoted by $\mu_1 \sim \mu_2$, if $\mu_1(v) = \mu_2(v)$ for all variables $v$ which are in both $\Dom{\mu_1}$ and $\Dom{\mu_2}$. If $\mu_1 \sim \mu_2$, then we write $\mu_1 \cup \mu_2$ for the mapping obtained  by extending $\mu_1$ according to $\mu_2$ on all the variables in $\Dom{\mu_2}\setminus\Dom{\mu_1}$.

Given two sets of mappings $\Omega_1$ and $\Omega_2$, the \emph{join}, \emph{union}, \emph{difference} and \emph{left outer join} between $\Omega_1$ and $\Omega_2$ are defined respectively as follows:
\begin{eqnarray*}
\Omega_1 \Join \Omega_2  &=& \{ \mu_1 \cup \mu_2 \mid \mu_1 \in \Omega_1,\, \mu_2 \in \Omega_2 \text{ and } \mu_1 \sim \mu_2 \},\\
\Omega_1 \cup \Omega_2  &=& \{ \mu \mid \mu \in \Omega_1 \text{ or } \mu \in \Omega_2 \},\\
\Omega_1 \setminus \Omega_2  &=& \{ \mu _1 \in \Omega_1 \mid \forall \mu_2 \in \Omega_2 : \mu_1 \sim \mu_2 \text{ does not hold} \},\\
\Omega_1 \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \Omega_2  &=& (\Omega_1 \Join \Omega_2) \cup (\Omega_1 \setminus \Omega_2).
\end{eqnarray*}

With this terminology, a \textit{relational graph pattern} is recursively defined as follows:
\begin{itemize}
\item If $N$ is a navigational graph pattern, then $N$ is also relational graph pattern;
\item If $R_1$ and $R_2$ are relational graph patterns, then $(R_1 ~\operatorname{AND}~ R_2)$ and $(R_1 ~\operatorname{OPT}~ R_2)$ are relational graph patterns.
\end{itemize}

The evaluation of a relational graph pattern $R$ over a property-domain graph $G$, denoted by $\semp{R}{G}$, is recursively defined as follows:
\begin{itemize}
\item if $R$ is a navigational graph pattern $N$, then $\semp{R}{G} = \semp{N}{G}$;
\item if $R$ is $(R_1 ~\operatorname{AND}~ R_2)$ then $\semp{R}{G} = \semp{R_1}{G} \Join \semp{R_2}{G}$;
\item if $R$ is  $(R_1 ~\operatorname{OPT}~ R_2)$ then $\semp{R}{G} = \semp{R_1}{G} \mathbin{\mathbin{\ojoin\mkern-6.6mu\Join}} \semp{R_2}{G}$.
\end{itemize}

\textbf{Selection conditions.}
In addition to match a graph pattern against a property-domain graph, we would like to filter the solutions by imposing selection conditions over the resulting objects (i.e. nodes and edges) and their properties.
In this sense, a \emph{selection condition} is defined recursively as follows:
(a) if $v_1, v_2 \in \mathsf{Var}$ and $o \in \mathsf{Obj}$, $k_1, k_2 \in \mathcal{K}$, $v \in \mathcal{V}$ then $(v_1 = v_2)$, $(v_1 = o)$, $v_1.k_1 = v_2.k_2$ and $v_1.k_1 = v$ are selection conditions; and (b) if $C_1, C_2$ are selection conditions, then $(\neg\ C_1)$, $(C_1 \land C_2)$, $(C_1
\lor C_2)$ are selection conditions.

Given a property-domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, a mapping $\mu$, and a selection condition $C$, we say that $\mu$ satisfies $C$ under $G$, denoted by $\mu \models_G C$, if
\begin{itemize}
\item
$C$ is $({v_1} = {v_2})$, $v_1, v_2 \in \Dom{\mu}$ and $\mu(v_1) = \mu(v_2)$;

\item
$C$ is $({v_1} = o_1)$, $v_1 \in \Dom{\mu}$ and $\mu(v_1) = o_1$;

\item
$C$ is $({v_1.k_1} = {v_2.k_2})$, $v_1, v_2 \in \Dom{\mu}$,
$\texttt{prop}(\mu(v_1),k_1) = \texttt{prop}(\mu(v_2),k_2)$;

\item
$C$ is $({v_1.k_1} = {v})$, $v_1 \in \Dom{\mu}$ and $\texttt{prop}(\mu(v_1),k_1) = v$;

\item
$C$ is $(\neg C_1)$, and it is not the case that $\mu \models_G C_1$;

\item
$C$ is $(C_1 \land C_2)$, $\mu \models_G C_1$ and $\mu \models_G C_2$;

\item
$C$ is $(C_1 \lor C_2)$, $\mu \models_G C_1$ or $\mu \models_G C_2$.
\end{itemize}

\textbf{Solution modifiers.}
We consider an initial set of solution modifiers that allow for applying a final transformation on the solutions generated by a graph pattern.
These include:
\textsf{selection}, which defines a set of elements (variables and properties) to be returned;
\textsf{order by}, which orders the solutions according to a sort criteria; and
\textsf{limit}, which returns the first $n$ mappings in a sequence of solutions.

Let $\mathbf{S}$ be the set of strings, $v \in var$ and $k \in \mathcal{K}$.
A \emph{selection mapping} is a function $\tau : \mathbf{S} \to \mathsf{Obj} \cup \mathcal{V}$.
A \emph{selection element} is either a variable $v$ or an expression $v.k$.
Assume that there is a simple way to transform a selection element into a string in $\mathbf{S}$.
Given a sequence of selection mappings $S$ and an integer $n$, the function $\texttt{limit}(S,n)$ returns the first $n$ elements of $S$ when $n > 0$, and returns $S$ otherwise.

Given a property-domain graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, a mapping $\mu$, and a sequence of selection elements $E$, the function $\texttt{sel}(\mu,E)_G$ returns a selection mapping $\tau$ defined as follows:
if $v \in E$ then $``v" \in \text{dom}(\tau)$ and $\tau(``v") = \mu(v)$;
if $v.k \in E$ then $``v.k" \in \text{dom}(\tau)$ and $\tau(``v.k") = \texttt{prop}(\mu(v),k)$.
Moreover, given a set of solution mappings $\Omega$, the function $\texttt{select}$ returns a set of selection mappings defined as
$\texttt{select}(\Omega,E)_G = \{ \texttt{sel}(\mu,E)_G \mid \mu \in \Omega \}$.

An \emph{order modifier} is a tuple $(e,\beta)$ where $e$ is a selection element and $\beta$ is either \texttt{asc} or \texttt{desc}.
Given a sequence of selection mappings $S$ and an order modifier $o = (e,\beta)$, we say that $S$ satisfies $o$, denoted $S \models o$, if it applies that:
(i) $\beta$ is \texttt{asc} and $S$ satisfies an ascending order with respect to $e$;
or (ii) $\beta$ is \texttt{desc} and $S$ satisfies a descending order with respect to $e$.
Moreover, given a sequence of order modifiers $O = (o_1, \dots, o_n)$, we say that $S$ satisfies $O$, denoted $S \models O$, if it applies that:
(i)  $S \models o_1$ when $n = 1$; or
(ii) $S \models o_1$ and, for every sub-sequence of selection mappings $S' \subseteq S$ it applies that $S' \models (o_2, \dots, o_n)$ such that $\tau_i(e_1) = \tau_j(e_1)$ for any pair of selection mappings $\tau_i, \tau_j \in S'$, with $o_1 = (e_1,\beta_1)$.

\textbf{Graph Query.}
A \textit{graph query} $Q$ is defined as a tuple ($R$, $C$, $E$, $O$, $n$), where $R$ is a relational graph pattern, $C$ is a selection condition, $E$ is a sequence of selection elements, $O = \{ o_1, \dots, o_n \}$ is a sequence of order modifiers, and $n$ is a positive integer. We assume that $R$ is the unique mandatory component.
Given a variable $v \in \text{dom}(R)$, the rest of components have the following expressions by default: $C$ is $v = v$, $E$ is $v$, $O$ is $(v,\texttt{asc})$ and $n = 0$.

The evaluation of $Q$ over $G$ is defined as $\texttt{limit}(S,n)$ where
$S = \texttt{Select}(\Omega,E)_G$,  $S \models O$, and
$\Omega = \{ \mu_{|_V} \mid \mu \in \semp{R}{G} \land \mu \models^G C \}$.

We will assume that every graph query $Q$ = ($R$, $C$, $E$, $O$, $n$) satisfies the following two conditions:
(i)  For every sub-pattern $R' = (R_1 ~\operatorname{OPT}~ R_2)$ of $R$ and for every variable $v$ occurring in $R$, it applies that, if $v$ occurs both inside $R_2$ and outside $R'$, then it also occurs in $R_1$;
(ii) It applies that $\var(C) \subseteq \var(R)$.
Then, we say that $Q$ is a \emph{well-designed graph query}.

It is easy to see that a declarative query expression
\textbf{SELECT} $E$
\textbf{MATCH} $R$
\textbf{WHERE} $C$
\textbf{LIMIT} $n$
\textbf{ORDER BY} $O$, can be transformed into a graph query
($R$, $C$, $E$, $O$, $n$).

\begin{comment}

\subsection{Concrete syntax}

The language supported by MillenniumDB borrows syntax from popular graph query languages SPARQL \cite{HarrisS13} and Cypher \cite{FrancisGGLLMPRS18}. The following is an example of a query in MillenniumDB which finds all people that a person named John knows, and additionally, the city where these people live, if this information is known:

\begin{lstlisting}
SELECT ?y, ?z
MATCH (?x :Person)-[:knows]->(?y :Person)
	OPTIONAL {(?y)-[:livesIn]->(?z :City)}
WHERE ?x.name == "John"
\end{lstlisting}

Intuitively, the \texttt{SELECT} clause specifies which of the matched variables will be returned (\textit{projection}), while the \texttt{MATCH} clause specifies the basic or navigational graph pattern which we will look for in our graph. We can transform or combine the results of one or more \texttt{MATCH} clauses using relational operators to generate a complex graph pattern. In the example, the \texttt{OPTIONAL} pattern invokes a left-outer-join that extends the obtained result with the name of the city only if this information is known (and assigns no value to \texttt{?z} otherwise). Note that \texttt{OPTIONAL} can be interpreted as \texttt{OPTIONAL MATCH}, i.e., it is a binary operator that combines the results of two basic or navigational graph patterns. Finally, the \texttt{WHERE} clause is used to filter result based on a selection, usually by restricting the values of some of the attributes of a matched object.

\begin{figure}
\begin{center}
\begin{lstlisting}
SELECT SelOptions
MATCH  MatchPattern
WHERE  Condition
\end{lstlisting}
\end{center}
\caption{Shape of a query in MillenniumDB}
\label{fig-shape}
\end{figure}

\begin{figure*}
\begin{center}
\fbox{Query elements}
\end{center}
\begin{align*}
\texttt{SelOptions} & :- \ \textcolor{blue}{\texttt{*}} \ | \ v \ | \ v\textcolor{blue}{\textbf{.}}k \ \quad , \quad v\in \mathsf{Var}, k \in \mathcal{K}\\
\texttt{MatchPattern} & :- \ \texttt{GraphPattern}\ |\   \textcolor{red}{\texttt{(}}\ \texttt{MatchPattern}\ \textcolor{red}{\texttt{)}} \ \textcolor{blue}{\texttt{OPTIONAL}} \ \textcolor{blue}{\texttt{\{}} \ \texttt{MatchPattern} \ \textcolor{blue}{\texttt{\}}}\\
\texttt{GraphPattern} & :- \ \texttt{GraphElement} \ | \  \texttt{GraphElement} \textcolor{blue}{\texttt{\textbf{,}}} \  \textcolor{red}{\texttt{(}} \ \texttt{GraphPattern} \ \textcolor{red}{\texttt{)}}\\
\texttt{GraphElement} & :- \ \texttt{NodePattern} \ |\ \texttt{EdgePattern} \ |\ \texttt{PropertyPath} \\
\texttt{Condition} & :- \ \texttt{Comparison} \ | \ \textcolor{blue}{\texttt{(}}\texttt{Condition \textcolor{blue}{AND} Condition}\textcolor{blue}{\texttt{)}} \ | \  \textcolor{blue}{\texttt{(}}\texttt{Condition \textcolor{blue}{OR} Condition}\textcolor{blue}{\texttt{)}}\\
\texttt{Comparison} & :- \ v\textcolor{blue}{\textbf{.}}k \sim val \ | \ v\textcolor{blue}{\textbf{.}}k \sim v'\textcolor{blue}{\textbf{.}}k' \quad , \quad v, v'\in \mathsf{Var}, k, k'\in \mathcal{K}, val \in \mathcal{V}, \sim \in \{\textcolor{blue}{\texttt{==,<=,>=,<,>}}\}
\end{align*}

\begin{center}
\fbox{Nodes, edges and property paths}
\end{center}
\begin{align*}
\texttt{NodePattern} & :- \ \textcolor{blue}{\texttt{(}} \ \texttt{Node}? \ \texttt{Labels}? \ \texttt{Properties}? \ \textcolor{blue}{\texttt{)}}\\
\texttt{Node} & :- \ v \in \mathsf{Var} \ | \ o\in \mathsf{Obj}\\
\texttt{Labels} & :- \ \textcolor{blue}{\textbf{:}}l \ | \ \textcolor{blue}{\textbf{:}}l \ \texttt{Labels} \quad , \quad l\in \mathcal{L}\\
\texttt{Properties} & :- \ \textcolor{blue}{\texttt{\{}} \ \texttt{PropertyList} \ \textcolor{blue}{\texttt{\}}}\\
\texttt{PropertyList} & :- \ k\textcolor{blue}{\textbf{:}}val \ | \ k\textcolor{blue}{\textbf{:}}val\textcolor{blue}{\textbf{,}}\ \texttt{PropertyList}  \quad , \quad k\in \mathcal{K}, val\in \mathcal{V}\\
 & \\
 \texttt{EdgePattern} & :- \ \texttt{NodePattern} \ \texttt{\textcolor{blue}{-}} \texttt{Edge}? \texttt{\textcolor{blue}{>}} \ \texttt{NodePattern} \ |\            \texttt{NodePattern} \ \texttt{\textcolor{blue}{<-}} \texttt{Edge}? \texttt{\textcolor{blue}{}} \ \texttt{NodePattern} \\
\texttt{Edge} & :- \ \texttt{\textcolor{blue}{[}} \ v? \ \texttt{Type}? \ \texttt{Properties}? \ \texttt{\textcolor{blue}{]-}} \quad , \quad v\in \mathsf{Var} \\
 \texttt{Type} & :-\ \textcolor{blue}{\textbf{:}}o \ | \ \textcolor{blue}{\texttt{=TYPE(}}v\textcolor{blue}{\texttt{)}} \quad , \quad o\in \mathsf{Obj}, \ v\in \mathsf{Var}\\
 & \\
 \texttt{PropertyPath} & :- \ \texttt{NodePattern} \ \textcolor{blue}{\texttt{=[}} \ \texttt{pathExp} \ \textcolor{blue}{\texttt{]=>}} \ \texttt{NodePattern} \ |\  \texttt{NodePattern} \ \textcolor{blue}{\texttt{<=}} \textcolor{blue}{[} \ \texttt{pathExp} \ \textcolor{blue}{\texttt{]=}} \ \texttt{NodePattern}\\
 \texttt{pathExp} & :- \ \texttt{\textcolor{blue}{\textbf{:}}}o  \ |\ \textcolor{blue}{\hat{ }} \ \texttt{pathExp} \ |\  \textcolor{blue}{\texttt{(}}\texttt{pathExp\textcolor{blue}{\textbf{/}}pathExp}\textcolor{blue}{\texttt{)}} \ |\ \texttt{pathExp}^{\textcolor{blue}{\texttt{*}}} \ |\\
 & \quad \quad \texttt{pathExp}^{\textcolor{blue}{\texttt{+}}} \ | \  \texttt{pathExp\textcolor{blue}{\{}n\textcolor{blue}{\textbf{,}}m\textcolor{blue}{\}}} \ |\ \textcolor{blue}{\texttt{(}}\texttt{pathExp \textcolor{blue}{|} pathExp}\textcolor{blue}{\texttt{)}} \ |\ \texttt{pathExp}\textcolor{blue}{\texttt{?}} \quad , \quad o\in \mathsf{Obj}, \texttt{n,m}\in \mathbf{N}, \texttt{n}\leq \texttt{m}
\end{align*}
\caption{Specification of query patterns in MilleniumDB. Blue symbols are taken literally. Red brackets in \texttt{MatchPattern} and \texttt{GraphPattern} are grouping specification for unambiguous parsing, and are not specified when writing the query.}
\label{fig-syntax}
\end{figure*}

The general structure of a query in MillenniumDB is defined in Figure \ref{fig-shape}. The syntax of different patters that appear in a query is defined in Figure \ref{fig-syntax}. The workhorse of a query in MillenniumDB is specified in the \texttt{MatchPattern}, which specifies a pattern that needs to be present in our graph. The \texttt{Condition} from the \texttt{WHERE} clause is then applied as a filter to the selected results, and \texttt{SelOptions} specify which data is to be projected out as the final result. To illustrate the use of these components consider following query:

\begin{lstlisting}
SELECT *
MATCH (?x :Person), (?y)-[:knows]->(?z), (?y)=[:follows*]=>(?w)
	OPTIONAL {(?x)-[:knows]->(?w)}
		OPTIONAL {(?x)-[:follows]->(?w)}
WHERE ?x.name == ?y.name
\end{lstlisting}

As specified by Figure \ref{fig-syntax}, the \texttt{MatchPattern} consists of a single \texttt{GraphPattern}, followed by a series of \texttt{OPTIONAL} patterns. The \texttt{GraphPattern} is a series of \texttt{GraphElements} which match a specific node, edge, or a path between nodes, separated by a comma. In the example above, the pattern \texttt{(?x :Person)} is saying that
 we want to match a node with the label \texttt{Person}, and store the result in the variable \texttt{?x}. Similarly, \texttt{(?y)-[:knows]->(?z)} matches an edge between a node stored in the variable \texttt{?y} and a node stored in the variable \texttt{?z}, that has a type \texttt{knows}. Lastly, the pattern \texttt{(?y)=[:follows*]=>(?w)} looks for a pair of nodes, stored in \texttt{?y} and \texttt{?w}, respectively, connected by a path of arbitrary length, where each edge has the type \texttt{follows}. Intuitively, the result of a \texttt{GraphPattern} can be thought as obtained by joining the results of each of its constituent \texttt{GraphElements}.

 Following a \texttt{GraphPattern}, we have a series of \texttt{OPTIONAL} statements. Each of these can again specify a new \{\ \texttt{MatchPattern}\ \}, placed inside braces, and can thus include nested \texttt{OPTIONAL} statements. Several consecutive \texttt{OPTIONAL} statements are parsed as being grouped to the left. We signal this in Figure \ref{fig-syntax} by placing the \texttt{MatchPattern} to the left of an optional into red braces. Similarly, in order to parse them unambiguously, \texttt{GraphPatterns} can be thought as being grouped to the right. That is, the \texttt{MatchPattern} above is grouped as follows:

\begin{lstlisting}
( ( (?x :Person), (?y)-[:knows]->(?z), (?y)=[:follows*]=>(?w) )
	OPTIONAL { (?x)-[:knows]->(?w) } )
		OPTIONAL { (?x)-[:follows]->(?w) }
\end{lstlisting}

The semantics of a query $q$ over a property-domain graph $G$ is defined in terms of mappings, analogously to SPARQL \cite{PerezAG09}, or to homomorphism based semantics of property graphs \cite{AnglesABHRV17}. A \textit{mapping} is a partial function $\mu: \mathsf{Var} \mapsto \mathsf{Obj}$. The \emph{domain} $\Dom{\mu}$ of a mapping $\mu$
is the set of variables on which $\mu$ is defined. Additionally, we will assume that $\mu(o)=o$, for all $o\in \mathsf{Obj}$. We begin by defining the semantics of mappings over each atomic block of a query, that is over a \texttt{NodePattern, EdgePattern} and \texttt{PropertyPath}. Before doing this, notice that each \texttt{NodePattern} can have an explicit identifier (e.g. in \texttt{(Q320 :Person)}), or a variable (e.g. in \texttt{(?x :Person)}), and each \texttt{Edge} can have a variable (e.g. in \texttt{(?x)-[?e :knows]->(?y)}). When these are not present, they are assumed to be existentially quantified; namely, when we write \texttt{(Q320)-[:knows]->()}, we are simply trying to count all the nodes that \texttt{Q320} can reach via an edge of the type \texttt{knows}, and these are ``virtually" assigned to an ``invisible" variable \texttt{?y} inside the empty node pattern\texttt{()}.

When defining the set of variables used in a query $q$, without loss of generality, we will assume that all \texttt{NodePattern} or \texttt{Edge} elements which do not have either an explicit identifier, nor a variable, are assigned a unique fresh variable not used elsewhere in $q$. We call such variables \textit{anonymous variables} of $q$, and denote them $\avar{q}$. All the \textit{explicit variables} of a query $q$, that is, the ones appearing in the definition of $q$, are denoted by $\evar{q}$. The set of variables of $q$, denoted $\qvars{q}$ equals the union $\avar{q} \cup \evar{q}$. We can now define the semantics of  a query $q$ over a property domain-graph $G=(O,\gamma,\texttt{lab},\texttt{prop})$, denoted $\semp{q}{G}$, inductively as the set of all mappings $\mu:\qvars{q}\mapsto \mathsf{Obj}$.

Basically, we do this in the next section in a bit more general setting (optional patterns are more general there).

\riveros{Can we query the domain graph, namely, the `keys' in the function? Also I would write some queries using the running example of Section 2.}

\end{comment}

redpajama_set_name: RedPajamaArXiv