Re: double linked list

From: Paul Vernon <paul.vernon_at_ukk.ibmm.comm>
Date: Wed, 12 Feb 2003 10:36:02 -0000
Message-ID: <b2d85d$lco$>

"--CELKO--" <> wrote in message
> >> First, there are missing links in your data ... <<
> ARRGGH! Let me try again:

Third time lucky?


            /        \
          /            \
        Bert         Chuck
                   /    |   \
                 /      |     \
               /        |       \
             /          |         \
        Donna        Eddie        Fred

> CREATE TABLE Parent_Down_Tree
> (parent_id CHAR (8), -- null means child is the root
> child_id CHAR(8) NOT NULL);
> parent child
> ======================
> NULL 'Albert'
> 'Albert' 'Bert'

Scrub this row
> 'Bert' 'Chuck'

> 'Albert' 'Chuck'
> 'Chuck' 'Donna'
> 'Chuck 'Eddie'
> 'Chuck' 'Fred'
> CREATE TABLE Child_Up_Tree
> (parent_id CHAR (8) NOT NULL,
> child_id CHAR(8)); -- null means child is a leaf
> parent child
> ======================
> 'Albert' 'Chuck'
> 'Albert' 'Bert'
> 'Bert' NULL'
> 'Donna' NULL
> 'Eddie' NULL
> 'Fred' NULL
> 'Chuck' 'Donna'
> 'Chuck' 'Eddie'
> 'Chuck' 'Fred'

So the only difference is whether we redundantly mark root or leaf nodes with NULL links? How does this make them different models? If it does, don't we have 4 models:

  1. Mark none
   'Albert'  'Chuck'
   'Albert'  'Bert'
   'Chuck'  'Donna'
   'Chuck'  'Eddie'
   'Chuck'  'Fred'

2) Mark all

    NULL     'Albert'
   'Albert'  'Chuck'
   'Albert'  'Bert'
   'Chuck'  'Donna'
   'Chuck'  'Eddie'
   'Chuck'  'Fred'
   'Bert'     NULL
   'Donna'    NULL
   'Eddie'    NULL
   'Fred'     NULL

plus the two above.

> >> Second, if you reorganize the model into 2 tables: nodes and links,
> then there would be no difference between both your representations
> (and plus, there would be no NULLs). <<
> That is not what I mean. The organizational chart is not the same
> thing as the personnel who hold those positions. Albert might be the
> president of the company, but when he gets fired, the office of the
> president is still there, only it is vacant. If I have personnel
> separated from the organizational structure, I can have one person
> hold two jobs, show vacant positions, etc.

I can't see why an org chart is not best represented by seperate node and link tables.

> The mild advantage of a child-up adjacency list model is when you have
> a tree that grows down from leaf nodes -- I can immediately find and
> update a leaf node with an IS NULL predicate.

'Parent-down' has the advantage of having a nice key

   CREATE TABLE Parent_Down_Tree
   (parent_id CHAR (8), -- null means child is the root     child_id CHAR(8) NOT NULL,
   PRIMARY KEY(child_id));

Paul Vernon
Business Intelligence, IBM Global Services Received on Wed Feb 12 2003 - 11:36:02 CET

Original text of this message