Selection operation implementation in DBMS Theory - Time & Space Complexity

Time Complexity: Selection operation implementation

O(n)

Understanding Time Complexity

When we run a selection operation in a database, we want to find rows that match a condition.

We ask: How does the time to find these rows grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query execution.

SELECT *
FROM Employees
WHERE Department = 'Sales';
    

This query looks through the Employees table to find all rows where the Department is 'Sales'.

Identify Repeating Operations

In this selection operation:

• Primary operation: Checking each row's Department value.
• How many times: Once for every row in the Employees table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows one by one.

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 find matching rows grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "The database only looks at a few rows, so time stays the same no matter the table size."

[OK] Correct: Without an index, the database must check every row to be sure it finds all matches.

Interview Connect

Understanding how selection scales helps you explain database performance clearly and shows you know how queries behave with growing data.

Self-Check

"What if the Department column had an index? How would the time complexity change?"

Practice

1. What is the main purpose of the SELECT statement with a WHERE clause in a database?

easy

A. To change the structure of a table

B. To delete rows from a table

C. To add new columns to a table

D. To retrieve only rows that meet specific conditions

Solution

1. Step 1: Understand the role of SELECT

   The SELECT statement is used to get data from a table.

2. Step 2: Understand the role of WHERE clause

   The WHERE clause filters rows to include only those that meet given conditions.

3. Final Answer:

   To retrieve only rows that meet specific conditions -> Option D

4. Quick Check:

   SELECT + WHERE = filtered rows [OK]

Hint: WHERE filters rows; SELECT retrieves data [OK]

Common Mistakes:

• Confusing WHERE with DELETE
• Thinking WHERE adds columns
• Believing WHERE changes table structure

2. Which of the following is the correct syntax to select all columns from a table named Employees where the Age is greater than 30?

easy

A. SELECT * FROM Employees WHERE Age > 30;

B. SELECT * Employees WHERE Age > 30;

C. SELECT FROM Employees WHERE Age > 30;

D. SELECT * FROM Employees AGE > 30;

Solution

1. Step 1: Check SELECT syntax

   The correct syntax starts with SELECT, then columns or *, then FROM table name.

2. Step 2: Check WHERE clause syntax

   WHERE must be followed by a condition like Age > 30.

3. Final Answer:

   SELECT * FROM Employees WHERE Age > 30; -> Option A

4. Quick Check:

   Correct SELECT + FROM + WHERE syntax [OK]

Hint: SELECT * FROM table WHERE condition; [OK]

Common Mistakes:

• Omitting FROM keyword
• Placing WHERE before FROM
• Missing semicolon at end

3. Consider the table Products with columns ProductID, Name, and Price. What will be the result of this query?

SELECT Name FROM Products WHERE Price <= 50;

medium

A. All product names regardless of price

B. All product names with price less than or equal to 50

C. All product names with price greater than 50

D. An error because Price <= 50 is invalid

Solution

1. Step 1: Understand the SELECT clause

   The query selects only the Name column from the Products table.

2. Step 2: Understand the WHERE condition

   The condition Price <= 50 filters rows to those with price 50 or less.

3. Final Answer:

   All product names with price less than or equal to 50 -> Option B

4. Quick Check:

   WHERE Price <= 50 filters products [OK]

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

Common Mistakes:

• Confusing <= with >= operator
• Expecting all products without filter
• Thinking query causes error

4. Identify the error in the following SQL query:

SELECT * FROM Customers WHERE City = 'New York'

medium

A. Missing FROM keyword

B. Incorrect use of single quotes around string

C. Missing semicolon at the end

D. WHERE clause should be after ORDER BY

Solution

1. Step 1: Check SQL syntax completeness

   SQL statements should end with a semicolon to mark the end.

2. Step 2: Verify other parts

   FROM keyword is present, single quotes around string are correct, WHERE comes before ORDER BY.

3. Final Answer:

   Missing semicolon at the end -> Option C

4. Quick Check:

   SQL statements end with ; [OK]

Hint: Always end SQL statements with a semicolon [OK]

Common Mistakes:

• Forgetting semicolon
• Misplacing WHERE clause
• Using double quotes instead of single quotes

5. You have a table Orders with columns OrderID, CustomerID, and Status. You want to select all orders that are either 'Pending' or 'Processing'. Which SQL query correctly implements this selection?

hard

A. SELECT * FROM Orders WHERE Status IN ('Pending', 'Processing');

B. SELECT * FROM Orders WHERE Status = 'Pending' AND 'Processing';

C. SELECT * FROM Orders WHERE Status = 'Pending' OR 'Processing';

D. SELECT * FROM Orders WHERE Status = 'Pending', 'Processing';

Solution

1. Step 1: Understand the condition for multiple values

   To select rows where Status matches multiple values, use IN or multiple OR conditions.

2. Step 2: Compare options

   IN ('Pending', 'Processing') is correct and concise. OR requires full conditions like Status = 'Pending' OR Status = 'Processing'. A lone string after OR like 'Processing' makes the condition always true, selecting extra rows. AND between values or commas cause syntax errors.

3. Final Answer:

   SELECT * FROM Orders WHERE Status IN ('Pending', 'Processing'); -> Option A

4. Quick Check:

   Use IN for multiple values in WHERE [OK]

Hint: Use IN for multiple OR conditions in WHERE [OK]

Common Mistakes:

• Using AND instead of OR
• Incorrect syntax with commas in WHERE
• Not using quotes around string values