Adjacency list pattern in DynamoDB - Mini Project: Build & Apply

Building a Family Tree Using the Adjacency List Pattern in DynamoDB

📖 Scenario: You want to create a simple family tree database using DynamoDB. Each person will have a unique ID and a reference to their parent's ID. This way, you can see who is related to whom by following the parent links.

🎯 Goal: Build a DynamoDB table structure using the adjacency list pattern to represent family members and their parent-child relationships.

📋 What You'll Learn

Create a DynamoDB table with a primary key called PersonID

Add items representing family members with attributes PersonID, Name, and ParentID

Use ParentID to link each child to their parent

Write a query to find all children of a specific parent using ParentID

Ensure the data structure supports easy traversal of family relationships

💡 Why This Matters

🌍 Real World

This pattern is useful for storing hierarchical data like organizational charts, family trees, or category trees in databases that do not support joins.

💼 Career

Understanding adjacency list pattern helps in designing efficient NoSQL database schemas and writing queries to navigate hierarchical relationships.

1

Create the DynamoDB table and add family members

Create a DynamoDB table named FamilyTree with PersonID as the primary key. Then add these family members as items with attributes exactly as follows: PersonID: '1', Name: 'John', ParentID: null, PersonID: '2', Name: 'Mary', ParentID: '1', and PersonID: '3', Name: 'Sam', ParentID: '1'.

DynamoDB

# Create the FamilyTree table and add the three family members
# Your code here

Hint

Think of FamilyTree as a list of dictionaries where each dictionary is a family member with their ID, name, and parent's ID.

2

Add a variable to select the parent to find children for

Create a variable called parent_id and set it to the string '1'. This will be used to find all children of the parent with PersonID '1'.

DynamoDB

FamilyTree = [
    {'PersonID': '1', 'Name': 'John', 'ParentID': None},
    {'PersonID': '2', 'Name': 'Mary', 'ParentID': '1'},
    {'PersonID': '3', 'Name': 'Sam', 'ParentID': '1'}
]

# Create a variable called parent_id and set it to '1'
# Your code here

Hint

This variable will help you filter the family members who have this parent.

3

Write a query to find children of the selected parent

Create a list called children that contains all items from FamilyTree where the ParentID matches the parent_id variable.

DynamoDB

FamilyTree = [
    {'PersonID': '1', 'Name': 'John', 'ParentID': None},
    {'PersonID': '2', 'Name': 'Mary', 'ParentID': '1'},
    {'PersonID': '3', 'Name': 'Sam', 'ParentID': '1'}
]

parent_id = '1'

# Create a list called children with all family members whose ParentID equals parent_id
# Your code here

Hint

Use a list comprehension to filter family members by ParentID.

4

Add a final attribute to mark the root ancestor

Add a new key called IsRoot to each item in FamilyTree. Set it to true if ParentID is null, otherwise false.

DynamoDB

FamilyTree = [
    {'PersonID': '1', 'Name': 'John', 'ParentID': None},
    {'PersonID': '2', 'Name': 'Mary', 'ParentID': '1'},
    {'PersonID': '3', 'Name': 'Sam', 'ParentID': '1'}
]

parent_id = '1'

children = [member for member in FamilyTree if member['ParentID'] == parent_id]

# Add 'IsRoot' key to each family member
# Your code here

Hint

Loop through each family member and add the IsRoot key based on whether ParentID is null.

Practice

1. What does the adjacency list pattern store in each item to represent relationships in DynamoDB?

easy

A. The parent item's identifier

B. The list of all child items

C. The full path from root to the item

D. The depth level of the item in the hierarchy

Solution

1. Step 1: Understand adjacency list pattern basics

   The adjacency list pattern stores a reference to the parent item for each node to represent hierarchy.

2. Step 2: Identify what is stored per item

   Each item contains the parent's ID, not the children or full path or depth.

3. Final Answer:

   The parent item's identifier -> Option A

4. Quick Check:

   Adjacency list = parent ID stored [OK]

Hint: Remember: adjacency list stores parent ID only [OK]

Common Mistakes:

• Thinking it stores all children in each item
• Confusing with storing full path or depth
• Assuming it stores unrelated metadata

2. Which of the following is the correct way to represent a parent-child relationship in a DynamoDB item using the adjacency list pattern?

easy

A. { "ItemId": "123", "Children": ["456", "789"] }

B. { "ItemId": "123", "ParentId": "456" }

C. { "ItemId": "123", "Path": "/root/456/123" }

D. { "ItemId": "123", "Depth": 2 }

Solution

1. Step 1: Identify adjacency list item structure

   Adjacency list stores the parent ID inside each item to link it to its parent.

2. Step 2: Match correct JSON structure

   { "ItemId": "123", "ParentId": "456" } shows an item with its own ID and a ParentId field, which is correct.

3. Final Answer:

   { "ItemId": "123", "ParentId": "456" } -> Option B

4. Quick Check:

   ParentId field present = adjacency list format [OK]

Hint: Look for ParentId key in item JSON [OK]

Common Mistakes:

• Using Children array instead of ParentId
• Including full path or depth instead of parent reference
• Confusing item ID with parent ID

3. Given the following DynamoDB items using adjacency list pattern:

{ "ItemId": "1", "ParentId": null }

{ "ItemId": "2", "ParentId": "1" }

{ "ItemId": "3", "ParentId": "1" }

{ "ItemId": "4", "ParentId": "2" }

If you query for items with ParentId = '1', which items will you get?

medium

A. [{ "ItemId": "2", "ParentId": "1" }, { "ItemId": "3", "ParentId": "1" }]

B. [{ "ItemId": "1", "ParentId": null }]

C. [{ "ItemId": "4", "ParentId": "2" }]

D. [{ "ItemId": "2", "ParentId": "1" }, { "ItemId": "3", "ParentId": "1" }, { "ItemId": "4", "ParentId": "2" }]

Solution

1. Step 1: Understand query condition

   The query filters items where ParentId equals '1'.

2. Step 2: Identify matching items

   Items with ParentId '1' are ItemId '2' and '3'. Item '4' has ParentId '2', so it does not match.

3. Final Answer:

   [{ "ItemId": "2", "ParentId": "1" }, { "ItemId": "3", "ParentId": "1" }] -> Option A

4. Quick Check:

   Filter ParentId='1' returns items 2 and 3 [OK]

Hint: Filter by ParentId to get direct children only [OK]

Common Mistakes:

• Including items with different ParentId values
• Confusing root item with children
• Assuming query returns grandchildren

4. You wrote this DynamoDB query to get children of item '5':

FilterExpression: "ParentId = :pid", ExpressionAttributeValues: { ":pid": "5" }

But it returns no results, even though you know children exist. What is the likely error?

medium

A. The ExpressionAttributeValues syntax is incorrect

B. You should use KeyConditionExpression instead of FilterExpression

C. You need to query with ItemId = '5' instead

D. ParentId attribute is missing or named differently in items

Solution

1. Step 1: Check attribute naming

   If ParentId attribute is missing or named differently, filter finds no matches.

2. Step 2: Verify attribute presence in items

   Ensure all child items have ParentId attribute exactly named 'ParentId'. If not, query returns empty.

3. Final Answer:

   ParentId attribute is missing or named differently in items -> Option D

4. Quick Check:

   Attribute name mismatch causes no results [OK]

Hint: Check attribute names match exactly in query and items [OK]

Common Mistakes:

• Confusing FilterExpression with KeyConditionExpression
• Incorrect syntax in ExpressionAttributeValues
• Querying by ItemId instead of ParentId

5. You want to retrieve the full hierarchy path from a child item up to the root using the adjacency list pattern in DynamoDB. Which approach is best?

hard

A. Use a DynamoDB join operation to combine parent and child items

B. Store the full path string in each item and query it directly

C. Iteratively query each item's ParentId until reaching the root

D. Use a single query filtering all items with ParentId equal to the child's ID

Solution

1. Step 1: Understand adjacency list limitations

   Adjacency list stores only parent references, so full path is not stored.

2. Step 2: Retrieve full path by iterative queries

   To get full path, query each item's parent repeatedly until root (ParentId null) is reached.

3. Step 3: Evaluate other options

   Store the full path string in each item and query it directly is a different pattern (materialized path). Use a single query filtering all items with ParentId equal to the child's ID gets children, not parents. Use a DynamoDB join operation to combine parent and child items is invalid as DynamoDB has no join.

4. Final Answer:

   Iteratively query each item's ParentId until reaching the root -> Option C

5. Quick Check:

   Adjacency list needs iterative parent queries for full path [OK]

Hint: Follow parent links step-by-step to build full path [OK]

Common Mistakes:

• Expecting DynamoDB to support joins
• Assuming full path is stored in adjacency list
• Trying to get full path with single query filtering children