Sunday, January 27, 2008

Table Design Pattern: Limited Transaction

Welcome to the Database Programmer. This is a blog for anybody who wants to learn about databases. The entries are meant to be simple and easy to read but definitely not dumbed down. Because most of us these days work on web sites of one sort or another, and since all non-trivial websites require a database, there is very good reason to learn how databases really work.

There is a new entry every Monday morning, and the complete table of contents is here. We are currently looking at Table Design Patterns and how they lead to tight and efficient code.

The Example: A School Class Schedule

In this series we are using the example of an application that manages a school of a few dozen faculty and few hundred or perhaps a couple thousand students. Each year the school administration must make up the actual class assignments for each teacher, including what classroom and period each class will be taught in. Then students must be assigned into the classes.

There are five rules that must be followed:

  1. A teacher may not teach a class he/she is not qualified to teach.
  2. No two classes can be given in the same classroom in the same period.
  3. No teacher can be in two places at once, a teacher can only teach one class in one period.
  4. No student can be in two places at once, so no student can be in more than one class in the same period.
  5. A student cannot take the same class again after passing the class once.

Last week's entry showed that rule 1 was an example of the Cross Reference Validation Pattern, and this week we are going to see that rules 2 and 3 are an example of the Limited Transaction pattern. Next week we will look at rules 4 and 5, which deal with the student.

Sidebar: Discovered Requirements

This week the rules are interesting because they are the kind that nobody would ever actually tell you. I call such rules discovered requirements because they are usually discovered by a programmer or database designer while the table design or programming is under way.

These rules will not be in the specification because they are so obvious that the customer would not think to write them down. It is not that the customer considers putting them in and decides not to, the rules simply never come into the customer's mind. They do not tell you these requirements for the same reason they do not tell you that fish live in water and people breathe air.

Nevertheless, if you do not seek out these rules and put them into the application, then you will get a call or an email that something is wrong because a teacher has been put into two rooms at the same time. Make no mistake, the blame always falls on the programmer, because, after all, what idiot would write a program that would let a teacher be in two places at once? It is very very hard to look a customer in the eye and say, "Well somebody really should have told me about that requirement."

Later in this series we will see more about this in an entry I am planning called "The Requirements Will Never Be Correct", but for now we will move on to the actual database design.

Looking At The Table

The table is fairly easy to work out:

     Rule 2                                   Primary Key
         |                                         |
   +-----+-----+                                   |
   |           |                                   |
  XXX     |   XXXX     |   XX     |  XXX     |   XXX    
  XXX     |   XXXX     |   XX     |  XXX     |   XXX      
  XXX     |   XXXX     |   XX     |  XXX     |   XXX      
  XXX     |   XXXX     |   XX     |  XXX     |   XXX      
                  |                   |                       
                   Rule 3: No teacher may be in    
                           two places at once      

The example above is a simple case of multiple unique constraints on a single table. The term "unique constraint" means that one or more columns must have unique values, just like a primary key. These are sometimes called "candidate keys" as well.

Identifying The Pattern: Limited Transactions

Th Limited Transaction Pattern occurs when there are limitations on what transactions are allowed. To see what I mean by a limitation, we will look at a counter-example, a transaction table that has no limitations. A shopping cart is a good example. We would never tell a customer that they may only have one order per day, or that a salepersons may enter only one order per day, or anything else along those lines. But the school example is the opposite, there are several limitations on what kind of transactions are allowed. Right now we are looking at the limitations that can be addressed with unique constraints.


Here is the SQL that will create the table as it is depicted above:

CREATE TABLE schedule (
   classroom char(5)
  ,period    char(5)
  ,course    char(10)
  ,teacher   char(10)
  ,assign_id int IDENTITY
  -- First define the primary key 
  ,primary key (assign_id)
  -- Rules 2 and 3 use additional unique constraints:
  ,constraint unique rooms_xp    (period,classroom)
  ,constraint unique teachers_xp (period,teacher)
  -- Every column in this table is actually a foreign key!
  ,foreign key  (classroom) references classrooms (classroom)
  ,foreign key  (period)    references periods    (period)
  ,foreign key  (course)    references courses    (course)
  ,foreign key  (teacher)   references teachers   (teacher)

Final Recap Of The Pattern

So let's review one final time how we ended up with this table.

  1. We have a transaction table, because we have an interaction between master elements (teachers, courses, classrooms and periods), so we have several foreign keys.
  2. We used an integer primary key as per Rule of Thumb 4 for Transaction Tables.
  3. A classroom is limited to only one course per period, so we add a unique constraint to enforce that.
  4. A teacher is limited to only one course per period, so we add a unique constraint to enforce that.

The pattern we have is the result of a limited transaction table, a table listing transactions in which not every conceivable combination is actually allowed. In this case the limits come from the physical reality that you cannot be in two places at once.

Conclusion: Patterns Reduce Application Code

When I first began working with databases, I had no idea how many problems could be resolved into simple unique constraints and foreign keys. A big step that any code grinder takes towards becoming a real database programmer is realizing how many seemingly complicated and difficult tasks actually resolve down to unique constraints and foreign keys.

Every time you can put a constraint into a database then you reduce the complexity of your application code. If your framework can trap server errors and report them then you have a very simple way to enforce a lot of the business rules of your application.

Next week we are going to look at rules 4 and 5, which relate to rules about the student's enrollment in certain courses.

Next Essay: False Patterns and The Reverse Foreign Key


--DD said...

Ken, let me thank you first for such interesting material. My question relates to the period column, and associated unique keys on teacher and classroom. When I think of period I think about a temporal object describing a start and end time, like "10am - 11am" and "10:30am - 12am", and obviously as strings they are different, but they still "logically" overlap, thus violating the not-be-in-two-places-at-once rule. You mention period is a FK to another table, so that's maybe how you side-step the issue, but what do you do if you must enforce the same "2-places" rule for arbitrary "chunks-of-time" instead of a finite list of periods?

I don't see how I could enforce non-overlapping arbitrary "periods" with just constraints, since I can have a reference table of periods in this case, no?

Thanks for any insights.

--DD said...

Also, where does the IDENTITY in your SQL come from? With Oracle 11g I get:

SQL> create table foo ( id int IDENTITY, state char(2));
create table foo ( id int IDENTITY, state char(2))
ERROR at line 1:
ORA-00907: missing right parenthesis

Since 11g is the first DB I've ever used, I'm curious is what IDENTITY exactly does, and how to emulate it in Oracle. Thanks.

KenDowns said...

DD, with respect to the PERIOD column, in this case it is a simple number that represents 1st period, 2nd period, 3rd period, etc. The resemblance to an interval or range is coincidental.

However, when it comes to ranges or intervals in databases, support is rather thin on the ground. For this reason, I had to build it into my framework (it is described
"" >here
). It works by allowing a range to be part of the primary key of table, so for instance billing rates can be specified for non-overlapping ranges of time by employee, or quantity breaks for items can be specified. This can be extended to foreign keys by allowing a single value to validate against the range. If it is inside the range, the FK is ok, otherwise it fails.

--DD said...

Would you mind outlining the "implementation" technique of such range PKs if I were to try to implement it myself in Oracle independently of Andromeda?

Is it trigger-based? (what else...)

Thanks, --DD

KenDowns said...

DD: triggers will work. You have a query that looks for overlapping ranges and tosses an error if it finds them. The catch is that you have to include the other PK column(s) (if any) in the query, otherwise it will return false matches. Something like:

Select date from table
where between date
and date_end
OR new.date_end between date
and date_end

KenDowns said...

-DD: The "IDENTITY" keyword is a MySQL-ism. I tend to pitch the examples towards MySQL. SQL Server has very similar syntax, but Postgres requires a couple of extra steps. I don't honestly know what the Oracle version is.