What is the Cartesian product of two relations, and how are the theta-join and equi-join defined in terms of it?
answer
- product = every pairing, |R| * |S|
- theta-join = sigma[theta](R x S), derived not primitive
- equi-join = equality-only theta
- equality hashes and sorts; inequality does not
- logical definition, never a literal execution recipe
basics
~20 sThe Cartesian product pairs every tuple of one relation with every tuple of the other, producing a relation with the combined attributes and a cardinality equal to the product of the inputs. A theta-join is that product filtered by a predicate; an equi-join is a theta-join whose predicate uses only equality comparisons.
solid answer
~50 s**Cartesian product** (`R x S`) forms every possible pairing: schema is the union of both attribute sets, cardinality is `|R| * |S|`. It is unconditional, so it is almost never what a query wants on its own. **Theta-join** is defined as selection applied to the product: `R JOIN[theta] S = sigma[theta](R x S)`, where theta is any predicate over both sides — equality, inequality, ranges, arbitrary boolean combinations. **Equi-join** is the special case where theta is a conjunction of equality comparisons between attributes of the two sides. It matters because equality is the only condition that hash- and merge-based physical strategies can exploit; non-equality theta-joins generally force a nested-loop shape. Two points to add: - The definition is *logical*, not physical. No engine materialises the product and then filters; it uses index lookups, hashing or merging to produce only qualifying pairs. - If the product's attribute names collide, a rename is required first, since a relation cannot have two attributes of the same name.
code
text · 3 linesR x S -- every pairing, |R|*|S| tuples
sigma[ R.b < S.d ] (R x S) -- theta-join, non-equality predicate
sigma[ R.a = S.c ] (R x S) -- equi-join; both R.a and S.c remaingo deeper
State the product's definition and cardinality, then that a theta-join is a product with a filter and an equi-join is the equality-only case.
Add that theta-join is derived rather than primitive, that both join columns survive an equi-join, and why attribute-name collisions force a rename.
Explain that the definition is logical and that the identity is what licenses predicate pushdown and free join reordering, plus why equality keeps more evaluation strategies open.
Discuss selectivity estimation as the practical consequence of the definition, and when a deliberate product is the right modelling tool for grid or parameter expansion.
## 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.
- Is the theta-join a primitive operator of relational algebra?No. It is derived: by definition it equals a selection applied to the Cartesian product, and the product plus selection are the primitives. The join gets its own notation because it is overwhelmingly the common case and because engines implement it as a single operator rather than as two.
- Why does the equality-versus-inequality distinction matter if both are just selections over a product?Logically it does not — both denote the same kind of filtered product. It matters underneath, because equality lets matching tuples be located by hashing or by position in a sorted order, so qualifying pairs can be produced without enumerating all combinations. An arbitrary inequality gives no such handle, so far more combinations must be considered.
- You see an unconditional Cartesian product in a plan for a query that specified join conditions. What does that suggest?Usually that the condition could not be used as a join predicate between those two relations — it may reference a third relation, so the two must be combined before it can be applied, or it may have been written in a form the optimizer cannot treat as a join condition. Occasionally it is deliberate, when one side is a single row or a tiny generated set and crossing is genuinely the cheapest option.
saying these in an interview costs you the question
- Believing the engine literally materialises the Cartesian product and then filters it
- Thinking a Cartesian product is always a bug rather than sometimes deliberate
- Claiming theta-join is a primitive operator alongside product and selection
- Assuming an equi-join removes the duplicate join column automatically — that is natural join
- Saying inequality joins are impossible rather than merely more expensive