Relational model mental model in SQL - Time & Space Complexity

Time Complexity: Relational model mental model

O(n)

Understanding Time Complexity

We want to understand how the time to run queries grows as the amount of data grows in a relational database.

How does the database handle more rows and tables when we ask questions?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT e.name, d.department_name
FROM employees e
JOIN departments d ON e.department_id = d.id
WHERE e.salary > 50000;
    

This query finds employees earning more than 50,000 and shows their department names by joining two tables.

Identify Repeating Operations

Look for repeated steps the database must do to answer the query.

• Primary operation: Scanning the employees table and matching each employee to a department.
• How many times: Once for each employee row, the database checks the salary and then finds the matching department.

How Execution Grows With Input

As the number of employees grows, the work grows too because each employee must be checked and matched.

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

Pattern observation: The work grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of employee rows.

Common Mistake

[X] Wrong: "Joining tables always takes the same time no matter how big the tables are."

[OK] Correct: The database must look at each row in the main table and find matching rows in the joined table, so more rows mean more work.

Interview Connect

Understanding how query time grows helps you explain how databases handle more data, a useful skill when discussing real-world data problems.

Self-Check

"What if we added an index on the department_id column? How would the time complexity change?"

Practice

1. In the relational model, what does a table represent?

easy

A. A collection of related records about a thing

B. A single piece of data

C. A programming function

D. A type of database software

Solution

1. Step 1: Understand the relational model basics

   In the relational model, data is organized into tables that represent entities or things.

2. Step 2: Identify what a table holds

   A table holds many rows, each row is a record about the thing the table represents.

3. Final Answer:

   A collection of related records about a thing -> Option A

4. Quick Check:

   Table = collection of records [OK]

Hint: Tables = things, rows = records, columns = details [OK]

Common Mistakes:

• Confusing a table with a single data value
• Thinking a table is a program or software
• Mixing up rows and columns

2. Which of the following is the correct way to describe a primary key in a table?

easy

A. A column or set of columns that uniquely identifies each row

B. A column that stores only numbers

C. A column that can have duplicate values

D. A column used to sort the table

Solution

1. Step 1: Recall the role of a primary key

   A primary key uniquely identifies each record in a table, so no two rows share the same primary key value.

2. Step 2: Check the options

   Only A column or set of columns that uniquely identifies each row describes uniqueness and identification, others describe unrelated properties.

3. Final Answer:

   A column or set of columns that uniquely identifies each row -> Option A

4. Quick Check:

   Primary key = unique identifier [OK]

Hint: Primary key means unique row ID [OK]

Common Mistakes:

• Thinking primary key allows duplicates
• Confusing primary key with sorting or data type
• Assuming primary key is always numeric

3. Given a table Employees with columns EmpID (primary key), Name, and Department, what will the following SQL query return?

SELECT Name FROM Employees WHERE Department = 'Sales';

medium

A. Only employees with no department assigned

B. All employee names regardless of department

C. All employee names who work in the Sales department

D. An error because Department is not a primary key

Solution

1. Step 1: Understand the SELECT and WHERE clauses

   The query selects the Name column from Employees where Department equals 'Sales'.

2. Step 2: Determine the output

   It returns all employee names whose Department is exactly 'Sales'. It does not return others or cause errors.

3. Final Answer:

   All employee names who work in the Sales department -> Option C

4. Quick Check:

   WHERE filters rows, SELECT chooses columns [OK]

Hint: WHERE filters rows; SELECT picks columns [OK]

Common Mistakes:

• Thinking it returns all employees ignoring WHERE
• Assuming Department must be primary key to filter
• Expecting error due to non-primary key in WHERE

4. Consider this SQL snippet:

CREATE TABLE Products (ProductID INT, Name VARCHAR(50), Price DECIMAL);
ALTER TABLE Products ADD PRIMARY KEY (ProductID);
INSERT INTO Products VALUES (1, 'Pen', 1.5), (1, 'Pencil', 0.5);

What is the problem with this code?

medium

A. Price column cannot be DECIMAL

B. It tries to insert duplicate primary key values

C. The primary key is not defined correctly

D. The table has no columns

Solution

1. Step 1: Check primary key uniqueness

   Primary key ProductID must be unique. The insert tries to add two rows with ProductID = 1.

2. Step 2: Identify the error cause

   Inserting duplicate primary keys violates uniqueness, causing an error.

3. Final Answer:

   It tries to insert duplicate primary key values -> Option B

4. Quick Check:

   Primary key must be unique [OK]

Hint: Primary keys cannot repeat values [OK]

Common Mistakes:

• Ignoring duplicate key violation
• Thinking DECIMAL is invalid for Price
• Assuming primary key syntax is wrong

5. You have two tables: Orders(OrderID, CustomerID, Amount) and Customers(CustomerID, Name). Which relational model concept explains why CustomerID appears in both tables?

hard

A. Column aliasing to rename data

B. Primary key duplication for faster queries

C. Data redundancy to store copies

D. Foreign key linking related records between tables

Solution

1. Step 1: Understand the role of CustomerID in both tables

   CustomerID uniquely identifies customers in Customers and links orders to customers in Orders.

2. Step 2: Identify relational model concept

   This linking is done by a foreign key, which references the primary key in another table to connect related data.

3. Final Answer:

   Foreign key linking related records between tables -> Option D

4. Quick Check:

   Foreign key = link between tables [OK]

Hint: Foreign key connects tables via shared column [OK]

Common Mistakes:

• Confusing foreign key with primary key duplication
• Thinking it's just data redundancy
• Mixing foreign key with column aliasing