  Graph database query languages feature expressive, yet computationally
expensive pattern matching capabilities. Answering optional query clauses in
SPARQL for instance renders the query evaluation problem immediately
Pspace-complete. Therefore, light-weight graph pattern matching relations, such
as simulation, have recently been investigated as promising alternatives to
more expensive query mechanisms like, e.g., computing subgraph isomorphism.
Still, graph pattern matching alone lacks expressive query capabilities: all
patterns are combined by usual join constructs, where more sophisticated
capabilities would be inevitable for making solutions useful to emerging
applications. In this paper we bridge this gap by introducing a new dual
simulation process operating on SPARQL queries. In addition to supporting the
full syntactic structure of SPARQL queries, it features polynomial-time pattern
matching to compute an overapproximation of query results from the database.
Moreover, to achieve runtimes competing with state-of-the-art database systems,
we develop a novel algorithmic solution to dual simulation graph pattern
matching, based on a system of inequalities that allows for several
optimization heuristics. Finally, we achieve soundness of our process for
SPARQL queries including UNION, AND and OPTIONAL operators not restricted to
well-designed patterns. Our experiments on synthetic and real-world graph data
promise a clear gain for graph database systems when incorporating the new dual
simulation techniques. In this supplement paper we present in detail all
proofs, discussions of experimental results, and complexity analysis for the
original paper "Fast Dual Simulation Processing of Graph Database Queries"
included in the Proceedings of the 35th IEEE International Conference on Data
Engineering (ICDE 2019), Macau, China.
