INFS2200 Chap.6 Relational Algebra Operations
Relational Algebra Operations
Relational algebra expresses a query as a pathway of relation-producing operators. This chapter separates selection from projection, checks union compatibility, composes joins and reads expression trees from the leaves upward.
It also applies equivalence conditions safely: local selections can move down, while projections must retain every attribute needed by later predicates, joins and final output.
Selection keeps tuples satisfying a condition, while projection keeps named attributes.
The SQL SELECT list corresponds to algebraic projection, and a WHERE predicate corresponds to algebraic selection, so shared vocabulary must not reverse the operators. Set union, intersection and difference require compatible schemas, and difference remains directional. Join combines related tuples through an explicit condition.
Every operator returns a relation, letting outputs feed later steps and form a query tree.
Translation starts with base relations, attaches local predicates, joins on qualified keys and leaves final display columns for the top projection. Intermediate assignments can name useful stages and make a long expression easier to audit.
Equivalent rewrites are conditional.
A local selection can move below a join when it uses one input, but a projection moves only if it preserves output attributes and all later predicate or join fields. The chapter annotates surviving schemas after every step, proving correctness before claiming that smaller intermediate rows or narrower tuples reduce work.
Renaming resolves two different problems.
It can distinguish two uses of the same relation in a self-join, and it can align compatible headings before a set operation. Qualification then shows which input supplies an attribute. These are semantic safeguards, not cosmetic notation: an unqualified shared name can make a condition ambiguous, while a missing alias can collapse two intended roles into one.
Product and join must not be conflated.
Cartesian product forms every pair of tuples and supplies the conceptual space from which a condition can select matching pairs. A theta join packages that product-and-selection meaning, and an equijoin uses equality.
Natural join additionally removes duplicate join columns and infers matches from shared names, so it is safe only when those names encode exactly the intended relationship.
Set operations answer population questions after both sides project to the same meaning. To find active students who have not submitted, build an active identifier relation, build a submitted identifier relation and subtract in that direction.
A row predicate using not-equal cannot discover a student with no submission row. Small witness tuples on the left only, both sides and right only test the expression quickly.
Expression-tree review tracks both rows and attributes. Beside each node, write the surviving schema and a plain-language description of its tuples.
A pushed selection should use only attributes present below it, a join must retain its keys, and the final projection should match the requested output exactly. Once equivalence is established, reduced intermediate size becomes a legitimate optimisation consequence rather than an assumption.
What this chapter covers
- 01
Selection and projection
- 02
Set operators and compatibility
- 03
Cartesian product and join
- 04
Expression trees
- 05
Equivalent rewrites and attribute lineage
Worked example · free
Translate an active booking request
- +1List the base relations.
- +1Apply the local status selection.
- +1Join on the qualified key.
- +1Retain attributes required above.
- +1Project the requested output.
Key terms
- Selection
- A unary operator that keeps tuples satisfying a condition.
- Projection
- A unary operator that keeps named attributes in the result.
- Join
- An operator combining related tuples from two relations.
- Union compatibility
- Matching relation degree and compatible corresponding domains for set operations.
Relational Algebra Operations FAQ
Why is algebraic selection not SQL SELECT?
Algebraic selection filters tuples and corresponds to an SQL WHERE condition. Algebraic projection keeps attributes and corresponds more closely to the SQL SELECT list. The shared word can otherwise reverse the operations, so identify rows versus columns explicitly.
When can a projection move down?
Only when it preserves final output attributes and every attribute still needed by a higher selection or join. Removing a join key makes the transformed expression invalid. Write the intermediate schema to prove that required fields survive.
Why avoid a Cartesian product in a plan?
A product creates every tuple pair and can make an enormous intermediate result. When an equality predicate supplies a relationship, product plus selection should normally be represented and implemented as a join. The logical equivalence does not justify materialising all pairs.
Exam move
Translate requests from relations to predicates, joins and final output. Read trees bottom to top and mark the surviving schema at each node. Prove equivalence before claiming that a pushed-down operator reduces work. Start each exercise by listing base schemas and qualifying ambiguous attributes.
Write local selections beside the correct relation, then draw join edges and delay the final projection until every key has been used. For set operations, check attribute count and corresponding domains before manipulating tuples. Practise reading a completed tree back into a plain-language request; this reverse translation exposes missing predicates and unintended joins.
When applying a rewrite, record the condition that makes it safe and the intermediate size or width it is expected to reduce.