Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges

The last decade has seen an emergence of numerous specialized graph DBMSs (GDBMSs) as well as graph-optimized extensions of RDBMSs. In addition, several query processing techniques, such as worst-case optimal join algorithms and factorized query processing, have been introduced in the context of RDBMSs, which find their best applications on graph workloads. In this tutorial, we review the recent advances in query processing techniques for graph workloads. For each technique, we first overview the theoretical foundations. Then, we overview how DBMSs implement these techniques. Finally, we discuss the open challenges for existing implementation approaches.