Literature on graph processing

This page lists scientific works on graph processing.

Dissertations and Master's thesis works

• Query, Analysis, and Benchmarking Techniques for Evolving Property Graphs of Software Systems by Gábor Szárnyas – PhD dissertation, BME (2019)
  • ⚡️ Chapter 2 contains the background for graph databases
  • ⭐️ Chapter 8 shows a mapping from openCypher queries to an extended relational algebra (it's also available as a concise preprint)
  • ⭐️ Section 10.5 summarizes the state of research (as of 2018) on mapping from graph queries to relational databases (see Table 10.2)
• 💫 Analysis and Comparison of Common Graph Query Languages by Martin Klampfer, TU Vienna (2020)
• 💫 A G-CORE Graph Query Language Interpreter by Georgiana Ciocirdel, CWI, VU Amsterdam (2018)
• Enabling Graph Analysis Over Relational Databases by Konstantinos Xirogiannopoulos – PhD dissertation, UMD (2019)

Papers

Graphs as relational data

• LIquid: The soul of a new graph database, Part 2: this part of LinkedIn Engineering's two-part series on the LIquid graph database discusses the representation of graphs as relational data and the limitations of naïve approaches (part 1 presents an object-oriented representation).

Graphs and SQL

• DuckPGQ: Bringing SQL/PGQ to DuckDB by Daniel ten Wolde, Gábor Szárnyas, Peter Boncz (VLDB 2023 demo)
• ⚡️ DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS (📺 slides, recording) by Daniel ten Wolde, Tavneet Singh, Gábor Szárnyas, Peter Boncz (CIDR 2023)
• ⚡️ Graph Processing in RDBMSs by Kangfei Zhao, Jeffrey Xu Yu (IEEE Data Eng. Bull., 2017)
  • Longer version: All-in-One: Graph Processing in RDBMSs Revisited (SIGMOD 2017)
• ⚡️ An Algebra and Equivalences to Transform Graph Patterns in Neo4j by Jürgen Hölsch, Michael Grossniklaus (GraphQ 2016)
• ⭐️ GraphGen: Adaptive Graph Processing using Relational Databases by Konstantinos Xirogiannopoulos
• ⭐️ Extending In-Memory Relational Database Engines with Native Graph Support by Mohamed S. Hassan, Tatiana Kuznetsova, Hyun Chai Jeong, Walid G. Aref, Mohammad Sadoghi (EDBT 2018) about GRFusion (SIGMOD demo), code
• 💫 Graph Pattern Matching – Do We Have to Reinvent the Wheel? by Andrey Gubichev, Manuel Then (GRADES 2014) 📺 slides
• Join Processing for Graph Patterns: An Old Dog with New Tricks by Dung T. Nguyen, Molham Aref et al. (GRADES 2015)
• G-SQL: Fast Query Processing via Graph Exploration by Hongbin Ma et al. (VLDB 2016)
• Cytosm: Declarative Property Graph Queries Without Data Migration by Benjamin A. Steer et al. (GRADES 2017)
• PGQL: a property graph query language by Oskar van Rest et al. (GRADES 2016)
• Extending SQL for Computing Shortest Paths by Dean De Leo and Peter Boncz (GRADES 2017), talk at the LDBC TUC 2017, 📺 slides
• GraphWrangler: An Interactive Graph View on Relational Data, demo paper (SIGMOD 2019)
• Towards compiling graph queries in relational engines (DBPL 2019)

Graphs and SPARQL

• G-SPARQL: a hybrid engine for querying large attributed graphs by Sherif Sakr, Sameh Elnikety, Yuxiong He (CIKM 2012)

Semantics of query languages

• openCypher
  • Cypher: An Evolving Query Language for Property Graphs by Nadime Francis et al. (SIGMOD 2018), technical report on semantics
  • Updating Graph Databases with Cypher by Alastair Green et al. (VLDB 2019)
• G-CORE
  • G-CORE: A Core for Future Graph Query Languages by Renzo Angles et al. (SIGMOD 2018)

Overview papers and posts

• ⚡️ Graph query languages by Gábor Szárnyas (2021), the top 10 graph query languages
• Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries by Maciej Besta et al. (preprint, 2020)
• Foundations of Modern Graph Query Languages by Renzo Angles et al. (ACM CSUR, 2017)
• The ubiquity of large graphs and surprising challenges of graph processing: Extended survey by Siddhartha Sahu et al. (VLDBJ 2020)

Talks

• ⚡️ 📺 Graph database applications with SQL/PGQ by Jan Michels, Andy Witkowski, Oracle (2020)
• ⚡️ 📺 Property Graph Extensions for the SQL Standard by Vasileios Trigonakis and Oskar van Rest, Oracle (LDBC TUC 2019)

Related

• ⚡️ 📺 PGQL Introduction and Deep Dive, an overview of PGQL by Melli Annamalai and Ryota Yamanaka, Oracle (2020)

Graph query engine implementations

• Morpheus: Cypher for Apache Spark (abandoned) 📺 slides
• AgensGraph
• Apache AGE