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
| Group | Operations |
|---|---|
| Unary | SELECT (σ), PROJECT (π), RENAME (←) |
| From set theory | UNION (∪), INTERSECTION (∩), DIFFERENCE / MINUS (−), CARTESIAN PRODUCT (×) |
| Binary relational | JOIN (⋈), DIVISION (÷) |
| Additional | NATURAL 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 Narayan1.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:
| Form | Renames |
|---|---|
S(B1, B2, …, Bn) ← R | relation name → S and attributes → B1…Bn |
S ← R | relation name only |
R(B1, B2, …, Bn) ← R | attribute (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, S1.6 Set operations
Union (type) compatibility
Required for ∪, ∩, −. R1(A1…An) and R2(B1…Bn) are union compatible if:
- same number of attributes, and
- 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).
| Operation | Result | Notes |
|---|---|---|
UNION R ∪ S | tuples in R, or in S, or in both | duplicates eliminated; union compatible |
INTERSECTION R ∩ S | tuples in both R and S | names of R; union compatible |
DIFFERENCE R − S (MINUS / EXCEPT) | tuples in R but not in S | names 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 * nStuples. - 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 ifr[Ai] = s[Bj].- Result generally has fewer than
nR * nStuples — 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.
| Type | Keeps 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}
| Divisor | Result |
|---|---|
| Proj1 = {p2} | e1, e2, e3, e4 |
| Proj2 = {p2, p4} | e1, e4 |
| Proj3 = {p1, p2, p3, p4} | e1 |