Keys (primary, candidate, foreign, super) in DBMS Theory - Time & Space Complexity

Time Complexity: Keys (primary, candidate, foreign, super)

O(n)

Understanding Time Complexity

When working with database keys, it's important to understand how the time to check or enforce these keys grows as the data grows.

We want to know how the cost of operations like searching or validating keys changes with more records.

Scenario Under Consideration

Analyze the time complexity of checking a primary key constraint during data insertion.

-- Assume a table with a primary key column
INSERT INTO Employees (EmployeeID, Name) VALUES (123, 'Alice');
-- The DBMS checks if EmployeeID 123 already exists
SELECT EmployeeID FROM Employees WHERE EmployeeID = 123;
-- If exists, reject insert; else, insert the new record
    

This snippet shows the DBMS verifying uniqueness of a primary key before inserting a new record.

Identify Repeating Operations

Look at what the DBMS does repeatedly when inserting data.

• Primary operation: Searching the existing records for the key value.
• How many times: Once per insert, but the search scans the data or index.

How Execution Grows With Input

As the number of records grows, the search to check key uniqueness takes more time.

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

Pattern observation: Without an index, the search grows linearly with the number of records.

Final Time Complexity

Time Complexity: O(n)

This means the time to check key uniqueness grows directly with the number of records in the table.

Common Mistake

[X] Wrong: "Checking a primary key is always instant no matter how big the table is."

[OK] Correct: Without an index, the database must scan records one by one, so more data means more time.

Interview Connect

Understanding how key checks scale helps you explain database performance and design better data models.

Self-Check

What if the primary key column has an index? How would the time complexity of checking uniqueness change?

Practice

1. Which key uniquely identifies each record in a database table and cannot have NULL values?

easy

A. Primary Key

B. Foreign Key

C. Candidate Key

D. Super Key

Solution

1. Step 1: Understand the role of Primary Key

   The primary key uniquely identifies each record and must not be NULL.

2. Step 2: Compare with other keys

   Foreign keys link tables, candidate keys are possible unique keys, super keys may have extra columns.

3. Final Answer:

   Primary Key -> Option A

4. Quick Check:

   Unique and not NULL = Primary Key [OK]

Hint: Primary key = unique + no NULL [OK]

Common Mistakes:

• Confusing foreign key with primary key
• Thinking candidate key is always primary
• Assuming super key must be minimal

2. Which of the following is the correct syntax to declare a primary key on column id in SQL?

easy

A. CREATE TABLE t (id INT SUPER KEY);

B. CREATE TABLE t (id INT FOREIGN KEY);

C. CREATE TABLE t (id INT CANDIDATE KEY);

D. CREATE TABLE t (id INT PRIMARY KEY);

Solution

1. Step 1: Recall SQL syntax for primary key

   Primary key is declared using PRIMARY KEY after the column definition.

2. Step 2: Check other options

   Foreign key requires reference clause, candidate and super key are not SQL keywords.

3. Final Answer:

   CREATE TABLE t (id INT PRIMARY KEY); -> Option D

4. Quick Check:

   Primary key syntax = column INT PRIMARY KEY [OK]

Hint: Primary key uses PRIMARY KEY keyword in SQL [OK]

Common Mistakes:

• Using FOREIGN KEY without REFERENCES
• Trying to declare candidate or super key directly
• Missing PRIMARY KEY keyword

3. Consider a table Orders with columns OrderID, CustomerID, and ProductID. If OrderID is the primary key and CustomerID is a foreign key referencing Customers table, what does this imply?

medium

A. OrderID uniquely identifies each order; CustomerID links to Customers table

B. CustomerID uniquely identifies each order; OrderID links to Customers table

C. ProductID is the primary key; CustomerID is a candidate key

D. OrderID and CustomerID together form a super key

Solution

1. Step 1: Understand primary key role

   OrderID uniquely identifies each order record.

2. Step 2: Understand foreign key role

   CustomerID links Orders to Customers table to maintain data consistency.

3. Final Answer:

   OrderID uniquely identifies each order; CustomerID links to Customers table -> Option A

4. Quick Check:

   Primary key = unique ID, foreign key = link [OK]

Hint: Primary key = unique; foreign key = link to another table [OK]

Common Mistakes:

• Mixing primary and foreign key roles
• Assuming foreign key is unique
• Confusing candidate key with foreign key

4. A table has columns EmpID, Email, and Phone. The EmpID is set as primary key, but duplicate emails exist. What is the problem and how to fix it?

medium

A. Phone should be primary key instead of EmpID

B. Duplicate emails violate candidate key uniqueness; add UNIQUE constraint on Email

C. Primary key allows duplicates; change EmpID to foreign key

D. No problem; duplicates in Email are allowed with primary key on EmpID

Solution

1. Step 1: Identify uniqueness requirements

   Primary key ensures EmpID is unique, but Email duplicates violate candidate key uniqueness if Email should be unique.

2. Step 2: Fix by adding UNIQUE constraint

   To prevent duplicate emails, add UNIQUE constraint on Email column.

3. Final Answer:

   Duplicate emails violate candidate key uniqueness; add UNIQUE constraint on Email -> Option B

4. Quick Check:

   Unique candidate keys need UNIQUE constraint [OK]

Hint: Add UNIQUE constraint to enforce candidate key uniqueness [OK]

Common Mistakes:

• Thinking primary key allows duplicates
• Changing primary key without reason
• Ignoring uniqueness of candidate keys

5. Given a table Students with columns StudentID, Email, and PhoneNumber, which of the following sets can be a super key?

hard

A. {StudentID, Email}

B. {Email, PhoneNumber}

C. All of the above

D. {StudentID}

Solution

1. Step 1: Define super key

   A super key is any set of columns that uniquely identifies a record, even if it has extra columns.

2. Step 2: Analyze each option

   StudentID alone uniquely identifies records; Email and PhoneNumber together can also uniquely identify; adding Email to StudentID still uniquely identifies (extra columns allowed).

3. Final Answer:

   All of the above -> Option C

4. Quick Check:

   Super key = unique set, extra columns allowed [OK]

Hint: Super key = unique columns, can include extras [OK]

Common Mistakes:

• Thinking super key must be minimal
• Confusing super key with candidate key
• Assuming single column only