A matcher emits only direct 'same entity' pairs between customer rows: what does the transitive closure of those pairs give you?
answer
- smallest relation with the property
- adds pairs, never removes them
- one or more steps along a chain
- transitive step goes last
- one wrong pair fuses two classes
basics
~20 sThe smallest transitive relation containing every reported pair: two rows are related when a chain of reported pairs links them. Closing reflexively and symmetrically too gives the smallest equivalence containing the pairs, which is the grouping the matcher implies.
solid answer
~40 sA **closure** is the smallest relation that contains the original pairs and has the property you are adding. The transitive closure relates `a` to `b` exactly when some chain of one or more reported pairs runs from `a` to `b`. To turn a matcher's output into groups you want the **equivalence closure** — close reflexively, then symmetrically, then transitively, in that order — and the result is the unique smallest equivalence containing the reported pairs. Two properties follow and both matter operationally. Closure only ever **adds** pairs, so it can merge classes and can never split one; and because merges chain, `n - 1` reported pairs are enough to fuse `n` rows into a single class. One wrong pair therefore fuses two entire classes, not two rows.
go deeper
Remember the phrase 'smallest relation that contains the pairs and has the property', and that transitive closure means 'linked by a chain', not 'reported directly'.
Explain why the closure is unique, and why the order reflexive, symmetric, transitive matters — the worked case of two pairs sharing a middle row makes the wrong order visible.
Bring the operational consequences: n - 1 pairs collapse n rows, a false pair fuses two whole classes, and closure can never undo a merge it made, so the class-size distribution is the metric to watch.
Treat taking the closure as a decision about what the business means by identity, not a formatting step, and require the chain length and class-size risk to be stated before it is adopted.
## What a closure is Given a relation `R` and a property, the **closure of `R` under that property** is the smallest relation that contains `R` and has the property. 'Smallest' is what makes it well defined and worth naming: many transitive relations contain your pairs — the relation that relates absolutely everything is one of them — but exactly one of them adds nothing that is not forced. For a matcher that emits only direct pairs: - The **reflexive closure** adds `a` to `a` for every row. - The **symmetric closure** adds the reverse of every reported pair. - The **transitive closure** adds `a` to `b` whenever a chain of one or more pairs runs from `a` to `b`. - The **equivalence closure** is all three, and it is the smallest equivalence relation containing the matcher's output — that is, the grouping the matcher implies whether or not anyone intended it. ## The order of closures is not free Closing reflexively, then symmetrically, then transitively produces an equivalence. Doing it in another order can leave you with something that is not transitive at all, which is a subtle defect because the result still looks symmetric and complete. Take a matcher that reports exactly two pairs: A with B, and C with B. 1. **Transitive first.** Nothing chains — there is no pair leaving B — so the transitive closure adds nothing. 2. **Symmetric second.** Now the relation holds A-B, B-A, C-B and B-C. 3. **Check transitivity.** A relates to B and B relates to C, so transitivity demands A relates to C. It does not. The result is symmetric and *not* transitive. Done in the other order — symmetric first, then transitive — the chain A-B-C is present when the transitive step runs, so A and C are joined and all three rows land in one class. The general rule is that closing transitively last preserves what the earlier closures established, while closing symmetrically last can introduce fresh chains that nothing ever resolves. ## What the closure costs you The closure is the smallest equivalence containing the pairs, and that minimality is a guarantee about what is added, not a promise that little is added. - **Merges chain.** Each reported pair can join two classes, so `n - 1` pairs arranged in a chain collapse `n` rows into a single class. Nine hundred rows joined by a chain of near matches need only 899 pairs to become one customer. - **One wrong pair is not one wrong merge.** A spurious pair between two rows fuses the entire class of the first with the entire class of the second. The blast radius of a false pair is the product of two class sizes, not two rows. - **Closure only adds.** There is no 'closure' operation that removes a pair the matcher should not have emitted. If a pair is wrong, it has to be prevented, corrected at the source, or the relation rebuilt without it — the closure will faithfully propagate whatever it is given. | Question | Answer | |---|---| | Can closure split a class that closure created? | No. It only adds pairs, and adding pairs can only merge classes. | | Is the closure unique? | Yes — it is the smallest relation with the property, and that is unique. | | Does a small number of pairs imply small classes? | No. A chain of `n - 1` pairs yields one class of `n`. | | Does closure make the matcher's rule transitive? | No. It builds a new relation; the matcher's own verdicts are unchanged. | ## Reading the result honestly The closure answers a precise question — 'which rows are linked by a chain of reported matches?' — and it is the right answer to that question. What it is not is a verdict on identity, because the chain interpretation is a *choice*: the matcher never claimed that the two ends of a chain are the same entity. Taking the closure is therefore an explicit decision to trust chaining, and it should be made deliberately, with a view on how long the chains get and how large the resulting classes are. Reporting the size distribution of the closed classes is the cheapest early warning available: a single class holding an implausible share of the table is the signature of a chain that ran away, and it shows up in the distribution long before anyone notices in the merged records. How such a relation is computed or maintained as pairs arrive is a separate question with its own data structures; the mathematics here only tells you what the answer must be.
- Why is the transitive step taken last when building an equivalence closure?Because closing transitively over an already-symmetric relation keeps it symmetric, while adding reverse pairs after a transitive step can create fresh chains nothing resolves. With reported pairs A-B and C-B, closing transitively first adds nothing, and the later symmetric step leaves A-B and B-C without A-C — symmetric but not transitive.
- How many reported pairs does it take to collapse 900 rows into a single class?899. Every pair can merge at most two classes into one, so reducing 900 separate classes to one takes 899 merging pairs — a single chain is enough. That is why a sparse matcher output is no assurance of small groups: sparsity limits the number of merges, not the size of the class they produce.
- The closure created a class that is clearly wrong. Can you close the relation differently to undo it?No. Closure only adds pairs, and adding pairs can only merge classes, never split them. The fix has to happen upstream — suppress or correct the offending pair and rebuild the relation from the corrected set — or the closure will keep faithfully propagating it.
saying these in an interview costs you the question
- Calls any transitive relation containing the pairs the closure
- Thinks closure can drop a pair that looks wrong
- Applies the symmetric closure after the transitive one
- Assumes few reported pairs imply small classes
- Confuses the closure of a relation with a similarity threshold
- Says closure makes the original matching rule transitive