Database Management Systems (DBMS) Module 4 – Relational algebra and relational calculus
Joins in relational algebra and join sizes
Theta, natural, outer, semi and anti joins built from the core operators, the size bounds that keys give, and every join checked in SQL.
What you will learn
- Express theta joins, equi-joins, natural joins and the three outer joins in relational algebra
- Use semijoin and antijoin for 'exists' and 'does not exist' questions
- Compute minimum and maximum result sizes of joins from keys and foreign keys
- Write the SQL equivalent of each join and predict its output
Before you start
What you’ll learn · Before you start
What you will learn
- Express theta joins, equi-joins, natural joins and the three outer joins in relational algebra
- Use semijoin and antijoin for 'exists' and 'does not exist' questions
- Compute minimum and maximum result sizes of joins from keys and foreign keys
- Write the SQL equivalent of each join and predict its output
Before you start
On this page
A join combines two relations by pairing the tuples that belong together, and in relational algebra it is a Cartesian product followed by a selection. The theta join R ⋈θ S keeps the pairs of the product that satisfy a condition θ, an equi-join is a theta join whose condition only tests equality, and the natural join R ⋈ S tests equality on every attribute the two relations share and keeps one copy of each. Three outer joins (left, right and full) also keep the tuples that found no partner, padded with NULL. The semijoin R ⋉ S keeps the tuples of R that have a partner in S, and the antijoin R ▷ S keeps those that have none: they answer “exists” and “does not exist” questions. Keys and foreign keys fix how large a join can be, which is what exam questions and query planners both need. This lesson builds each join from the core operators, checks the size rules on every small instance, and runs every join in SQL.
The join family at a glance
Every join here is shorthand for operators of the previous lesson, and the chain below shows which:
Every join is built from the core operators
Text description of the diagram
The diagram is a chain of boxes from top to bottom, with one branch.
- R × S, every pair of tuples.
- Below it, the θ-join R ⋈θ S, which is σ θ (R × S).
- From the θ-join, one arrow leads to the equi-join, a θ-join whose condition uses only =, and another to the outer joins ⟕, ⟖ and ⟗: the join plus the tuples without a partner, padded with NULL.
- Below the equi-join, the natural join R ⋈ S: equality on every common attribute name, with one copy of each.
- Below the natural join, the semijoin R ⋉ S, which keeps the attributes of R: π attributes of R (R ⋈ S).
- At the bottom, the antijoin R ▷ S, which is R − (R ⋉ S).
The examples use the sample college again: Student(sid, name, branch), Course(cid, title, dept, credits) and Enrolled(sid, cid, grade), with sid the key of Student, cid the key of Course, and (sid, cid) the key of Enrolled, whose sid and cid are foreign keys to the other two. Farhan has no enrolment, nobody takes CS301, Dev studies ME, and no department offers ME courses.
From product to theta join
The theta join of R and S on a condition θ is the selection of θ over their product:
θ may compare any attribute of R with any attribute of S using =, ≠, <, ≤, > or ≥. An equi-join
uses only =, which is by far the most common case: a foreign key equal to the key it refers to. Pairing every
student with the courses offered by the department of the same name is an equi-join on branch = dept, and it has 11
tuples: 3 CSE students with 3 CSE courses, 2 ECE students with 1 ECE course, and Dev with nothing, because no
department offers ME courses.
The definition says what the result contains, not how to compute it. Building the product first would cost |R| × |S| pairs, and database engines avoid that with join algorithms, such as hash joins and sort-merge joins, which find the matching pairs directly. A later module of this track covers how they work.
The natural join
The natural join R ⋈ S needs no condition: it equates every attribute name that R and S have in common, and keeps one copy of each. For Student(sid, name, branch) and Enrolled(sid, cid, grade), whose only common name is sid, the definition expands to a rename, a product, a selection and a projection:
Two special cases follow from the definition and are favourites of exam questions. With no common attribute, there is no equality to test, so every pair qualifies and the natural join is the product. With all attributes in common, a pair qualifies only when the two tuples are equal, so the natural join is the intersection. The run shows both: 36 tuples for Student ⋈ Course, which share no name, and 3 for two one-attribute relations of student ids.
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (
sid INTEGER NOT NULL REFERENCES student (sid),
cid TEXT NOT NULL REFERENCES course (cid),
grade TEXT,
PRIMARY KEY (sid, cid)
);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
-- A θ-join on branch = dept, and the three outer joins with the same condition.
SELECT 'inner' AS kind, count(*) AS rows_out FROM student s JOIN course c ON s.branch = c.dept
UNION ALL SELECT 'left', count(*) FROM student s LEFT JOIN course c ON s.branch = c.dept
UNION ALL SELECT 'right', count(*) FROM student s RIGHT JOIN course c ON s.branch = c.dept
UNION ALL SELECT 'full', count(*) FROM student s FULL JOIN course c ON s.branch = c.dept;
-- The rows only the full outer join adds: tuples without a partner, padded with NULL.
SELECT s.name, s.branch, c.cid, c.dept
FROM student s FULL JOIN course c ON s.branch = c.dept
WHERE s.sid IS NULL OR c.cid IS NULL;
-- Natural joins: on sid (the only common name), on no common name, and on every name.
SELECT
(SELECT count(*) FROM student NATURAL JOIN enrolled) AS on_sid,
(SELECT count(*) FROM student NATURAL JOIN course) AS no_common_name,
(SELECT count(*) FROM (SELECT sid FROM enrolled WHERE cid = 'CS201')
NATURAL JOIN (SELECT sid FROM enrolled WHERE cid = 'MA101')) AS all_names_common;Output
┌───────┬──────────┐ │ kind │ rows_out │ ├───────┼──────────┤ │ inner │ 11 │ │ left │ 12 │ │ right │ 13 │ │ full │ 14 │ └───────┴──────────┘ ┌──────┬────────┬───────┬──────┐ │ name │ branch │ cid │ dept │ ├──────┼────────┼───────┼──────┤ │ Dev │ ME │ │ │ │ │ │ MA101 │ MATH │ │ │ │ HS101 │ HSS │ └──────┴────────┴───────┴──────┘ ┌────────┬────────────────┬──────────────────┐ │ on_sid │ no_common_name │ all_names_common │ ├────────┼────────────────┼──────────────────┤ │ 12 │ 36 │ 3 │ └────────┴────────────────┴──────────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < joins.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
SQL has NATURAL JOIN too. SQLite’s documentation explains it as an implicit USING clause listing every column
name that the two inputs share, so the join condition is decided by the column names at the moment the query runs.
That is convenient and fragile. PostgreSQL’s manual warns that a schema
change that adds a matching column name to either side “will cause the join to combine that new column as well”.
Here two audit columns of the same name turn a 12-row join into an empty one:
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
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');
SELECT count(*) AS before_change FROM student NATURAL JOIN enrolled;
-- Later, a change adds an audit column of the same name to both tables.
ALTER TABLE student ADD COLUMN updated_by TEXT NOT NULL DEFAULT 'import';
ALTER TABLE enrolled ADD COLUMN updated_by TEXT NOT NULL DEFAULT 'portal';
SELECT
(SELECT count(*) FROM student NATURAL JOIN enrolled) AS natural_after,
(SELECT count(*) FROM student JOIN enrolled USING (sid)) AS using_after;Output
┌───────────────┐ │ before_change │ ├───────────────┤ │ 12 │ └───────────────┘ ┌───────────────┬─────────────┐ │ natural_after │ using_after │ ├───────────────┼─────────────┤ │ 0 │ 12 │ └───────────────┴─────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < natural_trap.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
JOIN ... USING (sid) names the join column, so it kept its 12 rows. In application code, prefer USING or an ON
condition, which keep working when somebody adds a column.
Outer joins
An inner join drops every tuple that has no partner. The outer joins keep them:
- Left outer join R ⟕ S: every tuple of R appears, joined with its partners or, if it has none, once with NULL in the attributes of S.
- Right outer join R ⟖ S: the mirror image, every tuple of S appears.
- Full outer join R ⟗ S: the tuples without a partner on both sides appear, each padded with NULL.
NULL is not a value of any domain of the basic algebra, so the outer joins are extensions of it. In the algebra, the left outer join is the join plus the tuples of R that did not take part in it, extended with nulls:
Here π R means the projection on the attributes of R, so D holds the tuples of R that found no partner, and N is a relation with a single tuple of nulls, one for each attribute of S that R does not have. On branch = dept, the run above found 11 inner rows, 12 left (Dev added), 13 right (MA101 and HS101 added, because no branch is called MATH or HSS) and 14 full, and it listed the three padded rows, in which the output shows each NULL as an empty cell. SQLite has supported RIGHT and FULL OUTER JOIN since version 3.39.0, so the browser’s SQLite 3.49.1 runs all four.
The place of a condition matters in an outer join. PostgreSQL’s manual explains the rule: a condition in ON takes effect before the join pads the rows that found no partner, and a condition in WHERE takes effect after it, which changes nothing for an inner join and a great deal for an outer one. For “every student with their CS201 grade”, the condition on cid belongs in ON:
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (
sid INTEGER NOT NULL REFERENCES student (sid),
cid TEXT NOT NULL REFERENCES course (cid),
grade TEXT,
PRIMARY KEY (sid, cid)
);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
-- Every student with their CS201 grade: the condition on cid in ON keeps all six students.
SELECT s.name, e.grade AS cs201_grade
FROM student s LEFT JOIN enrolled e ON e.sid = s.sid AND e.cid = 'CS201'
ORDER BY s.sid;
-- The same condition in WHERE runs after the join and removes the rows padded with NULL.
SELECT s.name, e.grade AS cs201_grade
FROM student s LEFT JOIN enrolled e ON e.sid = s.sid
WHERE e.cid = 'CS201'
ORDER BY s.sid;Output
┌────────┬─────────────┐ │ name │ cs201_grade │ ├────────┼─────────────┤ │ Asha │ A │ │ Bilal │ │ │ Chitra │ B │ │ Dev │ │ │ Esha │ A │ │ Farhan │ │ └────────┴─────────────┘ ┌────────┬─────────────┐ │ name │ cs201_grade │ ├────────┼─────────────┤ │ Asha │ A │ │ Chitra │ B │ │ Esha │ A │ └────────┴─────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < on_vs_where.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
In ON, the condition limits which enrolments may join, and the students without a CS201 enrolment are still padded and kept: 6 rows. In WHERE, it runs on the joined rows, and e.cid = ‘CS201’ is not true when e.cid is NULL, so the padded rows disappear: 3 rows, the same as an inner join. With inner joins, the two placements give the same result.
Semijoin and antijoin
Some questions ask only whether a partner exists. “Which students are enrolled in something?” wants each such student once, however many courses they take. The semijoin keeps the tuples of R that have at least one partner in S, with R’s attributes only, and the antijoin keeps those with none:
A semijoin never has more tuples than R, which a join can easily have. In SQL, EXISTS and NOT EXISTS write them directly, and PostgreSQL’s manual notes that an EXISTS test “produces at most one output row for each” row of the outer table, even when several rows match:
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (
sid INTEGER NOT NULL REFERENCES student (sid),
cid TEXT NOT NULL REFERENCES course (cid),
grade TEXT,
PRIMARY KEY (sid, cid)
);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
-- A join repeats a student once per enrolment; a semijoin (EXISTS) keeps each student once.
SELECT
(SELECT count(*) FROM student s JOIN enrolled e ON e.sid = s.sid) AS join_rows,
(SELECT count(*) FROM student s WHERE EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid)) AS semijoin_rows;
-- An antijoin (NOT EXISTS): the students with no enrolment.
SELECT name FROM student s
WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid);
-- A waiting list whose form once saved an empty student id.
CREATE TABLE waitlist (sid INTEGER, cid TEXT);
INSERT INTO waitlist VALUES (2, 'CS301'), (NULL, 'CS301');
-- Students not on the waiting list, written two ways.
SELECT
(SELECT count(*) FROM student s WHERE NOT EXISTS (SELECT 1 FROM waitlist w WHERE w.sid = s.sid)) AS not_exists_rows,
(SELECT count(*) FROM student WHERE sid NOT IN (SELECT sid FROM waitlist)) AS not_in_rows;Output
┌───────────┬───────────────┐ │ join_rows │ semijoin_rows │ ├───────────┼───────────────┤ │ 12 │ 5 │ └───────────┴───────────────┘ ┌────────┐ │ name │ ├────────┤ │ Farhan │ └────────┘ ┌─────────────────┬─────────────┐ │ not_exists_rows │ not_in_rows │ ├─────────────────┼─────────────┤ │ 5 │ 0 │ └─────────────────┴─────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < semi_anti.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
The join repeated a student once per enrolment, 12 rows, while the semijoin kept each of the 5 enrolled students once. The antijoin found Farhan. The last two counts are the trap: on a waiting list that contains a NULL student id, NOT EXISTS finds the 5 students who are not on the list, and NOT IN finds none. For a student with sid 4, NOT IN must establish 4 ≠ 2 and 4 ≠ NULL; the second comparison is unknown, so the whole condition is unknown, and WHERE keeps a row only when its condition is true. PostgreSQL’s manual states the same rule for NOT IN: with no equal value in the list and at least one null in it, the result is null instead of true. Write antijoins with NOT EXISTS, or make sure the column of the subquery cannot be NULL.
How big can a join be?
Exam questions, and the planners that choose join orders, need the size of a join before it is computed. For R(a, b) with r tuples and S(b, c) with s tuples, joined on b, the bounds depend on what the keys say:
| What is known | Size of R ⋈ S, and why |
|---|---|
| Nothing | 0 to r × s: no pair may match, or every pair may share one b |
| b is a key of S | 0 to r: each tuple of R finds at most one partner |
| b is a key of S, and R.b is a non-null foreign key to it | Exactly r: each tuple of R finds exactly one partner |
| b is a key of both R and S | 0 to min(r, s): each b value occurs at most once on each side |
| No common attribute (natural join) | Exactly r × s: it is the product |
The outer joins add the tuples without a partner, so R ⟕ S has between r and r × s tuples (when s is at least 1), and R ⟗ S between max(r, s) and the larger of r × s and r + s. The last bound surprises people: when no b matches, the full outer join has r + s tuples, which is more than r × s when one side has a single tuple.
Instead of trusting the table, the program below checks it. It builds every R with r tuples and every S with s tuples over small domains, joins each pair, and records the smallest and largest result under each condition:
"""Check the join-size bounds by trying every small instance of R(a, b) and S(b, c)."""
from itertools import combinations, product
A, B, C = (1, 2, 3), ("v", "w", "x", "y", "z"), (1, 2, 3)
def sizes(R, S):
"""The sizes of R ⋈ S, R ⟕ S and R ⟗ S, joining on the common attribute b."""
inner = sum(1 for (_, b) in R for (b2, _) in S if b == b2)
lonely_r = sum(1 for (_, b) in R if all(b != b2 for (b2, _) in S))
lonely_s = sum(1 for (b, _) in S if all(b != b2 for (_, b2) in R))
return inner, inner + lonely_r, inner + lonely_r + lonely_s
def distinct_b(rel, position):
values = [t[position] for t in rel]
return len(values) == len(set(values))
ROWS = [
# label, bound as text, bound as numbers (r, s), which size, which instances count
("R ⋈ S, no constraint", "0 to r·s", lambda r, s: (0, r * s), 0, lambda R, S: True),
("R ⋈ S, b a key of S", "0 to r", lambda r, s: (0, r), 0, lambda R, S: distinct_b(S, 0)),
("R ⋈ S, b a key of S, R.b references S", "exactly r", lambda r, s: (r, r), 0,
lambda R, S: distinct_b(S, 0) and {b for (_, b) in R} <= {b for (b, _) in S}),
("R ⋈ S, b a key of R and of S", "0 to min(r, s)", lambda r, s: (0, min(r, s)), 0,
lambda R, S: distinct_b(R, 1) and distinct_b(S, 0)),
("R ⟕ S, no constraint", "r to r·s", lambda r, s: (r, r * s), 1, lambda R, S: True),
("R ⟗ S, no constraint", "max(r, s) to max(r·s, r + s)", lambda r, s: (max(r, s), max(r * s, r + s)), 2,
lambda R, S: True),
]
SHAPES = [(3, 2), (2, 3), (1, 2)]
observed = {} # (row, shape) -> [min, max]
pairs = 0
for r, s in SHAPES:
for R in combinations(list(product(A, B)), r):
for S in combinations(list(product(B, C)), s):
pairs += 1
got = sizes(R, S)
for i, (_, _, _, which, counts) in enumerate(ROWS):
if counts(R, S):
lo_hi = observed.setdefault((i, (r, s)), [got[which], got[which]])
lo_hi[0], lo_hi[1] = min(lo_hi[0], got[which]), max(lo_hi[1], got[which])
print(f"{pairs:,} pairs of relations tried; each cell is the smallest to the largest size seen")
print((f"{'':39} {'bound':29}" + "".join(f"{f'r={r} s={s}':11}" for r, s in SHAPES)).rstrip())
all_match = True
for i, (label, text, bound, _, _) in enumerate(ROWS):
cells = ""
for r, s in SHAPES:
lo, hi = observed[(i, (r, s))]
all_match &= (lo, hi) == bound(r, s)
cells += f"{f'{lo} to {hi}':11}"
print(f"{label:39} {text:29}{cells}".rstrip())
print("every range seen equals its bound:", all_match)Output
97,125 pairs of relations tried; each cell is the smallest to the largest size seen
bound r=3 s=2 r=2 s=3 r=1 s=2
R ⋈ S, no constraint 0 to r·s 0 to 6 0 to 6 0 to 2
R ⋈ S, b a key of S 0 to r 0 to 3 0 to 2 0 to 1
R ⋈ S, b a key of S, R.b references S exactly r 3 to 3 2 to 2 1 to 1
R ⋈ S, b a key of R and of S 0 to min(r, s) 0 to 2 0 to 2 0 to 1
R ⟕ S, no constraint r to r·s 3 to 6 2 to 6 1 to 2
R ⟗ S, no constraint max(r, s) to max(r·s, r + s) 3 to 6 3 to 6 2 to 3
every range seen equals its bound: True
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 join_sizes.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each range that the 97,125 pairs of relations produced is exactly the bound, including the case r = 1, s = 2, where the full outer join reaches r + s = 3 while r × s is 2. On the sample college, the foreign-key row of the table predicts that Enrolled ⋈ Student has exactly 12 tuples, one per enrolment, and that adding Course keeps it at 12, because cid is the key of Course and every enrolment’s cid refers to it. The left outer join of Student with Enrolled should have 13: the 12 enrolments, and Farhan padded with NULL.
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (
sid INTEGER NOT NULL REFERENCES student (sid),
cid TEXT NOT NULL REFERENCES course (cid),
grade TEXT,
PRIMARY KEY (sid, cid)
);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
-- The sizes the key and foreign-key rules predict, on the sample college.
SELECT
(SELECT count(*) FROM enrolled) AS enrolments,
(SELECT count(*) FROM enrolled JOIN student USING (sid)) AS with_student,
(SELECT count(*) FROM enrolled JOIN student USING (sid) JOIN course USING (cid)) AS with_course_too,
(SELECT count(*) FROM student LEFT JOIN enrolled USING (sid)) AS student_left_join;Output
┌────────────┬──────────────┬─────────────────┬───────────────────┐ │ enrolments │ with_student │ with_course_too │ student_left_join │ ├────────────┼──────────────┼─────────────────┼───────────────────┤ │ 12 │ 12 │ 12 │ 13 │ └────────────┴──────────────┴─────────────────┴───────────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < sample_sizes.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
Read the other way, the table is also a test: a join of R with S that returns more than |R| tuples proves that the join attribute is not a key of S.
Join sizes in GATE CS
The relational model topics in Section 9 of the GATE 2027 Computer Science syllabus include relational algebra, and the size of a join is a typical numerical answer: two relations, their sizes, a key or a foreign key, and the number of tuples to find. Find the attribute the join tests, check whether it is a key on either side and whether a non-null foreign key guarantees a partner, and read the bound from the table above.
Exercises
Exercise · Easy · SQL
Every course with its A-grade students
The tables are the lesson's: student(sid, name, branch), course(cid, title, dept, credits) and enrolled(sid, cid, grade).
Write one query that returns two columns, cid and name: one row for every student who got grade A in a course, with that course's cid. Every course must appear, also the courses in which nobody got an A: for those, return one row with the cid and NULL as the name.
The order of the rows does not matter. The sample tests include a course whose students all got B, and a course with no enrolments at all.
Starter code · a_grades.sql
-- Every course, with the name of each student who got an A in it (NULL when nobody did).
SELECT c.cid, s.name
FROM course c
JOIN enrolled e ON e.cid = c.cid
JOIN student s ON s.sid = e.sid
WHERE e.grade = 'A';The sample tests · tests.yaml
# Sample tests: each one builds the three tables, runs your query on them and compares the rows it returns (in any
# order).
tests:
- name: lists each A with its course, and a course without any A once, with NULL
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
expected:
columns: [cid, name]
rows:
- [CS201, Asha]
- [CS201, Esha]
- [CS202, Esha]
- [CS301, null]
- [MA101, Asha]
- [MA101, Chitra]
- [EC210, Bilal]
- [HS101, Esha]
- name: keeps a course whose students all got B, and a course nobody took
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO student VALUES (10, 'Ravi', 'ECE'), (11, 'Meena', 'CSE'), (12, 'Kiran', 'ME');
INSERT INTO course VALUES
('CS250', 'Computer Networks', 'CSE', 4), ('ME110', 'Mechanics', 'ME', 3), ('HS102', 'Ethics', 'HSS', 2);
INSERT INTO enrolled VALUES (10, 'CS250', 'B'), (11, 'CS250', 'B'), (12, 'ME110', 'A'), (11, 'ME110', 'A');
expected:
columns: [cid, name]
rows:
- [CS250, null]
- [ME110, Kiran]
- [ME110, Meena]
- [HS102, null]
- name: does not repeat a course that has both A and other grades
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO student VALUES (20, 'Tara', 'CSE'), (21, 'Imran', 'CSE'), (22, 'Joseph', 'ECE');
INSERT INTO course VALUES ('CS201', 'Databases', 'CSE', 4);
INSERT INTO enrolled VALUES (20, 'CS201', 'A'), (21, 'CS201', 'C'), (22, 'CS201', NULL);
expected:
columns: [cid, name]
rows:
- [CS201, Tara]A hint
Start from course and keep every one of its rows with LEFT JOIN. The condition on the grade decides which enrolments may join: written in the WHERE clause, it runs after the join and throws away the padded rows again.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (sql.js): nothing is sent to mysmartcopilot.com. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Exercise · Medium · SQL
Students with no CSE course, even with a broken row
The tables are the lesson's: student(sid, name, branch), course(cid, title, dept, credits) and enrolled(sid, cid, grade), but enrolled was loaded from an old spreadsheet and has no constraints: some of its rows may have an empty (NULL) sid.
Write one query that returns a single column, name: the names of the students who are not enrolled in any course of the CSE department. Students with no enrolments at all count too. Return each student once; the order does not matter.
The sample tests include an enrolment with a NULL student id, which must not change the answer.
Starter code · no_cse_course.sql
-- The students who are not enrolled in any CSE course.
SELECT name
FROM student
WHERE sid NOT IN (
SELECT e.sid FROM enrolled e JOIN course c ON c.cid = e.cid WHERE c.dept = 'CSE'
);The sample tests · tests.yaml
# Sample tests: each one builds the three tables, runs your query on them and compares the rows it returns (in any
# order).
tests:
- name: finds the students without a CSE course in the lesson's data
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER, cid TEXT, grade TEXT);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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');
expected:
columns: [name]
rows:
- [Bilal]
- [Dev]
- [Farhan]
- name: gives the same answer when one enrolment has a NULL student id
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER, cid TEXT, grade TEXT);
INSERT INTO student VALUES
(1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
(4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
('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);
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'),
(NULL, 'CS301', 'B');
expected:
columns: [name]
rows:
- [Bilal]
- [Dev]
- [Farhan]
- name: counts students with no enrolment, and lists a student once despite two other courses
setup: |
CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER, cid TEXT, grade TEXT);
INSERT INTO student VALUES (10, 'Ravi', 'ECE'), (11, 'Meena', 'CSE'), (12, 'Kiran', 'ME'), (13, 'Lata', 'ME');
INSERT INTO course VALUES
('CS250', 'Computer Networks', 'CSE', 4), ('ME110', 'Mechanics', 'ME', 3), ('HS102', 'Ethics', 'HSS', 2);
INSERT INTO enrolled VALUES (10, 'ME110', 'A'), (10, 'HS102', 'B'), (11, 'CS250', 'A'), (12, 'CS250', 'C');
expected:
columns: [name]
rows:
- [Ravi]
- [Lata]A hint
This is an antijoin: the students for whom no matching enrolment in a CSE course exists. Run the starter on the sample tests and look at the test with the broken row: NOT IN meets a NULL in its list, and then no comparison is ever true. NOT EXISTS asks only whether a matching row exists.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (sql.js): nothing is sent to mysmartcopilot.com. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
Check yourself
6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
What does a natural join return when the two relations share no attribute names, and when they share all of them? With no common attribute there is nothing to compare, so every pair of tuples qualifies and the natural join is the Cartesian product, with |R| × |S| tuples. When every attribute is common, two tuples join only if they agree on all of them, that is, if they are the same tuple, so the natural join is the intersection R ∩ S. SQL’s NATURAL JOIN behaves the same way, which is why a column added to both tables can change its result.
Key takeaways
- A theta join is σ θ (R × S); an equi-join tests only equality; a natural join equates every common attribute name and keeps one copy of each.
- A natural join with no common attribute is a product, and with every attribute in common it is an intersection.
- Outer joins keep the tuples without a partner, padded with NULL; in SQL, a condition in ON runs before the padding and one in WHERE runs after it.
- A semijoin keeps the tuples of R that have a partner in S, and an antijoin those that have none; write antijoins with NOT EXISTS, because NOT IN returns nothing once its subquery yields a NULL.
- If the join attribute is a key of S, R ⋈ S has at most |R| tuples, and exactly |R| when it is also a non-null foreign key in R; without keys, anything from 0 to |R| × |S| is possible.
References
- A Relational Model of Data for Large Shared Data Banks (E. F. Codd, Communications of the ACM, volume 13, number 6, pages 377–387) (Association for Computing Machinery)
- PostgreSQL 18 Documentation: Table Expressions (joined tables) (The PostgreSQL Global Development Group)
- PostgreSQL 18 Documentation: Subquery Expressions (EXISTS, IN, NOT IN) (The PostgreSQL Global Development Group)
- SQLite: the SELECT statement (joins and the NATURAL keyword) (SQLite)
- SQLite Release 3.39.0 (support for RIGHT and FULL OUTER JOIN) (SQLite)
- itertools: functions creating iterators for efficient looping (Python Software Foundation)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress