GXJoin: Generalized Cell Transformations for Explainable Joinability
Published at ADBIS 2024 in Bayonne, France.
The problem
Say you are building profiles of faculty members from three sources. One table lists names like Davood Rafiei, Mario Antonio Nascimento and Osmar Zaiane. Another lists contact addresses like [email protected], [email protected] and [email protected]. A third writes the same people as D. Rafiei, M. A. Nascimento and O. Zaiane.
Every row has a match in the other tables, and a normal join finds none of them. The column names are fine. The mismatch is inside the values. Usually somebody then writes the rewriting rules by hand, once per dataset, which does not scale and leaves the rules invisible to everyone else.
Why it matters
A program can infer those rules from a few example pairs, but what it typically returns is a set of narrow rules, each covering only a few rows. One rule handles the plain name, a second handles the one with a middle name, a third handles the person whose address skips the initial.
That is really just a lookup table. It covers the rows it was built from and nothing else, so every new row that does not fit needs a rule of its own, and you end up with almost as many rules as rows. What you want instead is a rule that caught the pattern people were actually following, because that one keeps working on new rows.
Simplicity is the other half of it. A join is only useful if someone is willing to act on the results, and that means being able to check how they were produced. A rule made of two or three plain steps can be read and judged in seconds. A long, intricate one cannot, and it is also the one more likely to have fitted a coincidence rather than the convention.
Main idea
Prefer rules that are general and simple.
GXJoin takes rules fitted to particular rows and widens them. It lets a rule count from the end of a value as well as from the start, so a surname stays easy to find whether or not a middle name sits in the way. It lets part of a rule be optional, or repeat as often as needed, so one rule covers people with one given name and people with three. It tries both tables as the starting point rather than guessing, since the column with longer text is not always the more informative one. And when two rules fit the data equally well, it keeps the simpler one.
The result
GXJoin was tested on two real world benchmarks, one of noisy tables collected from the web and one of spreadsheet cleaning problems posted by Excel users. It needs fewer rules than the previous state of the art, each covering more rows and each simpler to read, and the joins built on those rules are more accurate. The advantage is largest exactly where it should be, on the messier web tables and when only a small sample is available to learn from.