One-to-many relationship design in SQL - Time & Space Complexity

Time Complexity: One-to-many relationship design

O(n)

Understanding Time Complexity

When working with one-to-many relationships in databases, it's important to understand how query time grows as data increases.

We want to know how the time to get related data changes when there are more records.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT customers.name, orders.order_id
FROM customers
JOIN orders ON customers.customer_id = orders.customer_id
WHERE customers.customer_id = 123;
    

This query finds all orders for one customer by joining the customers and orders tables on their IDs.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Scanning the orders table to find matching orders for the customer.
• How many times: Once for each order that belongs to the customer.

How Execution Grows With Input

As the number of orders for a customer grows, the query takes longer.

Input Size (n)	Approx. Operations
10 orders	About 10 checks to find orders
100 orders	About 100 checks
1000 orders	About 1000 checks

Pattern observation: The time grows directly with the number of orders for that customer.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all orders grows in a straight line with how many orders the customer has.

Common Mistake

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

[OK] Correct: The query filters by one customer, so only that customer's orders affect time, not all customers.

Interview Connect

Understanding how queries scale with data size helps you design efficient databases and write fast queries, a key skill in real projects.

Self-Check

"What if we added an index on orders.customer_id? How would that change the time complexity?"

Practice

1. What does a one-to-many relationship in a database mean?

easy

A. One record in a table relates to many records in another table

B. Many records in a table relate to one record in the same table

C. One record relates to exactly one record in another table

D. Many records relate to many records in another table

Solution

1. Step 1: Understand relationship types

   A one-to-many relationship means one record in a table connects to multiple records in another table.

2. Step 2: Match definition to options

   One record in a table relates to many records in another table correctly describes this as one record relating to many records in another table.

3. Final Answer:

   One record in a table relates to many records in another table -> Option A

4. Quick Check:

   One-to-many = one record to many records [OK]

Hint: One-to-many means one record links to many records [OK]

Common Mistakes:

• Confusing one-to-many with many-to-many
• Thinking one-to-many means one record links to one record
• Mixing up the direction of the relationship

2. Which SQL statement correctly creates a foreign key for a one-to-many relationship from Orders to Customers?

easy

A. ALTER TABLE Customers ADD FOREIGN KEY (OrderID) REFERENCES Orders(OrderID);

B. ALTER TABLE Customers ADD FOREIGN KEY (CustomerID) REFERENCES Orders(OrderID);

C. ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID);

D. ALTER TABLE Orders ADD FOREIGN KEY (OrderID) REFERENCES Customers(CustomerID);

Solution

1. Step 1: Identify the 'many' and 'one' tables

   Orders is the 'many' side, Customers is the 'one' side in a one-to-many relationship.

2. Step 2: Add foreign key in 'many' table referencing 'one' table

   The foreign key should be in Orders referencing Customers, so ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID); is correct.

3. Final Answer:

   ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID); -> Option C

4. Quick Check:

   Foreign key in 'many' table references 'one' table [OK]

Hint: Foreign key goes in 'many' table pointing to 'one' table [OK]

Common Mistakes:

• Placing foreign key in the 'one' table instead of 'many'
• Referencing wrong columns between tables
• Mixing table names in foreign key definition

3. Given these tables:
Customers(CustomerID, Name)
Orders(OrderID, CustomerID, Amount)
What will this query return?

SELECT Customers.Name, COUNT(Orders.OrderID) AS OrderCount FROM Customers LEFT JOIN Orders ON Customers.CustomerID = Orders.CustomerID GROUP BY Customers.Name;

medium

A. List of customers who have placed at least one order

B. List of customers with total amount spent on orders

C. List of orders with customer names repeated for each order

D. List of customers with the number of orders each placed, including customers with zero orders

Solution

1. Step 1: Understand the LEFT JOIN usage

   LEFT JOIN keeps all customers, even those without matching orders.

2. Step 2: COUNT(Orders.OrderID) counts orders per customer

   Grouping by customer name counts how many orders each customer has, zero if none.

3. Final Answer:

   List of customers with the number of orders each placed, including customers with zero orders -> Option D

4. Quick Check:

   LEFT JOIN + COUNT = all customers with order counts [OK]

Hint: LEFT JOIN + COUNT counts all, including zero matches [OK]

Common Mistakes:

• Thinking COUNT counts total amount spent
• Assuming only customers with orders appear
• Confusing JOIN types and their effects

4. You wrote this SQL to create a one-to-many relationship:

CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT, FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID));

But you get an error. What is the most likely cause?

medium

A. OrderID should not be primary key in Orders

B. Customers table does not exist or CustomerID is not a primary key

C. Foreign key should be in Customers table, not Orders

D. CustomerID column type must be VARCHAR, not INT

Solution

1. Step 1: Check foreign key reference validity

   Foreign key must reference an existing table and a primary or unique key column.

2. Step 2: Verify Customers table and CustomerID key

   If Customers table or CustomerID primary key is missing, error occurs.

3. Final Answer:

   Customers table does not exist or CustomerID is not a primary key -> Option B

4. Quick Check:

   Foreign key references must exist and be keys [OK]

Hint: Foreign key target must exist and be primary/unique key [OK]

Common Mistakes:

• Assuming foreign key can reference non-key columns
• Placing foreign key in wrong table
• Mismatching data types between foreign key and referenced key

5. You have two tables:
Authors(AuthorID, Name)
Books(BookID, Title, AuthorID)
You want to find authors who have written more than 3 books. Which query is correct?

hard

A. SELECT Name FROM Authors JOIN Books ON Authors.AuthorID = Books.AuthorID GROUP BY Name HAVING COUNT(BookID) > 3;

B. SELECT Name FROM Authors LEFT JOIN Books ON Authors.AuthorID = Books.AuthorID WHERE COUNT(BookID) > 3;

C. SELECT Name FROM Books GROUP BY AuthorID HAVING COUNT(BookID) > 3;

D. SELECT Name FROM Authors WHERE AuthorID IN (SELECT AuthorID FROM Books WHERE COUNT(BookID) > 3);

Solution

1. Step 1: Join Authors and Books on AuthorID

   We join to connect authors with their books.

2. Step 2: Group by author name and filter by book count

   Use GROUP BY Name and HAVING COUNT(BookID) > 3 to find authors with more than 3 books.

3. Final Answer:

   SELECT Name FROM Authors JOIN Books ON Authors.AuthorID = Books.AuthorID GROUP BY Name HAVING COUNT(BookID) > 3; -> Option A

4. Quick Check:

   JOIN + GROUP BY + HAVING filters authors by book count [OK]

Hint: Use GROUP BY and HAVING to filter by count in one-to-many [OK]

Common Mistakes:

• Using WHERE with aggregate functions instead of HAVING
• Missing GROUP BY clause
• Using LEFT JOIN but filtering with WHERE on aggregate