What is the Cartesian product of two relations, and how are the theta-join and equi-join defined in terms of it?

## Cartesian product The Cartesian product `R x S` combines every tuple of `R` with every tuple of `S`. If `R` has attributes `(a, b)` and `S` has `(c, d)`, the result has `(a, b, c, d)`, and if `R` has 1,000 tuples and `S` has 5,000, the result has 5,000,000. There is no condition and nothing is filtered — the operator's whole job is to make every combination available so a later operator can choose among them. Two requirements follow from the relational model itself: - **Distinct attribute names.** A relation's attributes form a set of names, so if `R` and `S` share a name the product would be ill-formed. A rename must be applied first. This is why joining a relation to itself always involves renaming. - **Closure.** The result is a relation, so products compose with every other operator. The product is a *primitive* operator of the basic algebra — one of Codd's original five. Everything in the join family is built on top of it. ## Theta-join A theta-join is exactly a product followed by a selection: ``` R JOIN[theta] S = sigma[theta] ( R x S ) ``` `theta` may be any predicate that references attributes of either side: `R.a = S.c`, `R.b < S.d`, `R.a = S.c AND R.b <> S.d`, a range overlap test, a distance comparison. Because it is defined by composition, theta-join is a **derived** operator, not a primitive. That is a distinction interviewers like: the join is convenience notation over product and selection, whereas the product itself cannot be built from anything simpler. Cardinality intuition: the theta-join result is somewhere between zero tuples (nothing satisfies the predicate) and `|R| * |S|` (everything does). The fraction that survives is the predicate's **selectivity**, and estimating it is the core problem of query optimization. ## Equi-join An equi-join is a theta-join where `theta` is a conjunction of equalities between attributes of the two relations, such as `R.dept_id = S.id`. Almost every join in a normalized OLTP schema is an equi-join, because joins follow foreign keys and a foreign key relationship is an equality relationship. Why the distinction earns its own name: equality has structure that inequality does not. Equal values hash to the same bucket and sort to the same position, which is what makes it possible to find matching pairs without examining every combination. A predicate like `R.b < S.d` offers no such handle in general — the matching set for each tuple is a range rather than a point — so non-equality joins tend to degrade toward examining many more combinations. The logical definition is identical in both cases; the difference is entirely about what strategies remain available underneath. An equi-join keeps **both** joined attributes in its result — `R.dept_id` and `S.id` both appear, holding equal values. Removing the redundant one requires a projection; the natural join is the variant that does this automatically. ## Logical definition versus physical evaluation The defining equation `sigma(R x S)` describes *what the answer is*, not how to compute it. Taken literally it would be disastrous: a join of two million-row tables would materialise a trillion intermediate tuples. Real engines never do this. They use the predicate to avoid generating non-qualifying pairs in the first place, and the physical strategies for doing so are a separate subject from the algebra. The algebraic identity still matters, though, because it is what licenses the optimizer's most valuable rewrites. Since a join is a selection over a product, and selection is commutative with itself, predicates can be split and pushed down; since inner join is commutative and associative (inherited from the product plus a conjunctive predicate), the optimizer may enumerate join orders freely. Those two facts come directly from the definition. ## When a Cartesian product legitimately appears Unconditional products are usually a symptom — a forgotten join predicate, producing a result that is both enormous and meaningless. But they have real uses: - Generating combinations deliberately: every product crossed with every region to build a complete grid before an outer join and aggregation fills in the zeros. - Joining a one-tuple relation of constants or parameters onto a query. - Cross-joining a small generated series to expand rows. An optimizer that reports a product in a plan for a query that named a join condition is telling you the condition could not be applied where you expected — often because it references a third relation or was written in a way that prevents it from being used as a join predicate. ## Interview framing Give the definitions crisply, state the cardinality arithmetic, note that theta-join is derived while product is primitive, and add the equality-versus-inequality point about which strategies stay available. Finishing with "the definition is logical, not a recipe" shows you understand why the identity matters to the optimizer rather than to the executor.