Relational algebra: operators, joins and division
Learning goals and semantic contract
Evaluate an algebra expression one operator at a time, preserve schemas, and recognize existential versus universal queries. Throughout this lesson relations are finite sets, attributes contain ordinary non-null values, and comparisons use ordinary two-valued logic. Projection removes duplicates. SQL bag and NULL semantics are a later topic. An algebra expression returns a relation, so its result can feed another operator.
1. Selection, projection and rename
Selection σ_condition(R) keeps tuples satisfying a predicate and preserves the schema. Projection π_attributes(R) keeps only listed attributes and removes duplicate result tuples. Rename ρ changes relation or attribute names so that self-joins and set operations have unambiguous schemas.
Use Enrol(sid,cid)={(1,A),(1,B),(2,A),(3,C)}. σ_cid=A(Enrol)={(1,A),(2,A)}. Projecting sid from this result gives {1,2}. Projecting sid from the whole relation gives {1,2,3}, cardinality 3 rather than 4. Selection cannot increase row count; projection cannot increase row count under set semantics. A zero-attribute projection, if allowed by the algebra, is {()} for a nonempty input and empty for an empty input; our exercises use nonempty attribute lists.
2. Set operators and Cartesian product
Union, intersection and difference require union-compatible schemas: equal arity and compatible corresponding domains, with names aligned under the chosen named-attribute notation. R−S keeps tuples in R that are absent from S; it is not commutative. If R={1,2,3} and S={2,4}, then R∪S={1,2,3,4}, R∩S={2}, R−S={1,3}.
Cartesian product pairs every tuple in R with every tuple in S, so cardinality is |R||S| when attributes are renamed to avoid collisions. Product of a relation with an empty relation is empty. A selection over a product can express a theta join: R ⋈_θ S = σ_θ(R×S). Equality is one possible theta predicate, not the only one.
3. Joins match values, not row positions
Student(sid,name)={(1,Ana),(2,Bob),(4,Dev)} and Enrol as above have sid in common. Their natural join equates all common attributes and keeps one copy of each common column. The result is {(1,Ana,A),(1,Ana,B),(2,Bob,A)} on (sid,name,cid). Student 4 has no enrollment and disappears from this inner join. Enrol's sid 3 has no matching Student and disappears too. No referential-integrity constraint is assumed in this illustrative instance.
Natural join is convenient but uses every shared name. If two unrelated columns both happen to be named name, they will also be equated unless renamed. With no shared attribute names, natural join becomes Cartesian product. Do not assume equal tuple counts or zipped row order.
A self-join needs two renamed copies. For Employee(eid,managerId), to obtain an employee and their manager, rename the copies E and M, select E.managerId=M.eid over E×M, and project E.eid and M.eid. Without distinct names, the two roles cannot be referenced clearly.
4. Division expresses “for every”
Let R(X,Y) and S(Y) be relations. R÷S returns X values appearing in π_X(R) that pair in R with every Y in S. The candidate domain is explicitly π_X(R). A useful construction is:
Candidates = π_X(R) Missing = (Candidates×S)−R Bad = π_X(Missing) Answer = Candidates−Bad
All operations are schema aligned. For Enrol above and Required(cid)={A,B}, Candidates={1,2,3}. Candidate 1 has both A and B; candidate 2 misses B; candidate 3 misses A and B. Therefore Enrol÷Required={1}. An existential query “takes at least one required course” would return {1,2}; it is a different query.
Empty-divisor edge case: if Required is empty, every candidate satisfies the universal condition vacuously, so division returns {1,2,3}. It does not invent sid 4, because 4 is absent from π_sid(Enrol). If the business query instead asks about all students, including students with no enrolments, use Student as the candidate domain: π_sid(Student)−π_sid((π_sid(Student)×Required)−Enrol). With empty Required this returns every Student sid. State the candidate domain before applying “for all.”
5. Safe rewrites and worked query
Selections can be pushed below joins when their predicates use only attributes from that input. Projection pushdown must preserve output attributes and all attributes still required for joins or later predicates. Dropping sid before joining Student to Enrol breaks the join.
To find names of students enrolled in A: first filter Enrol to cid=A, then join on sid with Student, then project name. The filtered Enrol rows are (1,A),(2,A); joined rows correspond to Ana and Bob; final result is {Ana,Bob}. If two qualifying students share a name, set projection outputs that name once. To preserve individual identities, project sid and name.
Pitfalls
- Selection chooses rows; projection chooses attributes and deduplicates.
- Difference is directional and needs compatible schemas.
- Natural join matches all common attribute names; rename accidental overlaps.
- “At least one” needs existence; “every” needs ruling out missing pairs.
- For an empty requirement set, universal truth holds over the chosen candidate domain.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For R(A,B)={(1,x),(1,y),(2,x)}, what is |π_A(R)| under set semantics?
A. 1 B. 2 C. 3 D. 6
Answer: B
A: Both A=1 and A=2 occur.
B: Projection yields {1,2}; the repeated 1 is removed.
C: This keeps duplicates, contrary to set projection.
D: Projection cannot double the tuple count.
P02. A relation with 4 tuples is multiplied by an empty relation. Product cardinality?
A. 0 B. 1 C. 4 D. Undefined
Answer: A
A: There are no pairs because the second input has no tuple.
B: An empty relation is not a singleton empty tuple.
C: Each first-input tuple still needs a partner.
D: The Cartesian product is defined.
P03. R(A)={1,2,3}, S(A)={2,4}. What is R−S?
A. {2} B. {4} C. {1,3} D. {1,2,3,4}
Answer: C
A: This is the intersection.
B: This is S−R.
C: Keep only R values absent from S.
D: This is the union.
P04. A natural join of relations with no common attribute names equals:
A. Union B. Cartesian product C. Always empty D. Difference
Answer: B
A: Union needs compatible schemas and has different semantics.
B: There are no shared equality conditions, so every pair joins.
C: No shared attributes does not forbid pairs.
D: Difference removes tuples and is not a join.
P05. R(s,c)={(1,A),(1,B),(2,A)}, S(c)={A,B}. R÷S is:
A. {1} B. {2} C. {1,2} D. Empty
Answer: A
A: Only 1 is paired with every required c.
B: 2 lacks B.
C: This would answer at least one required c.
D: 1 satisfies the universal requirement.
P06. For nonempty R(X,Y), divide by empty S(Y), with candidates π_X(R). The result is:
A. Always empty B. π_X(R) C. All imaginable X values D. R itself with both columns
Answer: B
A: No candidate has a missing required pair when requirements are empty.
B: Universal truth holds for every candidate in the stated domain.
C: Division does not create values outside the candidate domain.
D: Division returns the X schema, not X,Y.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in