Jailer - Discover Associations

Using "Discover Associations" to Reverse-Engineer a Data Model

When a database schema declares no foreign key constraints, Analyse Database cannot find any association, and every relationship has to be entered by hand. Discover Associations closes that gap without requiring any SQL script: it derives candidates from the column and table names, optionally from the data itself, and verifies every candidate against the database before proposing it.

What is the "Discover Associations" feature and when should I use it?

Use it whenever the data model is incomplete because the database has no foreign key constraints - a common situation with legacy schemas, with schemas managed by third-party applications, and with databases where the constraints have been dropped for load or performance reasons.

It complements Analyse SQL Script: that tool needs a collection of existing queries as input, whereas Discover Associations needs nothing but the database connection. Both tools feed their proposals into the same place, so you can use them one after the other.

How do I open the tool?

Choose

Data Model → Discover Associations

The menu item exists both in the Extraction Model Editor and in the Data Browser. Because the candidates are verified against the data, a database connection is required: in the Extraction Model Editor you are asked to connect if you are not connected yet, in the Data Browser the open connection is used.

The dialog does not start immediately. Set the options first, then click Start discovery.

How are candidates derived from the names?

For every table with a primary key, all other tables are searched for columns that look like a reference to that primary key. Comparison ignores quoting and case. Accepted are:

a column with exactly the name of the primary key column, e.g. ORDER.CUSTOMER_ID → CUSTOMER.CUSTOMER_ID
the table name followed by the primary key column name, e.g. ORDER.CUSTOMER_ID → CUSTOMER.ID
the usual variants of such a name: CUSTOMERID, CUSTOMER_NO, CUSTOMER_NR, CUSTOMER_KEY, CUSTOMER_CODE
singular and plural forms of the table name (CUSTOMERS, CATEGORIES / CATEGORY)
names carrying one of the usual foreign key affixes: FK_, REF_, ID_, _FK, _REF

In addition, the column types have to fit. Columns of the same type always do, no matter which type that is - two RAW(16) columns holding a UUID, for instance. Length and precision play no role there; whether the values really fit is what the data check is for. Columns of different types have to belong to the same category: numeric, short character, date/time or UUID. For everything else - LOBs, binaries, XML, geometries, booleans, long text - differing types are rejected.

For a composite primary key, all of its columns must find a distinct matching column in the other table; otherwise the candidate is discarded.

Why is a column named "ID" not treated as a reference to another table's "ID"?

Because it almost never is one. A primary key whose name says nothing about its table - ID, NO, NR, KEY, CODE, NAME, … - exists in nearly every table, where it is that table's own key. Accepting name equality in such a case would turn every pair of tables into a candidate, and since small key ranges overlap, many of those candidates would even pass the data check.

Therefore, if a primary key consists of generic names only, plain name equality counts as no evidence; only the qualified forms (CUSTOMER_ID, CUSTOMERID, …) are accepted. As soon as at least one column of the primary key has a specific name, name equality is accepted for the whole key - this keeps composite keys such as (ORDER_ID, POSITION) working.

The same applies to a key that is a house-wide convention: if one and the same column combination is the primary key of a large part of the model - a technical object id together with a tenant and a version, for instance - then those columns say nothing about a reference either, because every table carries them. Name equality is then not accepted for that key; the qualified forms and the data scan still are. Without this rule such a schema would turn every pair of tables into a candidate.

Can I enter the naming convention of my own schema?

Yes, and on a schema with its own systematics that is the fastest way to a complete data model. The button Naming rules... opens an editor in which any number of rules can be entered. A rule describes the name of the foreign key column and comes in two flavours.

Template - the column name with the placeholders ${table} for the parent table and ${pk} for its primary key column:

${table}_${pk}	matches PRODUCT_ID → PRODUCT.ID
${table}${pk}	matches PRODUCTID
FK_${table}	matches FK_PRODUCT

Regular expression - matched against the column name, with a group for the parent table and optionally one for the primary key column: ^FK_(?<table>.+)$, ^(?<table>.+)_(?<pk>.+)$. Unnamed groups work too: group 1 is the table, group 2 the key column.

Case and quotes are ignored, and the singular and plural form of the table name are tried.

${pk} is one key column, not the whole key. This matters as soon as a table has a composite primary key. The rule is not applied once per table pair, but once for every column of the primary key, and each of those columns needs its own column in the child table. Take PRODUCT with the key (ID, VERSION, LOCALE) and the rule ${table}_${pk}. It is then checked three times, once per key column:

key column of PRODUCT	${pk} stands for	expected column of the child table
ID	ID	PRODUCT_ID
VERSION	VERSION	PRODUCT_VERSION
LOCALE	LOCALE	PRODUCT_LOCALE

Only if the child table has all three of them does the candidate come about, and its join condition then compares all three pairs. If one is missing, nothing is proposed. A single column may serve only one key column, and the same applies to the pk group of a regular expression.

Often only part of the key is qualified that way, while the rest - a tenant, a version - is named alike in both tables. For that case every rule has the option Remaining key columns match by identical name: if the rule matches at least one key column, the remaining ones may be taken from columns of the identical name, even where name equality is otherwise suppressed. With that option the rule above already finds PRODUCT_ID + VERSION + LOCALE. It is safe here because the rule has already shown that the child refers to this very parent. For a key of a single column the option has no effect.

A rule can also state that its matches are accepted without checking the data. No verification query is then run for them: they are proposed as they are, their confidence stays empty and the evidence says so. Three situations call for it:

the convention is binding anyway, and the queries would only cost time
the tables are empty - the check can confirm nothing there, so without this option such a schema yields no proposal at all
the tables are too large to check

The option is deliberately conservative: it takes effect only if all rules that contributed to a candidate agree, and never if one of its columns was found by a built-in convention. If nothing has to be checked at all and the data scan is off, even the profiling queries are skipped.

A template must contain ${table} and a regular expression must have a table group; otherwise the rule would not depend on the parent table at all and every pair of tables would become a candidate. The editor refuses such rules.

The list does not start out empty. The first time the editor is opened for a data model it is filled with the built-in conventions, written as rules: ${table}_${pk}, ${table}${pk}, ${table}_ID, ${table}ID, ${table}_KEY, ${table}_NO, ${table}NO, ${table}_NR and ${table}_CODE. So what the discovery does is visible from the start and can be shortened or extended. They come with Remaining key columns match by identical name switched on, which is what a composite key usually looks like. Deleting them all is respected - they are not filled in again. To start over from the built-in set, delete the file naming_rules.csv from the folder of the data model; the next time the editor is opened it is filled again.

Three parts of the built-in matching cannot be written as a rule and therefore stay behind the check box Also use the built-in naming conventions:

name equality	a column named exactly like the key column. As a rule this would be ${pk}, which the editor refuses: it does not depend on the parent table. Built in it is guarded by the rules for generic and house-wide keys described above.
affixes	the tolerance towards FK_, REF_, ID_, _FK and _REF around an otherwise matching name.
key without prefix	if the key column repeats the table name (CUSTOMER.CUSTOMER_ID), a child column named just ID is accepted.

Uncheck the box if your schema follows its own systematics and those extras only add noise.

The rules belong to the data model: they are stored as naming_rules.csv in its folder and travel with it when the model is exported. Candidates found this way carry the evidence "Matches a naming rule" and are verified against the data like any other candidate.

How is a candidate verified against the data?

By counting the rows of the child table that have no matching row in the parent table - an inclusion dependency check:

Select count(*) From ORDER A Where A.CUSTOMER_ID is not null and not exists
(Select 1 From CUSTOMER P Where A.CUSTOMER_ID = P.ID)

Rows in which the foreign key is null are ignored, as they are for a real foreign key. Together with the total number of rows with a complete key this yields the fraction of matching rows.

A candidate is only proposed if that fraction reaches the value selected under Min. matching rows (95 % by default). Choose 100 % for a strict check, or a lower value if the database is known to contain orphaned rows.

Candidates from a rule that is marked accepted without checking the data skip all of this: no query is run for them, and their confidence column stays empty because there is no matching quota to report.

The exact statement of every candidate can be found in the Statements tab.

What does the confidence tell me?

It estimates how likely the candidate is a real foreign key, and it combines three things:

the fraction of matching rows determined by the check above
the strength of the name evidence - a name equal to the primary key counts more than a name that merely follows a convention, and both count more than a candidate found by the data scan alone
the number of distinct values of the column: a column holding only a handful of different values matches almost any key by chance and is therefore rated down

The Evidence column spells out what the value is based on, e.g. "Name matches primary key; 12480 of 12500 rows match (20 without parent); n:1". The detected cardinality is shown as well: 1:1 if the values of the column are unique, otherwise n:1. It is displayed for information only and is not written into the data model.

Sort by Confidence to review the most reliable proposals first. A confidence of 100 % is never reported: no heuristic can prove a foreign key, so the final judgement stays with you.

What does the option "Also find candidates without matching column names" do?

It scans the data for columns whose values are contained in a primary key although their names give no hint at all - the case of cryptic column names such as F_042, and of self-references such as EMPLOYEE.MANAGER_ID, whose name does not mention its own table.

Checking every column against every primary key would need a quadratic number of queries. To avoid that, all tables are profiled first - one aggregate query per table gathering the row count and, per column, the number of non-null values, the number of distinct values and the value range. A column pair is only verified if it survives this pre-filter:

the types are compatible
the value range of the column lies inside the value range of the primary key
the number of distinct values is not greater than the number of rows of the parent table
the column has at least three distinct values - flags and constants would only create noise

Composite keys take part as well: the pre-filter runs per key column, and only the surviving columns are combined - at most three per key column and at most four combinations per pair of tables, the most plausible ones first (a column whose name is related to the key column, then the higher number of distinct values). If combinations had to be left out, the number of affected table pairs is reported in the Problems tab - a naming rule resolves those pairs exactly.

For a key that most tables of the model share, the data scan requires in addition that at least one of the columns names the parent table. Without that restriction every table would be proposed as a reference to every other one, because the values of such a key appear everywhere.

Candidates found this way are listed with the evidence "Data scan only" and, unlike the name-based ones, they are not checked in advance - they need to be judged individually.

How much load does this put on the database, and how do I limit it?

Two kinds of statements are executed, and all of them are read-only:

one profiling query per table. Its duration is measured: as soon as one table takes longer than five seconds, the expensive count(distinct …) is dropped for all remaining tables, which is noted in the Problems tab. If a query fails, the table is profiled over a sample of its rows; if that fails too, the table is listed under Problems and takes part in the name-based search only.
one verification query per candidate (a second one only for composite keys).

Every candidate is verified; there is no query limit, so nothing is silently left out. Candidates are verified in the order of their evidence, the strongest first, so the most reliable proposals appear at the top while the run is still going. The status line reports how many queries were executed.

No query timeout is set, just as everywhere else in Jailer. Closing the dialog cancels a running discovery immediately, including the query that is currently running.

How do I interpret the four tabs?

Proposals	The confirmed candidates, with join condition, confidence, cardinality and evidence. The check box in each row decides what is accepted; the column headers allow sorting and filtering.
Already known	Candidates for which an equivalent association already exists in the data model. Informational only - they are not proposed again. A useful cross-check: known associations that reappear here confirm that the heuristic works on this schema.
Statements	Every statement that has been executed, in order - the profiling queries as well as the verification queries. A large run executes far more than fit into a text pane, so only the first 2000 are shown.
Problems	Tables that could not be profiled and candidates that could not be verified, e.g. because of a missing privilege or an expression the database does not support, plus the note when profiling switched to its cheaper mode. Everything else is unaffected.

How do I accept proposals and add them to the data model?

Check the proposals you want to keep. Name-based proposals are pre-checked, data-scan proposals are not. "Select all" and "Deselect all" act on the rows that are currently visible, so you can first filter, e.g. by confidence, and then select the remainder.
Click Accept.
The Data Model Editor opens with the new associations. In it you can rename them, adjust the cardinality and correct the join condition; nothing is written until you save.

Each accepted association receives an auto-generated name of the form P_TableA_TableB (with a numeric suffix if necessary to avoid duplicates) - the same naming as with Analyse SQL Script.

What is not found, and what should I watch out for?

The tool proposes, it does not decide. Known limits:

A table without a primary key can never be a parent. Use Check Primary Keys to find such tables and define the key in the Data Model Editor.
A self-reference whose column name does not mention its own table (e.g. MANAGER_ID in EMPLOYEE) is only found by the data scan.
Composite keys are found by all three ways, but the data scan checks only a limited number of column combinations per pair of tables (see above).
An empty table confirms nothing: without rows the check has no evidence, so no candidate is proposed. The way out is a naming rule marked accepted without checking the data.
Two columns that contain the same small numbers without being related pass the check as a false positive. The confidence rates such cases down, but does not eliminate them - a plausibility check of the column names remains worthwhile.

After accepting, Check referential consistency and the graphical view are good ways of validating the result: an association that pulls in unexpectedly large parts of the database during a subsetting run is usually a false positive.