Data denormalization strategies in Firebase - Time & Space Complexity

Time Complexity: Data denormalization strategies

O(n)

Understanding Time Complexity

When using data denormalization in Firebase, it is important to understand how the time to update or read data changes as the data grows.

We want to know how the number of operations changes when we duplicate data across multiple places.

Scenario Under Consideration

Analyze the time complexity of updating denormalized data in Firebase.

const updateUserName = async (userId, newName) => {
  // Update user name in main user record
  await db.ref(`users/${userId}/name`).set(newName);

  // Update user name in all posts by this user
  const postsSnapshot = await db.ref('posts').orderByChild('userId').equalTo(userId).once('value');
  postsSnapshot.forEach(post => {
    post.ref.child('userName').set(newName);
  });
};

This code updates a user's name in their main profile and then updates all posts they made with the new name.

Identify Repeating Operations

Look at what repeats when updating denormalized data.

• Primary operation: Writing the new name to each post made by the user.
• How many times: Once for the main user record, then once for each post by that user.

How Execution Grows With Input

As the number of posts by a user grows, the number of update operations grows too.

Input Size (number of posts)	Approx. Api Calls/Operations
10	11 (1 user update + 10 post updates)
100	101 (1 user update + 100 post updates)
1000	1001 (1 user update + 1000 post updates)

Pattern observation: The number of operations grows directly with the number of posts to update.

Final Time Complexity

Time Complexity: O(n)

This means the time to update grows linearly with the number of denormalized entries to update.

Common Mistake

[X] Wrong: "Updating the main user record automatically updates all denormalized copies instantly."

[OK] Correct: Each denormalized copy must be updated separately, so the time grows with how many copies exist.

Interview Connect

Understanding how denormalization affects update time helps you design scalable Firebase apps and shows you can think about real-world data costs.

Self-Check

What if we stored user names only in the main user record and referenced them in posts without copying? How would the time complexity change?

Practice

1. What is the main purpose of data denormalization in Firebase?

easy

A. To copy data for faster reading and fewer database calls

B. To reduce data storage by removing duplicates

C. To encrypt data for better security

D. To create backups automatically

Solution

1. Step 1: Understand denormalization concept

   Denormalization means copying data to make reading faster and reduce the number of database calls.

2. Step 2: Identify the main goal in Firebase context

   Firebase uses denormalization to speed up data access, not to reduce storage or encrypt data.

3. Final Answer:

   To copy data for faster reading and fewer database calls -> Option A

4. Quick Check:

   Denormalization = faster reads [OK]

Hint: Denormalization means copying data to speed up reads [OK]

Common Mistakes:

• Confusing denormalization with data encryption
• Thinking denormalization reduces storage space
• Assuming denormalization creates backups

2. Which Firebase data structure is best suited for denormalization?

easy

A. Nested arrays with repeated data

B. Encrypted blobs stored in Firestore

C. Flat JSON objects with duplicated fields

D. Single document with all data combined

Solution

1. Step 1: Review Firebase data structures

   Firebase uses JSON-like objects. Denormalization copies data into flat objects with duplicated fields for fast access.

2. Step 2: Compare options

   Nested arrays with repeated data are not ideal; single documents can be large and slow; encrypted blobs are unrelated to denormalization.

3. Final Answer:

   Flat JSON objects with duplicated fields -> Option C

4. Quick Check:

   Denormalization uses flat JSON with duplicates [OK]

Hint: Denormalization uses flat JSON with repeated fields [OK]

Common Mistakes:

• Choosing nested arrays which complicate queries
• Using single large documents that slow reads
• Confusing encryption with denormalization

3. Given this Firebase data snippet:

{
  "users": {
    "user1": {"name": "Anna", "city": "NY"},
    "user2": {"name": "Ben", "city": "LA"}
  },
  "posts": {
    "post1": {"author": "user1", "content": "Hello"},
    "post2": {"author": "user2", "content": "Hi"}
  }
}

Which denormalized structure speeds up reading posts with author names?

medium

A. { "users": { "user1": {"name": "Anna"}, "user2": {"name": "Ben"} }, "posts": {} }

B. { "posts": { "post1": {"author": "user1", "content": "Hello"}, "post2": {"author": "user2", "content": "Hi"} } }

C. { "posts": { "post1": {"authorId": "user1"}, "post2": {"authorId": "user2"} } }

D. { "posts": { "post1": {"authorName": "Anna", "content": "Hello"}, "post2": {"authorName": "Ben", "content": "Hi"} } }

Solution

1. Step 1: Understand denormalization for faster reads

   Copy author names directly into posts to avoid extra lookups when reading posts.

2. Step 2: Analyze options

   { "posts": { "post1": {"authorName": "Anna", "content": "Hello"}, "post2": {"authorName": "Ben", "content": "Hi"} } } copies author names into posts, speeding reads. Others keep references requiring extra calls.

3. Final Answer:

   { "posts": { "post1": {"authorName": "Anna", "content": "Hello"}, "post2": {"authorName": "Ben", "content": "Hi"} } } -> Option D

4. Quick Check:

   Copy data to avoid extra lookups = { "posts": { "post1": {"authorName": "Anna", "content": "Hello"}, "post2": {"authorName": "Ben", "content": "Hi"} } } [OK]

Hint: Copy related data into posts to speed reads [OK]

Common Mistakes:

• Keeping only IDs requiring extra database calls
• Removing posts data instead of denormalizing
• Not copying author names into posts

4. You denormalized user emails into multiple places in Firebase. What is a common error when updating user email?

medium

A. Forgetting to update all copies, causing inconsistent data

B. Deleting the original user record accidentally

C. Encrypting emails twice causing read errors

D. Using arrays instead of objects for user data

Solution

1. Step 1: Understand denormalization update challenges

   When data is copied, all copies must be updated to keep data consistent.

2. Step 2: Identify common mistake

   Forgetting to update all copies leads to inconsistent emails across the database.

3. Final Answer:

   Forgetting to update all copies, causing inconsistent data -> Option A

4. Quick Check:

   Missed updates cause inconsistency [OK]

Hint: Always update every copy of denormalized data [OK]

Common Mistakes:

• Updating only one copy of data
• Deleting original data by mistake
• Confusing encryption with denormalization

5. You want to denormalize product prices into order items in Firebase. Which approach best avoids stale prices when product prices change?

hard

A. Copy product price into each order item and update all order items on price change

B. Store only product IDs in order items and fetch price dynamically on read

C. Keep prices only in product records and never copy to orders

D. Use arrays to store prices inside product documents

Solution

1. Step 1: Understand denormalization trade-offs

   Copying prices into order items speeds reads but risks stale data if not updated.

2. Step 2: Choose best approach to avoid stale data

   Storing only product IDs and fetching prices dynamically on read avoids stale prices without complex updates.

3. Final Answer:

   Store only product IDs in order items and fetch price dynamically on read -> Option B

4. Quick Check:

   Fetch price dynamically to avoid stale data [OK]

Hint: Fetch prices dynamically to keep data fresh [OK]

Common Mistakes:

• Not updating copied prices causing stale data
• Copying prices without update causing stale data
• Using arrays which complicate updates