CARTESIAN PRODUCT (×) Operation

(Cross Product / Cross Join)

1. What is the Cartesian Product?

The CARTESIAN PRODUCT is a binary relational algebra operation denoted by:

$$R \times S$$

Unlike UNION or INTERSECTION:

• The two relations do NOT need to be union compatible

• It simply pairs every tuple of one relation with every tuple of the other

---

2. Formal Definition 

Let:

• $R(A_1,A_2,\dots ,A_n)$

• $S(B_1, B_2, \dots, B_m)$

Then:

$$R \times S = Q(A_1, A_2, \dots, A_n, B_1, B_2, \dots, B_m)$$

Properties:

• Degree of Q = $n + m$
  

• Number of tuples:

  $$|R \times S| = |R| \times |S|$$
  

👉 Each tuple in the result is formed by concatenating one tuple from R with one tuple from S.

---

3. Intuitive Understanding

Think of the Cartesian Product as:

“All possible combinations of tuples from the two relations.”

If:

• Relation R has 3 tuples

• Relation S has 4 tuples

Then:

• $R \times S$ will have 12 tuples

---

4. Why Cartesian Product Alone Is Usually Meaningless

By itself, the Cartesian Product:

• Produces large relations

• Creates combinations with no real-world meaning

📌 This is why :

“The CARTESIAN PRODUCT operation applied by itself is generally meaningless.”

It becomes meaningful only when followed by a SELECT condition that links related tuples.

---

5. Example  (EMPLOYEE and DEPENDENT)

Problem Statement:

Retrieve the names of each female employee’s dependents

Step 1: Select female employees

$$\text{FEMALE\_EMPS} \leftarrow \sigma_{Sex = 'F'}(\text{EMPLOYEE})$$

Step 2: Project required employee attributes

$$\text{EMPNAMES} \leftarrow \pi_{Fname,\; Lname,\; Ssn}(\text{FEMALE\_EMPS})$$

Step 3: Cartesian product with DEPENDENT

$$\text{EMP\_DEPENDENTS} \leftarrow \text{EMPNAMES} \times \text{DEPENDENT}$$

Step 4: Select matching employee–dependent tuples

$$\text{ACTUAL\_DEPENDENTS} \leftarrow \sigma_{Ssn = Essn}(\text{EMP\_DEPENDENTS})$$

Step 5: Final projection

$$\text{RESULT} \leftarrow \pi_{Fname,\; Lname,\; Dependent\_name}(\text{ACTUAL\_DEPENDENTS})$$

---

Single In-Line Expression (Optional Exam Form)

$$\pi_{Fname,\; Lname,\; Dependent\_name} \Big( \sigma_{Ssn = Essn} \big( \pi_{Fname,\; Lname,\; Ssn} (\sigma_{Sex='F'}(\text{EMPLOYEE})) \times \text{DEPENDENT} \big) \Big)$$

Explanation

---

Step 1: Select female employees

FEMALE_EMPS ← σSex='F'(EMPLOYEE)

✔ Keeps only tuples where Sex = 'F'

---

Step 2: Project required attributes

EMPNAMES ← πFname, Lname, Ssn(FEMALE_EMPS)

✔ Retains employee name and SSN only

---

Step 3: Apply Cartesian Product

EMP_DEPENDENTS ← EMPNAMES × DEPENDENT

🔴 Important observation:

• Every female employee is paired with every dependent

• Result includes invalid combinations

Example:

• Jennifer Wallace is paired with all dependents, even those who are not hers

This relation is syntactically correct but semantically meaningless

---

Step 4: Select only matching tuples

ACTUAL_DEPENDENTS ← σSsn = Essn(EMP_DEPENDENTS)

✔ Keeps only those tuples where:

• Employee SSN = Dependent’s Essn

This step filters out incorrect combinations

---

Step 5: Final projection

RESULT ← πFname, Lname, Dependent_name(ACTUAL_DEPENDENTS)

✔ Final meaningful result:

Jennifer Wallace → Abner

---

6. Key Teaching Insight (Very Important)

Relational algebra does not prevent meaningless results.

It is the user’s responsibility to:

• Apply correct operations

• Add appropriate conditions after Cartesian Product

---

7. Cartesian Product + Selection = JOIN

Because the pattern:

$$(R \times S) \text{ followed by } \sigma(\text{join condition})$$

is used so often, a new operation called JOIN was introduced.

📌 JOIN is simply:

A shorthand for Cartesian Product + Selection

---

8. SQL Correspondence

In SQL, Cartesian Product can be produced in two ways:

Method 1: CROSS JOIN

SELECT *
FROM EMPNAMES CROSS JOIN DEPENDENT;

Method 2: Missing join condition

SELECT *
FROM EMPNAMES, DEPENDENT;

⚠ If no WHERE clause connects the tables, SQL produces a Cartesian Product.

---

9. Summary Table (Exam-Friendly)

Aspect	Cartesian Product
Symbol	×
Type	Binary operation
Union compatibility	Not required
Result degree	Sum of degrees
Result tuples
Meaning by itself	Usually meaningless
Used with	SELECT or JOIN

---

10. Summary

The Cartesian Product combines every tuple of one relation with every tuple of another relation, and is meaningful only when followed by a selection that relates the tuples.