views:

368

answers:

3

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?

+2  A: 

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.

Adam Robinson
is this what's referred to as an 'adjacency list'?
ninesided
No, this is a tree structure defined from the bottom up (in other words, you define children by indicating a parent on the child, rather than indicating a list of children on the parent). An adjacency list allows for cyclical connections, whereas a tree does not.
Adam Robinson
so to build the tree would I not need a query for each node to determine the parents? Or would that depend on the RDBMS? I think I've seen CONNECT_BY_PRIOR used in Oracle for tree-walking.
ninesided
The tree construction would ideally be done client side, as SQL isn't suited for (and, realistically, doesn't support) recursion, at least in queries. You could go n-levels deep in your parent-child relationships if you needed to, but you'd basically have to have one left self join for each level.
Adam Robinson
Sounds like it might fit the bill thanks!
ninesided
+2  A: 

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.

cdonner
+1  A: 

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.

Cymen