Real-life analogy: SQL behind the scenes

Every SQL query you write is translated by the DBMS into a relational algebra expression tree, optimized, then executed. Knowing RA means you understand exactly what happens for SELECT with WHERE, JOIN, and GROUP BY. You can predict query behavior, write better SQL, and explain execution plans.

Core operations with SQL equivalents

-- R(A): Employee(EmpID, Name, DeptID, Salary)
-- R(B): Department(DeptID, DeptName, Location)

-- 1. Selection + Projection
-- RA: π_Name,Salary(σ_Salary>50000(Employee))
SELECT Name, Salary FROM Employee WHERE Salary > 50000;

-- 2. Theta Join (most common join type)
-- RA: σ_E.DeptID=D.DeptID(Employee × Department)
SELECT E.Name, D.DeptName
FROM Employee E JOIN Department D ON E.DeptID = D.DeptID;

-- 3. Union: employees in Dept 1 OR Dept 2
-- RA: π_EmpID(σ_DeptID=1(Employee)) ∪ π_EmpID(σ_DeptID=2(Employee))
SELECT EmpID FROM Employee WHERE DeptID = 1
UNION
SELECT EmpID FROM Employee WHERE DeptID = 2;

-- 4. Set Difference: employees NOT in Dept 1
-- RA: π_EmpID(Employee) − π_EmpID(σ_DeptID=1(Employee))
SELECT EmpID FROM Employee
EXCEPT
SELECT EmpID FROM Employee WHERE DeptID = 1;

-- 5. Division: employees who worked on ALL projects
-- RA: WorksOn ÷ Project
SELECT DISTINCT w1.EmpID FROM WorksOn w1
WHERE NOT EXISTS (
    SELECT ProjID FROM Project
    EXCEPT
    SELECT w2.ProjID FROM WorksOn w2 WHERE w2.EmpID = w1.EmpID
);

Tuple Relational Calculus (TRC)

TRC syntax: {t | P(t)} — the set of all tuples t that satisfy predicate P. TRC is non-procedural: you declare WHAT you want, not HOW to compute it. Uses ∃ (existential) and ∀ (universal) quantifiers.

Safe vs unsafe TRC expressions: TRC can express "unsafe" queries returning infinite results: {t | t ∉ Employee} — all tuples NOT in Employee is infinite. Safe TRC only produces values from the active domain. SQL is always safe by design.

Min/max result sizes — the classic GATE numerical

GATE loves asking "relation R has m tuples, S has n tuples — what are the minimum and maximum tuples in the result?" The complete cheat sheet (set operations assume union-compatible relations):

Equivalence rules — how the optimizer rewrites your query

Query optimizers are relational-algebra rewrite engines. The parser turns SQL into an RA expression tree; the optimizer then applies equivalence rules to find a cheaper but provably identical plan. The single most important rule family is pushing selections down: filtering early shrinks every intermediate result that follows.

• Cascade of σ: σ_c1∧c2(R) ≡ σ_c1(σ_c2(R)) — a compound filter can be split and applied in stages.
• Push σ through join: σ_c(R ⋈ S) ≡ σ_c(R) ⋈ S when c references only R's attributes — filter a million-row table before joining, not after.
• σ + × = ⋈: σ_R.a=S.b(R × S) ≡ R ⋈_{R.a=S.b} S — a selection over a Cartesian product is a theta join; optimizers never actually materialize the product.
• Join commutativity and associativity: R ⋈ S ≡ S ⋈ R and (R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T) — this freedom is what join-order optimization explores; for n tables there are Catalan-number-many orders.
• Push π down: discard unneeded columns early to shrink intermediate tuples — but only after keeping the columns later joins still need.

Reading EXPLAIN output: When PostgreSQL's EXPLAIN shows a filter applied at a table scan node underneath a join node, you are watching "push selection below join" in action. The optimizer chose σ-then-⋈ over ⋈-then-σ — exactly the rewrite above, applied automatically.

Sets vs bags, and extended relational algebra

Pure relational algebra is set-based: π_Dept(Employee) automatically deduplicates. SQL uses bag (multiset) semantics: SELECT Dept FROM Employee keeps every duplicate unless you write DISTINCT. This is the single most common source of confusion when translating between RA and SQL — UNION deduplicates (set), UNION ALL does not (bag), and COUNT can differ between the two worlds. Real query engines also need operations Codd's six primitives cannot express, collectively called extended relational algebra:

Practice questions (GATE-style)

1. Express in RA: names of employees earning more than 50000 in department named "IT". (Answer: π_Name(σ_Salary>50000(Employee ⋈_{E.DeptID=D.DeptID} σ_DeptName="IT"(Department))))
2. R has 5 tuples, S has 3 tuples. Maximum tuples in R ⋈ S (natural join on common attribute)? (Answer: 15 if all 5 tuples of R match all 3 of S. Minimum is 0 if no matches.)
3. What is R ∪ S where R={(1,a),(2,b)} and S={(2,b),(3,c)}? (Answer: {(1,a),(2,b),(3,c)} — set union removes duplicates.)
4. RA is procedural and TRC is non-procedural. What does this mean? (Answer: RA specifies a sequence of operations (HOW to retrieve). TRC specifies a predicate describing desired result (WHAT to retrieve) without specifying retrieval procedure.)
5. Express R ÷ S using basic operators. (Answer: R ÷ S = π_R-S(R) − π_R-S((π_R-S(R) × S) − R))