Home > SQL Server > Modelling trees for RDBMS

Modelling trees for RDBMS

An interesting problem on how to model tree structures with RDBMS came up this week. Google again came to the rescue. There are two approaches to model hierarchies in a RDBMS. The commonly used one is the adjacency list model

emp       boss      salary
===========================
‘Albert’  ‘NULL’    1000.00
‘Bert’    ‘Albert’   900.00
‘Chuck’   ‘Albert’   900.00
‘Donna’   ‘Chuck’    800.00
‘Eddie’   ‘Chuck’    700.00
‘Fred’    ‘Chuck’    600.00

Problem with the adjacency list model is that the boss and employee columns are the same kind ( names of personnel) and therefore should be shown in only one column in a normalized table.

A more efficient way would be the nested sets model

emp         lft  rgt
======================
‘Albert’      1    12
‘Bert’         2    3
‘Chuck’      4    11
‘Donna’      5    6
‘Eddie’       7    8
‘Fred’        9    10

            Albert (1,12)
            /       
          /           
    Bert (2,3)    Chuck (4,11)
                   /         |         
                 /           |            
               /             |             
             /               |               
        Donna (5,6)  Eddie (7,8)  Fred (9,10)

Imagine a little worm crawling anti-clockwise along the tree.  Every time he gets to the left or right side of a node, he numbers it.  The worm stops when he gets all the way around the tree and back to the top.

Here are two common queries which can be used to build others:

1. An employee and all their Supervisors, no matter how deep the tree.

SELECT P2.*
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = :myemployee;

2. The employee and all subordinates. There is a nice symmetry here.

SELECT P2.*
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P2.emp = :myemployee;

This approach will be two to three orders of magnitude faster than the adjacency list model for subtree and aggregate operations.

From a post by Joe Celko on the microsoft.public.sqlserver.programming newsgroup:

http://groups.google.co.in/groups?hl=en&lr=&selm=93kor0%24bls%241%40nnrp1.deja.com&rnum=3

Another good article can be found @ http://www.yafla.com/papers/sqlhierarchies/sqlhierarchies.htm

Also looks like SQL for Smarties will be a good book to read.

Advertisements
Categories: SQL Server
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: