Introduction to Relational Algebra

by K. Yue

1. Introduction

• More theoretical query languages of the relational model:
  1. relational algebra: procedural/operational/functional
  2. relational calculus: declarative
• Provide theoretical foundation for the relational model.
• Relational algebra:
  • Include a set of basic and derived set-theoretic operations.
  • Procedural: specify a sequence of operations.
    • performance optimization is important.
  • Operations can be unary or binary.
  • The result is also a relation: closure property => chained operations.
  • RA solutions are algorithmic.

2. Basic Operations

Cartesian Product

1. Same as the usual definition of Cartesian Product of two sets.
   1. Remember that a relation is a set.
2. Merge all possible information from two relations.
3. Also called Cross Product or Cross Join.
4. Name ambiguity may be resolved by using full names.
5. The cardinality of a set S is |S|, the number of elements in the set.
6. |RxS|= |R| * |S|
7. Not very useful in practice as the result can be large and constructing the result can be time consuming.

Example:

R(A,B,C) has three tuples. S(A,D) has four tuples.

The result of R x S always has 12 tuples with the schema (R.A, B, C, S.A, D).

Example: in toyu

student:
+--------+-----------+---------+-------+-------+---------+---------+
| stuId  | fname     | lname   | major | minor | credits | advisor |
+--------+-----------+---------+-------+-------+---------+---------+
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 |
+--------+-----------+---------+-------+-------+---------+---------+
10 rows in set


enroll:
+--------+---------+-------+----------+
| stuId  | classId | grade | n_alerts |
+--------+---------+-------+----------+
| 100000 |   10000 | A     |        0 |
| 100001 |   10000 | NULL  |     NULL |
| 100002 |   10000 | B-    |        3 |
| 100000 |   10001 | A     |        2 |
| 100001 |   10001 | A-    |        0 |
| 100000 |   10002 | B+    |        1 |
| 100002 |   10002 | B+    |        2 |
| 100000 |   10003 | C     |        0 |
| 100002 |   10003 | D     |        4 |
| 100004 |   10003 | A     |        0 |
| 100005 |   10003 | NULL  |     NULL |
| 100000 |   10004 | A-    |        1 |
| 100004 |   10004 | B+    |     NULL |
| 100005 |   10004 | A-    |        0 |
| 100006 |   10004 | C+    |     NULL |
| 100005 |   10005 | A-    |        0 |
| 100006 |   10005 | A     |     NULL |
| 100005 |   10006 | B+    |     NULL |
| 100007 |   10007 | F     |        4 |
| 100008 |   10007 | C-    |        0 |
| 100007 |   10008 | A-    |        0 |
| 100000 |   11001 | D     |        4 |
+--------+---------+-------+----------+
22 rows


student x enroll:
+--------+-----------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
| stuId  | fname     | lname   | major | minor | credits | advisor | stuId  | classId | grade | n_alerts |
+--------+-----------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10000 | A     |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   10000 | A     |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   10000 | A     |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   10000 | A     |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   10000 | A     |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   10000 | A     |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   10000 | A     |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   10000 | A     |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   10000 | A     |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   10000 | A     |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100001 |   10000 | NULL  |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100001 |   10000 | NULL  |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100001 |   10000 | NULL  |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100001 |   10000 | NULL  |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100001 |   10000 | NULL  |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100001 |   10000 | NULL  |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100001 |   10000 | NULL  |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100001 |   10000 | NULL  |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100001 |   10000 | NULL  |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100001 |   10000 | NULL  |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100002 |   10000 | B-    |        3 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100002 |   10000 | B-    |        3 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10000 | B-    |        3 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100002 |   10000 | B-    |        3 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100002 |   10000 | B-    |        3 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100002 |   10000 | B-    |        3 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100002 |   10000 | B-    |        3 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100002 |   10000 | B-    |        3 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100002 |   10000 | B-    |        3 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100002 |   10000 | B-    |        3 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10001 | A     |        2 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   10001 | A     |        2 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   10001 | A     |        2 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   10001 | A     |        2 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   10001 | A     |        2 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   10001 | A     |        2 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   10001 | A     |        2 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   10001 | A     |        2 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   10001 | A     |        2 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   10001 | A     |        2 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100001 |   10001 | A-    |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100001 |   10001 | A-    |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100001 |   10001 | A-    |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100001 |   10001 | A-    |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100001 |   10001 | A-    |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100001 |   10001 | A-    |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100001 |   10001 | A-    |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100001 |   10001 | A-    |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100001 |   10001 | A-    |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100001 |   10001 | A-    |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10002 | B+    |        1 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   10002 | B+    |        1 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   10002 | B+    |        1 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   10002 | B+    |        1 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   10002 | B+    |        1 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   10002 | B+    |        1 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   10002 | B+    |        1 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   10002 | B+    |        1 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   10002 | B+    |        1 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   10002 | B+    |        1 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100002 |   10002 | B+    |        2 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100002 |   10002 | B+    |        2 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10002 | B+    |        2 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100002 |   10002 | B+    |        2 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100002 |   10002 | B+    |        2 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100002 |   10002 | B+    |        2 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100002 |   10002 | B+    |        2 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100002 |   10002 | B+    |        2 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100002 |   10002 | B+    |        2 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100002 |   10002 | B+    |        2 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10003 | C     |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   10003 | C     |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   10003 | C     |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   10003 | C     |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   10003 | C     |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   10003 | C     |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   10003 | C     |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   10003 | C     |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   10003 | C     |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   10003 | C     |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100002 |   10003 | D     |        4 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100002 |   10003 | D     |        4 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10003 | D     |        4 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100002 |   10003 | D     |        4 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100002 |   10003 | D     |        4 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100002 |   10003 | D     |        4 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100002 |   10003 | D     |        4 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100002 |   10003 | D     |        4 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100002 |   10003 | D     |        4 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100002 |   10003 | D     |        4 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100004 |   10003 | A     |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100004 |   10003 | A     |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100004 |   10003 | A     |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100004 |   10003 | A     |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100004 |   10003 | A     |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100004 |   10003 | A     |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100004 |   10003 | A     |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100004 |   10003 | A     |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100004 |   10003 | A     |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100004 |   10003 | A     |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100005 |   10003 | NULL  |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100005 |   10003 | NULL  |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100005 |   10003 | NULL  |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100005 |   10003 | NULL  |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100005 |   10003 | NULL  |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10003 | NULL  |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100005 |   10003 | NULL  |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100005 |   10003 | NULL  |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100005 |   10003 | NULL  |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100005 |   10003 | NULL  |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10004 | A-    |        1 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   10004 | A-    |        1 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   10004 | A-    |        1 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   10004 | A-    |        1 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   10004 | A-    |        1 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   10004 | A-    |        1 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   10004 | A-    |        1 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   10004 | A-    |        1 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   10004 | A-    |        1 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   10004 | A-    |        1 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100004 |   10004 | B+    |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100004 |   10004 | B+    |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100004 |   10004 | B+    |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100004 |   10004 | B+    |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100004 |   10004 | B+    |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100004 |   10004 | B+    |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100004 |   10004 | B+    |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100004 |   10004 | B+    |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100004 |   10004 | B+    |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100004 |   10004 | B+    |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100005 |   10004 | A-    |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100005 |   10004 | A-    |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100005 |   10004 | A-    |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100005 |   10004 | A-    |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100005 |   10004 | A-    |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10004 | A-    |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100005 |   10004 | A-    |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100005 |   10004 | A-    |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100005 |   10004 | A-    |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100005 |   10004 | A-    |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100006 |   10004 | C+    |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100006 |   10004 | C+    |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100006 |   10004 | C+    |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100006 |   10004 | C+    |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100006 |   10004 | C+    |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100006 |   10004 | C+    |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100006 |   10004 | C+    |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100006 |   10004 | C+    |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100006 |   10004 | C+    |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100006 |   10004 | C+    |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100005 |   10005 | A-    |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100005 |   10005 | A-    |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100005 |   10005 | A-    |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100005 |   10005 | A-    |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100005 |   10005 | A-    |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10005 | A-    |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100005 |   10005 | A-    |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100005 |   10005 | A-    |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100005 |   10005 | A-    |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100005 |   10005 | A-    |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100006 |   10005 | A     |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100006 |   10005 | A     |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100006 |   10005 | A     |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100006 |   10005 | A     |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100006 |   10005 | A     |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100006 |   10005 | A     |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100006 |   10005 | A     |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100006 |   10005 | A     |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100006 |   10005 | A     |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100006 |   10005 | A     |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100005 |   10006 | B+    |     NULL |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100005 |   10006 | B+    |     NULL |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100005 |   10006 | B+    |     NULL |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100005 |   10006 | B+    |     NULL |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100005 |   10006 | B+    |     NULL |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10006 | B+    |     NULL |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100005 |   10006 | B+    |     NULL |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100005 |   10006 | B+    |     NULL |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100005 |   10006 | B+    |     NULL |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100005 |   10006 | B+    |     NULL |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100007 |   10007 | F     |        4 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100007 |   10007 | F     |        4 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100007 |   10007 | F     |        4 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100007 |   10007 | F     |        4 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100007 |   10007 | F     |        4 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100007 |   10007 | F     |        4 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100007 |   10007 | F     |        4 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100007 |   10007 | F     |        4 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100007 |   10007 | F     |        4 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100007 |   10007 | F     |        4 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100008 |   10007 | C-    |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100008 |   10007 | C-    |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100008 |   10007 | C-    |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100008 |   10007 | C-    |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100008 |   10007 | C-    |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100008 |   10007 | C-    |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100008 |   10007 | C-    |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100008 |   10007 | C-    |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100008 |   10007 | C-    |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100008 |   10007 | C-    |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100007 |   10008 | A-    |        0 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100007 |   10008 | A-    |        0 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100007 |   10008 | A-    |        0 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100007 |   10008 | A-    |        0 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100007 |   10008 | A-    |        0 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100007 |   10008 | A-    |        0 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100007 |   10008 | A-    |        0 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100007 |   10008 | A-    |        0 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100007 |   10008 | A-    |        0 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100007 |   10008 | A-    |        0 |
| 100000 | Tony      | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   11001 | D     |        4 |
| 100001 | Mary      | Hawk    | CSCI  | CINF  |      35 |    1011 | 100000 |   11001 | D     |        4 |
| 100002 | David     | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100000 |   11001 | D     |        4 |
| 100003 | Catherine | Lim     | ITEC  | CINF  |      20 |    1017 | 100000 |   11001 | D     |        4 |
| 100004 | Larry     | Johnson | ITEC  | NULL  |      66 |    1017 | 100000 |   11001 | D     |        4 |
| 100005 | Linda     | Johnson | CINF  | ENGL  |      13 |    1015 | 100000 |   11001 | D     |        4 |
| 100006 | Lillian   | Johnson | CINF  | ITEC  |      18 |    1015 | 100000 |   11001 | D     |        4 |
| 100007 | Ben       | Zico    | NULL  | NULL  |      16 |    NULL | 100000 |   11001 | D     |        4 |
| 100008 | Bill      | Ching   | ARTS  | ENGL  |      90 |    1018 | 100000 |   11001 | D     |        4 |
| 100009 | Linda     | King    | ARTS  | CSCI  |     125 |    1018 | 100000 |   11001 | D     |        4 |
+--------+-----------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
220 row

In SQL, the select statement is very powerful and can be used to simulate RA operations. For R * S:

SELECT R.*, S.*
FROM R, S; -- note that there is no join condition.

Select

1. Unary operation.
2. Select tuples (with the same schema) based on a Boolean condition.
3. Conditions may includes attributes in the relational schema.
4. The Boolean expression of the condition can be composite.
5. 'Horizontal' subset.
6. Not to be confused with the Select statement in SQL.

σ_cond(R) = {t | t ε R and cond}, or simply

σ_cond(R) = {t | t ε R, cond}

Example: All information of students majoring in CSCI.

σ_major='CSCI'(Student)

+--------+-------+-------+-------+-------+---------+---------+
| stuId  | fname | lname | major | minor | credits | advisor |
+--------+-------+-------+-------+-------+---------+---------+
| 100000 | Tony  | Hawk  | CSCI  | CINF  |      40 |    1011 |
| 100001 | Mary  | Hawk  | CSCI  | CINF  |      35 |    1011 |
| 100002 | David | Hawk  | CSCI  | ITEC  |      66 |    1011 |
+--------+-------+-------+-------+-------+---------+---------+
3 rows

In SQL, this is just:

SELECT *
FROM Student
WHERE major = 'CSCI';

Project

1. Unary operation
2. Select attributes from tuples.
3. Duplicate results removed (because a relation is a set).
4. 'Vertical' subset.

π_{c1, .., cm}(R) = {s | ∃t ε R (t(ci) = s(ci), for 1 <= i <= m)},

or simply

π_{c1, .., cm}(R) = {s | t ε R (t(ci) = s(ci), for 1 <= i <= m)}

Example: Names and majors of students

π_{LName, FName, Major}(Student):

+-----------+---------+-------+
| FName     | LName   | Major |
+-----------+---------+-------+
| Tony      | Hawk    | CSCI  |
| Mary      | Hawk    | CSCI  |
| David     | Hawk    | CSCI  |
| Catherine | Lim     | ITEC  |
| Larry     | Johnson | ITEC  |
| Linda     | Johnson | CINF  |
| Lillian   | Johnson | CINF  |
| Ben       | Zico    | NULL  |
| Bill      | Ching   | ARTS  |
| Linda     | King    | ARTS  |
+-----------+---------+-------+
10 rows

Union

1. The set union operator.
2. Condition for R U S: R and S must be union compatible. Their relation schema must have compatible schema with the same structures. Each corresponding attributes must have the same types (domains).

R U S = {t | t ε R V t ε S}

Example:

Suppose StaffID and FacultyID are union compatible.

 π_StaffID(Staff) U π_FacultyID(Faculty)

Example: All information of students majoring in CSCI or ARTS.

σ_{(major='CSCI')} (Student) U σ_{(major='ARTS')} (Student)

or

σ_{(major='CSCI') V (major='ARTS')} (Student)

+--------+-------+-------+-------+-------+---------+---------+
| stuId  | fname | lname | major | minor | credits | advisor |
+--------+-------+-------+-------+-------+---------+---------+
| 100008 | Bill  | Ching | ARTS  | ENGL  |      90 |    1018 |
| 100009 | Linda | King  | ARTS  | CSCI  |     125 |    1018 |
| 100000 | Tony  | Hawk  | CSCI  | CINF  |      40 |    1011 |
| 100001 | Mary  | Hawk  | CSCI  | CINF  |      35 |    1011 |
| 100002 | David | Hawk  | CSCI  | ITEC  |      66 |    1011 |
+--------+-------+-------+-------+-------+---------+---------+
5 rows

Difference (Minus)

1. The set difference operator.
2. R - S: R and S must be union compatible.

R - S = {t | t ε R and not (t ε S)}

Example: Information of all students majoring in CSCI but those not taken credits less than 40.

σ_major='CSCI'(Student) - σ_{credit <40} (Student)

+--------+-------+-------+-------+-------+---------+---------+
| stuId  | fname | lname | major | minor | credits | advisor |
+--------+-------+-------+-------+-------+---------+---------+
| 100000 | Tony  | Hawk  | CSCI  | CINF  |      40 |    1011 |
| 100002 | David | Hawk  | CSCI  | ITEC  |      66 |    1011 |
+--------+-------+-------+-------+-------+---------+---------+
2 rows

Note that this is the same as:

σ_{major='CSCI' and credit >=40}(Student)

Rename

1. Rename the names of selected attributes in a relation.
2. Maybe used to rename attributes before a set operation.
3. Notation in Elmarsi (a popular db textbook:

• A better notation includes the original name and the new name.

Example:

rename _{(FacultyId, department <- FacId, deptCde)} (Faculty)

+-----------+----------+----------+------------+---------------------+
| facultyId | fname    | lname    | department | rank                |
+-----------+----------+----------+------------+---------------------+
|      1011 | Paul     | Smith    | CSCI       | Professor           |
|      1012 | Mary     | Tran     | CSCI       | Associate Professor |
|      1013 | David    | Love     | CSCI       | NULL                |
|      1014 | Sharon   | Mannes   | CSCI       | Assistant Professor |
|      1015 | Daniel   | Kim      | CINF       | Professor           |
|      1016 | Andrew   | Byre     | CINF       | Associate Professor |
|      1017 | Deborah  | Gump     | ITEC       | Professor           |
|      1018 | Art      | Allister | ARTS       | Assistant Professor |
|      1019 | Benjamin | Yu       | ITEC       | Lecturer            |
|      1020 | Katrina  | Bajaj    | ENGL       | Lecturer            |
|      1021 | Jorginlo | Neymar   | ACCT       | Assistant Professor |
+-----------+----------+----------+------------+---------------------+
11 rows

• The basic set of operations is complete. Other relational algebra operations can be derived from them.

3. Common Derived Operations

Theta-join

1. Allow the application of condition on Cartesian product.
2. There are still redundant data on common attributes.
3. Allow the query engine to throw away tuples not in the result immediately.
4. Conceptually, a Cartesian Product followed by a selection.
5. Not usually used.

R₁ |x|_ΘR₂ = σ_Θ(R₁ x R₂)

Example: All related information of students with 70 or more credits and a grade A or better in some courses.

Student |x|_{(credits >= 70 and grade = 'A')} Enroll

+--------+-------+-------+-------+-------+---------+---------+--------+---------+-------+----------+
| stuId  | fname | lname | major | minor | credits | advisor | stuId  | classId | grade | n_alerts |
+--------+-------+-------+-------+-------+---------+---------+--------+---------+-------+----------+
| 100008 | Bill  | Ching | ARTS  | ENGL  |      90 |    1018 | 100000 |   10000 | A     |        0 |
| 100008 | Bill  | Ching | ARTS  | ENGL  |      90 |    1018 | 100000 |   10001 | A     |        2 |
| 100008 | Bill  | Ching | ARTS  | ENGL  |      90 |    1018 | 100004 |   10003 | A     |        0 |
| 100008 | Bill  | Ching | ARTS  | ENGL  |      90 |    1018 | 100006 |   10005 | A     |     NULL |
| 100009 | Linda | King  | ARTS  | CSCI  |     125 |    1018 | 100000 |   10000 | A     |        0 |
| 100009 | Linda | King  | ARTS  | CSCI  |     125 |    1018 | 100000 |   10001 | A     |        2 |
| 100009 | Linda | King  | ARTS  | CSCI  |     125 |    1018 | 100004 |   10003 | A     |        0 |
| 100009 | Linda | King  | ARTS  | CSCI  |     125 |    1018 | 100006 |   10005 | A     |     NULL |
+--------+-------+-------+-------+-------+---------+---------+--------+---------+-------+----------+
8 rows in set (0.01 sec)


 Equi-join

1. Theta-join where the condition involves only equality comparisons.
2. There are still redundant data on common attributes.
3. Common attributes are attributes that have the same names, not the same meaning.
4. Not usually used.

Example:

Student |x| _{(Student.StuId = Enrol.StuId)} Enroll

+--------+---------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
| stuId  | fname   | lname   | major | minor | credits | advisor | stuId  | classId | grade | n_alerts |
+--------+---------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10000 | A     |        0 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10001 | A     |        2 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10002 | B+    |        1 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10003 | C     |        0 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   10004 | A-    |        1 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 | 100000 |   11001 | D     |        4 |
| 100001 | Mary    | Hawk    | CSCI  | CINF  |      35 |    1011 | 100001 |   10000 | NULL  |     NULL |
| 100001 | Mary    | Hawk    | CSCI  | CINF  |      35 |    1011 | 100001 |   10001 | A-    |        0 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10000 | B-    |        3 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10002 | B+    |        2 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 | 100002 |   10003 | D     |        4 |
| 100004 | Larry   | Johnson | ITEC  | NULL  |      66 |    1017 | 100004 |   10003 | A     |        0 |
| 100004 | Larry   | Johnson | ITEC  | NULL  |      66 |    1017 | 100004 |   10004 | B+    |     NULL |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10003 | NULL  |     NULL |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10004 | A-    |        0 |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10005 | A-    |        0 |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 | 100005 |   10006 | B+    |     NULL |
| 100006 | Lillian | Johnson | CINF  | ITEC  |      18 |    1015 | 100006 |   10004 | C+    |     NULL |
| 100006 | Lillian | Johnson | CINF  | ITEC  |      18 |    1015 | 100006 |   10005 | A     |     NULL |
| 100007 | Ben     | Zico    | NULL  | NULL  |      16 |    NULL | 100007 |   10007 | F     |        4 |
| 100007 | Ben     | Zico    | NULL  | NULL  |      16 |    NULL | 100007 |   10008 | A-    |        0 |
| 100008 | Bill    | Ching   | ARTS  | ENGL  |      90 |    1018 | 100008 |   10007 | C-    |        0 |
+--------+---------+---------+-------+-------+---------+---------+--------+---------+-------+----------+
22 rows

It is important to note the difference between names and meaning. Consider

student(stuId, ... advisorFacId, ..., createTime) and

faculty(facId, ..., createTime)

1. The attributes createTime in student and faculty have the same name, but different meaning.
   1. Student(createTime) is the time the student row is inserted into the student table.
   2. Faculty(createTime) is the time the faculty row is inserted into the faculty table
2. student(advisorFacId) and faculty(facId) have different names but same meaning. In fact, student(advisorFacId) is a foreign key that references faculty(facId).

Natural Join

1. Remove redundant common attributes.
   1. Equi-join on all common attributes.
   2. Projection to remove redundant common attributes.
2. Used very frequently to combine two tables.
3. If two relations do not share any common attributes, their natural join is the same as their Cartesian Product.

Let C1, C2, ... Cm be the common attributes of R and S.

R |x| S = π_{A1, A2, .. Al}(σ_{R.C1=S.C1,.., R.Cm=S.Cm}(RxS)

where A1, A2, ... Al is the list of components in RxS except S.C1, S.C2,.. S.Cm.

Example:

The schema of R(A,B) |x| S(A,C) is ABC. The schema of R(A,B) x S(A,C) is {R.A, B, S.A, C}.

Example:

Student |x| Enroll:

+--------+---------+---------+-------+-------+---------+---------+---------+-------+----------+
| stuId  | fname   | lname   | major | minor | credits | advisor | classId | grade | n_alerts |
+--------+---------+---------+-------+-------+---------+---------+---------+-------+----------+
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   10000 | A     |        0 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   10001 | A     |        2 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   10002 | B+    |        1 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   10003 | C     |        0 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   10004 | A-    |        1 |
| 100000 | Tony    | Hawk    | CSCI  | CINF  |      40 |    1011 |   11001 | D     |        4 |
| 100001 | Mary    | Hawk    | CSCI  | CINF  |      35 |    1011 |   10000 | NULL  |     NULL |
| 100001 | Mary    | Hawk    | CSCI  | CINF  |      35 |    1011 |   10001 | A-    |        0 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 |   10000 | B-    |        3 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 |   10002 | B+    |        2 |
| 100002 | David   | Hawk    | CSCI  | ITEC  |      66 |    1011 |   10003 | D     |        4 |
| 100004 | Larry   | Johnson | ITEC  | NULL  |      66 |    1017 |   10003 | A     |        0 |
| 100004 | Larry   | Johnson | ITEC  | NULL  |      66 |    1017 |   10004 | B+    |     NULL |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 |   10003 | NULL  |     NULL |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 |   10004 | A-    |        0 |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 |   10005 | A-    |        0 |
| 100005 | Linda   | Johnson | CINF  | ENGL  |      13 |    1015 |   10006 | B+    |     NULL |
| 100006 | Lillian | Johnson | CINF  | ITEC  |      18 |    1015 |   10004 | C+    |     NULL |
| 100006 | Lillian | Johnson | CINF  | ITEC  |      18 |    1015 |   10005 | A     |     NULL |
| 100007 | Ben     | Zico    | NULL  | NULL  |      16 |    NULL |   10007 | F     |        4 |
| 100007 | Ben     | Zico    | NULL  | NULL  |      16 |    NULL |   10008 | A-    |        0 |
| 100008 | Bill    | Ching   | ARTS  | ENGL  |      90 |    1018 |   10007 | C-    |        0 |
+--------+---------+---------+-------+-------+---------+---------+---------+-------+----------+
22 rows

Exercise:

Let the cardinality of R(A,B) be 5 and the cardinality of S(A,C) be 6. What is the range of the cardinality of R(A,B) |x| S(A,C)?

Additional Materials: Other Joins

1. Some other joins are outer join, inner join and semi-join.
2. They can be defined through relational algebra expressions based on the basic operations.
3. Look them up when needs arise. For example: https://en.wikipedia.org/wiki/Relational_algebra

Additional Materials: Division

1. R / S
2. Condition: the domain of S is a proper subset of R.
3. Let the schemes of R, S and T be dom(R), dom(S) and dom(T) = dom(R) - dom(S) respectively.
4. R / S = {t | t in dom(T) and for all s ε S, there exist r ε R such that r = st}.
5. In term of basic RA operations, R / S = π_R-S(R) - π_R-S((π_R-S(R) x S) - R))

Example:

Find the student id of all students who enrolled in all courses offered by the faculty '1014':

Stuid and classNumber information (who is enrolled in which class):

π_{(stuId, classId)} (Enroll): rows added to Class.

+--------+---------+
| stuId  | classId |
+--------+---------+
| 100000 |   10000 |
| 100000 |   10001 |
| 100000 |   10002 |
| 100000 |   10003 |
| 100000 |   10004 |
| 100000 |   11001 |
| 100001 |   10000 |
| 100001 |   10001 |
| 100002 |   10000 |
| 100002 |   10002 |
| 100002 |   10003 |
| 100004 |   10003 |
| 100004 |   10004 |
| 100005 |   10003 |
| 100005 |   10004 |
| 100005 |   10005 |
| 100005 |   10006 |
| 100006 |   10004 |
| 100006 |   10005 |
| 100007 |   10007 |
| 100007 |   10008 |
| 100008 |   10007 |
+--------+---------+
22 rows

Classes offered by faculty '1014':

π_(classId) (σ_{(facId='1014)} (Class)):

+---------+
| classId |
+---------+
|   10003 |
|   10004 |
+---------+
2 rows
 

Solution:

π_{(stuId, classId)} (Enroll) / π_{(stuId, classId)} (Enroll):

+--------+
| stuId  |
+--------+
| 100000 |
| 100004 |
| 100005 |
+--------+
3 rows

4. Epilog

Some shortcomings of Relational Algebra:

1. Cannot navigate tuples.
2. Cannot deal with recursion.
   1. e.g. for the relation Employee(SSN, Supervisor_SSN, ...), find all supervisors (direct or indirect).
   2. May extend to logical database, e.g. Datalog.
3. No group functions.
   1. e.g. Show the available total quantities of all parts.
4. Operation too simple, resulting in long sequences.