Set Operations in Relational Algebra

Understanding the rules that govern set operations is essential for writing efficient, correct, and optimizable relational algebra expressions. These rules determine how operations can be combined, reordered, and transformed—forming the theoretical foundation for query optimization.

Just as arithmetic has rules like commutativity (a + b = b + a) and distributivity (a × (b + c) = a×b + a×c), relational algebra has its own laws that govern how operations interact. These laws enable query optimizers to transform your queries into equivalent but more efficient forms.

This page covers the complete set of rules for relational set operations: algebraic properties, operator precedence, equivalence transformations, and the optimization opportunities they enable.

The three set operations—union, intersection, and difference—exhibit distinct algebraic properties. Understanding these properties is crucial for query manipulation and optimization.

Commutativity:

An operation ⊕ is commutative if A ⊕ B = B ⊕ A for all A and B.

Associativity:

An operation ⊕ is associative if (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C).

Implications for Query Writing:

• Union chains can be freely reordered: A ∪ B ∪ C = C ∪ A ∪ B = any order
• Intersection chains can be freely reordered: A ∩ B ∩ C = B ∩ C ∩ A
• Difference chains MUST use explicit parentheses: (A − B) − C ≠ A − (B − C)
• Mixed operations follow precedence rules (covered in Section 3)

Set operations interact with each other through distributive laws and absorption laws. These rules enable complex transformations between equivalent expressions.

Distributivity:

An operation ⊗ distributes over ⊕ if: A ⊗ (B ⊕ C) = (A ⊗ B) ⊕ (A ⊗ C)

Absorption Laws:

Absorption describes how one operation can "absorb" a combined expression:

• R ∪ (R ∩ S) = R (union absorbs intersection)
• R ∩ (R ∪ S) = R (intersection absorbs union)

Proof of R ∪ (R ∩ S) = R:

1. R ∩ S ⊆ R (by definition of intersection)
2. R ⊆ R ∪ (anything) (by definition of union)
3. If A ⊆ B, then A ∪ B = B
4. Since R ∩ S ⊆ R, we have R ∪ (R ∩ S) = R ∎

When relational algebra expressions contain multiple operators without explicit parentheses, precedence rules determine the order of evaluation. Understanding precedence prevents ambiguity and ensures correct query interpretation.

Standard Precedence (Highest to Lowest):

Precedence Examples:

σ_salary>50000(Employees) ∪ Managers

Evaluates as: (σ_salary>50000(Employees)) ∪ Managers Selection binds to Employees first, then union.

R ∪ S ∩ T

Evaluates as: R ∪ (S ∩ T) Intersection has higher precedence than union.

R − S ∪ T

Evaluates as: (R − S) ∪ T Same precedence for − and ∪, so left-to-right.

π_name(R ∪ S)

Explicit parentheses: Union first, then project on result.

π_name(R) ∪ π_name(S)

Without parentheses on R and S, projection binds first.

Equivalence rules define when two relational algebra expressions produce identical results for all possible database states. These rules form the foundation of query optimization—optimizers transform queries into equivalent but more efficient forms.

Fundamental Equivalences for Set Operations:

Equivalences Involving Selection (σ):

Selection interacts with set operations in powerful ways:

-- Selection distributes over union:
σ_p(R ∪ S) ≡ σ_p(R) ∪ σ_p(S)

-- Selection distributes over intersection:
σ_p(R ∩ S) ≡ σ_p(R) ∩ σ_p(S)

-- Selection distributes over difference:
σ_p(R − S) ≡ σ_p(R) − σ_p(S)
           ≡ σ_p(R) − S  (if p applies to R's attributes)

Why these matter:

Pushing selection down (applying it earlier) often dramatically reduces the number of tuples processed by subsequent operations. This is one of the most effective optimization techniques.

Equivalences Involving Projection (π):

-- Projection distributes over union:
π_L(R ∪ S) ≡ π_L(R) ∪ π_L(S)

-- BUT NOT over intersection or difference in general!
π_L(R ∩ S) ≢ π_L(R) ∩ π_L(S)  -- May produce different results!
π_L(R − S) ≢ π_L(R) − π_L(S)  -- May produce different results!

Why projection doesn't distribute over intersection/difference:

Projection can merge previously distinct tuples. Consider:

• R = {(1, 'a'), (2, 'a')}
• S = {(1, 'a'), (3, 'a')}
• π_B(R ∩ S) = π_B({(1, 'a')}) = {('a')}
• π_B(R) ∩ π_B(S) = {('a')} ∩ {('a')} = {('a')} -- Same here, but...

With different data, results can differ when projection causes duplicates to collapse differently.

Query optimizers apply equivalence rules to transform queries into more efficient execution plans. Understanding these techniques helps you write optimizer-friendly queries and understand execution plans.

Key Optimization Strategies:

Example: Optimizing a Complex Query

Original query:

π_name(σ_dept='Engineering'(Employees ∪ Contractors))

Step 1: Push selection inside union:

π_name(σ_dept='Engineering'(Employees) ∪ σ_dept='Engineering'(Contractors))

Step 2: Push projection inside unions:

π_name(σ_dept='Engineering'(Employees)) ∪ π_name(σ_dept='Engineering'(Contractors))

Cost Analysis:

The optimized version processes 10x fewer tuples with narrower tuples—dramatic improvement!

Set operations don't exist in isolation—they interact with joins, selections, projections, and other operations. Understanding these interactions enables sophisticated query design.

Set Operations and Joins:

Warning: Be Careful with Join Distribution

Join distributing over union is valid:

(R ∪ S) ⋈ T = (R ⋈ T) ∪ (S ⋈ T)

But join does NOT fully distribute over intersection or difference! Consider this counterexample for intersection:

R = {(1, 'a')}, S = {(1, 'b')}, T = {(1, 'c')}

-- Left side: (R ∩ S) ⋈ T
R ∩ S = {} (no common tuples)
{} ⋈ T = {} 

-- Right side: (R ⋈ T) ∩ (S ⋈ T)
R ⋈ T = {(1, 'a', 'c')}
S ⋈ T = {(1, 'b', 'c')}
(R ⋈ T) ∩ (S ⋈ T) = {} (different tuples)

-- Same result here, but not in general!

Combining Set Operations in Complex Queries:

-- Find employees who have worked on all projects in Department X
-- This is a division problem, but can use set operations:

-- All (employee, project) pairs required:
Required ← π_emp_id(Employees) × π_proj_id(σ_dept='X'(Projects))

-- Actual assignments:
Actual ← π_emp_id,proj_id(Assignments)

-- Missing assignments:
Missing ← Required − Actual

-- Employees with no missing assignments (completed all):
Qualified ← π_emp_id(Employees) − π_emp_id(Missing)

This pattern uses Cartesian product to generate requirements, difference to find gaps, and another difference to find employees without gaps.

Experienced database practitioners recognize common patterns where set operations provide elegant solutions. Internalizing these patterns accelerates query design.

Pattern 1: OR Decomposition

Complex OR conditions can be decomposed into unions:

-- Instead of:
σ_{condition1 OR condition2 OR condition3}(R)

-- Consider:
σ_condition1(R) ∪ σ_condition2(R) ∪ σ_condition3(R)

Advantage: Each selection can use a different index.

Pattern 2: NOT IN as Difference

-- Find customers with no orders:
π_customer_id(Customers) − π_customer_id(Orders)

-- Equivalent to:
SELECT customer_id FROM Customers WHERE customer_id NOT IN (SELECT customer_id FROM Orders)

Pattern 3: Multi-way AND as Chained Intersection

-- Customers who bought products A, B, AND C:
π_cust_id(σ_product='A'(Purchases))
∩ π_cust_id(σ_product='B'(Purchases))
∩ π_cust_id(σ_product='C'(Purchases))

Pattern 4: Symmetric Difference for Change Detection

-- Records that changed (in old XOR new):
(OldData − NewData) ∪ (NewData − OldData)

-- Added records:
NewData − OldData

-- Deleted records:
OldData − NewData

-- Unchanged records:
OldData ∩ NewData

Pattern 5: Completeness Check via Division

-- Students who completed ALL required courses:
AllRequired ← π_student_id(Students) × π_course_id(RequiredCourses)
Completed ← π_student_id, course_id(Enrollments)
Incomplete ← AllRequired − Completed
CompleteStudents ← π_student_id(Students) − π_student_id(Incomplete)

We've comprehensively explored the rules governing set operations in relational algebra. These rules are fundamental to query correctness and optimization. Let's consolidate the essential knowledge: