Many-to-many with references in MongoDB - Time & Space Complexity

Time Complexity: Many-to-many with references

O(n)

Understanding Time Complexity

When working with many-to-many relationships in MongoDB using references, it's important to understand how the time to get data grows as the number of linked items grows.

We want to know how the number of operations changes when fetching related data from multiple collections.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find all students and their courses
const students = db.students.find().toArray();

for (const student of students) {
  const courses = db.courses.find({ _id: { $in: student.courseIds } }).toArray();
  // process student with courses
}
    

This code fetches all students, then for each student fetches all courses they are linked to by IDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over each student and querying courses for each.
• How many times: Once per student, and inside that, a query for their courses.

How Execution Grows With Input

As the number of students grows, the number of course queries grows too, since each student triggers a separate query.

Input Size (n students)	Approx. Operations
10	1 student query + 10 course queries
100	1 student query + 100 course queries
1000	1 student query + 1000 course queries

Pattern observation: The total operations grow roughly in direct proportion to the number of students.

Final Time Complexity

Time Complexity: O(n)

This means the time to fetch all students and their courses grows linearly with the number of students.

Common Mistake

[X] Wrong: "Fetching courses for all students is just one query, so it's constant time regardless of students."

[OK] Correct: Each student's courses are fetched separately, so the number of queries grows with students, making the total time grow too.

Interview Connect

Understanding how many queries run and how they grow with data size is a key skill. It helps you design better data fetching strategies and explain your choices clearly.

Self-Check

"What if we changed the code to fetch all courses for all students in a single query instead of one per student? How would the time complexity change?"

Practice

1. What does a many-to-many relationship with references mean in MongoDB?

easy

A. Only one collection has references, the other does not.

B. One collection stores all data, the other is empty.

C. Both collections store arrays of IDs pointing to each other.

D. Data is duplicated in both collections without IDs.

Solution

1. Step 1: Understand many-to-many references

   In MongoDB, many-to-many means each document in one collection can link to many documents in another, and vice versa.

2. Step 2: Identify how references are stored

   This is done by storing arrays of IDs in both collections, so each side knows its related documents.

3. Final Answer:

   Both collections store arrays of IDs pointing to each other. -> Option C

4. Quick Check:

   Many-to-many references = arrays of IDs in both collections [OK]

Hint: Many-to-many means both sides hold arrays of IDs [OK]

Common Mistakes:

• Thinking only one side stores references
• Confusing many-to-many with embedding all data
• Assuming data is duplicated without IDs

2. Which of the following is the correct way to store references for a many-to-many relationship between students and courses collections in MongoDB?

easy

A. { _id: 1, name: 'Alice', courses: 101 } and { _id: 101, title: 'Math', students: 1 }

B. { _id: 1, name: 'Alice', courses: [101, 102] } and { _id: 101, title: 'Math', students: [1, 2] }

C. { _id: 1, name: 'Alice', courses: 'Math' } and { _id: 101, title: 'Math', students: 'Alice' }

D. { _id: 1, name: 'Alice', courses: [] } and { _id: 101, title: 'Math', students: [] }

Solution

1. Step 1: Check reference format

   References must be arrays of IDs to represent many-to-many links.

2. Step 2: Validate { _id: 1, name: 'Alice', courses: [101, 102] } and { _id: 101, title: 'Math', students: [1, 2] }

   { _id: 1, name: 'Alice', courses: [101, 102] } and { _id: 101, title: 'Math', students: [1, 2] } shows arrays of IDs in both collections, correctly linking students and courses.

3. Final Answer:

   { _id: 1, name: 'Alice', courses: [101, 102] } and { _id: 101, title: 'Math', students: [1, 2] } -> Option B

4. Quick Check:

   Arrays of IDs in both collections = correct syntax [OK]

Hint: Use arrays of IDs, not single values or names [OK]

Common Mistakes:

• Using single ID instead of array for many-to-many
• Storing names instead of IDs as references
• Leaving reference arrays empty without reason

3. Given these two documents:
{ _id: 1, name: 'Bob', courses: [201, 202] }
{ _id: 201, title: 'History', students: [1, 3] }
What will be the result of querying the courses array for student with _id: 1?

medium

A. ['History']

B. [1, 3]

C. []

D. [201, 202]

Solution

1. Step 1: Identify the student's courses field

   The student document with _id 1 has a courses array: [201, 202].

2. Step 2: Understand the query result

   Querying the courses array for this student returns the IDs [201, 202], not titles or student IDs.

3. Final Answer:

   [201, 202] -> Option D

4. Quick Check:

   Student's courses array = [201, 202] [OK]

Hint: Query returns stored IDs, not linked document fields [OK]

Common Mistakes:

• Confusing course IDs with student IDs
• Expecting course titles instead of IDs
• Assuming empty array if unsure

4. You have these two collections:
students: { _id: 2, name: 'Eve', courses: [301] }
courses: { _id: 301, title: 'Science', students: [] }
What is the problem with this many-to-many reference setup?

medium

A. The students array in courses is missing the student ID.

B. The courses array in students is empty.

C. The student document is missing the courses field.

D. The course document has an invalid _id.

Solution

1. Step 1: Check references in both collections

   The student document lists course 301, but the course document's students array is empty.

2. Step 2: Identify missing reciprocal reference

   For many-to-many, both sides must reference each other. The course's students array should include student ID 2.

3. Final Answer:

   The students array in courses is missing the student ID. -> Option A

4. Quick Check:

   Both sides must reference each other [OK]

Hint: Both sides must list each other's IDs [OK]

Common Mistakes:

• Ignoring missing reciprocal references
• Assuming one side is enough
• Confusing empty arrays with missing fields

5. You want to find all courses taken by students who are enrolled in both course 401 and 402. Given collections with many-to-many references, which MongoDB aggregation pipeline stage helps find students enrolled in both courses?

hard

A. { $match: { courses: { $all: [401, 402] } } }

B. { $match: { courses: { $in: [401, 402] } } }

C. { $match: { courses: 401 } }

D. { $match: { courses: { $size: 2 } } }

Solution

1. Step 1: Understand the query goal

   We want students enrolled in both courses 401 and 402, so their courses array must contain both IDs.

2. Step 2: Choose correct MongoDB operator

   The $all operator matches arrays containing all specified elements, perfect for this case.

3. Final Answer:

   { $match: { courses: { $all: [401, 402] } } } -> Option A

4. Quick Check:

   $all matches arrays containing all elements [OK]

Hint: Use $all to match arrays containing all specified IDs [OK]

Common Mistakes:

• Using $in matches any, not all elements
• Using $size only checks array length, not content
• Matching single course ID misses the second course