Cartesian product and joins in DBMS Theory - Step-by-Step Execution

Concept Flow - Cartesian product and joins

Start with Table A and Table B

↓

Perform Cartesian Product

↓

All combinations of rows from A and B

↓

Apply Join Condition?

No→Result is Cartesian Product

Yes↓

Filter rows matching join condition

↓

Output Joined Table

Start with two tables, combine every row from the first with every row from the second (Cartesian product). Then, optionally apply a condition to keep only matching pairs (join).

Execution Sample

DBMS Theory

Table A: {1, 2}
Table B: {X, Y}
Cartesian Product: All pairs (A row, B row)
Join on A=1 and B='X'

Shows how all pairs form first, then join filters pairs matching condition.

Analysis Table

Step	Action	Table A Row	Table B Row	Pair Included?	Reason
1	Combine first row of A with first row of B	1	X	Yes	All pairs included in Cartesian product
2	Combine first row of A with second row of B	1	Y	Yes	All pairs included in Cartesian product
3	Combine second row of A with first row of B	2	X	Yes	All pairs included in Cartesian product
4	Combine second row of A with second row of B	2	Y	Yes	All pairs included in Cartesian product
5	Apply join condition A=1 and B='X' to pairs	1	X	Yes	Matches join condition
6	Apply join condition A=1 and B='X' to pairs	1	Y	No	B is not 'X'
7	Apply join condition A=1 and B='X' to pairs	2	X	No	A is not 1
8	Apply join condition A=1 and B='X' to pairs	2	Y	No	A is not 1
9	Result after join	-	-	Only (1, X)	Only pairs matching condition remain

💡 All pairs formed in Cartesian product, then filtered by join condition to keep only matching pairs.

State Tracker

Variable	Start	After Step 1	After Step 4	After Step 9
Current Pair	None	(1, X)	(2, Y)	Only (1, X) included in final result
Pairs Included	0	1	4	1 after filtering by join condition

Key Insights - 3 Insights

Why does Cartesian product include all pairs even if they don't match any condition?

Cartesian product combines every row from the first table with every row from the second table without any filtering, as shown in steps 1 to 4 in the execution table.

How does a join differ from a Cartesian product?

A join applies a condition to filter the pairs from the Cartesian product, keeping only those that satisfy the condition, as seen in steps 5 to 9.

Can a join result have fewer rows than the Cartesian product?

Yes, because the join condition filters out pairs that don't match, reducing the number of rows, demonstrated by the final result in step 9.

Visual Quiz - 3 Questions

Look at the execution table, how many pairs are formed in the Cartesian product before applying the join condition?

A 2

B 4

C 1

D 0

💡 Hint

Check steps 1 to 4 in the execution table where all pairs are combined.

At which step does the join condition filter out pairs?

A Step 4

B Step 9

C Step 5

D Step 2

💡 Hint

Look at when the join condition is first applied in the execution table.

If the join condition was removed, what would be the number of pairs in the final result?

A 4

B 2

C 1

D 0

💡 Hint

Refer to the variable_tracker showing pairs included after step 4.

Concept Snapshot

Cartesian product combines every row of one table with every row of another.
Joins filter these pairs using a condition to keep only matching rows.
Without a condition, join equals Cartesian product.
Common join types: INNER JOIN, LEFT JOIN, RIGHT JOIN.
Joins reduce data by matching related rows across tables.

Full Transcript

This visual execution shows how Cartesian product and joins work in databases. First, every row from Table A is paired with every row from Table B, creating all possible combinations. This is the Cartesian product, which can be very large. Then, a join condition is applied to filter these pairs, keeping only those that satisfy the condition. For example, if the condition is A=1 and B='X', only pairs matching this remain. The execution table traces each step, showing pairs formed and which are included or excluded. The variable tracker follows how pairs accumulate and reduce after filtering. Key moments clarify why Cartesian product includes all pairs and how joins filter them. The quiz tests understanding of pair counts and filtering steps. The snapshot summarizes that Cartesian product is the base for joins, which apply conditions to relate tables meaningfully.

Practice

1. What does a Cartesian product between two tables produce?

easy

A. Only rows with matching values in both tables

B. All possible pairs of rows from both tables

C. Only rows from the first table

D. Only rows from the second table

Solution

1. Step 1: Understand Cartesian product definition

   A Cartesian product combines every row of the first table with every row of the second table.

2. Step 2: Identify the result of combining rows

   This means the total rows in the result equal the number of rows in the first table multiplied by the number of rows in the second table.

3. Final Answer:

   All possible pairs of rows from both tables -> Option B

4. Quick Check:

   Cartesian product = all pairs [OK]

Hint: Cartesian product pairs every row with every other row [OK]

Common Mistakes:

• Confusing Cartesian product with INNER JOIN
• Thinking it returns only matching rows
• Assuming it returns rows from only one table

2. Which SQL keyword is used to combine rows from two tables based on a matching condition?

easy

A. GROUP BY

B. CROSS JOIN

C. UNION

D. INNER JOIN

Solution

1. Step 1: Identify join types

   INNER JOIN combines rows from two tables where a specified condition matches.

2. Step 2: Match keyword to function

   CROSS JOIN produces Cartesian product, UNION combines result sets vertically, GROUP BY groups rows. Only INNER JOIN matches rows based on condition.

3. Final Answer:

   INNER JOIN -> Option D

4. Quick Check:

   Matching rows use INNER JOIN [OK]

Hint: INNER JOIN returns only matching rows [OK]

Common Mistakes:

• Choosing CROSS JOIN for matching rows
• Confusing UNION with JOIN
• Using GROUP BY to combine tables

3. Consider two tables:
Table A: IDs 1, 2
Table B: IDs 3, 4
What is the number of rows returned by SELECT * FROM A CROSS JOIN B;?

medium

A. 4

B. 0

C. 1

D. 2

Solution

1. Step 1: Count rows in each table

   Table A has 2 rows, Table B has 2 rows.

2. Step 2: Calculate Cartesian product size

   CROSS JOIN returns all pairs: 2 rows * 2 rows = 4 rows.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   2 * 2 = 4 rows [OK]

Hint: Multiply row counts for CROSS JOIN result size [OK]

Common Mistakes:

• Counting only rows from one table
• Confusing CROSS JOIN with INNER JOIN
• Assuming zero rows if no matching IDs

4. Identify the error in this SQL query:
SELECT * FROM Employees INNER JOIN Departments;

medium

A. SELECT * is invalid syntax

B. INNER JOIN cannot be used with two tables

C. Missing ON clause for join condition

D. Departments table does not exist

Solution

1. Step 1: Review INNER JOIN syntax

   INNER JOIN requires an ON clause to specify how tables relate.

2. Step 2: Check query for ON clause

   The query lacks ON condition, so SQL cannot match rows properly.

3. Final Answer:

   Missing ON clause for join condition -> Option C

4. Quick Check:

   INNER JOIN needs ON clause [OK]

Hint: Always include ON clause with INNER JOIN [OK]

Common Mistakes:

• Omitting ON clause in JOIN
• Thinking INNER JOIN works without condition
• Assuming SELECT * is incorrect

5. You have two tables:
Students (id, name)
Grades (student_id, score)
Which join will return all students and their scores, showing NULL if a student has no grade?

hard

A. LEFT JOIN

B. INNER JOIN

C. RIGHT JOIN

D. CROSS JOIN

Solution

1. Step 1: Understand join types and requirements

   LEFT JOIN returns all rows from the left table (Students) and matching rows from the right (Grades). If no match, NULL appears.

2. Step 2: Match requirement to join type

   We want all students even if they have no grades, so LEFT JOIN is correct.

3. Final Answer:

   LEFT JOIN -> Option A

4. Quick Check:

   All left table rows with NULL for no match = LEFT JOIN [OK]

Hint: LEFT JOIN keeps all left table rows, fills NULL if no match [OK]

Common Mistakes:

• Using INNER JOIN which excludes unmatched rows
• Choosing RIGHT JOIN which keeps right table rows
• Confusing CROSS JOIN with conditional joins