Relational database concepts in MySQL - Time & Space Complexity

Time Complexity: Relational database concepts

O(n)

Understanding Time Complexity

When working with relational databases, it is important to understand how the time to run queries grows as the data grows.

We want to know how the number of operations changes when the database tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE department_id = 5;
    

This query selects all employees who belong to department number 5 from the employees table.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Checking each row in the employees table to see if the department_id matches 5.
• How many times: Once for every row in the employees table.

How Execution Grows With Input

As the number of employees grows, the query has to check more rows.

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 rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line with the number of rows in the table.

Common Mistake

[X] Wrong: "The query time stays the same no matter how many rows there are."

[OK] Correct: The database must check each row to find matches, so more rows mean more work.

Interview Connect

Understanding how query time grows helps you write better database queries and explain your thinking clearly in interviews.

Self-Check

"What if the employees table had an index on department_id? How would the time complexity change?"

Practice

1. What is the main purpose of a primary key in a relational database table?

easy

A. To speed up database backups

B. To store large text data

C. To link two tables together

D. To uniquely identify each record in the table

Solution

1. Step 1: Understand the role of primary keys

   A primary key is a column or set of columns that uniquely identifies each row in a table.

2. Step 2: Compare options with the definition

   Only To uniquely identify each record in the table describes this unique identification role correctly.

3. Final Answer:

   To uniquely identify each record in the table -> Option D

4. Quick Check:

   Primary key = unique record ID [OK]

Hint: Primary key means unique ID for each row [OK]

Common Mistakes:

• Confusing primary key with foreign key
• Thinking primary key stores large data
• Assuming primary key speeds backups

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

easy

A. PRIMARY KEY (id);

B. KEY PRIMARY id;

C. PRIMARY KEY id;

D. PRIMARY id KEY;

Solution

1. Step 1: Recall MySQL primary key syntax

   In MySQL, the primary key is declared using PRIMARY KEY (column_name).

2. Step 2: Match syntax with options

   PRIMARY KEY (id); matches the correct syntax with parentheses around the column name.

3. Final Answer:

   PRIMARY KEY (id); -> Option A

4. Quick Check:

   Primary key syntax uses parentheses [OK]

Hint: Primary key syntax uses parentheses around column [OK]

Common Mistakes:

• Omitting parentheses around column name
• Swapping order of keywords
• Using incorrect keywords like KEY PRIMARY

3. Given two tables: Customers(id, name) and Orders(order_id, customer_id), which SQL query correctly retrieves all orders with the customer names?

medium

A. SELECT Orders.order_id, Customers.name FROM Orders JOIN Customers ON Orders.id = Customers.customer_id;

B. SELECT Orders.order_id, Customers.name FROM Orders JOIN Customers ON Orders.customer_id = Customers.id;

C. SELECT order_id, name FROM Orders, Customers WHERE Orders.id = Customers.id;

D. SELECT order_id, name FROM Orders LEFT JOIN Customers ON Orders.customer_id = Customers.order_id;

Solution

1. Step 1: Identify the correct join condition

   The foreign key customer_id in Orders links to id in Customers.

2. Step 2: Check each option's join condition

   SELECT Orders.order_id, Customers.name FROM Orders JOIN Customers ON Orders.customer_id = Customers.id; correctly joins on Orders.customer_id = Customers.id. Others use wrong columns or join types.

3. Final Answer:

   SELECT Orders.order_id, Customers.name FROM Orders JOIN Customers ON Orders.customer_id = Customers.id; -> Option B

4. Quick Check:

   Join on foreign key = primary key [OK]

Hint: Join tables on foreign key = primary key [OK]

Common Mistakes:

• Swapping join columns incorrectly
• Using WHERE instead of JOIN condition properly
• Mixing up LEFT JOIN with INNER JOIN

4. You wrote this SQL to create a foreign key: FOREIGN KEY (customer_id) REFERENCES Customers(customer_id). But it gives an error. What is the likely cause?

medium

A. You must declare foreign keys before primary keys

B. Foreign keys cannot reference columns in the same table

C. The referenced column customer_id does not exist or is not a primary key in Customers

D. Foreign keys must reference columns named 'id' only

Solution

1. Step 1: Understand foreign key requirements

   A foreign key must reference a column that exists and is a primary or unique key in the referenced table.

2. Step 2: Analyze the error cause

   If Customers has no customer_id column or it is not a key, the foreign key declaration fails.

3. Final Answer:

   The referenced column customer_id does not exist or is not a primary key in Customers -> Option C

4. Quick Check:

   Foreign key must reference existing primary key [OK]

Hint: Foreign key must reference existing primary key column [OK]

Common Mistakes:

• Referencing non-existent columns
• Assuming foreign keys must reference 'id' column
• Incorrect order of key declarations

5. You have two tables: Employees(emp_id, name) and Departments(dept_id, dept_name, manager_id). The manager_id in Departments references emp_id in Employees. Which of these statements is TRUE about this relationship?

hard

A. An employee can manage multiple departments, but a department can have only one manager

B. Each department must have exactly one manager who is an employee

C. A department can have multiple managers if multiple employees share the same emp_id

D. The manager_id column in Departments can be NULL only if emp_id is NULL in Employees

Solution

1. Step 1: Understand foreign key relationship

   The manager_id in Departments points to emp_id in Employees, linking each department to one employee as manager.

2. Step 2: Analyze relationship cardinality

   One department has one manager, but an employee can manage many departments (one-to-many).

3. Step 3: Evaluate options

   An employee can manage multiple departments, but a department can have only one manager correctly states this one-to-many relationship. Each department must have exactly one manager who is an employee is wrong because departments can have one manager, but not necessarily exactly one if NULL allowed. A department can have multiple managers if multiple employees share the same emp_id is wrong because emp_id is unique. The manager_id column in Departments can be NULL only if emp_id is NULL in Employees is incorrect because NULL in manager_id is independent of emp_id NULL.

4. Final Answer:

   An employee can manage multiple departments, but a department can have only one manager -> Option A

5. Quick Check:

   One-to-many foreign key = An employee can manage multiple departments, but a department can have only one manager [OK]

Hint: Foreign key one-to-many means one employee, many departments [OK]

Common Mistakes:

• Assuming multiple managers per department
• Confusing NULL constraints
• Thinking emp_id can be duplicated