Relational algebra interview questions, with answers

The questions, with answers

1. 1.What is the difference between selection and projection?

   Selection, σ (sigma), picks rows: σ salary > 50000 (Employee) keeps the employees who satisfy the condition, with all their columns — SQL's WHERE. Projection, π (pi), picks columns: π name, salary (Employee) keeps only those two attributes for every row — SQL's SELECT list. The two are confused constantly because SQL uses the word SELECT for projection. Two details worth adding: projection in pure relational algebra removes duplicate rows, because a relation is a set, while SQL's SELECT keeps them unless you write DISTINCT; and both operators are unary, taking one relation and returning one, so they compose freely — π name (σ dept = 'Sales' (Employee)) is the name of everyone in Sales.

2. 2.What are the six basic operators of relational algebra?

   Selection (σ) and projection (π), which are unary; union (∪), set difference (−) and Cartesian product (×), which are binary; and rename (ρ), which gives a relation or its attributes new names so that a relation can be joined to itself. Everything else is defined from these: intersection is R − (R − S), a join is a selection over a Cartesian product, and division can be written with projection, product and difference. Union and difference require the two relations to be union-compatible — the same number of attributes with matching domains — which is the same rule SQL applies to UNION and EXCEPT. Interviewers often ask which operators are "basic" and which "derived"; that split is the answer.

3. 3.What is the difference between a Cartesian product, a theta join, an equijoin and a natural join?

   The Cartesian product R × S pairs every tuple of R with every tuple of S — m × n rows, almost never wanted on its own. A theta join is a Cartesian product followed by a selection on some condition θ, so R ⋈ θ S is σ θ (R × S); when θ is an equality it is an equijoin. A natural join, written R ⋈ S with no condition, is an equijoin on every attribute the two relations share by name, with the duplicate column removed. So Employee ⋈ Department joins on dept if both have a dept attribute — which is also the trap: if the two relations share an attribute you did not intend, such as name, the natural join silently joins on it too. SQL's NATURAL JOIN has the same hazard, which is why most style guides forbid it.

4. 4.How do you write a query that combines selection, projection and join?

   Inside out: join first to bring the attributes together, select the rows you want, then project the columns you need. The names of students enrolled in the course titled DBMS, with Student(sid, name), Enrolled(sid, cid) and Course(cid, title), is π name (σ title = 'DBMS' (Student ⋈ Enrolled ⋈ Course)). The equivalent SQL joins the three tables on sid and cid and filters on title in WHERE. Order matters for efficiency but not correctness — pushing the selection inside, σ title = 'DBMS' (Course) before the joins, gives the same result with a much smaller intermediate, which is precisely what a query optimiser does, and mentioning that earns a mark.

   π name ( σ title = 'DBMS' ( Student ⋈ Enrolled ⋈ Course ) )
   
   -- the same, with the selection pushed down
   π name ( Student ⋈ Enrolled ⋈ ( σ title = 'DBMS' ( Course ) ) )

5. 5.Which operator answers a "who has not" question, and how do you write it in SQL?

   Set difference. R − S is the set of tuples that appear in R but not in S; tuples in both are removed, tuples only in S never appear. The relations must be union-compatible. Students who registered but never paid is π sid (Registered) − π sid (Paid). In SQL it is EXCEPT (MINUS in Oracle), or, where EXCEPT is missing or the columns differ, NOT EXISTS with a correlated subquery, or a LEFT JOIN with IS NULL on the right side's key. Difference is not commutative — S − R is a different set — and it is the operator behind every "who has not" question, which is why it is asked far more than its size suggests.

   -- π sid (Registered) − π sid (Paid)
   SELECT sid FROM Registered
   EXCEPT
   SELECT sid FROM Paid;
   
   -- portable form
   SELECT r.sid FROM Registered r
   WHERE NOT EXISTS (SELECT 1 FROM Paid p WHERE p.sid = r.sid);

6. 6.What is the division operator, and what kind of question does it answer?

   Division answers "for all" questions. R ÷ S, where S's attributes are a subset of R's, returns the values of R's other attributes that are paired in R with every tuple of S. Given Enrolled(sid, cid) and Core(cid), Enrolled ÷ Core is the students enrolled in every core course. There is no DIVIDE keyword in SQL; the standard translation is a double NOT EXISTS — students for whom there is no core course they are not enrolled in — or a count: group by student and keep those whose count of distinct core courses equals the number of core courses. Division is the operator candidates most often cannot express in SQL, so it is the one to practise.

   -- students enrolled in every core course (Enrolled ÷ Core)
   SELECT s.sid FROM Students s
   WHERE NOT EXISTS (
       SELECT 1 FROM Core c
       WHERE NOT EXISTS (SELECT 1 FROM Enrolled e WHERE e.sid = s.sid AND e.cid = c.cid)
   );

7. 7.How do union, intersection and difference in relational algebra map to SQL?

   Directly, with one caveat about duplicates. R ∪ S is UNION, R ∩ S is INTERSECT, R − S is EXCEPT — all three remove duplicates, as set operators must, and all three need union-compatible inputs. The caveat is that SQL tables are bags, not sets: a table can hold identical rows, and SQL adds ALL variants (UNION ALL, INTERSECT ALL, EXCEPT ALL) that keep multiplicity and have no counterpart in pure relational algebra. Intersection is derived, not basic — R ∩ S equals R − (R − S) — which is a standard exam question. And a join is not a set operator at all: it produces new tuples by combining attributes, while union and friends only choose among existing ones.

8. 8.What is the difference between relational algebra and relational calculus?

   Relational algebra is procedural: an expression says which operators to apply and in what order — join these, select those rows, project these columns. Relational calculus is declarative: a formula says what tuples must satisfy, and says nothing about how to find them — tuple relational calculus quantifies over tuples ({ t | t ∈ Employee ∧ t.salary > 50000 }), domain relational calculus over attribute values. The two are equally expressive (Codd's theorem), and SQL is a calculus-flavoured language that the query optimiser translates into an algebra-flavoured plan. That last sentence is usually the answer the interviewer is hoping for: you write what, the optimiser decides how.

How the diagnostic asks it

One question from the DBMS bank, exactly as a sitting would show it. The bank has 4 on relational algebra and 60 across DBMS.