Every database type we have explored so far treats relationships as secondary.

Relational databases store relationships in foreign keys that must be joined at query time. Document databases embed related data or store references that require multiple queries. Wide-column databases denormalize relationships into the data model itself.

Graph databases flip this paradigm. Relationships become first-class citizens, stored and indexed just like the data itself.

Consider LinkedIn's "People You May Know" feature. To find potential connections, you need to traverse the social network: find friends of friends who are not already your friends, filter by shared interests or employers, and rank by connection strength.

In a relational database, each "hop" in the graph requires a JOIN operation. For a query that traverses 3-4 hops across millions of users, you are looking at joining billions of row pairs. Performance degrades exponentially with depth.

In a graph database, these traversals are what the system is optimized for. Relationships are stored as direct pointers between nodes. Traversing from one node to its neighbors is a pointer lookup, not a table scan.

The query "friends of friends of Alice" executes in milliseconds, regardless of how many total users exist in the system.

The Property Graph Model

The property graph model is the most common way to represent data in graph databases. It consists of three elements: nodes, relationships, and properties.

Nodes

Nodes represent entities in your domain. They are similar to rows in a relational table or documents in a document database. Each node:

Labels like "Person," "Company," and "Skill" categorize nodes. A node can have multiple labels, allowing flexible categorization.

Relationships

Relationships connect nodes. Unlike foreign keys in relational databases, relationships are stored as explicit connections between nodes. Each relationship:

Note that relationships have their own properties. The FRIENDS_WITH relationship has a "since" property recording when the friendship started. The KNOWS relationship has a "level" property indicating proficiency.

Properties

Both nodes and relationships can have properties, which are key-value pairs storing attributes:

Properties can be strings, numbers, booleans, dates, or arrays of these types.

Why This Model Matters

The property graph model closely matches how we naturally think about many domains:

When your domain is naturally a graph, modeling it as a graph is intuitive. You draw nodes and edges on a whiteboard, and that becomes your database schema.

Graph Database Architecture

Graph databases use specialized storage and indexing structures to make relationship traversal fast.

Index-Free Adjacency

The key architectural principle is index-free adjacency: each node directly stores pointers to its adjacent nodes. No index lookup is required to find neighbors.

Compare this to relational databases:

The difference becomes dramatic for deep traversals. In a relational database, each hop requires at least an index lookup. In a graph database, each hop is a pointer dereference.

Relationship Storage

Relationships are stored as first-class objects with their own storage:

Each relationship record contains:

This linked-list structure allows traversing all relationships of a node without indexes.

Traversal Performance

Graph database performance is measured differently than relational databases:

The crucial insight: query time depends on the portion of the graph touched, not the total size. Finding friends of friends for a user with 100 friends touches ~10,000 nodes regardless of whether the total graph has 1 million or 1 billion nodes.

Query Languages

Graph databases use specialized query languages designed for expressing graph patterns and traversals.

Cypher (Neo4j)

Cypher is a declarative pattern-matching language. You describe the pattern you want to find, and the database figures out how to find it.

Basic pattern matching:

The ASCII-art syntax is intentional: (node)-[:RELATIONSHIP]->(node) visually represents the graph pattern.

Creating data:

Aggregations:

Variable-length paths:

Gremlin (Apache TinkerPop)

Gremlin is an imperative traversal language. You describe step-by-step how to traverse the graph.

Gremlin reads like a pipeline: start with vertices (V), filter by property, traverse out, deduplicate, extract values.

SPARQL (RDF)

SPARQL is used for RDF (Resource Description Framework) graphs, common in semantic web and knowledge graphs.

Language Comparison

Use Cases

Graph databases excel in domains where relationships are the primary focus of queries.

Social Networks

The classic graph use case. Users are nodes, friendships are relationships.

Typical queries:

Recommendation Engines

Find items similar to what a user has liked, or items that similar users have liked.

Fraud Detection

Fraud often involves networks of connected accounts sharing devices, addresses, or payment methods.

Knowledge Graphs

Model entities and their relationships for semantic search and question answering.

Access Control

Model permissions as a graph to answer "Can user X access resource Y?"

Popular Graph Databases

Neo4j

The most popular graph database, with a mature ecosystem and the Cypher query language.

Amazon Neptune

AWS's managed graph database service supporting both property graphs and RDF.

JanusGraph

Open-source, distributed graph database designed for large-scale graphs.

ArangoDB

Multi-model database supporting graphs, documents, and key-value in one system.

Comparison

Performance Considerations

Traversal Depth

Query performance depends heavily on traversal depth and the number of relationships per node:

Graph databases handle depth 2-3 traversals easily. Depth 4+ requires careful consideration of filtering and limits.

Supernodes

Supernodes are nodes with an unusually high number of relationships (e.g., a celebrity with millions of followers). They can cause performance problems:

Mitigation strategies:

Indexing

While relationships are traversed without indexes, finding starting nodes requires indexes:

Always index properties used in initial node lookups (the starting point of traversals).

Scaling Graph Databases

Scaling graph databases is challenging because graphs are inherently connected. Partitioning a graph means cutting some relationships, which hurts performance for queries that cross partition boundaries.

Vertical Scaling

The simplest approach: use a bigger server. Neo4j can handle graphs with billions of nodes on a single large machine.

Read Replicas

Scale read throughput by replicating the graph:

Sharding (Challenging)

Partitioning a graph is hard because:

Approaches:

When sharding is acceptable:

When to Choose Graph Databases

Graph databases are the right choice when:

When to Consider Alternatives

Graph databases may not fit when:

Summary

Graph databases treat relationships as first-class citizens:

Key concepts:

The next chapter explores time-series databases, which are optimized for a completely different access pattern: data that is indexed by time and queried primarily with time-range filters and aggregations.