Relational algebra: the six core operators

Relational algebra is a small set of operators that take relations as input and give a relation back. Six of them form its core. Selection (σ) keeps the tuples that satisfy a condition. Projection (π) keeps the attributes you name. Union (∪) and set difference (−) combine two relations with matching headings. The Cartesian product (×) pairs every tuple of one relation with every tuple of another, and rename (ρ) gives a relation or its attributes new names. Intersection, the inner joins and division are shorthands for combinations of these six. Since every operator returns a relation, operators nest into expression trees, and the plans that database engines run are trees of operators of the same kind. This lesson runs each operator on a small college database, with a Python evaluator whose results you can check, and then asks the same questions in SQL, where duplicate rows behave differently.

The sample relations and the evaluator

Every example in this module uses the same three relations of a small college:

• Student(sid, name, branch): six students in the CSE, ECE and ME branches.
• Course(cid, title, dept, credits): six courses, each offered by one department.
• Enrolled(sid, cid, grade): twelve enrolments, one tuple per student and course.

Two details matter later. Farhan (sid 6) is enrolled in nothing, and nobody is enrolled in CS301, Compilers. Queries that look for what is missing, such as “students without a course”, need such tuples to give a non-empty answer.

"""The sample relations of this module: the students, courses and enrolments of a small college."""
from ra import Relation

Student = Relation(("sid", "name", "branch"), [
    (1, "Asha", "CSE"), (2, "Bilal", "ECE"), (3, "Chitra", "CSE"),
    (4, "Dev", "ME"), (5, "Esha", "CSE"), (6, "Farhan", "ECE"),
])

Course = Relation(("cid", "title", "dept", "credits"), [
    ("CS201", "Databases", "CSE", 4), ("CS202", "Operating Systems", "CSE", 4),
    ("CS301", "Compilers", "CSE", 4), ("MA101", "Discrete Mathematics", "MATH", 3),
    ("EC210", "Signals and Systems", "ECE", 3), ("HS101", "Technical Writing", "HSS", 2),
])

Enrolled = Relation(("sid", "cid", "grade"), [
    (1, "CS201", "A"), (1, "CS202", "B"), (1, "MA101", "A"),
    (2, "EC210", "A"), (2, "MA101", "B"),
    (3, "CS201", "B"), (3, "MA101", "A"),
    (4, "MA101", "C"),
    (5, "CS201", "A"), (5, "CS202", "A"), (5, "MA101", "B"), (5, "HS101", "A"),
])

A relation has a heading, the names of its attributes, and a body, a set of tuples. The evaluator stores the body as a Python frozenset, and a set holds each element once, so a tuple is either in a relation or not: it cannot be in it twice, which is exactly the set semantics of the algebra. Each operator is a few lines of code, and reading them is a good way to see what the operator promises. In a condition, t maps attribute names to the values of one tuple, so t["branch"] == "CSE" reads as branch = ‘CSE’.

"""A small relational-algebra evaluator, used by the examples of this lesson.

A relation has a heading (its attribute names, in order) and a body (a set of
tuples). The body is a Python frozenset, so a tuple is either in a relation or not:
it cannot be in it twice. That is the set semantics of relational algebra.
"""


def _order(row):
    # Numbers before text, so printed relations come out in a stable, readable order.
    return tuple((0, v, "") if isinstance(v, (int, float)) else (1, 0, str(v)) for v in row)


class Relation:
    def __init__(self, heading, rows):
        self.heading = tuple(heading)
        self.rows = frozenset(tuple(row) for row in rows)
        for row in self.rows:
            if len(row) != len(self.heading):
                raise ValueError(f"the tuple {row} does not fit the heading {self.heading}")

    def __len__(self):
        return len(self.rows)

    def show(self, title):
        rows = sorted(self.rows, key=_order)
        print(f"{title}: {len(rows)} tuple{'' if len(rows) == 1 else 's'}")
        widths = [max([len(h)] + [len(str(r[i])) for r in rows]) for i, h in enumerate(self.heading)]
        print("  " + " | ".join(h.ljust(w) for h, w in zip(self.heading, widths)).rstrip())
        for r in rows:
            print("  " + " | ".join(str(v).ljust(w) for v, w in zip(r, widths)).rstrip())
        print()


def select(r, condition):
    """σ: the tuples of r for which condition(t) is true (t maps attribute names to values)."""
    return Relation(r.heading, [row for row in r.rows if condition(dict(zip(r.heading, row)))])


def project(r, *names):
    """π: keep only the named attributes; tuples that become equal merge into one."""
    positions = [r.heading.index(n) for n in names]
    return Relation(names, [tuple(row[p] for p in positions) for row in r.rows])


def _union_compatible(r, s, op):
    if len(r.heading) != len(s.heading):
        raise ValueError(f"{op}: the degrees differ ({len(r.heading)} and {len(s.heading)})")
    for i in range(len(r.heading)):
        left = {type(row[i]).__name__ for row in r.rows}
        right = {type(row[i]).__name__ for row in s.rows}
        if left and right and left != right:
            raise ValueError(f"{op}: attribute {i + 1} holds {'/'.join(sorted(left))} values on the left "
                             f"and {'/'.join(sorted(right))} values on the right")


def union(r, s):
    """∪: the tuples in r, in s or in both (the result keeps r's attribute names)."""
    _union_compatible(r, s, "union")
    return Relation(r.heading, r.rows | s.rows)


def difference(r, s):
    """−: the tuples of r that are not in s."""
    _union_compatible(r, s, "difference")
    return Relation(r.heading, r.rows - s.rows)


def product(r, s):
    """×: every tuple of r followed by every tuple of s; no attribute name may appear on both sides."""
    clash = sorted(set(r.heading) & set(s.heading))
    if clash:
        raise ValueError(f"both relations have the attribute {', '.join(clash)}: rename one side first")
    return Relation(r.heading + s.heading, [a + b for a in r.rows for b in s.rows])


def rename(r, prefix=None, **new_names):
    """ρ: rename attributes one by one (rename(R, sid="esid")) or all at once (rename(R, "E") gives E.sid, ...)."""
    heading = [new_names.get(h, h) for h in r.heading]
    if prefix:
        heading = [f"{prefix}.{h}" for h in heading]
    return Relation(heading, r.rows)

Selection and projection

Selection filters tuples. The condition compares attributes with constants or with each other, using =, ≠, <, ≤, > and ≥, and combines comparisons with ∧ (and), ∨ (or) and ¬ (not). The result has the same heading as the input and at most as many tuples:

Projection cuts a relation down to the attributes it names, in that order. Tuples that differ only in the attributes that were dropped become equal, and a set keeps one of them. So π branch (Student) has one tuple per branch, not one per student:

from college import Course, Enrolled, Student
from ra import difference, product, project, rename, select, union

# σ and π
select(Student, lambda t: t["branch"] == "CSE").show("σ branch = 'CSE' (Student)")
project(Student, "branch").show("π branch (Student)")

# ∪ and −
took_cs201 = project(select(Enrolled, lambda t: t["cid"] == "CS201"), "sid")
took_ec210 = project(select(Enrolled, lambda t: t["cid"] == "EC210"), "sid")
union(took_cs201, took_ec210).show("π sid (σ cid = 'CS201' (Enrolled)) ∪ π sid (σ cid = 'EC210' (Enrolled))")
difference(project(Student, "sid"), project(Enrolled, "sid")).show("π sid (Student) − π sid (Enrolled)")
try:
    union(project(Student, "sid"), project(Course, "cid"))
except ValueError as error:
    print(f"π sid (Student) ∪ π cid (Course): refused, {error}")
print()

# × and ρ
pairs = product(Student, Course)
print(f"Student × Course: {len(pairs)} tuples, {len(pairs.heading)} attributes")
try:
    product(Student, Enrolled)
except ValueError as error:
    print(f"Student × Enrolled: refused, {error}")
both = product(Student, rename(Enrolled, "E"))
print(f"Student × ρ E (Enrolled): {len(both)} tuples, attributes {', '.join(both.heading)}")

σ branch = 'CSE' (Student): 3 tuples
  sid | name   | branch
  1   | Asha   | CSE
  3   | Chitra | CSE
  5   | Esha   | CSE

π branch (Student): 3 tuples
  branch
  CSE
  ECE
  ME

π sid (σ cid = 'CS201' (Enrolled)) ∪ π sid (σ cid = 'EC210' (Enrolled)): 4 tuples
  sid
  1
  2
  3
  5

π sid (Student) − π sid (Enrolled): 1 tuple
  sid
  6

π sid (Student) ∪ π cid (Course): refused, union: attribute 1 holds int values on the left and str values on the right

Student × Course: 36 tuples, 7 attributes
Student × Enrolled: refused, both relations have the attribute sid: rename one side first
Student × ρ E (Enrolled): 72 tuples, attributes sid, name, branch, E.sid, E.cid, E.grade

The first two results show the difference between the operators. Selection kept 3 whole tuples of Student. Projection kept all 6 students’ branches, which collapsed into 3 tuples, because three students share CSE and two share ECE. A projection is sure to return as many tuples as its input only when the attributes it keeps include a key of the input: π sid, name (Student) keeps all 6. Without a key it may return fewer, as here.

Two rules let you rearrange selections and projections without changing the answer. A selection on two conditions is the same as two selections, one after the other, in either order: σ c1 ∧ c2 (R) = σ c1 (σ c2 (R)). And a chain of projections is the same as its last one: π name (π sid, name (Student)) = π name (Student).

Union, difference and union compatibility

Union returns the tuples that are in either relation, and difference the tuples of the first relation that are not in the second. Both only make sense when the two relations are union-compatible: they have the same degree (number of attributes), and the attributes in the same position take their values from the same domain. The evaluator gives the result the attribute names of the left operand.

The examples above compare the students who took CS201 with those who took EC210. Both inputs are π sid of a selection on Enrolled, so they are union-compatible, and their union holds four students. π sid (Student) − π sid (Enrolled) finds the students with no enrolment at all: only Farhan, sid 6. The evaluator refuses π sid (Student) ∪ π cid (Course): both sides have one attribute, but one holds numbers and the other course codes. Real schemas declare their domains; the evaluator approximates that by comparing the types of the values.

The sizes are bounded by the inputs. If R has r tuples and S has s, then R ∪ S has at least the larger of r and s tuples and at most r + s, and R − S has at most r tuples and at least r − s. Union is commutative, but difference is not: R − S and S − R are different relations. Intersection is not one of the six because difference gives it:

R − S holds the tuples of R that are missing from S. Removing those from R leaves the tuples that are in both. E. F. Codd, who proposed the relational model in 1970, listed intersection, join and division as operators of their own when he defined his relational algebra in 1972, and showed in the same paper that division can be written with the others. This lesson and the next two build all three from the core six.

Cartesian product and rename

The Cartesian product R × S pairs every tuple of R with every tuple of S. Its heading is R’s attributes followed by S’s, so the degrees add up, and it has r × s tuples. Student × Course in the run above has 6 × 6 = 36 tuples of 3 + 4 = 7 attributes. A product on its own is rarely the answer to a question, but a product followed by a selection that matches attribute values pairs up tuples that belong together, and that combination is the join of the next lesson.

The product needs distinct attribute names, because a heading cannot name two attributes sid. Student × Enrolled was refused for that reason. Rename fixes it: ρ E (Enrolled) calls the relation E and its attributes E.sid, E.cid and E.grade, and the product Student × ρ E (Enrolled) then has 72 tuples with six distinct attribute names. Rename can also give attributes entirely new names, such as ρ Took(sid, course, mark) (Enrolled). Whenever a relation is compared with itself, rename is the way to have two copies of it in one expression.

Expression trees: one question, two trees

An expression is read as a tree. The leaves are the stored relations, each inner node is an operator applied to the results of the nodes below it, and the root is the answer. Consider “the names of the students enrolled in CS201”. One way to write it applies a single selection to the whole product:

The condition E.cid = ‘CS201’ uses only attributes of the enrolments, so it can be applied to them before the product. The second tree does that and gets the same answer through a much smaller product:

from college import Course, Enrolled, Student
from ra import difference, product, project, rename, select

E = rename(Enrolled, "E")


def node(label, relation):
    """Print one node of an expression tree with the size of its result, and pass the result on."""
    print(f"  {len(relation):>3} tuples  {label}")
    return relation


print("Names of the students enrolled in CS201, tree A (one selection over the whole product):")
a = node("Student × ρ E (Enrolled)", product(Student, E))
a = node("σ sid = E.sid ∧ E.cid = 'CS201'", select(a, lambda t: t["sid"] == t["E.sid"] and t["E.cid"] == "CS201"))
a = node("π name", project(a, "name"))

print("The same question, tree B (the selection on cid moved below the product):")
b = node("σ E.cid = 'CS201' (ρ E (Enrolled))", select(E, lambda t: t["E.cid"] == "CS201"))
b = node("Student × that", product(Student, b))
b = node("σ sid = E.sid", select(b, lambda t: t["sid"] == t["E.sid"]))
b = node("π name", project(b, "name"))
print("  same result:", a.rows == b.rows, sorted(name for (name,) in b.rows))

print()
print("Courses with the most credits, with no aggregate function:")
C1, C2 = rename(Course, "C1"), rename(Course, "C2")
pairs = node("ρ C1 (Course) × ρ C2 (Course)", product(C1, C2))
fewer = node("σ C1.credits < C2.credits", select(pairs, lambda t: t["C1.credits"] < t["C2.credits"]))
beaten = node("π C1.cid  (courses that some course beats)", project(fewer, "C1.cid"))
top = node("π cid (Course) − that", difference(project(Course, "cid"), beaten))
print("  top courses:", sorted(cid for (cid,) in top.rows))

Names of the students enrolled in CS201, tree A (one selection over the whole product):
   72 tuples  Student × ρ E (Enrolled)
    3 tuples  σ sid = E.sid ∧ E.cid = 'CS201'
    3 tuples  π name
The same question, tree B (the selection on cid moved below the product):
    3 tuples  σ E.cid = 'CS201' (ρ E (Enrolled))
   18 tuples  Student × that
    3 tuples  σ sid = E.sid
    3 tuples  π name
  same result: True ['Asha', 'Chitra', 'Esha']

Courses with the most credits, with no aggregate function:
   36 tuples  ρ C1 (Course) × ρ C2 (Course)
   11 tuples  σ C1.credits < C2.credits
    3 tuples  π C1.cid  (courses that some course beats)
    3 tuples  π cid (Course) − that
  top courses: ['CS201', 'CS202', 'CS301']

Tree A builds 72 tuples to keep 3; tree B builds only 18. The rule behind it says that a selection whose condition mentions only one side of a product can move to that side. Query optimisers rewrite trees with rules of this kind, and moving a selection towards the leaves is often called pushing it down. On six students the saving is small. On 60,000 students and 1.2 million enrolments, the product of tree A would hold 72 billion tuples.

The second half of the run answers a question that looks as if it needs an aggregate function: which courses have the most credits? The algebra has no max, but it can say “a course with the most credits is one that no other course beats”. The product of two renamed copies of Course compares every pair, the selection keeps the 11 pairs in which C1 has fewer credits than C2, and the projection lists the 3 courses that some other course beats. Subtracting them from all 6 courses leaves CS201, CS202 and CS301, which have 4 credits each. Rename and difference together express “no other tuple has a larger value”.

To write a tree for a multi-step question, work from the leaves up:

1. Name the relations that hold the facts the question needs, and rename any relation that appears twice.
2. Combine them with products, each followed by a selection that matches the tuples that belong together.
3. Add the conditions of the question as selections, as close to the leaves as their attributes allow.
4. Project the attributes the question asks for, at the root.
5. For “no”, “never” or “only” questions, compute the tuples to exclude and subtract them.

The same questions in SQL

Each operator has a direct counterpart in SQL, and each counterpart has its own rule for duplicate rows:

• σ c (R) is SELECT * FROM r WHERE c, which keeps duplicate rows just as the table holds them.
• π a, b (R) is SELECT DISTINCT a, b FROM r; without DISTINCT, the duplicates stay.
• R ∪ S is ... UNION ..., which removes duplicates; UNION ALL keeps them.
• R − S is ... EXCEPT ..., which removes duplicates.
• R × S is SELECT * FROM r CROSS JOIN s, which keeps every pair.
• ρ E (R) is a table alias, FROM r AS e, or a column alias, column AS new_name.

Duplicates are where SQL and the algebra part ways. An SQL table may hold the same row twice, and a SELECT keeps every row it finds unless the query says DISTINCT: in the words of SQLite’s documentation, with neither ALL nor DISTINCT “the behavior is as if ALL were specified”, and PostgreSQL’s manual also names ALL as the default of SELECT. The set operators go the other way: UNION, INTERSECT and EXCEPT remove duplicate rows from their results. UNION ALL keeps them, and PostgreSQL also has INTERSECT ALL and EXCEPT ALL, which SQLite does not.

CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT, branch TEXT);
INSERT INTO student VALUES
  (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
  (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
CREATE TABLE enrolled (sid INTEGER, cid TEXT, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO enrolled VALUES
  (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
  (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
  (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');

-- π branch (Student): SQL keeps every row unless the query says DISTINCT.
SELECT branch FROM student;
SELECT DISTINCT branch FROM student;

-- UNION removes duplicates like the algebra's ∪; UNION ALL keeps them all.
SELECT
  (SELECT count(*) FROM (SELECT sid FROM enrolled WHERE cid = 'CS201'
                         UNION SELECT sid FROM enrolled WHERE cid = 'MA101')) AS union_rows,
  (SELECT count(*) FROM (SELECT sid FROM enrolled WHERE cid = 'CS201'
                         UNION ALL SELECT sid FROM enrolled WHERE cid = 'MA101')) AS union_all_rows;

┌────────┐
│ branch │
├────────┤
│ CSE    │
│ ECE    │
│ CSE    │
│ ME     │
│ CSE    │
│ ECE    │
└────────┘
┌────────┐
│ branch │
├────────┤
│ CSE    │
│ ECE    │
│ ME     │
└────────┘
┌────────────┬────────────────┐
│ union_rows │ union_all_rows │
├────────────┼────────────────┤
│ 5          │ 8              │
└────────────┴────────────────┘

The program below asks seven questions twice, of the evaluator and of the same three tables in SQLite through Python’s sqlite3 module. It compares the results as sets and counts the rows SQL returned:

import sqlite3

from college import Course, Enrolled, Student
from ra import difference, product, project, select, union

# The same three relations as SQL tables, in an in-memory SQLite database.
db = sqlite3.connect(":memory:")
for name, relation in (("student", Student), ("course", Course), ("enrolled", Enrolled)):
    db.execute(f"CREATE TABLE {name} ({', '.join(relation.heading)})")
    db.executemany(f"INSERT INTO {name} VALUES ({', '.join('?' * len(relation.heading))})", sorted(relation.rows))


def took(cid):
    return project(select(Enrolled, lambda t: t["cid"] == cid), "sid")


cases = [
    ("σ branch = 'CSE' (Student)", select(Student, lambda t: t["branch"] == "CSE"),
     "SELECT * FROM student WHERE branch = 'CSE'"),
    ("π branch (Student)", project(Student, "branch"), "SELECT branch FROM student"),
    ("π grade (Enrolled)", project(Enrolled, "grade"), "SELECT grade FROM enrolled"),
    ("π sid (Enrolled)", project(Enrolled, "sid"), "SELECT sid FROM enrolled"),
    ("CS201 takers ∪ MA101 takers", union(took("CS201"), took("MA101")),
     "SELECT sid FROM enrolled WHERE cid = 'CS201' UNION SELECT sid FROM enrolled WHERE cid = 'MA101'"),
    ("MA101 takers − CS201 takers", difference(took("MA101"), took("CS201")),
     "SELECT sid FROM enrolled WHERE cid = 'MA101' EXCEPT SELECT sid FROM enrolled WHERE cid = 'CS201'"),
    ("Student × Course", product(Student, Course), "SELECT * FROM student CROSS JOIN course"),
]

print(f"{'expression':30} {'algebra':>7} {'SQL rows':>8} {'distinct':>8}  same set")
for label, algebra, sql in cases:
    rows = db.execute(sql).fetchall()
    same = "yes" if set(rows) == algebra.rows else "NO"
    print(f"{label:30} {len(algebra):>7} {len(rows):>8} {len(set(rows)):>8}  {same}")

expression                     algebra SQL rows distinct  same set
σ branch = 'CSE' (Student)           3        3        3  yes
π branch (Student)                   3        6        3  yes
π grade (Enrolled)                   3       12        3  yes
π sid (Enrolled)                     5       12        5  yes
CS201 takers ∪ MA101 takers          5        5        5  yes
MA101 takers − CS201 takers          2        2        2  yes
Student × Course                    36       36       36  yes

Every pair holds the same set of tuples, so the algebra and SQL agree on what the answer contains. They disagree on how many rows it has: π grade (Enrolled) is 3 tuples in the algebra, while SELECT grade FROM enrolled returns all 12 rows, one per enrolment. Whenever a query result is counted or summed, decide whether duplicates should count, and write DISTINCT, or leave it out, on purpose.

Exercise

"""Write each query with the six operators below, and return the Relation it gives.

The operators are the ones of the lesson's ra.py: in a condition, t maps attribute names to values.
Keep the operators as they are: the sample tests run your queries on other data too.
Student(sid, name, branch), Course(cid, title, dept, credits), Enrolled(sid, cid, grade)
"""


class Relation:
    def __init__(self, heading, rows):
        self.heading = tuple(heading)
        self.rows = frozenset(tuple(row) for row in rows)


def select(r, condition):
    return Relation(r.heading, [row for row in r.rows if condition(dict(zip(r.heading, row)))])


def project(r, *names):
    positions = [r.heading.index(n) for n in names]
    return Relation(names, [tuple(row[p] for p in positions) for row in r.rows])


def union(r, s):
    return Relation(r.heading, r.rows | s.rows)


def difference(r, s):
    return Relation(r.heading, r.rows - s.rows)


def product(r, s):
    if set(r.heading) & set(s.heading):
        raise ValueError("both relations have an attribute of the same name: rename one side first")
    return Relation(r.heading + s.heading, [a + b for a in r.rows for b in s.rows])


def rename(r, prefix=None, **new_names):
    heading = [new_names.get(h, h) for h in r.heading]
    if prefix:
        heading = [f"{prefix}.{h}" for h in heading]
    return Relation(heading, r.rows)


def ece_names(student, course, enrolled):
    """1. The names of the students of the ECE branch (one attribute: name)."""
    return Relation(("name",), [])


def courses_nobody_takes(student, course, enrolled):
    """2. The cid of every course in which no student is enrolled (one attribute: cid)."""
    return Relation(("cid",), [])


def took_cs201_and_ma101(student, course, enrolled):
    """3. The sid of every student enrolled in both CS201 and MA101 (one attribute: sid)."""
    return Relation(("sid",), [])


def a_grade_in_cse_course(student, course, enrolled):
    """4. The names of the students with grade A in at least one course of the CSE department."""
    return Relation(("name",), [])

from queries import Relation, a_grade_in_cse_course, courses_nobody_takes, ece_names, took_cs201_and_ma101


def college():
    """The sample relations of the lesson."""
    student = Relation(("sid", "name", "branch"), [
        (1, "Asha", "CSE"), (2, "Bilal", "ECE"), (3, "Chitra", "CSE"),
        (4, "Dev", "ME"), (5, "Esha", "CSE"), (6, "Farhan", "ECE"),
    ])
    course = Relation(("cid", "title", "dept", "credits"), [
        ("CS201", "Databases", "CSE", 4), ("CS202", "Operating Systems", "CSE", 4),
        ("CS301", "Compilers", "CSE", 4), ("MA101", "Discrete Mathematics", "MATH", 3),
        ("EC210", "Signals and Systems", "ECE", 3), ("HS101", "Technical Writing", "HSS", 2),
    ])
    enrolled = Relation(("sid", "cid", "grade"), [
        (1, "CS201", "A"), (1, "CS202", "B"), (1, "MA101", "A"), (2, "EC210", "A"),
        (2, "MA101", "B"), (3, "CS201", "B"), (3, "MA101", "A"), (4, "MA101", "C"),
        (5, "CS201", "A"), (5, "CS202", "A"), (5, "MA101", "B"), (5, "HS101", "A"),
    ])
    return student, course, enrolled


def other_college():
    """Different data: two students share a name, one course has no enrolments, and Lata took only CS201."""
    student = Relation(("sid", "name", "branch"), [
        (10, "Ravi", "ECE"), (11, "Ravi", "ECE"), (12, "Meena", "CSE"), (13, "Kiran", "ME"),
        (14, "Lata", "CSE"),
    ])
    course = Relation(("cid", "title", "dept", "credits"), [
        ("CS201", "Databases", "CSE", 4), ("CS250", "Computer Networks", "CSE", 4),
        ("MA101", "Discrete Mathematics", "MATH", 3), ("ME110", "Mechanics", "ME", 3),
        ("HS102", "Ethics", "HSS", 2),
    ])
    enrolled = Relation(("sid", "cid", "grade"), [
        (10, "MA101", "A"), (11, "CS250", "A"), (12, "CS201", "A"), (12, "MA101", "B"),
        (13, "CS201", "B"), (13, "MA101", "A"), (13, "ME110", "A"), (14, "CS201", "B"),
    ])
    return student, course, enrolled


def test_ece_names():
    """1 gives the names of ECE students, each name once"""
    result = ece_names(*college())
    assert result.heading == ("name",)
    assert result.rows == {("Bilal",), ("Farhan",)}
    assert ece_names(*other_college()).rows == {("Ravi",)}


def test_courses_nobody_takes():
    """2 gives the courses without a single enrolment"""
    result = courses_nobody_takes(*college())
    assert result.heading == ("cid",)
    assert result.rows == {("CS301",)}
    assert courses_nobody_takes(*other_college()).rows == {("HS102",)}


def test_took_cs201_and_ma101():
    """3 gives the students enrolled in both courses"""
    result = took_cs201_and_ma101(*college())
    assert result.heading == ("sid",)
    assert result.rows == {(1,), (3,), (5,)}
    assert took_cs201_and_ma101(*other_college()).rows == {(12,), (13,)}


def test_a_grade_in_cse_course():
    """4 gives the students with an A in a CSE course, not in any course"""
    result = a_grade_in_cse_course(*college())
    assert result.heading == ("name",)
    assert result.rows == {("Asha",), ("Esha",)}
    assert a_grade_in_cse_course(*other_college()).rows == {("Ravi",), ("Meena",)}


def test_without_enrolments():
    """all four work when nobody is enrolled yet"""
    student, course, _ = college()
    nobody = Relation(("sid", "cid", "grade"), [])
    assert courses_nobody_takes(student, course, nobody).rows == {(c,) for (c, _, _, _) in course.rows}
    assert took_cs201_and_ma101(student, course, nobody).rows == set()
    assert a_grade_in_cse_course(student, course, nobody).rows == set()
    assert ece_names(student, course, nobody).rows == {("Bilal",), ("Farhan",)}

Check yourself

Interview questions

Why can π branch (Student) return fewer tuples than SELECT branch FROM student? In relational algebra a relation is a set, so when the projection drops sid and name, students of the same branch turn into equal tuples, and the set keeps one of each: six students in three branches give three tuples. SQL works with bags, so a SELECT keeps one row per input row unless the query says DISTINCT. The two agree whenever the projected attributes include a key, because then no two rows become equal.

Key takeaways

• Six operators form the core of relational algebra: σ filters tuples, π keeps attributes, ∪ and − combine union-compatible relations, × pairs every tuple with every other, and ρ renames.
• Every operator returns a relation, so expressions nest into trees that are evaluated from the leaves up.
• A relation is a set: projection merges tuples that become equal, unless the attributes it keeps include a key.
• Union and difference need the same degree and matching domains; difference is not commutative, and R ∩ S = R − (R − S).
• A product of r and s tuples has r × s tuples, and a relation compared with itself needs rename.
• SQL keeps duplicate rows unless a query says DISTINCT, while UNION, INTERSECT and EXCEPT remove them; UNION ALL keeps them.