# Fast Dual Simulation Processing of Graph Database Queries
(Supplement)

Stephan Mennicke Jan-Christoph Kalo
Denis Nagel Hermann Kroll Wolf-Tilo Balke Institut für Informationssysteme, TU
Braunschweig, Braunschweig, Germany<EMAIL_ADDRESS>bs.de<EMAIL_ADDRESS>
##  1 Introduction

Mission: ImpossibleOscarawardedB. De
PalmadirectedNewarkborn_inActiongenreGoldfingergenreG.
HamiltondirectedParisborn_inThunderballawardedsequel_ofH.
Saltzmanworked_withSaint Johnborn_inFrom Russia with Loveprequel_ofT.
YoungdirectedBAFTA AwardsawardedD.
Koeppworked_withMortdecaidirected277.140population2.220.445population70.063populationP.R.
Huntworked_with

(a)

directormoviedirectedcoworkerworked_with

(b)

Figure 1: Representation of (a) an Example Graph Database and (b) a Graph
Pattern for $\textbf{(}\mathcal{X}_{1}\textbf{)}$

Extensive knowledge graphs are commonplace backbones in today’s information
infrastructures. Therefore, scalable query processing in graph databases has
sparked a vivid interest in the database community. Already at an early stage
specialized graph query languages such as Sparql, the W3C recommendation for
querying RDF data by SQL-like expressions [30], have been designed. Such
languages provide easy to use yet expressive query capabilities on graph
structures, but need to severely break down structural complexity to allow for
fast query evaluation. Indeed, the evaluation of complex graph patterns is
computationally expensive and thus a variety of implementational avenues have
been proposed [10, 26, 6].

At the heart of Sparql, basic graph patterns (BGPs) form the syntactically
least complex queries. BGPs are simply graphs, and their result sets contain
all graph-homomorphic matches from the graph database instance. Consider query
$\textbf{(}\mathcal{X}_{1}\textbf{)}$, retrieving all persons (cf. variable
?director) who directed at least one movie (?movie) and at some point
collaborated with another person (?coworker):

SELECT ∗ WHERE { ?director directed ?movie . ?director worked_with ?coworker .
} $\textbf{(}\mathcal{X}_{1}\textbf{)}$

$\textbf{(}\mathcal{X}_{1}\textbf{)}$ consists of two triple patterns. The
first requires a directed link between assignments to variables ?director and
?movie while the second asks for ?director to be in a worked_with relationship
with an object matching ?coworker. An evaluation of
$\textbf{(}\mathcal{X}_{1}\textbf{)}$ w. r. t. the database instance depicted
in Fig. 1(a) retrieves the two subgraphs in bold print, including nodes B. De
Palma or G. Hamilton assigned to variable ?director.

Besides full-fledged graph query languages simpler graph pattern matching for
diverse querying tasks raised a growing interest in the database community [9,
14, 13, 11, 19, 21, 12, 25, 32]. Some of these applications employ a form of
simulation graph pattern matching, showing computational advantages over
homomorphic and isomorphic matching. Yet, an in-depth analysis of the
approaches incorporating simulation [9, 21, 25, 32] reveals two shortcomings:

  1. (1)

The algorithms presented are not specifically designed for graph database
querying tasks, in contrast to state-of-the-art graph database management
systems like Virtuoso [10]. Thus, when it comes to performance evaluation of
the simulation algorithms, they are only compared to subgraph isomorphism
algorithms. But as their claimed application area is indeed database querying,
it would only be fair to test these algorithms against established database
systems, too (note that all isomorphism queries can be easily translated to
Sparql queries with conjunction and filter conditions [22]). While performance
evaluations of graph pattern matching papers generally show good evaluation
times, based on our experience we have reason to believe that Virtuoso and
other graph database systems would still perform much better. Therefore, we
have to find out whether we can algorithmically catch up with graph database
systems, since general simulation queries may not be easily expressed in
Sparql [22].

  2. (2)

What all the classical graph pattern matching problems have in common, is that
the input is given as a graph, i. e., there is no possibility of building more
complex patterns as by graph query languages. Hence, we have to study whether
there are major boundaries for an incorporation of graph query operators into
the pattern matching process.

Towards (1) we investigate dual simulation, a version of simulation
specifically developed for the graph data setting [21]. The algorithm
presented by Ma et al.follows a single passive strategy that checks whether
the definition of dual simulation is met resulting in a huge amount of
iterations and influencing the overall runtime (cf. Table 2). Based on a novel
characterization of dual simulation in Sect. 3, we develop a more flexible
algorithmic solution to the dual simulation problem: the fixpoint of a system
of inequalities (SOI) allows for fast dual simulation processing in the graph
query setting. We provide formal proof of the correctness of our algorithm as
well as experimental justification for the performance improvements brought by
our solution. And what is more, our algorithm is also applicable to highly
compressed database formats, as e. g., the BitMat storage structure [5], and
to massive parallelization techniques of bit-matrix operations.

Regarding (2), we also contribute a conservative extension of dual simulation
to work with typical graph query operators, exemplarily taken from Sparql (cf.
Sect. 4). We obtain an overapproximation of the actual Sparql query results
for further inspection, filtering, or actual query processing, depending on
the specific application. These extensions are complete in that none of the
matches under the Sparql semantics is neglected by dual simulation. In
particular, this allows for sound pruning and in any case makes it safe to use
the result for further query processing. Our algorithmic framework remains
efficient, since all the features we need to add are directly implementable
within the SOI solution and do not influence the overall polynomial-time
complexity. We do not only deal with well-designed patterns [28, 5]. Although
well-designed patterns have been of special interest, recent studies show that
non-well-designed patterns cannot be neglected, since they form a sizeable
portion of practical query loads [17]. Therefore, we may expect usage of non-
well-designed patterns in the above-mentioned applications. The advantage of
our extended dual simulation process is that is does not need to tell non-
well-designed patterns apart from well-designed ones.

In Sect. 5, we perform extensive experiments on two large-scale databases.
First, we provide evidence of the runtime improvements over the algorithm by
Ma et al.due to our solution. Second, we step into one possible application,
namely per-query database pruning. More than 95% irrelevant triples are
disqualified by dual simulation processing for all evaluated queries, which is
the reason for improved query evaluation times compared to two state-of-the-
art graph databases Virtuoso [10] and RDFox [26]. Moreover, we observe that
our dual simulation process may directly be incorporated as a pruning
preprocessing step in RDFox. In Sect. 6, we elaborate on related work while we
draw a conclusion in Sect. 7.

##  2 Graphs, Data and Matching

By graphs we refer to edge-labeled directed graphs with a finite set of nodes
$V$, a finite label alphabet $\Sigma$, and a directed labeled edge relation
$E\subseteq V\times\Sigma\times V$. A graph is a triple $G=(V,\Sigma,E)$ of
the aforementioned components. As exemplified in Fig. 1, nodes are depicted as
rounded-corner rectangles (with its identifier/name as centered label) while
edges are represented by directed arrows (with associated labels next to the
arrow) between nodes. We often identify the components of of graphs $G_{\\_}i$
by $V_{\\_}i$ and $E_{\\_}i$ ($i\in\mathbb{N}$). As a matter of simplicity we
assume all graphs to be labeled over a fixed alphabet $\Sigma$. For every
label $a\in\Sigma$, we associate with graphs $G$ two adjacency maps, a forward
map $\mathfrak{F}_{\\_}G^{a}$ and a backward map $\mathfrak{B}_{\\_}G^{a}$ of
$G$. Both mappings associate a subset of nodes with each node $v\in V$, in
case of forward maps, the set of successor nodes, and in case of backward
maps, the set of predecessor nodes of $v$, i. e.,
$\mathfrak{F}_{\\_}G^{a}(v):=\\{w\mid(v,a,w)\in E\\}$ and
$\mathfrak{B}_{\\_}G^{a}(v):=\\{u\mid(u,a,v)\in E\\}$.

In the Resource Description Framework (RDF), the basic ingredients are triples
$(s,p,o)$, describing a relationship ($p$) between two database resources $s$
and $o$. By analogy, $s$, $p$ and $o$ are thought of as subject, predicate and
object. Database resources ($s$ or $o$) stem from two universes: the set of
all objects $\mathcal{O}$, each of which usually referred to by an IRI
(Internationalized Resource Identifier), and the set of literals
$\mathcal{L}$. A literal is an element from an arbitrary data domain, such as
the integers, usually to describe attribute values of objects. Predicates are
also implemented by IRIs, which stem from the universe $\mathcal{P}$. To
simplify the presentation we assume all three universes to be disjoint.
Furthermore, we abstract from the implementation as IRIs and use intuitive
names to identify database objects and predicates (cf. example database in
Fig. 1(a)). RDF allows for generalized triples of type
$\mathcal{O}\times\mathcal{P}\times(\mathcal{O}\cup\mathcal{L})$, sufficient
to formulate interrelations and attributes of objects. Attributes connect
objects with literals, e. g., in Fig. 1(a), the information that Saint John
has 70,063 inhabitants is reflected by the triple $(\texttt{Saint
John},\texttt{population},\texttt{70,063})$. Further note that literals may
only occur in the third component of a triple.

A graph database is a finite instance of all possible triples. We formalize it
as a graph with all objects and literals occurring in triples as the set of
nodes, and all predicates as the alphabet. Handling literals properly leads to
the following divergence from our initial graph model.

######  Definition 1 (Graph Database).

A graph database is a graph
$\textit{DB}=(O_{\\_}\textit{DB},\Sigma,E_{\\_}\textit{DB})$ with a finite set
of database objects and literals
$O_{\\_}\textit{DB}\subset_{\\_}{\textit{fin}}\mathcal{O}\cup\mathcal{L}$, a
finite set of properties $\Sigma\subset_{\\_}{\textit{fin}}\mathcal{P}$, and a
labeled edge relation
$E_{\\_}\textit{DB}\subseteq(O_{\\_}\textit{DB}\cap\mathcal{O})\times\Sigma\times
O_{\\_}\textit{DB}$. ■

All the notions for graphs carry over to graph databases.

placedirector1born_indirector2born_incoworkerworked_withmoviedirected

(a)

placedirectorborn_incoworkerworked_withmoviedirected

(b)

Figure 2: Two Graph Patterns

A dual simulation [21] between two graphs $G_{\\_}1,G_{\\_}2$ is a binary
relation $S\subseteq V_{\\_}1\times V_{\\_}2$ such that for each pair of nodes
$(v_{\\_}1,v_{\\_}2)\in S$, all incoming and outgoing edges of $v_{\\_}1$ are
also featured by $v_{\\_}2$ and the adjacent nodes of $v_{\\_}1$ and
$v_{\\_}2$, ordered in pairs, belong to $S$. For a dual simulation $S$,
$(v_{\\_}1,v_{\\_}2)\in S$ means that $v_{\\_}2$ dual simulates $v_{\\_}1$. As
an example consider the graphs depicted in Fig. 2(a) and (b) as $G_{\\_}1$ and
$G_{\\_}2$. A dual simulation relates the nodes with the same label, e. g.,
place in $G_{\\_}2$ dual simulates node place in $G_{\\_}1$, and both nodes
director1 and director2 in $G_{\\_}1$ relate to director in $G_{\\_}2$, as in

${\left\\{\begin{array}[]{l}(\texttt{place},\texttt{place}),(\texttt{director1},\texttt{director}),\\\
(\texttt{director2},\texttt{director}),(\texttt{movie},\texttt{movie}),\\\
(\texttt{coworker},\texttt{coworker})\end{array}\right\\}}$ (1)

Node director2 features two outgoing edges, one labeled born_in to node place,
the other labeled directed to movie. Node director in $G_{\\_}2$ dual
simulates director2, since it has an outgoing edge with label born_in to node
place, and place in $G_{\\_}2$ dual simulates place in $G_{\\_}1$. The same
argument holds for node movie. By following through the argumentation for
every pair of nodes in (1), it can be shown that $G_{\\_}2$ indeed dual
simulates $G_{\\_}1$ under the indicated dual simulation (1). Observe that a
single node, e. g., director, may dual simulate more than one node.

Table 1: Summary of Symbols

$G=(V,\Sigma,E)$ | edge-labeled directed graph
---|---
$\mathfrak{F}_{\\_}G^{a}$, $\mathfrak{B}_{\\_}G^{a}$ | forward/backward map for label $a$ in $G$
$\textit{DB}=(O_{\\_}\textit{DB},\Sigma,E_{\\_}\textit{DB})$ | graph database
$\chi_{\\_}S:V_{\\_}1\to 2^{V_{\\_}2}$ | characteristic function for relation $S\subseteq V_{\\_}1\times V_{\\_}2$
$\mathcal{Q}$, $\mathcal{Q}_{1}$, $\mathcal{Q}_{2}$ |  Sparql queries
$\llbracket\mathcal{Q}\rrbracket_{\\_}\textit{DB}$ | set of matches due to Sparql semantics
$\mu:\textit{vars}(\mathcal{Q})\to O_{\\_}\textit{DB}$ | match to query $\mathcal{Q}$ in DB
$\mu_{\\_}1\mathbin{\rightleftharpoons}\mu_{\\_}2$ | compatibility predicate between $\mu_{\\_}1$ and $\mu_{\\_}2$
$\mathcal{E}=(\mathtt{Var},\mathtt{Eq})$ | system of inequalities

######  Definition 2 (Dual Simulation [21]).

Let $G_{\\_}i=(V_{\\_}i,\Sigma,E_{\\_}i)$ ($i=1,2$) be two graphs. A relation
$S\subseteq V_{\\_}1\times V_{\\_}2$ is a dual simulation between $G_{\\_}1$
and $G_{\\_}2$ iff for each $(v_{\\_}1,v_{\\_}2)\in S$,

  1. (i)

$(v_{\\_}1,a,w_{\\_}1)\in E_{\\_}1$ implies $\exists w_{\\_}2\in
V_{\\_}2:(v_{\\_}2,a,w_{\\_}2)\in E_{\\_}2$ and $(w_{\\_}1,w_{\\_}2)\in S$,

  2. (ii)

$(u_{\\_}1,a,v_{\\_}1)\in E_{\\_}1$ implies $\exists u_{\\_}2\in
V_{\\_}2:(u_{\\_}2,a,v_{\\_}2)\in E_{\\_}2$ and $(u_{\\_}1,u_{\\_}2)\in S$.

We say that $G_{\\_}2$ dual simulates $G_{\\_}1$ iff there is a non-empty dual
simulation between $G_{\\_}1$ and $G_{\\_}2$. ■

Note that the trivial dual simulation $S=\emptyset$ would certify that any two
graphs are dual simulating each other. In a graph query setting we call
$G_{\\_}1$ pattern graph and $G_{\\_}2$ is the graph database. Reconsider the
introductory example query $\textbf{(}\mathcal{X}_{1}\textbf{)}$. The graph in
Fig. 2(b) dual simulates the graph representation of
$\textbf{(}\mathcal{X}_{1}\textbf{)}$ in Fig. 1(b). A dual simulation is
realized by ignoring node place. Hence, not every node of the graph database
has to participate in a dual simulation relation. Furthermore, the graph in
Fig. 2(a) neither dual simulates nor is dual simulated by the graph in Fig.
1(b). Regarding the graph database depicted in Fig. 1(a) and the graph
representation of $\textbf{(}\mathcal{X}_{1}\textbf{)}$ in Fig. 1(b), dual
simulation (2) turns out to be particularly useful in the upcoming sections.

${\left\\{\begin{array}[]{l}(\texttt{director},\texttt{B. De
Palma}),(\texttt{director},\texttt{G. Hamilton}),\\\
(\texttt{coworker},\texttt{D. Koepp}),(\texttt{coworker},\texttt{H.
Saltzman}),\\\ (\texttt{movie},\texttt{Mission:
Impossible}),(\texttt{movie},\texttt{Goldfinger})\end{array}\right\\}}$ (2)

It comprises exactly the nodes of the two subgraphs from the result set of
$\textbf{(}\mathcal{X}_{1}\textbf{)}$. Instead of considering the full graph
database (i. e., Fig. 1(a)) we would ignore all graph database nodes but those
mentioned by dual simulation (2). Computing this dual simulation is possible
in Ptime [21], as opposed to Sparql query evaluation being Pspace-complete
[28, 31]. How to perform this computation fast is subject to the next section.
We apply dual simulation principles to Sparql for query processing in Sect. 4.

##  3 A Perspective on Dual Simulation

At the end of the last section we have seen a dual simulation between a graph
representation of a Sparql query (BGP $\textbf{(}\mathcal{X}_{1}\textbf{)}$)
and a graph database (Fig. 1(a)), covering all nodes relevant for computing
the result set of $\textbf{(}\mathcal{X}_{1}\textbf{)}$. In Sect. 4 we show
that the existence of such a dual simulation is not coincidental, since every
match for Sparql queries like $\textbf{(}\mathcal{X}_{1}\textbf{)}$ is
contained in a maximal dual simulation (cf. Theorem 1). A dual simulation $S$
is maximal iff there is no dual simulation $S^{\prime}$ such that $S\subset
S^{\prime}$. Fortunately, there is exactly one such maximal dual simulation
between any two graphs, the largest dual simulation.

######  Proposition 1 (Proposition 2.1 [21]).

For any two graphs $G_{\\_}1$ and $G_{\\_}2$, there is a unique largest dual
simulation $S_{\\_}{\max}$ between $G_{\\_}1$ and $G_{\\_}2$, i. e., for any
dual simulation $S$ between $G_{\\_}1$ and $G_{\\_}2$, $S\subseteq
S_{\\_}{\max}$.

The proof exploits the fact that, whenever we have two dual simulations
$S_{\\_}1$ and $S_{\\_}2$ between the graphs, their union $S_{\\_}1\cup
S_{\\_}2$ is a dual simulation. Incorporating dual simulation in graph pattern
matching or Sparql query processing amounts to computing the largest dual
simulation between an appropriate representation of the query and the graph
database. All graph database nodes captured by the largest dual simulation are
relevant for answering the query.

Computing the largest (dual) simulation is the algorithmic basis for solving
the graph (dual) simulation problem, i. e., given two graphs $G_{\\_}1$ and
$G_{\\_}2$, does $G_{\\_}2$ (dual) simulate $G_{\\_}1$. To the best of our
knowledge, all published algorithms for this task [21, 18] work on the same
principles. Starting with the largest possible relation between the two node
sets, the algorithms incrementally disqualify pairs of nodes violating Def. 2.
The procedures are guaranteed to terminate when no pair of nodes can be
disqualified anymore. Although the standard algorithms share an
$\mathcal{O}(|V_{\\_}2|^{3})$ data (runtime) complexity, we observed that
these algorithms only allow for the naive evaluation strategy described above,
which have originally been invented for comparing graphs of unknown sizes with
each other. The aforementioned data complexity follows from generalizing the
existing algorithms [18] and [21] to edge-labeled graphs (cf. Sect. 3.3 for a
detailed derivation). This inflexibility generates high query running times
that would easily be outperformed by state-of-the-art query evaluation, e. g.,
by Virtuoso (cf. Sect. 5).

Subsequently, we develop a novel solution which computes the largest dual
simulation and exploits run-time analytics to dynamically adapt evaluation
strategies. Key to our solution is the reformulation of the algorithm as a
system of inequalities which allows for two dynamically interchangeable
evaluation strategies. Although the worst-case complexity of our solution
remains unaltered (cf. Sect. 3.3), compared to the existing algorithms, we
gain a degree of freedom allowing for a systematic reduction of iterations to
eventually reach the largest dual simulation (cf. Sect. 3.3). As we show in
Sect. 5 the new procedure shows extremely low computation times, a solid basis
for query processing. Our solution is engineered in three steps. First, we
define a set of inequalities equivalent to the coinductive definition of dual
simulation in Def. 2. We further show how to derive a fast implementation
based on bit-vectors and bit-matrices. Last, we provide a discussion on
optimizations realized in our software prototype111available at GitHub
https://github.com/ifis-tu-bs/sparqlSim.

###  3.1 Groundwork

Any binary relation $R\subseteq A\times B$, over sets $A$ and $B$, has a
characteristic function $\chi_{\\_}R:A\to 2^{B}$ with $\chi_{\\_}R(a):=\\{b\in
B\mid(a,b)\in R\\}$. For a dual simulation $S$ between graphs $G_{\\_}1$ and
$G_{\\_}2$, $\chi_{\\_}S$ associates with each node $v\in V_{\\_}1$ a set of
dual simulating nodes $\chi_{\\_}S(v)\subseteq V_{\\_}2$. Consider an edge
$(v,a,w)$ of $G_{\\_}1$ and node $v^{\prime}\in\chi_{\\_}S(v)$. If $S$ is a
dual simulation, then for $\chi_{\\_}S$ we derive

$\exists w^{\prime}:(v^{\prime},a,w^{\prime})\in
E_{\\_}2\text{~{}and~{}}w^{\prime}\in\chi_{\\_}S(w)\text{.}$ (3)

The problem with (3) is that there may be many $w^{\prime}$ qualifying for
$(v^{\prime},a,w^{\prime})\in E_{\\_}2$ but $w^{\prime}\notin\chi_{\\_}S(w)$.
We pursue to have a single operation allowing us to quickly verify the
existence of $w^{\prime}$. Therefore, recall that for any graph, here graph
database $G_{\\_}2$, we have a forward adjacency map
$\mathfrak{F}_{\\_}{G_{\\_}2}^{a}$ for each label $a\in\Sigma$ (cf. Sect. 2).
By exploiting these maps we prove existence of a $w^{\prime}$ in (3) simply by
intersecting the row of $v^{\prime}$ in $\mathfrak{F}_{\\_}{G_{\\_}2}^{a}$ and
the nodes simulating $w$, i. e.,

$\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})\cap\chi_{\\_}S(w)\neq\emptyset\text{.}$
(4)

(4) still only checks for one pair of nodes $(v,v^{\prime})$. Combining this
equation for all $v^{\prime}\in\chi_{\\_}S(v)$ yields

$\begin{array}[]{rlcl}\bigwedge_{\\_}{v^{\prime}\in\chi_{\\_}S(v)}&\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})\cap\chi_{\\_}S(w)\neq\emptyset\text{.}\end{array}$
(5)

The same encoding applies to Def. 2(ii), this time using the backward map,

$\begin{array}[]{rlcl}\bigwedge_{\\_}{w^{\prime}\in\chi_{\\_}S(w)}&\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})\cap\chi_{\\_}S(v)\neq\emptyset\text{.}\end{array}$
(6)

The combination of both equations (5) and (6) yields two inequalities
equivalent to the definition of dual simulation and the key for our efficient
implementation.

######  Lemma 1.

Let $G_{\\_}1=(V_{\\_}1,\Sigma,E_{\\_}1)$ and
$G_{\\_}2=(V_{\\_}2,\Sigma,E_{\\_}2)$ be graphs with $(v,a,w)\in E_{\\_}1$.
For a binary relation $S\subseteq V_{\\_}1\times V_{\\_}2$ satisfying (5) and
(6), it holds that (7) is satisfied.

$\begin{array}[]{rcrclcl}(i)&&\chi_{\\_}S(w)&\subseteq&\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}S(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})&&\text{and}\\\
(ii)&&\chi_{\\_}S(v)&\subseteq&\bigcup_{\\_}{w^{\prime}\in\chi_{\\_}S(w)}\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})\end{array}$
(7)

######  Proof:

W. l. o. g., we show inequality (i) only. Inequality (ii) is completely
analogous. Towards a contradiction assume
$\chi_{\\_}S(w)\not\subseteq\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}S(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})$.
Hence, there is a $w^{\prime}\in\chi_{\\_}S(w)$ such that for each
$v^{\prime}\in\chi_{\\_}S(v)$,
$w^{\prime}\notin\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})$, i. e.,
$(v^{\prime},a,w^{\prime})\notin E_{\\_}2$. As a consequence, $\chi_{\\_}S(v)$
and $\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})$ are disjoint for each
$v^{\prime}\in\chi_{\\_}S(v)$, contradicting our assumption that (6) holds.
Therefore, such a $w^{\prime}$ cannot exist, allowing to conclude that
$\chi_{\\_}S(w)\subseteq\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}S(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})$.
□

Phrased differently, dual simulations $S$ satisfy (7) for every edge $(v,a,w)$
of $G_{\\_}1$. Lemma 1 reveals an important observation that, to the best of
our knowledge, has not been published so far: The reason why (7) holds is that
part (ii) prevents part (i) from getting ill-formed and vice versa. The fast
algorithm we obtain here is a consequence of the duality in dual simulation.
Conversely, every solution to (7) is a dual simulation.

######  Proposition 2.

Let $G_{\\_}1$ and $G_{\\_}2$ be graphs. $S\subseteq V_{\\_}1\times V_{\\_}2$
is a dual simulation between $G_{\\_}1$ and $G_{\\_}2$ iff for every edge
$(v,a,w)\in E_{\\_}1$, (7) holds for $S$.

######  Proof:

The implication, i. e., a dual simulation $S$ satisfies (7), is analogous to
the proof of Lemma 1. Therefore, assume that one of the inequalities is not
satisfied and conclude the assumption that $S$ is a dual simulation is
violated.

Conversely, assume we have $S\subseteq V_{\\_}1\times V_{\\_}2$ such that (7)
holds for every $(v,a,w)\in E_{\\_}1$. We prove $S$ to be a dual simulation.
Let $(v,v^{\prime})\in S$, i. e., $v^{\prime}\in\chi_{\\_}S(v)$, and
$(v,a,w)\in E_{\\_}1$. We need to show that there is a $w^{\prime}$ such that
$(v^{\prime},a,w^{\prime})\in E_{\\_}2$ and $(w,w^{\prime})\in S$. From
(7)(ii) we get that for some $w^{\prime}\in\chi_{\\_}S(w)$ we have that
$v^{\prime}\in\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})$. This $w^{\prime}$
completes the proof, since (1) from
$v^{\prime}\in\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})$ follows
$(v^{\prime},a,w^{\prime})\in E_{\\_}2$ and (2) from
$w^{\prime}\in\chi_{\\_}S(w)$, we get that $(w,w^{\prime})\in S$. Case
$(u,a,v)\in E_{\\_}1$ is completely analogous. □

Hence, (7) characterizes dual simulations, and we can use it to compute the
largest dual simulation. The algorithm works as follows. We begin with
$S_{\\_}0:=V_{\\_}1\times V_{\\_}2$. For each edge of $G_{\\_}1$, check
whether (7) is satisfied by $S_{\\_}0$. Assume (7)(i) fails for an edge
$(v,a,w)$. Then, $S_{\\_}{1}$ is computed by
$\chi_{\\_}{S_{\\_}{1}}(u):=\chi_{\\_}{S_{\\_}0}(u)$ for $u\neq w$ and
$\chi_{\\_}{S_{\\_}{1}}(w):=\chi_{\\_}{S_{\\_}0}(w)\cap\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}{S_{\\_}0}(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})$.
We get rid of all non-simulating nodes of $w$ relative to $S_{\\_}0$ in a
single iteration. This procedure is repeated for $S_{\\_}1,S_{\\_}2,\ldots$
until we reach an $S_{\\_}k$ satisfying (7) for every edge of $G_{\\_}1$.

Even though we maintain the Ptime nature of other algorithms (cf. Sect. 3.3),
we still miss a way to quickly compute
$\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}{S}(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})$
and access $\chi_{\\_}S(v)$. Therefore, the forthcoming implementation works
with bit-representations of $\chi_{\\_}S(v)$ and
$\mathfrak{F}_{\\_}{G_{\\_}2}^{a},\mathfrak{B}_{\\_}{G_{\\_}2}^{a}$, paving
the way for optimization in time- and space-consumption (e. g., [6]). In that
setting we derive a system of inequalities (SOI) from Prop. 2, for which dual
simulations $S$ serve as valid assignments.

###  3.2 Engineering

Our goal is to obtain the facilities for achieving a fast implementation of
dual simulation processing. Recall that we need to compute the largest dual
simulation and we do this by a system of inequalities according to (7). The
challenge is to find a way to quickly compute the unions

$\begin{array}[]{ccc}\bigcup_{\\_}{v^{\prime}\in\chi_{\\_}S(v)}\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(v^{\prime})&\text{and}&\bigcup_{\\_}{w^{\prime}\in\chi_{\\_}S(w)}\mathfrak{B}_{\\_}{G_{\\_}2}^{a}(w^{\prime})\text{.}\end{array}$
(8)

Combinations of vectors and matrices, especially when encoding information
only bit-wise, promise fast computations. Hence, we interpret the adjacency
maps of $G_{\\_}2$ as adjacency bit matrices. Reconsider the graph in Fig.
2(a). For label born_in, this graph provides two adjacency matrices,

$\begin{array}[]{ccc}\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(a)}^{\texttt{born\\_in}}=\left(\begin{array}[]{ccccc}0&0&0&0&0\\\
1&0&0&0&0\\\ 1&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\end{array}\right)&\text{and}&\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(a)}^{\texttt{born\\_in}}=\left(\begin{array}[]{ccccc}0&1&1&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\end{array}\right)\text{.}\end{array}$

Here, we assume the set of nodes of graphs to be ordered by some pre-defined
index, e. g., $v_{\\_}1=\texttt{place}$, $v_{\\_}2=\texttt{director1}$,
$v_{\\_}3=\texttt{director2}$, $v_{\\_}4=\texttt{coworker}$, and
$v_{\\_}5=\texttt{movie}$. Also, $\chi_{\\_}S$ can be seen as a matrix with
$k=|V_{\\_}{1}|$ rows, one for each node of pattern graph $G_{\\_}1$, and
$n=|V_{\\_}{2}|$ columns. Specifically, for a dual simulation $S$ a $1$ in
position $(i,j)$ means that the $i^{\text{th}}$ node of the pattern graph is
simulated by the $j^{\text{th}}$ node of the graph database. For ease of
presentation, the pattern graph $G_{\\_}1$ does not have an indexed node set.
Consequently, for node $v$ of the pattern graph and $j\leq n$, we access the
$j^{\text{th}}$ component of $v$’s row by $\chi_{\\_}S(v,j)$. By
$\chi_{\\_}S(v)$ we get $v$’s row vector sliced from matrix $\chi_{\\_}S$. The
desired unions (8) are now achieved by bit-matrix multiplications222For vector
$\mathfrak{v}$ and matrix $\mathfrak{A}$,
$\mathfrak{v}\times_{\\_}b\mathfrak{A}=\mathfrak{w}$ where $\mathfrak{w}(j)=1$
iff there is an $i$ such that $\mathfrak{v}(i)=1$ and $\mathfrak{A}(i,j)=1$.
(symbol $\times_{\\_}b$),

$\begin{array}[]{ccc}\chi_{\\_}S(v)\times_{\\_}b\mathfrak{F}_{\\_}{G_{\\_}2}^{a}&\text{and}&\chi_{\\_}S(w)\times_{\\_}b\mathfrak{B}_{\\_}{G_{\\_}2}^{a}\text{.}\end{array}$
(9)

The result of the multiplication is the reachable nodes via $a$-labeled
(forward) edges from any simulating node of $v$. For instance, assume that
$\chi_{\\_}S(\texttt{director})=\chi_{\\_}S(\texttt{place})=(1,1,1,1,1)$.
Then, for edge $(\texttt{director},\texttt{born\\_in},\texttt{place})$:

$\begin{array}[]{lclcl}\chi_{\\_}S(\texttt{director})&\times_{\\_}b&\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(a)}^{\texttt{born\\_in}}&=&(1,0,0,0,0)=r_{\\_}1\\\
\chi_{\\_}S(\texttt{place})&\times_{\\_}b&\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(a)}^{\texttt{born\\_in}}&=&(0,1,1,0,0)=r_{\\_}2\text{.}\end{array}$

Hence, $r_{\\_}1$ reveals that only node place is reachable via forward edges
labeled born_in. Conversely, by born_in-labeled backward edges we reach
director1 as well as director2. The results are used to update a given
relation $S$, according to (7). In the example above, $r_{\\_}2$ shows that
$\chi_{\\_}S(\texttt{director})\neq(1,1,1,1,1)$, since the only reachable
nodes are director1 and director2. Thus,
$\chi_{\\_}S(\texttt{director})=(1,1,1,1,1)\not\leq(0,1,1,0,0)=r_{\\_}2$, but
according to Prop. 2, a dual simulation $S$ satisfies (7), now possible to
formulate by bit-matrix operations for edges $(v,a,w)\in E_{\\_}{G_{\\_}1}$,

$\begin{array}[]{rclclcl}\chi_{\\_}S(w)&\leq&\chi_{\\_}S(v)&\times_{\\_}b&\mathfrak{F}_{\\_}{G_{\\_}2}^{a}&&\text{and}\\\
\chi_{\\_}S(v)&\leq&\chi_{\\_}S(w)&\times_{\\_}b&\mathfrak{B}_{\\_}{G_{\\_}2}^{a}\text{.}\end{array}$
(10)

After observing the wrong value of $\chi_{\\_}S(\texttt{director})$ we update
relation $S$ to $S^{\prime}$ by
$\chi_{\\_}{S^{\prime}}(\texttt{director}):=\chi_{\\_}S(\texttt{director})\wedge
r_{\\_}2$ (component-wise conjunction of the two vectors). This enables us to
give an algorithm for the dual simulation problem between two graphs
$G_{\\_}1$ and $G_{\\_}2$ as a solution of the system of inequalities
$\mathcal{E}=(\mathsf{Var},\mathsf{Eq})$, where every node $v$ of the graph
pattern is a variable, i. e., $\mathsf{Var}:=V_{\\_}{1}$, and $\mathsf{Eq}$
contains for each pattern edge $(v,a,w)\in E_{\\_}{1}$, the following
equations:

$\begin{array}[]{rclcrcl}w&\leq&v\times_{\\_}b\mathfrak{F}_{\\_}{G_{\\_}2}^{a}&\text{and}&v&\leq&w\times_{\\_}b\mathfrak{B}_{\\_}{G_{\\_}2}^{a}\text{.}\end{array}$
(11)

Fig. 3 shows the SOI for computing dual simulations for the graphs in Fig.
2(a) and (b). Assignments to the variables $v,w\in\mathsf{Var}$ are relations
$S\subseteq V_{\\_}{1}\times V_{\\_}{2}$. The algorithm computing the largest
dual simulation between $G_{\\_}1$ and $G_{\\_}2$ proceeds as follows.

  1. 1.

Set $S_{\\_}0:=V_{\\_}{1}\times V_{\\_}{2}$ and all inequalities in
$\mathsf{Eq}$ unstable.

  2. 2.

Let $S_{\\_}i$ be the current candidate relation. Pick any unstable inequality
$\epsilon\in\mathsf{Eq}$

    1. (a)

If $S_{\\_}i$ is valid for $\epsilon$, set $\epsilon$ stable and continue with
(2).

    2. (b)

If $S_{\\_}i$ is invalid for inequality $\epsilon=v\leq
w\times_{\\_}b\mathfrak{A}$ (for
$\mathfrak{A}\in\\{\mathfrak{F}_{\\_}{G_{\\_}2}^{a},\mathfrak{B}_{\\_}{G_{\\_}2}^{a}\mid
a\in\Sigma\\}$), then $\chi_{\\_}{S_{\\_}i}(w)\times_{\\_}b\mathfrak{A}=r$ and
$\chi_{\\_}S(v)\not\leq r$. Update $S_{\\_}i$ to $S_{\\_}{i+1}$ such that

$\chi_{\\_}{S_{\\_}{i+1}}(x):=\left\\{\begin{array}[]{lcl}\chi_{\\_}{S_{\\_}i}(x)\wedge
r&&\text{if }x=v\text{ and}\\\
\chi_{\\_}{S_{\\_}i}(x)&&\text{otherwise.}\end{array}\right.$

Furthermore, every inequality $y\leq v\times\mathfrak{A}\in\mathtt{Eq}$ are
reset to unstable. Mark $\epsilon$ stable and continue with (2).

The initialization step of $S_{\\_}0$ can also be expressed in terms of
inequalities, in that for every pattern node $v$, we add (12) to the set of
inequalities $\mathsf{Eq}$.

$\begin{array}[]{rcl}v&\leq&\underline{\bf{1}}\end{array}$ (12)

$\underline{\bf{1}}$ is the vector containing a $1$ in every component. The
dual simulation given by (1) is the largest solution to the SOI in Fig. 3,
thus it constitutes the largest dual simulation.

$\begin{array}[]{rcl}\texttt{place}&\leq&\texttt{director1}\times_{\\_}b\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{born\\_in}}\\\
\texttt{place}&\leq&\texttt{director2}\times_{\\_}b\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{born\\_in}}\\\
\texttt{director1}&\leq&\texttt{place}\times_{\\_}b\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{born\\_in}}\\\
\texttt{director2}&\leq&\texttt{place}\times_{\\_}b\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{born\\_in}}\\\
\texttt{coworker}&\leq&\texttt{director1}\times_{\\_}b\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{worked\\_with}}\\\
\texttt{director1}&\leq&\texttt{coworker}\times_{\\_}b\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{worked\\_with}}\\\
\texttt{movie}&\leq&\texttt{director2}\times_{\\_}b\mathfrak{F}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{directed}}\\\
\texttt{director2}&\leq&\texttt{movie}\times_{\\_}b\mathfrak{B}_{\\_}{Fig.~{}\ref{fig:dualsim-
patterns}(b)}^{\texttt{directed}}\end{array}$

Figure 3: System of Inequalities Characterizing Largest Dual Simulation
between Fig. 2(a) and (b)

###  3.3 Complexity and Optimization

Initializing $S_{\\_}0$ takes time $\mathcal{O}(|V_{\\_}1|\cdot|V_{\\_}2|)$ in
a naive implementation. We execute step 2) at most $|V_{\\_}1|\cdot|V_{\\_}2|$
times, since there are $|V_{\\_}1|$ pattern nodes for which at most
$|V_{\\_}2|$ data nodes can be disqualified. Let $\epsilon=v\leq
w\times_{\\_}b\mathfrak{A}$ be in $\mathsf{Eq}$ and $S_{\\_}i$ the current
candidate relation. Computing
$r=\chi_{\\_}{S_{\\_}i}(w)\times_{\\_}b\mathfrak{A}$ is in
$\mathcal{O}(|V_{\\_}2|^{2})$ time. By further regarding the intersection
$\chi_{\\_}{S_{\\_}i}(v)\wedge r$, we obtain an overall time complexity of
$\mathcal{O}(|V_{\\_}2|^{2}+|V_{\\_}2|)=\mathcal{O}(|V_{\\_}2|^{2})$ for
updating $S_{\\_}i$ to $S_{\\_}{i+1}$ which validates $\epsilon$. For every
edge in $G_{\\_}1$ we have two equations in $\mathsf{Eq}$, i. e.,
$|\mathsf{Eq}|=\mathcal{O}(|E_{\\_}1|)$. Thus, assuming pattern $G_{\\_}1$ and
data graph $G_{\\_}2$ as input, our algorithm has a combined complexity of
$\mathcal{O}((|V_{\\_}1|\cdot|V_{\\_}2|)\cdot|E_{\\_}1|\cdot|V_{\\_}2|^{2})$.
In terms of data complexity we have a worst-case runtime of
$\mathcal{O}(|V_{\\_}2|^{3})$, virtually the same complexity as of any other
dual simulation algorithm.

The acquired combined complexity of our solution is higher than that of an
algorithm leveraging by Henzinger et al.’s so-called HHK algorithm, being in
$\mathcal{O}(mn)$ time. Note that HHK assumes a single node-labeled graph (i.
e., no labels on the edges) $G=(V,E)$ and $|V|=n<m=|E|$ ($m\leq n^{2}$). Dual
simulation requires the execution of HHK two times, which leaves the overall
complexity invariant. However, considering a separation into pattern and data
graph as well as adding edge labels does have an effect on the resulting HHK
adaptation. Separating pattern $G_{\\_}1=(V_{\\_}1,E_{\\_}1)$ from data graph
$G_{\\_}2=(V_{\\_}2,E_{\\_}2)$ yields an overall combined complexity of
$O(|E_{\\_}2|\cdot|V_{\\_}2|)$, i. e., the runtime complexity solely depends
on the data graph $G_{\\_}2$. The crux of HHK is an additional data structure
which tracks for each pattern node $v$, the set of adjacent data nodes from
which the simulating nodes of $v$ are unreachable. These are the definite
nodes that cannot simulate the respective adjacent nodes. The maintenance of
these removal sets is the key component in the complexity analysis [18].
Remarkably, combined and data complexity are equal for HHK for unlabeled
graphs. If, additionally, edge labels are considered, the runtime estimation
alters at least to $O(|\Sigma(G_{\\_}1)|\cdot|V_{\\_}2|^{3})$, where
$\Sigma(G_{\\_}1)$ denotes the set of actually used labels in $G_{\\_}1$. This
is because every update of a removal set requires only a single adjacency
matrix of size $O(|V_{\\_}2|^{2})$. However, for every label on the incident
edge of a node, there is a different removal set to maintain.

Due to the graph query setting, there is no difference in worst-case data
complexity between HHK and our solution. In fact, the algorithm of Ma et al.
[21], adjusted to labeled graphs, enjoys the same data complexity, i. e.,
$\mathcal{O}(|V_{\\_}2|^{3})$. As a consequence, we formulate the specific
data complexity hypothesis for dual simulation graph query processing: The
real computation times of naive implementations of HHK and the algorithm of Ma
et al.should show no significant differences in the (labeled) graph query
setting. We provide experimental evidence for this hypothesis in Sect. 5.
Although the existence of suitable algorithmic tweaks for any of the
abovementioned algorithms is not deniable, we advertise our algorithmic
framework for its separation into algorithmic representation as a system of
inequalities and evaluation algorithm, externally adaptable by static and
dynamic heuristics.

An immediate optimization is given by altering the initial relation
$S_{\\_}0$, syntactically exploiting that for a variable/node $v$ in
$G_{\\_}1$, candidate nodes are only those supporting incident edges of $v$.
Therefore, let us denote by $\mathfrak{f}_{\\_}{G_{\\_}2}^{a}$ the bit-vector
that summarizes the rows of $\mathfrak{F}_{\\_}{G_{\\_}2}^{a}$ in that
$\mathfrak{f}_{\\_}{G_{\\_}2}^{a}(i)=1$ if there is a $j$ with
$\mathfrak{F}_{\\_}{G_{\\_}2}^{a}(i,j)=1$, and
$\mathfrak{f}_{\\_}{G_{\\_}2}^{a}(i)=0$ otherwise. In the same lines,
$\mathfrak{b}_{\\_}{G_{\\_}2}^{a}$ is defined as the summary of
$\mathfrak{B}_{\\_}{G_{\\_}2}^{a}$. Then for each variable/node $v$ in
$G_{\\_}1$, we replace inequality (12) by

$\begin{array}[]{rcl}v&\leq&\bigwedge_{\\_}{(v,a,w)\in
E_{\\_}1}\mathfrak{f}_{\\_}{G_{\\_}2}^{a}\wedge\bigwedge_{\\_}{(u,a,v)\in
E_{\\_}1}\mathfrak{b}_{\\_}{G_{\\_}1}^{a}\text{.}\end{array}$ (13)

Our characterization of dual simulation and its implementation open up dynamic
evaluation strategies for the constructed SOI. First, the order in which the
equations are evaluated has an impact on the overall runtime. For our
experiments, we have chosen an order that aims at shrinking the simulation as
early as possible, e. g., by preferring inequalities with matrix components
having more empty columns, which indicates sparsity of the respective
matrices. Second, the computation of $r$ (step 2b of the algorithm) may be
performed row-wise or column-wise. Again, we follow the strategy of fewer
iterations, i. e., in $v\leq w\times_{\\_}b\mathfrak{A}$ we choose a row-wise
evaluation if and only if $\chi_{\\_}S(w)$ has fewer bits set than
$\chi_{\\_}S(v)$. As it turns out (cf. Sect. 5.3) there is not a single
heuristic that fits all input patterns and databases.

Our proof-of-concept implementation keeps $G_{\\_}2$ in memory by its
adjacency matrices. $G_{\\_}1$ is stored by its system of inequalities,
including $\mathcal{O}(|V_{\\_}1|)$ bit-vectors representing $\chi_{\\_}S$.
For every graph pattern $G_{\\_}1$, it suffices to load those adjacency
matrices that are needed the pattern. Hence, the worst-case memory consumption
is determined by the graph pattern and by the adjacency matrix requiring the
most memory. Note that due to bit-vector storage techniques, such as gap-
length encoding, the worst memory consumption might not occur with the label
storing the most bits. Combined with the memory-economical implementation by
Atre et al. [6, 5] we are quite optimistic that our implementation may
directly be used within the preprocessing step of the BitMat tool set. Our
dual simulation processing applied to Sparql queries yields decent pruning
factors (cf. Sect. 5), significantly improving upon those reported by Atre
[5].

##  4 Dual Simulation for Sparql

Having clarified the foundational and algorithmic aspects of dual simulations
we now approach an actual query language, namely Sparql. We choose Sparql for
its high-quality standardization by the W3C [30] and its extensive formal
treatment, e. g., [28, 31, 3, 4]. Although Sparql 1.1 has been around for some
time, the fundamental properties of the query language remain the same as for
Sparql 1.0. We are aware of the recent report on the semantic foundation of
the Neo4J query language Cypher [15], and confident about the wider
applicability of the forthcoming techniques to this language. Subsequently,
for Sparql’s least complex construct we canonically obtain dual simulation
processing respecting all matches any Sparql query processor would find. We
further discuss Sparql’s join operators. For each query language feature we
obtain a soundness result guaranteeing that the original Sparql matches are
preserved for further processing.

###  4.1 Basic Graph Patterns

As for RDF, triple patterns are first-class citizens of Sparql. For the
presentation of the upcoming material, we assume subject and object of a
triple $t=(s,p,o)$ to be variables from an infinite domain of variables
$\mathcal{V}$, ranging over by
$\mathtt{v},\mathtt{v_{\\_}1},\mathtt{v_{\\_}2},\ldots$. A variable
$\mathtt{v_{\\_}1}$ is usually introduced by a leading question mark, i.
e.,?$\mathtt{v_{\\_}1}$ (cf. $\textbf{(}\mathcal{X}_{1}\textbf{)}$). In formal
notation, however, we drop this syntactic convention and write
$\mathtt{v_{\\_}1}$.

Querying a graph database
$\textit{DB}=(O_{\\_}\textit{DB},\Sigma,E_{\\_}\textit{DB})$ yields a set of
partial mappings from the set of variables to actual database objects. For
instance, the single triple pattern
$t=(\mathtt{v_{\\_}1},\texttt{population},\mathtt{v_{\\_}2})$ gives rise to a
match identifying $\mathtt{v_{\\_}1}$ with node Saint Join and
$\mathtt{v_{\\_}2}$ with 70.063 (cf. Fig. 1(a)). By $\textit{vars}(t)$ we
denote the set of variables occurring in triple $t$, i. e.,
$\textit{vars}(t)=\\{\mathtt{v_{\\_}1},\mathtt{v_{\\_}2}\\}$ for the
abovementioned $t$. A candidate in DB is a partial function
$\mu:\mathcal{V}\to O_{\\_}\textit{DB}$. $\textit{dom}(\mu)$ denotes the set
of variables for which candidate $\mu$ is defined. A candidate $\mu$ is a
match for triple $t$ in DB iff $\textit{dom}(\mu)=\textit{vars}(t)$ and,
assuming $t=(\mathtt{v_{\\_}1},a,\mathtt{v_{\\_}2})$,
$(\mu(\mathtt{v_{\\_}1}),a,\mu(\mathtt{v_{\\_}2}))\in E_{\\_}\textit{DB}$,
abbreviated by $\mu(t)\in\textit{DB}$.

We call sets of triple patterns $\mathbb{G}$ basic graph patterns (BGPs).
Function vars and thereupon the notion of matches extend to BGPs by
$\textit{vars}(\mathbb{G})=\bigcup_{\\_}{t\in\mathbb{G}}\textit{vars}(t)$, and
$\mu$ is a match for $\mathbb{G}$ iff $\mu$ is a match for all triples
$t\in\mathbb{G}$. The result set
$\llbracket\mathbb{G}\rrbracket_{\\_}\textit{DB}$ for $\mathbb{G}$ w. r. t. DB
contains all matches for $\mathbb{G}$ in DB. Every BGP $\mathbb{G}$ can be
seen as a graph $G(\mathbb{G})=(V_{\\_}{\mathbb{G}},\Sigma,\mathbb{G})$ by
taking the set of variables occurring in $\mathbb{G}$ as set of nodes, i. e.,
$V_{\\_}{\mathbb{G}}:=\\{\mathtt{v},\mathtt{w}\mid(\mathtt{v},a,\mathtt{w})\in\mathbb{G}\\}$.
The graph in Fig. 1(b) represents such a conversion of of query
$\textbf{(}\mathcal{X}_{1}\textbf{)}$.

For dual simulation processing of a BGP $\mathbb{G}$ w. r. t. DB, we compute
the largest dual simulation between $G(\mathbb{G})$ and DB. This procedure is
sound in that every match $\mu$ for $\mathbb{G}$ in DB is a dual simulation
and therefore must be contained in the largest dual simulation.

######  Lemma 2.

Let DB be a graph database and $\mathbb{G}$ be a BGP. Each
$\mu\in\llbracket\mathbb{G}\rrbracket_{\\_}\textit{DB}$ is a dual simulation
between $G(\mathbb{G})$ and DB.

######  Proof:

We show that $\mu$ is a dual simulation between $G(\mathbb{G})$ and DB. Let
$(\mathtt{v},o)\in\mu$, i. e., $\mu(\mathtt{v})=o$, and let $t\in\mathbb{G}$
such that $\mathtt{v}\in\textit{vars}(t)$. There are two cases to distinguish,
for some $a\in\Sigma$ and $\mathtt{w},\mathtt{u}\in\textit{vars}(\mathbb{G})$,
(a) $t=(\mathtt{v},a,\mathtt{w})$and  (b) $t=(\mathtt{u},a,\mathtt{v})$.
Since case (b) is completely analogous, we consider only (a). As $\mu$ is a
match for $\mathbb{G}$, it is a match for $t$, i. e., there is exactly one
$o^{\prime}=\mu(\mathtt{w})$ and $(o,a,o^{\prime})\in E_{\\_}\textit{DB}$.
Hence, $o^{\prime}$ meets the requirements of Def. 2(i). □

The nodes disqualified by the largest dual simulation are irrelevant for any
further query processing, obeying the original Sparql semantics.

######  Theorem 1.

Let DB be a graph database, $\mathbb{G}$ a BGP and $S$ the largest dual
simulation between $G(\mathbb{G})$ and DB. For each database node $o\in
O_{\\_}\textit{DB}$ such that there are
$\mathtt{v}\in\textit{vars}(\mathbb{G})$ and
$\mu\in\llbracket\mathbb{G}\rrbracket_{\\_}\textit{DB}$ with
$\mu(\mathtt{v})=o$, it holds that $(\mathtt{v},o)\in S$.

######  Proof:

Towards a contradiction, assume there is a database node $o$ relevant to match
variable $\mathtt{v}$ by
$\mu\in\llbracket\mathbb{G}\rrbracket_{\\_}\textit{DB}$ with
$(\mathtt{v},o)\notin S$. But then $S\cup\mu$ is a dual simulation larger than
$S$, contradicting the assumption that $S$ is the largest one. □

vwknowsknows

(a)

$p_{\\_}2$$p_{\\_}1$knowsknows$p_{\\_}3$knowsknows$p_{\\_}4$knowsknows

(b)

Figure 4: (a) Graph Pattern $P$ and (b) Graph Database $K$, an example adapted
from Ma et al. [21]

Unfortunately, the converse, i. e., irrelevant nodes for BGP result sets are
ruled out by the largest dual simulation, does not hold in general. Consider
the example graphs $P$ and $K$ depicted in Fig. 4(a) and (b). The largest dual
simulation between $P$ and $K$ includes node $p_{\\_}4$ which is, however, not
belonging to any match for the respective BGP. The reason why $p_{\\_}4$ must
not be disqualified for variable/node $\mathtt{v}$ is that nodes $p_{\\_}1$
and $p_{\\_}3$ distribute the obligations for simulating variable/node
$\mathtt{w}$. Informally, $p_{\\_}1$ knows $p_{\\_}4$ via $p_{\\_}2$ and
$p_{\\_}3$, although $p_{\\_}1$ and $p_{\\_}4$ do not have a direct link to
one another. Non-transitive relationships sometimes appear transitive under
dual simulation. As long as acyclic queries are concerned, our process is also
sound.

We compute the largest dual simulation by the largest solution of the SOI
constructed from $G(\mathbb{G})$ (cf. Sect. 3). From Theorem 1 we learn the
desirable property for systems of inequalities $\mathcal{E}$ of any query
$\mathcal{Q}$, that we must not remove nodes from the database important for
any further processing of matches. We call this property soundness of
$\mathcal{E}$ w. r. t. $\mathcal{Q}$.

######  Definition 3.

Let DB be a graph database, $\mathcal{Q}$ a Sparql query and $\mathcal{E}$ any
SOI representation of $\mathcal{Q}$ with solutions
$S\subseteq\textit{vars}(\mathcal{Q})\times O_{\\_}\textit{DB}$. $\mathcal{E}$
is sound w. r. t. $\mathcal{Q}$ iff for the largest solution $S$ of
$\mathcal{E}$, it holds that if $\mu(v)=o$ for some
$v\in\textit{vars}(\mathcal{Q})$ and
$\mu\in\llbracket\mathcal{Q}\rrbracket_{\\_}\textit{DB}$, then $(v,o)\in S$. ■

###  4.2 Advanced Graph Patterns

BGPs, and Sparql queries in general, may be combined by operators, further
restricting and linking the sets of matches. This subsection is devoted to
applying dual simulation principles to queries with $\mathbin{\text{UNION}}$\-
and $\mathbin{\text{AND}}$-operators. The $\mathbin{\text{AND}}$-operator is
best characterized by relational inner-joins of the results of two queries.

The $\mathbin{\text{UNION}}$-operator is the least invasive operator. It
combines any two queries $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$ to query
$\mathcal{Q}_{1}\mathbin{\text{UNION}}\mathcal{Q}_{2}$. The result set is the
union of the result sets of the constituent queries, i. e.,
$\llbracket\mathcal{Q}_{1}\mathbin{\text{UNION}}\mathcal{Q}_{2}\rrbracket_{\\_}{\textit{DB}}:=\llbracket\mathcal{Q}_{1}\rrbracket_{\\_}\textit{DB}\cup\llbracket\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}$.
It is well-known that any Sparql query may be rewritten as the union of
finitely many union-free queries. A Sparql query $\mathcal{Q}$ is union-free
if the $\mathbin{\text{UNION}}$-operator does not occur in $\mathcal{Q}$.

######  Proposition 3 (Proposition 3.8 [28]).

Let $\mathcal{Q}$ be a Sparql query. Then there are union-free Sparql queries
$\mathcal{Q}_{1},\mathcal{Q}_{2},\ldots,\mathcal{Q}_{k}$ ($k\in\mathbb{N}$)
such that $\mathcal{Q}$ is equivalent to
$\mathcal{Q}^{\prime}=\mathcal{Q}_{1}\mathbin{\text{UNION}}\mathcal{Q}_{2}\mathbin{\text{UNION}}\ldots\mathbin{\text{UNION}}\mathcal{Q}_{k}$,
i. e.,
$\llbracket\mathcal{Q}\rrbracket_{\\_}\textit{DB}=\llbracket\mathcal{Q}^{\prime}\rrbracket_{\\_}\textit{DB}$.

The construction of $\mathcal{Q}^{\prime}$ follows similar principles as
constructing the DNF (disjunctive normal form) in propositional logic. In
consequence, the result set of $\mathcal{Q}$ is the union of the result sets
of all the $\mathcal{Q}_{i}$ ($1\leq i\leq k$). Instead of $\mathcal{Q}$ we
may process each union-free part of $\mathcal{Q}$ individually and later
combine their results. Henceforth, we assume every query to be union-free.

While Sparql’s disjunction unifies the result sets of the constituents,
conjunction unifies compatible results, i. e., those results agreeing upon
shared variables. Matches $\mu_{\\_}1$ and $\mu_{\\_}2$ are compatible,
denoted $\mu_{\\_}1\mathbin{\rightleftharpoons}\mu_{\\_}2$, if for all
$v\in\textit{dom}(\mu_{\\_}1)\cap\textit{dom}(\mu_{\\_}2)$ ($v$ shared by
$\mu_{\\_}1$ and $\mu_{\\_}2$), $\mu_{\\_}1(v)=\mu_{\\_}2(v)$. The conjunction
of two queries $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$ is the query
$\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$. As an example, the
Sparql representation of the graph pattern in Fig. 4(a) may be described as
the conjunction of two BGPs,
$\mathbb{G}_{\\_}1=\\{(\mathtt{v},\texttt{knows},\mathtt{w})\\}$ and
$\mathbb{G}_{\\_}2=\\{(\mathtt{w},\texttt{knows},\mathtt{v})\\}$. The
semantics of conjunctions is defined by

$\llbracket\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}:=\\{\mu_{\\_}1\cup\mu_{\\_}2\mid\mu_{\\_}i\in\llbracket\mathcal{Q}_{i}\rrbracket_{\\_}\textit{DB}\wedge\mu_{\\_}1\mathbin{\rightleftharpoons}\mu_{\\_}2\\}$.

For example, in the database in Fig. 4(b), queries $\mathbb{G}_{\\_}i$ from
above enjoy matches $\mu_{\\_}i$ ($i=1,2$) with
$\mu_{\\_}1(\mathtt{v})=\mu_{\\_}2(\mathtt{v})=p_{\\_}1$ and
$\mu_{\\_}1(\mathtt{w})=\mu_{\\_}2(\mathtt{w})=p_{\\_}2$. These matches are
compatible, thus
$(\mu_{\\_}1\cup\mu_{\\_}2)\in\llbracket\mathbb{G}_{\\_}1\mathbin{\text{AND}}\mathbb{G}_{\\_}2\rrbracket_{\\_}\textit{DB}$.
In contrast, $\mu_{\\_}1$ from before and $\mu_{\\_}3$ with
$\mu_{\\_}3(\texttt{w})=p_{\\_}2$ and $\mu_{\\_}3(\texttt{v})=p_{\\_}3$
constitute incompatible matches, thus
$(\mu_{\\_}1\cup\mu_{\\_}3)\notin\llbracket\mathbb{G}_{\\_}1\mathbin{\text{AND}}\mathbb{G}_{\\_}2\rrbracket_{\\_}\textit{DB}$.

Regarding our dual simulation process, for conjunctions
$\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$, we create the systems of
inequalities for $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$ separately, denoted
by $\mathcal{E}(\mathcal{Q}_{1})$ and $\mathcal{E}(\mathcal{Q}_{2})$. Recall
that the variables of both queries directly refer to variables occurring in
$\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$, respectively. The semantics of
conjunctions requires matches to queries $\mathcal{Q}_{1}$ and
$\mathcal{Q}_{2}$ to be compatible. In consequence, assignments to common
variables must be identical. This may be achieved by simply unifying the
systems of inequalities of both queries. The following lemma defines the sound
system of inequalities.

######  Lemma 3.

Let DB be a graph database and $\mathcal{Q}_{1},\mathcal{Q}_{2}$ BGPs or
conjunctions with sound systems of inequalities
$\mathcal{E}(\mathcal{Q}_{1})=(\mathtt{Var}_{\\_}1,\mathtt{Eq}_{\\_}1)$ and
$\mathcal{E}(\mathcal{Q}_{2})=(\mathtt{Var}_{\\_}2,\mathtt{Eq}_{\\_}2)$. Then
$\mathcal{E}=(\mathtt{Var}_{\\_}1\cup\mathtt{Var}_{\\_}2,\mathtt{Eq}_{\\_}1\cup\mathtt{Eq}_{\\_}2)$
is sound for $\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$.

######  Proof:

Let
$\mu\in\llbracket\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}$.
It holds that $\mu=\mu_{\\_}1\cup\mu_{\\_}2$ for compatible
$\mu_{\\_}i\in\llbracket\mathcal{Q}_{i}\rrbracket_{\\_}\textit{DB}$ ($i=1,2$).
Let $v\in\textit{vars}(\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2})$
with $\mu(v)=o$. We need to show that the largest solution $S$ of
$\mathcal{E}$ contains $(v,o)$. In case
$v\in\textit{vars}(\mathcal{Q}_{1})\cap\textit{vars}(\mathcal{Q}_{2})$, it
holds that $\mu_{\\_}1(v)=\mu_{\\_}2(v)=o$. Hence, the largest solutions
$S_{\\_}i$ of $\mathcal{E}(\mathcal{Q}_{i})$ ($i=1,2$) contain $(v,o)$, i. e.,
$(v,o)\in S_{\\_}1\cap S_{\\_}2$, because $\mathcal{E}(\mathcal{Q}_{i})$ are
sound. It remains to be shown that $S_{\\_}1\cap S_{\\_}2\subseteq S$. Let
$(v,o)\in S_{\\_}1\cap S_{\\_}2$. By construction, any
$\epsilon\in\mathtt{Eq}$ either comes from $\mathtt{Eq}_{\\_}1$ or
$\mathtt{Eq}_{\\_}2$, and since $(v,o)\in S_{\\_}1\cap S_{\\_}2$, $(v,o)$
cannot contradict $\epsilon$. Thus, $(v,o)$ belongs to the largest solution
$S$.

In the other case we have
$v\in\textit{vars}(\mathcal{Q}_{i})\setminus\textit{vars}(\mathcal{Q}_{j})$
($i,j=1,2$ and $i\neq j$). Of course $(v,o)\in S_{\\_}i$. The only way
$(v,o)\notin S$ holds is if there is a shared variable $w$ that is connected
to $v$, via one or more triple patterns, and every possible assignment to $w$
disagrees with $S_{\\_}2$. However, there is at least one object $S_{\\_}1$
and $S_{\\_}2$ have to agree upon for $w$, because $\mu_{\\_}1$ and
$\mu_{\\_}2$ are compatible assignments. Hence the assumption leads to a
contradiction and $(v,o)\in S$. □

###  4.3 Optional Patterns

The last syntactic construct of Sparql for which we provide a sound dual
simulation procedure is that of optional patterns. While, in terms of
complexity, it is the most involved Sparql operator [31], our procedure needs
rather small adjustments. Reconsider our introductory query
$\textbf{(}\mathcal{X}_{1}\textbf{)}$, where we asked for directors and their
coworkers. If we are not sure whether every director has a person listed they
worked with, then we may put this information in an optional pattern, yielding
query $\textbf{(}\mathcal{X}_{2}\textbf{)}$.

SELECT ∗ WHERE { ?director directed ?movie . OPTIONAL { ?director worked_with
?coworker . } }

$\textbf{(}\mathcal{X}_{2}\textbf{)}$

Optional patterns are left-outer joins in the relational model, i. e., matches
to $\textbf{(}\mathcal{X}_{2}\textbf{)}$ definitely assign nodes from the
database to variable ?director and ?movie, but to variable ?coworker only if
there is one. Regarding the graph database in Fig. 1(a), we obtain all bold
subgraphs, as before, and additionally the semi-thick subgraphs (with D. Koepp
and T. Young as ?director). In general, for queries $\mathcal{Q}_{1}$ and
$\mathcal{Q}_{2}$, the result set of
$\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$ is contained in the
result set of the optional pattern
$\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$. Additionally, all
matches to $\mathcal{Q}_{1}$ that have no compatible matches to
$\mathcal{Q}_{2}$ are matches, i. e.,

$\begin{array}[]{rcl}\llbracket\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}&:=&\llbracket\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}\cup\\\
&&\\{\mu\in\llbracket\mathcal{Q}_{1}\rrbracket_{\\_}\textit{DB}\mid\not\exists\mu^{\prime}\in\llbracket\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}:\mu\mathbin{\rightleftharpoons}\mu^{\prime}\\}\text{.}\end{array}$

In $\textbf{(}\mathcal{X}_{2}\textbf{)}$, variable ?director occurs in two
different roles. First, the optional pattern mandates variable ?director to
feature triples with label directed. Second, triples labeled worked_with are
only optional. These two roles must be reflected by our SOI representation of
$\textbf{(}\mathcal{X}_{2}\textbf{)}$ by including two copies of that
variable, $\texttt{?director}_{\\_}m$ (mandatory) and
$\texttt{?director}_{\\_}o$ (optional) with the property that a solution $S$
in variable $\texttt{?director}_{\\_}o$ must not exceed $S$ in variable
$\texttt{?director}_{\\_}m$. In other words, there is no database node
matching $\texttt{director}_{\\_}o$ that does not match
$\texttt{?director}_{\\_}m$. This is expressed by inequality

$\texttt{?director}_{\\_}o\leq\texttt{?director}_{\\_}m\text{.}$ (14)

To faithfully describe such dependencies, we need to distinguish optional
variable occurrences from mandatory ones, based the formal query syntax.

The query language $\mathcal{S}$ comprises union-free Sparql queries with
$\mathbin{\text{AND}}$ and $\mathbin{\text{OPTIONAL}}$ operators, as the
following grammar describes:

$\begin{array}[]{rcc|c|c}\mathcal{Q}&::=&\mathbb{G}&\mathcal{Q}\mathbin{\text{AND}}\mathcal{Q}&\mathcal{Q}\mathbin{\text{OPTIONAL}}\mathcal{Q}\end{array}$

where $\mathbb{G}$ ranges over by BGPs. Queries in $\mathcal{S}$ range over by
$\mathcal{Q},\mathcal{Q}_{1},\mathcal{Q}_{2},\ldots$. As observed above, we
need to consider mandatory and optional variable occurrences. Function
$\mathit{mand}$ maps queries $\mathcal{Q}$ from $\mathcal{S}$ to the set of
variables that occur as mandatory in $\mathcal{Q}$, defined by

  1. 1.

$\mathit{mand}(\mathbb{G}):=\textit{vars}(\mathbb{G})$,

  2. 2.

$\mathit{mand}(\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}):=\mathit{mand}(\mathcal{Q}_{1})\cup\mathit{mand}(\mathcal{Q}_{2})$,
and

  3. 3.

$\mathit{mand}(\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}):=\mathit{mand}(\mathcal{Q}_{1})$.

For handling optional pattern
$\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$ correctly, we need
to decide, in which cases an occurrence of variable $\mathtt{v}$ in
$\mathcal{Q}_{2}$ has an optional dependency to another occurrence of the same
variable. The case $\mathtt{v}\in\textit{vars}(\mathcal{Q}_{1})$ is reflected
by query $\textbf{(}\mathcal{X}_{2}\textbf{)}$. Upon identification of such
mandatory/optional pairs, we rename the optional occurrences of variables in
our SOI and add an inequality as before, e. g., (14). More precisely, for the
special case of query
$\mathcal{Q}=\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$, we
create the SOI representation for $\mathcal{Q}$ by first identifying
mandatory/optional dependencies between $\mathcal{Q}_{1}$ and
$\mathcal{Q}_{2}$, that are occurrences of variables
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})$.
For
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})$,
we reserve a unique name $\mathtt{v}_{\\_}{\mathcal{Q}_{2}}$, which we use to
replace $\mathtt{v}$ in every inequality of $\mathcal{Q}_{2}$, achieved by a
renaming
$\rho:=\\{(\mathtt{v},\mathtt{v}_{\\_}{\mathcal{Q}_{2}})\mid\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})\\}$.
Upon renaming, we add inequality

$\mathtt{v}_{\\_}{\mathcal{Q}_{2}}\leq\mathtt{v}$ (15)

for
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})$
to the overall SOI. The largest solution to the resulting SOI consists of all
assignments to the new variables $\mathtt{v}_{\\_}{\mathcal{Q}_{2}}$, i. e.,
to variables not occurring in the original formulation of the query. Since
these variables are only surrogates necessary for handling optionality
correctly, and the largest solution for these variables is subsumed by the
respective mandatory variables (cf. (15)), we may ignore them in the final
result of the pruning step.

######  Lemma 4.

Let DB be a graph database and $\mathcal{Q}_{1},\mathcal{Q}_{2}$ two Sparql
queries with sound systems of inequalities
$\mathcal{E}(\mathcal{Q}_{1})=(\mathtt{Var}_{\\_}1,\mathtt{Eq}_{\\_}1)$ and
$\mathcal{E}(\mathcal{Q}_{2})=(\mathtt{Var}_{\\_}2,\mathtt{Eq}_{\\_}2)$.
Furthermore, define renaming as $\rho$ by
$\rho(\mathtt{v}):=\mathtt{v}_{\\_}{\mathcal{Q}_{2}}$ for all
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})$.
Then
$\begin{array}[]{rcl}\mathcal{E}&=&(\mathtt{Var}_{\\_}1\cup\mathtt{Var}_{\\_}2\cup\rho(\mathtt{Var}_{\\_}2),\mathtt{Eq}_{\\_}1\cup\rho(\mathtt{Eq}_{\\_}2)\cup\mathtt{Eq}_{\\_}0)\end{array}$
with
$\mathtt{Eq}_{\\_}0:=\\{\mathtt{v}_{\\_}{\mathcal{Q}_{2}}\leq\mathtt{v}\mid\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})\cap\mathit{mand}(\mathcal{Q}_{1})\\}$
is sound for $\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$.

######  Proof:

Let
$\mu\in\llbracket\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}$
with $\mu(v)=o$ for
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2})$.
We need to show that $(\mathtt{v},o)\in S$ where $S$ is the largest solution
of $\mathcal{E}$. There are two cases to distinguish,  (a)
$\mu=\mu_{\\_}1\cup\mu_{\\_}2$where
$\mu_{\\_}i\in\llbracket\mathcal{Q}_{i}\rrbracket_{\\_}\textit{DB}$ ($i=1,2$)
with $\mu_{\\_}1\mathbin{\rightleftharpoons}\mu_{\\_}2$ and  (b)
$\mu=\mu_{\\_}1$where
$\mu_{\\_}1\in\llbracket\mathcal{Q}_{1}\rrbracket_{\\_}\textit{DB}$ and there
is no $\mu_{\\_}2\in\llbracket\mathcal{Q}_{2}\rrbracket_{\\_}\textit{DB}$
compatible to $\mu_{\\_}1$.  Case (a) becomes analogous to the proof of Lemma
3, considering that for any occurrence of $\mathtt{v}_{\\_}{\mathcal{Q}_{2}}$
in $\rho(\mathtt{Eq}_{\\_}2)$, inequality (15) makes the requirements upon
$\mathtt{v}_{\\_}{\mathcal{Q}_{2}}$ only weaker. Hence,
$\mu_{\\_}2(\mathtt{v})$ is preserved. In case (b), we distinguish two further
cases for variable $\mathtt{v}$,  (i)
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{1})\setminus\textit{vars}(\mathcal{Q}_{2})$and
(ii)
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{1})\cap\textit{vars}(\mathcal{Q}_{2})$.
The claim for case (i) directly follows from the sound SOI
$\mathcal{E}(\mathcal{Q}_{1})$. In case (ii), it might be that in the largest
solution $S_{\\_}2$ of $\mathcal{E}(\mathcal{Q}_{2})$, $(\mathtt{v},o)\notin
S_{\\_}2$. However, $\mathtt{v}$ is subject to renaming, since it is a
variable of both sub-queries. Therefore
$(\mathtt{v}_{\\_}{\mathcal{Q}_{2}},o)\notin\rho{S_{\\_}2}$ but as we added
inequality (15) to $\mathtt{Eq}_{\\_}o$, we get that $(\mathtt{v},o)\in S$ by
soundness of $\mathtt{E}(\mathcal{Q}_{1})$. □

###  4.4 The General Case

The general case, outlined by example $\textbf{(}\mathcal{X}_{3}\textbf{)}$,
needs to take the contexts of optional patterns into account. Since
$\mathtt{v_{\\_}3}$ has a mandatory occurrence in
$\textbf{(}\mathcal{X}_{3}\textbf{)}$ but an optional in the sub-query
$\\{(\mathtt{v_{\\_}1},a,\mathtt{v_{\\_}2})\\}\mathbin{\text{OPTIONAL}}\\{(\mathtt{v_{\\_}3},b,\mathtt{v_{\\_}2})\\}$,
Sparql’s evaluation semantics defines the second occurrence of
$\mathtt{v_{\\_}3}$ to be mandatory w. r. t. the first. For any optional
pattern $\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$ occurring as
a sub-query of a query $\mathcal{Q}\in\mathcal{S}$, if a variable
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})$ occurs as mandatory in
$\mathcal{Q}$, then we perform the same renaming as in Lemma 4 for
$\mathcal{Q}_{2}$. For a variable
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})$, there may be several
candidates. From all the choices we pick the syntactically closest. As an
example, consider the optional patterns

$\begin{array}[]{rcl}P&=&(P_{\\_}1\mathbin{\text{OPTIONAL}}P_{\\_}2)\mathbin{\text{OPTIONAL}}P_{\\_}3\text{
and}\\\
R&=&R_{\\_}1\mathbin{\text{OPTIONAL}}(R_{\\_}2\mathbin{\text{OPTIONAL}}R_{\\_}3)\text{.}\end{array}$

Assume that $\mathtt{y}\in\textit{vars}(P_{\\_}i)$ ($i=1,2,3$) and
$\mathtt{z}\in\textit{vars}(R_{\\_}i)$ ($i=1,2,3$). The occurrences of
$\mathtt{y}$ in $P_{\\_}2$ and $P_{\\_}3$ are syntactically closest to the
mandatory occurrence of $\mathtt{y}$ in $P_{\\_}1$, giving rise to
inequalities

$\begin{array}[]{rcl}\mathtt{y}_{\\_}{P_{\\_}2}&\leq&\mathtt{y}\\\
\mathtt{y}_{\\_}{P_{\\_}3}&\leq&\mathtt{y}\text{.}\end{array}$

It may also be that $\mathtt{x}\in\textit{vars}(P_{\\_}i)$ ($i=2,3$) and
$\mathtt{x}\notin\textit{vars}(P_{\\_}1)$. In these situations, we rename
$\mathtt{x}$ to $\mathtt{x}_{\\_}{P_{\\_}2}$ and $\mathtt{x}_{\\_}{P_{\\_}3}$,
respectively, but would not add any interdependencies between these variables.
In extreme cases, the original variable $\mathtt{x}$ may not occur in the
resulting SOI at all. In these cases, the soundness proof requires that every
solution to $\mathtt{x}_{\\_}{P_{\\_}2}$ or $\mathtt{x}_{\\_}{P_{\\_}3}$ also
is a solution to variable $\mathtt{x}$.

The occurrence of $\mathtt{z}$ in $R_{\\_}3$ is closest to the occurrence in
$R_{\\_}2$, and the occurrence in $R_{\\_}2$ is closest to $R_{\\_}1$, raising
the following inequalities,

$\begin{array}[]{rcl}\mathtt{z}_{\\_}{R_{\\_}3}&\leq&\mathtt{z}_{\\_}{R_{\\_}2}\\\
\mathtt{z}_{\\_}{R_{\\_}2}&\leq&\mathtt{z}\text{.}\end{array}$

Handling the general case formally, needs to conduct a notion of
$\mathcal{S}$-contexts, being queries with holes. Since the proof of the
resulting soundness lemma is completely analogous, thus gives no more insights
than the proof of Lemma 4, our considerations about optional patterns are
complete. What if optional patterns occur within the clauses of a conjunction?
Let us consider another example:

$\left(\\{(\mathtt{v_{\\_}1},a,\mathtt{v_{\\_}2})\\}\mathbin{\text{OPTIONAL}}\\{(\mathtt{v_{\\_}3},b,\mathtt{v_{\\_}2})\\}\right)\mathbin{\text{AND}}\\{(\mathtt{v_{\\_}3},c,\mathtt{v_{\\_}4})\\}$.

$\textbf{(}\mathcal{X}_{3}\textbf{)}$

12$a$3$a$4$b$5$d$$c$6$d$

(a)

1$\mathsf{v_{\\_}1}$2$\mathsf{v_{\\_}2}$$a$4$\mathsf{v_{\\_}3}$$b$5$\mathsf{v_{\\_}4}$$c$

(b)

1$\mathsf{v_{\\_}1}$3$\mathsf{v_{\\_}2}$$a$4$\mathsf{v_{\\_}3}$5$\mathsf{v_{\\_}4}$$c$

(c)

Figure 5: (a) Graph Database, (b) and (c) Matches of
$\textbf{(}\mathcal{X}_{3}\textbf{)}$

The query consists of three triple patterns, the first two constitute an
optional pattern and their results are joined with the third triple pattern.
Fig. 5(b) and (c) show possible matches of
$\textbf{(}\mathcal{X}_{3}\textbf{)}$ w. r. t. the graph database in Fig.
5(a). Analogous to $\textbf{(}\mathcal{X}_{2}\textbf{)}$, we derive
$\mathtt{v_{\\_}2}_{\\_}m$ and $\mathtt{v_{\\_}2}_{\\_}o$ with
$\mathtt{v_{\\_}2}_{\\_}o\leq\mathtt{v_{\\_}2}_{\\_}m$ from the optional
pattern. The first occurrence of $\mathtt{v_{\\_}3}$ is optional whilst the
second occurrence is a mandatory one. Matches to $\mathtt{v_{\\_}3}$ have an
outgoing $c$-labeled edge and may feature the $b$-labeled edge from the
optional pattern. Although both occurrences are not directly linked in an
optional pattern, the second occurrence restricts the possible assignments for
the first one. Formally, we express such relations as a generalization of
Lemma 3. We use renamings based on a unique identification of subqueries. If
we abstract $\textbf{(}\mathcal{X}_{3}\textbf{)}$ to
$\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$, then $\mathcal{Q}_{1}$
is $R_{\\_}1\mathbin{\text{OPTIONAL}}R_{\\_}2$. In the course of renaming, we
replace $\mathtt{v_{\\_}3}$ in $R_{\\_}2$ by a fresh variable, e. g.,
$\mathtt{v_{\\_}3}^{R_{\\_}2}$, and add inequality
$\mathtt{v_{\\_}3}^{R_{\\_}2}\leq\mathtt{v_{\\_}3}$ to the system of
inequalities for $\textbf{(}\mathcal{X}_{3}\textbf{)}$. Renaming functions
$\rho_{\\_}i$ ($i=1,2$) are defined accordingly to rename variables that occur
only optional in $\mathcal{Q}_{i}$ but mandatory in the other subquery
$\mathcal{Q}_{j}$.

######  Lemma 5.

Let DB be a graph database and $\mathcal{Q}_{1},\mathcal{Q}_{2}\in\mathcal{S}$
with sound systems of inequalities
$\mathcal{E}(\mathcal{Q}_{1})=(\mathtt{Var}_{\\_}1,\mathtt{Eq}_{\\_}1)$ and
$\mathcal{E}(\mathcal{Q}_{2})=(\mathtt{Var}_{\\_}2,\mathtt{Eq}_{\\_}2)$.
Define renaming $\rho_{\\_}i$ ($i=1,2$) as given above, and
$\mathtt{Eq}_{\\_}0:=\\{\mathtt{v}^{\prime}\leq\mathtt{v}\mid(\mathtt{v},\mathtt{v})\in\rho_{\\_}i,i\in\\{1,2\\}\\}$.
Then
$\mathcal{E}=(\mathtt{Var}_{\\_}1\cup\mathtt{Var}_{\\_}2\cup\rho_{\\_}1(\mathtt{Var}_{\\_}1)\cup\rho_{\\_}2(\mathtt{Var}_{\\_}2),\rho_{\\_}1(\mathtt{Eq}_{\\_}1)\cup\rho_{\\_}2(\mathtt{Eq}_{\\_}2)\cup\mathtt{Eq}_{\\_}0)$
is sound for $\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$.

Independence of the results due to $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$ is
guaranteed by the renaming function and the additional inequalities. The
solution is interpreted as if all renamed variables are unified with their
originals.

###  4.5 Discussion

Before we discuss an important query type, we conclude this section by showing
that the constructed systems of inequalities are sound for any query
$\mathcal{Q}\in\mathcal{S}$, using all the results we obtained so far in the
proof.

######  Theorem 2 (Soundness).

Let DB be a graph database and $\mathcal{Q}\in\mathcal{S}$. Then
$\mathcal{E}(\mathcal{Q})$ is a sound SOI.

######  Proof:

For the base case, $\mathcal{Q}=\mathbb{G}$, Theorem 1 provides us with the
necessary argument. Since the largest dual simulation is the largest solution
of the respective SOI, soundness of $\mathcal{E}(\mathbb{G})$ immediately
follows. Assume for queries $\mathcal{Q}_{1},\mathcal{Q}_{2}\in\mathcal{S}$,
soundness of the respective SOIs $\mathcal{E}(\mathcal{Q}_{1})$ and
$\mathcal{E}(\mathcal{Q}_{2})$ is already provided, which may already conduct
some renaming due to our discussion in Sect. 4.3. For the recursive step, we
distinguish two cases. First, if
$\mathcal{Q}=\mathcal{Q}_{1}\mathbin{\text{AND}}\mathcal{Q}_{2}$, then
$\mathcal{E}(\mathcal{Q})$ is sound due to Lemma 3333Adjustments to the
soundness notion has no influence on the lemma’s correctness.. Lemma 4 proves
soundness of $\mathcal{E}(\mathcal{Q})$ with
$\mathcal{Q}=\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$. □

Our theoretical considerations are limited to Sparql queries in which every
node of a triple pattern is a variable. Sparql also allows mentioning
constants, i. e., objects and literals from the database, often drastically
reducing the number of possible results. The key to integrating constant nodes
into our pruning technique is to alter inequality (12).

Our dual simulation process is not restricted to well-designed patterns. Well-
designed patterns are Sparql queries $\mathcal{Q}$ with the property that for
every sub-query $\mathcal{Q}_{1}\mathbin{\text{OPTIONAL}}\mathcal{Q}_{2}$ and
every $\mathtt{v}\in\textit{vars}(\mathcal{Q}_{2})$ that also occurs outside
the optional pattern also occurs in $\mathcal{Q}_{1}$, i. e.,
$\mathtt{v}\in\textit{vars}(\mathcal{Q}_{1})$ [28]. Query
$\textbf{(}\mathcal{X}_{3}\textbf{)}$ is not well-designed, since
$\mathtt{v_{\\_}3}$ occurs as an optional variable but also outside the
optional sub-pattern. Non-well-designed patterns give rise to cross-product
results, as indicated by the match in Fig. 5(c). Assume that we have several
$c$-labeled edges, then each of these edges together with the $a$-labeled edge
forms an answer to the query. In these situations, our procedure remains
effective, since it handles both occurrences of variable $\mathtt{v_{\\_}3}$
separately. In fact, the addition of $\mathbin{\text{AND}}$ and
$\mathbin{\text{OPTIONAL}}$ operators does not influence the complexity of our
procedure. Considering dual simulation as a query processor for $\mathcal{S}$,
Pspace-completeness of the evaluation problem [31] may be evaded, since
checking whether a given relation $S$ constitutes a valid assignment to
$\mathcal{E}(Q)$ and extensions of it may be performed in Ptime. More
expressive fragments of Sparql add combinatorial complexity not solvable by
pure dual simulation pattern matching.

There are two reasons which make well-designed patterns interesting. First,
the fragment containing only well-designed patterns has a coNP-complete
evaluation problem [28, 3], as opposed to Pspace-completeness of Sparql’s
evaluation problem. Second, every well-designed pattern is weakly monotone
[3], an important property when discussing NULL semantics. To this end, we
cannot tell whether or not we handle all weakly monotone queries effectively.
However, the next section provides indications in this respect.

##  5 Evaluation

First, we compare our algorithm to the state-of-the-art dual simulation
algorithm as introduced by Ma et al. [21] and used in implementations of [25,
32, 21] for evaluation purposes. Both are implemented within our prototype
called sparqlSim. Second, we analyze how our Sparql extension of dual
simulation may be used to effectively and efficiently prune graph databases to
improve query processing on an in-memory RDF database and a triple store based
on relational database technology. After analyzing the effectiveness of the
pruning, we compare query evaluation times with two graph database systems on
two very large graph datasets comprising 750 million and 1.3 billion triples.
We focus on time-consuming optional queries which were also used by Atre [5].
Details concerning the evaluation results, a list of queries, and our
implementation can be found on our project’s Github page.

###  5.1 Experimental Setup

For the first experiment, we have implemented the dual simulation algorithm of
Ma et al.as an option in our tool. To evaluate our prototypes’ performance as
a pruning mechanism, we employed one of the fastest RDF databases Virtuoso
[10] and the high-performance in-memory database RDFox [26]. All experiments
have been performed on a server running Ubuntu 16.04 with four XEON E7-8837,
$2.67\text{\,}\mathrm{GHz}$, having 8 Cores each, $384\text{\,}\mathrm{GB}$
RAM and a Kingston DCP1000 NVMe PCI-E SSD. We deactivated caching for Virtuoso
to achieve stable query evaluation times. RDFox is not using query caches. For
the evaluation, we have run all queries 10 times on each database and averaged
the times.

Since we provide a dual simulation algorithm that can be used as an external
pruning mechanism, we imported the result sets from our tool into the two
databases manually and then re-evaluated the queries on the pruning in
comparison to queries on the full databases. Here, we did not consider the
export time from our tool and the import time into the database, because our
tool could easily be integrated into a standard database system, using our
computations internally.

Table 2: Runtimes of our sparqlSim for BGPs from queries $\mathcal{B}_{0}$-$\mathcal{B}_{21}$ compared to Ma et al. [21]. Query | $t_{\\_}{\textsc{sparqlSim}}$ | $t_{\\_}{\textsc{Ma et al.}}$ | Query | $t_{\\_}{\textsc{sparqlSim}}$ | $t_{\\_}{\textsc{Ma et al.}}$
---|---|---|---|---|---
$\mathcal{B}_{0}$ | 0.10385 | 6.72121 | $\mathcal{B}_{10}$ | 0.02397 | 0.27126
$\mathcal{B}_{1}$ | 0.03876 | 3.33471 | $\mathcal{B}_{11}$ | 0.01392 | 0.02099
$\mathcal{B}_{2}$ | 0.79097 | 3.84781 | $\mathcal{B}_{12}$ | 0.01477 | 0.02287
$\mathcal{B}_{3}$ | 0.69797 | 5.62662 | $\mathcal{B}_{13}$ | 0.35515 | 11.30355
$\mathcal{B}_{4}$ | 0.00003 | 0.00004 | $\mathcal{B}_{14}$ | 5.46599 | 16.63957
$\mathcal{B}_{5}$ | 0.04091 | 0.31700 | $\mathcal{B}_{15}$ | 13.43710 | 24.99660
$\mathcal{B}_{6}$ | 0.41105 | 0.54291 | $\mathcal{B}_{16}$ | 0.00002 | 0.00003
$\mathcal{B}_{7}$ | 0.26991 | 0.51206 | $\mathcal{B}_{17}$ | 1.12649 | 2.30390
$\mathcal{B}_{8}$ | 0.13562 | 5.51084 | $\mathcal{B}_{18}$ | 0.32056 | 0.54057
$\mathcal{B}_{9}$ | 0.02551 | 0.08707 | $\mathcal{B}_{19}$ | 0.69515 | 5.15070

Our evaluation data comprises two popular RDF datasets:  (1) The DBpedia dump
2016-10 in the English language version [7] and  (2) the synthetic Lehigh
University Benchmark [16] (LUBM) dataset generated for $10000$ universities.
DBpedia comprises $751603507$ triples with $216132665$ nodes and $65430$
predicates. While the DBpedia queries $\mathcal{D}_{0}$-$\mathcal{D}_{5}$ stem
from [5], benchmark queries $\mathcal{B}_{0}$-$\mathcal{B}_{19}$ appeared in
the DBpedia benchmark dataset in [24]. The LUBM benchmark dataset comprises
$1381692508$ triples with $18$ predicates and $328620750$ nodes. Since
official query sets hardly cover optional patterns, we rely on queries that
have been used by Atre [5] (cf. $\mathcal{L}_{0}$-$\mathcal{L}_{5}$).

The space our tool allocates for storing the adjacency matrices sums up to
$35\text{\,}\mathrm{GB}$ for LUBM and $23\text{\,}\mathrm{GB}$ for DBpedia.
The biggest matrices of LUBM consume between $1\text{\,}\mathrm{GB}$ and
$4\text{\,}\mathrm{GB}$ of main memory (11 out of 36, e. g.,rdf:type). $99$%
of the DBpedia predicates allocate less than $1\text{\,}\mathrm{MB}$.
Constructing the adjacency matrices and producing the result triples requires
additional space for storing maps and string objects.

###  5.2 Evaluation Analysis

#### Comparison of Dual Simulation Algorithms

Due to the fact that Ma et al.’s algorithm [21] considers BGPs as input we
have removed the Sparql keyword $\mathbin{\text{OPTIONAL}}$ from benchmark
queries $\mathcal{B}_{0}$-$\mathcal{B}_{19}$. Evaluation times are shown in
Table 2. We observe that the optimizations allowed by sparqlSim (cf. Sect.
3.3) pay off, since we outperform Ma et al.’s algorithm in every case, often
even by an order of magnitude. When running in graph database query scenarios,
it is this order of magnitude the naive algorithm lacks.

#### Dual Simulation as Pruning Mechanism

Table 3: Result set sizes, numbers of required triples, runtimes of sparqlSim in seconds and numbers of triples after pruning. Query | Result No. | Req. Triples | $t_{\\_}{\textsc{sparqlSim}}$ | Tripl. aft. Pruning
---|---|---|---|---
$\mathcal{L}_{0}$ | $10448905$ | $3276841$ | $106.451$ | $10181730$
$\mathcal{L}_{1}$ | $226641$ | $114989$ | $8.464$ | $25429750$
$\mathcal{L}_{2}$ | $32828280$ | $15416012$ | $147.335$ | $48674046$
$\mathcal{L}_{3}$ | $11$ | $35$ | $0.138$ | $126$
$\mathcal{L}_{4}$ | $10$ | $33$ | $0.125$ | $101$
$\mathcal{L}_{5}$ | $7$ | $35$ | $1.220$ | $35$
$\mathcal{D}_{0}$ | $523066$ | $3139273$ | $4.396$ | $3141102$
$\mathcal{D}_{1}$ | $0$ | $0$ | $0.002$ | $0$
$\mathcal{D}_{2}$ | $12$ | $60$ | $0.088$ | $60$
$\mathcal{D}_{3}$ | $5794$ | $28704$ | $0.143$ | $28704$
$\mathcal{D}_{4}$ | $25102459$ | $22630477$ | $6.230$ | $22691521$
$\mathcal{D}_{5}$ | $365693$ | $79943$ | $0.574$ | $79944$
$\mathcal{B}_{0}$ | $12$ | $60$ | $0.088$ | $60$
$\mathcal{B}_{1}$ | $859751$ | $726749$ | $0.022$ | $726812$
$\mathcal{B}_{2}$ | $913786$ | $1587731$ | $0.532$ | $1588127$
$\mathcal{B}_{3}$ | $438542$ | $386000$ | $0.606$ | $386020$
$\mathcal{B}_{4}$ | $0$ | $0$ | $0.000$ | $0$
$\mathcal{B}_{5}$ | $0$ | $0$ | $0.033$ | $0$
$\mathcal{B}_{6}$ | $815522$ | $886826$ | $0.503$ | $886939$
$\mathcal{B}_{7}$ | $34991$ | $37965$ | $0.443$ | $37965$
$\mathcal{B}_{8}$ | $8416$ | $30258$ | $0.113$ | $30258$
$\mathcal{B}_{9}$ | $8247$ | $13116$ | $0.022$ | $13116$
$\mathcal{B}_{10}$ | $8061$ | $12642$ | $0.027$ | $12642$
$\mathcal{B}_{11}$ | $9849$ | $8955$ | $0.018$ | $8955$
$\mathcal{B}_{12}$ | $9554$ | $8660$ | $0.018$ | $8660$
$\mathcal{B}_{13}$ | $123467$ | $365131$ | $0.273$ | $365154$
$\mathcal{B}_{14}$ | $22673220$ | $27652055$ | $4.322$ | $27747192$
$\mathcal{B}_{15}$ | $0$ | $0$ | $0.000$ | $0$
$\mathcal{B}_{16}$ | $2$ | $4$ | $0.009$ | $4$
$\mathcal{B}_{17}$ | $7898331$ | $8285964$ | $0.917$ | $8294385$
$\mathcal{B}_{18}$ | $66903$ | $41808$ | $0.472$ | $41808$
$\mathcal{B}_{19}$ | $879460$ | $292531$ | $0.602$ | $292541$

First, we analyze sparqlSim’s pruning effectiveness (cf. Table 3) of dual
simulation for all LUBM and DBpedia queries. Observe that the number of
triples is drastically decreased from the original databases for all queries.
For queries with 0 triples left, there is no need for any further query
evaluation. Over all tested queries we prune at least 95% of the original
database. Hence, for most DBpedia queries we prune all triples not required
for any result (compare req. triples and tripl. aft. pruning in Table 3). In
comparison, the effectiveness of our pruning is smaller for LUBM queries,
being least effective for query $\mathcal{L}_{1}$. Here, only $0.9$% of the
triples after pruning are actually part of some result. Later on we provide
evidence that, e. g., for $\mathcal{L}_{1}$, our pruning allows the two
database systems to enormously improve upon their evaluation times.

Regarding efficiency, sparqlSim’s evaluation time heavily depends on the query
and the dataset. With LUBM, having only 18 distinct predicates, we have an
extreme case that often needs over 30 iterations to compute the largest dual
simulation, which leads to high running times of our algorithm, e. g., for
$\mathcal{L}_{0}$ or $\mathcal{L}_{2}$. As an outstanding characteristic,
these two queries have a huge number of results. It is further a combination
of the cyclic shape of the queries and the low selectivity of the predicates
within the queries that explains the long runtime of our algorithm. In
DBpedia, predicates usually have a much higher selectivity. Hence, we usually
perform the computation for these queries in only a split-second.

#### Runtime of RDF Databases

Table 4: Query processing times on the full and pruned dataset, and query times including pruning times for RDFox. All times are measured in seconds. Query | $t_{\\_}{\text{DB}}$ | $t_{\\_}{\text{DB pruned}}$ | $t_{\\_}{\text{DB pruned}}+t_{\\_}{\textsc{sparqlSim}}$
---|---|---|---
$\mathcal{L}_{0}$ | 19.100 | 1.401 | 107.852
$\mathcal{L}_{1}$ | $25900.000$ | 888.000 | 896.464
$\mathcal{L}_{2}$ | 161.000 | 15.690 | 163.025
$\mathcal{L}_{3}$ | 0.000 | 0.000 | 0.138
$\mathcal{L}_{4}$ | 0.000 | 0.000 | 0.125
$\mathcal{L}_{5}$ | 0.000 | 0.000 | 1.223
$\mathcal{D}_{0}$ | 1.400 | 1.115 | 5.511
$\mathcal{D}_{1}$ | 0.000 | 0.000 | 0.002
$\mathcal{D}_{2}$ | 1.100 | 0.003 | 0.091
$\mathcal{D}_{3}$ | 0.620 | 0.002 | 0.145
$\mathcal{D}_{4}$ | 5.960 | 3.493 | 9.722
$\mathcal{D}_{5}$ | 3.230 | 0.016 | 0.590
$\mathcal{B}_{0}$ | 1.468 | 0.000 | 0.088
$\mathcal{B}_{1}$ | 0.099 | 0.030 | 0.052
$\mathcal{B}_{2}$ | 0.348 | 0.110 | 0.642
$\mathcal{B}_{3}$ | 0.104 | 0.012 | 0.618
$\mathcal{B}_{4}$ | 0.033 | 0.000 | 0.000
$\mathcal{B}_{5}$ | 0.000 | 0.000 | 0.033
$\mathcal{B}_{6}$ | 12.830 | 0.042 | 0.545
$\mathcal{B}_{7}$ | 14.410 | 0.002 | 0.445
$\mathcal{B}_{8}$ | 0.793 | 0.001 | 0.114
$\mathcal{B}_{9}$ | 0.117 | 0.001 | 0.023
$\mathcal{B}_{10}$ | 0.004 | 0.001 | 0.028
$\mathcal{B}_{11}$ | 0.001 | 0.000 | 0.018
$\mathcal{B}_{12}$ | 0.001 | 0.001 | 0.019
$\mathcal{B}_{13}$ | 0.643 | 0.022 | 0.295
$\mathcal{B}_{14}$ | 3.282 | 1.998 | 6.320
$\mathcal{B}_{15}$ | 0.941 | 0.000 | 0.000
$\mathcal{B}_{16}$ | 0.000 | 0.000 | 0.009
$\mathcal{B}_{17}$ | 0.758 | 0.310 | 1.227
$\mathcal{B}_{18}$ | 0.119 | 0.001 | 0.473
$\mathcal{B}_{19}$ | 18.750 | 0.048 | 0.650

By the next experiments we compare the query evaluation time of the in-memory
database RDFox to sparqlSim in combination with RDFox as a query processor. In
Table 4, we observe an improvement of the query time in 15 out of 32 queries.
Especially the improvement on query $\mathcal{L}_{1}$ with a query processing
time of $25900$ seconds on RDFox is worth mentioning. We could run our dual
simulation algorithm in only 8 seconds (cf. Table 3), decreasing the query
time of RDFox by more than 20 times. For $\mathcal{L}_{0}$, however,
$t_{\\_}{\textsc{sparqlSim}}$ alone is around 5 times slower than RDFox
($t_{\\_}{\text{DB}}$). Also, in queries $\mathcal{D}_{5}$, $\mathcal{B}_{0}$,
$\mathcal{B}_{7}$-$\mathcal{B}_{9}$, $\mathcal{B}_{17}$, $\mathcal{B}_{21}$ we
show good improvements of the in-memory databases’ evaluation times. For most
of the remaining queries we show comparable results to RDFox, varying by some
milliseconds.

Table 5: Query processing times on the full and pruned dataset, and query times including pruning times for Virtuoso. All times are measured in seconds. Query | $t_{\\_}{\text{DB}}$ | $t_{\\_}{\text{DB pruned}}$ | $t_{\\_}{\text{DB pruned}}+t_{\\_}{\textsc{sparqlSim}}$
---|---|---|---
$\mathcal{L}_{0}$ | 5.126 | 2.261 | 108.712
$\mathcal{L}_{1}$ | 50.853 | 0.971 | 9.435
$\mathcal{L}_{2}$ | 56.676 | 26.767 | 174.102
$\mathcal{L}_{3}$ | 0.001 | 0.000 | 0.138
$\mathcal{L}_{4}$ | 0.000 | 0.000 | 0.125
$\mathcal{L}_{5}$ | 0.000 | 0.000 | 1.223
$\mathcal{D}_{0}$ | 0.395 | 0.359 | 4.755
$\mathcal{D}_{1}$ | 0.001 | 0.000 | 0.002
$\mathcal{D}_{2}$ | 0.002 | 0.000 | 0.089
$\mathcal{D}_{3}$ | 0.010 | 0.003 | 0.147
$\mathcal{D}_{4}$ | 2.148 | 4.008 | 10.238
$\mathcal{D}_{5}$ | 0.039 | 0.021 | 0.595
$\mathcal{B}_{0}$ | 0.002 | 0.000 | 0.088
$\mathcal{B}_{1}$ | 0.003 | 0.001 | 0.023
$\mathcal{B}_{2}$ | 0.003 | 0.003 | 0.030
$\mathcal{B}_{3}$ | 0.001 | 0.002 | 0.020
$\mathcal{B}_{4}$ | 0.001 | 0.002 | 0.020
$\mathcal{B}_{5}$ | 0.054 | 0.031 | 0.303
$\mathcal{B}_{6}$ | 1.082 | 0.441 | 4.762
$\mathcal{B}_{7}$ | 0.000 | 0.000 | 0.000
$\mathcal{B}_{8}$ | 0.000 | 0.000 | 0.009
$\mathcal{B}_{9}$ | 0.121 | 0.099 | 1.016
$\mathcal{B}_{10}$ | 0.043 | 0.009 | 0.031
$\mathcal{B}_{11}$ | 0.012 | 0.003 | 0.476
$\mathcal{B}_{12}$ | 0.102 | 0.056 | 0.658
$\mathcal{B}_{13}$ | 0.069 | 0.064 | 0.596
$\mathcal{B}_{14}$ | 0.000 | 0.000 | 0.000
$\mathcal{B}_{15}$ | 0.000 | 0.000 | 0.034
$\mathcal{B}_{16}$ | 0.042 | 0.026 | 0.594
$\mathcal{B}_{17}$ | 0.022 | 0.013 | 0.516
$\mathcal{B}_{18}$ | 0.003 | 0.001 | 0.444
$\mathcal{B}_{19}$ | 0.021 | 0.005 | 0.118

Table 5 shows an improvement of the running times of only 3 queries for
Virtuoso. For most other queries, evaluation times are on par with
$t_{\\_}{\text{DB}}$. For some queries, our pruning could not increase
Virtuoso’s evaluation time as much as for RDFox. A detailed analysis of
Virtuoso’s query plans revealed that this was due to changes in the join order
that sometimes seems to turn against optimal evaluation times by drastically
increasing the number of intermediate results, e. g., $\mathcal{D}_{4}$ with
doubled evaluation time $t_{\\_}{\text{DB pruned}}$ on the 3% portion of
DBpedia. Nevertheless, we believe that Virtuoso could benefit from a direct
integration of sparqlSim as a pruning technique. In turn, our tool may advance
by employing Virtuoso’s built-in heuristics for query evaluation plans. On the
downside, our algorithm is often slightly slower than the professionally
implemented and highly optimized RDF triple store. Some of the more complex
queries took longer to produce the pruning than for Virtuoso to produce the
actual answers. These queries took several iterations in sparqlSim to compute.
We believe that we can benefit from more sophisticated join order optimization
techniques as used for example in Virtuoso which could boost our computation
times tremendously. The very fast pruning time for the cyclic query
$\mathcal{L}_{1}$ requires only two iterations, and thereby points to the
potential of our solution.

###  5.3 Discussion

The evaluation results suggest dual simulation pruning as an effective
technique allowing two state-of-the-art graph database systems to improve upon
their query evaluation times, sometimes enormously. Preprocessing
$\mathcal{L}_{1}$ is most profitable, since huge intermediate tables can be
avoided. In this case we observe a decrease by more than one order of
magnitude while the pruning time is vastly fast in only two iterations. In
contrast, because intermediate results in the evaluation of $\mathcal{L}_{0}$
are rather small, the benefits of dual simulation pruning are not as
significant as for $\mathcal{L}_{1}$. Furthermore, the low selectivity
predicates of $\mathcal{L}_{0}$ result in a rather big number of iterations
that increases the pruning time compared to e. g., $\mathcal{L}_{1}$. As a
general rule we recommend using dual simulation for pruning in cases where
queries produce large intermediate results. Such cases can usually be detected
employing database statistics for join result size estimation, also used for
join order optimization.

The queries discussed so far are outstanding in their own roles. While
$\mathcal{L}_{0}$’s evaluation is always faster than the computation of the
dual simulation pruning, both database systems we considered benefit from the
pruning for $\mathcal{L}_{1}$. The mandatory cores of both queries are
depicted in Fig. 6. First observe that both queries are cyclic. Although
$\mathcal{L}_{0}$ is quite small, our dual simulation algorithm takes more
than $30$ iterations until it reaches the fixpoint. From a brute force
analysis we learn that the number of iterations may be reduced by $16$, but
only resulting in half the time of the computation reported in Table 3. After
having stabilized the equations for any two nodes of $\mathcal{L}_{0}$, the
third node may turns equations for the other two nodes unstable. Hence, the
evaluation performance of Virtuoso and RDFox cannot be beaten by our current
implementation, no matter which specific heuristic we choose. The predicates
of $\mathcal{L}_{0}$ share quite a low selectivity rate. In contrast, dual
simulation between query $\mathcal{L}_{1}$ and the LUBM dataset takes only two
iterations, allowing for an overall improvement of Virtuoso as well as RDFox.

studentprofessoradvisorcourseassistantteacher

(a) $\mathcal{L}_{\\_}0$

publicationub:Publicationtypestudentauthorprofessorauthoruniversitydegreedepartmentsub_organizationmemberworks_for

(b) $\mathcal{L}_{\\_}1$

Figure 6: The mandatory (basic graph pattern) cores of queries
$\mathcal{L}_{\\_}0$ and $\mathcal{L}_{\\_}1$

Regarding the effectiveness of the pruning, LUBM query $\mathcal{L}_{1}$
represents one of the worst examples with over $200$ times more leftover
triples than necessary. The reason for such a huge difference can be found in
the counterexample to Theorem 1 described at the end of Sect. 4.1. Let us
transfer the known example by considering a subexpression of query
$\mathcal{L}_{1}$ which is depicted in Fig. 6(b). At its core,
$\mathcal{L}_{1}$ asks for all publications together with two of their
authors, both affiliated with a department (one is a student member, the other
is an employee) that is part of the university from which the student got
their degree. Suppose we have two disjoint matches isomorphic to the graph
representation of $\mathcal{L}_{1}$, i. e., two different papers with authors
from two distinct departments. It is important that the departments belong to
different universities. Now assume the second paper has a third author who got
his degree from the second university but is a student member of the first
department. Furthermore, this student has no other incident edges. Then this
student node is not part of any match due to Sparql. However, dual simulation
does not discriminate this node, since it reflects a similar situation and all
adjacent nodes dual simulate their respective counterparts in
$\mathcal{L}_{1}$.

The LUBM dataset is especially prone to queries like $\mathcal{L}_{1}$, since
it is a very large dataset with only little diversity in the generated
subgraphs (recall that 18 predicates are distributed over 1.33 billion edges).
As a consequence of the low diversity, potential matches are often adjacent
and dual simulation combines them frequently by edges not belonging to any
match. Custom-tailored notions of query matches based on dual simulations may
avoid these (possibly) unwanted results. However, no such solution can resolve
this issue completely without stepping into np-completeness or even Pspace-
completeness.

##  6 Related Work

Recently, graph pattern matching has become a trending topic for graph
databases, different from the canonical though costly prime candidate of graph
isomorphism, with the goal of reducing structural requirements of the answer
graphs. Especially, simulations have been implemented for different graph
database tasks [9, 13, 11, 25]. Ma et al. [21] introduce the notion of dual
simulation. Having a simulation preorder in a database context considering
forward and backward edges is mentioned as early as in the year 2000 [2]. On
the downside, performance improvements by dual simulation come with a loss of
topology [21].

Mottin et al. [25] build on simulation as one solution to their query paradigm
called Exemplar Queries. For a given exemplar graph pattern, the user obtains
subgraphs from the database similar to the exemplar. We foresee that exemplar
queries as well as other applications of graph pattern matching may exhibit
the portion of Sparql integrated in our framework, making their proposals even
more attractive to users.

Using simulation for graph database pruning has been proposed as a component
in Panda [32]. In Panda, subgraph simulation is used to filter unnecessary
tuples before answering isomorphism queries. Their large-scale evaluation
shows improvements in query time compared to several other isomorphism-based
query processors. In contrast, we rely on dual simulation being more effective
in pruning unnecessary triples, and we implement a fast dual simulation
algorithm operating on bit-matrices which are particularly useful for large
graph databases. Furthermore, we use a more expressive query model that could
also be integrated into their pruning technique to support more complex
queries. Other existing approaches for optimizing graph database querying rely
on adapting traditional database optimization techniques, usually leading to
major improvements with regard to the query performance [8, 10]. However,
graph database queries usually consist of numerous joins with oftentimes huge
intermediate results, requiring specialized optimization techniques.
Therefore, join order estimation for graph databases, especially RDF triple
stores, is still an active field [31, 27, 20, 5]. Our proposal appreciates the
graph data model and performs light-weight algorithms to support traditional
database optimization. In fact, upon effectiveness of sparqlSim huge
intermediate results may be avoided.

Simulation-based indexing techniques have already been used for join-ahead
pruning in databases on XML data [23]. The index is created by computing
bisimulation equivalence classes of nodes on the original database. Each
equivalence class groups structurally bisimilar nodes [29, 33]. Bisimulation
is more restrictive than dual simulation which we use throughout this paper.
However, our algorithm could benefit from similar ideas. It would be
sufficient to produce dual simulation equivalence classes, which promises to
obtain a much smaller database fingerprint than possible with bisimulations,
since (dual) simulation equivalence is coarser than bisimulation.

##  7 Conclusion

We proposed efficient processing of Sparql queries based on graph pattern
matching. Our algorithm builds upon dual simulation and for all extensions,
due to Sparql, we provided soundness proofs. To derive an algorithm competing
with state-of-the-art graph databases we contribute an alternative
characterization of dual simulation in terms of a system of inequalities. Dual
simulation is directly applicable to Sparql’s BGPs, whereas composite queries
including $\mathbin{\text{AND}}$ and $\mathbin{\text{OPTIONAL}}$ operators,
are handled by conservative extensions of dual simulation.

We could show that our algorithm outperforms standard dual simulation
algorithms on a variety of real-world Sparql BGPs. Furthermore, our dual
simulation algorithm can be used to aggressively prune triples, speeding up
graph database query processing for state-of-the-art graph databases. In
comparison to these graph databases, we could improve the query evaluation
time for several queries drastically and showed comparable results for the
others. We believe that most database systems would benefit from a direct
integration of our proposal into their query processor. Further applications
already using dual simulation may benefit from our Sparql extension to offer
more expressive query capabilities.

We plan to extend our prototype by applying more heuristics with which we
conduct extensive experiments to find better guidelines for the applicability
of dual simulation pruning. Our experiments with two state-of-the-art graph
database systems showed that such guidelines make sense on a per-system and
per-data basis. We are currently investigating the limits of our dual
simulation procedure w. r. t. different Sparql fragments. While this work
suggests a tremendous enhancement of the complexity of optional pattern
evaluation, other operators add combinatorial problems unavoidable for a dual
simulation evaluation semantics for Sparql.

## References

  * [1]
  * [2] Serge Abiteboul, Peter Buneman & Dan Suciu (2000): _Data on the Web: From Relations to Semistructured Data and XML_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
  * [3] Marcelo Arenas, Claudio Gutierrez, Daniel P. Miranker, Jorge Pérez & Juan F. Sequeda (2013): _Querying Semantic Data on the Web?_ SIGMOD Rec. 41(4), pp. 6–17, 10.1145/2430456.2430458.  Available at http://doi.acm.org/10.1145/2430456.2430458.
  * [4] Marcelo Arenas & Martin Ugarte (2017): _Designing a Query Language for RDF: Marrying Open and Closed Worlds_.  ACM Trans. Database Syst. 42(4), pp. 21:1–21:46, 10.1145/3129247.  Available at http://doi.acm.org/10.1145/3129247.
  * [5] Medha Atre (2015): _Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)_.  In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD ’15, ACM, New York, NY, USA, pp. 1793–1808, 10.1145/2723372.2746483.  Available at http://doi.acm.org/10.1145/2723372.2746483.
  * [6] Medha Atre, Vineet Chaoji, Mohammed J. Zaki & James A. Hendler (2010): _Matrix ”Bit” Loaded: A Scalable Lightweight Join Query Processor for RDF Data_.  In: Proceedings of the 19th International Conference on World Wide Web, WWW ’10, ACM, New York, NY, USA, pp. 41–50, 10.1145/1772690.1772696.  Available at http://doi.acm.org/10.1145/1772690.1772696.
  * [7] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak & Zachary Ives (2007): _DBpedia: A Nucleus for a Web of Open Data_.  In: The Semantic Web, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 722–735.
  * [8] Mihaela A. Bornea, Julian Dolby, Anastasios Kementsietsidis, Kavitha Srinivas, Patrick Dantressangle, Octavian Udrea & Bishwaranjan Bhattacharjee (2013): _Building an Efficient RDF Store over a Relational Database_.  In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, ACM, New York, NY, USA, pp. 121–132, 10.1145/2463676.2463718.  Available at http://doi.acm.org/10.1145/2463676.2463718.
  * [9] Joel Brynielsson, Johanna Hogberg, Lisa Kaati, Christian Martenson & Pontus Svenson (2010): _Detecting Social Positions Using Simulation_.  In: Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’10, IEEE Computer Society, Washington, DC, USA, pp. 48–55, 10.1109/ASONAM.2010.52.  Available at http://dx.doi.org/10.1109/ASONAM.2010.52.
  * [10] Orri Erling & Ivan Mikhailov (2009): _RDF Support in the Virtuoso DBMS_ , pp. 7–24.  Springer Berlin Heidelberg, Berlin, Heidelberg, 10.1007/978-3-642-02184-8_2.  Available at https://doi.org/10.1007/978-3-642-02184-8_2.
  * [11] Wenfei Fan (2012): _Graph Pattern Matching Revised for Social Network Analysis_.  In: Proceedings of the 15th International Conference on Database Theory, ICDT ’12, ACM, New York, NY, USA, pp. 8–21, 10.1145/2274576.2274578.  Available at http://doi.acm.org/10.1145/2274576.2274578.
  * [12] Wenfei Fan, Zhe Fan, Chao Tian & Xin Luna Dong (2015): _Keys for Graphs_.  Proc. VLDB Endow. 8(12), pp. 1590–1601, 10.14778/2824032.2824056.  Available at http://dx.doi.org/10.14778/2824032.2824056.
  * [13] Wenfei Fan, Jianzhong Li, Shuai Ma, Nan Tang, Yinghui Wu & Yunpeng Wu (2010): _Graph Pattern Matching: From Intractable to Polynomial Time_.  Proc. VLDB Endow. 3(1-2), pp. 264–275, 10.14778/1920841.1920878.  Available at http://dx.doi.org/10.14778/1920841.1920878.
  * [14] Wenfei Fan, Jianzhong Li, Shuai Ma, Hongzhi Wang & Yinghui Wu (2010): _Graph Homomorphism Revisited for Graph Matching_.  Proc. VLDB Endow. 3(1-2), pp. 1161–1172, 10.14778/1920841.1920986.  Available at http://dx.doi.org/10.14778/1920841.1920986.
  * [15] Nadime Francis, Alastair Green, Paolo Guargliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Martin Schuster, Petra Selmer & Andrés Taylor (2018): _Formal Semantics of the Language Cypher_.  CoRR abs/1802.09984.  Available at http://arxiv.org/abs/1802.09984.
  * [16] Yuanbo Guo, Zhengxiang Pan & Jeff Heflin (2005): _LUBM: A benchmark for OWL knowledge base systems_.  Web Semantics: Science, Services and Agents on the World Wide Web 3(2), pp. 158 – 182, https://doi.org/10.1016/j.websem.2005.06.005.  Available at http://www.sciencedirect.com/science/article/pii/S1570826805000132.  Selcted Papers from the International Semantic Web Conference, 2004.
  * [17] Xingwang Han, Zhiyong Feng, Xiaowang Zhang, Xin Wang, Guozheng Rao & Shuo Jiang (2016): _On the Statistical Analysis of Practical SPARQL Queries_.  In: Proceedings of the 19th International Workshop on Web and Databases, WebDB ’16, ACM, New York, NY, USA, pp. 2:1–2:6, 10.1145/2932194.2932196.  Available at http://doi.acm.org/10.1145/2932194.2932196.
  * [18] M. R. Henzinger, T. A. Henzinger & P. W. Kopke (1995): _Computing Simulations on Finite and Infinite Graphs_.  In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS ’95, IEEE Computer Society, Washington, DC, USA, pp. 453–.  Available at http://dl.acm.org/citation.cfm?id=795662.796255.
  * [19] Jinsoo Lee, Wook-Shin Han, Romans Kasperovics & Jeong-Hoon Lee (2013): _An in-depth comparison of subgraph isomorphism algorithms in graph databases_.  In: Proceedings of the 39th international conference on Very Large Data Bases, VLDB Endowment, pp. 133–144.  Available at http://dl.acm.org/citation.cfm?id=2448936.2448946.
  * [20] Andrés Letelier, Jorge Pérez, Reinhard Pichler & Sebastian Skritek (2013): _Static Analysis and Optimization of Semantic Web Queries_.  ACM Trans. Database Syst. 38(4), pp. 25:1–25:45, 10.1145/2500130.  Available at http://doi.acm.org/10.1145/2500130.
  * [21] Shuai Ma, Yang Cao, Wenfei Fan, Jinpeng Huai & Tianyu Wo (2014): _Strong Simulation: Capturing Topology in Graph Pattern Matching_.  ACM Trans. Database Syst. 39(1), pp. 4:1–4:46, 10.1145/2528937.  Available at http://doi.acm.org/10.1145/2528937.
  * [22] Stephan Mennicke, Denis Nagel, Jan-Christoph Kalo, Niklas Aumann & Wolf-Tilo Balke (2017): _Reconstructing Graph Pattern Matches Using SPARQL_.  In: (LWDA) Conference Proceedings, Rostock, Germany, September 11-13, 2017., p. 152.  Available at http://ceur-ws.org/Vol-1917/paper24.pdf.
  * [23] Tova Milo & Dan Suciu (1999): _Index Structures for Path Expressions_.  In: Proceedings of the 7th International Conference on Database Theory, ICDT ’99, Springer-Verlag, London, UK, UK, pp. 277–295.  Available at http://dl.acm.org/citation.cfm?id=645503.656266.
  * [24] Mohamed Morsey, Jens Lehmann, Sören Auer & Axel-Cyrille Ngonga Ngomo (2011): _DBpedia SPARQL Benchmark – Performance Assessment with Real Queries on Real Data_.  In: The Semantic Web – ISWC 2011, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 454–469, 10.1007/978-3-642-25073-6_29.
  * [25] Davide Mottin, Matteo Lissandrini, Yannis Velegrakis & Themis Palpanas (2016): _Exemplar Queries: A New Way of Searching_.  The VLDB Journal 25(6), pp. 741–765, 10.1007/s00778-016-0429-2.  Available at https://doi.org/10.1007/s00778-016-0429-2.
  * [26] Yavor Nenov, Robert Piro, Boris Motik, Ian Horrocks, Zhe Wu & Jay Banerjee (2015): _RDFox: A Highly-Scalable RDF Store_ , pp. 3–20.  Springer International Publishing, 10.1007/978-3-319-25010-6_1.  Available at https://doi.org/10.1007/978-3-319-25010-6_1.
  * [27] Thomas Neumann & Gerhard Weikum (2009): _Scalable Join Processing on Very Large RDF Graphs_.  In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09, ACM, New York, NY, USA, pp. 627–640, 10.1145/1559845.1559911.  Available at http://doi.acm.org/10.1145/1559845.1559911.
  * [28] Jorge Pérez, Marcelo Arenas & Claudio Gutierrez (2009): _Semantics and Complexity of SPARQL_.  ACM Trans. Database Syst. 34(3), pp. 16:1–16:45, 10.1145/1567274.1567278.  Available at http://doi.acm.org/10.1145/1567274.1567278.
  * [29] François Picalausa, Yongming Luo, George H. L. Fletcher, Jan Hidders & Stijn Vansummeren (2012): _A Structural Approach to Indexing Triples_.  In: Proceedings of the 9th International Conference on The Semantic Web: Research and Applications, ESWC’12, Springer-Verlag, Berlin, Heidelberg, pp. 406–421, 10.1007/978-3-642-30284-8_34.  Available at http://dx.doi.org/10.1007/978-3-642-30284-8_34.
  * [30] Eric Prud’hommeaux & Seaborne, Andy (2008): _SPARQL Query Language for RDF_.  Technical Report, W3C.  Available at https://www.w3.org/TR/rdf-sparql-query/.
  * [31] Michael Schmidt, Michael Meier & Georg Lausen (2010): _Foundations of SPARQL Query Optimization_.  In: Proceedings of the 13th International Conference on Database Theory, ICDT ’10, ACM, New York, NY, USA, pp. 4–33, 10.1145/1804669.1804675.  Available at http://doi.acm.org/10.1145/1804669.1804675.
  * [32] Miao Xie, Sourav S. Bhowmick, Gao Cong & Qing Wang (2017): _PANDA: toward partial topology-based search on large networks in a single machine_.  The VLDB Journal 26(2), pp. 203–228, 10.1007/s00778-016-0447-0.
  * [33] Lei Zou, Jinghui Mo, Lei Chen, M. Tamer Özsu & Dongyan Zhao (2011): _gStore: Answering SPARQL Queries via Subgraph Matching_.  Proc. VLDB Endow. 4(8), pp. 482–493, 10.14778/2002974.2002976.  Available at http://dx.doi.org/10.14778/2002974.2002976.