Source-linked AI summary
Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries
Maciej Besta, Robert Gerstenberger, Emanuel Peter, Marc Fischer, Michał Podstawski, Claude Barthels, Gustavo Alonso, Torsten Hoefler
TL;DR
Large graph workloads are difficult because graphs can be massive, irregular, dynamic, and richly attributed, while graph database systems must support varied query and management requirements. This paper develops the first survey and taxonomy of graph databases, compares 51 systems across their designs, models, organization, distribution, and query execution, and identifies performance patterns and open challenges.
Problem
Graph database systems face unique design challenges when managing large, evolving, richly attributed graphs with irregular computation and both local and global queries.
Method
The paper presents the first taxonomy of graph databases and uses it to survey, categorize, and compare 51 systems across system design, graph models, data organization, distribution, transactions, and queries.
Results
The survey identifies relationships among graph data organization, database type, and performance, with non-graph models often favoring transactional updates and native graph stores often favoring read-only workloads.
Takeaways & Limitations
The taxonomy provides a framework for researchers and practitioners to understand graph database designs and select or develop systems for different graph workloads.
Takeaways & Limitations
The survey notes that hypergraph and simple directed-graph models are used by very few systems and are therefore less relevant to practitioners.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Graph databases address the scale, irregularity, dynamism, and rich data of modern graph workloads. This survey introduces a taxonomy and applies it to graph database systems, related queries, and future design challenges.
- Motivation: Graph algorithms are difficult to design because processed graphs can be large, poorly localized, and irregularly communicating.These difficulties increase for dynamic graphs with rich properties or labels on vertices and edges.
- Motivation: Graph databases support storing, processing, and analyzing large, evolving, and rich graph datasets.They must handle both local queries on small graph regions and global queries over large portions of a graph, while addressing low latency and high throughput.
- Survey scope: The survey presents a taxonomy covering graph database design, data models and organization, data distribution, transactions, and queries.These areas correspond to general engine structure, graph representation and storage, distribution across servers, and extracting useful information through queries.
- Contributions: The work provides the first taxonomy of graph databases and uses it to survey, categorize, and compare 51 systems.It also discusses selected system designs, related graph queries and workloads, and future design challenges.
- Related work: Earlier surveys addressed graph database history, data models, structures, query languages, integrity constraints, and basic landscape concepts.This work extends that literature with a system-focused taxonomy and comparison.
2 GRAPH DATABASES AND OTHER CLASSES OF GRAPH SYSTEMS
Graph databases overlap with other database and graph-processing systems but differ in their data models, update complexity, and database-management requirements. The survey positions graph databases relative to NoSQL stores, graph streaming frameworks, and static graph-processing systems.
- Scope: Graph databases are defined as systems designed to manage graph-like data with persistent storage, data independence, integrity, and consistency.The survey compares them with other systems that can also store and process dynamic graphs.
- Database classes: NoSQL stores include native graph databases as well as wide-column, document, and key-value systems, and the survey considers graph-maintenance uses of these classes.The systems primarily differ in their storage backends, which influence data organization and other design aspects.
- Graph streaming: Graph streaming frameworks process streams of graph updates, whereas graph databases commonly support richer models such as LPG or RDF with typed vertices, edges, and arbitrary properties.Graph streaming commonly uses simpler graphs with weights and sometimes timestamps.
- Graph streaming: Graph databases additionally address transactions, persistence, data independence, integrity, and consistency, which are less related to graph streaming frameworks.These requirements distinguish database-management systems from update-stream processing frameworks.
- Static graph processing: Static graph-processing systems usually emphasize static, simple graphs, unlike graph databases that handle evolving graphs with rich attached data.The survey notes vertex-centric, edge-centric, and linear-algebra paradigms among static graph analytics.
3 GRAPH DATA MODELS IN THE LANDSCAPE OF GRAPH DATABASES
Graph databases use multiple conceptual and physical representations to model rich, irregular data. The section covers simple graphs, hypergraphs, labeled property graphs, RDF, transformations between models, and storage-oriented data models.
- Simple Graph Model: Simple graphs model vertices and edges, while adjacency matrices and lists represent vertex connectivity.An adjacency matrix uses O(n^2) space and O(1) connectivity checks; adjacency lists use O(n+m) space and inspect a vertex’s adjacency list.
- Hypergraph Model: Hypergraphs generalize graphs by allowing each edge to join any non-empty subset of vertices.Hypergraphs are rarely used in graph databases, with HyperGraphDB described as a system focused on storing and querying them.
- Labeled Property Graph Model: Labeled Property Graphs augment vertices and edges with labels and arbitrary key-value properties, and may permit multiple identical edges.The survey states that its considered systems use LPG variants except RDF systems or when otherwise noted.
- RDF Model: RDF represents information as triples consisting of a subject, predicate, and object, using URIs, blank nodes, or literals.RDF databases are therefore commonly called triple stores and support connections between identifiers and literals.
- Transformations between LPG and RDF: LPG-to-RDF transformation maps vertices to URIs, properties to predicate-object triples, edges to adjacent-vertex links, and labels to label triples.When vertices and edges have one label, labels can instead be incorporated into identifiers; RDF-to-LPG conversion is more complex and may increase graph size.
- Storage-Oriented Models: Graph databases also use non-graph storage models, including key-value pairs, documents, tuples, relations, tables, and objects.The survey briefly summarizes how these models represent graphs rather than reviewing their underlying database systems extensively.
4 QUERIES & WORKLOADS IN THE LANDSCAPE OF GRAPH DATABASES
Graph database queries range from local operations on individual elements to global analytics over the whole graph. The survey relates these scopes to OLTP, OLAP, LDBC workloads, graph-query families, and bulk loading.
- Workload Classes: OLTP queries are small, interactive, transactional, and local, whereas OLAP queries are complex, global, and generally non-interactive.Local examples include lookups and updates of a few vertices or edges; OLAP spans the graph.
- Query Scopes: The survey analyzes query scope from local queries and neighborhoods through traversals to global graph analytics.These scopes are presented for LPG access and ordered by increasing scope.
- Query Scopes: Global graph analytics consider the whole graph and support applications such as threat detection and computational chemistry.Many graph databases and graph-processing systems support such large-scale queries.
- LDBC Workloads: LDBC defines interactive, Business Intelligence, and graph analytics workloads for standardizing graph-database performance measurement.Interactive workloads emphasize reads and transactional updates, BI workloads use large-volume aggregation, and analytics workloads specify six graph algorithms.
- LDBC Workloads: LDBC maps interactive workloads to local, neighborhood, and traversal queries, while BI spans traversals to global analytics and graph analytics targets global analytics.This mapping connects benchmark workload classes to the survey’s query-scope taxonomy.
- Graph Query Families: Graph-query theory includes simple and complex graph pattern matching, path queries, and related query families.Complex pattern matching extends simple matching with aggregation and projection.
- Additional Workloads: Bulk-input benchmarks measure the time required to load an input dataset into a database, especially during migration between systems.This workload is distinct from graph-query execution after data has been loaded.
5 TAXONOMY OF GRAPH DATABASE SYSTEMS
The survey’s taxonomy categorizes graph database systems through backend type, data organization, and query execution. It begins by grouping systems according to storage backends because backend design affects other system dimensions.
- Taxonomy Dimensions: The taxonomy’s three main dimensions are general backend type, data organization, and query execution.Figures 8 and 9 summarize the considered database types and the taxonomy’s elements.
- Backend Types: General backend types primarily differ by storage backend, such as triple stores or document stores.This grouping supports further analysis because backend design influences many other graph-database aspects.
- Backend Types: Backend-based systems adapt tuple, document, key-value, wide-column, and relational technologies to store graph data and add graph-query frontends.The survey uses backend type as the starting point for categorizing graph database systems.
Row RDBMS
The survey classifies graph databases across storage organization, graph models, indexing, distribution, optimizations, and query execution. These dimensions connect physical design choices with graph-query performance and supported workloads.
- Taxonomy dimensions: The taxonomy covers graph structure representation, conceptual data models, indexes, data distribution, and common optimizations.
- Data organization: Adjacency-list or adjacency-matrix representation directly affects query performance, while supported RDF or LPG models influence query languages and data layout.
- Indexes: Indexes are analyzed by use case and implementation, including neighborhood, graph-element, structural, and internal or external data indexes.
- Data distribution: Distributed systems may replicate data for fault tolerance or shard it across servers to reduce the amount of data used by each server.
- Optimizations: Common optimizations include records, lightweight edges, and direct pointers, which can accelerate connectivity queries and reduce storage overhead.
- Query execution: Query execution is categorized by concurrent and parallel queries, ACID transactions, supported query classes, and query languages.
6 ANALYSIS OF DATABASE SYSTEMS
The survey compares selected graph database systems using its taxonomy, covering backends, models, storage organization, query languages, and system features. It also distinguishes RDF and tuple-store variants by how they represent and annotate graph data.
- System comparison: Selected systems are surveyed by graph model, data organization, storage organization, and features summarized in comparison tables.
- System selection: System selection combines popularity in each backend category with interesting research systems and available technical design details.
- RDF stores: RDF stores organize data into triples, while Cray Graph Engine stores quads whose fourth element identifies the graph.
- RDF extensions: AllegroGraph attaches immutable arbitrary attributes to triples, whereas BlazeGraph’s RDF* attaches triples to triple predicates for representing LPG edges and edge properties.
- Tuple stores: Tuple stores generalize RDF stores by allowing tuples of arbitrary length rather than restricting records to triples or quads.
6.4 Key-Value Stores
The survey describes graph storage using key-value, document, wide-column, relational, and related backends. These systems encode graph entities in cells, documents, rows, or tables, with backend-specific choices for links and edge organization.
- Key-value stores: Key-value graph systems store vertices and graph elements as values addressed by keys, including distributed cells in Trinity and uniquely identified atoms in HyperGraphDB.
- Document stores: Document stores represent vertices as documents with labels and properties, while edge storage is system-dependent and may use source or destination documents.
- Document stores: OrientDB distinguishes regular edge documents with properties from lightweight edges stored directly in adjacent vertex documents as document identifiers.
- Document stores: ArangoDB separates vertex and edge collections, and edge-type-specific collections can avoid scanning unrelated edge types during retrieval.
- Wide-column stores: Titan and JanusGraph use wide-column backends where each vertex is a row and each property or adjacent edge occupies a separate cell.
- Relational stores: Relational graph systems represent vertices with table rows and relationships between rows as edges, with properties stored in separate key-value structures.
6.8 Object-Oriented Databases
The survey contrasts object-oriented and native graph designs with map- and matrix-based structures and multi-model data hubs. It emphasizes how physical links, indexes, and workload assumptions shape graph access.
- Object-oriented databases: Object-oriented databases model, store, and manage data as language objects used by object-oriented programming languages.
- Object-oriented databases: VelocityGraph stores vertices, edges, and properties as C# objects containing references to other objects, with unique identifiers for physical storage locations.
- Native graph databases: Neo4j implements LPG with fixed-size vertex and edge records, linked property lists, and doubly linked adjacency lists.
- Native graph databases: Neo4j’s direct pointers allow neighborhood queries and traversals to follow physical neighbor locations without an index, making complexity depend on the visited subgraph rather than graph size.
- Indexed graph storage: Sparksee uses B+ trees and bitmaps for properties, labels, and connectivity, including bitwise operations for combining property filters.
- Indexed graph storage: GBase compresses an adjacency matrix into blocks to retrieve selected neighbors without the O(n^2) storage overhead of an uncompressed matrix.
- Data hubs: Data hubs combine multiple data models and storage designs, while Virtuoso provides relational, RDF, and document capabilities but stores graphs in RDF format.
7 TAKEAWAYS, INSIGHTS, FUTURE DIRECTIONS
The section presents insights about the surveyed systems for practitioners and researchers, alongside suggestions for future developments and research.
- The section offers insights about the described graph database systems.
- The insights address both practitioners and researchers.
- Suggestions for future developments and research are interleaved with the discussion.
7.1 Discussion, Takeaways, and Insights on Data Organization
The discussion compares conceptual models and data organization choices across graph databases. It highlights LPG and RDF tradeoffs, neighborhood-oriented layouts, and unresolved design questions.
- Conceptual graph models: RDF supports simple subject–predicate–object triples, whereas LPG supports labels and properties on vertices and edges.RDF is standardized; LPG is not standardized but is becoming standardized through SQL/PGQ and GQL.
- Conceptual graph models: Some RDF systems also support LPG, while many non-graph database classes offer only LPG.The surveyed systems include exceptions and recent work on unifying RDF and LPG.
- Conceptual graph models: LPG and RDF design tradeoffs remain unclear across workload classes and storage and distribution constraints.The paper proposes formal runtime and storage models followed by extensive evaluation.
- Data organization: Most surveyed systems use adjacency-list variants because neighborhood traversal is efficient and straightforward.RDF, relational, and data-hub systems do not explicitly use adjacency lists in the analyzed designs.
- Data organization: No analyzed system uses an uncompressed adjacency matrix because its O(n^2) space cost is inefficient for sparse graphs.Systems using adjacency matrices instead focus on compression to reduce storage and query overhead.
- Data organization: Adjacency-list implementations can use neighborhood indexes requiring O(n) space for a graph with n vertices.These indexes avoid scanning all edges to find a vertex’s neighbors.
7.2 Discussion, Takeaways, and Insights on Data Optimizations
Graph database optimization depends on storage layout, record linking, indexing, and distribution choices, each creating workload-specific trade-offs. The survey identifies broad opportunities in sharding, replication, higher-order indexes, and systematic performance comparisons.
- Data organization: Most systems use records for vertices, while edges may be stored separately or with adjacent vertices; properties may reside directly in records or through pointers.Some systems instead distribute vertex and edge information across separate property or label indexes.
- Data organization: Direct pointers accelerate traversals by avoiding index lookups, whereas IDs simplify updates when records move because only the address index changes.The preferred choice depends on the workload’s read/write ratio: pointers favor reads, while IDs can make writes more efficient.
- Data distribution: Almost all systems support multi-server operation and replication, but some native graph databases provide replication without sharding.The survey links this gap to the greater maturity of non-graph backends and identifies automated partitioning of large collections or documents as a research opportunity.
- Research opportunities: The survey proposes partial adjacency-matrix replication for graph OLAP and richer indexes for higher-order structures such as triangles.These directions target workloads including BFS, clique mining, dense-subgraph discovery, and clustering.
- Performance: A broad performance comparison of index implementations across workloads remains an open research opportunity, while existing studies report workload-dependent performance differences between backend types.Non-graph data models often perform better for transactional graph updates, whereas native graph stores often perform better on read-only workloads and parallelized global analytics.
- Data organization: Record-based layouts favor retrieving most vertex or edge information, while index-based layouts can be better for retrieving a single property.Records improve locality but may fetch unnecessary data; property indexes can reduce data retrieval while causing more random access.
7.3 Discussion and Takeaways on Query Execution
The survey finds broad support for concurrent OLTP, parallel OLAP, ACID transactions, and graph query languages, but concurrent OLAP/OLTP execution and topology-aware optimization remain limited. Query-execution evidence is also constrained because most systems disclose data layouts more readily than execution engines.
- Concurrency and parallelization: Almost all systems support concurrent OLTP queries, while fewer support parallel OLTP execution, emphasizing throughput over single-query latency.The Cray Graph Engine is a notable exception: it lacks concurrent queries but supports parallel single-query execution.
- Concurrency and parallelization: OLAP queries are usually parallelized because they often access all vertices and edges, making sequential execution prohibitively long.Existing work on traversals and centrality analyses facilitates this parallelization.
- Concurrency and parallelization: Concurrent OLAP and OLTP execution is not widely supported; snapshot-based systems isolate analytics, while Neo4j leaves OLAP inconsistencies to the client by default.LiveGraph and Weaver use consistent graph snapshots while OLTP operations modify other versions.
- Related systems: Streaming graph frameworks can be up to orders of magnitude faster than graph databases, although they often use simpler graph models rather than LPG or RDF.This comparison connects graph databases with a related but distinct class of dynamic graph systems.
- Open challenges: Topology-aware data distribution, hardware acceleration, and optimized collective communication remain open opportunities for graph database workloads.The survey identifies limited work on network-aware distribution and hardware designs such as FPGAs, SmartNICs, and processing in memory.
- ACID transactions: Support for ACID transactions is widespread, but all considered document and RDBMS graph databases support ACID compared with only around half of key-value and wide-column systems.The survey attributes this difference possibly to the greater maturity of transaction designs in some backends.
- Graph query languages: Backend classes correlate with graph query languages: triple stores with SPARQL, document and wide-column stores with Gremlin, RDBMS with SQL, and native LPG stores commonly with Cypher.Supported query languages are primarily affected by the conceptual graph model.
7.4 Insights for Practitioners
Practitioner choice depends on schema knowledge, workload, and priorities such as predictable isolation behavior or peak graph-workload performance. The survey presents RDBMS and native graph backends as having different strengths rather than identifying one universally superior option.
- Open comparison: Whether RDBMS or native graph backends are more suitable remains unresolved because existing comparisons often focus on single workload classes and homogeneous graphs.The survey notes that these evaluations may not represent rich graphs or mixed workloads.
- System selection: RDBMS designs may be preferable when the data schema is known in advance, whereas graph databases may offer more performance when the schema is unknown.This distinction follows the survey’s comparison of established relational optimizations with graph-oriented flexibility.
- System selection: Non-graph backends generally provide more mature and predictable isolation behavior for standard workloads, while native graph systems are worth considering for highest-performance purely graph workloads.The survey frames this as a trade-off between predictable behavior and peak graph-workload performance.
8 CONCLUSION
The paper surveys and organizes the diverse graph database landscape for both researchers and practitioners. Its taxonomy covers varied models, representations, design choices, queries, and workloads to support system selection and design.
- Conclusion: The work provides the first survey and taxonomy of graph databases across their models, representations, design choices, queries, and workloads.It is intended to help researchers learn the field and help architects, developers, and project managers select systems or designs.