Division, Rename & Extended Operators

## What rename is The rename operator, usually written with the Greek letter rho, takes a relation and returns exactly the same set of tuples under a different name and/or different attribute names. Two common forms are used: - `rho E1(Emp)` — the relation `Emp` is now referred to as `E1`. - `rho (manager_id <- id)(Emp)` — the attribute `id` is now called `manager_id`. Nothing about the data changes. Rename is a pure schema operation: same cardinality, same tuples, different labels. ## Why the algebra needs it at all Relational algebra is normally defined under the **named perspective**: a tuple is a mapping from attribute *names* to values, not an ordered list of columns. That choice buys a lot — natural join, union compatibility and projection all become simple name-based definitions — but it costs you the ability to distinguish two things that happen to have the same name. The algebra is also **closed**: every operator takes relations and returns a relation. A relation must have a set of distinct attribute names. So any operator that could produce two attributes with the same name would break closure. The Cartesian product of `Emp` with itself would yield two attributes called `id`, two called `name`, and so on — not a relation. Rename is the escape hatch that restores well-formedness. ## The self-join case The canonical query is "list each employee together with their manager's name", where `Emp(id, name, mgr_id)` refers to itself. Written naively, `Emp JOIN Emp` is meaningless: under natural-join semantics it would match every attribute to itself and simply give you `Emp` back; under product semantics it would produce duplicate attribute names. The algebraic formulation renames first: ``` E <- rho E(Emp) M <- rho M(Emp) result <- pi E.name, M.name ( E JOIN[E.mgr_id = M.id] M ) ``` Now the two occurrences are distinct *variables* ranging over the same relation, and the join condition can refer unambiguously to each side. This is exactly what a SQL table alias does — the alias is the surface syntax for rho. The same trick generalises: any query over a hierarchy (employee/manager, part/subpart, node/parent), any "pairs of rows from the same table" query (find two products with the same price, find duplicate emails), and any comparison of a row to an aggregate over its own relation needs at least one rename. ## Rename as a control knob for natural join Natural join equates attributes that share a name. That means the join condition is decided entirely by the *schema*, and rename is the only way to change it. If `Orders(id, customer_id, ...)` and `Customers(id, ...)` are joined naturally, the shared attribute `id` is the wrong one; you must rename first: ``` Orders JOIN rho (customer_id <- id)(Customers) ``` Conversely, renaming two semantically unrelated attributes to the same name would silently make natural join use them. This fragility is one reason practitioners prefer explicit join conditions in production code. ## Rename and the theory around it Rename is what makes relational algebra equivalent in expressive power to the safe subset of tuple relational calculus. Without it, you cannot express queries whose calculus form quantifies over the same relation twice — the algebra would be strictly weaker. Codd's original set of primitives (selection, projection, product, union, difference) is therefore usually extended with rename to make the correspondence exact. It also interacts with the closure property in a useful way for optimizers: because rename touches no data, it can always be pushed anywhere in the expression tree at zero cost. Physical plans typically do not have a rename operator at all — column naming is resolved at binding time, and the runtime works with positional slots. ## Practical mapping - Rename of a relation = a table alias. - Rename of an attribute = a column alias, or a projection list that assigns new names. - Correlated references in a subquery = a rename that makes the outer occurrence addressable from the inner one. ## Common mistakes Candidates often say rename "copies the table", which suggests two independent materialisations; it does not — it introduces two *bindings* to the same relation. Others claim rename is needed only for pretty output; in fact, without it certain queries are inexpressible. And some assume a self-join always needs a rename on both sides — one is enough, as long as the two occurrences end up distinguishable.