Many-to-many with junction tables in SQL - Time & Space Complexity

Time Complexity: Many-to-many with junction tables

O(n)

Understanding Time Complexity

When working with many-to-many relationships in databases, we often use junction tables to connect data.

We want to understand how the time to get results grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT students.name, courses.title
FROM students
JOIN student_courses ON students.id = student_courses.student_id
JOIN courses ON courses.id = student_courses.course_id
WHERE students.id = 123;
    

This query finds all courses taken by a specific student using a junction table.

Identify Repeating Operations

Look for repeated steps that affect performance.

• Primary operation: Scanning the junction table rows matching the student ID.
• How many times: Once for each course the student takes.

How Execution Grows With Input

As the number of courses a student takes grows, the query does more work.

Input Size (n)	Approx. Operations
10	About 10 lookups in the junction table and courses table
100	About 100 lookups
1000	About 1000 lookups

Pattern observation: The work grows roughly in direct proportion to the number of courses linked to the student.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all courses grows linearly with how many courses the student has.

Common Mistake

[X] Wrong: "The query time depends on the total number of students or courses in the database."

[OK] Correct: The query only processes rows related to one student, so the total database size does not directly affect this query's time.

Interview Connect

Understanding how many-to-many queries scale helps you explain database performance clearly and confidently.

Self-Check

What if we changed the query to find all students enrolled in a specific course? How would the time complexity change?

Practice

1. What is the main purpose of a junction table in a many-to-many relationship?

easy

A. To store pairs of related records from two tables using foreign keys

B. To store all data from both tables in one place

C. To replace one of the original tables completely

D. To create a one-to-one relationship between tables

Solution

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

   Many-to-many means each record in one table can relate to many records in another table, and vice versa.

2. Step 2: Role of junction table

   A junction table holds pairs of foreign keys from both tables to link related records without duplicating data.

3. Final Answer:

   To store pairs of related records from two tables using foreign keys -> Option A

4. Quick Check:

   Junction table = pairs of foreign keys [OK]

Hint: Junction tables link two tables with pairs of keys [OK]

Common Mistakes:

• Thinking junction table stores all data from both tables
• Confusing junction table with a single main table
• Assuming junction table creates one-to-one links

2. Which SQL statement correctly creates a junction table named StudentCourse linking Student and Course tables by their IDs?

easy

A. CREATE TABLE StudentCourse (StudentID INT, CourseID INT, FOREIGN KEY (StudentID) REFERENCES Student(ID));

B. CREATE TABLE StudentCourse (ID INT PRIMARY KEY, StudentID INT, CourseID INT);

C. CREATE TABLE StudentCourse (StudentID INT UNIQUE, CourseID INT UNIQUE);

D. CREATE TABLE StudentCourse (StudentID INT, CourseID INT, PRIMARY KEY (StudentID, CourseID));

Solution

1. Step 1: Define junction table columns

   It needs two columns for foreign keys: StudentID and CourseID.

2. Step 2: Set primary key on both columns

   Primary key on (StudentID, CourseID) ensures unique pairs and no duplicates.

3. Final Answer:

   CREATE TABLE StudentCourse (StudentID INT, CourseID INT, PRIMARY KEY (StudentID, CourseID)); -> Option D

4. Quick Check:

   Junction table needs composite primary key [OK]

Hint: Use composite primary key on both foreign keys [OK]

Common Mistakes:

• Using UNIQUE on individual columns instead of composite key
• Missing one foreign key column
• Not defining primary key on the pair

3. Given tables Author, Book, and junction table AuthorBook with columns AuthorID and BookID, what does this query return?

SELECT Author.Name, Book.Title FROM Author
JOIN AuthorBook ON Author.ID = AuthorBook.AuthorID
JOIN Book ON Book.ID = AuthorBook.BookID;

medium

A. A list of authors and the titles of books they wrote

B. A list of books without any author names

C. A list of all authors with all books, including unrelated pairs

D. An error because of missing WHERE clause

Solution

1. Step 1: Understand JOINs with junction table

   The query joins Author to AuthorBook by AuthorID, then AuthorBook to Book by BookID, linking authors to their books.

2. Step 2: Result of the query

   It returns pairs of author names and book titles where the author wrote the book, no unrelated pairs included.

3. Final Answer:

   A list of authors and the titles of books they wrote -> Option A

4. Quick Check:

   JOINs with junction table = related pairs only [OK]

Hint: JOIN junction table to get related pairs only [OK]

Common Mistakes:

• Thinking it returns all combinations of authors and books
• Expecting an error without WHERE clause
• Ignoring the role of junction table in filtering

4. You wrote this query to find all students and their courses:

SELECT Student.Name, Course.Title FROM Student
JOIN StudentCourse ON Student.ID = StudentCourse.StudentID
JOIN Course ON Course.ID = StudentCourse.CourseID
WHERE StudentCourse.StudentID = Student.ID;

But it has a problem. What is the problem?

medium

A. The WHERE clause is redundant and causes a syntax error

B. Missing alias for tables causes ambiguity

C. The WHERE clause is unnecessary because JOIN already matches IDs

D. StudentCourse.CourseID is missing in the WHERE clause

Solution

1. Step 1: Analyze the JOIN conditions

   The JOINs already match Student.ID to StudentCourse.StudentID and Course.ID to StudentCourse.CourseID.

2. Step 2: Check the WHERE clause

   The WHERE clause repeats the JOIN condition, which is unnecessary but not an error; however, it does not filter or add value.

3. Final Answer:

   The WHERE clause is unnecessary because JOIN already matches IDs -> Option C

4. Quick Check:

   JOIN matches IDs, WHERE clause redundant [OK]

Hint: JOIN conditions handle matching; WHERE often not needed here [OK]

Common Mistakes:

• Assuming WHERE clause causes syntax error
• Adding unnecessary conditions that duplicate JOINs
• Confusing alias usage with errors

5. You have tables Employee, Project, and junction table EmployeeProject with EmployeeID and ProjectID. How do you find employees who work on all projects listed in Project?

hard

A. Join EmployeeProject and Project, then filter with WHERE ProjectID IS NOT NULL

B. Use GROUP BY EmployeeID and HAVING count of projects equal to total projects count

C. Select employees with a simple JOIN to EmployeeProject without grouping

D. Use DISTINCT on EmployeeID in EmployeeProject without counting projects

Solution

1. Step 1: Count total projects

   Find total number of projects from Project table.

2. Step 2: Group EmployeeProject by EmployeeID

   Count how many projects each employee works on.

3. Step 3: Use HAVING to compare counts

   Only select employees whose project count equals total projects count.

4. Final Answer:

   Use GROUP BY EmployeeID and HAVING count of projects equal to total projects count -> Option B

5. Quick Check:

   Group and count projects per employee = all projects [OK]

Hint: Group by employee, HAVING count = total projects [OK]

Common Mistakes:

• Not grouping and counting projects per employee
• Using WHERE instead of HAVING for aggregate filtering
• Ignoring total projects count in comparison