Selection operation in DBMS Theory - Time & Space Complexity

Time Complexity: Selection operation

O(n)

Understanding Time Complexity

When we perform 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 code snippet.

SELECT * FROM Employees WHERE Department = 'Sales';

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• 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 complete the selection grows in a straight line as the table gets bigger.

Common Mistake

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

[OK] Correct: Without special indexes, the database must check each row to be sure, so time grows with table size.

Interview Connect

Understanding how selection time grows helps you explain database performance clearly and shows you know how data size affects queries.

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 operation with a WHERE clause in a database?

easy

A. To delete all rows from a table

B. To add new rows to a table

C. To change the structure of a table

D. To filter rows that meet a specific condition

Solution

1. Step 1: Understand the SELECT operation

   The SELECT operation retrieves data from a table.

2. Step 2: Role of WHERE clause

   The WHERE clause filters rows based on a condition, returning only matching rows.

3. Final Answer:

   To filter rows that meet a specific condition -> Option D

4. Quick Check:

   Selection with WHERE filters rows [OK]

Hint: WHERE clause filters rows based on condition [OK]

Common Mistakes:

• Confusing SELECT with INSERT or DELETE
• Thinking WHERE changes table structure
• Assuming SELECT without WHERE deletes data

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 * Employees WHERE Age > 30;

B. SELECT ALL FROM 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 to select all columns is SELECT * FROM table_name.

2. Step 2: Verify WHERE clause usage

   The WHERE clause must follow FROM and include a condition like Age > 30.

3. Final Answer:

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

4. Quick Check:

   Correct SELECT with WHERE syntax [OK]

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

Common Mistakes:

• Omitting FROM keyword
• Using ALL instead of *
• Placing condition outside WHERE

3. Consider the table Students with columns ID, Name, and Score. What will be the result of the query?

SELECT Name FROM Students WHERE Score >= 75;

medium

A. Names of students with scores 75 or more

B. Names of students with scores less than 75

C. All columns of students with scores 75 or more

D. Error due to missing columns

Solution

1. Step 1: Analyze SELECT clause

   The query selects only the Name column from Students.

2. Step 2: Analyze WHERE condition

   WHERE Score >= 75 filters students with scores 75 or higher.

3. Final Answer:

   Names of students with scores 75 or more -> Option A

4. Quick Check:

   WHERE filters Score >= 75, SELECT Name only [OK]

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

Common Mistakes:

• Thinking it selects all columns
• Confusing >= with >
• Assuming it returns scores too

4. Identify the error in the following SQL query:

SELECT * FROM Orders WHERE OrderDate = '2023-13-01';

medium

A. Table name Orders is incorrect

B. Invalid date format in WHERE clause

C. SELECT * is not allowed

D. Missing semicolon at end

Solution

1. Step 1: Check date format in WHERE clause

   The date '2023-13-01' has month 13, which is invalid.

2. Step 2: Verify other syntax parts

   SELECT * FROM Orders; and semicolon are correct; table name assumed valid.

3. Final Answer:

   Invalid date format in WHERE clause -> Option B

4. Quick Check:

   Date month must be 1-12 [OK]

Hint: Check date values carefully in WHERE clause [OK]

Common Mistakes:

• Ignoring invalid month number
• Thinking missing semicolon causes error
• Assuming SELECT * is wrong

5. You have a table Products with columns ProductID, Name, and Price. How would you write a query to select only products priced between 50 and 100 inclusive?

hard

A. SELECT * FROM Products WHERE Price >= 50 AND Price <= 100;

B. SELECT * FROM Products WHERE Price > 50 AND Price < 100;

C. SELECT * FROM Products WHERE Price >= 50 OR Price <= 100;

D. SELECT * FROM Products WHERE Price = 50 OR Price = 100;

Solution

1. Step 1: Understand inclusive range selection

   Inclusive means including 50 and 100, so use >= and <= operators.

2. Step 2: Construct the WHERE clause

   Use Price >= 50 AND Price <= 100 to filter the range correctly.

3. Step 3: Compare options

   The query with > 50 AND < 100 excludes boundaries; the one with = 50 OR = 100 selects only extremes; the one with >= 50 OR <= 100 selects all rows.

4. Final Answer:

   SELECT * FROM Products WHERE Price >= 50 AND Price <= 100; -> Option A

5. Quick Check:

   Inclusive range uses >= and <= [OK]

Hint: Use >= and <= for inclusive range [OK]

Common Mistakes:

• Using > and < excludes boundary values
• Using OR instead of AND for range
• Using OR with inequalities selects all rows