Relational Algebra

Relational algebra is a set of operators that take relations as input and produce a relation as output. It is the mathematical basis of SQL: a DBMS turns every SQL query into a relational algebra expression before running it. Because each result is again a relation, operators can be nested freely.

We use these two relations throughout:

Student

Takes

The basic operators

These six are complete: every other operator can be written using them. Union, intersection and difference need union-compatible relations: the same number of attributes, with matching domains.

Examples:

• σ_{dept = 'CSE'}(Student) gives Asha and Meena.
• π_course(Takes) gives {DBMS, OS}: 2 tuples, not 5, because projection removes duplicates.
• π_roll(Student) − π_roll(σ_{course = 'OS'}(Takes)) gives {2}: the student who does not take OS.

Derived operators

Result sizes

For R with m tuples and S with n tuples:

Outer joins

A natural join drops tuples that have no match. Outer joins keep them, filling the missing side with NULL:

• Left outer join (⟕): all tuples of the left relation.
• Right outer join (⟖): all tuples of the right relation.
• Full outer join (⟗): all tuples of both.

Division

R(A, B) ÷ S(B) gives the A values that are paired in R with every B value of S. It answers "for all" questions: which students take all courses?

π_{roll, course}(Takes) ÷ π_course(Takes) = {1, 3}, because Asha and Meena take both DBMS and OS, while Ravi takes only DBMS.

Using basic operators: R ÷ S = π_A(R) − π_A((π_A(R) × S) − R). The inner part, (π_A(R) × S) − R, lists the (A, B) pairs that are missing; any A with a missing pair is removed.

Relational algebra in Python

Here the operators are written as small Python functions on relations stored as sets of tuples, so you can see exactly what each one computes:

student = {"attrs": ("roll", "name", "dept"),
           "rows": {(1, "Asha", "CSE"), (2, "Ravi", "ECE"), (3, "Meena", "CSE")}}
takes = {"attrs": ("roll", "course"),
         "rows": {(1, "DBMS"), (1, "OS"), (2, "DBMS"), (3, "DBMS"), (3, "OS")}}

def select(r, pred):
    return {"attrs": r["attrs"],
            "rows": {t for t in r["rows"] if pred(dict(zip(r["attrs"], t)))}}

def project(r, attrs):
    idx = [r["attrs"].index(a) for a in attrs]
    return {"attrs": tuple(attrs), "rows": {tuple(t[i] for i in idx) for t in r["rows"]}}

def natural_join(r, s):
    common = [a for a in r["attrs"] if a in s["attrs"]]
    extra = [a for a in s["attrs"] if a not in common]
    rows = set()
    for t in r["rows"]:
        for u in s["rows"]:
            d, e = dict(zip(r["attrs"], t)), dict(zip(s["attrs"], u))
            if all(d[a] == e[a] for a in common):
                rows.add(t + tuple(e[a] for a in extra))
    return {"attrs": r["attrs"] + tuple(extra), "rows": rows}

def divide(r, s):
    a_attrs = [a for a in r["attrs"] if a not in s["attrs"]]
    candidates = project(r, a_attrs)["rows"]
    pairs = project(r, a_attrs + list(s["attrs"]))["rows"]
    return {x for x in candidates if all(x + y in pairs for y in s["rows"])}

print(sorted(select(student, lambda t: t["dept"] == "CSE")["rows"]))
print(sorted(project(takes, ["course"])["rows"]))
print(len(natural_join(student, takes)["rows"]), "tuples in Student ⋈ Takes")
print(sorted(divide(takes, project(takes, ["course"]))))

[(1, 'Asha', 'CSE'), (3, 'Meena', 'CSE')]
[('DBMS',), ('OS',)]
5 tuples in Student ⋈ Takes
[(1,), (3,)]

The natural join has 5 tuples, one per Takes tuple, because roll in Takes refers to the key of Student. The division gives rolls 1 and 3.

The same queries in SQL

SQL keeps duplicates by default, so π corresponds to SELECT DISTINCT. SQL has no division operator; "for all" is written with NOT EXISTS or by counting, as in the last query below.

CREATE TABLE student (roll INTEGER PRIMARY KEY, name TEXT, dept TEXT);
CREATE TABLE takes (roll INTEGER, course TEXT);
INSERT INTO student VALUES (1, 'Asha', 'CSE'), (2, 'Ravi', 'ECE'), (3, 'Meena', 'CSE');
INSERT INTO takes VALUES (1, 'DBMS'), (1, 'OS'), (2, 'DBMS'), (3, 'DBMS'), (3, 'OS');
SELECT DISTINCT course FROM takes;
SELECT roll FROM student
EXCEPT
SELECT roll FROM takes WHERE course = 'OS';
SELECT roll FROM takes GROUP BY roll
HAVING COUNT(DISTINCT course) = (SELECT COUNT(DISTINCT course) FROM takes);

course
------
DBMS
OS

roll
----
2

roll
----
1
3

Practice questions

CREATE TABLE emp (id INTEGER, dept INTEGER);
CREATE TABLE dept (dept INTEGER, name TEXT);
INSERT INTO emp VALUES (1, 10), (2, 20), (3, 10), (4, 30);
INSERT INTO dept VALUES (10, 'CSE'), (20, 'ECE'), (40, 'ME');
SELECT COUNT(*) FROM emp FULL OUTER JOIN dept ON emp.dept = dept.dept;