Re: Is this possible w/o a stored procedure?

From: Philip Lijnzaad <lijnzaad_at_ebi.ac.uk>
Date: 2000/06/20
Message-ID: <u7u2eo91jv.fsf_at_o2-3.ebi.ac.uk>#1/1

>>> Also, please ignore the comments in Mr. Celko's posting about

Joe> normalization. I believe those comments are simply wrong.  He suggests
Joe> that, under some notion of normalization, the nested set model is
Joe> normalized while the standard adjacency model (as shown by the original
Joe> poster) is not. <<

Joe> The basic characteristic of a normalized table is that it is free from
Joe> anomalies.  One fact, one place, one time.  A table is a set; a set is

Joe> a collection made up of one kind of thing. The adjacency list model Joe> holds both structure and elements,

no, not if you normalize it into two tables

create table tree_topology (node_id number primary key

                            parent_id number);

create table node_contents (employee_id number,
                            node_id number references tree_topology(node_id));

You can update node_contents and tree_topology independently (as long as the primary and foreign keys are satisfied and meaningful).

Joe> When you update the adjacency list model, you have to repeat updates Joe> for the same entity as both a subordinate and superior.

no, it depends on your application. In biology, it's not uncommon to have to change parts of the Tree of Life by simply moving one node and its whole subtree. E.g., the Ctenosquamata may first be classified as a sub-group of the Eurypterygii, but new evidence might place it under the Neoteleostei. In taxonomy, this is a natural and atomic operation; it's perfectly normalized, because one fact (Ctenosquamata are a direct child of Eurypterygii) is recorded one time and place only (in the parent_id of Ctenosquamata). The 'fact' that Ctenosquamata has Actinopterygii somewhere higher up in the tree is derived a chain of these direct adjacencies. One could in fact argue that the nested set model in fact records too much information!

Joe> When you delete a node from the adjacency list model, you destroy Joe> subordination (i.e. daggling trees),

yes, this is true.

Joe> while nested set preserve
Joe> subordination, which is shown by containment.

But after deleting a sub-tree, you still have to re-enumerate the nested sets. And inserting or moving a sub-tree is simply cumbersome.

                                                                      Philip

-- 
Ban GM foods! Long live the Mesolithicum, pesticides and starvation
-----------------------------------------------------------------------------
Philip Lijnzaad, lijnzaad_at_ebi.ac.uk \ European Bioinformatics Institute,rm A2-24
+44 (0)1223 49 4639                 / Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax)           \ Cambridgeshire CB10 1SD,  GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC  50 3D 1F 64 40 75 FB 53

Received on Tue Jun 20 2000 - 00:00:00 CEST