Introduction

The Cartesian Product, also known as the Cross Product, is a fundamental binary operation in relational algebra. It combines two relations (tables) to produce a new relation containing all possible combinations of tuples from both relations.

Syntax

R × S

Here, R and S are two relations. The result is a relation containing every combination of tuples from R and S.

Key Properties

• Number of Tuples: If R has M tuples and S has N tuples, the resulting relation will have M × N tuples.
• Number of Attributes: The resulting relation will have attributes equal to the sum of attributes in R and S.
• Commutativity: Cartesian product is not commutative (order matters).
• Associativity: Cartesian product is associative.

Example: Basic Cartesian Product

Relation R (a, b, c):
a | b | c
1 | A | X
2 | B | Y
3 | C | Z

Relation S (d, e):
d  | e
10 | P
20 | Q

Result of R × S:
a | b | c | d  | e
1 | A | X | 10 | P
1 | A | X | 20 | Q
2 | B | Y | 10 | P
2 | B | Y | 20 | Q
3 | C | Z | 10 | P
3 | C | Z | 20 | Q
            

Use Cases of Cartesian Product

The Cartesian Product is often used with selection to derive meaningful results:

Example: Combining Employee and Dependent Tables

Employee(emp_id, emp_name):
emp_id | emp_name
101    | Alice
102    | Bob

Dependent(emp_id, dep_name):
emp_id | dep_name
101    | Charlie
102    | Dave
102    | Eve

Step 1: Perform the Cartesian Product:
emp_id | emp_name | emp_id | dep_name
101    | Alice    | 101    | Charlie
101    | Alice    | 102    | Dave
101    | Alice    | 102    | Eve
102    | Bob      | 101    | Charlie
102    | Bob      | 102    | Dave
102    | Bob      | 102    | Eve

Step 2: Apply Selection:
σ(Employee.emp_id = Dependent.emp_id)(Employee × Dependent)

Result:
emp_id | emp_name | dep_name
101    | Alice    | Charlie
102    | Bob      | Dave
102    | Bob      | Eve
            

Cartesian Product and Joins

The Cartesian Product often serves as the foundation for advanced join operations:

• Natural Join: Combines tuples with matching attributes, effectively a Cartesian Product followed by selection.
• Theta Join: Extends the Natural Join by allowing custom conditions.

Conclusion

• Cartesian Product generates all possible combinations of tuples.
• It is a powerful operation that forms the basis for join operations in databases.
• Used meaningfully with selection, it can combine related data from different tables.