A merge pipeline groups customer rows by a 'same person' rule: which three properties must that rule satisfy for the groups to be well defined?
answer
- three properties, not two
- every row matches itself
- direction must not matter
- chains must close
- classes: disjoint and covering
basics
~20 sReflexivity, symmetry and transitivity. A rule with all three is an equivalence relation, and only then does it cut the rows into disjoint groups where every row lands in exactly one group, whichever row you start from.
solid answer
~40 sThe rule has to be an **equivalence relation**: reflexive (every row matches itself), symmetric (if `a` matches `b` then `b` matches `a`), and transitive (if `a` matches `b` and `b` matches `c` then `a` matches `c`). Those three are exactly what is needed for the classes `[a] = { x : x matches a }` to partition the table — non-empty, pairwise disjoint, covering every row. Reflexivity is what makes the classes cover everything; symmetry and transitivity are what stop two classes from partially overlapping. The practical payoff is that 'the group of this row' becomes a property of the data rather than of the order the pipeline happened to read it in. Antisymmetry is a different property that belongs to ordering rules, not grouping rules.
go deeper
Memorise the three names and one sentence each: a row matches itself, matching works both ways, and matches chain. Those three are what 'equivalence relation' means.
Be able to derive the groups from the properties: classes are non-empty because of reflexivity, and cannot partially overlap because symmetry plus transitivity force two overlapping classes to be the same class.
Show how you would audit a real matching rule: the absent-field case for reflexivity, argument swapping for symmetry, and a hunt for one counterexample triple for transitivity.
Frame it as a contract other systems depend on: if the identity relation is not an equivalence, every downstream key, join and count built on 'the customer' is defined by traversal order rather than by data.
## A rule is a relation, and a relation is just a set of pairs A 'same person' rule is a binary relation `R` over the rows of the customer table: for any two rows `a` and `b` it either holds (`a R b`) or it does not. Nothing about a rule being written in code makes it well behaved. The three properties below are the checkable conditions that turn an arbitrary yes/no rule into something you can group by. - **Reflexive** — for every row `a`, `a R a` holds. This sounds free and is not: a rule phrased as 'both rows carry the same non-empty account email' fails it for every row whose email is missing, because such a row does not even match itself. - **Symmetric** — whenever `a R b` holds, `b R a` holds too. A rule that reads one row's fields as the 'candidate' and the other's as the 'reference' can quietly fail this, and then 'is this row the same as that one?' has two different answers depending on which one you name first. - **Transitive** — whenever `a R b` and `b R c` hold, `a R c` holds. This is the one that near-match and threshold rules break. A relation with all three is an **equivalence relation**. ## Why exactly those three give you groups Define the **class** of a row as `[a] = { x : x R a }`. The claim an interviewer is really testing is that an equivalence relation partitions the set, and the argument is short enough to say out loud: 1. **The classes cover everything.** Reflexivity puts `a` inside `[a]`, so no class is empty and no row is left out of every class. 2. **The classes do not partially overlap.** Suppose some row `c` lies in both `[a]` and `[b]`. Then `c R a` and `c R b`. Symmetry turns the first into `a R c`, and transitivity then gives `a R b`, from which the same two properties give `[a] = [b]`. So two classes are either identical or share nothing at all. 3. **Therefore every row lies in exactly one class**, and the classes are the groups the pipeline emits. The converse also holds: any partition you can draw on the table induces an equivalence relation — 'in the same part as'. Equivalence relations and partitions are two descriptions of the same object, which is why a grouping specification and a matching rule are the same specification written twice. ## What each broken property looks like downstream | Property broken | A rule that breaks it | What the pipeline shows | |---|---|---| | Reflexivity | matches only on a field that may be absent | rows that belong to no group at all, or singleton groups created inconsistently by whichever code path notices | | Symmetry | a one-directional comparison, or a normalized value compared against a raw one | membership answers that depend on argument order; a row inside a group that the group does not claim back | | Transitivity | 'close enough' scores, distance thresholds, shared-token heuristics | the grouping stops being a property of the data and becomes a property of the traversal order | ## Antisymmetry is a different job **Antisymmetric** means: if `a R b` and `b R a` both hold, then `a` and `b` are the same element. That is a property of *ordering* rules — precedence, supersession, ranking — not of grouping rules. 'Record A supersedes record B when A is strictly newer' is transitive and antisymmetric, but it is neither reflexive (a record is not strictly newer than itself) nor symmetric, so it can rank records and can never group them. The two properties are not opposites, and that is the detail candidates get wrong. A rule can be both symmetric and antisymmetric — but only when it relates nothing except an element to itself, which is to say only when it is equality restricted to some subset. Plain equality is the everyday example. ## Checking a rule before you trust it 1. **Reflexivity by inspection of the missing case.** Feed the rule a row with every optional field empty, compared against itself. If the answer is not 'same', the rule is not reflexive. 2. **Symmetry by swapping the arguments** on a sample of pairs, including pairs where one side is normalized and the other is not. 3. **Transitivity by hunting for a witness**: a triple where the first two pairs hold and the third does not. One witness is enough to prove the rule is not an equivalence, and no amount of passing samples proves it is — that has to come from the shape of the rule, and the shape that guarantees it is comparing a derived key for equality.
- Which of the three properties is what guarantees the groups cover every row, leaving none behind?Reflexivity. It puts every row inside its own class, so no class is empty and no row is missing from all of them. Drop it and a row that matches nothing — typically one whose matching field is absent — belongs to no group, and different parts of the pipeline will disagree about whether it exists as a group of one.
- 'Record A supersedes record B when A is strictly newer.' Why can that rule never define groups?It is irreflexive (nothing is strictly newer than itself) and asymmetric (at most one direction ever holds), so two of the three equivalence properties fail. It is transitive and antisymmetric, which makes it an ordering relation: it tells you which record wins, never which records belong together.
- Can a rule be both symmetric and antisymmetric at the same time?Yes, but only in one situation: when it never relates two distinct elements at all. Antisymmetry says that two-way agreement forces the elements to be identical; symmetry says agreement is always two-way. Together they force every related pair to be a pair of one element with itself, so the rule is equality restricted to some subset.
A filing room where each customer has exactly one drawer: any clerk who picks up any card in a drawer is led back to that same drawer. A rule that lets one card belong in two drawers is not a filing scheme at all.
saying these in an interview costs you the question
- Says a rule that returns true or false automatically partitions the set
- Treats reflexivity as free without checking rows with absent fields
- Calls a similarity score above a threshold an equivalence relation
- Thinks two classes may partially overlap for borderline rows
- Confuses antisymmetry with symmetry when auditing the rule
- Believes symmetry alone is enough to define a row's group