Yet another way to model hierarchies

I'm seriously considering to use a nested set model, but I'm still not too happy about all the overhead involved.

I reread the article by Mike Hillyer, especially the bit that handles inserting new nodes. I like the function I wrote because it uses a single insert statement to handle both the rearrangement of the tree as well as the insertion of the new node. This also relieves me from the task of explicitly locking tables.
On the other hand, the wee lines Mike uses to perform an insert seem so elegant, that I can't help thinking I'm doing something horribly wrong. But then again, in Mike's article, the user that's inserting the nodes somehow magically knows where to make room in the tree. The whole point of using a hybrid model like I want to, is to allow for easy inserts (and updates for that matter, although I'd still have to implement it) as well as straighforward, efficient extraction. On the other hand, what I really want is to encapsulate all the tree maintenance within triggers, but I know already that this approach will not be easy to realize in MySQL.
Think of it, I would want to build triggers that handle insert,update and delete, but in order to insert or to update or to delete, I would have to rearrange the tree and run some updates as a side effect. This would of course fire my update trigger, which would have to be so smart as to prevent reentry. The fact that mysql only supports row triggers makes it all very cumbersome.
In Oracle or MSSQL I'd probably solve this by writing a view with INSTEAD OF triggers. These triggers would perform the necesary actions in the base table, and everything would be hunky dory.
The table would not be granted to anyone, but the view would. The view wouldn't even expose the left and right attributes upon which the nested set model relies. Anyway, I can't do this in MySQL, not now anyway, so I'm still willing to use other soltions.

Now, I have not yet investigated it thoroughly, but I think that, besides the hybrid solution, there's another way to handle hierarchies that is about as intuitive as the adjacency list model, and yet nearly as manageable as the nested set model when it comes to extracting data from it. I don't know if there's an official name for it, but I will call it the 'ordered level' model until someone prompts me for something better than that.

create table ordered_level(
    id int unsigned not null auto_increment
,   scope int unsigned not null
,   position int unsigned not null
,   level int unsigned not null
,   label varchar(32) not null
,   constraint pk_ordered_level
        primary key (id)
,   constraint uk_ordered_level
        unique (
            scope
        ,   position
        )
);

insert into ordered_level(scope,position,level,label)values
 (1,1,1'Clothing')
,(1,2,2'Footwear')
,(1,5,2'Suits')
,(1,3,3'Shoes')
,(1,4,3'Socks')
,(2,1,1'Food')
,(2,2,2'Beverages')
,(2,5,2'Pastry')
,(2,3,3'Alcoholic')
,(2,4,3'Non-Alcoholic')

Like the nested set model, the ordered level model may be seen as a serialization of the depth first traversal of the tree underlying the hierarchy. The difference with the nested set as described by Joe Celko and Mike Hillyer is that instead of maintaining a left_node and a right_node property, we now rember only the position and level properties.

The position is quite like left_node in the nested set in that it stores a depth first traversal path through the tree. The level is needed to add depth to the tree. Together, level and position are sufficient to maintain the hierarchy.

The scope property is there to allow for multiple trees. So, the position reflects a depth first traversal within the tree identified by scope. The advantadge to me previous attemt is that it's now a lot easier to keep trees separate. This is reflected in updates: instead of having a single insert potetially update the entire forest, the worst what can happen here is only an entire tree needs to be updated.

Querying is not very hard compared to the original nested set, and some queries are actually easier:

/**
*    printing an entire tree
*
*/

select     scope
,          id
,          position
,          level
,          concat( 
               repeat(' ',4*(level-1))
           ,   label
           ) label
from       ordered_level ol
order by   scope
,          position


/*
*    printing a tree starting with an arbitrary node
*
*/

select     r.scope                   scope
,          d.position                position
,          r.id                      rid
,          r.level                   rlevel
,          r.label                   rlabel
,          d.id                      did
,          d.level                   dlevel
,          concat(
               repeat(' '
           ,  (d.level-1)*4)
           ,   d.label
           )                         label
from       ordered_level   r
inner join ordered_level   d
on         r.scope       = d.scope
and        r.position   <= d.position
and        r.level      <= d.level
where      d.position   <  (
               select coalesce(min(position),d.position+1)
               from   ordered_level n
               where  n.scope = r.scope
               and    n.level = r.level
               and    n.position > r.position
           )
order by   r.scope
,          r.level
,          r.position
,          d.position

For the latter ,there's a variant that does not need a correlated subquery:

select     r.scope                   scope
,          d.position                position
,          r.id                      rid
,          r.level                   rlevel
,          r.label                   rlabel
,          d.id                      did
,          d.level                   dlevel
,          concat(
               repeat(' '
           ,  (d.level-1)*4)
           ,   d.label
           )                         dlabel
from      (select    r.id            id
           ,         r.scope         scope
           ,         r.position      position
           ,         r.level         level
           ,         r.label         label
           ,         min(n.position) next_position
           from      ordered_level r
           left join ordered_level n
           on        r.scope    = n.scope
           and       r.level    = n.level
           and       r.position < n.position
           group by  r.id
           ,         r.scope
           ,         r.position
           ,         r.level
           ,         r.label
          ) as r
inner join ordered_level     d
on         r.scope         = d.scope
and        r.position     <= d.position
and        r.level        <= d.level
where     (r.next_position > d.position
or         r.next_position is null)
order by   scope
,          r.level
,          r.position
,          position

Getting all the leafs is harder than in the nested set though:

/**
*    Getting all the leafs
*
*/

select     *
from       ordered_level ol
where not exists (
           select null 
           from   ordered_level p
           where  p.scope = ol.scope
           and    p.level > ol.level
           )

Getting all the roots is a similar query:

/**
*    Getting all the roots
*
*/

select     *
from       ordered_level ol
where not exists (
           select null 
           from   ordered_level p
           where  p.scope = ol.scope
           and    p.level < ol.level
           )

When we don't want to make the strucure redundant by combining it with the adjacency list model, we must resort to something like this to retrieve a parent or the children:

/**
*
*    Getting the parent
*/

select     c.label
,          p.label
from       ordered_level c
left join  ordered_level p
on         c.scope    = p.scope
and        c.position > p.position
and        c.level    > p.level
where      p.position = (
               select max(pp.position)
               from   ordered_level pp
               where  pp.scope = c.scope
               and    pp.position < c.position
               and    pp.level    < c.level
           )
or         p.position is null


/**
*
*    Getting the children
*
*/
select     r.id
,          r.level
,          r.label
,          d.id
,          d.level
,          d.position
,          d.label
from       ordered_level   r
inner join ordered_level   d
on         r.scope       = d.scope
and        r.position   <= d.position
and        r.level      <= d.level
where      d.position   <  coalesce((
               select min(n.position)
               from   ordered_level n
               where  n.scope = r.scope
               and    n.level = r.level
               and    n.position > r.position
           ),d.position+1)
and        d.level = r.level + 1
and        r.id = 18

Getting all ancestors is similar:

/*
*
*    getting the ancestors
*
*/
select     a.id
,          a.position
,          a.level
,          concat( 
               repeat(' ',4*(a.level-1))
           ,   a.label
           ) label
from       ordered_level c
inner join ordered_level a
on         c.scope     = a.scope
and        c.position >= a.position
and        c.level    >= a.level
where      a.position = (
               select   max(aa.position)
               from     ordered_level aa
               where    aa.scope = c.scope
               and      aa.level = a.level
               and      aa.position <= c.position
               group by aa.level
           )
and        c.id  = 16

For those who are wondering: no, I did not just make this model up. I picked it up working with Microsoft Project. When you save a project in the database, the task list is stored according to such a datamodel. I've known that structure for quite some time, but only now I see the resemblance to the nested set, in that this too relies on linearization of the depth first traversal of the hierarchy.