Why is the outer join treated as an extended relational-algebra operator rather than something derivable from the basic operators, and what does it do with tuples that find no match on the other side?

## Dangling tuples When two relations are joined on a condition, a tuple of either operand that satisfies the condition with *no* tuple of the other operand is called a **dangling tuple**. Inner join drops it. That loss is often exactly what you want and often exactly what you do not: a report of "every customer with their order total" must still show customers with zero orders; an inner join silently deletes them, and the resulting number is wrong in a way nobody notices until an audit. The outer-join family exists to preserve dangling tuples: - **Left outer join** returns all inner-join results plus, for every dangling tuple of the left operand, that tuple padded with null in all right-side attributes. - **Right outer join** is the mirror image. - **Full outer join** preserves dangling tuples from both operands. The result schema is identical to the inner join's; only the tuple set differs. ## Why it counts as an extension Two independent reasons, and a strong answer names both. **1. Value-preservation.** Selection, projection, product, union and difference never invent a value: everything in an output appeared in an input. Outer join places a null into an attribute position where no input supplied one. Like aggregation, it is therefore outside the expressive closure of the basic operators. **2. The model has no null.** Codd's original relational model is defined over relations of total tuples: every attribute has a value from its domain. Introducing null requires a new marker outside every domain, a definition of what comparisons involving it mean, and a decision about how the logic of predicates changes. The standard answer — three-valued logic with true, false and unknown, where a selection keeps only tuples for which the predicate is true — is a substantive extension of the model, not a notational convenience. Some relational purists reject outer join for exactly this reason and prefer to model optionality with a separate relation, so that absence is represented by the absence of a tuple rather than by a marker inside one. ## The consequences the interviewer is really after Once nulls are in play, several algebraic identities that optimizers rely on break down. **Inner joins reorder freely.** Inner join is commutative (`A JOIN B = B JOIN A`) and associative (`(A JOIN B) JOIN C = A JOIN (B JOIN C)`), which is the entire basis of join-order enumeration: any order produces the same relation, so the optimizer is free to choose the cheapest. **Outer joins do not.** `(A LEFT JOIN B) LEFT JOIN C` and `A LEFT JOIN (B LEFT JOIN C)` can differ, because in the first form a null-padded row from the `A/B` step is offered to the `C` predicate, while in the second form `B`'s dangling behaviour with respect to `C` is decided first. Full outer join is commutative but still not associative in general. Optimizers therefore carry explicit rules about which reorderings are valid, usually expressed with a notion of null-rejecting predicates and conflict sets, and in the absence of such analysis they simply refuse to reorder — which is why a chain of outer joins often executes in written order and performs badly. **Predicate placement changes meaning.** A predicate on the null-supplying side applied *after* a left outer join rejects the null-padded rows (any comparison with null is unknown, not true), which collapses the outer join into an inner join. The same predicate applied *inside* the join condition filters before padding and preserves the dangling rows. This is the single most common real-world outer-join bug, and it is a pure algebra issue: the two expressions are different trees, not different syntaxes for one tree. A predicate that is guaranteed to reject nulls is precisely the thing an optimizer looks for when deciding whether it may legally rewrite an outer join into an inner one — a rewrite it *wants* to perform, because the inner form reorders freely. **Duplicate and cardinality intuition shifts.** A left outer join returns at least as many tuples as the left operand has, and exactly that many when the join is on a key of the right side. Chained outer joins can still multiply rows if any join is on a non-unique attribute; "outer" preserves rows, it does not prevent fan-out. ## Relationship to other extended operators Outer join sits in the same family as grouping/aggregation and generalised projection: operators real systems cannot do without, that nevertheless step outside the value-preserving basic algebra. It also composes with them in a load-bearing way. The standard recipe for "show zero for categories with no rows" is an outer join from a complete dimension relation to the fact relation, followed by aggregation — because aggregation alone can never produce a group for a value it never saw. Reporting queries are full of exactly this pattern. ## Simulating outer join with basic operators plus null If you are permitted a null value but not an outer-join operator, you can build a left outer join as: the inner join, unioned with (the left operand minus the projection of the inner-join result back onto the left's attributes) Cartesian-producted with a one-tuple relation of nulls for the right's attributes. Writing this out is a useful whiteboard exercise, and it makes the point precisely: the derivation needs a relation of nulls supplied from outside, which is the extension. Without such a relation, no derivation exists. ## Interview framing Define dangling tuples, give the three variants, name both reasons it is an extension, and then spend most of your time on the practical consequence — reorderability and predicate placement. That last part is what separates a textbook answer from an operational one.