Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 79 ยท Relational Algebra and Calculus

Selection, Projection and Renaming

Learn the unary operators of relational algebra: selection (sigma), projection (pi) and rename (rho), how they compose, and the SQL each one corresponds to.

SQL tells a database what you want. Underneath, every query is turned into relational algebra, a small mathematical language whose operators take relations in and produce relations out. The optimizer rewrites algebra expressions to find cheaper plans (Algebraic Equivalence and Heuristic Optimization), and textbooks use the same notation to define exactly what a query means. If you can read algebra, you can predict what SQL will do.

Because every operator returns a relation, operators can be composed: the output of one becomes the input of the next. This lesson covers the three one-input (unary) operators: selection (pick rows), projection (pick columns) and rename (change names). The examples use the school dataset, where courses(id, code, title, teacher_id, credits, capacity) lists the courses.

The three unary operators

Rows, columns, names

Selection Keeps the rows that satisfy a condition.
Projection Keeps only the listed columns.
Rename Gives a relation or its attributes new names.

Each one takes a relation and returns a relation.

1 / 2

Selection: sigma

Selection written ฯƒcondition(R) returns the tuples of relation R for which the condition is true. The result has the same attributes as R, and a subset of its tuples.

TEXT
ฯƒ credits >= 4 (courses)

The condition compares attributes with constants or with each other (=, <>, <, <=, >, >=) and can be combined with โˆง (and), โˆจ (or) and ยฌ (not). In SQL the condition goes in WHERE.

SQL Selection is WHERE ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

A tuple is kept only when the condition is true. In textbook algebra there are no nulls, but real SQL has three-valued logic: a row whose condition is unknown is dropped, just like a false one (Nulls and Three-Valued Logic). This is why the students in homeroom A and the students not in homeroom A do not add up to everyone: students with no homeroom (NULL) belong to neither group.

Projection: pi

Projection ฯ€A1, A2, ...(R) keeps only the listed attributes, in the listed order, and drops the rest.

TEXT
ฯ€ code, title (courses)

In SQL that is the SELECT list. There is one important difference. In the algebra, a relation is a set, so projecting away the key can make two tuples identical, and the duplicate disappears automatically. SQL tables are bags (multisets): SELECT keeps duplicates unless you ask for DISTINCT.

SQL Projection removes columns, and duplicates only with DISTINCT ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The first query returns one row per course (including repeats, because some teachers give two courses, and an empty value for the course without a teacher), the second returns each teacher id once. Compare the row counts. Whenever the algebra says "relation", read "set"; whenever SQL returns rows, expect a bag unless DISTINCT appears.

Projection can also compute: generalized projection allows expressions such as credits * 10 in the list. That extension is covered in Division, Aggregation and Extended Operators.

Rename: rho

Rename ฯS(B1, ..., Bn)(R) gives the result the relation name S and attribute names B1, ..., Bn. It looks like a luxury, but it is essential in two situations: joining a relation with itself (you need two names for it) and making the output of an expression readable.

TEXT
ฯ big_courses(course_code, name) ( ฯ€ code, title ( ฯƒ credits >= 4 (courses) ) )

In SQL, renaming is done with AS, for both columns and tables.

SQL Rename is AS ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Composing operators

Because each operator returns a relation, you can nest them. To list the codes of the courses worth at least four credits, first select the rows, then project the column:

TEXT
ฯ€ code ( ฯƒ credits >= 4 (courses) )

Read it from the inside out: first ฯƒ, then ฯ€. The same query can be drawn as an expression tree, with the base relation at the leaf and the final result at the root.

flowchart BT
    C["courses"] --> S["ฯƒ credits >= 4"]
    S --> P["ฯ€ code, title"]

An expression tree is evaluated bottom-up: each node feeds its parent.

The nesting order matters. You can not project first and then select on a column that has already been dropped:

TEXT
ฯƒ credits >= 4 ( ฯ€ code, title (courses) )     -- invalid: credits no longer exists

The reverse composition (select, then project) is always possible. A few useful equivalences also hold:

  • Cascade of selections: ฯƒa โˆง b(R) = ฯƒa(ฯƒb(R)).
  • Selections commute: ฯƒa(ฯƒb(R)) = ฯƒb(ฯƒa(R)).
  • Only the last projection of a cascade matters: ฯ€A(ฯ€B(R)) = ฯ€A(R) when A โІ B.
SQL Selection cascades: one query, two forms ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Both queries return the same three titles (Algebra Foundations, Mechanics and Cell Biology). An optimizer is free to choose either form, because the algebra proves they are equivalent. That freedom is the reason the algebra exists.

Reading SQL as algebra

Any simple SELECT ... FROM ... WHERE query is the composition ฯ€(ฯƒ(R)). The order the engine thinks in is: pick the table (FROM), filter its rows (WHERE, ฯƒ), and finally choose and rename columns (SELECT, ฯ€ and ฯ), even though you write SELECT first. Queries Through the Lens of Theory walks through the full order of evaluation.

SQL Translate algebra to SQL yourself ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The first query returns three students. The second returns A, B, C and one row with an empty (NULL) value: duplicates are removed, but NULL still counts as a value for DISTINCT.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does ฯƒ credits >= 4 (courses) return?

    Selection filters tuples and keeps every attribute. Choosing columns is the job of projection.
  2. 2. Why can projecting a relation produce fewer tuples than the input?

    In the algebra the result is a set, so duplicates vanish. In SQL you only get this behavior with DISTINCT.
  3. 3. Which SQL clause corresponds to selection?

    WHERE filters rows, which is selection (ฯƒ). The SELECT list is projection (ฯ€).
  4. 4. Why is ฯƒ credits >= 4 ( ฯ€ code, title (courses) ) invalid?

    Each operator sees only the attributes produced by the one inside it. Select first, then project.
  5. 5. When is rename (ฯ) essential rather than cosmetic?

    To join a relation with itself, each use needs its own name, which rename (AS in SQL) provides.

Summary

  • Relational algebra operators take relations and return relations, so they compose into expression trees.
  • Selection ฯƒ filters rows (SQL WHERE), projection ฯ€ chooses columns (the SELECT list), rename ฯ gives new names (AS).
  • The algebra works on sets, so projection removes duplicates; SQL works on bags and needs DISTINCT to match.
  • Selections cascade and commute; a projection can only name attributes its input still has.
  • Rows whose condition is unknown (NULL) are filtered out, just like false ones.

Next: combining two relations with Union, Intersection, Difference and Cartesian Product.