Union, intersection, difference in DBMS Theory - Time & Space Complexity

Time Complexity: Union, intersection, difference

O(n * m)

Understanding Time Complexity

When working with sets of data in databases, operations like union, intersection, and difference combine or compare rows from tables.

We want to understand how the time to perform these operations grows as the size of the data increases.

Scenario Under Consideration

Analyze the time complexity of the following SQL queries using UNION, INTERSECT, and EXCEPT.

SELECT * FROM TableA
UNION
SELECT * FROM TableB;

SELECT * FROM TableA
INTERSECT
SELECT * FROM TableB;

SELECT * FROM TableA
EXCEPT
SELECT * FROM TableB;
    

These queries combine or compare two tables to produce a result set with unique rows.

Identify Repeating Operations

Each operation involves scanning rows and comparing them.

• Primary operation: Comparing rows from both tables to find matches or differences.
• How many times: Each row in one table is compared against rows in the other table.

How Execution Grows With Input

As the number of rows in each table grows, the number of comparisons grows roughly with the product of their sizes.

Input Size (n)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: Doubling the size of both tables roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly with the number of rows in the first table times the number in the second table.

Common Mistake

[X] Wrong: "These operations only scan one table, so time grows linearly with one table's size."

[OK] Correct: The operations compare rows between two tables, so both sizes affect the total work.

Interview Connect

Understanding how set operations scale helps you reason about database query performance and write efficient queries in real projects.

Self-Check

"What if one table is much smaller than the other? How would that affect the time complexity?"

Practice

1. Which of the following best describes the union operation in databases?

easy

A. Finds only the common records between two tables

B. Combines all unique records from two tables

C. Returns records from the first table that are not in the second

D. Deletes duplicate records from a table

Solution

1. Step 1: Understand the union operation

   The union operation combines all unique records from two sets or tables, removing duplicates.

2. Step 2: Compare with other operations

   Intersection finds common records, difference finds records in one set but not the other, and deletion removes records.

3. Final Answer:

   Combines all unique records from two tables -> Option B

4. Quick Check:

   Union = Combine unique records [OK]

Hint: Union = all unique items combined [OK]

Common Mistakes:

• Confusing union with intersection
• Thinking union includes duplicates
• Mixing difference with union

2. Which SQL keyword is used to find common records between two tables?

easy

A. UNION

B. DIFFERENCE

C. JOIN

D. INTERSECT

Solution

1. Step 1: Identify the keyword for common records

   The SQL keyword INTERSECT returns only the records common to both tables.

2. Step 2: Differentiate from other keywords

   UNION combines unique records, DIFFERENCE is not a standard SQL keyword, and JOIN combines rows based on a condition.

3. Final Answer:

   INTERSECT -> Option D

4. Quick Check:

   Common records = INTERSECT [OK]

Hint: Common records use INTERSECT keyword [OK]

Common Mistakes:

• Using UNION instead of INTERSECT
• Confusing JOIN with INTERSECT
• Assuming DIFFERENCE is a valid SQL keyword

3. Given two sets A = {1, 2, 3, 4} and B = {3, 4, 5, 6}, what is the result of A INTERSECT B?

medium

A. {3, 4}

B. {1, 2, 3, 4, 5, 6}

C. {1, 2}

D. {5, 6}

Solution

1. Step 1: Identify common elements in A and B

   The common elements between A and B are 3 and 4.

2. Step 2: Understand INTERSECT operation

   INTERSECT returns only the common elements, so the result is {3, 4}.

3. Final Answer:

   {3, 4} -> Option A

4. Quick Check:

   Intersection = common elements [OK]

Hint: Intersection = only common items [OK]

Common Mistakes:

• Listing all elements instead of common ones
• Confusing intersection with union
• Including elements only in one set

4. Consider the SQL query:
SELECT * FROM Table1
EXCEPT
SELECT * FROM Table2;
What is the purpose of the EXCEPT keyword?

medium

A. Returns records in Table1 but not in Table2

B. Returns records in Table2 but not in Table1

C. Returns records common to both tables

D. Returns all records from both tables

Solution

1. Step 1: Understand the EXCEPT keyword

   EXCEPT returns records from the first query that are not present in the second query.

2. Step 2: Apply to given tables

   So, it returns records in Table1 but not in Table2.

3. Final Answer:

   Returns records in Table1 but not in Table2 -> Option A

4. Quick Check:

   Difference = records in first not in second [OK]

Hint: EXCEPT = first table minus second table [OK]

Common Mistakes:

• Confusing EXCEPT with UNION
• Thinking EXCEPT returns common records
• Mixing order of tables in EXCEPT

5. You have two tables:
Employees_A with IDs {101, 102, 103, 104} and Employees_B with IDs {103, 104, 105, 106}.
You want to find IDs that are in either table but not in both. Which SQL operation gives this result?

hard

A. FULL OUTER JOIN with WHERE condition

B. INTERSECT

C. SYMMETRIC DIFFERENCE using UNION and EXCEPT

D. UNION

Solution

1. Step 1: Understand the requirement

   We want IDs in either table but not in both, which is called symmetric difference.

2. Step 2: Identify SQL approach

   SQL does not have a direct symmetric difference keyword, but it can be done by combining UNION and EXCEPT operations.

3. Step 3: Explain why other options are incorrect

   UNION returns all unique IDs including common ones, INTERSECT returns only common IDs, FULL OUTER JOIN with WHERE can be complex but not direct symmetric difference.

4. Final Answer:

   SYMMETRIC DIFFERENCE using UNION and EXCEPT -> Option C

5. Quick Check:

   Symmetric difference = union minus intersection [OK]

Hint: Symmetric difference = union minus intersection [OK]

Common Mistakes:

• Using UNION alone includes common IDs
• Using INTERSECT returns only common IDs
• Assuming FULL OUTER JOIN alone solves it