Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

M. Besta, R. Gerstenberger, E. Peter, M. Fischer, M. Podstawski, C. Barthels, G. Alonso, T. Hoefler:

 Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries

(ACM Comput. Surv.. Vol 56, Nr. 2, Association for Computing Machinery, ISSN: 0360-0300, Sep. 2023)

Publisher Reference


Numerous irregular graph datasets, for example social networks or web graphs, may contain even trillions of edges. Often, their structure changes over time and they have domain-specific rich data associated with vertices and edges. Graph database systems such as Neo4j enable storing, processing, and analyzing such large, evolving, and rich datasets. Due to the sheer size and irregularity of such datasets, these systems face unique design challenges. To facilitate the understanding of this emerging domain, we present the first survey and taxonomy of graph database systems. We focus on identifying and analyzing fundamental categories of these systems (e.g., document stores, tuple stores, native graph database systems, or object-oriented systems), the associated graph models (e.g., Resource Description Framework or Labeled Property Graph), data organization techniques (e.g., storing graph data in indexing structures or dividing data into records), and different aspects of data distribution and query execution (e.g., support for sharding and Atomicity, Consistency, Isolation, Durability). Fifty-one graph database systems are presented and compared, including Neo4j, OrientDB, and Virtuoso. We outline graph database queries and relationships with associated domains (NoSQL stores, graph streaming, and dynamic graph algorithms). Finally, we outline future research and engineering challenges related to graph databases.


download article:
access preprint on arxiv:

Recorded talk (best effort)



  author={Maciej Besta and Robert Gerstenberger and Emanuel Peter and Marc Fischer and MichaƂ Podstawski and Claude Barthels and Gustavo Alonso and Torsten Hoefler},
  title={{Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries}},
  journal={ACM Comput. Surv.},
  publisher={Association for Computing Machinery},