Re: Bill of materials / Groups in Groups

joe_celko_at_my-deja.com wrote:
>
> CREATE TABLE Personnel
> (emp CHAR(10) PRIMARY KEY,
> boss CHAR(10), -- unneed & denormalizes the table
> salary DECIMAL(6,2) NOT NULL,
> lft INTEGER NOT NULL,
> rgt INTEGER NOT NULL);
>
> Personnel
> emp boss salary lft rgt
> ===================================
> Albert NULL 1000.00 1 12
> Bert Albert 900.00 2 3
> Chuck Albert 900.00 4 11
> Donna Chuck 800.00 5 6
> Eddie Chuck 700.00 7 8
> Fred Chuck 600.00 9 10
>
> column in a normalized table. To prove that this is not normalized,
> assume that "Chuck" changes his name to "Charles"; you have to change
> his name in both columns and several places. The defining
> characteristic of a normalized table is that you have one fact, one
> place, one time.

The Personnel table is not normalized because there is a functional dependency between the person and the persons name. Change the table to the following to be normalized. The limitation of databases to handle these types of tables says more about the implementation than about the table layout.

Personnel
key name boss salary

 1   Albert NULL     1000.00 
 2   Bert    1        900.00 
 3   Chuck   1        900.00 
 4   Donna   3        800.00 
 5   Eddie   3        700.00 
 6   Fred    3        600.00 

The above table is normal, WRT the information provided. It is also the most elegant table design; unfortunate that database implementations can not handle this common scenario.

> To show a tree as nested sets, replace the nodes with ovals, then nest
> subordinate ovals inside each other. The root will be the largest oval
> and will contain every other node. The leaf nodes will be the
> innermost ovals with nothing else inside them and the nesting will show
> the hierarchical relationship. The rgt and lft columns (I cannot use
> the reserved words LEFT and RIGHT in SQL) are what shows the nesting.

This is an interesting solution, but it is only good for directed graphs without cycles, and limited to 2 dimensions.

Example, hierarchy defined when many bosses, for a single employee, is possible.

Personnel		Management Relation
key  name   		key  Boss  Employee
===========		===================
 1   Albert              A    1      4
 2   Bert                B    1      5
 3   Chuck               C    1      6
 4   Donna               D    1      7
 5   Eddie               E    2      5
 6   Fred                F    2      7
 7   Roger               G    2      8
 8   Bernie              H    2      9
 9   Kyle                I    3      6 
10   Rhonda              J    3      7
                         K    3      9
                         L    3     10

The above simply is equivalent to a three sets, all sharing a single employee (5), each pair with a shared employee (5, 6, 9) and an exclusive employee each (4, 8 10). Notice that this can not be mapped to the method you proposed. The hierarchy defined must have an overlapping edge (not 2D).

With cyclic graphs information is lost about the relationship between the nodes.

Personnel		Management Relation
key  name   		key  Boss  Employee
===========		===================
 1   Albert              A    1      2
 2   Bert                B    2      1
 3   Chuck               C    1      3
 4   Donna               D    2      4

The best that could be done is to map all 4 personnel to a single range.

You may not have meant for you method to be applied to these situations. I only bring them up to show that the simple hierarchy is just a restricted case of the Personnel-Management Relation tables above. Therefore its structure should be just as simple, if not simpler.

Last, the table design you propose is not normal because there is a functional dependency between the LFT and RHT columns; LFT<=RHT at all times.
Fix it by replacing RHT with DELTA=RHT-LFT. Received on Sun Jan 09 2000 - 00:00:00 CET