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?"