Foreign key ON DELETE behavior in SQL - Time & Space Complexity

Time Complexity: Foreign key ON DELETE behavior

O(n)

Understanding Time Complexity

When a row is deleted in a table with foreign keys, the database must handle related rows in other tables.

We want to understand how the work grows when deleting rows with different ON DELETE rules.

Scenario Under Consideration

Analyze the time complexity of deleting a row with foreign key constraints.

-- Parent table
CREATE TABLE departments (
  id INT PRIMARY KEY,
  name VARCHAR(50)
);

-- Child table with foreign key
CREATE TABLE employees (
  id INT PRIMARY KEY,
  name VARCHAR(50),
  dept_id INT,
  FOREIGN KEY (dept_id) REFERENCES departments(id) ON DELETE CASCADE
);

-- Deleting a department row
DELETE FROM departments WHERE id = 10;
    

This code deletes a department and triggers actions on employees linked by foreign key with ON DELETE CASCADE.

Identify Repeating Operations

Look at what the database does when deleting a row with ON DELETE CASCADE.

• Primary operation: The database searches the child table for all rows referencing the deleted parent row.
• How many times: It checks each child row that matches the foreign key condition, potentially many rows.

How Execution Grows With Input

As the number of child rows linked to the parent grows, the work to delete grows too.

Input Size (n)	Approx. Operations
10 child rows	10 checks and deletes
100 child rows	100 checks and deletes
1000 child rows	1000 checks and deletes

Pattern observation: The work grows roughly in direct proportion to the number of child rows linked to the deleted parent.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete grows linearly with the number of related child rows that must be handled.

Common Mistake

[X] Wrong: "Deleting a parent row is always a quick, single-step operation regardless of child rows."

[OK] Correct: The database must find and process all child rows affected by the foreign key rule, which takes more time as child rows increase.

Interview Connect

Understanding how foreign key deletions scale helps you explain database behavior clearly and shows you know how data relationships affect performance.

Self-Check

"What if the foreign key used ON DELETE SET NULL instead of CASCADE? How would the time complexity change?"

Practice

1. What does the ON DELETE CASCADE option do in a foreign key constraint?

easy

A. Deletes all related child rows automatically when the parent row is deleted.

B. Prevents deletion of the parent row if related child rows exist.

C. Sets the foreign key in child rows to NULL when the parent row is deleted.

D. Does nothing to child rows when the parent row is deleted.

Solution

1. Step 1: Understand ON DELETE CASCADE behavior

   This option means that when a parent row is deleted, all child rows linked by the foreign key are also deleted automatically.

2. Step 2: Compare with other options

   Other options like RESTRICT block deletion, and SET NULL clears the foreign key, so only CASCADE deletes child rows.

3. Final Answer:

   Deletes all related child rows automatically when the parent row is deleted. -> Option A

4. Quick Check:

   ON DELETE CASCADE = delete related rows [OK]

Hint: CASCADE means delete children when parent is deleted [OK]

Common Mistakes:

• Confusing CASCADE with RESTRICT
• Thinking CASCADE sets foreign keys to NULL
• Assuming CASCADE does nothing

2. Which of the following is the correct syntax to add a foreign key with ON DELETE SET NULL in SQL?

easy

A. FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE CASCADE

B. FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE SET NULL

C. FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE RESTRICT

D. FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE NO ACTION

Solution

1. Step 1: Identify the syntax for ON DELETE SET NULL

   The correct syntax includes the phrase ON DELETE SET NULL after the foreign key reference.

2. Step 2: Match options with syntax

   FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE SET NULL exactly matches the required syntax for setting foreign keys to NULL on parent deletion.

3. Final Answer:

   FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE SET NULL -> Option B

4. Quick Check:

   ON DELETE SET NULL syntax = FOREIGN KEY (child_id) REFERENCES parent(id) ON DELETE SET NULL [OK]

Hint: Look for 'ON DELETE SET NULL' phrase exactly [OK]

Common Mistakes:

• Choosing CASCADE instead of SET NULL
• Confusing RESTRICT and NO ACTION
• Missing ON DELETE clause

3. Given these tables:

CREATE TABLE parent (id INT PRIMARY KEY);
CREATE TABLE child (id INT PRIMARY KEY, parent_id INT, FOREIGN KEY (parent_id) REFERENCES parent(id) ON DELETE RESTRICT);
INSERT INTO parent VALUES (1);
INSERT INTO child VALUES (10, 1);

What happens if you run DELETE FROM parent WHERE id = 1;?

medium

A. The parent row is deleted, and the child row is also deleted.

B. The parent row is deleted, but the child row's parent_id is set to NULL.

C. The delete succeeds and leaves the child row with a dangling parent_id.

D. The delete fails because the child row exists and ON DELETE RESTRICT blocks it.

Solution

1. Step 1: Understand ON DELETE RESTRICT effect

   RESTRICT prevents deleting a parent row if any child rows reference it.

2. Step 2: Apply to given data

   Since child row with parent_id=1 exists, deleting parent id=1 is blocked.

3. Final Answer:

   The delete fails because the child row exists and ON DELETE RESTRICT blocks it. -> Option D

4. Quick Check:

   ON DELETE RESTRICT blocks delete if children exist [OK]

Hint: RESTRICT blocks delete if child rows exist [OK]

Common Mistakes:

• Assuming CASCADE behavior with RESTRICT
• Thinking child foreign key becomes NULL
• Believing delete always succeeds

4. You wrote this SQL:

ALTER TABLE child ADD CONSTRAINT fk_parent FOREIGN KEY (parent_id) REFERENCES parent(id) ON DELETE SET NULL;

But when you delete a parent row, the child row's parent_id does not become NULL. What is the likely problem?

medium

A. The foreign key syntax is incorrect and ignored by the database.

B. ON DELETE SET NULL only works with CASCADE.

C. The parent_id column is NOT NULL, so it cannot be set to NULL.

D. You must delete child rows manually before deleting parent.

Solution

1. Step 1: Check column nullability

   ON DELETE SET NULL requires the foreign key column to allow NULL values.

2. Step 2: Identify the cause

   If parent_id is NOT NULL, the database cannot set it to NULL, so it leaves it unchanged.

3. Final Answer:

   The parent_id column is NOT NULL, so it cannot be set to NULL. -> Option C

4. Quick Check:

   SET NULL needs nullable foreign key column [OK]

Hint: Foreign key must allow NULL for SET NULL to work [OK]

Common Mistakes:

• Assuming syntax error causes issue
• Thinking SET NULL requires CASCADE
• Believing manual delete is always needed

5. You have two tables:

CREATE TABLE orders (order_id INT PRIMARY KEY);
CREATE TABLE order_items (item_id INT PRIMARY KEY, order_id INT, FOREIGN KEY (order_id) REFERENCES orders(order_id) ON DELETE CASCADE);

You want to delete an order and all its items safely. However, sometimes order_items.order_id can be NULL for items not linked to any order. What is the best ON DELETE behavior to use for the foreign key to avoid errors and keep data consistent?

hard

A. ON DELETE CASCADE, because it deletes all linked items automatically.

B. ON DELETE NO ACTION, to do nothing on delete.

C. ON DELETE RESTRICT, to prevent deleting orders with linked items.

D. ON DELETE SET NULL, so deleting an order sets linked items' order_id to NULL.

Solution

1. Step 1: Identify the goal

   You want to delete an order and automatically delete all its related items safely.

2. Step 2: Evaluate ON DELETE CASCADE

   CASCADE deletes all child rows (order_items) where order_id matches the deleted order, achieving the goal automatically.

3. Step 3: Handle NULL values

   Items with NULL order_id are not referencing any order, so CASCADE leaves them untouched, maintaining consistency without errors.

4. Final Answer:

   ON DELETE CASCADE, because it deletes all linked items automatically. -> Option A

5. Quick Check:

   Delete order + linked items safely = ON DELETE CASCADE [OK]

Hint: CASCADE deletes linked items automatically, ignores NULLs [OK]

Common Mistakes:

• Choosing SET NULL, which orphans items instead of deleting
• Using RESTRICT, blocking necessary deletes
• Picking NO ACTION, requiring manual item deletes