Relational Algebra: Selection, Projection and Rename

Concept

Relational algebra is a formal language of operators that take relations as input and produce relations as output. It is procedural — an expression describes a sequence of operations, not just a desired result.

It matters for two reasons: it is the foundation of query optimisation, because algebraic equivalences let an optimiser rewrite a query safely, and it is examined in almost every DBMS paper.

The closure property

   relation(s)  --->  [ operator ]  --->  relation

   Output is always a relation, so the output of one operator
   can be the input of the next. That is CLOSURE, and it is
   what allows expressions to be composed to any depth.

The sample relations

Every example in this phase uses these three, so they are worth reading once carefully.

  STUDENT                          COURSE
  +---------+--------+------+      +--------+-----------+---------+
  | roll_no | name   | dept |      | code   | title     | credits |
  +---------+--------+------+      +--------+-----------+---------+
  |   21    | Meera  | CS   |      | CS201  | Databases |    4    |
  |   22    | Ravi   | CS   |      | CS202  | Networks  |    3    |
  |   23    | Anitha | EC   |      | EC101  | Circuits  |    4    |
  |   24    | Kumar  | EC   |      +--------+-----------+---------+
  |   25    | Divya  | CS   |
  +---------+--------+------+      ENROL
                                   +---------+--------+-------+
                                   | roll_no | code   | marks |
                                   +---------+--------+-------+
                                   |   21    | CS201  |  87   |
                                   |   21    | CS202  |  74   |
                                   |   22    | CS201  |  91   |
                                   |   23    | EC101  |  65   |
                                   |   25    | CS201  |  45   |
                                   +---------+--------+-------+

1. Selection — sigma

Selection picks the tuples that satisfy a condition. It is a horizontal operation: it never changes the columns.

  NOTATION   sigma <condition> ( R )
  WRITTEN    SELECT[condition](R)

  SELECT[dept = CS](STUDENT)

  +---------+-------+------+
  | roll_no | name  | dept |
  +---------+-------+------+
  |   21    | Meera | CS   |
  |   22    | Ravi  | CS   |
  |   25    | Divya | CS   |
  +---------+-------+------+

  degree unchanged (3), cardinality reduced (5 -> 3)

Conditions may combine with AND, OR and NOT, and use the comparison operators. Selection is commutative: applying two selections in either order gives the same result, and two selections can always be merged into one with AND.

  SELECT[dept = CS](SELECT[roll_no > 21](STUDENT))
    =  SELECT[roll_no > 21](SELECT[dept = CS](STUDENT))
    =  SELECT[dept = CS AND roll_no > 21](STUDENT)

  All three are equivalent. An optimiser uses exactly this
  freedom to reorder work.

2. Projection — pi

Projection picks the attributes listed. It is a vertical operation, and it does one thing beginners forget: it removes duplicate tuples, because the result must be a relation and a relation is a set.

  NOTATION   pi <attribute list> ( R )
  WRITTEN    PROJECT[attributes](R)

  PROJECT[dept](STUDENT)

  +------+          NOT CS, CS, EC, EC, CS
  | dept |          Duplicates are removed, so five tuples
  +------+          become two.
  | CS   |
  | EC   |
  +------+

  PROJECT[name, dept](STUDENT)   -> 5 tuples, all distinct

  degree reduced, cardinality may reduce

Duplicate removal is the single most examined property of projection. Note that real query languages do not remove duplicates unless asked, which is one of the places where practice departs from the algebra.

Projection is not commutative with itself in a useful sense — the outer projection must use attributes the inner one kept:

  PROJECT[name](PROJECT[name, dept](STUDENT))   valid
  PROJECT[dept](PROJECT[name](STUDENT))         INVALID
                                                dept no longer exists

3. Rename — rho

Rename gives a relation, or its attributes, a new name. It exists so that an expression can refer to the same relation twice, which is what makes a self join possible.

  NOTATION   rho <new name> ( R )
             rho <new name (a1, a2, ...)> ( R )
  WRITTEN    RENAME[S](STUDENT)
             RENAME[S(r, n, d)](STUDENT)

  Needed whenever one relation appears twice in an
  expression, otherwise the attribute names are ambiguous:

    RENAME[A](STUDENT)  and  RENAME[B](STUDENT)
    then A.dept and B.dept are distinguishable.

Combining the three

  "The names of Computing students"

    PROJECT[name]( SELECT[dept = CS](STUDENT) )

    +-------+
    | name  |
    +-------+
    | Meera |
    | Ravi  |
    | Divya |
    +-------+

  ORDER MATTERS. Select first, then project:

    PROJECT[name](SELECT[dept = CS](STUDENT))   correct

    SELECT[dept = CS](PROJECT[name](STUDENT))   INVALID
      the projection already discarded dept, so the
      selection has nothing to test.

Why selection goes first — the optimisation rule

  Selection reduces the number of tuples.
  Projection reduces the number of attributes.

  Doing selection EARLY means every later operator handles
  fewer tuples. This is called PUSHING SELECTIONS DOWN, and
  it is the first heuristic every optimiser applies.

  Phase 14 returns to this. The point here is that the rule
  is justified by algebra, not by guesswork.

Common mistakes

• Forgetting projection removes duplicates. This is the most common lost mark in the whole phase.
• Projecting away an attribute a later selection needs. Select first.
• Thinking selection changes the columns. It never does.
• Omitting rename when a relation appears twice. The expression is then ambiguous.
• Writing conditions on attributes of another relation. Selection can only test attributes of its own input.

Exam and interview questions

1. Define selection, projection and rename with notation and an example of each.
2. Why does projection remove duplicates, and does a real query language do the same?
3. Show that two selections can be merged into one, and state why an optimiser cares.
4. Explain why selection should be applied before projection.
5. When is the rename operator necessary?

Practice

Use the three sample relations above.

1. Write the expression for the roll numbers of students scoring more than 70.
2. Write the expression for the distinct departments that have at least one student.
3. Explain why SELECT[credits = 4](PROJECT[title](COURSE)) is invalid.
4. Write an expression using rename that would let you compare two students from the same relation.

Conclusion

Selection filters rows, projection filters columns and removes duplicates, and rename makes reuse possible. Closure lets them compose, selection before projection is both correct and faster, and these three operators underpin every optimisation rule in Phase 14.