Graph Databases for AI: When Relationships Are the Data

Entity Resolution: One Thing, Many Names gave Mailmind a clean, deduplicated record for each person, thread, order, and payment. Now those entities need to connect. RAG vs Knowledge Graphs: Two Kinds of AI Memory Lookup introduced knowledge graphs as a way to answer precise questions about how things connect, and showed a first Cypher query. This part looks at the database underneath.

In a graph database, each hop is a direct pointer follow instead of an index lookup and a join, and you can ask for "one to three hops away" in one line. The total work still grows with how many connections fan out at each hop, so deep queries on busy nodes can still be slow. That mix of cheap hops and readable path queries makes a graph a natural long-term memory for an AI assistant like Mailmind, where the meaning lives in connections among emails, people, orders, and tasks.

In a graph, you can also invent a new relationship type like INTRODUCED_BY without a schema migration. You just start drawing lines between existing nodes. That means the memory layer can grow sideways as the assistant learns new kinds of connection.

What does a graph database actually store?

A graph stores entities as nodes and connections as first-class relationships. A node gets a label like Person or Thread and holds properties like name: "Sam" or subject: "Invoice for Q3". A relationship has a type, a direction, and its own properties. For example, the Cypher pattern (sam:Person)-[:SENT {date: date('2025-11-03')}]->(t:Thread {id: 'T42'}) says Sam sent thread T42 on that date. Each node keeps direct references to its own relationships, rather than a foreign key that must be looked up in another table. The design is known as index-free adjacency. As a Neo4j engineering post explains (The co-evolution of computer hardware & graph databases: Why graph-native matters), following a relationship is then a pointer chase at about the same cost per hop however big the graph grows, where a system without it looks up each step in a global index.

Think of a subway map. Each station is a node. Each colored line is a relationship with a label and direction. You find a route by following the lines from station to station, not by looking every station up in a table. That mental model carries directly into a graph database: traversal is pointer chasing, one hop at a time, and each hop is cheap. But cheap hops do not make a long trip cheap. If every station connects to many others, the number of possible routes multiplies with every hop, as we will see.

How does a Cypher query mirror the mental model?

Cypher reads like ASCII art of the pattern you want. This query finds every thread Sam sent:

MATCH (p:Person {name: "Sam"})-[:SENT]->(t:Thread)
RETURN t

You draw the shape: a person node with that property, an arrow labeled SENT, and a target thread node. If you have created an index on the name (CREATE INDEX FOR (p:Person) ON (p.name)), the database finds Sam through it; without one, it scans every Person node to find him. From there it follows Sam's outgoing SENT relationships and returns whatever it lands on. No join predicates.

Multi-hop questions add variable-length paths. This asks for unanswered threads sent by anyone within 1 to 3 working relationships of the user:

MATCH (me:Person {id: $myId})-[:WORKS_WITH]-{1,3}(colleague:Person)-[:SENT]->(t:Thread)
WHERE t.unanswered = true AND colleague <> me
RETURN DISTINCT colleague.name, t.subject

The {1,3} means "follow the WORKS_WITH relationship one to three times." Older Cypher, and many examples online, write the same thing as -[:WORKS_WITH*1..3]-; Neo4j's manual on variable-length patterns says that older form still works but does not conform to the GQL standard. Two details matter. WORKS_WITH has no real direction (if I work with you, you work with me), so the pattern has no arrowhead and matches either direction. And the same colleague can be reached along several paths, so DISTINCT removes the repeats, while colleague <> me stops the walk from counting the user as their own colleague.

Why do multi-hop questions strain SQL joins?

A SQL join combines two tables by matching keys. In a relational database, each hop of a relationship question is another join, usually with an index lookup for every row it touches. With a fixed number of hops you write a chain of self-joins on a works_with table; for "one to three hops" you write a recursive query. As the joins pile up, the query planner has more orders to choose from and its estimates get worse.

SQL is not helpless here. Postgres can walk relationships with recursive queries (WITH RECURSIVE), including built-in cycle detection. Here is the same question in SQL, assuming works_with stores each pair in both directions:

WITH RECURSIVE reach(person_id, depth) AS (
    SELECT colleague_id, 1
    FROM works_with
    WHERE person_id = $1
  UNION
    SELECT w.colleague_id, r.depth + 1
    FROM reach r
    JOIN works_with w ON w.person_id = r.person_id
    WHERE r.depth < 3
)
SELECT DISTINCT r.person_id, t.id
FROM reach r
JOIN threads t ON t.sender_id = r.person_id
WHERE t.unanswered AND r.person_id <> $1;

The SQL:2023 standard also added property graph queries inside SQL (SQL/PGQ, ISO/IEC 9075-16), with pattern syntax close to Cypher. So the real difference is not what can be asked. It is how each hop is done and how readable the query stays: a native graph follows stored links, and a three-hop pattern stays one line.

Neither approach escapes the fan-out. A 3-hop query visits up to (connections per node) multiplied by itself three times. If everyone in Mailmind's graph has 50 colleagues, the first hop reaches 50 people, the second up to 2,500 paths, and the third up to 125,000, in any database. Following each link is cheap in a graph, but 125,000 cheap steps are still 125,000 steps. So a deep query that starts at a very connected node (a company-wide mailing list, a shared support address) can be slow in a graph too. Cap the depth, start from specific nodes, and watch out for the busiest ones.

For Mailmind, "who introduced me to the merchant I'm chasing a refund from?" is a 3-hop path (me → colleague → introduction thread → merchant). Each step follows a few links from a specific node, so it stays fast even when the system holds millions of threads and hundreds of thousands of contacts.

How does a graph become an agent's long-term memory?

An AI assistant's hardest questions are relationship-heavy. "What subscriptions did I pay for through which credit cards last year?" "Everyone connected to the Falcon project I owe replies to." "Who introduced me to the person I'm emailing right now?" Each of those is a few traversals in a graph, where a SQL query would chain many tables or recurse.

Graph databases let you add relationship types without a schema migration. When Mailmind discovers that an email thread introduced two people, it creates an INTRODUCED_BY relationship from each person introduced to the author of the thread. If later you want to model that an email thread resolves a support case, you add a RESOLVED relationship between the thread node and a Case node. No schema migration is needed to start writing the new type. Old threads still need a backfill job if you want them to have it, so the new relationship is only as complete as the data you have run it over.

The real memory payoff comes from combining this with entity resolution. Once every alias of Sam is collapsed into a single Person node, every relationship attached to Sam across all mailboxes and threads lands on that one node. The graph becomes the single source of truth for how everything the assistant knows is connected. Agents query the graph to retrieve context for a tool call, to decide which colleague to CC on a draft, or to surface a past refund that looks similar to a new one.

How does the agent talk to the graph?

There are two ways to let an agent use the graph, and they carry very different risks.

The safer way is a fixed tool for each question, built the way Tool Calling and MCP: How Agents Touch the World describes. The model picks the tool and fills in an ID. Your code runs a query you wrote and tested, with the ID passed as a parameter, never pasted into the query text (the same rule that prevents SQL injection):

{
  "name": "find_introducer",
  "description": "Find who introduced the user to a given person, by following INTRODUCED_BY links in Mailmind's contact graph. Use this when the user asks how they know someone or who connected them. Returns at most 5 introducers, each with the ID of the introduction thread.",
  "input_schema": {
    "type": "object",
    "properties": {
      "person_id": {
        "type": "string",
        "description": "The canonical ID of the person, as returned by search_contacts, such as per_0193."
      }
    },
    "required": ["person_id"]
  }
}

MATCH (target:Person {id: $personId})-[r:INTRODUCED_BY]->(introducer:Person)
RETURN introducer.name, r.thread_id
LIMIT 5

The flexible way is to let the model write Cypher itself. That answers questions nobody planned for, but generated queries go wrong in new ways: a pattern that joins the wrong things and returns a confident wrong answer, an unbounded path (* with no upper limit) that walks half the graph, or a write clause such as DELETE or SET that changes memory. If you allow it, apply the structural limits from Guardrails: Input, Process, Output: connect with credentials that can only read, reject queries that contain write clauses, require an upper bound on every path, and set a timeout and a row limit. Many teams start with fixed tools and add generated queries only for a reviewed set of question types.

Should we replace the relational database entirely?

No. Mailmind still needs a relational store for operational data. User settings, application state, plain key-value lookups, and audit logs all belong in a relational database with mature tooling and well-understood backup strategies.

The graph earns its place as the relationship layer. When an email arrives, an ingestion pipeline resolves entities and writes nodes and relationships into the graph. Relationship-heavy queries go against the graph. Simple lookups stay on the relational side. That hybrid architecture isolates risk and puts each store to work on what it does best.

The decision to add a graph turns on one question: are deep or variable-length relationship queries central to the product's value? For an assistant whose job is connecting your people, threads, orders, and commitments, they often are. If your relationship questions are mostly one or two fixed hops, Postgres with good indexes, and a recursive query where needed, may be all you need.

How do the fourteen parts fit together?

This is the last part of the series, so here is the whole of Mailmind on one page. Follow an email from the top: it is screened on the way in, the agent loop reasons and calls tools, memory and retrieval feed it context, checks verify what it produces, a person approves anything risky, and traces and evaluations close the loop.

A final design question to try on your own: Mailmind's users want it to pay small invoices for them, up to 50 dollars each. Walk the diagram and decide what changes. One good answer: a new payment tool with a hard spending limit inside the tool, not in the prompt; human approval for every payment at first, showing the exact payee and amount; the agent that reads invoice emails gets no payment tool at all, so an injected invoice cannot pay itself; entity resolution must match the payee to a known merchant before any payment; golden cases for fake and duplicate invoices; every payment fully traced and kept; and no self-improving loop on payment rules until months of clean data say it is safe.

Quick Reference

Frequently Asked Questions

Q: When does adding a graph pay for its complexity?

A graph earns its keep when the product's most valuable queries are deep or variable-length relationship questions. If you only need simple lookups, a relational database with indexes is cheaper and simpler. The moment users expect "find everyone related to X who touched Y" style answers, a graph's cheap hops and readable path queries start to pay for themselves. Measure on your own data before you decide.

Q: Can't we just denormalize and precompute those joins in SQL?

Denormalizing a level or two works. But precomputing every 4-step path means storing one row per path, and the number of paths grows fast with the number of connections and relationship types. A graph stores only the direct relationships and walks them on demand, staying sparse while covering any depth you allow.

Q: Do we need a dedicated graph database, or can an extension on top of Postgres work?

Extensions like Apache AGE add graph queries inside Postgres, and recursive SQL covers many relationship questions on its own. They still run on a relational engine underneath, so test them on your traversal-heavy queries before you decide. For a team that already runs Postgres, starting there and adding a native graph only when measurements demand it is a reasonable path.

Q: How does a graph handle schema evolution when relationships change meaning over time?

You add new relationship types without touching existing ones. An old INTRODUCED_BY relationship can coexist with a newer INTRODUCED_IN_THREAD relationship. Since queries match specific types, old data stays queryable. You can version relationship types and deprecate old ones later by stopping writes to them. Moving old data onto the new type is still a backfill job, just not a schema migration.

Q: What's the learning curve for a team used only to SQL?

Cypher's pattern syntax is quick to read for most SQL users, because it mirrors how you would draw the answer on a whiteboard. The harder shift is design: you must think in terms of nodes and relationships, not rows and foreign keys. The team needs to become comfortable asking "what are the things, and how are they connected?" before they write a single query.

Test yourself

Your team is debating the Mailmind architecture. Half the team argues that Postgres, with proper indexes, can handle the "who introduced me to this vendor?" query at scale. The other half wants a dedicated graph database. You've been asked to decide.

Answer: List the top 20 queries Mailmind will run and count how many need more than two hops or a variable depth. The "introduced by" question is a 3-hop path: me → colleague → introduction thread → vendor. "Active subscriptions paid via card ending in 4242" is two hops. Postgres is not helpless: a recursive query handles variable depth, and indexes make each hop's lookup fast. So the question is not whether SQL can answer. It is whether deep, variable-length traversals are the main workload: if they are, a graph does each hop as a pointer follow and keeps those queries short and readable. Either way, cost grows with fan-out, so cap the depth and start from specific nodes. If most valuable queries are multi-hop, go hybrid: keep Postgres for the operational schema and add a graph fed by an ingestion pipeline, with entity resolution (Entity Resolution: One Thing, Many Names) supplying clean node identities. If not, stay on Postgres.

If you want this kind of breakdown every week, how real systems actually work under the hood, subscribe to Internals Decoded at internalsdecoded.com.

Sources

• Neo4j Cypher Manual
• Neo4j Graph Data Modeling Guide
• The co-evolution of computer hardware & graph databases: Why graph-native matters
• variable-length patterns
• recursive queries
• age.apache.org