FOREIGN KEY constraint in SQL - Time & Space Complexity

Time Complexity: FOREIGN KEY constraint

O(log n)

Understanding Time Complexity

When we use a FOREIGN KEY constraint, the database checks that related data exists. This checking takes time.

We want to understand how this checking time grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of inserting a row with a FOREIGN KEY constraint.

INSERT INTO Orders (OrderID, CustomerID, OrderDate)
VALUES (101, 5, '2024-06-01');

-- CustomerID is a FOREIGN KEY referencing Customers(CustomerID)
    

This code inserts a new order and checks if the CustomerID exists in the Customers table.

Identify Repeating Operations

When inserting, the database must check the FOREIGN KEY value exists.

• Primary operation: Searching the referenced table for the matching key.
• How many times: Once per insert, but the search depends on the size of the referenced table.

How Execution Grows With Input

The search to verify the key usually uses an index, making it fast even if the table grows.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find the key
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, not directly with the number of rows.

Final Time Complexity

Time Complexity: O(log n)

This means the check gets a little slower as the referenced table grows, but it stays efficient.

Common Mistake

[X] Wrong: "Checking a FOREIGN KEY is as slow as scanning the whole referenced table every time."

[OK] Correct: Databases use indexes to find keys quickly, so they don't scan the whole table.

Interview Connect

Understanding how FOREIGN KEY checks scale shows you know how databases keep data correct without slowing down too much.

Self-Check

"What if the referenced column does not have an index? How would the time complexity change?"

Practice

1. What is the main purpose of a FOREIGN KEY constraint in a database?

easy

A. To store large amounts of text data efficiently

B. To speed up database queries by creating indexes

C. To link two tables by ensuring values in one table match values in another

D. To automatically backup the database

Solution

1. Step 1: Understand the role of FOREIGN KEY

   A FOREIGN KEY connects columns in two tables to keep data related and consistent.

2. Step 2: Compare options with this role

   Only To link two tables by ensuring values in one table match values in another describes linking tables by matching values, which is the purpose of FOREIGN KEY.

3. Final Answer:

   To link two tables by ensuring values in one table match values in another -> Option C

4. Quick Check:

   FOREIGN KEY links tables = A [OK]

Hint: FOREIGN KEY links tables by matching columns [OK]

Common Mistakes:

• Confusing FOREIGN KEY with indexing
• Thinking FOREIGN KEY stores data
• Assuming FOREIGN KEY backs up data

2. Which of the following is the correct syntax to add a FOREIGN KEY constraint to an existing table Orders referencing Customers(CustomerID)?

easy

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

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

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

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

Solution

1. Step 1: Recall correct ALTER TABLE syntax for FOREIGN KEY

   The correct syntax uses: ALTER TABLE table_name ADD FOREIGN KEY (column) REFERENCES other_table(column);

2. Step 2: Check each option

   ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID); matches the correct syntax exactly. Options A, B, and C have syntax errors or wrong keywords.

3. Final Answer:

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

4. Quick Check:

   Correct ALTER TABLE FOREIGN KEY syntax = D [OK]

Hint: Use ADD FOREIGN KEY (col) REFERENCES table(col) syntax [OK]

Common Mistakes:

• Using PRIMARY KEY instead of FOREIGN KEY
• Omitting parentheses around column name
• Using TO instead of 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));
What happens if you try to insert INSERT INTO Orders (OrderID, CustomerID) VALUES (1, 999); when there is no customer with CustomerID = 999?

medium

A. The insert fails due to FOREIGN KEY constraint violation

B. The insert succeeds but CustomerID is set to NULL

C. The insert succeeds and adds the order with CustomerID 999

D. The insert succeeds but triggers a warning

Solution

1. Step 1: Understand FOREIGN KEY enforcement

   FOREIGN KEY requires the referenced value to exist in the parent table before inserting.

2. Step 2: Apply to the insert statement

   Since CustomerID 999 does not exist in Customers, the insert violates the FOREIGN KEY rule and fails.

3. Final Answer:

   The insert fails due to FOREIGN KEY constraint violation -> Option A

4. Quick Check:

   Insert with missing parent key = fails [OK]

Hint: Insert fails if referenced key doesn't exist [OK]

Common Mistakes:

• Assuming insert sets foreign key to NULL automatically
• Thinking insert triggers only warnings, not errors
• Believing insert succeeds without parent key

4. You have 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. PRIMARY KEY cannot be used with FOREIGN KEY in the same table

B. CustomerID must be declared as PRIMARY KEY

C. REFERENCES keyword is not allowed in FOREIGN KEY constraints

D. FOREIGN KEY must be declared with parentheses around the column name

Solution

1. Step 1: Check FOREIGN KEY syntax

   FOREIGN KEY columns must be enclosed in parentheses, like FOREIGN KEY (CustomerID).

2. Step 2: Identify the error in the statement

   The statement misses parentheses around CustomerID in FOREIGN KEY declaration, causing syntax error.

3. Final Answer:

   FOREIGN KEY must be declared with parentheses around the column name -> Option D

4. Quick Check:

   FOREIGN KEY columns need parentheses [OK]

Hint: Always use parentheses around FOREIGN KEY columns [OK]

Common Mistakes:

• Omitting parentheses around foreign key columns
• Thinking PRIMARY KEY conflicts with FOREIGN KEY
• Misunderstanding REFERENCES usage

5. You want to delete a customer from Customers table who has orders in Orders table. The Orders table has a FOREIGN KEY on CustomerID referencing Customers(CustomerID) with ON DELETE CASCADE. What will happen when you delete that customer?

hard

A. The delete fails because orders exist for that customer

B. The customer is deleted and all their orders are automatically deleted

C. The customer is deleted but orders remain with invalid CustomerID

D. The delete succeeds but sets CustomerID in orders to NULL

Solution

1. Step 1: Understand ON DELETE CASCADE effect

   ON DELETE CASCADE means deleting a parent row also deletes all related child rows automatically.

2. Step 2: Apply to deleting a customer with orders

   Deleting the customer will also delete all orders linked by CustomerID in Orders table.

3. Final Answer:

   The customer is deleted and all their orders are automatically deleted -> Option B

4. Quick Check:

   ON DELETE CASCADE deletes related rows [OK]

Hint: ON DELETE CASCADE removes child rows with parent [OK]

Common Mistakes:

• Assuming delete fails due to existing child rows
• Thinking child rows remain with broken references
• Confusing CASCADE with SET NULL behavior