Home -> Usenet -> comp.databases.theory -> Re: Proper siblings sorting in nested sets model

Re: Proper siblings sorting in nested sets model

From: John Gilson <jag_at_acm.org>
Date: Tue, 27 Apr 2004 04:27:41 GMT
Message-ID: <1jljc.46077$Nn4.10021247_at_twister.nyc.rr.com> 






"Pavel Schevaev" <pacha_shevaev_at_mail.ru> wrote in message
news:320b3b2.0404090545.692729f1_at_posting.google.com...


> Nested sets are just great and i've been using it for quite a while

> already.

> The only inconvenience that popped up lately was that it seems like

> it's impossible to order node siblings by some arbitrary parameter,

> say, alphabetically, in sigle query without any vendor-specific stuff.

>

> Oracle10g supports such sorting, even without nested sets(of course we

> can't afford it):

>

> SELECT LEVEL, LPAD('  ',2*(LEVEL - 1)) || EMP_NAME "EMPLOYEE", EMP_ID,


> MGR_IDFROM EMPLOYEESTART WITH EMP_ID = 7839CONNECT BY PRIOR EMP_ID =


> MGR_IDORDER SIBLINGS BY EMP_NAME;


> LEVEL EMPLOYEE                 EMP_ID     MGR_ID


> ----- -------------------- ---------- ----------

>     1 KING                       7839


>     2   BLAKE                    7698       7839


>     3     ALLEN                  7499       7698


>     3     JAMES                  7900       7698


>     3     MARTIN                 7654       7698


>     3     TURNER                 7844       7698


>     3     WARD                   7521       7698


>     2   CLARK                    7782       7839


>     3     MILLER                 7934       7782


>     2   JONES                    7566       7839


>     3     FORD                   7902       7566


>     4       SMITH                7369       7902


>     3     SCOTT                  7788       7566


>     4       ADAMS                7876       7788


>

> (if above ascii art is messed up here's the link

> http://www.dbazine.com/mishra3.shtml)

>

> Probably there's someone who faced the same problem already and got a

> solution?




The idea is to assign a sequence number to each node which is in
accordance with the ordering desired, i.e., an ORDER BY on the
sequence number column will return the nodes in the required order.



To find the sequence number of a given node N, gather together the set
A which is comprised of node N and each of its ancestor nodes.  Let's
refer to the cardinality of set A as |A|.  For each node "a" in A:



    
  
  1.   Find each sibling node S of node "a" that meets the specified
ordering, e.g., all siblings less than the node "a".

  
  2.   For each sibling node S, count the sibling node S and all of its
descendants to get count C.

  
  3.   Sum all the counts C and add to |A| and this becomes the sequence
number for node N.






CREATE TABLE Tree


(


node_value INT NOT NULL PRIMARY KEY,


left_value INT NOT NULL UNIQUE,


right_value INT NOT NULL UNIQUE,


CHECK (right_value > left_value)


)



    
  
  •   All paths for tree along with path length
CREATE VIEW PathsToRoot (from_node_value, from_node_left, from_node_right,
                                                  path_node_value, path_node_left, path_node_right,
                                                  path_edges_tally)
AS
SELECT T1.node_value, T1.left_value, T1.right_value,
               T2.node_value, T2.left_value, T2.right_value,
               COUNT(T3.node_value)
FROM Tree AS T1
            INNER JOIN

            Tree AS T2
            ON T2.left_value <= T1.left_value AND
                  T2.right_value >= T1.right_value
            LEFT OUTER JOIN

            Tree AS T3
            ON T3.left_value < T1.left_value AND
                   T3.left_value >= T2.left_value AND
                   T3.right_value > T1.right_value AND
                   T3.right_value <= T2.right_value
GROUP BY T1.node_value, T1.left_value, T1.right_value,
                     T2.node_value, T2.left_value, T2.right_value

  
  •   For each node, all sibling nodes
CREATE VIEW Siblings (node_value,
                                          node_left, node_right,
                                          sibling_node_value,
                                          sibling_node_left, sibling_node_right)
AS
SELECT SP1.from_node_value, SP1.from_node_left, SP1.from_node_right,
               SP2.from_node_value, SP2.from_node_left, SP2.from_node_right
FROM PathsToRoot AS SP1
            INNER JOIN

            PathsToRoot AS SP2
            ON SP1.from_node_value <> SP2.from_node_value AND
                   SP1.path_node_value = SP2.path_node_value AND
                   SP1.path_edges_tally = 1 AND
                   SP2.path_edges_tally = 1

  
  •   Sequence number of nodes when using nested set model with no gaps
CREATE VIEW OrderedNodes (node_value, sequence_number)
AS
SELECT P.from_node_value,
               SUM(COALESCE((S.sibling_node_right - S.sibling_node_left) / 2 + 1, 0))
               + COUNT(DISTINCT P.path_node_value)
FROM PathsToRoot AS P
            LEFT OUTER JOIN

            Siblings AS S
            ON S.node_value = P.path_node_value AND
                   S.sibling_node_value < P.path_node_value -- ordering constraint
GROUP BY P.from_node_value

  
  •   Sequence number of nodes when using nested set model with gaps
CREATE VIEW OrderedNodesWhenGaps (node_value, sequence_number)
AS
SELECT P.from_node_value,
               COUNT(SP.path_node_value) + COUNT(DISTINCT P.path_node_value)
FROM PathsToRoot AS P
            LEFT OUTER JOIN

            Siblings AS S
            ON S.node_value = P.path_node_value AND
                   S.sibling_node_value < P.path_node_value -- ordering constraint
            LEFT OUTER JOIN

            PathsToRoot AS SP
            ON SP.path_node_value = S.sibling_node_value
GROUP BY P.from_node_value

  
  •   Sample tree encoded with nested set model with no gaps
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (5, 1, 30)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (12, 2, 9)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (6, 3, 4)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (3, 5, 6)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (7, 7, 8)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (10, 10, 23)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (2, 11, 12)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (13, 13, 14)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (17, 15, 16)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (1, 17, 22)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (9, 18, 19)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (4, 20, 21)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (18, 24, 29)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (25, 25, 26)

INSERT INTO Tree (node_value, left_value, right_value)
VALUES (20, 27, 28)





SELECT node_value, sequence_number


FROM OrderedNodes


ORDER BY sequence_number ASC



node_value sequence_number

5                 1
10               2
1                 3
4                 4
9                 5
2                 6
13               7
17               8
12               9
3                 10
6                 11
7                 12
18               13
20               14
25               15




--
JAG


Received on Tue Apr 27 2004 - 06:27:41 CEST












Original text of this message