INFO20003 Chap.4 Relational Algebra
Relational Algebra
Relational algebra provides the formal operator language behind relational queries. Because each operator returns another relation, selections, projections, joins and set operations can be composed into expression trees and transformed when equivalence is preserved.
The chapter teaches the horizontal and vertical roles of selection and projection, compatibility requirements for set operations, join variants and division for universal questions. Selection keeps the heading and retains tuples satisfying a predicate. Projection chooses attributes and, under set semantics, removes duplicate projected tuples. Rename resolves heading conflicts and gives meaningful names to intermediate results.
Cartesian product pairs every tuple from two relations when their headings are disjoint; a theta join is a product followed by a condition, while a natural join uses equally named attributes and can be unsafe when those names coincide accidentally. Outer joins preserve unmatched tuples by introducing null markers and therefore need care when compared with classical two-valued algebra.
Set union, intersection and difference require compatible headings because they compare complete tuples from the same kind of relation. Composition is easiest when each intermediate is annotated with its heading. Start from the requested output attributes, identify the relations that contain them, then preserve every attribute needed by joins and later predicates until its last use.
A selection can move toward a base relation only when its predicate is defined there and the rewrite preserves the surrounding join semantics. A projection can move only when it retains required keys and result attributes. These conditions explain optimisation equivalences without treating them as symbol shuffling. Universal questions deserve a separate method.
Division can identify values associated with every member of a required set, but the same logic can be expressed by finding missing candidate-required pairs and subtracting candidates that have a counterexample.
This double-difference form exposes the quantifier and helps distinguish “all” from “at least one.” Validate any expression with boundary tuples: an unmatched row, an empty required set, two rows that collapse under projection and a same-named attribute that should not join. Reading the final tree as an English sentence provides a second check that every operator answers the original question rather than a nearby one.
What this chapter covers
- 01
Closure
- 02
Selection
- 03
Projection
- 04
Rename
- 05
Set operations
- 06
Cartesian product
- 07
Join variants
- 08
Division
Worked example · free
Build an operator tree
- 1Select the Indexing session tuples from Session.
- 1Join the selected sessions to Attends on session identifier.
- 1Join Member on member identifier.
- 1Project member name only after the required joins.
Key terms
- Closure
- The property that every relational algebra operator returns a relation.
- Selection
- A unary operator that keeps tuples satisfying a predicate.
- Projection
- A unary operator that retains named attributes under relational set semantics.
- Theta join
- A join whose tuple pairs satisfy a stated comparison predicate.
- Natural join
- A join on same-named attributes that removes duplicate join columns.
- Division
- An operator used to find values related to every tuple in a required set.
Relational Algebra FAQ
How can I check an algebra tree before simplifying it?
Write the heading below every intermediate relation and mark the last point where each attribute is needed. Then test one ordinary tuple, one missing match and one pair that becomes duplicate after projection. These checks reveal predicates moved below their required attributes, incompatible set operands and projections that discard a later join key.
Why can projection break a query plan?
Pushing projection down is safe only when it retains every join key, predicate attribute and output value needed later. Removing an identifier too early leaves the next join without a matching attribute.
When is division the right operator?
Division matches a universal condition. Build a relation of qualifying pairs and divide it by the complete required set when the prompt asks for an item connected to every required partner.
How can I validate an algebra expression?
Write each intermediate schema, confirm predicates reference available attributes, check set-operator compatibility, then translate the tree into plain English from leaves upward. The sentence should match the prompt's quantifier and output heading.
Exam move
Memorise operator meaning through schema changes rather than symbols alone. For a small pair of relations, write the input and output heading for selection, projection, product and join. Rebuild common SQL questions as algebra trees, placing base-specific filters near their relations and preserving every needed key. Practise universal conditions by first writing the required set and qualifying pairs.
After each expression, read it as a sentence and test a boundary tuple. This exposes lost attributes, unsafe natural joins and a mistaken existential answer to an all-items question.
Working through Relational Algebra in INFO20003? Sia is AskSia’s AI Computer Science tutor — ask any INFO20003 Relational Algebra question and get a clear, step-by-step explanation grounded in how INFO20003 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.