Relational Algebra I

The last lesson promised a language for questioning a relation, not just filling it — here it is. You want every student whose marks are above 80, then only their names, with no IDs or roll numbers cluttering the answer. SQL spells that SELECT name FROM Student WHERE marks > 80. Underneath, the database engine does something simpler: it runs two tiny operators back to back. That underneath layer is relational algebra — six little symbols that combine to build every query you will ever write. It is no museum piece, either: every query planner, from Postgres to Spark SQL, rewrites your SQL into exactly these operators before deciding how to run it.

Each operator takes one or two relations (think tables) and returns another relation. So you can chain them freely, like Lego.

The six basic operators

We will meet them with one table: Student(id, name, marks) with rows (1, Asha, 85), (2, Ravi, 70), (3, Maya, 92).

Selection σ picks rows that satisfy a predicate (a true/false test on a row, like marks ≥ 80). Projection π picks columns. Two operators, two halves of every basic SQL query.

• σ_predicate(R) — keep the rows of R where the predicate is true. The predicate can use =, comparisons, AND, OR, NOT on attributes.
• π_attrs(R) — keep only the listed columns. Set semantics: if dropping columns creates duplicate rows, they collapse into one.
• R × S — Cartesian product. Every row of R paired with every row of S. If R has m rows and S has n, the result has m·n rows.
• R ∪ S, R ∩ S, R − S — set operations. R and S must be union-compatible: same number of columns, same domains in the same order.
• ρ_S(R) or ρ_S(a,b,c)(R) — rename the relation (and optionally its attributes). Useful before joining a table to itself.

That is it — six operators. SQL is mostly sugar over them.

The subset idiom — encoding “for-all”

Plain SQL has no tidy way to say “every row of A appears in B.” In relational algebra, set difference makes it tidy:

A − B = ∅   ⇔   A ⊆ B   ⇔   every tuple of A is also in B

If A minus B is empty, nothing in A was missing from B — so A is a subset. That tiny trick is how RA encodes “for-all” questions before you reach for division.

How GATE asks this

A favourite MCQ pattern: give you four candidate expressions and ask which one checks a “for-all” condition. The answer hinges on whether you can read the A − B = ∅ shape. GATE DA 2024 Q16 did exactly that — see the worked example.

Worked example — GATE DA 2024 Q16

Relations are Team(name), Defender(name), Forward(name). Which expression evaluates to true if and only if every player in Team is BOTH a defender AND a forward?

The condition is “every name in Team is in π_name(Defender) ∩ π_name(Forward)” — a subset check. Apply the idiom:

π_name(Team) − ( π_name(Defender) ∩ π_name(Forward) )  =  ∅

Reading it left to right: take all the names in Team; subtract those who are in both Defender and Forward; if nothing is left over, every Team member is both — which was the question. That is the 2024 answer (option C).

Watch the direction. The expression ( π_name(Defender) ∩ π_name(Forward) ) − π_name(Team) = ∅ says the OPPOSITE — every dual-role player is in Team — a different claim entirely.

A second sanity rule: π drops duplicates (set semantics). So π_name(σ_marks ≥ 80(Student)) on a table where two students happen to share a name returns one row, not two. SQL is bag-semantics by default; pure RA is set-semantics. GATE expects set-semantics unless told otherwise.

A question to carry forward

One operator above is quietly wasteful. The cross product R × S pairs every row of R with every row of S — m·n rows — but you almost never want all of them. Ask for “each student beside the courses they took” and the cross product also pairs Asha with courses she never enrolled in, then leaves you to filter the garbage out by hand. There has to be a cleaner way to combine two tables on a shared column. And the subset idiom hinted at something more too — a single operator for “for-all” questions. Here is the thread onward: how do you join two relations on matching values without the cross-product explosion, and what one operator answers “find the students who took every course”?

In one breath

• Relational algebra = six operators on relations, chainable like Lego; every SQL query compiles down to them.
• σ_pred(R) keeps matching rows (schema unchanged); π_attrs(R) keeps columns (and drops duplicates — set semantics).
• R × S = Cartesian product, |R|·|S| rows. ∪, ∩, − need union-compatible operands (same arity + domains). ρ renames (no data change).
• Subset idiom: A − B = ∅ ⇔ A ⊆ B — RA’s way to say “every tuple of A is in B” (direction matters; B − A is the opposite claim).
• Pure RA is set-semantics (no duplicates); SQL is bag-semantics unless you write DISTINCT.

Practice