Relational algebra is a set of operators to retrieve and manipulate tuples in a relation. Each operator takes in one or more relations as inputs, and outputs a new relation. To write queries we can “chain” these operators together to create more complex operations.

Relational algebra describes a step-by-step procedure (i.e. describes the how) for computing the desired answer (imperative). This contrast with tuple calculus, which is declarative.

Different relational algebra expressions can be logically equivalent but with different execution costs. This gives DBMS opportunities to optimize.

Basic Operators

Select

Select is a unary operator that selects a subset of rows from a relation.

  • Syntax:
  • Example:
  • SQL: SELECT * FROM Students WHERE country = 'AUS'

The select operator corresponds to WHERE rather than SELECT in SQL

Projection

The projection is an unary operator that selects a subset of columns from a relation

  • Syntax:
  • Example:
  • SQL: SELECT name,country FROM Students

The projection operator correspond to SELECT in SQL

Cross-product

The cross product operator, also known as the Cartesian product, generates all possible combinations of tuples from two relations. It is defined as . SQL: (SELECT * FROM R) CROSS JOIN (SELECT * FROM S), or simply SELECT * FROM R, S

Join

combines matching tuples from two relations

Conditional (or Theta) Join

Equi-Join

Special case of theta join where the condition contains only equalities

Natural Join

Equijoin on all common (i.e. same named) fields, followed by a projection

  • Syntax:
  • SQL: SELECT * FROM R JOIN S USING (ATTRIBUTE1, ATTRIBUTE)

Set Operations

Important constraint: and have compatible schema

Union

Set union of a relations A and B returns all tuples in relation A plus those that are in relation B Syntax: SQL: (SELECT * FROM R) UNION ALL (SELECT * FROM S)

Intersection

Set intersection Syntax: SQL: (SELECT * FROM R) INTERSECT (SELECT * FROM S)

Difference

Set difference Syntax: SQL: (SELECT * FROM R) EXCEPT (SELECT * FROM S)

Rename ()

Notation 1:

  • returns the expression under the name Notation 2:
  • (assumes that the relational-algebra expression E has arity N)
  • rename all the attributes

Basis versus Derived Operations

Only 6 basic operators are required to express everything else

  • Selection
  • Projection
  • Cross-product
  • Union
  • Set Difference
  • Rename

Other operators can be derived. For example:

  • Intersection
  • join