What is the best way to model user defined hierarchical relationships in a database?

Question

Essentially, I want the user to be able to define a hierarchical model, but then I need to allow the user to store data within their defined model. Does this make sense? So the users will be able to create new "unit types" to be organised in a hierarchical way and decide how units of these types are allowed to be organised. A simple example: in my hypothetical interface a user creates three unit types, trunk, branch and leaf. The user then defines the relationships between them. A leaf can exist at any point in the hierarchy, a branch must have a trunk as a parent. The user can then creates instances of these unit types (as units) and can organise them according the rules defined in their model... is there a good way of doing this in the database?

Answer 1

This is an extremely broad question, but this may point you in the right direction. Note that you're only going to be able to store the relationship rules in the database. Enforcing them will be up to your client code. Try this on for size..

unit:
    unit id,
    name,

unit relationship:
    unit id,
    foreign unit id

You can then use your unit relationship table in the following way..

unit id relates to the unit it's describing. foreign unit id should be nullable.

A unit with no relationship records can only exist at the root of the heirarchy. A unit with a null foreign unit id can have any other unit as its parent. Otherwise, a unit must have another unit as its parent, and it's type must be one of those defined in its relationship records.

As for storing the instances themselves, that should be straightforward..

instance:
    instance id,
    unit id,
    parent instance_id

I'm sure there would be other fields you'd need (name, for instance), but I assume you get the drift.

Answer 2

You need to implement three concepts:

• the "unit types" and their allowed associations
• the hierarchy
• the actual units

These concepts can coexist more or less independently in the model, but work together.

create table unittype
(
    id int;
    name varchar(20);
)

create table unitrelationship
(
    id int;
    parent_id int;
)

You could model the hierarchy as self-referencing table:

create table hierarchy
(
    id int;
    parent_id int;
    unit_type_id int;
    unit_id int;
)

You can then have your unit instances in one or more tables and do with them what you described.

create table unit
{
    id int;
    ....
}

The good news is that you are constraining only the allowed parent types, which can be easily enforced in a user interface, for instance by picking the parent from a list of all existing units of the allowed type.

Answer 3

I'm working on a similar issue although I need to support multiple hierarchies (one set of children, multiple hierarchical views). I've found Joe Celko's "Trees and Hierarchies in SQL for Smarties" (ISBN: 1558609202) useful. I'm still working on the problem but it comes up so often when discussing this topic that it seemed appropriate to mention.