# Express semantic duplicates of records formally

I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates. Hard ones are a 100% match; where's only true or false- Semantic ones have different variations but still are representing the same thing.

Now I'd like to write it as a set but actually I have forgotten all about this.

Here are my thoughts about it. All 4 records are part of the Set "Persons" p

For both: Values are already filtered according to custom settings.
Hard Duplicates

{[Name]Max; [Surname] Mustermann} ≙

{[Name]Max; [Surname] Mustermann} ≠

{[Surname]Max; [Name] Mustermann} ≠

{[Name]Max; [Surname] M.}

Semantic Duplicates

{[Name]Max; [Surname] Mustermann}

{[Name]Max; [Surname] Mustermann} ≙

{[Surname]Max; [Name] Mustermann ≙

{[Name]Max; [Surname] M.} ≙

Any help is appreciated

• Do I understand correctly that the question is how express semantic duplicates formally? In order for that to work, you have to specify exactly when two records are semantically equivalent. So far, you have given only one example -- that's not enough. (And I'll just note that, at least in Germany, there are "palindrome" names like "Martin Hanna" and "Hanna Martin" -- two different individuals with probably different gender.) – Raphael Apr 12 '16 at 9:19
• Community votes, please: is this unclear? – Raphael Apr 12 '16 at 9:20
• I actually developed already the whole program and it works as intended. You're right in that that whe have a huge amount of palindromes, but in this program, it checks about 20 attributes of the data, so I'm pretty sure these won't be marked as duplicates. Indeed, the given amounts aren't chosen well on a second tought. I wanted to keep it simple (also had only a few minutes at this moment). I will edit the Q later. – pguetschow Apr 12 '16 at 12:43

The basic mathematical concept at play here is a binary relation. For a certain measure of similarity, two records are either similar or not. Formally, a binary relation assigns a truth value (true or false) to every ordered pair of records. The usual notation to state that two records are similar is $r_1 \approx r_2$ where $\approx$ is the notion of similarity. There can be multiple notions of similarity (allowing for more or fewer differences between records).

Given the intended purpose, any notion of similarity should be reflexive: a record is similar to itself. Any notion of similarity should probably be symmetric: if $r_1$ is similar to $r_2$ (for a given notion of similarity) then $r_2$ is similar to $r_1$ for that same notion of similarity. It's less clear whether the similarity relation should be transitive, which would make it an equivalence relation. If $r_1$ is similar to $r_2$ and $r_2$ is similar to $r_3$, does that make $r_1$ similar to $r_3$? Or in other words, is a duplicate of a duplicate a duplicate? If your intuition of similarity is that the records are at most a certain distance from each other, then no (this thread on Math.SE discusses this intuition). But if you think of all records falling into a well-defined bucket, with sufficiently similar records ending up in the same bucket, then you have an equivalence relation, and the buckets are called equivalence classes. If you have a way of defining a privileged element in each equivalent class (a “completed” or “presentation” version of the record), that's called a canonical representation.

Equality is the finest (i.e. most discriminating) equivalence. It is normally written $=$. A generic equivalence relations is typically written $\equiv$. If you need to consider more than one equivalence relation, then the typical notation scheme is to use $=$ or $\equiv$ with some ornaments on it.

The terminology “hard duplicate” or “soft duplicate” isn't standard, but it's comprehensible. “Equal” vs. “equivalent” or “equal” vs. “similar” are more standard terms.

To define an equivalence, a typical approach is to give rules: “if $r_1$ and $r_2$ are such that … then the two records are equivalent”. For example, you might have a rule that if two records are the same except for letter case variations on the name field then they're equivalent. Two records are equivalent if there's a way to find a chain using those rules plus the “built-in” reflexivity, symmetry and transitivity rules from one record to the other.

To define a non-transitive similarity, a typical approach is to define a distance between records.

The general problem of determining when records in a database should be treated as representing the same entity is called data normalization. With respect to database design, that's database normalization.

• I struggle to see how recounting basic textbook material answers the specific (if rather unclear) question. – Raphael Apr 12 '16 at 12:43
• @Raphael: As someone, who just started getting into CS, I'm really thankful for this brief recitation of "texbook-material" – pguetschow Apr 12 '16 at 12:48
• @TechTreeDev I understand that, but there is little large-picture need for multiple answers of this kind. Gilles, should this be a reference post? The question would probably need some rewriting then. – Raphael Apr 12 '16 at 12:57