Graph databases like Neo4j excel at traversal queries, but many production systems already run on MySQL or TiDB and cannot justify the operational cost of a separate graph store. By carefully designing relational tables for accounts, generations, nodes, and edges, you can represent versioned graph snapshots entirely within a SQL database. Each “generation” freezes a complete graph state, enabling time-travel queries, rollback, and audit without ever mutating historical data.
The core insight is treating graph mutations as an append-only log of generations. When a graph changes, a new generation is created that references the new set of nodes and edges. Previous generations remain intact, providing an immutable history of every graph state. This is analogous to how MVCC works at the database level, but implemented in application schema for domain-specific graph versioning.
In a typical distributed data platform, this pattern is used to model account-scoped knowledge graphs where each account maintains its own graph with generation-based versioning. Nodes carry JSON payloads for flexible schema evolution, edges use composite primary keys for efficient traversal, and cascading foreign keys ensure referential integrity across the account/generation/node/edge hierarchy.
The versioned graph model uses four tables arranged in a strict hierarchy:
A generation is an immutable snapshot of an entire graph. When you need to modify the graph, you create a new generation, copy forward the unchanged nodes and edges, and apply mutations. The old generation remains frozen. This gives you time-travel queries (read any historical generation), atomic graph updates (a generation is either fully committed or not), and simple rollback (just point to a previous generation).
Every table below accounts uses a composite primary key that embeds its parent’s identity. Nodes are keyed by (account_id, generation_id, node_id), and edges by (account_id, generation_id, source_node_id, target_node_id, edge_type). This design has two benefits: it eliminates the need for surrogate keys (reducing joins), and it makes partition-pruning trivial—all queries for a single account or generation naturally cluster on disk.
Foreign keys with ON DELETE CASCADE enforce that deleting a generation automatically removes all its nodes and edges, and deleting an account removes all its generations. This prevents orphaned rows and simplifies cleanup. In TiDB, foreign keys are supported but must be explicitly enabled—the cascade behavior matches MySQL semantics.
Nodes and edges store their domain-specific data in a JSON column rather than fixed columns. This allows different node types (e.g., “person”, “document”, “concept”) to carry different attributes without schema migrations. MySQL 8.0+ and TiDB support JSON column types with indexing via generated columns and multi-valued indexes.
Graph traversal means following edges from a source node to find its neighbors. The primary key on edges (account_id, generation_id, source_node_id, ...) naturally supports forward traversal (find all edges from a source). For reverse traversal (find all edges pointing to a target), a secondary index on (account_id, generation_id, target_node_id) is required. Without this index, reverse lookups require a full table scan.
The account_id at the root of every composite key provides natural multi-tenant isolation. Queries for one account never touch another account’s data. In TiDB, this also enables region-level data placement—all data for a single account can be pinned to specific TiKV nodes for data residency compliance.
The DDL for the four-table hierarchy with cascading foreign keys:
CREATE TABLE accounts (
account_id BIGINT NOT NULL AUTO_INCREMENT,
name VARCHAR(255) NOT NULL,
created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (account_id)
);
CREATE TABLE generations (
account_id BIGINT NOT NULL,
generation_id BIGINT NOT NULL AUTO_INCREMENT,
status ENUM('building', 'committed', 'archived') NOT NULL DEFAULT 'building',
created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
committed_at TIMESTAMP NULL,
PRIMARY KEY (generation_id),
INDEX idx_account_gen (account_id, generation_id),
FOREIGN KEY (account_id) REFERENCES accounts(account_id) ON DELETE CASCADE
);
CREATE TABLE nodes (
account_id BIGINT NOT NULL,
generation_id BIGINT NOT NULL,
node_id BIGINT NOT NULL AUTO_INCREMENT,
node_type VARCHAR(64) NOT NULL,
payload JSON NOT NULL,
created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (node_id),
INDEX idx_gen_nodes (account_id, generation_id, node_type),
FOREIGN KEY (generation_id) REFERENCES generations(generation_id) ON DELETE CASCADE
);
CREATE TABLE edges (
account_id BIGINT NOT NULL,
generation_id BIGINT NOT NULL,
source_node_id BIGINT NOT NULL,
target_node_id BIGINT NOT NULL,
edge_type VARCHAR(64) NOT NULL,
metadata JSON NULL,
created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (account_id, generation_id, source_node_id, target_node_id, edge_type),
INDEX idx_reverse_edge (account_id, generation_id, target_node_id),
FOREIGN KEY (generation_id) REFERENCES generations(generation_id) ON DELETE CASCADE,
FOREIGN KEY (source_node_id) REFERENCES nodes(node_id) ON DELETE CASCADE,
FOREIGN KEY (target_node_id) REFERENCES nodes(node_id) ON DELETE CASCADE
);Building a new graph version follows a transactional workflow: create the generation record, insert all nodes and edges, then commit the generation by updating its status:
package graph
import (
"database/sql"
"encoding/json"
"fmt"
"time"
)
type Node struct {
NodeType string
Payload map[string]interface{}
}
type Edge struct {
SourceID int64
TargetID int64
EdgeType string
Metadata map[string]interface{}
}
// CreateGeneration builds a new graph snapshot for an account.
func CreateGeneration(tx *sql.Tx, accountID int64, nodes []Node, edges []Edge) (int64, error) {
// 1. Create the generation record
res, err := tx.Exec(
"INSERT INTO generations (account_id, status) VALUES (?, 'building')",
accountID,
)
if err != nil {
return 0, fmt.Errorf("creating generation: %w", err)
}
genID, _ := res.LastInsertId()
// 2. Insert nodes and collect their assigned IDs
nodeIDs := make([]int64, len(nodes))
for i, n := range nodes {
payload, _ := json.Marshal(n.Payload)
res, err := tx.Exec(
"INSERT INTO nodes (account_id, generation_id, node_type, payload) VALUES (?, ?, ?, ?)",
accountID, genID, n.NodeType, payload,
)
if err != nil {
return 0, fmt.Errorf("inserting node %d: %w", i, err)
}
nodeIDs[i], _ = res.LastInsertId()
}
// 3. Insert edges using the resolved node IDs
for _, e := range edges {
metadata, _ := json.Marshal(e.Metadata)
_, err := tx.Exec(
`INSERT INTO edges (account_id, generation_id, source_node_id,
target_node_id, edge_type, metadata) VALUES (?, ?, ?, ?, ?, ?)`,
accountID, genID, e.SourceID, e.TargetID, e.EdgeType, metadata,
)
if err != nil {
return 0, fmt.Errorf("inserting edge %s->%s: %w", e.SourceID, e.TargetID, err)
}
}
// 4. Commit the generation
now := time.Now()
_, err = tx.Exec(
"UPDATE generations SET status = 'committed', committed_at = ? WHERE generation_id = ?",
now, genID,
)
if err != nil {
return 0, fmt.Errorf("committing generation: %w", err)
}
return genID, nil
}Forward traversal (finding neighbors of a node) uses the primary key on edges. Reverse traversal uses the secondary index on target_node_id:
package graph
import "database/sql"
// Neighbor represents a connected node with its edge type.
type Neighbor struct {
NodeID int64
NodeType string
EdgeType string
Payload json.RawMessage
}
// GetOutboundNeighbors returns all nodes reachable from sourceID via forward edges.
func GetOutboundNeighbors(db *sql.DB, accountID, genID, sourceID int64) ([]Neighbor, error) {
rows, err := db.Query(`
SELECT n.node_id, n.node_type, e.edge_type, n.payload
FROM edges e
JOIN nodes n ON n.node_id = e.target_node_id
WHERE e.account_id = ? AND e.generation_id = ? AND e.source_node_id = ?
`, accountID, genID, sourceID)
if err != nil {
return nil, err
}
defer rows.Close()
var neighbors []Neighbor
for rows.Next() {
var nb Neighbor
if err := rows.Scan(&nb.NodeID, &nb.NodeType, &nb.EdgeType, &nb.Payload); err != nil {
return nil, err
}
neighbors = append(neighbors, nb)
}
return neighbors, rows.Err()
}
// GetInboundNeighbors returns all nodes that have edges pointing to targetID.
func GetInboundNeighbors(db *sql.DB, accountID, genID, targetID int64) ([]Neighbor, error) {
rows, err := db.Query(`
SELECT n.node_id, n.node_type, e.edge_type, n.payload
FROM edges e
JOIN nodes n ON n.node_id = e.source_node_id
WHERE e.account_id = ? AND e.generation_id = ? AND e.target_node_id = ?
`, accountID, genID, targetID)
if err != nil {
return nil, err
}
defer rows.Close()
var neighbors []Neighbor
for rows.Next() {
var nb Neighbor
if err := rows.Scan(&nb.NodeID, &nb.NodeType, &nb.EdgeType, &nb.Payload); err != nil {
return nil, err
}
neighbors = append(neighbors, nb)
}
return neighbors, rows.Err()
}Since each generation is immutable, querying a historical graph state is just a matter of specifying the generation ID. Comparing two generations (diffing the graph) can be done with set operations:
-- Nodes added in generation 5 that weren't in generation 4
SELECT n.node_id, n.node_type, n.payload
FROM nodes n
WHERE n.account_id = 1 AND n.generation_id = 5
AND n.node_id NOT IN (
SELECT node_id FROM nodes WHERE account_id = 1 AND generation_id = 4
);
-- Edges removed between generation 4 and generation 5
SELECT e.source_node_id, e.target_node_id, e.edge_type
FROM edges e
WHERE e.account_id = 1 AND e.generation_id = 4
AND (e.source_node_id, e.target_node_id, e.edge_type) NOT IN (
SELECT source_node_id, target_node_id, edge_type
FROM edges WHERE account_id = 1 AND generation_id = 5
);A marketplace application uses versioned graph tables to maintain per-account knowledge graphs. When an account’s data is re-indexed or updated, a new generation is built atomically. The application can serve queries against the current committed generation while a new one is being built in the background. Once the new generation is committed, a pointer swap makes it the active version.
Systems that model dependencies as graphs (infrastructure topology, service meshes, permission hierarchies) benefit from versioned snapshots. Each deployment creates a new generation of the dependency graph. If a deployment causes issues, rolling back means pointing to the previous generation—no graph mutations required.
Regulated environments require the ability to reconstruct the exact state of data at any point in time. Versioned graph tables provide this naturally: each generation is timestamped and immutable. Auditors can query any historical generation to see the exact relationships that existed at that time.
When multiple users edit a shared graph (e.g., a diagram tool or ontology editor), each save creates a new generation. Conflict resolution can compare two concurrent generations against their common ancestor generation, similar to a three-way merge in version control.
When most of a graph is unchanged between generations, copying all nodes and edges is wasteful. A copy-on-write approach only creates new rows for modified nodes/edges and references unchanged ones from the previous generation via a “base generation” pointer:
-- Resolve a node: check current generation first, fall back to base
SELECT node_id, node_type, payload
FROM nodes
WHERE account_id = ? AND generation_id = ?
UNION ALL
SELECT node_id, node_type, payload
FROM nodes
WHERE account_id = ? AND generation_id = (
SELECT base_generation_id FROM generations WHERE generation_id = ?
)
AND node_id NOT IN (
SELECT node_id FROM nodes WHERE account_id = ? AND generation_id = ?
)
LIMIT 1;Rather than querying “the latest committed generation for account X” on every request, maintain a current_generation_id column on the accounts table. This pointer is updated atomically when a new generation is committed:
package graph
import "database/sql"
// CommitAndActivate commits a generation and makes it the active one for its account.
func CommitAndActivate(tx *sql.Tx, accountID, genID int64) error {
_, err := tx.Exec(
"UPDATE generations SET status = 'committed', committed_at = NOW() WHERE generation_id = ?",
genID,
)
if err != nil {
return err
}
_, err = tx.Exec(
"UPDATE accounts SET current_generation_id = ? WHERE account_id = ?",
genID, accountID,
)
return err
}Over time, old generations accumulate. A retention policy (e.g., keep the last 10 generations per account) can be enforced with a periodic cleanup job. Thanks to cascading foreign keys, deleting a generation row automatically removes all its nodes and edges:
-- Delete generations older than the last 10 for each account
DELETE g FROM generations g
WHERE g.account_id = ?
AND g.status = 'archived'
AND g.generation_id NOT IN (
SELECT generation_id FROM (
SELECT generation_id FROM generations
WHERE account_id = ? AND status IN ('committed', 'archived')
ORDER BY generation_id DESC
LIMIT 10
) AS keep
);When a generation is deleted, ON DELETE CASCADE removes all associated nodes and edges in a single operation. This avoids orphaned rows and eliminates the need for application-level cleanup logic. However, cascading deletes on large generations (millions of nodes) can cause long-running transactions. For very large graphs, batch the delete: first delete edges in chunks, then nodes, then the generation record.
If every generation copies all nodes and edges (full materialization), storage grows linearly with the number of generations times the graph size. For a graph with 1 million nodes and 100 generations, that’s 100 million node rows. Use copy-on-write or delta-based approaches to share unchanged data across generations.
TiDB supports foreign keys but enforces them differently than MySQL. In distributed mode, foreign key checks require cross-region reads, adding latency. For high-throughput bulk inserts (e.g., building a new generation with millions of nodes), consider temporarily disabling foreign key checks with SET @@foreign_key_checks = 0 during the build phase, then re-enabling and validating before committing.
The composite primary key on edges supports efficient forward traversal (from source to targets), but reverse traversal (from target to sources) requires a secondary index. Without idx_reverse_edge, any query asking “what points to this node?” triggers a full table scan. This is easy to overlook during initial schema design and only surfaces under load.
While JSON columns provide schema flexibility, querying inside JSON payloads (JSON_EXTRACT, ->> operator) cannot use standard B-tree indexes. For frequently queried JSON fields, create generated columns with indexes:
ALTER TABLE nodes
ADD COLUMN name VARCHAR(255) GENERATED ALWAYS AS (payload->>'$.name') STORED,
ADD INDEX idx_node_name (account_id, generation_id, name);Building a large generation (millions of nodes and edges) in a single transaction can exhaust TiDB’s transaction size limit (default 100MB) or cause excessive lock contention. Split the build into batches: insert nodes in chunks, then edges in chunks, all within the “building” status. Only the final status update to “committed” needs to be atomic.
When using copy-on-write between generations, edges may reference nodes from a base generation. If the base generation is garbage-collected before the derived generation, the edges become dangling. Always track generation dependencies and only delete a generation when no other generation depends on it as a base.