Referential integrity enforcement in SQL - Time & Space Complexity

Time Complexity: Referential integrity enforcement

O(n)

Understanding Time Complexity

When a database checks referential integrity, it makes sure related data matches correctly.

We want to know how the time to check this grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL snippet enforcing referential integrity.

ALTER TABLE Orders
ADD CONSTRAINT fk_customer
FOREIGN KEY (CustomerID)
REFERENCES Customers(CustomerID);

-- When inserting or updating Orders, the database checks if CustomerID exists in Customers.

This code sets a foreign key so that every order must link to an existing customer.

Identify Repeating Operations

What repeats when the database enforces this rule?

• Primary operation: Checking if the CustomerID in Orders exists in Customers.
• How many times: Once for each insert or update on Orders.

How Execution Grows With Input

As the number of orders grows, the database checks more CustomerIDs.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks grows directly with the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to enforce referential integrity grows in a straight line with the number of orders.

Common Mistake

[X] Wrong: "The database checks all customers every time an order is added."

[OK] Correct: The database only checks the specific CustomerID for the new or changed order, not all customers.

Interview Connect

Understanding how referential integrity checks scale helps you explain database behavior clearly and confidently.

Self-Check

"What if the Customers table had no index on CustomerID? How would the time complexity change?"

Practice

1. What is the main purpose of referential integrity in a database?

easy

A. To speed up query execution

B. To ensure relationships between tables remain consistent

C. To store large amounts of data efficiently

D. To create backup copies of the database

Solution

1. Step 1: Understand referential integrity concept

   Referential integrity ensures that foreign keys in one table correctly reference existing rows in another table.

2. Step 2: Identify the main purpose

   This prevents orphan records and keeps data relationships consistent and safe.

3. Final Answer:

   To ensure relationships between tables remain consistent -> Option B

4. Quick Check:

   Referential integrity = consistent relationships [OK]

Hint: Referential integrity means keeping table links correct [OK]

Common Mistakes:

• Confusing referential integrity with performance optimization
• Thinking it creates backups
• Assuming it stores data efficiently

2. Which SQL statement correctly defines a foreign key with referential integrity enforcement?

easy

A. INSERT INTO Orders (OrderID, CustomerID) VALUES (1, 100);

B. CREATE TABLE Orders (OrderID INT, CustomerID INT PRIMARY KEY);

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

D. SELECT * FROM Orders WHERE CustomerID = Customers.CustomerID;

Solution

1. Step 1: Identify foreign key syntax

   The correct syntax to add a foreign key is using ALTER TABLE with ADD FOREIGN KEY referencing another table's column.

2. Step 2: Check each option

   ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID); correctly adds a foreign key constraint. CREATE TABLE Orders (OrderID INT, CustomerID INT PRIMARY KEY); wrongly sets CustomerID as primary key without foreign key. INSERT INTO Orders (OrderID, CustomerID) VALUES (1, 100); is an insert, not a constraint. SELECT * FROM Orders WHERE CustomerID = Customers.CustomerID; is a select query, not a constraint definition.

3. Final Answer:

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

4. Quick Check:

   Foreign key syntax = ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID); [OK]

Hint: Foreign keys use ALTER TABLE ADD FOREIGN KEY ... REFERENCES [OK]

Common Mistakes:

• Confusing primary key with foreign key syntax
• Using INSERT or SELECT instead of constraint definition
• Missing REFERENCES keyword

3. Given these tables:

CREATE TABLE Customers (CustomerID INT PRIMARY KEY, Name VARCHAR(50));
CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT, FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID) ON DELETE CASCADE);

What happens if a customer with CustomerID = 5 is deleted?

medium

A. All orders with CustomerID = 5 are also deleted

B. The delete fails due to foreign key constraint

C. Orders with CustomerID = 5 remain unchanged

D. CustomerID in Orders is set to NULL for those orders

Solution

1. Step 1: Understand ON DELETE CASCADE

   The ON DELETE CASCADE option means deleting a referenced row causes all related rows to be deleted automatically.

2. Step 2: Apply to the scenario

   Deleting customer with CustomerID=5 will delete all orders linked to that customer in Orders table.

3. Final Answer:

   All orders with CustomerID = 5 are also deleted -> Option A

4. Quick Check:

   ON DELETE CASCADE = delete related rows [OK]

Hint: ON DELETE CASCADE deletes related rows automatically [OK]

Common Mistakes:

• Thinking delete will fail due to constraint
• Assuming related rows remain unchanged
• Confusing CASCADE with SET NULL

4. You have this foreign key constraint:

FOREIGN KEY (ProductID) REFERENCES Products(ProductID) ON DELETE SET NULL

Which error will occur if you try to delete a product that is referenced by an order, but the ProductID column in Orders is defined as NOT NULL?

medium

A. Delete fails due to NOT NULL constraint violation

B. Delete succeeds and sets ProductID to NULL

C. Delete succeeds and removes the order row

D. Delete succeeds without affecting Orders

Solution

1. Step 1: Understand ON DELETE SET NULL behavior

   This option sets the foreign key column to NULL in referencing rows when the referenced row is deleted.

2. Step 2: Check NOT NULL constraint conflict

   If the foreign key column is NOT NULL, setting it to NULL violates the column constraint, causing the delete to fail.

3. Final Answer:

   Delete fails due to NOT NULL constraint violation -> Option A

4. Quick Check:

   SET NULL + NOT NULL column = delete fails [OK]

Hint: SET NULL fails if foreign key column is NOT NULL [OK]

Common Mistakes:

• Assuming delete succeeds and sets NULL anyway
• Thinking delete removes referencing rows
• Ignoring NOT NULL constraint on foreign key

5. You want to enforce referential integrity between Employees and Departments tables. When a department is deleted, you want all employees in that department to be reassigned to department ID 0 (which means 'Unassigned'). Which foreign key option should you use?

hard

A. FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID) ON DELETE RESTRICT

B. FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID) ON DELETE CASCADE

C. FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID) ON DELETE SET NULL

D. FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID) ON DELETE SET DEFAULT

Solution

1. Step 1: Understand ON DELETE SET DEFAULT

   This option sets the foreign key column to its default value when the referenced row is deleted.

2. Step 2: Match requirement

   Since you want employees reassigned to department ID 0, set DepartmentID column default to 0 and use ON DELETE SET DEFAULT to assign that value automatically.

3. Final Answer:

   FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID) ON DELETE SET DEFAULT -> Option D

4. Quick Check:

   Reassign on delete = ON DELETE SET DEFAULT [OK]

Hint: Use ON DELETE SET DEFAULT to assign default on delete [OK]

Common Mistakes:

• Using CASCADE deletes employees instead of reassigning
• Using SET NULL when column disallows NULL
• Using RESTRICT blocks deletion