nasloan.com

A Tricky Problem

We are going to create a simple database which stores states, counties and cities and the links between them. You might expect to design a database in which there is a Cities table, which has a foreign key linking it to the Counties table, which has a foreign key linking it to the States table. This is a pretty reasonable schema. Each county may contain many cities, but each city may only be in one county. Each state may contain many counties, but each county may only be in one state. Perfect you say? Not exactly.

In our great country, we allow all sorts of freedoms. One such freedom is the right for government officials to screw up simple and basic organizational heirarchies. While it is true that most cities are contained within a single county, there are actually many that are not. One very notable example is New York, NY, which spans the counties of Queens, Kings, Bronx, Richmond, and New York.

Back to the drawing board then. We need a design that supports a many-to-many relationship between the Counties table and the Cities table. More importantly every city and every county belongs to a single state, so every Cities or Counties record ought to link to exactly one States record. So far, so good.

The trouble starts when we consider that for any pair of counties and cities, both the county and city must belong to the same state. Sure, it's trivial for our application to verify that Counties.state_id is the same as Cities.state_id on insert, but I'm the kind of guy that likes to deal in certainties whenever I can, and in software you can't get much more certain than a database constraint.

Solving the Puzzle

Now that we've got a pretty good grasp on the problem, let's take a look at how to fix it.

Above is a diagram illustrating the relationships between the tables. Below this paragraph is the SQL DDL for the table, with the concepts we've discussed applied.

CREATE TABLE States (
    id VARCHAR(2) PRIMARY KEY,
    name VARCHAR(15)
);
CREATE TABLE Counties (
    id INTEGER AUTOINCREMENT,
    state_id VARCHAR(2) REFERENCES States (id),
    name VARCHAR(20),
    PRIMARY KEY (id, state_id)
);
CREATE TABLE Cities (
    id INTEGER AUTOINCREMENT,
    state_id VARCHAR(2) REFERENCES States (id),
    name VARCHAR(30),
    PRIMARY KEY (id, state_id)
);
CREATE TABLE States_Counties_Cities (
    state_id VARCHAR(2) REFERENCES States (id),
    county_id INTEGER,
    city_id INTEGER,
    PRIMARY KEY (state_id, county_id, city_id),
    FOREIGN KEY (state_id, county_id) REFERENCES Counties (state_id, id),
    FOREIGN KEY (state_id, city_id) REFERENCES Cities (state_id, id)
);

Because we make the primary key of the Muncipalities and Counties tables include the state_id, we are forced to include it in our reference to them from the States_Counties_Cities table. The trick here is to only include one state_id column, so that it has to serve as the state_id portion of the foreign key to both Cities and Counties. Since we're only using one column, we cannot possibly join a muncipality in one state with a county in another state. Our problem is solved in such a way that we can rest assured that our database's integrity will be preserved.

A Final Thought

I came up with this schema while considering a project that I am working on for a friend's martial arts school. The actual context that I am using this concept in for that project is more complex than this and was difficult to explain to people. I hope this entry has been easy to understand and gives you a chance to think about how a similar concept might be applied to data challenges which you are facing now, or have faced in the past. I had great help in figuring this out from Robert Treat, Alejandro Garcia, and Twist from the #sql channel on Freenode. In fact, the #sql, #sqlite and #postgresql channels on the Freenode IRC network are very helpful places to get answers to any crazy database problem you might dream up.

If you come up with a creative way to apply this, or an interesting problem that it helps solve, please let me know in the comments. Oh, and thanks for reading!

PS: Some early readers reported that the abstract discussion of this concept was muddying the waters a bit in terms of clarity. I've moved that paragraph below, so if you're interested in my abstraction of this whole mess, read on. Otherwise, thanks again for reading!

In Technical Terms…

Table B and table C in the diagram below both have a many-to-one relationship with table A. They also enjoy a many-to-many relationship with eachother through table D. The record in table A that is referenced by table B has to be the same record in table A that is referenced by table C. In other words, table D not only has to join B and C, but also make sure they are talking about the same record from table A. Yikes! A tall order.

The above diagram illustrates a set of tables A, B, C and D which have the following constraints:

Table A:

• Primary Key: a
• Foreign Keys: None

Table B:

• Primary Key: (a, b)
• Foreign Keys: A.a

Table C:

• Primary Key: (a, c)
• Foreign Keys: A.a

Table D:

• Primary Key: (a, b, c)
• Foreign Keys: A.a, (B.a, B.b), (C.a, C.c)

Because the foreign-key to table A is used as a part of the primary key for tables B and C, we must use it to reference tables B and C in table D. The caveat is that instead making an aB column and a separate aC column on table D, we simply create one a column, which is used in the foreign key for table B and table C. This forces the joined records from B and C to share the same foreign key value for table A, and thus is the solution to our problem.