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

arXiv: https://arxiv.org/abs/1910.09017 · HTML: https://mlsanity.com/paper/1910.09017/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2019.

## Built on by (most cited first, 22 of 22)

- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding](https://mlsanity.com/paper/2409.03258/) (2024)
- [Aligning Large Language Models to a Domain-specific Graph Database for NL2GQL](https://mlsanity.com/paper/2402.16567/) (2024)
- [Agentic Medical Knowledge Graphs Enhance Medical Question Answering: Bridging the Gap Between LLMs and Evolving Medical Knowledge](https://mlsanity.com/paper/2502.13010/) (2025)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities](https://mlsanity.com/paper/2309.17255/) (2023)
- [HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers](https://mlsanity.com/paper/2311.18526/) (2023)
- [Synergizing Logical Reasoning, Knowledge Management and Collaboration in Multi-Agent LLM System](https://mlsanity.com/paper/2507.02170/) (2025)
- [Knowledge Graphs Querying](https://mlsanity.com/paper/2305.14485/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [The Ontoverse: Democratising Access to Knowledge Graph-based Data Through a Cartographic Interface](https://mlsanity.com/paper/2408.03339/) (2024)
- [Applying Text Embedding Models for Efficient Analysis in Labeled Property Graphs](https://mlsanity.com/paper/2507.10772/) (2025)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Scaling Knowledge Graphs for Automating AI of Digital Twins](https://mlsanity.com/paper/2210.14596/) (2022)
- [Knowledge Engineering for Wind Energy](https://mlsanity.com/paper/2310.00804/) (2023)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [From SQL to Knowledge Graphs: An LLM-Driven Multi-Agent Approach with Data Schema Improvement](https://mlsanity.com/paper/2608.26117/) (2026)
- [Graph Memory for LLM Agents: At What Cost? A Comparative Evaluation of Query, Ingest, and Update Performance Across Graph Database Engines](https://mlsanity.com/paper/2609.23315/) (2026)

## Abstract (arXiv)

Graph processing has become an important part of multiple areas of computer science, such as machine learning, computational sciences, medical applications, social network analysis, and many others. Numerous graphs such as web or social networks may contain up to trillions of edges. Often, these graphs are also dynamic (their structure changes over time) and 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 of such datasets, combined with the irregular nature of graph processing, 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., triple stores, tuple stores, native graph database systems, or object-oriented systems), the associated graph models (e.g., RDF 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 ACID). 51 graph database systems are presented and compared, including Neo4j, OrientDB, or Virtuoso. We outline graph database queries and relationships with associated domains (NoSQL stores, graph streaming, and dynamic graph algorithms). Finally, we describe research and engineering challenges to outline the future of graph databases.