Foreign key linking mental model in SQL - Time & Space Complexity

Time Complexity: Foreign key linking mental model

O(n)

Understanding Time Complexity

When we use foreign keys in databases, we link tables together. Understanding how this linking affects the time it takes to run queries helps us write better database code.

We want to know how the work grows when the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a foreign key join.

SELECT orders.order_id, customers.name
FROM orders
JOIN customers ON orders.customer_id = customers.customer_id
WHERE customers.city = 'New York';
    

This query finds all orders made by customers who live in New York by linking the orders and customers tables using a foreign key.

Identify Repeating Operations

Look at what repeats as the query runs.

• Primary operation: Scanning the orders table and looking up matching customers based on the customer_id foreign key.
• How many times: For each order, the database looks up the matching customer to check the city.

How Execution Grows With Input

As the number of orders and customers grows, the work to find matching rows grows too.

Input Size (n)	Approx. Operations
10	About 10 lookups
100	About 100 lookups
1000	About 1000 lookups

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of orders.

Common Mistake

[X] Wrong: "Joining tables with foreign keys always makes queries slow and complex."

[OK] Correct: With proper indexes, the database can quickly find matching rows, so the query time grows in a simple, predictable way.

Interview Connect

Understanding how foreign key joins scale helps you explain how databases handle linked data efficiently, a useful skill in many real-world projects.

Self-Check

"What if we added an index on customers.city? How would the time complexity change?"

Practice

1. What is the main purpose of a foreign key in a database?

easy

A. To link one table to another and ensure data consistency

B. To store large amounts of text data

C. To speed up database queries

D. To create a backup of the database

Solution

1. Step 1: Understand the role of foreign keys

   A foreign key connects one table to another by referencing a primary key in the related table.

2. Step 2: Identify the purpose of this connection

   This connection helps keep data consistent and organized by preventing invalid data entries.

3. Final Answer:

   To link one table to another and ensure data consistency -> Option A

4. Quick Check:

   Foreign key = link tables + data consistency [OK]

Hint: Foreign keys link tables to keep data correct [OK]

Common Mistakes:

• Thinking foreign keys store data themselves
• Confusing foreign keys with indexes
• Believing foreign keys speed up queries directly

2. Which of the following is the correct syntax to declare a foreign key in SQL?

easy

A. FOREIGN KEY column_name REFERENCES other_table

B. PRIMARY KEY (column_name) REFERENCES other_table(other_column)

C. FOREIGN KEY (column_name) REFERENCES other_table(other_column)

D. KEY FOREIGN (column_name) REFERENCES other_table(other_column)

Solution

1. Step 1: Recall the standard foreign key syntax

   The correct syntax includes the keywords FOREIGN KEY, the column in parentheses, then REFERENCES followed by the referenced table and column in parentheses.

2. Step 2: Compare options to syntax

   FOREIGN KEY (column_name) REFERENCES other_table(other_column) matches the correct syntax exactly. Other options have wrong keyword order or missing parentheses.

3. Final Answer:

   FOREIGN KEY (column_name) REFERENCES other_table(other_column) -> Option C

4. Quick Check:

   FOREIGN KEY + REFERENCES + (table.column) = A [OK]

Hint: FOREIGN KEY (col) REFERENCES table(col) is correct syntax [OK]

Common Mistakes:

• Omitting parentheses around column names
• Swapping PRIMARY KEY with FOREIGN KEY
• Incorrect keyword order

3. Given these tables:
CREATE TABLE Authors (AuthorID INT PRIMARY KEY, Name VARCHAR(50));
CREATE TABLE Books (BookID INT PRIMARY KEY, Title VARCHAR(100), AuthorID INT, FOREIGN KEY (AuthorID) REFERENCES Authors(AuthorID));
What happens if you try to insert INSERT INTO Books (BookID, Title, AuthorID) VALUES (1, 'My Book', 99); when there is no author with AuthorID = 99 in Authors?

medium

A. The insert succeeds but AuthorID is set to NULL

B. The insert fails due to foreign key constraint violation

C. The database creates a new author with AuthorID 99 automatically

D. The insert succeeds and adds the book

Solution

1. Step 1: Understand foreign key constraint behavior

   A foreign key requires that the referenced value exists in the parent table to maintain data integrity.

2. Step 2: Apply this to the insert statement

   Since AuthorID 99 does not exist in Authors, the insert violates the foreign key constraint and fails.

3. Final Answer:

   The insert fails due to foreign key constraint violation -> Option B

4. Quick Check:

   Foreign key requires existing parent row = D [OK]

Hint: Foreign key insert fails if parent key missing [OK]

Common Mistakes:

• Assuming automatic creation of missing parent rows
• Thinking insert will succeed with NULL foreign key
• Ignoring foreign key constraints

4. Consider this table creation:
CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT, FOREIGN KEY CustomerID REFERENCES Customers(CustomerID));
What is wrong with this statement?

medium

A. Foreign key cannot reference Customers table

B. CustomerID should be declared as PRIMARY KEY

C. PRIMARY KEY must be declared after FOREIGN KEY

D. Missing parentheses around the foreign key column name

Solution

1. Step 1: Check foreign key syntax

   The foreign key column name must be enclosed in parentheses after FOREIGN KEY.

2. Step 2: Identify the error in the statement

   The statement uses FOREIGN KEY CustomerID without parentheses, which is invalid syntax.

3. Final Answer:

   Missing parentheses around the foreign key column name -> Option D

4. Quick Check:

   FOREIGN KEY (col) needs parentheses [OK]

Hint: Always use parentheses around foreign key columns [OK]

Common Mistakes:

• Omitting parentheses in FOREIGN KEY declaration
• Misordering PRIMARY and FOREIGN KEY declarations
• Confusing foreign key with primary key requirements

5. You have two tables:
CREATE TABLE Departments (DeptID INT PRIMARY KEY, DeptName VARCHAR(50));
CREATE TABLE Employees (EmpID INT PRIMARY KEY, EmpName VARCHAR(50), DeptID INT, FOREIGN KEY (DeptID) REFERENCES Departments(DeptID) ON DELETE SET NULL);
If a department is deleted, what happens to employees linked to that department?

hard

A. Their DeptID is set to NULL automatically

B. The delete is blocked and fails

C. Employees linked to that department are deleted

D. Nothing happens; DeptID remains unchanged

Solution

1. Step 1: Understand ON DELETE SET NULL behavior

   This option means when the referenced row is deleted, the foreign key column in dependent rows is set to NULL.

2. Step 2: Apply to Employees and Departments

   Deleting a department sets DeptID to NULL in Employees who referenced it, keeping employees but removing the link.

3. Final Answer:

   Their DeptID is set to NULL automatically -> Option A

4. Quick Check:

   ON DELETE SET NULL means foreign keys become NULL [OK]

Hint: ON DELETE SET NULL clears foreign keys on delete [OK]

Common Mistakes:

• Assuming delete blocks or cascades employees
• Thinking employees get deleted automatically
• Ignoring ON DELETE action effects