How the Graph Data Structure Is Represented in the Codebase Memory MCP Store Module

The store module represents the graph data structure using two SQLite tables (nodes and edges) mirrored by plain C structs (cbm_node_t and cbm_edge_t), accessed through an opaque cbm_store_t handle that caches prepared statements for CRUD operations and BFS traversal.

The DeusData/codebase-memory-mcp project persists code-level relationships in a specialized store module that implements a graph data structure using SQLite as the backend. This article examines how the graph data structure is represented in the store module, revealing an adjacency-based model where C structs map directly to relational tables. This architecture enables efficient insertion, querying, and traversal of function calls, imports, and file dependencies while keeping SQL details hidden behind a type-safe C API.

Core C Data Structures for Graph Elements

The public API defined in src/store/store.h exposes three fundamental structures that abstract the underlying SQLite implementation. These plain-old-data structs contain only scalar values or pointers to heap-allocated UTF-8 strings, with memory management handled by helper functions like heap_strdup and cbm_store_free_*.

The cbm_node_t Structure

Defined in src/store/store.h at lines 29-40, cbm_node_t represents a vertex in the graph corresponding to code entities such as functions, classes, or files. The structure contains:

• id (rowid)
• project (namespace)
• label (entity type)
• name and qualified_name
• file_path, start_line, end_line
• properties_json (arbitrary JSON metadata)

The cbm_edge_t Structure

Defined in src/store/store.h at lines 41-48, cbm_edge_t represents directed relationships between nodes. Key fields include:

• id (rowid)
• project (namespace)
• source_id and target_id (node references)
• type (relationship category such as "CALLS" or "IMPORTS")
• properties_json (relationship metadata)

The Opaque Store Handle

The internal implementation in src/store/store.c (lines 100-130) defines cbm_store_t as an opaque structure containing the SQLite database handle (sqlite3 *db), the database path, and caches of prepared statements including stmt_upsert_node, stmt_find_edge_by_source, and stmt_find_edges_by_target.

SQLite Schema for Graph Persistence

The graph data structure is persisted in two main tables created by init_schema() in src/store/store.c at lines 219-265. Both tables reference the projects table for cascade deletes, ensuring that removing a project cleans up its graph automatically.

The Nodes Table

The nodes table stores one row per cbm_node_t with the following schema:

• id INTEGER PRIMARY KEY AUTOINCREMENT
• project TEXT NOT NULL
• label TEXT NOT NULL
• name TEXT NOT NULL
• qualified_name TEXT NOT NULL
• file_path TEXT
• start_line INTEGER
• end_line INTEGER
• properties TEXT

The project column namespaces the graph, allowing multiple projects to coexist in separate database files.

The Edges Table

The edges table stores relationships with generated columns for fast lookups:

• id INTEGER PRIMARY KEY AUTOINCREMENT
• project TEXT NOT NULL
• source_id INTEGER NOT NULL
• target_id INTEGER NOT NULL
• type TEXT NOT NULL
• properties TEXT
• url_path_gen TEXT GENERATED ...
• local_name_gen TEXT GENERATED ...

A unique constraint on (source_id, target_id, type, local_name_gen) prevents duplicate IMPORTS edges while allowing multiple CALLS relationships between the same nodes.

Graph Lifecycle: From Open to Traversal

The store module manages the graph lifecycle through specific functions that bridge the C structs and SQLite tables.

Opening a Store

cbm_store_open() (implemented in src/store/store.c lines 870-884) builds a file path at <cache_dir>/<project>.db and executes:

1. store_open_internal() to open SQLite
2. configure_pragmas() for performance tuning
3. init_schema() to create tables if missing
4. create_user_indexes() to optimize query paths

Inserting Nodes

cbm_store_upsert_node() at lines 1888-1916 prepares (or reuses) an INSERT ... ON CONFLICT ... RETURNING id statement, binds all fields using bind_text for strings and sqlite3_bind_int for numbers, and returns the autoincremented id.

Creating Relationships

cbm_store_insert_edge() follows the same pattern, creating rows that link source_id to target_id while populating the type and JSON properties fields. This function respects the unique constraint that includes local_name_gen for IMPORTS edges.

Querying and Traversal

Helper functions like cbm_store_find_node_by_qn() and cbm_store_find_edges_by_source() read rows, allocate strings with heap_strdup, and fill the corresponding structs. For graph traversal, cbm_store_bfs() walks the edge table using cached stmt_find_edges_by_source and stmt_find_edges_by_target statements, building an array of cbm_node_hop_t structures that capture hop depth for each visited node.

Complete Working Example

The following example demonstrates opening a store, inserting a function node, creating a CALLS relationship, and querying outgoing edges:

#include "store.h"

/* Open a store for project "myapp" */
cbm_store_t *s = cbm_store_open("myapp");
if (!s) { /* handle error */ }

/* Insert a function node */
cbm_node_t fn = {
    .project = "myapp",
    .label   = "Function",
    .name    = "process_data",
    .qualified_name = "myapp.utils.process_data",
    .file_path = "src/utils.c",
    .start_line = 42,
    .end_line   = 78,
    .properties_json = "{\"doc\":\"Processes input data\"}"
};
int64_t fn_id = cbm_store_upsert_node(s, &fn);

/* Insert a CALLS edge from another function */
cbm_edge_t e = {
    .project = "myapp",
    .source_id = caller_id,          /* previously obtained */
    .target_id = fn_id,
    .type = "CALLS",
    .properties_json = "{\"arg\":\"data\"}"
};
int64_t edge_id = cbm_store_insert_edge(s, &e);

/* Find all callees of a given node */
cbm_edge_t *out = NULL;
int count = 0;
cbm_store_find_edges_by_source(s, fn_id, &out, &count);
/* …process results… */
cbm_store_free_edges(out, count);

/* Close the store */
cbm_store_close(s);

All functions used above are declared in src/store/store.h and implemented in src/store/store.c.

Summary

• The graph data structure in the store module uses an adjacency model with separate SQLite tables for vertices (nodes) and edges (edges).
• C structs (cbm_node_t, cbm_edge_t) map directly to table schemas, with JSON columns storing extensible properties.
• The cbm_store_t opaque handle caches prepared statements and manages the SQLite connection lifecycle.
• Generated columns (url_path_gen, local_name_gen) in the edges table enable fast lookups while maintaining data integrity through unique constraints.
• BFS traversal is implemented directly in SQL using cached prepared statements that walk the edge table by source_id or target_id.

Frequently Asked Questions

What data structure does the store module use to represent the graph?

The store module uses a persistent adjacency list represented by two SQLite tables (nodes and edges) mirrored by C structs. This differs from an in-memory graph library by using SQLite as the storage engine, with the cbm_store_t handle managing prepared statements for efficient access to the relational data.

How are node properties stored in the SQLite schema?

Node properties are stored as JSON text in the properties column of the nodes table (mapped from cbm_node_t.properties_json). This schemaless approach allows arbitrary metadata—such as documentation strings or AST annotations—without requiring schema migrations for new property types.

What is the purpose of the generated columns in the edges table?

The url_path_gen and local_name_gen columns are generated columns derived from the JSON in the properties field. These enable fast lookups for specific relationship patterns (such as import paths) while maintaining a unique constraint that prevents duplicate IMPORTS edges between the same nodes, as implemented in init_schema() at src/store/store.c lines 219-265.

How does the store module handle graph traversal?

Graph traversal uses breadth-first search (BFS) implemented in cbm_store_bfs(), which executes cached prepared statements (stmt_find_edges_by_source and stmt_find_edges_by_target) to walk the edge table. The function returns an array of cbm_node_hop_t structures containing the visited node and its hop depth from the source, without loading the entire graph into memory.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}