Re: Nested Sets Insertion

Hi,
I had a question regarding the nested set idea. Can we use another approach for such tree problems? We can assign each node two numbers (preorder,postorder). preorder is the number in preorder traversal and postorder is the postorder traversal number. Then, a node i is a descendant of node j if preorder(i) < preorder(j) and postorder(i) > postorder(j). This handles the queries in pretty much the same way as the nested set model.

Any thoughts?

Regards,
San

71062.1056_at_compuserve.com (--CELKO--) wrote in message news:<c0d87ec0.0305101916.3a6f873d_at_posting.google.com>...
> >> INSERT and UPDATE statements that can append a child to a node and
> update the left and right values of the affected nodes. <<
>
> The nested set model has an implied ordering of siblings which the
> adjacency list model does not. To insert a new node, G1, under part G.
> We can insert one node at a time like this:
>
> BEGIN ATOMIC
> DECLARE rightmost_spread INTEGER;
>
> SET rightmost_spread
> = (SELECT rgt
> FROM Frammis
> WHERE part = 'G');
> UPDATE Frammis
> SET lft = CASE WHEN lft > rightmost_spread
> THEN lft + 2
> ELSE lft END,
> rgt = CASE WHEN rgt >= rightmost_spread
> THEN rgt + 2
> ELSE rgt END
> WHERE rgt >= rightmost_spread;
>
> INSERT INTO Frammis (part, lft, rgt)
> VALUES ('G1', rightmost_spread, (rightmost_spread + 1));
> COMMIT WORK;
> END;
>
> The idea is to spread the lft and rgt numbers after the youngest child
> of the parent, G in this case, over by two to make room for the new
> addition, G1. This procedure will add the new node to the rightmost
> child position, which helps to preserve the idea of an age order among
> the siblings.
>
> To convert a nested sets model into an adjacency list model:
>
> SELECT B.emp AS boss, P.emp
> FROM OrgChart AS P
> LEFT OUTER JOIN
> OrgChart AS B
> ON B.lft
> = (SELECT MAX(lft)
> FROM OrgChart AS S
> WHERE P.lft > S.lft
> AND P.lft < S.rgt);
Received on Tue May 13 2003 - 15:47:29 CEST