Re: double linked list

>> First, there are missing links in your data ... <<

ARRGGH! Let me try again:

  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'

  'Bert'    'Chuck'

  'Albert'  'Chuck' 

  'Chuck'   'Donna'

  CREATE TABLE Child_Up_Tree
  (parent_id CHAR (8) NOT NULL,
   child_id CHAR(8)); -- null means child is a leaf

  parent child

>> 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.

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.

>> for arbitrary graphs ... <<

I am only concerned with trees in these models. The adjacency list (or perhaps an adjacency array) would be the way to do an arbitrary graph. I would say that it is too easy to accidently do an arbitrary graph in the adjacency list model and that people forget to put all of the constraints they need to assure that they have a tree.

>> There is only one adjacency model simply because there is only one adjacency matrix definition in graph theory. The fact that we can consider transposed adjacency matrix too is not important. <<

Only if you are a programmer <g> Received on Wed Feb 12 2003 - 06:01:28 CET