Lecture 03: Relational Algebra I & Fundamental Operators

1. NULL: The Value That Isn't

In relational databases, NULL does not equal zero (0) and does not equal the empty string (''). It signifies:

• Unknown value (e.g., we know an instructor has a salary, but do not know the exact number yet).
• Missing value (e.g., phone number not provided during signup).
• Inapplicable value (e.g., apartment number for a single-family house).

Three-Valued Logic (3VL)

Any standard comparison with NULL (such as salary > 50000 or salary = NULL) evaluates to UNKNOWN rather than TRUE or FALSE.

Rule: To check for nullability, always use IS NULL or IS NOT NULL.

2. What is Relational Algebra?

Relational Algebra is a formal procedural query language consisting of a set of mathematical operations that take one or two relations as input and produce a new relation as output.

The Closure Property

Because every relational algebra operator takes relations as input and outputs a relation, operators can be nested and composed arbitrarily into query trees:

π_name(σ_(salary > 80000)(instructor))

3. The Six Fundamental Operators

All relational queries can theoretically be expressed using these 6 fundamental operators:

1. Selection (σ_p)

Selects tuples that satisfy a given predicate p:

σ_p(r) = { t ∈ r | p(t) is true }

• Input: Relation r, Predicate p using comparison operators (=, !=, <, <=, >, >=, AND, OR, NOT).
• Example: Find all instructors in the 'Physics' department earning more than 75,000:

σ_(dept_name = 'Physics' AND salary > 75000)(instructor)

2. Projection (π_(A1, A2, ..., Ak))

Extracts specified attributes and eliminates duplicate tuples (since the output is a mathematical set):

π_(A1, ..., Ak)(r)

• Example: List all department names from the instructor table:

π_dept_name(instructor)

(Note: Any duplicate department rows are automatically collapsed).

3. Rename (ρ)

Assigns a new name to a relation or its attributes to resolve naming conflicts:

ρ_S(r)   or   ρ_S(B1, B2, ..., Bn)(r)

• Example: Rename relation instructor to faculty:

ρ_faculty(instructor)

4. Union (∪)

Combines all tuples from two relations into a single set:

r ∪ s = { t | t ∈ r OR t ∈ s }

• Prerequisite (Union Compatibility):
  1. Relations r and s must have the exact same arity (same number of attributes).
  2. The domains of corresponding attributes must be compatible from left to right.
• Example: All courses taught in Fall 2025 or Spring 2026:

π_course_id(σ_(sem='Fall' AND year=2025)(section)) ∪ π_course_id(σ_(sem='Spring' AND year=2026)(section))

5. Set Difference (−)

Finds tuples that are present in relation r but not in relation s:

r - s = { t | t ∈ r AND t ∉ s }

• Prerequisite: Relations r and s must be union-compatible.
• Example: Courses taught in Fall 2025 but NOT taught in Spring 2026:

π_course_id(σ_(sem='Fall' AND year=2025)(section)) - π_course_id(σ_(sem='Spring' AND year=2026)(section))

6. Cartesian Product (×)

Pairs every tuple of relation r with every tuple of relation s:

r × s = { t ∘ q | t ∈ r AND q ∈ s }

• If r has n1 tuples and k1 attributes, and s has n2 tuples and k2 attributes:
  • Output has n1 * n2 tuples.
  • Output has k1 + k2 attributes.

4. Derived Operator: Set Intersection (∩)

Set intersection returns tuples that belong to both relations:

r ∩ s = { t | t ∈ r AND t ∈ s }

Intersection can be rewritten using set difference:

r ∩ s = r - (r - s)

5. Review Exercises & Conceptual Questions

π_name(σ_(tot_cred > 100)(student))