How to Implement Adjacency List Pattern in DynamoDB

To implement the adjacency list pattern in DynamoDB, store each item with a unique ID and a reference to its parent ID in the same table. This lets you represent tree or graph structures by linking child items to their parents using a ParentId attribute.

Syntax

The adjacency list pattern in DynamoDB uses a table where each item has a unique Id and a ParentId attribute that points to its parent item. The root items have ParentId set to null or omitted.

Typical attributes:

• Id: Unique identifier for the item.
• ParentId: Identifier of the parent item.
• Other attributes: Data fields related to the item.

plaintext

Table: Items
Attributes:
  - Id (Partition Key)
  - ParentId (String, nullable)
  - Name (String)

Example item:
{
  "Id": "3",
  "ParentId": "1",
  "Name": "Child Node"
}

Example

This example shows how to create items representing a simple hierarchy of categories using the adjacency list pattern in DynamoDB.

python

import boto3
from boto3.dynamodb.conditions import Key

# Initialize DynamoDB resource
dynamodb = boto3.resource('dynamodb')
table = dynamodb.Table('Items')

# Sample data representing a tree
items = [
    {"Id": "1", "ParentId": None, "Name": "Root"},
    {"Id": "2", "ParentId": "1", "Name": "Child A"},
    {"Id": "3", "ParentId": "1", "Name": "Child B"},
    {"Id": "4", "ParentId": "2", "Name": "Grandchild A1"}
]

# Put items into the table
for item in items:
    table.put_item(Item=item)

# Query children of '1'
response = table.scan(
    FilterExpression=Key('ParentId').eq('1')
)

print("Children of node 1:")
for child in response['Items']:
    print(child)

Output

Children of node 1:
{'Id': '2', 'ParentId': '1', 'Name': 'Child A'}
{'Id': '3', 'ParentId': '1', 'Name': 'Child B'}

Common Pitfalls

Common mistakes when using the adjacency list pattern in DynamoDB include:

• Not indexing ParentId for efficient queries, causing full table scans.
• Assuming DynamoDB supports recursive queries natively; you must handle recursion in your application code.
• Using scan instead of query with proper indexes, which is inefficient.
• Not handling root nodes properly by omitting or setting ParentId to null.

python

Wrong approach (inefficient scan):
response = table.scan(
    FilterExpression=Key('ParentId').eq('1')
)

Right approach (using Global Secondary Index on ParentId):
response = table.query(
    IndexName='ParentId-index',
    KeyConditionExpression=Key('ParentId').eq('1')
)

Quick Reference

Concept	Description
Id	Unique identifier for each item (Partition Key)
ParentId	References the parent item's Id; null for root nodes
Global Secondary Index	Create on ParentId for efficient child lookups
Query vs Scan	Use Query with GSI on ParentId instead of Scan for performance
Recursion	Handle tree traversal in application code, DynamoDB has no recursive queries

Key Takeaways

Store each item with a unique Id and a ParentId pointing to its parent to model hierarchy.

Create a Global Secondary Index on ParentId to efficiently query child items.

DynamoDB does not support recursive queries; handle recursion in your application.

Avoid using scan for parent-child lookups; use query with proper indexes.

Root nodes should have ParentId set to null or omitted.