Adjacency list pattern in DynamoDB

Introduction

The adjacency list pattern helps you store and find relationships between items, like family trees or company teams, in a simple way.

You want to represent a family tree where each person has parents and children.

You need to model an organization chart showing who reports to whom.

You want to track categories and subcategories in a product catalog.

You want to store comments and replies in a discussion thread.

You want to find all connected items starting from one item.

Syntax

DynamoDB

Table: Items
Attributes:
  - id (Primary Key)
  - parent_id (can be null or id of another item)
  - other attributes...

To find children of an item:
  Query where parent_id = :id_value

The id uniquely identifies each item.

The parent_id points to the item's parent, or is null if it has none.

Examples

This shows a root item with two children.

DynamoDB

id: 1, parent_id: null, name: 'Root Node'
id: 2, parent_id: 1, name: 'Child A'
id: 3, parent_id: 1, name: 'Child B'

Items can have children and multiple root items can exist.

DynamoDB

id: 4, parent_id: 2, name: 'Grandchild of Root'
id: 5, parent_id: null, name: 'Another Root'

This query finds all children of the item with id 1.

DynamoDB

Query: SELECT * FROM Items WHERE parent_id = 1

This query finds all root items (items without parents).

DynamoDB

Query: SELECT * FROM Items WHERE parent_id IS NULL

Sample Program

This example creates a table, adds a root item and two children, then queries the children of the root.

DynamoDB

/* DynamoDB example using AWS CLI syntax for clarity */

# Create table
aws dynamodb create-table \
    --table-name Items \
    --attribute-definitions AttributeName=id,AttributeType=S \
    --key-schema AttributeName=id,KeyType=HASH \
    --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

# Insert root item
aws dynamodb put-item --table-name Items --item '{"id": {"S": "1"}, "parent_id": {"NULL": true}, "name": {"S": "Root Node"}}'

# Insert child items
aws dynamodb put-item --table-name Items --item '{"id": {"S": "2"}, "parent_id": {"S": "1"}, "name": {"S": "Child A"}}'
aws dynamodb put-item --table-name Items --item '{"id": {"S": "3"}, "parent_id": {"S": "1"}, "name": {"S": "Child B"}}'

# Query children of root
aws dynamodb scan --table-name Items --filter-expression "parent_id = :pid" --expression-attribute-values '{":pid": {"S": "1"}}'

Important Notes

The adjacency list pattern is simple but can be slow for deep trees because you query one level at a time.

Time complexity for finding direct children is fast (depends on number of children), but finding all descendants requires multiple queries.

Use this pattern when your relationships are mostly one-level or you don't need to query deep hierarchies often.

Summary

The adjacency list pattern stores each item's parent to represent relationships.

It is easy to understand and works well for simple hierarchies.

Querying deep or complex trees may need extra logic or different patterns.