Relational algebra: joins, division and grouping

Last week you saw that you can write any query with six fundamental operators. But writing the $\sigma(R \times S)$ pattern every time is both long and error-prone. This week brings the shorthands: joins, outer joins, division and grouping (aggregation). Two patterns that earn the most points in the exam are here: multi-table joins and “for every” = division.

Golden rules:

1. A natural join equates all columns with the same name. Not only the one you want.
2. NULL equals no value. A row with NULL disappears in an inner join; an outer join brings it back.
3. The moment you see “every / all”, think division.
4. Grouping builds groups only from values that exist. A value that never appears does not show up with 0.

The tables are the sample database from last week: student, course, takes, instructor, department, teaches.

Theta join and equijoin

A theta join is the product and selection written with a single symbol:

$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)$

$\theta$ can be any condition ($<, \neq, \ge$ …). If the condition consists only of equalities, it is called an equijoin.

Example: pairs of instructors in the same department where one earns more than the other. Since we join the table with itself, ρ is required:

$\pi_{i.name,\, j.name}(\rho_{i}(instructor) \bowtie_{i.dept\_name = j.dept\_name \land i.salary > j.salary} \rho_{j}(instructor))$

EE and BIO have only one instructor each, so no pair appears. If you had written $\neq$ instead of $>$, each pair would come twice: (Aksoy, Demir) and (Demir, Aksoy).

Natural join: ⋈

The natural join $R \bowtie S$ does three things:

1. take $R \times S$,
2. select equality for every pair of columns with the same name,
3. keep repeated columns once.

$instructor \bowtie teaches$: the only common column is inst_id.

6 rows, 5 columns. Yildiz (I6) is not there because she has no match. If there is no common column at all, the natural join turns into a plain product.

PITFALL · a common column you did not want. When you write $student \bowtie takes \bowtie course$, student.dept_name and course.dept_name are equated too. The result is 9 records, not 14: only the courses that students took from their own department remain. Ada’s MA101, Cem’s MA101 and CS101, Defne’s CS305, and everything of Gizem’s disappear. Fix: before the join, drop the extra column with $\pi_{course\_id,\, title,\, credits}(course)$, or write an explicit theta condition.

The natural join is commutative and associative: $(R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)$. The column order may change, but the content stays the same.

Chained joins

Instructors who teach the courses of the departments in the Galata building: teaches → course (course_id) → department (dept_name).

$\pi_{inst\_id}(teaches \bowtie \pi_{course\_id,\, dept\_name}(course) \bowtie \sigma_{building = \text{'Galata'}}(department))$

Galata has CS and EE. The courses of these departments are taught by I1, I2 and I3.

Outer joins

An inner join drops rows that have no partner. Sometimes that row is exactly what you want: “instructors who teach no course should also appear in the list”. An outer join keeps the unmatched rows and fills the missing columns with NULL.

instructor ⟕ teaches (some of the columns):

teaches ⟖ course, on the other hand, brings BI100 (inst_id = NULL). A right outer join is a left outer join with the sides swapped: R ⟖ S = S ⟕ R (except for column order).

student ⟗ department (on dept_name):

Gizem is unmatched on the left (NULL department), BIO is unmatched on the right (it has no students). 6 + 1 + 1 = 8 rows.

PITFALL · SQL dialects. Standard SQL has FULL OUTER JOIN. SQLite has supported it since version 3.39; older SQLite and MySQL do not. In that case you imitate it by taking a left outer join and a UNION with the unmatched rows on the right side. The result on this page was verified both ways.

Division: ÷

Division answers the question: “Which A values are matched with every value in B?” The result of $R(A, B) \div S(B)$ is the $a$ values for which $(a, b) \in R$ holds for every $b$ in $S$.

Example: students who took all the CS courses.

$\pi_{stu\_id,\, course\_id}(takes) \div \pi_{course\_id}(\sigma_{dept\_name = \text{'CS'}}(course))$

The divisor is {CS101, CS201, CS305}. Result: S1. Bora is eliminated because he did not take CS305, and Ece because she did not take CS201 and CS305.

Deriving it from the fundamental operators

Division is not fundamental:

$R \div S = \pi_{A}(R) - \pi_{A}((\pi_{A}(R) \times S) - R)$

The idea: everyone minus “those who are missing at least one”. Step by step ($T = \pi_{stu\_id, course\_id}(takes)$, $CS$ = the CS courses):

1) π_stu_id(T)                   = {S1, S2, S3, S4, S5, S7}       candidate students
2) π_stu_id(T) × CS              = 6 · 3 = 18 rows                if everyone had taken every CS course
3) (2) − T                       = 10 rows                         the missing (student, course) pairs
     S2-CS305  S3-CS201  S3-CS305  S4-CS101  S4-CS201
     S5-CS201  S5-CS305  S7-CS101  S7-CS201  S7-CS305
4) π_stu_id(3)                   = {S2, S3, S4, S5, S7}           those with something missing
5) (1) − (4)                     = {S1}

You write the same query in SQL with a double NOT EXISTS (“a student for whom there is no CS course they did not take”). You will see it in week 7.

PITFALL · the columns of the dividend. $R$ should have only the columns $A$ and $B$. If you write $takes \div ...$ and leave grade in, $A$ becomes (stu_id, grade) and the query asks something completely different. Always narrow with $\pi$ before the division.

Assignment: ←

To break up long expressions, you define temporary relations:

cs_courses ← π_course_id(σ_{dept_name='CS'}(course))
enrol      ← π_stu_id,course_id(takes)
result     ← enrol ÷ cs_courses

Assignment adds no new power; it adds readability. Using it in complex exam questions does not cost points, and most of the time it keeps you from making mistakes.

Generalized projection

Generalized projection allows arithmetic expressions in the π list. A 10% raise for the MATH instructors:

$\pi_{name,\; salary \cdot 1.1}(\sigma_{dept\_name = \text{'MATH'}}(instructor))$

Result: Sahin 77000, Celik 79200.

Grouping and aggregate functions: 𝒢

Aggregate functions produce a single value from a set of values: count, sum, avg, min, max. The grouping symbol:

${}_{G_1, \dots, G_n}\mathcal{G}_{F_1(A_1), \dots}(E)$

The subscript on the left holds the grouping columns, and on the right are the aggregate functions. Some sources use the letter $\gamma$, with the same meaning.

Average salary and number of instructors per department:

${}_{dept\_name}\mathcal{G}_{\text{avg}(salary),\ \text{count}(inst\_id)}(instructor)$

If you write no grouping column, the whole table becomes one group: $\mathcal{G}_{\text{sum}(salary),\ \text{max}(salary)}(instructor)$ = (462000, 95000).

Rules:

• Aggregate functions skip NULL values. $\mathcal{G}_{\text{count}(dept\_name)}(student)$ = 6, while the table has 7 rows.
• For a condition on the group result (HAVING in SQL), you write σ on top of the grouping. For this, name the aggregate result with as: $\sigma_{avg\_sal > 75000}({}_{dept\_name}\mathcal{G}_{\text{avg}(salary) \text{ as } avg\_sal}(instructor))$ → CS, EE.
• No group is created for a value that does not appear in the input.

Which operator for which question

Common mistakes