Time Complexity: Referential integrity enforcement
O(n)
0
0
Referential integrity enforcement in SQL - Time & Space Complexity
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?"