Enforcing Transitive Constraints in SQL

By raylu

In this post, we’ll use compound foreign keys to enforce triangular relationships with an example using organizations, teams, users, and a nursery rhyme.

Many webapps like Benchling start with the concept of users and then add a concept of organizations later. In SQL, it’s pretty easy to model a many-to-many relationship between organizations and users. It’s also pretty straightforward to enforce that the association/membership table refers only to organizations and users that exist (via foreign keys).

Just like GitHub, we needed a 3rd level of access control, so we added teams. Users still belong directly to organizations, but they can also belong to any number of teams within that organization (and teams belong to exactly one organization). It’s a little less obvious how to enforce that a user U can’t belong to a team T if T is in organization O but U is not in O — a “transitive” constraint.

These sorts of transitive constraints appear in any app that has this sort of orgs/teams/users setup and in some other cases (nested subfolders, multi-tenancy) discussed at the end. But first, let’s walk through our orgs/teams/users example.

If you happen to have docker installed, you can follow along by running a Postgres container named otu:
$ docker run --name otu -d postgres
 and then pasting the SQL statements into a psql shell:
$ docker exec -it otu psql -U postgres

Ancient lore tells us of man and his cow:

user_id serial PRIMARY KEY,
INSERT INTO users (name) VALUES ('Old MacDonald'), ('a cow');

and this happens to be how many webapps start. But we learn from that same lore (as many webapp developers also learn from their users) that the man and his cow belong to the same farm.

CREATE TABLE organizations (
org_id serial PRIMARY KEY,
CREATE TABLE org_memberships (
org_id INTEGER NOT NULL REFERENCES organizations (org_id),
user_id INTEGER NOT NULL REFERENCES users (user_id),
UNIQUE (org_id, user_id)
INSERT INTO organizations (name) VALUES('MacDonald''s Farm');
INSERT INTO org_memberships (org_id, user_id) VALUES (1, 1), (1, 2);

This puts Old MacDonald and a cow in the same organization.

SELECT users.*, organizations.* FROM users
JOIN org_memberships ON users.user_id = org_memberships.user_id
JOIN organizations ON org_memberships.org_id = organizations.org_id;
user_id | name | org_id | name
1 | Old MacDonald | 1 | MacDonald's Farm
2 | a cow | 1 | MacDonald's Farm

For some farms and some webapps, this is enough. But for many, it is not. Certainly not for MacDonald, who built a secret barn and wanted to ensure access to the barn was limited to a trusted few. At first, he tried securing the secret barn with a password (E-I-E-I-O), but he ran into all the standard problems of a shared password. Eventually, he realized he needed to federate secret barn access through the concept of a “team”.

team_id serial PRIMARY KEY,
org_id INTEGER NOT NULL REFERENCES organizations (org_id),
CREATE TABLE team_memberships (
team_id INTEGER NOT NULL REFERENCES teams (team_id),
user_id INTEGER NOT NULL REFERENCES users (user_id)
INSERT INTO teams (org_id, name) VALUES (1, 'Secret Barn Access');
INSERT INTO team_memberships (team_id, user_id) VALUES (1, 2);

And thus, the cow had access to the secret barn.

SELECT users.*, teams.* FROM users
JOIN team_memberships ON users.user_id = team_memberships.user_id
JOIN teams ON team_memberships.team_id = teams.team_id;
user_id | name | team_id | org_id | name
2 | a cow | 1 | 1 | Secret Barn Access

And all was well… for a while.

Eventually, as happens occasionally, the cow went rogue and started abusing her powers. There was nothing to do but remove her from the farm entirely.

DELETE FROM org_memberships WHERE org_id = 1 AND user_id = 2;

Does this remove all of the cow’s access from the farm? No, it does not! The cow is still in the Secret Barn Access team! We rollback to leave the cow in the farm for the time being.

SELECT * FROM team_memberships;
team_id | user_id
1 | 2

If the secret barn door only checked team_memberships for access, it would have let the cow in despite not being in the organization at all! But the larger issue is that even if if the secret barn door checks org_memberships, it shouldn’t have to. The database shouldn’t be in an inconsistent state.

It’s clear that there should be some kind of constraint on the team_memberships table that stops this from happening. The constraint has something to do with org_memberships, which means it's a foreign key. Right now, team_memberships has nothing to do with organizations, but that's solved by adding an org_id column.

Let’s redo our concept of teams so that MacDonald can manage his farm with proper transitive constraints.

DROP TABLE team_memberships;
team_id serial PRIMARY KEY,
org_id INTEGER NOT NULL REFERENCES organizations (org_id),
UNIQUE (team_id, org_id)
CREATE TABLE team_memberships (
user_id INTEGER NOT NULL REFERENCES users (user_id),
FOREIGN KEY (org_id, team_id) REFERENCES teams (org_id, team_id),
FOREIGN KEY (org_id, user_id) REFERENCES org_memberships (org_id, user_id)

We added an org_id column to team_memberships so that we could create composite foreign keys.

The first one is to the teams table on (org_id, team_id). This simply checks that when you declare a team membership, you also declare the correct organization. Normally, foreign keys are to the primary key of some other table, but teams' primary key is just team_id. We could have made the teams table have a composite primary key, but we instead add a (team_id, org_id) unique constraint on teams to support this foreign key.

The second one is to the org_memberships table on (org_id, user_id) and enforces that team memberships can only exist where organization memberships also exist. This foreign key is what would have prevented us from only removing the cow from the organization without also removing her from the team.

This second key is a bit unusual because not only is it not referencing a primary key, it references an association table. We aren’t enforcing that some referenced model exists (orgs or users), but that some relationship exists (user belongs to org). It's also a little unusual that we are using the org_id column in two foreign keys, but this is how we declare the transitive constraint in SQL.

Now when we re-instate secret barn access

INSERT INTO teams (org_id, name) VALUES (1, 'Secret Barn Access');
INSERT INTO team_memberships (org_id, team_id, user_id) VALUES (1, 1, 2);

we can do so with the confidence that our database won’t let us make a mistake revoking it.

DELETE FROM org_memberships WHERE org_id = 1 AND user_id = 2;
ERROR: update or delete on table "org_memberships" violates foreign key constraint "team_memberships_org_id_fkey" on table "team_memberships"
DETAIL: Key (org_id, user_id)=(1, 2) is still referenced from table "team_memberships".

Besides the orgs/teams/users case, this technique has also been useful in a couple of other places in Benchling. We have a concept of projects with root folders which can have nested subfolders. We store the parent folder of each folder to track the folder tree. One way to find out what project a folder belongs to is to traverse all the way up to the root folder, but this is not great (you need to do as many joins as your depth in the tree or rewrite your queries to use recursive CTEs). The obvious solution is to store the project on each folder, but you might break a transitive constraint if a folder’s project doesn’t match the root folder’s project. This is subtly different from the orgs/teams/users problem because users can belong to many teams but folders can only have one parent. Luckily, since the entire folder hierarchy must belong to the same project, we can enforce this by just looking at the our parent’s project: FOREIGN KEY (project_id, parent_id) REFERENCES folder (project_id, folder_id).

We also approach tenant isolation very similarly to what Sentry describes in this blog post. They have an automatic tenant check that runs as a SQLAlchemy event listener:

@db.event.listens_for(TenantQuery, 'before_compile', retval=True)
def ensure_tenant_constrained(query):
return query.filter_by(tenant=get_current_tenant())

To make something like this possible, we need to have a tenant_id on the models we want to check. Since most of them are not top-level models that directly belong to a tenant (item belongs to a user which belongs to a tenant), this results in another transitive constraint.

Is it always worth enforcing transitive constraints this way? Not necessarily. Besides generally making your data model more complex, it makes moving a team from one org to another harder. You have to move the team and the users at the same time, which means you have to defer constraints. But for things critical enough that you prefer to not be able to make a change without understanding the complexity, this technique is very useful. Benchling’s orgs/teams/users are modeled this way because we believe it’s better for permission changes to fail than be subtly wrong.

Finally, as always, we’re hiring engineers who are excited to make life sciences research faster by solving these sorts of problems.