Best design for a tree-like structure database

Question

I'm designing a database in MS Access which is used for tracking the locations of a variety of chemical solutions, made in batches.

Each batch can be split (aliquoted) practically indefinitely. That is, we may manufacture 100g of a product, which is aliquoted into two 50g vials. One is kept in storage, the other is shipped somewhere else and further split into 50 1g vials. These vials may be transported at any time, and may be aliquoted further.

I would like to be able to track the history of any particular vial. Where it has been (and when), including the history of its 'parent' vial and the parents of that.

That is, if I look at the history of vial #7 in the above image, I want to see the history of vial #7, (reverse chronologically, for example), followed by the histories of vials #6, #3 and #8.

I'm struggling to find the best way to record this data; currently I have one main table (plus several lookup tables) which has one line for each 'node'. A node represents a vial being in a location; so each line has an AutoNumber primary key, a 'parent' (the primary key of the previous node - either the previous location of the vial, or the parent vial if it was aliquoted), a 'location' field, the batch number etc.

There is already redundancy here because the batch number is on each node whereas it really only needs to be on the first node after manufacture (it clearly doesn't change when the batch is aliquoted).

So the data structure is the first issue here.

Once I've got the data structure, does anyone have any ideas for how best to show historical data for a vial?

Many thanks

Answer 1

Bill Karwin covers the alternatives well in his presentation. I have a few notes on a similar but slightly different closure table on this page.

The idea is to have one table that represents the parent relation, and another that represents the ancestor relation. All changes to the ancestor relation is a consequence of a change in the parents relation. As an example, adding a child c to a node n means adding the ancestors of n plus n as ancestors of c.

In most DBMS you can use triggers to implement this, but AFAIK ms-access does not support this. Since I don't use Windows and/or MS-Access I cannot verify it but this StackOverflow question appears to mimic triggers, so that can perhaps be of use.

You asked for the best design for a tree like structure, but I don't think there is one best way to solve all such problems. All methods have their strength as well as weaknesses so what I describe above is just another way to deal with them. Hopefully the will at least give you some food for thought.

Answer 2

I would create a separate table for history. If it was me, I would use an auto-increment column for the primary key (historyID) , a column for the vial ID, and a column for a location ID. I would think the vial ID would be foreign key to the nodes table. You could then query against a vial to see it's full history.

Since you don't list what your lookup tables are, I am going going to assume you don't have a history table yet. I am also not sure you have a separate location table, and if you don't I would also use a location table that simply has a autoincrement primary key and a location description the primary key of the location table would have foreign keys in both your node table and the history table.

Since you mention that the batch number is redundant, I would also add a separate batch table that uses auto-increment as the primary key (batchID) along with any columns that would be useful for a batch, (date of manufacture,other information unique to the batch, etc.) The batchID would would then be a foreign key in your node table and although the batch ID might be repeated many times for different nodes, you might be able to remove other redundancies related to the batch in your node table. Of course, since you don't list all the columns that are in your node table, it's difficult to give advice that is not based on some assumptions. As I review my post, I would also put the batchID in the history table. It would give you an easy way to trace the history of the parent batch.

Basically, you want to go through the process of normalizing your database. By the time you normalize, your first main nodes table might end up being a very simple table that provides for the relationships between parent and children vials in a single table. (Some might advocate for a separate table of parent and children vials, but since your manufacturing methods allow for multiple generations, I would keep it in a single table, and keep it simple.)

Sounds like an interesting project.

I hope this all makes sense and is helpful.

Although I have been involved with databases since the days when Access 97 was still current, this is my first post in dba.stackexchange. I've been the accidental DBA for multiple projects at our company and I am finally finding some of the most commonly used resources for help and information on the web DBAs.