Projection operation in DBMS Theory - Time & Space Complexity

Time Complexity: Projection operation

O(n)

Understanding Time Complexity

Projection operation selects specific columns from a database table.

We want to know how the time to perform projection changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT name, age FROM employees;
    

This query retrieves only the name and age columns from all rows in the employees table.

Identify Repeating Operations

Look for repeated actions in the operation.

• Primary operation: Reading each row to extract selected columns.
• How many times: Once for every row in the table.

How Execution Grows With Input

The time grows directly with the number of rows because each row is checked once.

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

Pattern observation: Doubling rows doubles the work; time grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to perform projection grows directly with the number of rows in the table.

Common Mistake

[X] Wrong: "Projection is instant because it only selects columns, so size doesn't matter."

[OK] Correct: Even though only some columns are chosen, the database still reads every row to get those columns, so time grows with the number of rows.

Interview Connect

Understanding how projection scales helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we add a WHERE clause to filter rows before projection? How would the time complexity change?"

Practice

1. What does the projection operation in a database primarily do?

easy

A. Select specific columns from a table

B. Combine rows from two tables

C. Delete rows from a table

D. Sort rows in ascending order

Solution

1. Step 1: Understand the purpose of projection

   Projection is used to choose certain columns from a table, not rows or sorting.

2. Step 2: Compare options with definition

   Only Select specific columns from a table matches the definition of projection as selecting columns.

3. Final Answer:

   Select specific columns from a table -> Option A

4. Quick Check:

   Projection = Selecting columns [OK]

Hint: Projection means picking columns only, not rows or sorting [OK]

Common Mistakes:

• Confusing projection with selection (which filters rows)
• Thinking projection changes row order
• Mixing projection with join operations

2. Which of the following is the correct SQL syntax for projection to get columns name and age from a table students?

easy

A. SELECT * FROM students WHERE name, age;

B. SELECT name age FROM students;

C. SELECT name AND age FROM students;

D. SELECT name, age FROM students;

Solution

1. Step 1: Recall correct SELECT syntax

   The correct syntax uses SELECT followed by column names separated by commas, then FROM table.

2. Step 2: Check each option

   SELECT name, age FROM students; matches the correct syntax: SELECT name, age FROM students;

3. Final Answer:

   SELECT name, age FROM students; -> Option D

4. Quick Check:

   Correct SELECT syntax = SELECT name, age FROM students; [OK]

Hint: Use commas between columns after SELECT, then FROM table [OK]

Common Mistakes:

• Using * instead of column names for projection
• Using AND instead of comma between columns
• Omitting commas between column names

3. Given a table employees with columns id, name, and salary, what will the result of SELECT name FROM employees; be?

medium

A. All rows with only the name column values

B. All rows with id and name columns

C. All rows with all columns

D. Only the first row with name column

Solution

1. Step 1: Understand the SELECT statement

   SELECT name FROM employees returns all rows but only the 'name' column values.

2. Step 2: Compare options with expected output

   All rows with only the name column values correctly describes the output as all rows with only the 'name' column.

3. Final Answer:

   All rows with only the name column values -> Option A

4. Quick Check:

   Projection selects columns, so only 'name' column shown [OK]

Hint: SELECT column returns all rows but only that column [OK]

Common Mistakes:

• Thinking it returns only one row
• Expecting multiple columns without listing them
• Confusing projection with filtering rows

4. Identify the error in this SQL query for projection: SELECT name age FROM employees;

medium

A. SELECT keyword is misspelled

B. Table name is incorrect

C. Missing comma between column names

D. No error, query is correct

Solution

1. Step 1: Analyze the column list syntax

   Column names must be separated by commas in SELECT statements.

2. Step 2: Check the given query

   The query has 'name age' without a comma, which is a syntax error.

3. Final Answer:

   Missing comma between column names -> Option C

4. Quick Check:

   Columns need commas between them [OK]

Hint: Always separate columns with commas in SELECT [OK]

Common Mistakes:

• Forgetting commas between columns
• Assuming space works as separator
• Ignoring syntax errors in column list

5. You have a table orders with columns order_id, customer_id, product, and quantity. You want to create a new table order_summary that only stores order_id and quantity. Which SQL statement correctly uses projection to do this?

hard

A. CREATE TABLE order_summary SELECT * FROM orders;

B. CREATE TABLE order_summary AS SELECT order_id, quantity FROM orders;

C. INSERT INTO order_summary SELECT customer_id, product FROM orders;

D. CREATE order_summary AS SELECT order_id, quantity FROM orders;

Solution

1. Step 1: Understand creating a new table with selected columns

   To create a new table with specific columns, use CREATE TABLE ... AS SELECT with projection.

2. Step 2: Evaluate each option

   CREATE TABLE order_summary AS SELECT order_id, quantity FROM orders; correctly creates the table with only order_id and quantity columns from orders.

3. Final Answer:

   CREATE TABLE order_summary AS SELECT order_id, quantity FROM orders; -> Option B

4. Quick Check:

   Projection + CREATE TABLE AS SELECT = CREATE TABLE order_summary AS SELECT order_id, quantity FROM orders; [OK]

Hint: Use CREATE TABLE ... AS SELECT columns for projection [OK]

Common Mistakes:

• Using SELECT * instead of specific columns
• Omitting CREATE TABLE keyword
• Selecting wrong columns for the new table