Set Theoretic Operations Quiz

Set Theoretic Operations

• Set operators include union (∪), intersection (∩), difference (-), and Cartesian product (X).
• Operate only on binary relations or sets of data.
• Union compatible sets must have the same number of attributes (degree) and matching domains across attributes.

Union (∪)

• For union compatible relations R & S, union R U S contains all unique tuples from both R and S.

Intersection (∩)

• Intersection R ∩ S comprises tuples present in both R and S.
• The order of operations does not affect the result (R ∩ S = S ∩ R).

Difference (-)

• Difference R - S includes tuples in R that are not in S.
• R - S is not equal to S - R, demonstrating that order matters.

Cartesian Product (X)

• Also known as the "cross product," it does not require union compatibility.
• Result of R(A1, A2,..., An) X S(B1, B2,...., Bm) yields Q(A1, A2,..., An, B1, B2,..., Bm).
• If R contains C tuples and S contains D tuples, the resulting set will have C*D tuples.

Relational Operations

• Designed specifically for relational databases to manipulate data beyond set operations.
• Includes select, project, join, and division operations.

Selection Operation (σ)

• Selects a subset of tuples based on a specified condition, functioning as a filter.
• Notation: σ(condition).
• The degree of the resulting relation remains constant as the original relation.
• Selection conditions can be any expression resolving to a boolean value.

Project Operation (π)

• Filters out columns from a relation rather than rows.
• Notation: π(Relation).
• Reduces data returned and eliminates redundant columns from cross products.
• The degree of the resulting relation equals the number of attributes specified in the project.

Kinds of Joins

• Theta Join: A specified join with defined conditions.
• Equijoin: Only uses "=" for comparisons and relates tuples via foreign keys; most common type of join.
• Natural Join: An equijoin with duplicate columns removed and denoted by (*); requires columns being joined to have the same name.

Size of Natural Join

• If R has n tuples and S has m tuples, the size of the natural join R ⋈ S ranges from 0 to n*m.
• Join selectivity is calculated as expected result size divided by n*m, aiding optimizers in cost estimation.

Types of Joins

• Left Outer Join: Retains all tuples from the left relation, joining with the right and filling non-matching tuples with NULLs.
• Right Outer Join: The reverse of left outer join; all tuples from the right relation are retained.
• Full Outer Join: Maintains all tuples from both relations.

Complete Set of Relational Algebra Operators

• {σ, π, ∪, -, X} constitute a complete set of operators for expressing any relational algebra operations.
• Intersection can be defined as R ∩ S ≡ (R ∪ S) - ((R - S) ∪ (S - R)).
• Join can be expressed as R ⋈ S ≡ σ(R X S).