Graph Theory for Database Engineers

Translate business entities and their interactions into nodes and edges.

In this lesson, you will learn how to shift your perspective from relational tables to a graph-based model by translating business entities into nodes and their interactions into edges.

Shifting the Mental Model

In traditional relational or column-family databases, we prioritize grouping attributes together or normalizing data into tables. In graph theory, we prioritize relationships. When modeling, you must stop asking, "Where should I store this attribute?" and start asking, "How does this entity relate to others?"

Defining Nodes and Edges

To translate a domain into a graph, use these two fundamental building blocks:

Nodes (Vertices): These represent your core business entities—the "nouns" of your system (e.g., User, Product, Order).
Edges (Relationships): These represent the connections between entities—the "verbs" of your system (e.g., PURCHASED, FOLLOWS, IS_FRIEND_OF).

Unlike a join in SQL, which is calculated at query time by matching keys, an edge in a graph is a first-class citizen stored physically as a pointer or a direct reference.

Concrete Example: An E-commerce Social Network

Imagine you want to model a system where users follow each other and purchase products. Instead of building join tables, you translate your entities like this:

Nodes: Create a User node and a Product node.
Edges: Create an edge type PURCHASED that connects a User node to a Product node.

If you were to represent this in a property graph structure, it might look like this:

(User:ID_101) -[:PURCHASED {timestamp: "2023-10-01"}]-> (Product:SKU_99)
(User:ID_101) -[:FOLLOWS]-> (User:ID_202)

In a traditional database, querying "what did my friends buy?" requires joining multiple tables, which becomes computationally expensive as your dataset grows. In a graph model, you simply "traverse" the edges: start at the current user node, move across FOLLOWS edges to reach friend nodes, and then follow their PURCHASED edges to identify products. By treating relationships as stored objects rather than ephemeral query-time joins, you enable deep, multi-hop traversals that are constant-time operations relative to the path length, rather than the total size of your database.

Key Takeaway: Translate business entities into nodes and their functional interactions into edges to store relationships as first-class data, enabling efficient traversal across complex datasets.