Relational algebra: basic operators

Relational algebra is a small set of operators that work on relations (tables) and whose result is again a relation. This is the mathematics behind SQL. The database engine first translates your SQL query into an expression like this, then optimizes it. The exam has two kinds of questions: “Write a relational algebra expression for …” and “Give the result of this expression”. For both, knowing the six fundamental operators on this page is enough.

Golden rules:

1. σ selects rows, π selects columns. Whoever mixes them up loses the easiest points.
2. Every result is a set. There are no repeated rows; π removes duplicates.
3. ∪, −, ∩ are only done between union-compatible relations.
4. × alone is almost never useful. A σ with the matching condition follows it.
5. Read the expression from the inside out. The innermost parentheses are evaluated first.

The sample database

We use the same small university database all semester. These are the tables needed most on this page.

student

course

takes (S6 has taken no course, S3 has no grade yet for CS101)

instructor and department

teaches(inst_id, course_id): (I1, CS101), (I1, CS305), (I2, CS201), (I3, EE210), (I4, MA101), (I5, MA202). I6 teaches no course, and nobody teaches BI100.

Selection: σ

Selection $\sigma_{p}(R)$ returns the rows of $R$ that satisfy the condition $p$. The columns stay as they are. The condition uses comparison operators ($=, \neq, <, \le, >, \ge$) and logical connectives ($\land$ and, $\lor$ or, $\lnot$ not).

$\sigma_{dept\_name = \text{'CS'}}(student)$

If two conditions concern the same row, they combine in a single selection: $\sigma_{dept\_name = \text{'CS'} \land tot\_cred > 20}(student)$ gives S1 (Ada) and S2 (Bora).

The order of selections does not matter: $\sigma_{p}(\sigma_{q}(R)) = \sigma_{q}(\sigma_{p}(R)) = \sigma_{p \land q}(R)$.

Projection: π

Projection $\pi_{A_1, \dots, A_k}(R)$ keeps only the listed columns. Because a relation is a set, duplicate rows are removed.

$\pi_{dept\_name}(student)$

There are 7 students but the result has 4 rows. In SQL, SELECT dept_name FROM student returns 7 rows; to get the same result as relational algebra you need to write SELECT DISTINCT. SQL uses multiset semantics, algebra uses set semantics.

PITFALL · π can reduce the number of rows. For a “How many tuples?” question, do not just count the table and move on. After a projection, count rows that look the same as one.

Composition

Since the result of every operator is a relation, operators can be nested. The names of instructors who earn more than 75000:

$\pi_{name}(\sigma_{salary > 75000}(instructor)) = \{\text{Aksoy}, \text{Demir}, \text{Kaya}\}$

The order matters: first σ, then π. If you write the opposite ($\sigma_{salary > 75000}(\pi_{name}(instructor))$), the expression is invalid, because after the projection the salary column no longer exists.

Set operations: ∪, −, ∩

All three require the two relations to be union-compatible:

• the same degree (arity), that is, the same number of columns,
• the domains of the $i$th columns are the same.

Column names do not have to be the same; the result takes the names of the left relation.

Let us work with the courses taken by S1 and S4: $A = \pi_{course\_id}(\sigma_{stu\_id = \text{'S1'}}(takes))$ = {CS101, CS201, CS305, MA101}, $B = \pi_{course\_id}(\sigma_{stu\_id = \text{'S4'}}(takes))$ = {MA101, MA202, CS305}.

Difference is not commutative: $A - B \neq B - A$. Intersection is not counted as a fundamental operator, because it can be written with difference: $A \cap B = A - (A - B)$.

“None” questions with difference. Courses that no student has taken:

$\pi_{course\_id}(course) - \pi_{course\_id}(takes) = \{\text{BI100}\}$

Departments that have both students and instructors are an intersection: $\pi_{dept\_name}(student) \cap \pi_{dept\_name}(instructor)$ = {CS, EE, MATH}. BIO has no students, and NULL has no instructors.

Cartesian product: ×

$R \times S$ puts each row of $R$ next to each row of $S$. The number of rows is $|R| \cdot |S|$, the number of columns is the sum of the degrees. Columns with the same name are told apart by the table name.

$instructor \times department$: $6 \cdot 4 = 24$ rows, $4 + 3 = 7$ columns (instructor.dept_name and department.dept_name are separate).

Most of these 24 rows are meaningless: it pairs Aksoy with the BIO building. You keep the meaningful ones with a selection:

$\pi_{name,\, building}(\sigma_{instructor.dept\_name = department.dept\_name}(instructor \times department))$

Of the 24 rows, 6 remained, each instructor with their own department. This “multiply, then select by equality” pattern is the definition of a join. Next week we will abbreviate it with ⋈.

PITFALL · forgetting the matching condition. If you do not write a σ after the product, fake rows like “every instructor in every building” get into the result. In every expression with a product, ask “which column links the tables?”

Rename: ρ

$\rho_{x}(E)$ gives the result of expression $E$ the name $x$. $\rho_{x(A_1, \dots, A_n)}(E)$ also renames the columns. Its real job: comparing a table with itself. Without giving the two copies different names, you cannot say which salary in $instructor \times instructor$ comes from which copy.

Example: the highest salary (without aggregate functions). The idea: the highest salary is a salary for which no higher salary exists.

1) ρ_i(instructor) × ρ_j(instructor)          36 rows
2) σ_{i.salary < j.salary}(...)               there is a j that earns more than i
3) π_{i.salary}(...)                           = {80000, 85000, 70000, 72000, 60000}
4) π_salary(instructor) − (3)                  = {95000}

$\pi_{salary}(instructor) - \pi_{i.salary}(\sigma_{i.salary < j.salary}(\rho_{i}(instructor) \times \rho_{j}(instructor))) = \{95000\}$

If you change the condition to $>$, the same pattern gives the lowest salary (60000).

Fundamental and derived operators

There are six fundamental operators: $\sigma, \pi, \cup, -, \times, \rho$. Every relational algebra query can be written with them. $\cap$, joins and division are derived from these six; they are only shorthand.

Query tree

An expression is drawn as a tree: leaves are tables, inner nodes are operators, the root is the result. For the instructor building query:

              π name, building
                    |
   σ instructor.dept_name = department.dept_name
                    |
                    ×
                  /   \
         instructor   department

The tree is evaluated from bottom to top. In the optimization week (week 13) we will compare different trees of the same query and see why pushing σ below the product is cheap.

Method for solving questions

For a “Write the relational algebra” question, follow this order:

1. Which tables are needed? If more than one, take the product and equate the linking columns.
2. Put the row conditions in σ.
3. Take the requested columns with π on the outside.
4. If the question has “both / every / never / only”, you need a set operation: “both” → ∩, “never” → difference.

Example: the names of students who take courses outside their own department. Three tables are needed, two matching conditions and one inequality condition:

$\pi_{s.name}(\sigma_{s.stu\_id = t.stu\_id \land t.course\_id = c.course\_id \land s.dept\_name \neq c.dept\_name}(\rho_{s}(student) \times \rho_{t}(takes) \times \rho_{c}(course)))$

The product has $7 \cdot 14 \cdot 7 = 686$ rows, and after the selection Ada, Cem and Defne remain. Because Gizem’s department is NULL, the $\neq$ comparison does not come out true and the row is dropped.

Common mistakes