1.1 What it is

  • Relational algebra = the basic set of operations of the relational model; it lets a user specify queries (retrieval requests).
  • The result of every operation is a new relation, built from one or more input relations.
  • Closure property: every object in the algebra is a relation → results can be fed into further operations of the same algebra.

1.2 Groups of operations

GroupOperations
UnarySELECT (σ), PROJECT (π), RENAME (←)
From set theoryUNION (∪), INTERSECTION (∩), DIFFERENCE / MINUS (−), CARTESIAN PRODUCT (×)
Binary relationalJOIN (⋈), DIVISION (÷)
AdditionalNATURAL JOIN, OUTER JOINs (left / right / full)

1.3 SELECT — σ (filter rows)

Notation: σ <selection condition> (R)

  • Selects a subset of tuples of R that satisfy the condition.
  • The condition is a Boolean expression on R’s attributes, built from clauses of 2 formats:
    • <attribute> <comparison> <constant>
    • <attribute1> <comparison> <attribute2>
    • where <comparison> ∈ { =, <, ≤, >, ≥, ≠ }
  • Clauses combine with AND, OR, NOT.
  • Acts as a filter: tuples satisfying the condition are selected; others are discarded.

Properties

  • Result has the same schema (same attributes) as R.
  • Commutative: σc1(σc2(R)) = σc2(σc1(R))
  • Hence a cascade of selects can be applied in any order: σc1(σc2(σc3(R))) = σc2(σc3(σc1(R)))
  • A cascade can be replaced by one select with a conjunction: σc1(σc2(σc3(R))) = σ c1 AND c2 AND c3 (R)
  • |σ(R)| ≤ |R| (number of tuples).

Examples

σ DNO=4 (EMPLOYEE)                         -- employees of dept 4
σ SALARY>4200 (EMPLOYEE)
σ Lname='Smith' (EMPLOYEE)
σ SALARY>3100 AND Sex='F' (EMPLOYEE)
σ Fname=Lname (EMPLOYEE)                   -- attribute vs attribute
σ (Dno=4 AND Salary>25000) OR (Dno=5 AND Salary>30000) (EMPLOYEE)
   → Franklin Wong, Jennifer Wallace, Ramesh Narayan

1.4 PROJECT — π (keep columns)

Notation: π <attribute list> (R)

  • Result contains only the listed attributes.
  • Removes duplicate tuples (the result must be a set; mathematical sets have no duplicates).

Properties

  • |π(R)| ≤ |R|; if the list includes a key of R → |π(R)| = |R|.
  • Not commutative.
  • π list1 (π list2 (R)) = π list1 (R) provided list2 contains all attributes of list1.

Example: π Sex,Salary (EMPLOYEE) → duplicates such as (F, 25000)… collapse into one tuple, while π Lname,Fname,Salary(EMPLOYEE) keeps all 8 rows.


1.5 RENAME — ←

Three forms:

FormRenames
S(B1, B2, …, Bn) ← Rrelation name → S and attributes → B1…Bn
S ← Rrelation name only
R(B1, B2, …, Bn) ← Rattribute (column) names only
  • Useful when a query needs several successive operations (name intermediate results).
  • Necessary in some cases to avoid name conflicts.
RESULT ← π FNAME,LNAME,SALARY (EMPLOYEE)           -- attrs keep their names
RESULT(F, L, S) ← π FNAME,LNAME,SALARY (DEP5_EMPS)  -- attrs renamed F, L, S

1.6 Set operations

Union (type) compatibility

Required for ∪, ∩, −. R1(A1…An) and R2(B1…Bn) are union compatible if:

  1. same number of attributes, and
  2. corresponding attributes have the same domains: dom(Ai) = dom(Bi), i = 1…n.

By convention, the result has the attribute names of the first operand (R1).

OperationResultNotes
UNION R ∪ Stuples in R, or in S, or in bothduplicates eliminated; union compatible
INTERSECTION R ∩ Stuples in both R and Snames of R; union compatible
DIFFERENCE R − S (MINUS / EXCEPT)tuples in R but not in Snames of R; union compatible
  • ∪ and ∩ are commutative; − is not (STUDENT − INSTRUCTOR ≠ INSTRUCTOR − STUDENT).
  • Example: RESULT1(Ssn) = {123…, 333…, 666…, 453…}, RESULT2 = {333…, 888…} → union has 5 SSNs (333… only once).

Cartesian product — ×

  • R(A1…An) × S(B1…Bm) → Q(A1…An, B1…Bm) — degree n + m, attributes in that order.
  • One tuple for every combination (one tuple of R, one of S) → nR * nS tuples.
  • Operands do not need to be type compatible.

1.7 JOIN — ⋈

  • Cartesian product followed by select is very common → combined into one operation: JOIN.
  • Essential for multi‑relation databases: combines related tuples from different relations.
  • General form: R ⋈ <join condition> S
  • R ⋈ R.Ai=S.Bj S → Q(A1…An, B1…Bm), degree n + m; one tuple per combination only if r[Ai] = s[Bj].
  • Result generally has fewer than nR * nS tuples — only related tuples appear.
  • Example: DEPARTMENT ⋈ Dnumber DEPT_LOCATIONS → each department repeated once per location (Research appears 3×: Bellaire, Sugarland, Houston).

Vocabulary: a join with a general condition is a theta join; when only = is used it is an equijoin.

NATURAL JOIN — R3 = R1 ⋈ R2 (no condition written)

  • Problem: an equijoin on same‑named attributes produces two identical columns.
  • NATURAL JOIN automatically uses all attributes with identical names as the join condition and keeps only one copy of each.
  • Example: Employe(Employe, Departement) ⋈ Departement(Departement, Chef) → (Black, production, Mori), (White, production, Mori). Smith (vente) disappears — no matching department.

OUTER JOIN

Keeps tuples even if they don’t satisfy the join condition, padding missing values with NULL.

TypeKeeps all tuples of
Left outer join ⋈LEFT (⟕)left relation
Right outer join ⋈RIGHT (⟖)right relation
Full outer join ⋈FULL (⟗)both relations

Example (Employee ⋈ Dep=Code Department, Employee: Smith/sales, Black/production, White/production; Department: production/Mori, HR/Brown):

  • LEFT → Smith, sales, NULL, NULL + Black and White matched with Mori.
  • RIGHT → Black, White matched + NULL, NULL, HR, Brown.
  • FULL → all four rows (both unmatched sides kept).

1.8 DIVISION — ÷

  • R(A, B) ÷ S(B) where B ⊆ attributes of R.
  • Result: the tuples of π A (R) that appear in R combined with every tuple of S (“for all” queries).

Example: Emp(eno, pno) = {e1:p1,p2,p3,p4; e2:p1,p2; e3:p2; e4:p2,p4}

DivisorResult
Proj1 = {p2}e1, e2, e3, e4
Proj2 = {p2, p4}e1, e4
Proj3 = {p1, p2, p3, p4}e1