Skip to content

Relational Algebra

Relation Algebra

alt text

A relational algebra calculator - RelaX

  • https://dbis-uibk.github.io/relax/landing
  • An online tool designed to help users learn and practice relational algebra by executing queries and visualizing the results
  • How to create relations and insert tuples into them:
    1. Click on 'Group Editor' tab
    2. Copy into 'Group Editor' window your data. Find below my examples!
    3. Click on "preview" button then double click on "use Group in editor" button
    4. Now you can run your queries clicking on 'Relational Algebra' or 'SQL' tab.
  • This implementation allows only sets and not multisets.
  • There are differences between Oracle and Relax SQL syntax.
  • Name of a relation is case-sensitive.

RelaX Example

alt text

RelaX Website

(Free online tool to practice relational algebra expressions with instant results and SQL comparison.)

Core Relational Algebra

  • Union, intersection, and difference.
    • Usual set operations, but both operands must have the same relation schema.
  • Selection: picking certain rows.
  • Projection: picking certain columns.
  • Products and joins: compositions of relations.
  • Renaming of relations and attributes.

Union, intersection, difference

  • \( R \cup S \)
    • SELECT ... UNION SELECT ...;
    • (Duplicate elimination: UNION ALL: multiset, UNION: set)
  • \( R \cap S \)
    • SELECT ... INTERSECT SELECT ...;
  • \( R - S \)
    • SELECT ... MINUS SELECT ...;
    • (Some DBMS uses EXCEPT)

Selection

  • \( R1 := \sigma_{C}(R2) \)
    • \( C \) is a condition (as in "if" statements) that refers to attributes of \( R2 \).
    • \( R1 \) is all those tuples of \( R2 \) that satisfy \( C \).
    • SELECT * FROM R2 WHERE C;

Projection

  • \( R1 := \pi_{L}(R2) \)
    • \( L \) is a list of attributes from the schema of \( R2 \).
    • \( R1 \) is constructed by looking at each tuple of \( R2 \), extracting the attributes on list \( L \), in the order specified, and creating from those components a tuple for \( R1 \).
    • Eliminate duplicate tuples, if any.
    • SELECT DISTINCT L FROM R2;

Extended Projection

  • Using the same \( \pi_L \) operator, we allow the list \( L \) to contain arbitrary expressions involving attributes:
    1. Arithmetic on attributes, e.g., \( A+B \rightarrow C \).
    2. Duplicate occurrences of the same attribute.
  • SELECT A+B AS C FROM R;
  • (AS -> optional)

Product

  • \( R3 := R1 \times R2 \)
    • Pair each tuple \( t1 \) of \( R1 \) with each tuple \( t2 \) of \( R2 \).
    • Concatenation \( t1t2 \) is a tuple of \( R3 \).
    • Schema of \( R3 \) is the attributes of \( R1 \) and then \( R2 \), in order.
    • But beware attribute \( A \) of the same name in \( R1 \) and \( R2 \): use \( R1.A \) and \( R2.A \).
  • SELECT * FROM R1, R2; or
  • SELECT * FROM R1 CROSS JOIN R2;

Theta-Join

  • \( R3 := R1 \bowtie_{C} R2 \)
    • Take the product \( R1 \times R2 \).
    • Then apply \( \sigma_{C} \) to the result.
  • As for \( \sigma \), \( C \) can be any boolean-valued condition.
    • Historic versions of this operator allowed only \( A\ \theta\ B \), where \( \theta \) is \( =, < \), etc.; hence the name "theta-join."
  • SELECT * FROM R1 JOIN R2 ON (C);

Natural Join

  • A useful join variant (natural join) connects two relations by:
    • Equating attributes of the same name, and
    • Projecting out one copy of each pair of equated attributes.
  • Denoted \( R3 := R1 \bowtie R2 \).
  • SELECT * FROM R1 NATURAL JOIN R2;

Renaming

  • The \( \rho \) operator gives a new schema to a relation.
  • \( R1 := \rho_{R1(A1, ..., An)}(R2) \) makes \( R1 \) be a relation with attributes \( A1, ..., An \) and the same tuples as \( R2 \).
  • Simplified notation: \( R1(A1, ..., An) := R2 \).
  • SELECT X1 A1, X2 A2, ... Xn An FROM R2;
  • CREATE TABLE R1 AS SELECT X1 A1, X2 A2, ... Xn An FROM R2;

Sequences of Assignments

  • Create temporary relation names.
  • Renaming can be implied by giving relations a list of attributes.
  • Example: \( R3 := R1 \bowtie_{C} R2 \) can be written:
    • \( R4 := R1 \times R2 \) (CREATE TABLE R4 ...)
    • \( R3 := \sigma_{C}(R4) \) (SELECT ... FROM R4 ...)

Expressions in a Single Assignment

  • Example: the theta-join \( R3 := R1 \bowtie_{C} R2 \) can be written:
    • \( R3 := \sigma_{C}(R1 \times R2) \)
  • Precedence of relational operators:
    1. \( [\sigma, \pi, \rho] \) (highest).
    2. \( [\times, \bowtie] \).
    3. \( \cap \).
    4. \( [\cup, -] \).

The Extended Algebra

  • \( \pi_{L} \) extended projection
  • \( \delta \) = eliminate duplicates from bags.
  • \( \tau \) = sort tuples.
  • \( \gamma \) = grouping and aggregation.
  • Outerjoin: avoids "dangling tuples" = tuples that do not join with anything.

Extended Projection

  • Using the same \( \pi_{L} \) operator, we allow the list \( L \) to contain arbitrary expressions involving attributes:
    1. Arithmetic on attributes, e.g., \( A+B \rightarrow C \)
      • "→" stands for renaming the attribute in the result to "\( C \)"
    2. Duplicate occurrences of the same attribute.
  • SELECT A+B AS C FROM R;
  • ("AS" is optional)

Duplicate Elimination

  • \( R1 := \delta(R2) \).
  • \( R1 \) consists of one copy of each tuple that appears in \( R2 \) one or more times.

Sorting

  • \( R1 := \tau_{L}(R2) \).
    • \( L \) is a list of some of the attributes of \( R2 \).
  • \( R1 \) is the list of tuples of \( R2 \) sorted first on the value of the first attribute on \( L \), then on the second attribute of \( L \), and so on.
    • Break ties arbitrarily.
  • \( \tau \) is the only operator whose result is neither a set nor a bag.

Aggregation Operators

  • Aggregation operators are not operators of relational algebra.
  • Rather, they apply to entire columns of a table and produce a single result.
  • The most important examples: SUM, AVG, COUNT, MIN, and MAX.
    • Example with Table \( R(A, B) \):
      • \( SUM(A) = 7 \)
      • \( COUNT(A) = 3 \)
      • \( MAX(B) = 4 \)
      • \( AVG(B) = 3 \)

Grouping Operator

  • \( R1 := \gamma_{L}(R2) \). \( L \) is a list of elements that are either:
    1. Individual (grouping) attributes.
    2. \( AGG(A) \), where \( AGG \) is one of the aggregation operators and \( A \) is an attribute.
      • An arrow and a new attribute name renames the component.

Applying \( \gamma\ L\ (R) \)

  • Group \( R \) according to all the grouping attributes on list \( L \).
    • That is: form one group for each distinct list of values for those attributes in \( R \).
  • Within each group, compute \( AGG(A) \) for each aggregation on list \( L \).
  • Result has one tuple for each group:
    1. The grouping attributes and
    2. Their group’s aggregations.

Outer join

  • Suppose we join \( R \bowtie_{C} S \).
  • A tuple of \( R \) that has no tuple of \( S \) with which it joins is said to be dangling.
    • Similarly for a tuple of \( S \).
  • Outerjoin preserves dangling tuples by padding them NULL.

Examples

Relational Algebra Expression SQL Equivalent
\( \pi_{A, B+C \rightarrow X}(R) \) SELECT A, B+C AS X FROM R;
\( \delta(R) \) SELECT DISTINCT * FROM R;
\( R \cup S \) SELECT * FROM R UNION ALL SELECT * FROM S; (multiset)
\( R \cap S \) SELECT * FROM R INTERSECT ALL SELECT * FROM S; (!)
\( R - S \) SELECT * FROM R MINUS ALL SELECT * FROM S; (!)
\( \delta(R \cup S) \) SELECT * FROM R UNION SELECT * FROM S; (set)
\( \delta(R \cap S) \) SELECT * FROM R INTERSECT SELECT * FROM S; (set)
\( \delta(R) - \delta(S) \) SELECT * FROM R MINUS SELECT * FROM S; (set)
\( R \bowtie S \) SELECT * FROM R NATURAL JOIN S;
\( R \bowtie_{\theta} S \) SELECT * FROM R JOIN S ON (\theta);
\( R \times S \) SELECT * FROM R CROSS JOIN S; or SELECT * FROM R, S;
\( \gamma_{A, SUM(B)}(R) \) SELECT A, SUM(B) FROM R GROUP BY A;
\( \gamma_{A, COUNT(B)}(\delta \pi_{A,B} R) \) SELECT A, COUNT(DISTINCT B) FROM R GROUP BY A;
\( \tau_{A, B+C}(R) \) SELECT * FROM R ORDER BY A, B+C;
Outer join SELECT * FROM R NATURAL LEFT OUTER JOIN S;
Outer join SELECT * FROM R LEFT OUTER JOIN S ON R.B > S.D;

Execution steps

Execution steps of a SELECT statement expressed in relational algebra:

  1. Replace all usages of the temporary-tables defined in the WITH-clause.
  2. \( \bowtie \) joins or product operations after FROM-clause.
  3. \( \sigma \) selection based on the WHERE-clause.
  4. \( \gamma \) creating groups and computing aggregations, based on GROUP BY-clause.
  5. \( \sigma \) selection for the groups or tuples created from the groups, based on HAVING-clause.
  6. \( \pi \) projection based on SELECT-clause.
  7. \( \rho \) rename result attributes based on AS keyword.
  8. \( \cup \cap - \) UNION, INTERSECT, MINUS set operations.
  9. \( \delta \) duplicate elimination if we have DISTINCT.
  10. \( \tau \) sorting based on ORDER BY clause.