Relational Databases vs. Graph Databases

What each model actually is

A relational database organizes data into tables of rows and columns. Relationships between tables exist only as foreign key values; there is no physical link between a row in one table and a row in another until a query joins them. The join is computed every time, by matching key values across tables.

A graph database organizes data as nodes (entities) and edges (relationships), where each edge is a first-class record connecting two nodes and can carry its own properties. Many graph engines use index-free adjacency: each node stores direct references to its adjacent edges, so moving from one node to its neighbors is a pointer lookup, not a search through an index or a table scan.

The term "RGDB" is sometimes used loosely to mean a relational database that has been extended or layered with graph capability, as opposed to a database built as a graph engine from the start.

How traversal cost differs internally

In a relational database, following a chain of relationships means joining the same table to itself (or across tables) once per hop. A one-hop query (find a user's direct friends) is a single join and is usually fast with the right index. A multi-hop query (find friends of friends of friends) requires either several nested joins or a recursive query, and the cost tends to grow with each additional hop because the engine has to re-evaluate matches at every level.

In a graph database, each hop is a pointer traversal from the current node to its stored adjacency list. The cost of one hop does not depend on the total size of the dataset, only on the number of edges at that node. This is the main reason graph engines outperform relational joins on deep or variable-depth traversals, such as shortest-path or recommendation queries.

Example: hierarchical traversal in both models

Here is the same problem, finding every employee who reports up to a given manager at any depth, solved two ways. PostgreSQL can do this with a recursive common table expression:

WITH RECURSIVE org_chart AS (
  SELECT id, name, manager_id
  FROM employees
  WHERE id = 1

  UNION ALL

  SELECT e.id, e.name, e.manager_id
  FROM employees e
  JOIN org_chart o ON e.manager_id = o.id
)
SELECT * FROM org_chart;

This works correctly, but the planner has to re-run the join step for every level of depth, and performance depends heavily on indexing manager_id. A graph engine using a Cypher-style query language expresses the same traversal as a single pattern match. Exact syntax varies by engine; the example below follows the general openCypher pattern-matching style:

MATCH (m:Employee {id: 1})

The * means "any number of hops," and the engine walks edges directly instead of re-joining a table at each level.