Introduction: From Tables to Graphs

The Relational Comfort Zone

Think of a relational database like a filing cabinet with many labeled drawers. Each drawer holds one type of document — one drawer for Students, one for Classes, one for Enrollments. When you need to answer "which students are in which classes?", you open all three drawers and manually cross-reference them. This cross-referencing is called a JOIN, and relational databases are built around it.

In a relational database, modeling a Many-to-Many relationship (e.g., Students enrolled in Classes) means creating a Join Table (also called an Associative Entity):

• Table Students
• Table Classes
• Table Enrollments (StudentId, ClassId)

To answer "who is enrolled in Math101?", the database engine JOINs all three tables at query time. This is powerful but expensive at scale — joins require reading from multiple locations and combining results in memory.

The DynamoDB Approach: Adjacency Lists

DynamoDB has no JOIN operation. Instead, it uses a pattern called an Adjacency List — a way of storing graph-like relationships directly in a single table so that complex queries can be answered with a single request.

A graph is a data structure with two components:

• Nodes (also called Vertices): the entities themselves — a Student, a Class, a User.
• Edges: the relationships between entities — "Student A is enrolled in Class B", "User X follows User Y".

In DynamoDB, both Nodes and Edges are stored as items in the same table. The trick is in how you assign the Partition Key (PK) and Sort Key (SK):

• Node item: PK = ENTITY#id, SK = METADATA — stores the entity's own attributes.
• Edge item: PK = ENTITY#id, SK = RELATED_ENTITY#other_id — stores the relationship and any relationship-level attributes (e.g., enrollment date, role).

Because all edges for a given entity share the same PK, a single Query on that PK returns the entity itself AND all its relationships in one round-trip.

Why This Matters at Scale

The adjacency list pattern is the foundation of Single-Table Design in DynamoDB. Every advanced pattern — sparse indexes, write sharding, inverted indexes — builds on top of this core idea. Understanding it deeply means you can model almost any domain in DynamoDB without sacrificing query performance.