Relational-Techniques-for-Graph-Processing.md

Graph Processing Using Relational Operators

Worst-Case Optimal Join (WCOJ) Algorithms and Factorized Query Processing

• [WCOJ]: worst-case optimal joins
• [FACT]: factorized query processing

Lectures and Tutorials

• GraphflowDB and Modern Query Processing Techniques for GDBMSs, 1-hour lecture by Semih Salihoglu at Pinterest Labs (2021) [WCOJ] [FACT]
• From joins to aggregates and optimization problems (slides), lecture by Dan Olteanu (2018) [WCOJ] [FACT]
• From joins to aggregates and optimization problems, lectures series by Dan Olteanu (2018) [WCOJ] [FACT]
• Factorised databases, slides, short lecture by Dan Olteanu (2017) [FACT]
• SIGMOD 2020 tutorial: Optimal Join Algorithms Meet Top-k [WCOJ]
• LIquid: Soul of a New Graph Database by Scott Meyer, presented at the University of Waterloo's DSG Seminar Series
  • YouTube
• Relational databases can handle graphs too! Experiences with optimizing the Umbra RDBMS for LDBC SNB BI (slides) by Altan Birler (Technische Universität München), presented at the 15th LDBC TUC

Papers

• ⚡️ Graph Processing in RDBMSs by Kangfei Zhao, Jeffrey Xu Yu (IEEE Data Eng. Bull., 2017)

Papers on worst-case optimal joins

Theory

• Worst-Case Optimal Join Algorithms (PODS 2012)
• Skew Strikes Back: New Developments in the Theory of Join Algorithms (SIGMOD Record 2013)
• Worst-Case Optimal Join Algorithms (Journal of the ACM 2018)
• Worst-Case Optimal Graph Joins in Almost No Space (SIGMOD 2021)
• Optimizing One-Time and Continuous Subgraph Queries using Worst-Case Optimal Joins (ACM TODS 2021)

Implementation

Papers from the University of Waterloo:

• Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows by Khaled Ammar et al. (VLDB 2017)
• Optimizing subgraph queries by combining binary and worst-case optimal joins by Amine Mhedhbi et al. (VLDB 2019)
• GRainDB: A Relational-core Graph-Relational DBMS (recording) by Guodong Jin et al. (CIDR 2022)
  • GRainDB: A Hybrid Graph-Relational DBMS (recording) by Semih Salihoglu (LDBC TUC 2021)
• Integrating Column-Oriented Storage and Query Processing Techniques Into Graph Database Management Systems by Pranjal Gupta et al. (VLDB 2021)
• Making RDBMSs Efficient on Graph Workloads Through Predefined Joins by Guodong Jin and Semih Salihoglu (VLDB 2022)

Other papers:

• Adopting Worst-Case Optimal Joins in Relational Database Systems Michael Freitag et al. (VLDB 2020): WCOJs in the context of the Umbra compiled columnar RDBMS
• Towards Multi-way Join Aware Optimizer in SAP HANA by Sungheun Wi et al. (VLDB 2020)
• A Worst-Case Optimal Join Algorithm for SPARQL by Aidan Hogan et al. (ISWC 2019)

Papers on graph analytics

• The case against specialized graph analytics engines (CIDR 2015), a paper showing how implementing graph algorithms (SSSP, PageRank, connected components) in T-SQL (Microsoft SQL Server) can outperform the implementations of dedicated graph analytics engines
• In-database connected component analysis (ICDE 2020), a connected components implementation in SQL

Papers on data structures and indexing

• A+ Indexes: Tunable and Space-Efficient Adjacency Lists in Graph Database Management Systems (ICDE 2020)

Loosely related papers/talks

• The Relational Data Borg is Learning, VLDB 2020 keynote
  • Slides, part 1
  • Slides, part 2

Factorized joins

• Factorized Databases (SIGMOD Record 2016)

Relational databases and property graphs

• On Directly Mapping Relational Databases to Property Graphs, AMW 2019
• SAP HANA Graph: blog post, tutorial, using the CREATE GRAPH WORKSPACE language construct