Graph Model — Graph Databases: Modeling… | OneNoughtOne

0/278

NoSQL DatabasesGraph Databases

Graph Databases: Modeling Connected Data

LevelAdvanced

Duration75 mins

TopicGraph Databases

1 / 5

Graph Model

When Relationships Are the Data

Consider a deceptively simple question: Who are the friends of my friends who work at the same company as me but whom I don't know yet? In a relational database, answering this requires multiple self-joins on a users table, intersections with employment records, and exclusion of existing connections. The query becomes baroque, the performance degrades exponentially with network size, and the semantic intent drowns in SQL gymnastics. Now consider how humans naturally think about this: start from me, traverse to my friends, traverse to their friends, filter by company, exclude those I already know. This is graph thinking —and graph databases are built to make this natural expression of connected queries not just possible, but efficient.

What You Will Learn

By the end of this page, you will understand the graph data model at a deep level—its mathematical foundations in graph theory, the property graph model used by modern graph databases, how graphs differ fundamentally from relational and document models, and why certain problems that are intractable in other paradigms become elegant in graph form.

Graph Theory Foundations

Before examining graph databases, we must establish the mathematical foundation upon which they rest. Graph theory—originated by Leonhard Euler in 1736 with his solution to the Seven Bridges of Königsberg problem—provides the formal framework for representing and analyzing connected structures. Formal Definition: A graph G is defined as an ordered pair G = (V, E) where: V is a set of vertices (also called nodes) E is a set of edges (also called relationships or links), where each edge connects two vertices This deceptively simple definition encompasses an enormous range of structures—from social networks to molecular diagrams, from transit systems to neural pathways, from organizational hierarchies to the World Wide Web itself.

Fundamental Graph Types
Graph Type	Definition	Real-World Example	Database Implication
Undirected Graph	Edges have no direction; (v₁, v₂) = (v₂, v₁)	Facebook friendships (mutual)	Relationship queries work bidirectionally
Directed Graph (Digraph)	Edges have direction; (v₁, v₂) ≠ (v₂, v₁)	Twitter follows (asymmetric)	Must specify traversal direction in queries
Weighted Graph	Edges carry numerical values	Road networks with distances	Supports shortest-path algorithms
Multigraph	Multiple edges between same vertex pair	Multiple flight routes between cities	Requires edge identification beyond endpoints
Hypergraph	Edges connect more than two vertices	Co-authorship (multiple authors per paper)	Extended property model needed
Bipartite Graph	Vertices split into two disjoint sets	Users and products in recommendations	Optimized join patterns in queries

Why Graph Theory Matters for Databases

Understanding graph theory isn't mere academic exercise. The algorithms developed over 300 years of graph theory—shortest paths (Dijkstra, Bellman-Ford), minimum spanning trees (Prim, Kruskal), centrality measures (PageRank, betweenness), community detection (Louvain, Girvan-Newman)—become directly applicable database operations. Graph databases don't reinvent these algorithms; they make them first-class citizens of the query language.

The Property Graph Model

While pure graph theory provides the mathematical foundation, modern graph databases implement the Property Graph Model—an extension that adds semantic richness without sacrificing the structural elegance of graphs. The property graph model introduces four key enhancements: 1. Labels (Types) Both vertices and edges can be assigned one or more labels that categorize them. A vertex might be labeled :Person, :Employee, and :Manager simultaneously. An edge might be labeled :WORKS_FOR or :MANAGES. Labels enable efficient filtering and indexing. 2. Properties (Attributes) Vertices and edges can carry key-value pairs as properties. A :Person vertex might have {name: "Alice", age: 32, email: "alice@example.com"}. An :EMPLOYED_BY edge might have {since: "2019-03-15", role: "Senior Engineer"}. Properties store the actual data. 3. Directed Relationships Edges always have direction (though they can be traversed in reverse). This models real-world asymmetry: Alice :FOLLOWS Bob doesn't imply Bob :FOLLOWS Alice. 4. Identities Every vertex and edge has a unique identifier, enabling precise reference and deduplication.

property-graph-example.txt
PROPERTY GRAPH: SOCIAL-PROFESSIONAL NETWORK
============================================
 
VERTICES (Nodes):
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n1                                                              │
│  Labels: [:Person, :Employee]                                        │
│  Properties: {                                                       │
│      name: "Alice Chen",                                             │
│      email: "alice@techcorp.com",                                    │
│      department: "Engineering",                                      │
│      joinedDate: "2019-03-15"                                        │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n2                                                              │
│  Labels: [:Person, :Employee, :Manager]                              │
│  Properties: {                                                       │
│      name: "Bob Singh",                                              │
│      email: "bob@techcorp.com",                                      │
│      department: "Engineering",                                      │
│      directReports: 5                                                │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n3                                                              │
│  Labels: [:Company]                                                  │
│  Properties: {                                                       │
│      name: "TechCorp Inc.",                                          │
│      industry: "Software",                                           │
│      founded: 2010,                                                  │
│      employees: 500                                                  │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
 
EDGES (Relationships):
(n1)-[:WORKS_FOR {since: "2019-03-15", role: "Senior Engineer"}]->(n3)
(n2)-[:WORKS_FOR {since: "2015-08-01", role: "Engineering Manager"}]->(n3)
(n1)-[:REPORTS_TO {since: "2020-01-01"}]->(n2)
(n1)-[:KNOWS {context: "colleague", strength: 0.8}]->(n2)
(n2)-[:KNOWS {context: "colleague", strength: 0.8}]->(n1)
 
GRAPH VISUALIZATION:
                        ┌─────────────┐
                        │  TechCorp   │
                        │  (Company)  │
                        └──────┬──────┘
                               │
              ┌────────────────┴────────────────┐
              │ WORKS_FOR            WORKS_FOR  │
              ▼                                 ▼
       ┌─────────────┐    REPORTS_TO    ┌─────────────┐
       │    Alice    │ ───────────────► │     Bob     │
       │  (Person,   │                  │  (Person,   │
       │  Employee)  │ ◄──────────────► │  Employee,  │
       └─────────────┘      KNOWS       │  Manager)   │
                                        └─────────────┘

Property Graphs vs RDF

An alternative graph model is RDF (Resource Description Framework), which represents everything as subject-predicate-object triples. RDF excels at semantic web applications and knowledge graphs where standardized vocabularies matter. Property graphs, used by Neo4j, Amazon Neptune, and TigerGraph, offer more intuitive modeling for application development and typically provide better write performance. The choice depends on whether you need semantic interoperability (RDF) or application-centric flexibility (property graphs).

Why Not Just Use Relational?

A natural question arises: relational databases can model relationships with foreign keys. Why introduce an entirely new paradigm? The answer lies in performance at depth . Consider querying "friends of friends of friends" (3-hop traversal) in a social network of 1 million users where each person has an average of 200 connections. The Relational Approach:

relational-friends-of-friends.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
-- Friends of friends of friends (3-hop traversal)
-- Assuming: users(id, name), friendships(user_id_1, user_id_2)
 
SELECT DISTINCT u4.name
FROM users u1
JOIN friendships f1 ON u1.id = f1.user_id_1
JOIN users u2 ON f1.user_id_2 = u2.id
JOIN friendships f2 ON u2.id = f2.user_id_1
JOIN users u3 ON f2.user_id_2 = u3.id
JOIN friendships f3 ON u3.id = f3.user_id_1
JOIN users u4 ON f3.user_id_2 = u4.id
WHERE u1.id = 12345
  AND u4.id NOT IN (
      -- Exclude the origin user themselves
      12345  
  )
  AND u4.id NOT IN (
      -- Exclude direct friends (1-hop)
      SELECT f.user_id_2 FROM friendships f WHERE f.user_id_1 = 12345
  )
  AND u4.id NOT IN (
      -- Exclude friends of friends (2-hop)
      SELECT f2.user_id_2
      FROM friendships f1
      JOIN friendships f2 ON f1.user_id_2 = f2.user_id_1
      WHERE f1.user_id_1 = 12345
  );
 
-- Performance characteristics:
-- - 6 JOINs on potentially millions of rows
-- - 3 subqueries for exclusion logic
-- - Cartesian product explosion at each hop
-- - Estimated I/O: Thousands of disk seeks
-- - Typical execution time: 30-60 seconds

The Graph Approach:

graph-friends-of-friends.cypher

Cypher

// Friends of friends of friends (3-hop traversal)
// Using Neo4j's Cypher query language
 
MATCH (me:Person {id: 12345})-[:FRIEND*3..3]-(distantFriend:Person)
WHERE NOT (me)-[:FRIEND]-(distantFriend)     // Not direct friends
  AND NOT (me)-[:FRIEND*2..2]-(distantFriend) // Not 2-hop friends
  AND me <> distantFriend                    // Not self
RETURN DISTINCT distantFriend.name
 
// Performance characteristics:
// - Native graph traversal following pointer chains
// - Only touches nodes actually connected to origin
// - Index-free adjacency (O(1) relationship lookup)
// - Estimated I/O: Hundreds of memory accesses
// - Typical execution time: 10-100 milliseconds

Performance Comparison: Relational vs Graph for Traversal Queries
Metric	Relational DB	Graph DB	Factor
1-hop (direct friends)	~2ms	~0.5ms	4x faster
2-hop (friends of friends)	~20ms	~2ms	10x faster
3-hop traversal	~2 seconds	~10ms	200x faster
4-hop traversal	~30 seconds	~50ms	600x faster
5-hop traversal	Often timeout	~150ms	Orders of magnitude
Scaling with depth	O(n^d) where d = depth	O(m) where m = edges traversed	Exponential vs Linear

Index-Free Adjacency: The Secret Sauce

The dramatic performance difference stems from index-free adjacency . In relational databases, JOINs require index lookups to match foreign keys—an O(log n) operation per relationship. In native graph databases, each node physically stores pointers to its adjacent nodes. Traversing a relationship is simply following a pointer—O(1). This constant-time traversal means performance depends only on the local neighborhood, not the total database size.

Graph Model vs Other NoSQL Models

Graph databases occupy a unique position in the NoSQL ecosystem. While key-value, document, and column-family stores optimize for different access patterns, graph databases specifically optimize for relationship-heavy queries . To understand where graphs excel (and where they don't), let's compare how each model handles a common e-commerce scenario: "Show products frequently bought together with items in the user's cart."

NoSQL Model Comparison for Connected Data
Model	Data Structure	Relationship Handling	Query Pattern	Sweet Spot
Key-Value	Opaque binary blobs	None—must denormalize	Single key lookup	Session storage, caching
Document	Nested JSON/BSON	Embedding or referencing	Single document aggregation	Content management, user profiles
Column-Family	Wide rows, column families	Row key design	Range scans on rows	Time-series, analytics
Graph	Nodes + Edges + Properties	First-class citizens	Multi-hop traversal	Networks, recommendations, fraud

When Graphs Excel

•Many-to-many relationships — Where entities connect in complex, unpredictable patterns
•Deep traversals — Queries spanning 3+ relationship hops
•Path analysis — Finding routes, shortest paths, or all connections between entities
•Pattern matching — Detecting subgraph patterns (critical for fraud detection)
•Real-time recommendations — Collaborative filtering based on connection patterns
•Network analysis — Centrality, influence, community detection

When Graphs Are Overkill

•Simple CRUD operations — Basic entity storage without relationships
•High-volume writes — Heavy transaction logging or event streams
•Aggregate queries — Sum, average, count across entire datasets
•Tabular analytics — Columnar scans for business intelligence
•Blob storage — Binary files, images, documents
•Cache layers — Simple key-value lookups

Polyglot Persistence in Practice

Modern architectures often combine a graph database with other storage systems. A common pattern: PostgreSQL for transactional data, Elasticsearch for full-text search, Redis for caching, and Neo4j for relationship queries. The graph database doesn't replace other stores—it augments them for specific query patterns that would otherwise be prohibitively expensive.

Core Graph Concepts Deep Dive

To work effectively with graph databases, you must internalize several key concepts that govern how data is modeled and queried. Vertex Degree and Cardinality: The degree of a vertex is the number of edges connected to it. In directed graphs, we distinguish: In-degree : Number of incoming edges (e.g., how many people follow this user) Out-degree : Number of outgoing edges (e.g., how many people this user follows) Cardinality affects query performance—a highly connected "hub" node (celebrity with millions of followers) creates different performance characteristics than typical nodes.

graph-concepts.txt
GRAPH TOPOLOGY CONCEPTS
=======================
 
PATH: A sequence of vertices connected by edges
  Example: Alice → Bob → Carol → David
  Path length = 3 (number of edges)
 
CYCLE: A path that starts and ends at the same vertex
  Example: Alice → Bob → Carol → Alice
  
CONNECTED COMPONENT: Maximal set of vertices where any two
  vertices are connected by a path
  
STRONGLY CONNECTED: In directed graphs, every vertex reachable
  from every other vertex (following edge directions)
  
WEAKLY CONNECTED: In directed graphs, every vertex reachable
  ignoring edge directions
 
DEGREE DISTRIBUTION:
┌────────────────────────────────────────────────────────────┐
│  Most real-world networks follow power-law distribution:   │
│                                                             │
│  Frequency                                                  │
│     │                                                       │
│  ▓▓ │▓                                                      │
│  ▓▓ │▓▓                                                     │
│  ▓▓ │▓▓▓                                                    │
│  ▓▓ │▓▓▓▓▓                                                  │
│  ▓▓ │▓▓▓▓▓▓▓▓▓▓▓▓▓▓......                                   │
│     └────────────────────────────    Node Degree            │
│                                                             │
│  Few nodes = many connections (hubs/influencers)            │
│  Many nodes = few connections (typical users)               │
└────────────────────────────────────────────────────────────┘
 
SUPERNODE PROBLEM:
  - Celebrity with 10M followers
  - Traversing all edges is expensive
  - Mitigation: Edge sampling, degree limits, or indexing

Traversal Patterns: Graph queries fundamentally involve traversal —starting from one or more vertices and systematically exploring connected vertices. The two primary strategies are: Breadth-First Search (BFS) : Explore all neighbors at the current depth before moving deeper. Optimal for shortest-path queries. Depth-First Search (DFS) : Explore as far as possible along each branch before backtracking. Optimal for detecting cycles and exhaustive path enumeration. Graph query languages provide primitives that express these patterns declaratively, letting the database engine choose optimal execution.

The Importance of Anchors

Every efficient graph query needs an anchor —an indexed starting point that dramatically reduces the search space. Without anchors, queries must scan the entire graph. Common anchor strategies: unique identifiers (WHERE id = 12345), indexed properties (WHERE email = 'alice@example.com'), or label scans with filters (MATCH (p:Person) WHERE p.country = 'USA').

Graph Modeling Principles

Effective graph modeling requires a different mindset than relational design. While normalization and foreign keys dominate relational thinking, graph modeling emphasizes query-driven design and relationship semantics . Key Principles:

Graph Modeling Best Practices

•Model for queries, not storage — Unlike normalization which optimizes storage, graph models should optimize for the traversals your application needs. If you frequently query "products purchased together," that relationship should be explicit, not computed.
•Relationships are first-class citizens — Don't treat edges as mere foreign keys. Relationships carry semantic meaning. :PURCHASED vs :VIEWED vs :WISHLISTED are different relationship types that enable different query patterns.
•Properties on relationships — Unlike relational join tables, graph edges can (and should) carry properties. A :RATED relationship should store the rating value, timestamp, and perhaps confidence score.
•Use specific relationship types — Prefer :MANAGES and :MENTORS over generic :RELATED_TO. Specific types enable more precise queries and better indexing.
•Leverage multiple labels — A single node can be :Person, :Employee, :Engineer, and :TeamLead. This enables flexible querying across different conceptual hierarchies.
•Consider bidirectional semantics — For symmetric relationships (:FRIEND), you may store one edge and traverse both directions. For asymmetric relationships (:FOLLOWS), the direction carries meaning.

modeling-evolution.txt
MODELING EVOLUTION: E-COMMERCE ORDERS
======================================
 
NAIVE (RELATIONAL THINKING):
  (Customer)-[:PLACED]->(Order)-[:CONTAINS]->(Item)-[:IS]->(Product)
  
  Problem: To find "customers who bought similar products," we must
  traverse multiple hops through intermediate Order and Item nodes.
 
EVOLVED (GRAPH NATIVE):
  (Customer)-[:PURCHASED {date, quantity, price}]->(Product)
  (Product)-[:OFTEN_BOUGHT_WITH {correlation: 0.85}]->(Product)
  (Customer)-[:SIMILAR_TASTE {score: 0.72}]->(Customer)
  
  Why better:
  1. Direct PURCHASED relationship for simple queries
  2. Pre-computed OFTEN_BOUGHT_WITH for recommendations
  3. SIMILAR_TASTE enables collaborative filtering without traversal
  
  Note: Original Order/Item data may still exist in relational DB
  for transactional integrity—graph stores derived relationships.
 
HYBRID APPROACH:
┌──────────────────────────────────────────────────────────────┐
│  OPERATIONAL DATA (PostgreSQL):                               │
│    - Orders, OrderItems, Inventory, Payments                  │
│    - Strong consistency, ACID transactions                    │
│                                                               │
│  GRAPH LAYER (Neo4j):                                         │
│    - Customer-Product relationships                           │
│    - Product similarities                                     │
│    - Customer segments                                        │
│    - Recommendation paths                                     │
│                                                               │
│  SYNC: ETL pipeline updates graph from operational changes    │
└──────────────────────────────────────────────────────────────┘

Common Modeling Antipatterns

Antipattern 1: Overconnected nodes — Avoid nodes that connect to everything (e.g., a :Country node linked to millions of users). These become performance bottlenecks. Antipattern 2: Using properties instead of relationships — Storing {friendIds: [1,2,3]} as a property defeats the purpose. This data belongs in edges. Antipattern 3: Generic relationships — A single :RELATED type requires filtering on properties, losing graph-native efficiency.

Internal Storage Architecture

Understanding how graph databases physically store data illuminates their performance characteristics. While implementations vary, most native graph databases use some variant of adjacency lists with fixed-size record stores . Neo4j's Storage Model (Representative Example): Neo4j stores data in multiple specialized files: Node Store (neostore.nodestore.db): Fixed-size records (15 bytes each) containing: First relationship ID (pointer to relationship chain) First property ID (pointer to property chain) Label information Relationship Store (neostore.relationshipstore.db): Fixed-size records (34 bytes) containing: Start node ID End node ID Relationship type Pointers to next relationship for both start and end nodes (doubly-linked list) First property ID Property Store (neostore.propertystore.db): Linked list of property records, with overflow to string/array stores for large values.

neo4j-storage-layout.txt
NEO4J PHYSICAL STORAGE LAYOUT
==============================
 
NODE RECORD (15 bytes, fixed):
┌─────────────────────────────────────────────────────────────────┐
│ inUse │ nextRel (5 bytes) │ nextProp (5 bytes) │ labels (5b)   │
│  1b   │   Pointer to      │   Pointer to       │  Label store  │
│       │   first relation  │   first property   │  reference    │
└─────────────────────────────────────────────────────────────────┘
  │
  │ Fixed-size → O(1) lookup by node ID (multiplication)
  │ Node ID 1000 = byte offset 1000 × 15 = 15000
  ▼
 
RELATIONSHIP RECORD (34 bytes, fixed):
┌─────────────────────────────────────────────────────────────────┐
│ inUse │ startNode │ endNode │ type │ startPrev│startNext│endPrev│
│  1b   │    5b     │   5b    │  4b  │    5b    │   5b    │  5b   │
├─────────────────────────────────────────────────────────────────┤
│ endNext │ nextProp │ firstInChain │                             │
│   5b    │    5b    │     1b       │         Reserved            │
└─────────────────────────────────────────────────────────────────┘
  │
  │ Doubly-linked list allows bidirectional traversal
  │ without index lookups—pure pointer chasing
  ▼
 
INDEX-FREE ADJACENCY IN ACTION:
  
  Query: MATCH (a:Person {id:100})-[:FRIEND]->(b)
  
  1. Look up node 100 → byte offset 100 × 15 = 1500
  2. Read node record → get firstRelationship pointer
  3. Jump to relationship record → read startNode, endNode, type
  4. If FRIEND, add endNode to results
  5. Follow startNext pointer to next relationship
  6. Repeat until end of chain (null pointer)
  
  TOTAL INDEX LOOKUPS: 1 (to find starting node)
  REMAINING OPERATIONS: Sequential pointer traversal

Why Fixed-Size Records Matter

Fixed-size records enable O(1) random access. To find node N, the database computes byte offset = N \times record_size and reads directly. No B-tree traversal needed. This is why graph databases maintain separate stores (nodes, relationships, properties)—each with fixed-size records—rather than a unified variable-length structure.

NoSQL DatabasesGraph Databases

Graph Databases: Modeling Connected Data

LevelAdvanced

Duration75 mins

TopicGraph Databases

1 / 5

Graph Model

When Relationships Are the Data

Consider a deceptively simple question: Who are the friends of my friends who work at the same company as me but whom I don't know yet? In a relational database, answering this requires multiple self-joins on a users table, intersections with employment records, and exclusion of existing connections. The query becomes baroque, the performance degrades exponentially with network size, and the semantic intent drowns in SQL gymnastics. Now consider how humans naturally think about this: start from me, traverse to my friends, traverse to their friends, filter by company, exclude those I already know. This is graph thinking —and graph databases are built to make this natural expression of connected queries not just possible, but efficient.

What You Will Learn

By the end of this page, you will understand the graph data model at a deep level—its mathematical foundations in graph theory, the property graph model used by modern graph databases, how graphs differ fundamentally from relational and document models, and why certain problems that are intractable in other paradigms become elegant in graph form.

Graph Theory Foundations

Before examining graph databases, we must establish the mathematical foundation upon which they rest. Graph theory—originated by Leonhard Euler in 1736 with his solution to the Seven Bridges of Königsberg problem—provides the formal framework for representing and analyzing connected structures. Formal Definition: A graph G is defined as an ordered pair G = (V, E) where: V is a set of vertices (also called nodes) E is a set of edges (also called relationships or links), where each edge connects two vertices This deceptively simple definition encompasses an enormous range of structures—from social networks to molecular diagrams, from transit systems to neural pathways, from organizational hierarchies to the World Wide Web itself.

Fundamental Graph Types
Graph Type	Definition	Real-World Example	Database Implication
Undirected Graph	Edges have no direction; (v₁, v₂) = (v₂, v₁)	Facebook friendships (mutual)	Relationship queries work bidirectionally
Directed Graph (Digraph)	Edges have direction; (v₁, v₂) ≠ (v₂, v₁)	Twitter follows (asymmetric)	Must specify traversal direction in queries
Weighted Graph	Edges carry numerical values	Road networks with distances	Supports shortest-path algorithms
Multigraph	Multiple edges between same vertex pair	Multiple flight routes between cities	Requires edge identification beyond endpoints
Hypergraph	Edges connect more than two vertices	Co-authorship (multiple authors per paper)	Extended property model needed
Bipartite Graph	Vertices split into two disjoint sets	Users and products in recommendations	Optimized join patterns in queries

Why Graph Theory Matters for Databases

Understanding graph theory isn't mere academic exercise. The algorithms developed over 300 years of graph theory—shortest paths (Dijkstra, Bellman-Ford), minimum spanning trees (Prim, Kruskal), centrality measures (PageRank, betweenness), community detection (Louvain, Girvan-Newman)—become directly applicable database operations. Graph databases don't reinvent these algorithms; they make them first-class citizens of the query language.

The Property Graph Model

While pure graph theory provides the mathematical foundation, modern graph databases implement the Property Graph Model—an extension that adds semantic richness without sacrificing the structural elegance of graphs. The property graph model introduces four key enhancements: 1. Labels (Types) Both vertices and edges can be assigned one or more labels that categorize them. A vertex might be labeled :Person, :Employee, and :Manager simultaneously. An edge might be labeled :WORKS_FOR or :MANAGES. Labels enable efficient filtering and indexing. 2. Properties (Attributes) Vertices and edges can carry key-value pairs as properties. A :Person vertex might have {name: "Alice", age: 32, email: "alice@example.com"}. An :EMPLOYED_BY edge might have {since: "2019-03-15", role: "Senior Engineer"}. Properties store the actual data. 3. Directed Relationships Edges always have direction (though they can be traversed in reverse). This models real-world asymmetry: Alice :FOLLOWS Bob doesn't imply Bob :FOLLOWS Alice. 4. Identities Every vertex and edge has a unique identifier, enabling precise reference and deduplication.

property-graph-example.txt
PROPERTY GRAPH: SOCIAL-PROFESSIONAL NETWORK
============================================
 
VERTICES (Nodes):
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n1                                                              │
│  Labels: [:Person, :Employee]                                        │
│  Properties: {                                                       │
│      name: "Alice Chen",                                             │
│      email: "alice@techcorp.com",                                    │
│      department: "Engineering",                                      │
│      joinedDate: "2019-03-15"                                        │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n2                                                              │
│  Labels: [:Person, :Employee, :Manager]                              │
│  Properties: {                                                       │
│      name: "Bob Singh",                                              │
│      email: "bob@techcorp.com",                                      │
│      department: "Engineering",                                      │
│      directReports: 5                                                │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│  ID: n3                                                              │
│  Labels: [:Company]                                                  │
│  Properties: {                                                       │
│      name: "TechCorp Inc.",                                          │
│      industry: "Software",                                           │
│      founded: 2010,                                                  │
│      employees: 500                                                  │
│  }                                                                   │
└─────────────────────────────────────────────────────────────────────┘
 
EDGES (Relationships):
(n1)-[:WORKS_FOR {since: "2019-03-15", role: "Senior Engineer"}]->(n3)
(n2)-[:WORKS_FOR {since: "2015-08-01", role: "Engineering Manager"}]->(n3)
(n1)-[:REPORTS_TO {since: "2020-01-01"}]->(n2)
(n1)-[:KNOWS {context: "colleague", strength: 0.8}]->(n2)
(n2)-[:KNOWS {context: "colleague", strength: 0.8}]->(n1)
 
GRAPH VISUALIZATION:
                        ┌─────────────┐
                        │  TechCorp   │
                        │  (Company)  │
                        └──────┬──────┘
                               │
              ┌────────────────┴────────────────┐
              │ WORKS_FOR            WORKS_FOR  │
              ▼                                 ▼
       ┌─────────────┐    REPORTS_TO    ┌─────────────┐
       │    Alice    │ ───────────────► │     Bob     │
       │  (Person,   │                  │  (Person,   │
       │  Employee)  │ ◄──────────────► │  Employee,  │
       └─────────────┘      KNOWS       │  Manager)   │
                                        └─────────────┘

Property Graphs vs RDF

An alternative graph model is RDF (Resource Description Framework), which represents everything as subject-predicate-object triples. RDF excels at semantic web applications and knowledge graphs where standardized vocabularies matter. Property graphs, used by Neo4j, Amazon Neptune, and TigerGraph, offer more intuitive modeling for application development and typically provide better write performance. The choice depends on whether you need semantic interoperability (RDF) or application-centric flexibility (property graphs).

Why Not Just Use Relational?

A natural question arises: relational databases can model relationships with foreign keys. Why introduce an entirely new paradigm? The answer lies in performance at depth . Consider querying "friends of friends of friends" (3-hop traversal) in a social network of 1 million users where each person has an average of 200 connections. The Relational Approach:

relational-friends-of-friends.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
-- Friends of friends of friends (3-hop traversal)
-- Assuming: users(id, name), friendships(user_id_1, user_id_2)
 
SELECT DISTINCT u4.name
FROM users u1
JOIN friendships f1 ON u1.id = f1.user_id_1
JOIN users u2 ON f1.user_id_2 = u2.id
JOIN friendships f2 ON u2.id = f2.user_id_1
JOIN users u3 ON f2.user_id_2 = u3.id
JOIN friendships f3 ON u3.id = f3.user_id_1
JOIN users u4 ON f3.user_id_2 = u4.id
WHERE u1.id = 12345
  AND u4.id NOT IN (
      -- Exclude the origin user themselves
      12345  
  )
  AND u4.id NOT IN (
      -- Exclude direct friends (1-hop)
      SELECT f.user_id_2 FROM friendships f WHERE f.user_id_1 = 12345
  )
  AND u4.id NOT IN (
      -- Exclude friends of friends (2-hop)
      SELECT f2.user_id_2
      FROM friendships f1
      JOIN friendships f2 ON f1.user_id_2 = f2.user_id_1
      WHERE f1.user_id_1 = 12345
  );
 
-- Performance characteristics:
-- - 6 JOINs on potentially millions of rows
-- - 3 subqueries for exclusion logic
-- - Cartesian product explosion at each hop
-- - Estimated I/O: Thousands of disk seeks
-- - Typical execution time: 30-60 seconds

The Graph Approach:

graph-friends-of-friends.cypher

Cypher

// Friends of friends of friends (3-hop traversal)
// Using Neo4j's Cypher query language
 
MATCH (me:Person {id: 12345})-[:FRIEND*3..3]-(distantFriend:Person)
WHERE NOT (me)-[:FRIEND]-(distantFriend)     // Not direct friends
  AND NOT (me)-[:FRIEND*2..2]-(distantFriend) // Not 2-hop friends
  AND me <> distantFriend                    // Not self
RETURN DISTINCT distantFriend.name
 
// Performance characteristics:
// - Native graph traversal following pointer chains
// - Only touches nodes actually connected to origin
// - Index-free adjacency (O(1) relationship lookup)
// - Estimated I/O: Hundreds of memory accesses
// - Typical execution time: 10-100 milliseconds

Performance Comparison: Relational vs Graph for Traversal Queries
Metric	Relational DB	Graph DB	Factor
1-hop (direct friends)	~2ms	~0.5ms	4x faster
2-hop (friends of friends)	~20ms	~2ms	10x faster
3-hop traversal	~2 seconds	~10ms	200x faster
4-hop traversal	~30 seconds	~50ms	600x faster
5-hop traversal	Often timeout	~150ms	Orders of magnitude
Scaling with depth	O(n^d) where d = depth	O(m) where m = edges traversed	Exponential vs Linear

Index-Free Adjacency: The Secret Sauce

The dramatic performance difference stems from index-free adjacency . In relational databases, JOINs require index lookups to match foreign keys—an O(log n) operation per relationship. In native graph databases, each node physically stores pointers to its adjacent nodes. Traversing a relationship is simply following a pointer—O(1). This constant-time traversal means performance depends only on the local neighborhood, not the total database size.

Graph Model vs Other NoSQL Models

Graph databases occupy a unique position in the NoSQL ecosystem. While key-value, document, and column-family stores optimize for different access patterns, graph databases specifically optimize for relationship-heavy queries . To understand where graphs excel (and where they don't), let's compare how each model handles a common e-commerce scenario: "Show products frequently bought together with items in the user's cart."

NoSQL Model Comparison for Connected Data
Model	Data Structure	Relationship Handling	Query Pattern	Sweet Spot
Key-Value	Opaque binary blobs	None—must denormalize	Single key lookup	Session storage, caching
Document	Nested JSON/BSON	Embedding or referencing	Single document aggregation	Content management, user profiles
Column-Family	Wide rows, column families	Row key design	Range scans on rows	Time-series, analytics
Graph	Nodes + Edges + Properties	First-class citizens	Multi-hop traversal	Networks, recommendations, fraud

When Graphs Excel

•Many-to-many relationships — Where entities connect in complex, unpredictable patterns
•Deep traversals — Queries spanning 3+ relationship hops
•Path analysis — Finding routes, shortest paths, or all connections between entities
•Pattern matching — Detecting subgraph patterns (critical for fraud detection)
•Real-time recommendations — Collaborative filtering based on connection patterns
•Network analysis — Centrality, influence, community detection

When Graphs Are Overkill

•Simple CRUD operations — Basic entity storage without relationships
•High-volume writes — Heavy transaction logging or event streams
•Aggregate queries — Sum, average, count across entire datasets
•Tabular analytics — Columnar scans for business intelligence
•Blob storage — Binary files, images, documents
•Cache layers — Simple key-value lookups

Polyglot Persistence in Practice

Modern architectures often combine a graph database with other storage systems. A common pattern: PostgreSQL for transactional data, Elasticsearch for full-text search, Redis for caching, and Neo4j for relationship queries. The graph database doesn't replace other stores—it augments them for specific query patterns that would otherwise be prohibitively expensive.

Core Graph Concepts Deep Dive

To work effectively with graph databases, you must internalize several key concepts that govern how data is modeled and queried. Vertex Degree and Cardinality: The degree of a vertex is the number of edges connected to it. In directed graphs, we distinguish: In-degree : Number of incoming edges (e.g., how many people follow this user) Out-degree : Number of outgoing edges (e.g., how many people this user follows) Cardinality affects query performance—a highly connected "hub" node (celebrity with millions of followers) creates different performance characteristics than typical nodes.

graph-concepts.txt
GRAPH TOPOLOGY CONCEPTS
=======================
 
PATH: A sequence of vertices connected by edges
  Example: Alice → Bob → Carol → David
  Path length = 3 (number of edges)
 
CYCLE: A path that starts and ends at the same vertex
  Example: Alice → Bob → Carol → Alice
  
CONNECTED COMPONENT: Maximal set of vertices where any two
  vertices are connected by a path
  
STRONGLY CONNECTED: In directed graphs, every vertex reachable
  from every other vertex (following edge directions)
  
WEAKLY CONNECTED: In directed graphs, every vertex reachable
  ignoring edge directions
 
DEGREE DISTRIBUTION:
┌────────────────────────────────────────────────────────────┐
│  Most real-world networks follow power-law distribution:   │
│                                                             │
│  Frequency                                                  │
│     │                                                       │
│  ▓▓ │▓                                                      │
│  ▓▓ │▓▓                                                     │
│  ▓▓ │▓▓▓                                                    │
│  ▓▓ │▓▓▓▓▓                                                  │
│  ▓▓ │▓▓▓▓▓▓▓▓▓▓▓▓▓▓......                                   │
│     └────────────────────────────    Node Degree            │
│                                                             │
│  Few nodes = many connections (hubs/influencers)            │
│  Many nodes = few connections (typical users)               │
└────────────────────────────────────────────────────────────┘
 
SUPERNODE PROBLEM:
  - Celebrity with 10M followers
  - Traversing all edges is expensive
  - Mitigation: Edge sampling, degree limits, or indexing

Traversal Patterns: Graph queries fundamentally involve traversal —starting from one or more vertices and systematically exploring connected vertices. The two primary strategies are: Breadth-First Search (BFS) : Explore all neighbors at the current depth before moving deeper. Optimal for shortest-path queries. Depth-First Search (DFS) : Explore as far as possible along each branch before backtracking. Optimal for detecting cycles and exhaustive path enumeration. Graph query languages provide primitives that express these patterns declaratively, letting the database engine choose optimal execution.

The Importance of Anchors

Every efficient graph query needs an anchor —an indexed starting point that dramatically reduces the search space. Without anchors, queries must scan the entire graph. Common anchor strategies: unique identifiers (WHERE id = 12345), indexed properties (WHERE email = 'alice@example.com'), or label scans with filters (MATCH (p:Person) WHERE p.country = 'USA').

Graph Modeling Principles

Effective graph modeling requires a different mindset than relational design. While normalization and foreign keys dominate relational thinking, graph modeling emphasizes query-driven design and relationship semantics . Key Principles:

Graph Modeling Best Practices

•Model for queries, not storage — Unlike normalization which optimizes storage, graph models should optimize for the traversals your application needs. If you frequently query "products purchased together," that relationship should be explicit, not computed.
•Relationships are first-class citizens — Don't treat edges as mere foreign keys. Relationships carry semantic meaning. :PURCHASED vs :VIEWED vs :WISHLISTED are different relationship types that enable different query patterns.
•Properties on relationships — Unlike relational join tables, graph edges can (and should) carry properties. A :RATED relationship should store the rating value, timestamp, and perhaps confidence score.
•Use specific relationship types — Prefer :MANAGES and :MENTORS over generic :RELATED_TO. Specific types enable more precise queries and better indexing.
•Leverage multiple labels — A single node can be :Person, :Employee, :Engineer, and :TeamLead. This enables flexible querying across different conceptual hierarchies.
•Consider bidirectional semantics — For symmetric relationships (:FRIEND), you may store one edge and traverse both directions. For asymmetric relationships (:FOLLOWS), the direction carries meaning.

modeling-evolution.txt
MODELING EVOLUTION: E-COMMERCE ORDERS
======================================
 
NAIVE (RELATIONAL THINKING):
  (Customer)-[:PLACED]->(Order)-[:CONTAINS]->(Item)-[:IS]->(Product)
  
  Problem: To find "customers who bought similar products," we must
  traverse multiple hops through intermediate Order and Item nodes.
 
EVOLVED (GRAPH NATIVE):
  (Customer)-[:PURCHASED {date, quantity, price}]->(Product)
  (Product)-[:OFTEN_BOUGHT_WITH {correlation: 0.85}]->(Product)
  (Customer)-[:SIMILAR_TASTE {score: 0.72}]->(Customer)
  
  Why better:
  1. Direct PURCHASED relationship for simple queries
  2. Pre-computed OFTEN_BOUGHT_WITH for recommendations
  3. SIMILAR_TASTE enables collaborative filtering without traversal
  
  Note: Original Order/Item data may still exist in relational DB
  for transactional integrity—graph stores derived relationships.
 
HYBRID APPROACH:
┌──────────────────────────────────────────────────────────────┐
│  OPERATIONAL DATA (PostgreSQL):                               │
│    - Orders, OrderItems, Inventory, Payments                  │
│    - Strong consistency, ACID transactions                    │
│                                                               │
│  GRAPH LAYER (Neo4j):                                         │
│    - Customer-Product relationships                           │
│    - Product similarities                                     │
│    - Customer segments                                        │
│    - Recommendation paths                                     │
│                                                               │
│  SYNC: ETL pipeline updates graph from operational changes    │
└──────────────────────────────────────────────────────────────┘

Common Modeling Antipatterns

Antipattern 1: Overconnected nodes — Avoid nodes that connect to everything (e.g., a :Country node linked to millions of users). These become performance bottlenecks. Antipattern 2: Using properties instead of relationships — Storing {friendIds: [1,2,3]} as a property defeats the purpose. This data belongs in edges. Antipattern 3: Generic relationships — A single :RELATED type requires filtering on properties, losing graph-native efficiency.

Internal Storage Architecture

Understanding how graph databases physically store data illuminates their performance characteristics. While implementations vary, most native graph databases use some variant of adjacency lists with fixed-size record stores . Neo4j's Storage Model (Representative Example): Neo4j stores data in multiple specialized files: Node Store (neostore.nodestore.db): Fixed-size records (15 bytes each) containing: First relationship ID (pointer to relationship chain) First property ID (pointer to property chain) Label information Relationship Store (neostore.relationshipstore.db): Fixed-size records (34 bytes) containing: Start node ID End node ID Relationship type Pointers to next relationship for both start and end nodes (doubly-linked list) First property ID Property Store (neostore.propertystore.db): Linked list of property records, with overflow to string/array stores for large values.

neo4j-storage-layout.txt
NEO4J PHYSICAL STORAGE LAYOUT
==============================
 
NODE RECORD (15 bytes, fixed):
┌─────────────────────────────────────────────────────────────────┐
│ inUse │ nextRel (5 bytes) │ nextProp (5 bytes) │ labels (5b)   │
│  1b   │   Pointer to      │   Pointer to       │  Label store  │
│       │   first relation  │   first property   │  reference    │
└─────────────────────────────────────────────────────────────────┘
  │
  │ Fixed-size → O(1) lookup by node ID (multiplication)
  │ Node ID 1000 = byte offset 1000 × 15 = 15000
  ▼
 
RELATIONSHIP RECORD (34 bytes, fixed):
┌─────────────────────────────────────────────────────────────────┐
│ inUse │ startNode │ endNode │ type │ startPrev│startNext│endPrev│
│  1b   │    5b     │   5b    │  4b  │    5b    │   5b    │  5b   │
├─────────────────────────────────────────────────────────────────┤
│ endNext │ nextProp │ firstInChain │                             │
│   5b    │    5b    │     1b       │         Reserved            │
└─────────────────────────────────────────────────────────────────┘
  │
  │ Doubly-linked list allows bidirectional traversal
  │ without index lookups—pure pointer chasing
  ▼
 
INDEX-FREE ADJACENCY IN ACTION:
  
  Query: MATCH (a:Person {id:100})-[:FRIEND]->(b)
  
  1. Look up node 100 → byte offset 100 × 15 = 1500
  2. Read node record → get firstRelationship pointer
  3. Jump to relationship record → read startNode, endNode, type
  4. If FRIEND, add endNode to results
  5. Follow startNext pointer to next relationship
  6. Repeat until end of chain (null pointer)
  
  TOTAL INDEX LOOKUPS: 1 (to find starting node)
  REMAINING OPERATIONS: Sequential pointer traversal

Why Fixed-Size Records Matter

Fixed-size records enable O(1) random access. To find node N, the database computes byte offset = N \times record_size and reads directly. No B-tree traversal needed. This is why graph databases maintain separate stores (nodes, relationships, properties)—each with fixed-size records—rather than a unified variable-length structure.

Graph Model

When Relationships Are the Data

Graph Theory Foundations

The Property Graph Model

Why Not Just Use Relational?

Graph Model vs Other NoSQL Models

Core Graph Concepts Deep Dive

Graph Modeling Principles

Internal Storage Architecture

There’s more to understand.

Graph Model

When Relationships Are the Data

Graph Theory Foundations

The Property Graph Model

Why Not Just Use Relational?

Graph Model vs Other NoSQL Models

Core Graph Concepts Deep Dive

Graph Modeling Principles

Internal Storage Architecture

There’s more to understand.