Integrity constraints in DBMS Theory - Time & Space Complexity

Time Complexity: Integrity constraints

O(n)

Understanding Time Complexity

When using integrity constraints in a database, it is important to understand how checking these rules affects performance.

We want to know how the time to verify constraints grows as the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL constraint check.

-- Check uniqueness of a column before insert
SELECT COUNT(*) FROM Employees WHERE EmployeeID = new.EmployeeID;
-- If count is 0, allow insert; else reject
    

This code checks if a new employee ID already exists to keep IDs unique.

Identify Repeating Operations

Look at what repeats when checking the constraint.

• Primary operation: Scanning the Employees table to find matching EmployeeID.
• How many times: Once per insert operation, but the scan may check many rows depending on data size.

How Execution Grows With Input

As the number of employees grows, the time to check uniqueness grows too.

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

Pattern observation: The time grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the constraint grows linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "Checking a constraint always takes the same time no matter how big the table is."

[OK] Correct: The database often needs to look through many rows to verify constraints, so more data usually means more work.

Interview Connect

Understanding how constraints affect performance helps you design databases that stay fast as they grow.

Self-Check

What if we added an index on EmployeeID? How would the time complexity change?

Practice

1. Which of the following best describes the purpose of integrity constraints in a database?

easy

A. To ensure data accuracy and consistency

B. To speed up database queries

C. To store large amounts of data

D. To create user interfaces

Solution

1. Step 1: Understand the role of integrity constraints

   Integrity constraints are rules that keep data accurate and consistent in a database.

2. Step 2: Match the purpose with the options

   Only To ensure data accuracy and consistency mentions accuracy and consistency, which matches the purpose of integrity constraints.

3. Final Answer:

   To ensure data accuracy and consistency -> Option A

4. Quick Check:

   Integrity constraints = data accuracy and consistency [OK]

Hint: Integrity constraints keep data correct and reliable [OK]

Common Mistakes:

• Confusing constraints with performance features
• Thinking constraints create user interfaces
• Assuming constraints store data

2. Which of the following is the correct syntax to declare a NOT NULL constraint on a column named email in SQL?

easy

A. email VARCHAR(50) NOT NULL

B. email VARCHAR(50) NULL

C. email VARCHAR(50) UNIQUE

D. email VARCHAR(50) PRIMARY KEY

Solution

1. Step 1: Recall the syntax for NOT NULL constraint

   The NOT NULL constraint is added after the data type to ensure the column cannot have empty values.

2. Step 2: Identify the correct option

   email VARCHAR(50) NOT NULL correctly uses email VARCHAR(50) NOT NULL. Other options either allow NULL or use different constraints.

3. Final Answer:

   email VARCHAR(50) NOT NULL -> Option A

4. Quick Check:

   NOT NULL syntax = column datatype NOT NULL [OK]

Hint: NOT NULL means column must have a value, no blanks allowed [OK]

Common Mistakes:

• Using NULL instead of NOT NULL
• Confusing UNIQUE with NOT NULL
• Using PRIMARY KEY when only NOT NULL is needed

3. Consider this SQL table definition:
<pre>CREATE TABLE Students ( ID INT PRIMARY KEY, Name VARCHAR(100) NOT NULL, Age INT CHECK (Age >= 18) );
What will happen if you try to insert (1, 'Alice', 16) into this table?

medium

A. Insertion succeeds without error

B. Insertion fails due to CHECK constraint violation

C. Insertion fails due to PRIMARY KEY violation

D. Insertion fails due to NOT NULL violation

Solution

1. Step 1: Analyze the CHECK constraint on Age

   The CHECK constraint requires Age to be 18 or older.

2. Step 2: Compare the inserted Age value

   The inserted Age is 16, which violates the CHECK constraint.

3. Final Answer:

   Insertion fails due to CHECK constraint violation -> Option B

4. Quick Check:

   Age 16 violates CHECK (Age >= 18) [OK]

Hint: CHECK constraints validate data ranges or conditions [OK]

Common Mistakes:

• Ignoring CHECK constraints and assuming insert works
• Confusing PRIMARY KEY violation with CHECK violation
• Thinking NOT NULL is violated when it is not

4. You have a table with a UNIQUE constraint on the username column. Assume the table already contains a row with username = 'john_doe'. Which of the following SQL statements will cause an error?

medium

A. INSERT INTO Users (username) VALUES ('new_user');

B. INSERT INTO Users (username) VALUES ('jane_smith');

C. INSERT INTO Users (username) VALUES ('john_doe');

D. UPDATE Users SET username = 'jane_smith' WHERE id = 1;

Solution

1. Step 1: Understand UNIQUE constraint behavior

   The UNIQUE constraint prevents duplicate values in the username column.

2. Step 2: Identify duplicate insertion

   INSERT INTO Users (username) VALUES ('john_doe'); tries to insert 'john_doe' which already exists, causing a UNIQUE violation.

3. Final Answer:

   INSERT INTO Users (username) VALUES ('john_doe'); -> Option C

4. Quick Check:

   Duplicate username violates UNIQUE constraint [OK]

Hint: UNIQUE means no duplicates allowed in that column [OK]

Common Mistakes:

• Assuming UPDATE causes error without duplicate
• Thinking inserts of new usernames cause error
• Confusing UNIQUE with PRIMARY KEY

5. A database table has two columns: OrderID and CustomerID. You want to ensure that each order belongs to an existing customer and that no two orders have the same OrderID. Which combination of integrity constraints should you use?

hard

A. NOT NULL on both columns only

B. UNIQUE on CustomerID and NOT NULL on OrderID

C. CHECK constraint on OrderID and UNIQUE on CustomerID

D. PRIMARY KEY on OrderID and FOREIGN KEY on CustomerID referencing Customers table

Solution

1. Step 1: Ensure unique OrderID

   Use PRIMARY KEY on OrderID to guarantee uniqueness and not null.

2. Step 2: Ensure Order belongs to existing Customer

   Use FOREIGN KEY on CustomerID referencing the Customers table to enforce valid customer links.

3. Final Answer:

   PRIMARY KEY on OrderID and FOREIGN KEY on CustomerID referencing Customers table -> Option D

4. Quick Check:

   Unique orders + valid customers = PRIMARY + FOREIGN KEY [OK]

Hint: Use PRIMARY KEY for unique ID, FOREIGN KEY for valid references [OK]

Common Mistakes:

• Using UNIQUE instead of PRIMARY KEY for OrderID
• Missing FOREIGN KEY for CustomerID
• Assuming NOT NULL alone enforces relationships