What Is a Graph Database?

A graph database stores data as nodes and the relationships between them, rather than as rows in tables. Where a relational database represents a connection between two records with a foreign key that has to be resolved through a join, a graph database stores that connection directly as an edge — a first-class object with its own properties, sitting right alongside the nodes it connects. That difference sounds small, but it changes which kinds of queries stay fast as data and its connections grow more complex.

Nodes, edges, and properties

The graph model has three basic pieces. Nodes represent entities — a person, a product, a company. Edges represent relationships between nodes — “follows,” “purchased,” “works at” — and, unlike a plain foreign key, an edge can carry its own properties, like the date a relationship started or the strength of a connection. Properties are key-value attributes attached to either nodes or edges, similar to columns in a relational table but not fixed to a rigid schema shared across every row.

A social network is the canonical example: each person is a node, each “follows” relationship is a directed edge between two nodes, and a query like “friends of friends who also follow this account” is a graph traversal — walk from one node, across a few edges, checking a condition along the way. In a relational schema, the same query means a self-join on the followers table, then another join to check the third condition, and the query gets more expensive with each additional hop you add.

Why joins get expensive and traversals don’t

This is the central technical argument for graph databases. In a relational database, a relationship isn’t stored directly — it’s implied by matching a foreign key in one table against a primary key in another, and the database has to actually perform that match at query time, for every row involved, every time the query runs. A query that needs to traverse several relationships deep — friends of friends of friends, or a supply chain three tiers up from a given part — means several chained joins, and the cost of that chain tends to grow sharply as the number of hops increases, since each join can multiply the number of intermediate rows the database has to consider.

A graph database instead stores each node’s relationships as direct, already-materialized pointers to its neighbors. Traversing from one node to its connected nodes is a matter of following those pointers, not searching for matches — a cost that stays roughly constant per hop regardless of how large the overall dataset is, since the database never has to scan the whole graph to find a specific node’s neighbors. This is often summarized as “index-free adjacency,” and it’s the property that makes deep traversals practical in a graph database in a way they usually aren’t in a relational one.

Property graphs vs RDF triple stores

Most graph databases in common use today follow the property graph model described above — nodes and edges that can each carry arbitrary key-value properties. A separate lineage, RDF triple stores, represents everything as subject-predicate-object triples ("Alice" "follows" "Bob"), a model rooted in semantic-web standards and more common in academic and linked-data contexts, with its own query language (SPARQL) rather than the graph-specific query languages (like Cypher or Gremlin) that property graph databases typically use. The two models overlap conceptually but diverge in tooling and typical use case, and it’s worth knowing which one a given product implements before assuming query patterns transfer between them.

When a graph database is the right fit

Graph databases earn their keep specifically when relationships, and traversals across them, are the main thing a query cares about — not just an occasional lookup. Common cases include social networks and recommendation engines (people who bought this also bought…), fraud detection (finding rings of accounts connected through shared attributes several hops apart), and knowledge graphs that represent facts and their relationships for retrieval and reasoning. If your data is mostly independent records with occasional simple lookups, a relational database — or for unstructured documents, a broader move to NoSQL — is usually still the simpler and better-supported choice.

Graph databases vs the rest of the field

	Relational	Document / NoSQL	Graph
Core unit	Row in a table	Document (JSON-like)	Node and edge
Relationships	Foreign keys, resolved via joins	Usually denormalized/embedded	First-class, stored directly
Best at	Structured, tabular data	Flexible schema, nested data	Deep, multi-hop traversals
Gets slower with	More join depth	N/A (relations are flattened)	Very little, per additional hop

Graph databases are also a distinct concept from the graph data structures — trees, adjacency lists, BFS and DFS traversal — taught in a computer-science curriculum; a graph database is a full persistence and query engine built around that structure, with indexing, transactions, and a query language, rather than an in-memory structure you’d implement yourself for an algorithm.

Where they fit alongside vector search

Graph databases are also increasingly used alongside vector databases in retrieval systems: a vector index finds semantically similar content, and a graph layered on top can represent the explicit relationships between those pieces of content — citations, dependencies, hierarchies — that similarity alone doesn’t capture. The two approaches to vector vs full-text search both answer “what’s relevant,” while a graph answers “what’s connected,” which is a genuinely different question worth keeping separate.

The takeaway

A graph database stores relationships as direct, first-class edges instead of implied foreign keys, which keeps multi-hop traversals fast as data grows in a way that chained relational joins usually don’t. That advantage only matters when your workload actually depends on those traversals — social graphs, recommendations, fraud rings, knowledge graphs — and for most other workloads, a relational or document database remains the simpler and more battle-tested default.